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