the make ngon function's overlap test needed some work, the API function
[blender.git] / source / blender / bmesh / intern / bmesh_mods.c
1 #include <limits.h>
2 #include "MEM_guardedalloc.h"
3
4 #include "DNA_listBase.h"
5 #include "BKE_utildefines.h"
6 #include "BLI_blenlib.h"
7 #include "BLI_linklist.h"
8 #include "BLI_ghash.h"
9 #include "BLI_arithb.h"
10
11 #include "bmesh.h"
12 #include "bmesh_private.h"
13
14 #include <stdlib.h>
15 #include <string.h>
16
17 /*
18  * BME_MODS.C
19  *
20  * This file contains functions for locally modifying
21  * the topology of existing mesh data. (split, join, flip ect).
22  *
23 */
24
25 /**
26  *                      bmesh_dissolve_disk
27  *
28  *  Turns the face region surrounding a manifold vertex into 
29  *  A single polygon.
30  *
31  * 
32  * Example:
33  * 
34  *          |=========|             |=========|
35  *          |  \   /  |             |         |
36  * Before:  |    V    |      After: |         |
37  *          |  /   \  |             |         |
38  *          |=========|             |=========|
39  * 
40  * 
41  */
42 #if 1
43 int BM_Dissolve_Vert(BMesh *bm, BMVert *v) {
44         BMIter iter;
45         BMEdge *e;
46         int len=0;
47
48         if (!v) return 0;
49         
50         e = BMIter_New(&iter, bm, BM_EDGES_OF_VERT, v);
51         for (; e; e=BMIter_Step(&iter)) {
52                 len++;
53         }
54         
55         if (len == 1) {
56                 bmesh_ke(bm, v->edge);
57                 bmesh_kv(bm, v);
58                 return 1;
59         }
60
61         if(BM_Nonmanifold_Vert(bm, v)) {
62                 if (!v->edge) bmesh_kv(bm, v);
63                 else if (!v->edge->loop) {
64                         bmesh_ke(bm, v->edge);
65                         bmesh_kv(bm, v);
66                 } else return 0;
67
68                 return 1;
69         }
70
71         return BM_Dissolve_Disk(bm, v);
72 }
73
74 int BM_Dissolve_Disk(BMesh *bm, BMVert *v) {
75         BMFace *f, *f2;
76         BMEdge *e, *keepedge=NULL, *baseedge=NULL;
77         BMLoop *loop;
78         int done, len;
79
80         if(BM_Nonmanifold_Vert(bm, v)) {
81                 return 0;
82         }
83         
84         if(v->edge){
85                 /*v->edge we keep, what else?*/
86                 e = v->edge;
87                 len = 0;
88                 do{
89                         e = bmesh_disk_nextedge(e,v);
90                         if(!(BM_Edge_Share_Faces(e, v->edge))){
91                                 keepedge = e;
92                                 baseedge = v->edge;
93                                 break;
94                         }
95                         len++;
96                 }while(e != v->edge);
97         }
98         
99         /*this code for handling 2 and 3-valence verts
100           may be totally bad.*/
101         if (keepedge == NULL && len == 3) {
102                 /*handle specific case for three-valence.  solve it by
103                   increasing valence to four.  this may be hackish. . .*/
104                 loop = e->loop;
105                 if (loop->v == v) loop = (BMLoop*) loop->head.next;
106                 if (!BM_Split_Face(bm, loop->f, v, loop->v, NULL, NULL, 0))
107                         return 0;
108
109                 BM_Dissolve_Disk(bm, v);
110                 return 1;
111         } else if (keepedge == NULL && len == 2) {
112                 /*handle two-valence*/
113                 f = v->edge->loop->f;
114                 f2 = ((BMLoop*)v->edge->loop->radial.next->data)->f;
115                 /*collapse the vertex*/
116                 BM_Collapse_Vert(bm, v->edge, v, 1.0, 0);
117                 BM_Join_Faces(bm, f, f2, NULL, 0, 0);
118
119                 return 1;
120         }
121
122         if(keepedge){
123                 done = 0;
124                 while(!done){
125                         done = 1;
126                         e = v->edge;
127                         do{
128                                 f = NULL;
129                                 len = bmesh_cycle_length(&(e->loop->radial));
130                                 if(len == 2 && (e!=baseedge) && (e!=keepedge)) {
131                                         f = BM_Join_Faces(bm, e->loop->f, ((BMLoop*)(e->loop->radial.next->data))->f, e, 0, 0); 
132                                         /*return if couldn't join faces in manifold
133                                           conditions.*/
134                                         //!disabled for testing why bad things happen
135                                         if (!f) return 0;
136                                 }
137
138                                 if(f){
139                                         done = 0;
140                                         break;
141                                 }
142                                 e = bmesh_disk_nextedge(e, v);
143                         }while(e != v->edge);
144                 }
145
146                 /*get remaining two faces*/
147                 f = v->edge->loop->f;
148                 f2 = ((BMLoop*)v->edge->loop->radial.next->data)->f;
149
150                 /*collapse the vertex*/
151                 BM_Collapse_Vert(bm, baseedge, v, 1.0, 0);
152                 
153                 if (f != f2) {
154                         /*join two remaining faces*/
155                         if (!BM_Join_Faces(bm, f, f2, NULL, 0, 0)) return 0;
156                 }
157         }
158
159         return 1;
160 }
161 #else
162 void BM_Dissolve_Disk(BMesh *bm, BMVert *v){
163         BMFace *f;
164         BMEdge *e;
165         BMIter iter;
166         int done, len;
167         
168         if(v->edge){
169                 done = 0;
170                 while(!done){
171                         done = 1;
172                         
173                         /*loop the edges looking for an edge to dissolve*/
174                         for (e=BMIter_New(&iter, bm, BM_EDGES_OF_VERT, v); e;
175                              e = BMIter_Step(&iter)) {
176                                 f = NULL;
177                                 len = bmesh_cycle_length(&(e->loop->radial));
178                                 if(len == 2){
179                                         f = BM_Join_Faces(bm,e->loop->f,((BMLoop*)
180                                               (e->loop->radial.next->data))->f, 
181                                                e, 1, 0);
182                                 }
183                                 if(f){ 
184                                         done = 0;
185                                         break;
186                                 }
187                         };
188                 }
189                 BM_Collapse_Vert(bm, v->edge, v, 1.0, 1);
190         }
191 }
192 #endif
193
194 /**
195  *                      bmesh_join_faces
196  *
197  *  joins two adjacenct faces togather. If weldUVs == 1
198  *  and the uv/vcols of the two faces are non-contigous, the
199  *  per-face properties of f2 will be transformed into place
200  *  around f1.
201  * 
202  *  Returns -
203  *      BMFace pointer
204  */
205  
206 BMFace *BM_Join_Faces(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e, int calcnorm, int weldUVs) {
207
208         BMLoop *l1, *l2;
209         BMEdge *jed=NULL;
210         
211         jed = e;
212         if(!jed){
213                 /*search for an edge that has both these faces in its radial cycle*/
214                 l1 = f1->loopbase;
215                 do{
216                         if( ((BMLoop*)l1->radial.next->data)->f == f2 ){
217                                 jed = l1->e;
218                                 break;
219                         }
220                         l1 = ((BMLoop*)(l1->head.next));
221                 }while(l1!=f1->loopbase);
222         }
223
224         l1 = jed->loop;
225         l2 = l1->radial.next->data;
226         if (l1->v == l2->v) {
227                 bmesh_loop_reverse(bm, f2);
228         }
229
230         f1 = bmesh_jfke(bm, f1, f2, jed);
231         
232         if (calcnorm && f1) BM_Face_UpdateNormal(bm, f1);
233         
234         return f1;
235 }
236
237 /*connects two verts together, automatically (if very naively) finding the
238   face they both share (if there is one) and splittling it.  use this at your 
239   own risk, as it doesn't handle the many complex cases it should (like zero-area faces,
240   multiple faces, etc).
241
242   this is really only meant for cases where you don't know before hand the face
243   the two verts belong to for splitting (e.g. the subdivision operator).
244 */
245
246 BMEdge *BM_Connect_Verts(BMesh *bm, BMVert *v1, BMVert *v2, BMFace **nf) {
247         BMIter iter, iter2;
248         BMVert *v;
249         BMLoop *nl;
250         BMFace *face;
251
252         /*this isn't the best thing in the world.  it doesn't handle cases where there's
253           multiple faces yet.  that might require a convexity test to figure out which
254           face is "best," and who knows what for non-manifold conditions.*/
255         for (face = BMIter_New(&iter, bm, BM_FACES_OF_VERT, v1); face; face=BMIter_Step(&iter)) {
256                 for (v=BMIter_New(&iter2, bm, BM_VERTS_OF_FACE, face); v; v=BMIter_Step(&iter2)) {
257                         if (v == v2) {
258                                 face = BM_Split_Face(bm, face, v1, v2, &nl, NULL, 1);
259
260                                 if (nf) *nf = face;
261                                 return nl->e;
262                         }
263                 }
264         }
265
266         return NULL;
267 }
268
269 /**
270  *                      BM_split_face
271  *
272  *  Splits a single face into two.
273  * 
274  *  Returns -
275  *      BMFace pointer
276  */
277  
278 BMFace *BM_Split_Face(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, BMLoop **nl, BMEdge *example, int calcnorm)
279 {
280         BMFace *nf;
281         nf = bmesh_sfme(bm,f,v1,v2,nl);
282         
283         BM_Copy_Attributes(bm, bm, f, nf);
284
285         if (calcnorm && nf) {
286                 BM_Face_UpdateNormal(bm, nf);
287                 BM_Face_UpdateNormal(bm, f);
288         }
289
290         return nf;
291 }
292
293 /**
294  *                      bmesh_collapse_vert
295  *
296  *  Collapses a vertex that has only two manifold edges
297  *  onto a vertex it shares an edge with. Fac defines
298  *  the amount of interpolation for Custom Data.
299  *
300  *  Note that this is not a general edge collapse function. For
301  *  that see BM_manifold_edge_collapse 
302  *
303  *  TODO:
304  *    Insert error checking for KV valance.
305  *
306  *  Returns -
307  *      Nothing
308  */
309  
310 void BM_Collapse_Vert(BMesh *bm, BMEdge *ke, BMVert *kv, float fac, int calcnorm){
311         void *src[2];
312         float w[2];
313         BMLoop *l=NULL, *kvloop=NULL, *tvloop=NULL;
314         BMVert *tv = bmesh_edge_getothervert(ke,kv);
315
316         w[0] = 1.0f - fac;
317         w[1] = fac;
318
319         if(ke->loop){
320                 l = ke->loop;
321                 do{
322                         if(l->v == tv && ((BMLoop*)(l->head.next))->v == kv){
323                                 tvloop = l;
324                                 kvloop = ((BMLoop*)(l->head.next));
325
326                                 src[0] = kvloop->data;
327                                 src[1] = tvloop->data;
328                                 CustomData_bmesh_interp(&bm->ldata, src,w, NULL, 2, kvloop->data);                                                              
329                         }
330                         l=l->radial.next->data;
331                 }while(l!=ke->loop);
332         }
333         BM_Data_Interp_From_Verts(bm, kv, tv, kv, fac);   
334         bmesh_jekv(bm,ke,kv);
335 }
336
337 /**
338  *                      BM_split_edge
339  *      
340  *      Splits an edge. v should be one of the vertices in e and
341  *  defines the direction of the splitting operation for interpolation
342  *  purposes.
343  *
344  *  Returns -
345  *      the new vert
346  */
347
348 BMVert *BM_Split_Edge(BMesh *bm, BMVert *v, BMEdge *e, BMEdge **ne, float percent, int calcnorm) {
349         BMVert *nv, *v2;
350
351         v2 = bmesh_edge_getothervert(e,v);
352         nv = bmesh_semv(bm,v,e,ne);
353         if (nv == NULL) return NULL;
354         VECSUB(nv->co,v2->co,v->co);
355         VECADDFAC(nv->co,v->co,nv->co,percent);
356         if (ne) {
357                 if(bmesh_test_sysflag(&(e->head), BM_SELECT)) bmesh_set_sysflag(&((*ne)->head), BM_SELECT);
358                 if(bmesh_test_sysflag(&(e->head), BM_HIDDEN)) bmesh_set_sysflag(&((*ne)->head), BM_HIDDEN);
359         }
360         /*v->nv->v2*/
361         BM_Data_Facevert_Edgeinterp(bm,v2, v, nv, e, percent);  
362         BM_Data_Interp_From_Verts(bm, v2, v, nv, percent);
363         return nv;
364 }
365
366 BMVert  *BM_Split_Edge_Multi(BMesh *bm, BMEdge *e, int numcuts)
367 {
368         int i;
369         float percent;
370         BMVert *nv = NULL;
371         
372         for(i=0; i < numcuts; i++){
373                 percent = 1.0f / (float)(numcuts + 1 - i);
374                 nv = BM_Split_Edge(bm, e->v2, e, NULL, percent, 0);
375         }
376         return nv;
377 }
378
379 int BM_Validate_Face(BMesh *bm, BMFace *face, FILE *err) 
380 {
381         BMIter iter;
382         V_DECLARE(verts);
383         BMVert **verts = NULL;
384         BMLoop *l;
385         int ret = 1, i, j;
386         
387         if (face->len == 2) {
388                 fprintf(err, "warning: found two-edged face. face ptr: %p\n", face);
389                 fflush(err);
390         }
391
392         for (l=BMIter_New(&iter, bm, BM_LOOPS_OF_FACE, face);l;l=BMIter_Step(&iter)) {
393                 V_GROW(verts);
394                 verts[V_COUNT(verts)-1] = l->v;
395                 
396                 if (l->e->v1 == l->e->v2) {
397                         fprintf(err, "Found bmesh edge with identical verts!\n");
398                         fprintf(err, "  edge ptr: %p, vert: %p\n",  l->e, l->e->v1);
399                         fflush(err);
400                         ret = 0;
401                 }
402         }
403
404         for (i=0; i<V_COUNT(verts); i++) {
405                 for (j=0; j<V_COUNT(verts); j++) {
406                         if (j == i) continue;
407                         if (verts[i] == verts[j]) {
408                                 fprintf(err, "Found duplicate verts in bmesh face!\n");
409                                 fprintf(err, "  face ptr: %p, vert: %p\n", face, verts[i]);
410                                 fflush(err);
411                                 ret = 0;
412                         }
413                 }
414         }
415         
416         V_FREE(verts);
417         return ret;
418 }