378c29e3f9ad7828cfb2060386f47bc8d8f25f2a
[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         return bmesh_jfke(bm, f1, f2, jed);
231 }
232
233 /*connects two verts together, automatically (if very naively) finding the
234   face they both share (if there is one) and splittling it.  use this at your 
235   own risk, as it doesn't handle the many complex cases it should (like zero-area faces,
236   multiple faces, etc).
237
238   this is really only meant for cases where you don't know before hand the face
239   the two verts belong to for splitting (e.g. the subdivision operator).
240 */
241
242 BMEdge *BM_Connect_Verts(BMesh *bm, BMVert *v1, BMVert *v2, BMFace **nf) {
243         BMIter iter, iter2;
244         BMVert *v;
245         BMLoop *nl;
246         BMFace *face;
247
248         /*this isn't the best thing in the world.  it doesn't handle cases where there's
249           multiple faces yet.  that might require a convexity test to figure out which
250           face is "best," and who knows what for non-manifold conditions.*/
251         for (face = BMIter_New(&iter, bm, BM_FACES_OF_VERT, v1); face; face=BMIter_Step(&iter)) {
252                 for (v=BMIter_New(&iter2, bm, BM_VERTS_OF_FACE, face); v; v=BMIter_Step(&iter2)) {
253                         if (v == v2) {
254                                 face = BM_Split_Face(bm, face, v1, v2, &nl, NULL, 1);
255
256                                 if (nf) *nf = face;
257                                 return nl->e;
258                         }
259                 }
260         }
261
262         return NULL;
263 }
264
265 /**
266  *                      BM_split_face
267  *
268  *  Splits a single face into two.
269  * 
270  *  Returns -
271  *      BMFace pointer
272  */
273  
274 BMFace *BM_Split_Face(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, BMLoop **nl, BMEdge *example, int calcnorm)
275 {
276         BMFace *nf;
277         nf = bmesh_sfme(bm,f,v1,v2,nl);
278         
279         BM_Copy_Attributes(bm, bm, f, nf);
280
281         /*
282         nf->flag = f->flag;
283         if (example->flag & SELECT) f->flag |= BM_SELECT;
284         nf->h = f->h;
285         nf->mat_nr = f->mat_nr;
286         if (nl && example) {
287                 (*nl)->e->flag = example->flag;
288                 (*nl)->e->h = example->h;
289                 (*nl)->e->crease = example->crease;
290                 (*nl)->e->bweight = example->bweight;
291         }
292         */
293         return nf;
294 }
295
296 /**
297  *                      bmesh_collapse_vert
298  *
299  *  Collapses a vertex that has only two manifold edges
300  *  onto a vertex it shares an edge with. Fac defines
301  *  the amount of interpolation for Custom Data.
302  *
303  *  Note that this is not a general edge collapse function. For
304  *  that see BM_manifold_edge_collapse 
305  *
306  *  TODO:
307  *    Insert error checking for KV valance.
308  *
309  *  Returns -
310  *      Nothing
311  */
312  
313 void BM_Collapse_Vert(BMesh *bm, BMEdge *ke, BMVert *kv, float fac, int calcnorm){
314         void *src[2];
315         float w[2];
316         BMLoop *l=NULL, *kvloop=NULL, *tvloop=NULL;
317         BMVert *tv = bmesh_edge_getothervert(ke,kv);
318
319         w[0] = 1.0f - fac;
320         w[1] = fac;
321
322         if(ke->loop){
323                 l = ke->loop;
324                 do{
325                         if(l->v == tv && ((BMLoop*)(l->head.next))->v == kv){
326                                 tvloop = l;
327                                 kvloop = ((BMLoop*)(l->head.next));
328
329                                 src[0] = kvloop->data;
330                                 src[1] = tvloop->data;
331                                 CustomData_bmesh_interp(&bm->ldata, src,w, NULL, 2, kvloop->data);                                                              
332                         }
333                         l=l->radial.next->data;
334                 }while(l!=ke->loop);
335         }
336         BM_Data_Interp_From_Verts(bm, kv, tv, kv, fac);   
337         bmesh_jekv(bm,ke,kv);
338 }
339
340 /**
341  *                      BM_split_edge
342  *      
343  *      Splits an edge. v should be one of the vertices in e and
344  *  defines the direction of the splitting operation for interpolation
345  *  purposes.
346  *
347  *  Returns -
348  *      the new vert
349  */
350
351 BMVert *BM_Split_Edge(BMesh *bm, BMVert *v, BMEdge *e, BMEdge **ne, float percent, int calcnorm) {
352         BMVert *nv, *v2;
353
354         v2 = bmesh_edge_getothervert(e,v);
355         nv = bmesh_semv(bm,v,e,ne);
356         if (nv == NULL) return NULL;
357         VECSUB(nv->co,v2->co,v->co);
358         VECADDFAC(nv->co,v->co,nv->co,percent);
359         if (ne) {
360                 if(bmesh_test_sysflag(&(e->head), BM_SELECT)) bmesh_set_sysflag(&((*ne)->head), BM_SELECT);
361                 if(bmesh_test_sysflag(&(e->head), BM_HIDDEN)) bmesh_set_sysflag(&((*ne)->head), BM_HIDDEN);
362         }
363         /*v->nv->v2*/
364         BM_Data_Facevert_Edgeinterp(bm,v2, v, nv, e, percent);  
365         BM_Data_Interp_From_Verts(bm, v2, v, nv, percent);
366         return nv;
367 }
368
369 BMVert  *BM_Split_Edge_Multi(BMesh *bm, BMEdge *e, int numcuts)
370 {
371         int i;
372         float percent;
373         BMVert *nv = NULL;
374         
375         for(i=0; i < numcuts; i++){
376                 percent = 1.0f / (float)(numcuts + 1 - i);
377                 nv = BM_Split_Edge(bm, e->v2, e, NULL, percent, 0);
378         }
379         return nv;
380 }
381
382 int BM_Validate_Face(BMesh *bm, BMFace *face, FILE *err) 
383 {
384         BMIter iter;
385         V_DECLARE(verts);
386         BMVert **verts = NULL;
387         BMLoop *l;
388         int ret = 1, i, j;
389         
390         if (face->len == 2) {
391                 fprintf(err, "warning: found two-edged face. face ptr: %p\n", face);
392                 fflush(err);
393         }
394
395         for (l=BMIter_New(&iter, bm, BM_LOOPS_OF_FACE, face);l;l=BMIter_Step(&iter)) {
396                 V_GROW(verts);
397                 verts[V_COUNT(verts)-1] = l->v;
398                 
399                 if (l->e->v1 == l->e->v2) {
400                         fprintf(err, "Found bmesh edge with identical verts!\n");
401                         fprintf(err, "  edge ptr: %p, vert: %p\n",  l->e, l->e->v1);
402                         fflush(err);
403                         ret = 0;
404                 }
405         }
406
407         for (i=0; i<V_COUNT(verts); i++) {
408                 for (j=0; j<V_COUNT(verts); j++) {
409                         if (j == i) continue;
410                         if (verts[i] == verts[j]) {
411                                 fprintf(err, "Found duplicate verts in bmesh face!\n");
412                                 fprintf(err, "  face ptr: %p, vert: %p\n", face, verts[i]);
413                                 fflush(err);
414                                 ret = 0;
415                         }
416                 }
417         }
418         
419         V_FREE(verts);
420         return ret;
421 }