bmesh api name change, add _count suffix for BM_*_share functions.
[blender.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 "BLI_math.h"
35
36 #include "bmesh.h"
37 #include "bmesh_private.h"
38
39 #define BM_OVERLAP (1 << 13)
40
41 /*
42  * BMESH COUNT ELEMENT
43  *
44  * Return the amount of element of
45  * type 'type' in a given bmesh.
46  */
47
48 int BM_mesh_elem_count(BMesh *bm, const char htype)
49 {
50         if (htype == BM_VERT) return bm->totvert;
51         else if (htype == BM_EDGE) return bm->totedge;
52         else if (htype == BM_FACE) return bm->totface;
53
54         return 0;
55 }
56
57
58 /*
59  * BMESH VERT IN EDGE
60  *
61  * Returns whether or not a given vertex is
62  * is part of a given edge.
63  *
64  */
65
66 int BM_vert_in_edge(BMEdge *e, BMVert *v)
67 {
68         return bmesh_vert_in_edge(e, v);
69 }
70
71 /*
72  * BMESH OTHER EDGE IN FACE SHARING A VERTEX
73  *
74  * Returns an opposing loop that shares the same face.
75  *
76  */
77
78 BMLoop *BM_face_other_loop(BMEdge *e, BMFace *f, BMVert *v)
79 {
80         BMLoop *l_iter;
81         BMLoop *l_first;
82
83         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
84         
85         do {
86                 if (l_iter->e == e) {
87                         break;
88                 }
89         } while ((l_iter = l_iter->next) != l_first);
90         
91         return l_iter->v == v ? l_iter->prev : l_iter->next;
92 }
93
94 /*
95  * BMESH VERT IN FACE
96  *
97  * Returns whether or not a given vertex is
98  * is part of a given face.
99  *
100  */
101
102 int BM_vert_in_face(BMFace *f, BMVert *v)
103 {
104         BMLoop *l_iter, *l_first;
105
106 #ifdef USE_BMESH_HOLES
107         BMLoopList *lst;
108         for (lst = f->loops.first; lst; lst = lst->next)
109 #endif
110         {
111 #ifdef USE_BMESH_HOLES
112                 l_iter = l_first = lst->first;
113 #else
114                 l_iter = l_first = f->l_first;
115 #endif
116                 do {
117                         if (l_iter->v == v) {
118                                 return TRUE;
119                         }
120                 } while ((l_iter = l_iter->next) != l_first);
121         }
122
123         return FALSE;
124 }
125
126 /*
127  * BMESH VERTS IN FACE
128  *
129  * Compares the number of vertices in an array
130  * that appear in a given face
131  *
132  */
133 int BM_verts_in_face(BMesh *bm, BMFace *f, BMVert **varr, int len)
134 {
135         BMLoop *l_iter, *l_first;
136
137 #ifdef USE_BMESH_HOLES
138         BMLoopList *lst;
139 #endif
140
141         int i, count = 0;
142         
143         for (i = 0; i < len; i++) {
144                 BMO_elem_flag_enable(bm, varr[i], BM_OVERLAP);
145         }
146
147 #ifdef USE_BMESH_HOLES
148         for (lst = f->loops.first; lst; lst = lst->next)
149 #endif
150         {
151
152 #ifdef USE_BMESH_HOLES
153                 l_iter = l_first = lst->first;
154 #else
155                 l_iter = l_first = f->l_first;
156 #endif
157
158                 do {
159                         if (BMO_elem_flag_test(bm, l_iter->v, BM_OVERLAP)) {
160                                 count++;
161                         }
162
163                 } while ((l_iter = l_iter->next) != l_first);
164         }
165
166         for (i = 0; i < len; i++) BMO_elem_flag_disable(bm, varr[i], BM_OVERLAP);
167
168         return count;
169 }
170
171 /*
172  * BMESH EDGE IN FACE
173  *
174  * Returns whether or not a given edge is
175  * is part of a given face.
176  *
177  */
178
179 int BM_edge_in_face(BMFace *f, BMEdge *e)
180 {
181         BMLoop *l_iter;
182         BMLoop *l_first;
183
184         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
185
186         do {
187                 if (l_iter->e == e) {
188                         return TRUE;
189                 }
190         } while ((l_iter = l_iter->next) != l_first);
191
192         return FALSE;
193 }
194
195 /*
196  * BMESH VERTS IN EDGE
197  *
198  * Returns whether or not two vertices are in
199  * a given edge
200  *
201  */
202
203 int BM_verts_in_edge(BMVert *v1, BMVert *v2, BMEdge *e)
204 {
205         return bmesh_verts_in_edge(v1, v2, e);
206 }
207
208 /*
209  * BMESH GET OTHER EDGEVERT
210  *
211  * Given a edge and one of its vertices, returns
212  * the other vertex.
213  *
214  */
215
216 BMVert *BM_edge_other_vert(BMEdge *e, BMVert *v)
217 {
218         return bmesh_edge_getothervert(e, v);
219 }
220
221 /*
222  *  BMESH VERT EDGECOUNT
223  *
224  *      Returns the number of edges around this vertex.
225  */
226
227 int BM_vert_edge_count(BMVert *v)
228 {
229         return bmesh_disk_count(v);
230 }
231
232 /*
233  *  BMESH EDGE FACECOUNT
234  *
235  *      Returns the number of faces around this edge
236  */
237
238 int BM_edge_face_count(BMEdge *e)
239 {
240         int count = 0;
241         BMLoop *l_iter = NULL;
242
243         if (e->l) {
244                 l_iter = e->l;
245                 do {
246                         count++;
247                 } while ((l_iter = bmesh_radial_nextloop(l_iter)) != e->l);
248         }
249
250         return count;
251 }
252
253 /*
254  *  BMESH VERT FACECOUNT
255  *
256  *      Returns the number of faces around this vert
257  */
258
259 int BM_vert_face_count(BMVert *v)
260 {
261         int count = 0;
262         BMLoop *l;
263         BMIter iter;
264
265         BM_ITER(l, &iter, NULL, BM_LOOPS_OF_VERT, v) {
266                 count++;
267         }
268
269         return count;
270 #if 0 //this code isn't working
271         BMEdge *curedge = NULL;
272
273         if (v->e) {
274                 curedge = v->e;
275                 do {
276                         if (curedge->l) count += BM_edge_face_count(curedge);
277                         curedge = bmesh_disk_nextedge(curedge, v);
278                 } while (curedge != v->e);
279         }
280         return count;
281 #endif
282 }
283
284 /*
285  *                      BMESH WIRE VERT
286  *
287  *      Tests whether or not the vertex is part of a wire edge.
288  *  (ie: has no faces attached to it)
289  *
290  *  Returns -
291  *      1 for true, 0 for false.
292  */
293
294 int BM_vert_is_wire(BMesh *UNUSED(bm), BMVert *v)
295 {
296         BMEdge *curedge;
297
298         if (v->e == NULL) {
299                 return FALSE;
300         }
301         
302         curedge = v->e;
303         do {
304                 if (curedge->l) {
305                         return FALSE;
306                 }
307
308                 curedge = bmesh_disk_nextedge(curedge, v);
309         } while (curedge != v->e);
310
311         return TRUE;
312 }
313
314 /*
315  *                      BMESH WIRE EDGE
316  *
317  *      Tests whether or not the edge is part of a wire.
318  *  (ie: has no faces attached to it)
319  *
320  *  Returns -
321  *      1 for true, 0 for false.
322  */
323
324 int BM_edge_is_wire(BMesh *UNUSED(bm), BMEdge *e)
325 {
326         return (e->l) ? FALSE : TRUE;
327 }
328
329 /*
330  *                      BMESH NONMANIFOLD VERT
331  *
332  *  A vertex is non-manifold if it meets the following conditions:
333  *    1: Loose - (has no edges/faces incident upon it)
334  *    2: Joins two distinct regions - (two pyramids joined at the tip)
335  *    3: Is part of a non-manifold edge (edge with more than 2 faces)
336  *    4: Is part of a wire edge
337  *
338  *  Returns -
339  *      1 for true, 0 for false.
340  */
341
342 int BM_vert_is_manifold(BMesh *UNUSED(bm), BMVert *v)
343 {
344         BMEdge *e, *oe;
345         BMLoop *l;
346         int len, count, flag;
347
348         if (v->e == NULL) {
349                 /* loose vert */
350                 return FALSE;
351         }
352
353         /* count edges while looking for non-manifold edges */
354         oe = v->e;
355         for (len = 0, e = v->e; e != oe || (e == oe && len == 0); len++, e = bmesh_disk_nextedge(e, v)) {
356                 if (e->l == NULL) {
357                         /* loose edge */
358                         return FALSE;
359                 }
360
361                 if (bmesh_radial_length(e->l) > 2) {
362                         /* edge shared by more than two faces */
363                         return FALSE;
364                 }
365         }
366
367         count = 1;
368         flag = 1;
369         e = NULL;
370         oe = v->e;
371         l = oe->l;
372         while (e != oe) {
373                 l = (l->v == v) ? l->prev : l->next;
374                 e = l->e;
375                 count++; /* count the edges */
376
377                 if (flag && l->radial_next == l) {
378                         /* we've hit the edge of an open mesh, reset once */
379                         flag = 0;
380                         count = 1;
381                         oe = e;
382                         e = NULL;
383                         l = oe->l;
384                 }
385                 else if (l->radial_next == l) {
386                         /* break the loop */
387                         e = oe;
388                 }
389                 else {
390                         l = l->radial_next;
391                 }
392         }
393
394         if (count < len) {
395                 /* vert shared by multiple regions */
396                 return FALSE;
397         }
398
399         return TRUE;
400 }
401
402 /*
403  *                      BMESH NONMANIFOLD EDGE
404  *
405  *      Tests whether or not this edge is manifold.
406  *  A manifold edge either has 1 or 2 faces attached
407  *      to it.
408  *
409  *  Returns -
410  *      1 for true, 0 for false.
411  */
412
413 int BM_edge_is_manifold(BMesh *UNUSED(bm), BMEdge *e)
414 {
415         int count = BM_edge_face_count(e);
416         if (count != 2 && count != 1) {
417                 return FALSE;
418         }
419         return TRUE;
420 }
421
422 /*
423  *                      BMESH BOUNDARY EDGE
424  *
425  *      Tests whether or not an edge is on the boundary
426  *  of a shell (has one face associated with it)
427  *
428  *  Returns -
429  *      1 for true, 0 for false.
430  */
431
432 int BM_edge_is_boundary(BMEdge *e)
433 {
434         int count = BM_edge_face_count(e);
435         if (count == 1) {
436                 return TRUE;
437         }
438         return FALSE;
439 }
440
441 /*
442  *                      BMESH FACE SHAREDEDGES
443  *
444  *  Counts the number of edges two faces share (if any)
445  *
446  *  BMESH_TODO:
447  *    Move this to structure, and wrap.
448  *
449  *  Returns -
450  *      Integer
451  */
452
453 int BM_face_share_edge_count(BMFace *f1, BMFace *f2)
454 {
455         BMLoop *l_iter;
456         BMLoop *l_first;
457         int count = 0;
458         
459         l_iter = l_first = BM_FACE_FIRST_LOOP(f1);
460         do {
461                 if (bmesh_radial_find_face(l_iter->e, f2)) {
462                         count++;
463                 }
464         } while ((l_iter = l_iter->next) != l_first);
465
466         return count;
467 }
468
469 /*
470  *
471  *           BMESH EDGE SHARE FACES
472  *
473  *      Tests to see if e1 shares any faces with e2
474  *
475  */
476
477 int BM_edge_share_face_count(BMEdge *e1, BMEdge *e2)
478 {
479         BMLoop *l;
480         BMFace *f;
481
482         if (e1->l && e2->l) {
483                 l = e1->l;
484                 do {
485                         f = l->f;
486                         if (bmesh_radial_find_face(e2, f)) {
487                                 return TRUE;
488                         }
489                         l = l->radial_next;
490                 } while (l != e1->l);
491         }
492         return FALSE;
493 }
494
495 /**
496  *
497  *           BMESH EDGE SHARE A VERTEX
498  *
499  *      Tests to see if e1 shares a vertex with e2
500  *
501  */
502
503 int BM_edge_share_vert_count(struct BMEdge *e1, struct BMEdge *e2)
504 {
505         return (e1->v1 == e2->v1 ||
506                 e1->v1 == e2->v2 ||
507                 e1->v2 == e2->v1 ||
508                 e1->v2 == e2->v2);
509 }
510
511 /**
512  *
513  *           BMESH EDGE ORDERED VERTS
514  *
515  *      Returns the verts of an edge as used in a face
516  *  if used in a face at all, otherwise just assign as used in the edge.
517  *
518  *  Useful to get a determanistic winding order when calling
519  *  BM_face_create_ngon() on an arbitrary array of verts,
520  *  though be sure to pick an edge which has a face.
521  *
522  */
523
524 void BM_edge_ordered_verts(BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
525 {
526         if ( (edge->l == NULL) ||
527              ( ((edge->l->prev->v == edge->v1) && (edge->l->v == edge->v2)) ||
528                ((edge->l->v == edge->v1) && (edge->l->next->v == edge->v2)) )
529              )
530         {
531                 *r_v1 = edge->v1;
532                 *r_v2 = edge->v2;
533         }
534         else {
535                 *r_v1 = edge->v2;
536                 *r_v2 = edge->v1;
537         }
538 }
539
540 /*
541  *                      BMESH LOOP ANGLE
542  *
543  *  Calculates the angle between the previous and next loops
544  *  (angle at this loops face corner).
545  *
546  *  Returns -
547  *      Float.
548  */
549
550 float BM_loop_face_angle(BMesh *UNUSED(bm), BMLoop *l)
551 {
552         return angle_v3v3v3(l->prev->v->co,
553                             l->v->co,
554                             l->next->v->co);
555 }
556
557 /*
558  *                      BMESH FACE ANGLE
559  *
560  *  Calculates the angle between two faces.
561  *  Assumes the face normals are correct.
562  *
563  *  Returns -
564  *      Float.
565  */
566
567 float BM_edge_face_angle(BMesh *UNUSED(bm), BMEdge *e)
568 {
569         if (BM_edge_face_count(e) == 2) {
570                 BMLoop *l1 = e->l;
571                 BMLoop *l2 = e->l->radial_next;
572                 return angle_normalized_v3v3(l1->f->no, l2->f->no);
573         }
574         else {
575                 return DEG2RADF(90.0f);
576         }
577 }
578
579 /*
580  *                      BMESH FACE ANGLE
581  *
582  *  Calculates the angle a verts 2 edges.
583  *
584  *  Returns -
585  *      Float.
586  */
587 float BM_vert_edge_angle(BMesh *UNUSED(bm), BMVert *v)
588 {
589         BMEdge *e1, *e2;
590
591         /* saves BM_vert_edge_count(v) and and edge iterator,
592          * get the edges and count them both at once */
593
594         if ((e1 = v->e) &&
595                 (e2 =  bmesh_disk_nextedge(e1, v)) &&
596             /* make sure we come full circle and only have 2 connected edges */
597                 (e1 == bmesh_disk_nextedge(e2, v)))
598         {
599                 BMVert *v1 = BM_edge_other_vert(e1, v);
600                 BMVert *v2 = BM_edge_other_vert(e2, v);
601
602                 return M_PI - angle_v3v3v3(v1->co, v->co, v2->co);
603         }
604         else {
605                 return DEG2RADF(90.0f);
606         }
607 }
608
609 /*
610  * BMESH EXIST FACE OVERLAPS
611  *
612  * Given a set of vertices (varr), find out if
613  * all those vertices overlap an existing face.
614  *
615  * Returns:
616  * 0 for no overlap
617  * 1 for overlap
618  *
619  *
620  */
621
622 int BM_face_exists_overlap(BMesh *bm, BMVert **varr, int len, BMFace **overlapface)
623 {
624         BMIter vertfaces;
625         BMFace *f;
626         int i, amount;
627
628         if (overlapface) *overlapface = NULL;
629
630         for (i = 0; i < len; i++) {
631                 f = BM_iter_new(&vertfaces, bm, BM_FACES_OF_VERT, varr[i]);
632                 while (f) {
633                         amount = BM_verts_in_face(bm, f, varr, len);
634                         if (amount >= len) {
635                                 if (overlapface) *overlapface = f;
636                                 return TRUE;
637                         }
638                         f = BM_iter_step(&vertfaces);
639                 }
640         }
641         return FALSE;
642 }
643
644 /*
645  * BMESH FACE EXISTS
646  *
647  * Given a set of vertices (varr), find out if
648  * there is a face with exactly those vertices
649  * (and only those vertices).
650  *
651  * Returns:
652  * 0 for no face found
653  * 1 for face found
654  */
655
656 int BM_face_exists(BMesh *bm, BMVert **varr, int len, BMFace **existface)
657 {
658         BMIter vertfaces;
659         BMFace *f;
660         int i, amount;
661
662         if (existface) *existface = NULL;
663
664         for (i = 0; i < len; i++) {
665                 f = BM_iter_new(&vertfaces, bm, BM_FACES_OF_VERT, varr[i]);
666                 while (f) {
667                         amount = BM_verts_in_face(bm, f, varr, len);
668                         if (amount == len && amount == f->len) {
669                                 if (existface) *existface = f;
670                                 return TRUE;
671                         }
672                         f = BM_iter_step(&vertfaces);
673                 }
674         }
675         return FALSE;
676 }