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