dcad4023d8aac4be3b5eeb46e45c9c930ad2f3a5
[blender.git] / source / blender / bmesh / intern / bmesh_queries.c
1 #include <string.h>
2
3 #include "bmesh.h"
4 #include "bmesh_private.h"
5
6 #include "BLI_arithb.h"
7 #include "MTC_vectorops.h"
8
9 /*
10  * BM_QUERIES.C
11  *
12  * This file contains functions for answering common
13  * Topological and geometric queries about a mesh, such
14  * as, "What is the angle between these two faces?" or,
15  * "How many faces are incident upon this vertex?" Tool
16  * authors should use the functions in this file instead
17  * of inspecting the mesh structure directly.
18  *
19 */
20
21 /*
22  * BMESH COUNT ELEMENT
23  *
24  * Return the amount of element of
25  * type 'type' in a given bmesh.
26  *
27  *
28 */
29
30 int BM_Count_Element(BMesh *bm, int type)
31 {
32         if(type == BM_VERT) return bm->totvert;
33         else if(type == BM_EDGE) return bm->totedge;
34         else if(type == BM_FACE) return bm->totface;
35
36         return 0;
37 }
38
39 int BM_EdgesAroundVert(BMVert *v)
40 {
41         if (v == v->edge->v1) return bmesh_cycle_length(&v->edge->d1);
42         else return bmesh_cycle_length(&v->edge->d2);
43 }
44
45 /*
46  * BMESH VERT IN EDGE
47  *
48  * Returns whether or not a given vertex is
49  * is part of a given edge.
50  *
51 */
52
53 int BM_Vert_In_Edge(BMEdge *e, BMVert *v)
54 {
55         return bmesh_vert_in_edge(e, v);
56 }
57
58 /*
59  * BMESH OTHER EDGE IN FACE SHARING A VERTEX
60  *
61  * Returns an opposing loop that shares the same face.
62  *
63 */
64
65 BMLoop *BM_OtherFaceLoop(BMEdge *e, BMFace *f, BMVert *v)
66 {
67         BMLoop *l = f->loopbase, *l2, *l3;
68         int found = 0;
69         
70         do {
71                 if (l->e == e) break;
72                 found = 1;
73                 l = l->head.next;
74         } while (l != f->loopbase);
75         
76         return l->v == v ? l->head.prev : l->head.next;
77 }
78
79 int BM_FacesAroundEdge(BMEdge *e)
80 {
81         if (!e->loop) return 0;
82
83         return bmesh_cycle_length(&(e->loop->radial));
84 }
85
86 /*
87  * BMESH VERT IN FACE
88  *
89  * Returns whether or not a given vertex is
90  * is part of a given face.
91  *
92 */
93
94 int BM_Vert_In_Face(BMFace *f, BMVert *v)
95 {
96         BMLoop *l;
97
98         l = f->loopbase;
99         do{
100                 if(l->v == v) return 1;
101                 l = ((BMLoop*)(l->head.next));
102         }while(l != f->loopbase);
103         return 0;
104 }
105
106 /*
107  * BMESH VERTS IN FACE
108  *
109  * Compares the number of vertices in an array
110  * that appear in a given face
111  *
112 */
113 int BM_Verts_In_Face(BMesh *bm, BMFace *f, BMVert **varr, int len)
114 {
115         BMLoop *curloop = NULL;
116         int i, count = 0;
117         
118         for(i=0; i < len; i++) BMO_SetFlag(bm, varr[i], BM_OVERLAP);
119
120         curloop = f->loopbase;
121         do{
122                 if(BMO_TestFlag(bm, curloop->v, BM_OVERLAP)) count++;
123                 curloop = (BMLoop*)(curloop->head.next);
124         } while(curloop != f->loopbase);
125
126         for(i=0; i < len; i++) BMO_ClearFlag(bm, varr[i], BM_OVERLAP);
127
128         return count;
129 }
130
131 /*
132  * BMESH EDGE IN FACE
133  *
134  * Returns whether or not a given edge is
135  * is part of a given face.
136  *
137 */
138
139 int BM_Edge_In_Face(BMFace *f, BMEdge *e)
140 {
141         BMLoop *l;
142
143         l = f->loopbase;
144         do{
145
146                 if(l->e == e) return 1;
147                 l = ((BMLoop*)(l->head.next));
148         }while(l != f->loopbase);
149
150         return 0;
151 }
152
153 /*
154  * BMESH VERTS IN EDGE
155  *
156  * Returns whether or not two vertices are in 
157  * a given edge
158  *
159 */
160
161 int BM_Verts_In_Edge(BMVert *v1, BMVert *v2, BMEdge *e)
162 {
163         return bmesh_verts_in_edge(v1,v2,e);
164 }
165
166 /*
167  * BMESH GET OTHER EDGEVERT
168  *
169  * Given a edge and one of its vertices, returns
170  * the other vertex.
171  *
172 */
173
174 BMVert *BM_OtherEdgeVert(BMEdge *e, BMVert *v)
175 {
176         return bmesh_edge_getothervert(e,v);
177 }
178
179 /**
180  *                      BMESH EDGE EXIST
181  *
182  *  Finds out if two vertices already have an edge
183  *  connecting them. Note that multiple edges may
184  *  exist between any two vertices, and therefore
185  *  This function only returns the first one found.
186  * 
187  *  Returns -
188  *      BMEdge pointer
189  */
190
191 BMEdge *BM_Edge_Exist(BMVert *v1, BMVert *v2)
192 {
193         BMNode *diskbase;
194         BMEdge *curedge;
195         int i, len=0;
196         
197         if(v1->edge){
198                 diskbase = bmesh_disk_getpointer(v1->edge,v1);
199                 len = bmesh_cycle_length(diskbase);
200                 
201                 for(i=0,curedge=v1->edge;i<len;i++,curedge = bmesh_disk_nextedge(curedge,v1)){
202                         if(bmesh_verts_in_edge(v1,v2,curedge)) return curedge;
203                 }
204         }
205         
206         return NULL;
207 }
208
209 /*
210  *  BMESH VERT EDGECOUNT
211  *
212  *      Returns the number of edges around this vertex.
213  */
214
215 int BM_Vert_EdgeCount(BMVert *v)
216 {
217         int count = 0;
218         BMEdge *curedge = NULL;
219
220         if(v->edge){
221                 curedge = v->edge;
222                 do{
223                         count++;
224                         curedge = bmesh_disk_nextedge(curedge,v);
225                 }while(curedge !=v->edge);
226         }
227         return count;
228 }
229
230 /**
231  *  BMESH EDGE FACECOUNT
232  *
233  *      Returns the number of faces around this edge
234 */
235
236 int BM_Edge_FaceCount(BMEdge *e)
237 {
238         int count = 0;
239         BMLoop *curloop = NULL;
240
241         if(e->loop){
242                 curloop = e->loop;
243                 do{
244                         count++;
245                         curloop = bmesh_radial_nextloop(curloop);
246                 }while(curloop != e->loop);
247         }
248
249         return count;
250 }       
251
252 /**
253  *  BMESH VERT FACECOUNT
254  *
255  *      Returns the number of faces around this vert
256 */
257
258 int BM_Vert_FaceCount(BMVert *v){
259         int count = 0;
260         BMEdge *curedge = NULL;
261
262         if(v->edge){
263                 curedge = v->edge;
264                 do{
265                         if(curedge->loop) count += BM_Edge_FaceCount(curedge);
266                         curedge = bmesh_disk_nextedge(curedge,v);
267                 }while(curedge != v->edge);
268         }
269         return count;
270 }
271
272 /**
273  *                      BMESH WIRE VERT
274  *
275  *      Tests whether or not the vertex is part of a wire edge.
276  *  (ie: has no faces attached to it)
277  *
278  *  Returns -
279  *      1 for true, 0 for false.
280  */
281
282 int BM_Wire_Vert(BMesh *bm, BMVert *v)
283 {
284         BMEdge *curedge;
285
286         if(!(v->edge)) return 0;
287         
288         curedge = v->edge;
289         do{
290                 if(curedge->loop) return 0;
291                 curedge = bmesh_disk_nextedge(curedge, v);
292         }while(curedge != v->edge);
293
294         return 1;
295 }
296
297 /**
298  *                      BMESH WIRE EDGE
299  *
300  *      Tests whether or not the edge is part of a wire.
301  *  (ie: has no faces attached to it)
302  *
303  *  Returns -
304  *      1 for true, 0 for false.
305  */
306
307 int BM_Wire_Edge(BMesh *bm, BMEdge *e)
308 {
309         if(e->loop) return 0;
310         return 1;
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 *bm, BMVert *v) {
327         BMEdge *e, *oe;
328         BMLoop *l;
329         int len, count, flag;
330
331         if (v->edge == NULL) {
332                 /* loose vert */
333                 return 1;
334         }
335
336         /* count edges while looking for non-manifold edges */
337         oe = v->edge;
338         for (len=0,e=v->edge; e != oe || (e == oe && len == 0); len++,e=bmesh_disk_nextedge(e,v)) {
339                 if (e->loop == NULL) {
340                         /* loose edge */
341                         return 1;
342                 }
343
344                 if (bmesh_cycle_length(&(e->loop->radial)) > 2) {
345                         /* edge shared by more than two faces */
346                         return 1;
347                 }
348         }
349
350         count = 1;
351         flag = 1;
352         e = NULL;
353         oe = v->edge;
354         l = oe->loop;
355         while(e != oe) {
356                 if (l->v == v) l = ((BMLoop*)(l->head.prev));
357                 else l = ((BMLoop*)(l->head.next));
358                 e = l->e;
359                 count++; /* count the edges */
360
361                 if (flag && l->radial.next->data == 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->loop;
368                 }
369                 else if (l->radial.next->data == l) {
370                         /* break the loop */
371                         e = oe;
372                 }
373                 else {
374                         l = l->radial.next->data;
375                 }
376         }
377
378         if (count < len) {
379                 /* vert shared by multiple regions */
380                 return 1;
381         }
382
383         return 0;
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 *bm, BMEdge *e)
398 {
399         int count = BM_Edge_FaceCount(e);
400         if(count != 2 && count != 1) return 1;
401         return 0;
402 }
403
404 /**
405  *                      BMESH BOUNDARY EDGE
406  *
407  *      Tests whether or not an edge is on the boundary
408  *  of a shell (has one face associated with it)
409  *
410  *  Returns -
411  *      1 for true, 0 for false.
412  */
413
414 int BM_Boundary_Edge(BMEdge *e)
415 {
416         int count = BM_Edge_FaceCount(e);
417         if(count == 1) return 1;
418         return 0;
419 }
420
421 /**
422  *                      BMESH FACE SHAREDEDGES
423  *
424  *  Counts the number of edges two faces share (if any)
425  *
426  *  TODO:
427  *    Move this to structure, and wrap.
428  * 
429  *  Returns -
430  *      Integer
431  */
432
433 int BM_Face_Sharededges(BMFace *f1, BMFace *f2){
434         BMLoop *l;
435         int count = 0;
436         
437         l = f1->loopbase;
438         do{
439                 if(bmesh_radial_find_face(l->e,f2)) count++;
440                 l = ((BMLoop*)(l->head.next));
441         }while(l != f1->loopbase);
442         
443         return count;
444 }
445
446 /**
447  *
448  *           BMESH EDGE SHARE FACES
449  *
450  *      Tests to see if e1 shares any faces with e2
451  *
452 */
453
454 int BM_Edge_Share_Faces(BMEdge *e1, BMEdge *e2)
455 {
456         BMLoop *l;
457         BMFace *f;
458
459         if(e1->loop && e2->loop){
460                 l = e1->loop;
461                 do{
462                         f = l->f;
463                         if(bmesh_radial_find_face(e2,f)){
464                                 return 1;
465                         }
466                         l = (BMLoop*)(l->radial.next->data);
467                 }while(l != e1->loop);
468         }
469         return 0;
470 }
471
472
473
474 /**
475  *                      BMESH FACE ANGLE
476  *
477  *  Calculates the angle between two faces. Assumes
478  *  That face normals are correct.
479  * 
480  *  Returns -
481  *      Float.
482  */
483
484 float BM_Face_Angle(BMesh *bm, BMEdge *e)
485 {
486         BMLoop *l1, *l2;
487         int radlen;
488         float edge_angle_cos = 0.0;
489
490         radlen = BM_Edge_FaceCount(e);
491         if(radlen == 2){
492                 l1 = e->loop;
493                 l2 = e->loop->radial.next->data;
494                 edge_angle_cos = MTC_dot3Float(l1->f->no, l2->f->no);
495         }
496         return edge_angle_cos;
497
498 }
499
500 /*
501  * BMESH EXIST FACE OVERLAPS
502  *
503  * Given a set of vertices (varr), find out if
504  * a face exists with those vertices already, or
505  * if those vertices overlap an existing face.
506  *
507  * Returns:
508  * 0 for no overlap
509  * 1 for overlap
510  * 
511  *
512 */
513
514 int BM_Exist_Face_Overlaps(BMesh *bm, BMVert **varr, int len, BMFace **existface)
515 {
516         BMIter vertfaces;
517         BMFace *f;
518         int i, amount;
519
520         *existface = NULL;
521
522         for(i=0; i < len; i++){
523                 f = BMIter_New(&vertfaces, bm, BM_FACES_OF_VERT, varr[i] );
524                 while(f){
525                         amount = BM_Verts_In_Face(bm, f, varr, len);
526                         if(amount >= len){
527                                 if((len == f->len) && existface)
528                                         *existface = f;
529                                 return 1;                               
530                         }
531                         f = BMIter_Step(&vertfaces);
532                 }
533         }
534         return 0;
535 }