a38f3992dfeb0c6f52221730510815c0e38c16f3
[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 /*
40  * BMESH VERT IN EDGE
41  *
42  * Returns whether or not a given vertex is
43  * is part of a given edge.
44  *
45 */
46
47 int BM_Vert_In_Edge(BMEdge *e, BMVert *v)
48 {
49         return bmesh_vert_in_edge(e, v);
50 }
51
52 /*
53  * BMESH OTHER EDGE IN FACE SHARING A VERTEX
54  *
55  * Returns an opposing edge that shares the same face.
56  *
57 */
58
59 BMLoop *BM_OtherFaceLoop(BMEdge *e, BMFace *f, BMVert *v)
60 {
61         BMLoop *l = f->loopbase, *l2, *l3;
62         int found = 0;
63         
64         do {
65                 if (l->e == e) break;
66                 found = 1;
67                 l = l->head.next;
68         } while (l != f->loopbase);
69         
70         return l->v == v ? l->head.prev : l->head.next;
71 }
72
73 int BM_FacesAroundEdge(BMEdge *e)
74 {
75         if (!e->loop) return 0;
76
77         return bmesh_cycle_length(&(e->loop->radial));
78 }
79
80 /*
81  * BMESH VERT IN FACE
82  *
83  * Returns whether or not a given vertex is
84  * is part of a given face.
85  *
86 */
87
88 int BM_Vert_In_Face(BMFace *f, BMVert *v)
89 {
90         BMLoop *l;
91
92         l = f->loopbase;
93         do{
94                 if(l->v == v) return 1;
95                 l = ((BMLoop*)(l->head.next));
96         }while(l != f->loopbase);
97         return 0;
98 }
99
100 /*
101  * BMESH VERTS IN FACE
102  *
103  * Compares the number of vertices in an array
104  * that appear in a given face
105  *
106 */
107 int BM_Verts_In_Face(BMesh *bm, BMFace *f, BMVert **varr, int len)
108 {
109         BMLoop *curloop = NULL;
110         int i, count = 0;
111         
112         for(i=0; i < len; i++) BMO_SetFlag(bm, varr[i], BM_OVERLAP);
113
114         curloop = f->loopbase;
115         do{
116                 if(BMO_TestFlag(bm, curloop->v, BM_OVERLAP)) count++;
117                 curloop = ((BMLoop*)(curloop->head.next));
118         } while(curloop != f->loopbase);
119
120         for(i=0; i < len; i++) BMO_ClearFlag(bm, varr[i], BM_OVERLAP);
121
122         return count;
123 }
124
125 /*
126  * BMESH EDGE IN FACE
127  *
128  * Returns whether or not a given edge is
129  * is part of a given face.
130  *
131 */
132
133 int BM_Edge_In_Face(BMFace *f, BMEdge *e)
134 {
135         BMLoop *l;
136
137         l = f->loopbase;
138         do{
139
140                 if(l->e == e) return 1;
141                 l = ((BMLoop*)(l->head.next));
142         }while(l != f->loopbase);
143
144         return 0;
145 }
146
147 /*
148  * BMESH VERTS IN EDGE
149  *
150  * Returns whether or not two vertices are in 
151  * a given edge
152  *
153 */
154
155 int BM_Verts_In_Edge(BMVert *v1, BMVert *v2, BMEdge *e)
156 {
157         return bmesh_verts_in_edge(v1,v2,e);
158 }
159
160 /*
161  * BMESH GET OTHER EDGEVERT
162  *
163  * Given a edge and one of its vertices, returns
164  * the other vertex.
165  *
166 */
167
168 BMVert *BM_OtherEdgeVert(BMEdge *e, BMVert *v)
169 {
170         return bmesh_edge_getothervert(e,v);
171 }
172
173 /**
174  *                      BMESH EDGE EXIST
175  *
176  *  Finds out if two vertices already have an edge
177  *  connecting them. Note that multiple edges may
178  *  exist between any two vertices, and therefore
179  *  This function only returns the first one found.
180  * 
181  *  Returns -
182  *      BMEdge pointer
183  */
184
185 BMEdge *BM_Edge_Exist(BMVert *v1, BMVert *v2)
186 {
187         BMNode *diskbase;
188         BMEdge *curedge;
189         int i, len=0;
190         
191         if(v1->edge){
192                 diskbase = bmesh_disk_getpointer(v1->edge,v1);
193                 len = bmesh_cycle_length(diskbase);
194                 
195                 for(i=0,curedge=v1->edge;i<len;i++,curedge = bmesh_disk_nextedge(curedge,v1)){
196                         if(bmesh_verts_in_edge(v1,v2,curedge)) return curedge;
197                 }
198         }
199         
200         return NULL;
201 }
202
203 /*
204  *  BMESH VERT EDGECOUNT
205  *
206  *      Returns the number of edges around this vertex.
207  */
208
209 int BM_Vert_EdgeCount(BMVert *v)
210 {
211         int count = 0;
212         BMEdge *curedge = NULL;
213
214         if(v->edge){
215                 curedge = v->edge;
216                 do{
217                         count++;
218                         curedge = bmesh_disk_nextedge(curedge,v);
219                 }while(curedge !=v->edge);
220         }
221         return count;
222 }
223
224 /**
225  *  BMESH EDGE FACECOUNT
226  *
227  *      Returns the number of faces around this edge
228 */
229
230 int BM_Edge_FaceCount(BMEdge *e)
231 {
232         int count = 0;
233         BMLoop *curloop = NULL;
234
235         if(e->loop){
236                 curloop = e->loop;
237                 do{
238                         count++;
239                         curloop = bmesh_radial_nextloop(curloop);
240                 }while(curloop != e->loop);
241         }
242
243         return count;
244 }       
245
246 /**
247  *  BMESH VERT FACECOUNT
248  *
249  *      Returns the number of faces around this vert
250 */
251
252 int BM_Vert_FaceCount(BMVert *v){
253         int count = 0;
254         BMEdge *curedge = NULL;
255
256         if(v->edge){
257                 curedge = v->edge;
258                 do{
259                         if(curedge->loop) count += BM_Edge_FaceCount(curedge);
260                         curedge = bmesh_disk_nextedge(curedge,v);
261                 }while(curedge != v->edge);
262         }
263         return count;
264 }
265
266 /**
267  *                      BMESH WIRE VERT
268  *
269  *      Tests whether or not the vertex is part of a wire edge.
270  *  (ie: has no faces attached to it)
271  *
272  *  Returns -
273  *      1 for true, 0 for false.
274  */
275
276 int BM_Wire_Vert(BMesh *bm, BMVert *v)
277 {
278         BMEdge *curedge;
279
280         if(!(v->edge)) return 0;
281         
282         curedge = v->edge;
283         do{
284                 if(curedge->loop) return 0;
285                 curedge = bmesh_disk_nextedge(curedge, v);
286         }while(curedge != v->edge);
287
288         return 1;
289 }
290
291 /**
292  *                      BMESH WIRE EDGE
293  *
294  *      Tests whether or not the edge is part of a wire.
295  *  (ie: has no faces attached to it)
296  *
297  *  Returns -
298  *      1 for true, 0 for false.
299  */
300
301 int BM_Wire_Edge(BMesh *bm, BMEdge *e)
302 {
303         if(e->loop) return 0;
304         return 1;
305 }
306
307 /**
308  *                      BMESH NONMANIFOLD VERT
309  *
310  *  A vertex is non-manifold if it meets the following conditions:
311  *    1: Loose - (has no edges/faces incident upon it)
312  *    2: Joins two distinct regions - (two pyramids joined at the tip)
313  *    3: Is part of a non-manifold edge (edge with more than 2 faces)
314  *    4: Is part of a wire edge
315  * 
316  *  Returns -
317  *      1 for true, 0 for false.
318  */
319
320 int BM_Nonmanifold_Vert(BMesh *bm, BMVert *v) {
321         BMEdge *e, *oe;
322         BMLoop *l;
323         int len, count, flag;
324
325         if (v->edge == NULL) {
326                 /* loose vert */
327                 return 1;
328         }
329
330         /* count edges while looking for non-manifold edges */
331         oe = v->edge;
332         for (len=0,e=v->edge; e != oe || (e == oe && len == 0); len++,e=bmesh_disk_nextedge(e,v)) {
333                 if (e->loop == NULL) {
334                         /* loose edge */
335                         return 1;
336                 }
337
338                 if (bmesh_cycle_length(&(e->loop->radial)) > 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->edge;
348         l = oe->loop;
349         while(e != oe) {
350                 if (l->v == v) l = ((BMLoop*)(l->head.prev));
351                 else l = ((BMLoop*)(l->head.next));
352                 e = l->e;
353                 count++; /* count the edges */
354
355                 if (flag && l->radial.next->data == l) {
356                         /* we've hit the edge of an open mesh, reset once */
357                         flag = 0;
358                         count = 1;
359                         oe = e;
360                         e = NULL;
361                         l = oe->loop;
362                 }
363                 else if (l->radial.next->data == l) {
364                         /* break the loop */
365                         e = oe;
366                 }
367                 else {
368                         l = l->radial.next->data;
369                 }
370         }
371
372         if (count < len) {
373                 /* vert shared by multiple regions */
374                 return 1;
375         }
376
377         return 0;
378 }
379
380 /**
381  *                      BMESH NONMANIFOLD EDGE
382  *
383  *      Tests whether or not this edge is manifold.
384  *  A manifold edge either has 1 or 2 faces attached
385  *      to it.
386  *
387  *  Returns -
388  *      1 for true, 0 for false.
389  */
390
391 int BM_Nonmanifold_Edge(BMesh *bm, BMEdge *e)
392 {
393         int count = BM_Edge_FaceCount(e);
394         if(count != 2 && count != 1) return 1;
395         return 0;
396 }
397
398 /**
399  *                      BMESH BOUNDARY EDGE
400  *
401  *      Tests whether or not an edge is on the boundary
402  *  of a shell (has one face associated with it)
403  *
404  *  Returns -
405  *      1 for true, 0 for false.
406  */
407
408 int BM_Boundary_Edge(BMEdge *e)
409 {
410         int count = BM_Edge_FaceCount(e);
411         if(count == 1) return 1;
412         return 0;
413 }
414
415 /**
416  *                      BMESH FACE SHAREDEDGES
417  *
418  *  Counts the number of edges two faces share (if any)
419  *
420  *  TODO:
421  *    Move this to structure, and wrap.
422  * 
423  *  Returns -
424  *      Integer
425  */
426
427 int BM_Face_Sharededges(BMFace *f1, BMFace *f2){
428         BMLoop *l;
429         int count = 0;
430         
431         l = f1->loopbase;
432         do{
433                 if(bmesh_radial_find_face(l->e,f2)) count++;
434                 l = ((BMLoop*)(l->head.next));
435         }while(l != f1->loopbase);
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->loop && e2->loop){
454                 l = e1->loop;
455                 do{
456                         f = l->f;
457                         if(bmesh_radial_find_face(e2,f)){
458                                 return 1;
459                         }
460                         l = (BMLoop*)(l->radial.next->data);
461                 }while(l != e1->loop);
462         }
463         return 0;
464 }
465
466
467
468 /**
469  *                      BMESH FACE ANGLE
470  *
471  *  Calculates the angle between two faces. Assumes
472  *  That face normals are correct.
473  * 
474  *  Returns -
475  *      Float.
476  */
477
478 float BM_Face_Angle(BMesh *bm, BMEdge *e)
479 {
480         BMLoop *l1, *l2;
481         int radlen;
482         float edge_angle_cos = 0.0;
483
484         radlen = BM_Edge_FaceCount(e);
485         if(radlen == 2){
486                 l1 = e->loop;
487                 l2 = e->loop->radial.next->data;
488                 edge_angle_cos = MTC_dot3Float(l1->f->no, l2->f->no);
489         }
490         return edge_angle_cos;
491
492 }
493
494 /*
495  * BMESH EXIST FACE OVERLAPS
496  *
497  * Given a set of vertices (varr), find out if
498  * a face exists with those vertices already, or
499  * if those vertices overlap an existing face.
500  *
501  * Returns:
502  * 0 for no overlap
503  * 1 for overlap
504  * 
505  *
506 */
507
508 int BM_Exist_Face_Overlaps(BMesh *bm, BMVert **varr, int len, BMFace **existface)
509 {
510         BMIter vertfaces;
511         BMFace *f;
512         int i, amount;
513
514         *existface = NULL;
515
516         for(i=0; i < len; i++){
517                 f = BMIter_New(&vertfaces, bm, BM_FACES_OF_VERT, varr[i] );
518                 while(f){
519                         amount = BM_Verts_In_Face(bm, f, varr, len);
520                         if(amount >= len){
521                                 if((len == f->len) && existface)
522                                         *existface = f;
523                                 return 1;                               
524                         }
525                         f = BMIter_Step(&vertfaces);
526                 }
527         }
528         return 0;
529 }