fast-path for BM_edge_is_manifold, BM_edge_is_boundary functions.
[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 "MEM_guardedalloc.h"
35
36 #include "BLI_array.h"
37 #include "BLI_math.h"
38
39 #include "bmesh.h"
40 #include "bmesh_private.h"
41
42 #define BM_OVERLAP (1 << 13)
43
44 /**
45  * Return the amount of element of type 'type' in a given bmesh.
46  */
47 int BM_mesh_elem_count(BMesh *bm, const char htype)
48 {
49         if (htype == BM_VERT) return bm->totvert;
50         else if (htype == BM_EDGE) return bm->totedge;
51         else if (htype == BM_FACE) return bm->totface;
52
53         return 0;
54 }
55
56 /**
57  * Returns whether or not a given vertex is
58  * is part of a given edge.
59  */
60 int BM_vert_in_edge(BMEdge *e, BMVert *v)
61 {
62         return bmesh_vert_in_edge(e, v);
63 }
64
65 /**
66  * \brief BMESH OTHER EDGE IN FACE SHARING A VERTEX
67  *
68  * Finds the other loop that shares 'v' with 'e's loop in 'f'.
69  */
70 BMLoop *BM_face_other_loop(BMEdge *e, BMFace *f, BMVert *v)
71 {
72         BMLoop *l_iter;
73         BMLoop *l_first;
74
75         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
76         
77         do {
78                 if (l_iter->e == e) {
79                         break;
80                 }
81         } while ((l_iter = l_iter->next) != l_first);
82         
83         return l_iter->v == v ? l_iter->prev : l_iter->next;
84 }
85
86 /**
87  * Returns TRUE if the vertex is used in a given face.
88  */
89
90 int BM_vert_in_face(BMFace *f, BMVert *v)
91 {
92         BMLoop *l_iter, *l_first;
93
94 #ifdef USE_BMESH_HOLES
95         BMLoopList *lst;
96         for (lst = f->loops.first; lst; lst = lst->next)
97 #endif
98         {
99 #ifdef USE_BMESH_HOLES
100                 l_iter = l_first = lst->first;
101 #else
102                 l_iter = l_first = f->l_first;
103 #endif
104                 do {
105                         if (l_iter->v == v) {
106                                 return TRUE;
107                         }
108                 } while ((l_iter = l_iter->next) != l_first);
109         }
110
111         return FALSE;
112 }
113
114 /**
115  * Compares the number of vertices in an array
116  * that appear in a given face
117  */
118 int BM_verts_in_face(BMesh *bm, BMFace *f, BMVert **varr, int len)
119 {
120         BMLoop *l_iter, *l_first;
121
122 #ifdef USE_BMESH_HOLES
123         BMLoopList *lst;
124 #endif
125
126         int i, count = 0;
127         
128         for (i = 0; i < len; i++) {
129                 BMO_elem_flag_enable(bm, varr[i], BM_OVERLAP);
130         }
131
132 #ifdef USE_BMESH_HOLES
133         for (lst = f->loops.first; lst; lst = lst->next)
134 #endif
135         {
136
137 #ifdef USE_BMESH_HOLES
138                 l_iter = l_first = lst->first;
139 #else
140                 l_iter = l_first = f->l_first;
141 #endif
142
143                 do {
144                         if (BMO_elem_flag_test(bm, l_iter->v, BM_OVERLAP)) {
145                                 count++;
146                         }
147
148                 } while ((l_iter = l_iter->next) != l_first);
149         }
150
151         for (i = 0; i < len; i++) BMO_elem_flag_disable(bm, varr[i], BM_OVERLAP);
152
153         return count;
154 }
155
156 /**
157  * Returns whether or not a given edge is is part of a given face.
158  */
159 int BM_edge_in_face(BMFace *f, BMEdge *e)
160 {
161         BMLoop *l_iter;
162         BMLoop *l_first;
163
164         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
165
166         do {
167                 if (l_iter->e == e) {
168                         return TRUE;
169                 }
170         } while ((l_iter = l_iter->next) != l_first);
171
172         return FALSE;
173 }
174
175 /**
176  * Returns whether or not two vertices are in
177  * a given edge
178  */
179 int BM_verts_in_edge(BMVert *v1, BMVert *v2, BMEdge *e)
180 {
181         return bmesh_verts_in_edge(v1, v2, e);
182 }
183
184 /**
185  * Given a edge and one of its vertices, returns
186  * the other vertex.
187  */
188 BMVert *BM_edge_other_vert(BMEdge *e, BMVert *v)
189 {
190         return bmesh_edge_other_vert_get(e, v);
191 }
192
193 /**
194  *      Returns the number of edges around this vertex.
195  */
196 int BM_vert_edge_count(BMVert *v)
197 {
198         return bmesh_disk_count(v);
199 }
200
201 /**
202  *      Returns the number of faces around this edge
203  */
204 int BM_edge_face_count(BMEdge *e)
205 {
206         int count = 0;
207         BMLoop *l_iter = NULL;
208
209         if (e->l) {
210                 l_iter = e->l;
211                 do {
212                         count++;
213                 } while ((l_iter = bmesh_radial_loop_next(l_iter)) != e->l);
214         }
215
216         return count;
217 }
218
219 /**
220  *      Returns the number of faces around this vert
221  */
222 int BM_vert_face_count(BMVert *v)
223 {
224         int count = 0;
225         BMLoop *l;
226         BMIter iter;
227
228         BM_ITER(l, &iter, NULL, BM_LOOPS_OF_VERT, v) {
229                 count++;
230         }
231
232         return count;
233 #if 0 //this code isn't working
234         BMEdge *curedge = NULL;
235
236         if (v->e) {
237                 curedge = v->e;
238                 do {
239                         if (curedge->l) count += BM_edge_face_count(curedge);
240                         curedge = bmesh_disk_edge_next(curedge, v);
241                 } while (curedge != v->e);
242         }
243         return count;
244 #endif
245 }
246
247 /**
248  * Tests whether or not the vertex is part of a wire edge.
249  * (ie: has no faces attached to it)
250  */
251 int BM_vert_is_wire(BMesh *UNUSED(bm), BMVert *v)
252 {
253         BMEdge *curedge;
254
255         if (v->e == NULL) {
256                 return FALSE;
257         }
258         
259         curedge = v->e;
260         do {
261                 if (curedge->l) {
262                         return FALSE;
263                 }
264
265                 curedge = bmesh_disk_edge_next(curedge, v);
266         } while (curedge != v->e);
267
268         return TRUE;
269 }
270
271 /**
272  * Tests whether or not the edge is part of a wire.
273  * (ie: has no faces attached to it)
274  */
275 int BM_edge_is_wire(BMesh *UNUSED(bm), BMEdge *e)
276 {
277         return (e->l) ? FALSE : TRUE;
278 }
279
280 /**
281  * A vertex is non-manifold if it meets the following conditions:
282  * 1: Loose - (has no edges/faces incident upon it)
283  * 2: Joins two distinct regions - (two pyramids joined at the tip)
284  * 3: Is part of a non-manifold edge (edge with more than 2 faces)
285  * 4: Is part of a wire edge
286  */
287 int BM_vert_is_manifold(BMesh *UNUSED(bm), BMVert *v)
288 {
289         BMEdge *e, *oe;
290         BMLoop *l;
291         int len, count, flag;
292
293         if (v->e == NULL) {
294                 /* loose vert */
295                 return FALSE;
296         }
297
298         /* count edges while looking for non-manifold edges */
299         oe = v->e;
300         for (len = 0, e = v->e; e != oe || (e == oe && len == 0); len++, e = bmesh_disk_edge_next(e, v)) {
301                 if (e->l == NULL) {
302                         /* loose edge */
303                         return FALSE;
304                 }
305
306                 if (bmesh_radial_length(e->l) > 2) {
307                         /* edge shared by more than two faces */
308                         return FALSE;
309                 }
310         }
311
312         count = 1;
313         flag = 1;
314         e = NULL;
315         oe = v->e;
316         l = oe->l;
317         while (e != oe) {
318                 l = (l->v == v) ? l->prev : l->next;
319                 e = l->e;
320                 count++; /* count the edges */
321
322                 if (flag && l->radial_next == l) {
323                         /* we've hit the edge of an open mesh, reset once */
324                         flag = 0;
325                         count = 1;
326                         oe = e;
327                         e = NULL;
328                         l = oe->l;
329                 }
330                 else if (l->radial_next == l) {
331                         /* break the loop */
332                         e = oe;
333                 }
334                 else {
335                         l = l->radial_next;
336                 }
337         }
338
339         if (count < len) {
340                 /* vert shared by multiple regions */
341                 return FALSE;
342         }
343
344         return TRUE;
345 }
346
347 /**
348  * Tests whether or not this edge is manifold.
349  * A manifold edge either has 1 or 2 faces attached to it.
350  */
351
352 #if 1 /* fast path for checking manifold */
353 int BM_edge_is_manifold(BMesh *UNUSED(bm), BMEdge *e)
354 {
355         const BMLoop *l = e->l;
356         return (l && ((l->radial_next == l) ||              /* 1 face user  */
357                       (l->radial_next->radial_next == l))); /* 2 face users */
358 }
359 #else
360 int BM_edge_is_manifold(BMesh *UNUSED(bm), BMEdge *e)
361 {
362         int count = BM_edge_face_count(e);
363         if (count == 2 || count == 1) {
364                 return TRUE;
365         }
366         else {
367                 return FALSE;
368         }
369 }
370 #endif
371
372 /**
373  * Tests whether or not an edge is on the boundary
374  * of a shell (has one face associated with it)
375  */
376
377 #if 1 /* fast path for checking boundry */
378 int BM_edge_is_boundary(BMEdge *e)
379 {
380         const BMLoop *l = e->l;
381         return (l && (l->radial_next == l));
382 }
383 #else
384 int BM_edge_is_boundary(BMEdge *e)
385 {
386         int count = BM_edge_face_count(e);
387         if (count == 1) {
388                 return TRUE;
389         }
390         else {
391                 return FALSE;
392         }
393 }
394 #endif
395
396 /**
397  *  Counts the number of edges two faces share (if any)
398  */
399 int BM_face_share_edge_count(BMFace *f1, BMFace *f2)
400 {
401         BMLoop *l_iter;
402         BMLoop *l_first;
403         int count = 0;
404         
405         l_iter = l_first = BM_FACE_FIRST_LOOP(f1);
406         do {
407                 if (bmesh_radial_face_find(l_iter->e, f2)) {
408                         count++;
409                 }
410         } while ((l_iter = l_iter->next) != l_first);
411
412         return count;
413 }
414
415 /**
416  *      Test if e1 shares any faces with e2
417  */
418 int BM_edge_share_face_count(BMEdge *e1, BMEdge *e2)
419 {
420         BMLoop *l;
421         BMFace *f;
422
423         if (e1->l && e2->l) {
424                 l = e1->l;
425                 do {
426                         f = l->f;
427                         if (bmesh_radial_face_find(e2, f)) {
428                                 return TRUE;
429                         }
430                         l = l->radial_next;
431                 } while (l != e1->l);
432         }
433         return FALSE;
434 }
435
436 /**
437  *      Tests to see if e1 shares a vertex with e2
438  */
439 int BM_edge_share_vert_count(BMEdge *e1, BMEdge *e2)
440 {
441         return (e1->v1 == e2->v1 ||
442                 e1->v1 == e2->v2 ||
443                 e1->v2 == e2->v1 ||
444                 e1->v2 == e2->v2);
445 }
446
447 /**
448  *      Return the shared vertex between the two edges or NULL
449  */
450 BMVert *BM_edge_share_vert(BMEdge *e1, BMEdge *e2)
451 {
452         if (BM_vert_in_edge(e2, e1->v1)) {
453                 return e1->v1;
454         }
455         else if (BM_vert_in_edge(e2, e1->v2)) {
456                 return e1->v2;
457         }
458         else {
459                 return NULL;
460         }
461 }
462
463 /**
464  * Returns the verts of an edge as used in a face
465  * if used in a face at all, otherwise just assign as used in the edge.
466  *
467  * Useful to get a determanistic winding order when calling
468  * BM_face_create_ngon() on an arbitrary array of verts,
469  * though be sure to pick an edge which has a face.
470  */
471 void BM_edge_ordered_verts(BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
472 {
473         if ((edge->l == NULL) ||
474             (((edge->l->prev->v == edge->v1) && (edge->l->v == edge->v2)) ||
475              ((edge->l->v == edge->v1) && (edge->l->next->v == edge->v2)))
476             )
477         {
478                 *r_v1 = edge->v1;
479                 *r_v2 = edge->v2;
480         }
481         else {
482                 *r_v1 = edge->v2;
483                 *r_v2 = edge->v1;
484         }
485 }
486
487 /**
488  * Calculates the angle between the previous and next loops
489  * (angle at this loops face corner).
490  *
491  * \return angle in radians
492  */
493 float BM_loop_face_angle(BMesh *UNUSED(bm), BMLoop *l)
494 {
495         return angle_v3v3v3(l->prev->v->co,
496                             l->v->co,
497                             l->next->v->co);
498 }
499
500 /**
501  * \brief BMESH EDGE/FACE ANGLE
502  *
503  *  Calculates the angle between two faces.
504  *  Assumes the face normals are correct.
505  *
506  * \return angle in radians
507  */
508 float BM_edge_face_angle(BMesh *UNUSED(bm), BMEdge *e)
509 {
510         if (BM_edge_face_count(e) == 2) {
511                 BMLoop *l1 = e->l;
512                 BMLoop *l2 = e->l->radial_next;
513                 return angle_normalized_v3v3(l1->f->no, l2->f->no);
514         }
515         else {
516                 return DEG2RADF(90.0f);
517         }
518 }
519
520 /**
521  * \brief BMESH VERT/EDGE ANGLE
522  *
523  * Calculates the angle a verts 2 edges.
524  *
525  * \returns the angle in radians
526  */
527 float BM_vert_edge_angle(BMesh *UNUSED(bm), BMVert *v)
528 {
529         BMEdge *e1, *e2;
530
531         /* saves BM_vert_edge_count(v) and and edge iterator,
532          * get the edges and count them both at once */
533
534         if ((e1 = v->e) &&
535                 (e2 =  bmesh_disk_edge_next(e1, v)) &&
536             /* make sure we come full circle and only have 2 connected edges */
537                 (e1 == bmesh_disk_edge_next(e2, v)))
538         {
539                 BMVert *v1 = BM_edge_other_vert(e1, v);
540                 BMVert *v2 = BM_edge_other_vert(e2, v);
541
542                 return M_PI - angle_v3v3v3(v1->co, v->co, v2->co);
543         }
544         else {
545                 return DEG2RADF(90.0f);
546         }
547 }
548
549 /**
550  * Returns the edge existing between v1 and v2, or NULL if there isn't one.
551  *
552  * \note multiple edges may exist between any two vertices, and therefore
553  * this function only returns the first one found.
554  */
555 BMEdge *BM_edge_exists(BMVert *v1, BMVert *v2)
556 {
557         BMIter iter;
558         BMEdge *e;
559
560         BM_ITER(e, &iter, NULL, BM_EDGES_OF_VERT, v1) {
561                 if (e->v1 == v2 || e->v2 == v2)
562                         return e;
563         }
564
565         return NULL;
566 }
567
568 /**
569  * Given a set of vertices \a varr, find out if
570  * all those vertices overlap an existing face.
571  *
572  * \note Making a face here is valid but in some cases you wont want to
573  * make a face thats part of another.
574  *
575  * \returns TRUE for overlap
576  *
577  */
578 int BM_face_exists_overlap(BMesh *bm, BMVert **varr, int len, BMFace **r_overlapface)
579 {
580         BMIter viter;
581         BMFace *f;
582         int i, amount;
583
584         for (i = 0; i < len; i++) {
585                 BM_ITER(f, &viter, bm, BM_FACES_OF_VERT, varr[i]) {
586                         amount = BM_verts_in_face(bm, f, varr, len);
587                         if (amount >= len) {
588                                 if (r_overlapface) {
589                                         *r_overlapface = f;
590                                 }
591                                 return TRUE;
592                         }
593                 }
594         }
595
596         if (r_overlapface) {
597                 *r_overlapface = NULL;
598         }
599
600         return FALSE;
601 }
602
603 /**
604  * Given a set of vertices (varr), find out if
605  * there is a face with exactly those vertices
606  * (and only those vertices).
607  */
608 int BM_face_exists(BMesh *bm, BMVert **varr, int len, BMFace **r_existface)
609 {
610         BMIter viter;
611         BMFace *f;
612         int i, amount;
613
614         for (i = 0; i < len; i++) {
615                 BM_ITER(f, &viter, bm, BM_FACES_OF_VERT, varr[i]) {
616                         amount = BM_verts_in_face(bm, f, varr, len);
617                         if (amount == len && amount == f->len) {
618                                 if (r_existface) {
619                                         *r_existface = f;
620                                 }
621                                 return TRUE;
622                         }
623                 }
624         }
625
626         if (r_existface) {
627                 *r_existface = NULL;
628         }
629         return FALSE;
630 }
631
632
633 /**
634  * Given a set of vertices and edges (\a varr, \a earr), find out if
635  * all those vertices are filled in by existing faces that _only_ use those vertices.
636  *
637  * This is for use in cases where creating a face is possible but would result in
638  * many overlapping faces.
639  *
640  * An example of how this is used: when 2 tri's are selected that share an edge,
641  * pressing Fkey would make a new overlapping quad (without a check like this)
642  *
643  * \a earr and \a varr can be in any order, however they _must_ form a closed loop.
644  */
645 int BM_face_exists_multi(BMesh *bm, BMVert **varr, BMEdge **earr, int len)
646 {
647         BMFace *f;
648         BMEdge *e;
649         BMVert *v;
650         int ok;
651         int tot_tag;
652
653         BMIter fiter;
654         BMIter viter;
655
656         int i;
657
658         for (i = 0; i < len; i++) {
659                 /* save some time by looping over edge faces rather then vert faces
660                  * will still loop over some faces twice but not as many */
661                 BM_ITER(f, &fiter, bm, BM_FACES_OF_EDGE, earr[i]) {
662                         BM_elem_flag_disable(f, BM_ELEM_INTERNAL_TAG);
663                         BM_ITER(v, &viter, bm, BM_VERTS_OF_FACE, f) {
664                                 BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
665                         }
666                 }
667
668                 /* clear all edge tags */
669                 BM_ITER(e, &fiter, bm, BM_EDGES_OF_VERT, varr[i]) {
670                         BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
671                 }
672         }
673
674         /* now tag all verts and edges in the boundry array as true so
675          * we can know if a face-vert is from our array */
676         for (i = 0; i < len; i++) {
677                 BM_elem_flag_enable(varr[i], BM_ELEM_INTERNAL_TAG);
678                 BM_elem_flag_enable(earr[i], BM_ELEM_INTERNAL_TAG);
679         }
680
681
682         /* so! boundry is tagged, everything else cleared */
683
684
685         /* 1) tag all faces connected to edges - if all their verts are boundry */
686         tot_tag = 0;
687         for (i = 0; i < len; i++) {
688                 BM_ITER(f, &fiter, bm, BM_FACES_OF_EDGE, earr[i]) {
689                         if (!BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
690                                 ok = TRUE;
691                                 BM_ITER(v, &viter, bm, BM_VERTS_OF_FACE, f) {
692                                         if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) {
693                                                 ok = FALSE;
694                                                 break;
695                                         }
696                                 }
697
698                                 if (ok) {
699                                         /* we only use boundry verts */
700                                         BM_elem_flag_enable(f, BM_ELEM_INTERNAL_TAG);
701                                         tot_tag++;
702                                 }
703                         }
704                         else {
705                                 /* we already found! */
706                         }
707                 }
708         }
709
710         if (tot_tag == 0) {
711                 /* no faces use only boundry verts, quit early */
712                 return FALSE;
713         }
714
715         /* 2) loop over non-boundry edges that use boundry verts,
716          *    check each have 2 tagges faces connected (faces that only use 'varr' verts) */
717         ok = TRUE;
718         for (i = 0; i < len; i++) {
719                 BM_ITER(e, &fiter, bm, BM_EDGES_OF_VERT, varr[i]) {
720
721                         if (/* non-boundry edge */
722                             BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == FALSE &&
723                             /* ...using boundry verts */
724                             BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) == TRUE &&
725                             BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG) == TRUE)
726                         {
727                                 int tot_face_tag = 0;
728                                 BM_ITER(f, &fiter, bm, BM_FACES_OF_EDGE, e) {
729                                         if (BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
730                                                 tot_face_tag++;
731                                         }
732                                 }
733
734                                 if (tot_face_tag != 2) {
735                                         ok = FALSE;
736                                         break;
737                                 }
738
739                         }
740                 }
741
742                 if (ok == FALSE) {
743                         break;
744                 }
745         }
746
747         return ok;
748 }
749
750 /* same as 'BM_face_exists_multi' but built vert array from edges */
751 int BM_face_exists_multi_edge(BMesh *bm, BMEdge **earr, int len)
752 {
753         BMVert **varr;
754         BLI_array_fixedstack_declare(varr, BM_NGON_STACK_SIZE, len, __func__);
755
756         int ok;
757         int i, i_next;
758
759         /* first check if verts have edges, if not we can bail out early */
760         ok = TRUE;
761         for (i = len - 1, i_next = 0; i_next < len; (i = i_next++)) {
762                 if (!(varr[i] = BM_edge_share_vert(earr[i], earr[i_next]))) {
763                         ok = FALSE;
764                         break;
765                 }
766         }
767
768         if (ok == FALSE) {
769                 BMESH_ASSERT(0);
770                 BLI_array_fixedstack_free(varr);
771                 return FALSE;
772         }
773
774         ok = BM_face_exists_multi(bm, varr, earr, len);
775
776         BLI_array_fixedstack_free(varr);
777
778         return ok;
779 }