9018ab8c14a2ab2c8425bdbf9d398f5bd8fdf27c
[blender-staging.git] / source / blender / bmesh / intern / bmesh_queries.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Joseph Eagar, Geoffrey Bantle, Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/intern/bmesh_queries.c
24  *  \ingroup bmesh
25  *
26  * This file contains functions for answering common
27  * Topological and geometric queries about a mesh, such
28  * as, "What is the angle between these two faces?" or,
29  * "How many faces are incident upon this vertex?" Tool
30  * authors should use the functions in this file instead
31  * of inspecting the mesh structure directly.
32  */
33
34 #include <string.h>
35
36 #include "bmesh.h"
37 #include "bmesh_private.h"
38
39 #include "BKE_utildefines.h"
40
41 #include "BLI_math.h"
42 #include "BLI_utildefines.h"
43
44 #define BM_OVERLAP (1 << 13)
45
46 /*
47  * BMESH COUNT ELEMENT
48  *
49  * Return the amount of element of
50  * type 'type' in a given bmesh.
51  */
52
53 int BM_Count_Element(BMesh *bm, const char htype)
54 {
55         if (htype == BM_VERT) return bm->totvert;
56         else if (htype == BM_EDGE) return bm->totedge;
57         else if (htype == BM_FACE) return bm->totface;
58
59         return 0;
60 }
61
62
63 /*
64  * BMESH VERT IN EDGE
65  *
66  * Returns whether or not a given vertex is
67  * is part of a given edge.
68  *
69  */
70
71 int BM_Vert_In_Edge(BMEdge *e, BMVert *v)
72 {
73         return bmesh_vert_in_edge(e, v);
74 }
75
76 /*
77  * BMESH OTHER EDGE IN FACE SHARING A VERTEX
78  *
79  * Returns an opposing loop that shares the same face.
80  *
81  */
82
83 BMLoop *BM_OtherFaceLoop(BMEdge *e, BMFace *f, BMVert *v)
84 {
85         BMLoop *l_iter;
86         BMLoop *l_first;
87
88         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
89         
90         do {
91                 if (l_iter->e == e) {
92                         break;
93                 }
94         } while ((l_iter = l_iter->next) != l_first);
95         
96         return l_iter->v == v ? l_iter->prev : l_iter->next;
97 }
98
99 /*
100  * BMESH VERT IN FACE
101  *
102  * Returns whether or not a given vertex is
103  * is part of a given face.
104  *
105  */
106
107 int BM_Vert_In_Face(BMFace *f, BMVert *v)
108 {
109         BMLoopList *lst;
110         BMLoop *l_iter;
111
112         for (lst = f->loops.first; lst; lst = lst->next) {
113                 l_iter = lst->first;
114                 do {
115                         if (l_iter->v == v) {
116                                 return TRUE;
117                         }
118                 } while ((l_iter = l_iter->next) != lst->first);
119         }
120
121         return FALSE;
122 }
123
124 /*
125  * BMESH VERTS IN FACE
126  *
127  * Compares the number of vertices in an array
128  * that appear in a given face
129  *
130  */
131 int BM_Verts_In_Face(BMesh *bm, BMFace *f, BMVert **varr, int len)
132 {
133         BMLoopList *lst;
134         BMLoop *curloop = NULL;
135         int i, count = 0;
136         
137         for (i = 0; i < len; i++) BMO_SetFlag(bm, varr[i], BM_OVERLAP);
138         
139         for (lst = f->loops.first; lst; lst = lst->next) {
140                 curloop = lst->first;
141
142                 do {
143                         if (BMO_TestFlag(bm, curloop->v, BM_OVERLAP))
144                                 count++;
145
146                         curloop = curloop->next;
147                 } while (curloop != lst->first);
148         }
149
150         for (i = 0; i < len; i++) BMO_ClearFlag(bm, varr[i], BM_OVERLAP);
151
152         return count;
153 }
154
155 /*
156  * BMESH EDGE IN FACE
157  *
158  * Returns whether or not a given edge is
159  * is part of a given face.
160  *
161  */
162
163 int BM_Edge_In_Face(BMFace *f, BMEdge *e)
164 {
165         BMLoop *l_iter;
166         BMLoop *l_first;
167
168         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
169
170         do {
171                 if (l_iter->e == e) {
172                         return TRUE;
173                 }
174         } while ((l_iter = l_iter->next) != l_first);
175
176         return FALSE;
177 }
178
179 /*
180  * BMESH VERTS IN EDGE
181  *
182  * Returns whether or not two vertices are in
183  * a given edge
184  *
185  */
186
187 int BM_Verts_In_Edge(BMVert *v1, BMVert *v2, BMEdge *e)
188 {
189         return bmesh_verts_in_edge(v1, v2, e);
190 }
191
192 /*
193  * BMESH GET OTHER EDGEVERT
194  *
195  * Given a edge and one of its vertices, returns
196  * the other vertex.
197  *
198  */
199
200 BMVert *BM_OtherEdgeVert(BMEdge *e, BMVert *v)
201 {
202         return bmesh_edge_getothervert(e, v);
203 }
204
205 /*
206  *  BMESH VERT EDGECOUNT
207  *
208  *      Returns the number of edges around this vertex.
209  */
210
211 int BM_Vert_EdgeCount(BMVert *v)
212 {
213         return bmesh_disk_count(v);
214 }
215
216 /*
217  *  BMESH EDGE FACECOUNT
218  *
219  *      Returns the number of faces around this edge
220  */
221
222 int BM_Edge_FaceCount(BMEdge *e)
223 {
224         int count = 0;
225         BMLoop *curloop = NULL;
226
227         if (e->l) {
228                 curloop = e->l;
229                 do {
230                         count++;
231                         curloop = bmesh_radial_nextloop(curloop);
232                 } while (curloop != e->l);
233         }
234
235         return count;
236 }
237
238 /*
239  *  BMESH VERT FACECOUNT
240  *
241  *      Returns the number of faces around this vert
242  */
243
244 int BM_Vert_FaceCount(BMVert *v)
245 {
246         int count = 0;
247         BMLoop *l;
248         BMIter iter;
249
250         BM_ITER(l, &iter, NULL, BM_LOOPS_OF_VERT, v)
251                 count++;
252
253         return count;
254 #if 0 //this code isn't working
255         BMEdge *curedge = NULL;
256
257         if (v->e) {
258                 curedge = v->e;
259                 do {
260                         if (curedge->l) count += BM_Edge_FaceCount(curedge);
261                         curedge = bmesh_disk_nextedge(curedge, v);
262                 } while (curedge != v->e);
263         }
264         return count;
265 #endif
266 }
267
268 /*
269  *                      BMESH WIRE VERT
270  *
271  *      Tests whether or not the vertex is part of a wire edge.
272  *  (ie: has no faces attached to it)
273  *
274  *  Returns -
275  *      1 for true, 0 for false.
276  */
277
278 int BM_Wire_Vert(BMesh *UNUSED(bm), BMVert *v)
279 {
280         BMEdge *curedge;
281
282         if (v->e == NULL) {
283                 return FALSE;
284         }
285         
286         curedge = v->e;
287         do {
288                 if (curedge->l) {
289                         return FALSE;
290                 }
291
292                 curedge = bmesh_disk_nextedge(curedge, v);
293         } while (curedge != v->e);
294
295         return TRUE;
296 }
297
298 /*
299  *                      BMESH WIRE EDGE
300  *
301  *      Tests whether or not the edge is part of a wire.
302  *  (ie: has no faces attached to it)
303  *
304  *  Returns -
305  *      1 for true, 0 for false.
306  */
307
308 int BM_Wire_Edge(BMesh *UNUSED(bm), BMEdge *e)
309 {
310         return (e->l) ? FALSE : TRUE;
311 }
312
313 /*
314  *                      BMESH NONMANIFOLD VERT
315  *
316  *  A vertex is non-manifold if it meets the following conditions:
317  *    1: Loose - (has no edges/faces incident upon it)
318  *    2: Joins two distinct regions - (two pyramids joined at the tip)
319  *    3: Is part of a non-manifold edge (edge with more than 2 faces)
320  *    4: Is part of a wire edge
321  *
322  *  Returns -
323  *      1 for true, 0 for false.
324  */
325
326 int BM_Nonmanifold_Vert(BMesh *UNUSED(bm), BMVert *v)
327 {
328         BMEdge *e, *oe;
329         BMLoop *l;
330         int len, count, flag;
331
332         if (v->e == NULL) {
333                 /* loose vert */
334                 return TRUE;
335         }
336
337         /* count edges while looking for non-manifold edges */
338         oe = v->e;
339         for (len = 0, e = v->e; e != oe || (e == oe && len == 0); len++, e = bmesh_disk_nextedge(e, v)) {
340                 if (e->l == NULL) {
341                         /* loose edge */
342                         return TRUE;
343                 }
344
345                 if (bmesh_radial_length(e->l) > 2) {
346                         /* edge shared by more than two faces */
347                         return TRUE;
348                 }
349         }
350
351         count = 1;
352         flag = 1;
353         e = NULL;
354         oe = v->e;
355         l = oe->l;
356         while (e != oe) {
357                 l = (l->v == v) ? l->prev : l->next;
358                 e = l->e;
359                 count++; /* count the edges */
360
361                 if (flag && l->radial_next == l) {
362                         /* we've hit the edge of an open mesh, reset once */
363                         flag = 0;
364                         count = 1;
365                         oe = e;
366                         e = NULL;
367                         l = oe->l;
368                 }
369                 else if (l->radial_next == l) {
370                         /* break the loop */
371                         e = oe;
372                 }
373                 else {
374                         l = l->radial_next;
375                 }
376         }
377
378         if (count < len) {
379                 /* vert shared by multiple regions */
380                 return TRUE;
381         }
382
383         return FALSE;
384 }
385
386 /*
387  *                      BMESH NONMANIFOLD EDGE
388  *
389  *      Tests whether or not this edge is manifold.
390  *  A manifold edge either has 1 or 2 faces attached
391  *      to it.
392  *
393  *  Returns -
394  *      1 for true, 0 for false.
395  */
396
397 int BM_Nonmanifold_Edge(BMesh *UNUSED(bm), BMEdge *e)
398 {
399         int count = BM_Edge_FaceCount(e);
400         if (count != 2 && count != 1) {
401                 return TRUE;
402         }
403         return FALSE;
404 }
405
406 /*
407  *                      BMESH BOUNDARY EDGE
408  *
409  *      Tests whether or not an edge is on the boundary
410  *  of a shell (has one face associated with it)
411  *
412  *  Returns -
413  *      1 for true, 0 for false.
414  */
415
416 int BM_Boundary_Edge(BMEdge *e)
417 {
418         int count = BM_Edge_FaceCount(e);
419         if (count == 1) {
420                 return TRUE;
421         }
422         return FALSE;
423 }
424
425 /*
426  *                      BMESH FACE SHAREDEDGES
427  *
428  *  Counts the number of edges two faces share (if any)
429  *
430  *  BMESH_TODO:
431  *    Move this to structure, and wrap.
432  *
433  *  Returns -
434  *      Integer
435  */
436
437 int BM_Face_Share_Edges(BMFace *f1, BMFace *f2)
438 {
439         BMLoop *l_iter;
440         BMLoop *l_first;
441         int count = 0;
442         
443         l_iter = l_first = BM_FACE_FIRST_LOOP(f1);
444         do {
445                 if (bmesh_radial_find_face(l_iter->e, f2)) {
446                         count++;
447                 }
448         } while ((l_iter = l_iter->next) != l_first);
449
450         return count;
451 }
452
453 /*
454  *
455  *           BMESH EDGE SHARE FACES
456  *
457  *      Tests to see if e1 shares any faces with e2
458  *
459  */
460
461 int BM_Edge_Share_Faces(BMEdge *e1, BMEdge *e2)
462 {
463         BMLoop *l;
464         BMFace *f;
465
466         if (e1->l && e2->l) {
467                 l = e1->l;
468                 do {
469                         f = l->f;
470                         if (bmesh_radial_find_face(e2, f)) {
471                                 return TRUE;
472                         }
473                         l = l->radial_next;
474                 } while (l != e1->l);
475         }
476         return FALSE;
477 }
478
479 /**
480  *
481  *           BMESH EDGE SHARE A VERTEX
482  *
483  *      Tests to see if e1 shares a vertex with e2
484  *
485  */
486
487 int BM_Edge_Share_Vert(struct BMEdge *e1, struct BMEdge *e2)
488 {
489         return (e1->v1 == e2->v1 ||
490                 e1->v1 == e2->v2 ||
491                 e1->v2 == e2->v1 ||
492                 e1->v2 == e2->v2);
493 }
494
495 /**
496  *
497  *           BMESH EDGE ORDERED VERTS
498  *
499  *      Returns the verts of an edge as used in a face
500  *  if used in a face at all, otherwise just assign as used in the edge.
501  *
502  *  Useful to get a determanistic winding order when calling
503  *  BM_Make_Ngon() on an arbitrary array of verts,
504  *  though be sure to pick an edge which has a face.
505  *
506  */
507
508 void BM_Edge_OrderedVerts(BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
509 {
510         if ( (edge->l == NULL) ||
511              ( ((edge->l->prev->v == edge->v1) && (edge->l->v == edge->v2)) ||
512                ((edge->l->v == edge->v1) && (edge->l->next->v == edge->v2)) )
513              )
514         {
515                 *r_v1 = edge->v1;
516                 *r_v2 = edge->v2;
517         }
518         else {
519                 *r_v1 = edge->v2;
520                 *r_v2 = edge->v1;
521         }
522 }
523
524 /**
525  *                      BMESH FACE ANGLE
526  *
527  *  Calculates the angle between two faces. Assumes
528  *  That face normals are correct.
529  *
530  *  Returns -
531  *      Float.
532  */
533
534 float BM_Face_Angle(BMesh *UNUSED(bm), BMEdge *e)
535 {
536         if (BM_Edge_FaceCount(e) == 2) {
537                 BMLoop *l1 = e->l;
538                 BMLoop *l2 = e->l->radial_next;
539                 return acosf(dot_v3v3(l1->f->no, l2->f->no));
540         }
541         else {
542                 return (float)M_PI / 2.0f; /* acos(0.0) */
543         }
544 }
545
546 /*
547  * BMESH EXIST FACE OVERLAPS
548  *
549  * Given a set of vertices (varr), find out if
550  * all those vertices overlap an existing face.
551  *
552  * Returns:
553  * 0 for no overlap
554  * 1 for overlap
555  *
556  *
557  */
558
559 int BM_Exist_Face_Overlaps(BMesh *bm, BMVert **varr, int len, BMFace **overlapface)
560 {
561         BMIter vertfaces;
562         BMFace *f;
563         int i, amount;
564
565         if (overlapface) *overlapface = NULL;
566
567         for (i = 0; i < len; i++) {
568                 f = BMIter_New(&vertfaces, bm, BM_FACES_OF_VERT, varr[i]);
569                 while (f) {
570                         amount = BM_Verts_In_Face(bm, f, varr, len);
571                         if (amount >= len) {
572                                 if (overlapface) *overlapface = f;
573                                 return TRUE;
574                         }
575                         f = BMIter_Step(&vertfaces);
576                 }
577         }
578         return FALSE;
579 }
580
581 /*
582  * BMESH FACE EXISTS
583  *
584  * Given a set of vertices (varr), find out if
585  * there is a face with exactly those vertices
586  * (and only those vertices).
587  *
588  * Returns:
589  * 0 for no face found
590  * 1 for face found
591  */
592
593 int BM_Face_Exists(BMesh *bm, BMVert **varr, int len, BMFace **existface)
594 {
595         BMIter vertfaces;
596         BMFace *f;
597         int i, amount;
598
599         if (existface) *existface = NULL;
600
601         for (i = 0; i < len; i++) {
602                 f = BMIter_New(&vertfaces, bm, BM_FACES_OF_VERT, varr[i]);
603                 while (f) {
604                         amount = BM_Verts_In_Face(bm, f, varr, len);
605                         if (amount == len && amount == f->len) {
606                                 if (existface) *existface = f;
607                                 return TRUE;
608                         }
609                         f = BMIter_Step(&vertfaces);
610                 }
611         }
612         return FALSE;
613 }