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