finished bmeshafying merge, though probably needs further testing and debugging....
[blender.git] / source / blender / bmesh / operators / removedoubles.c
1 #include "MEM_guardedalloc.h"
2
3 #include "DNA_meshdata_types.h"
4 #include "DNA_mesh_types.h"
5 #include "DNA_object_types.h"
6 #include "DNA_scene_types.h"
7
8 #include "BKE_utildefines.h"
9
10 #include "BLI_arithb.h"
11 #include "BLI_ghash.h"
12 #include "BLI_blenlib.h"
13
14 #include "bmesh.h"
15 #include "mesh_intern.h"
16 #include "bmesh_private.h"
17
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <string.h>
21
22 #define BL(ptr) ((BMLoop*)(ptr))
23
24 void remdoubles_splitface(BMFace *f, BMesh *bm, BMOperator *op)
25 {
26         BMIter liter;
27         BMLoop *l;
28         BMVert *v2, *doub;
29         int split=0;
30
31         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
32                 v2 = BMO_Get_MapPointer(bm, op, "targetmap", l->v);
33                 /*ok: if v2 is NULL (e.g. not in the map) then it's
34                       a target vert, otherwise it's a double*/
35                 if (v2 && BM_Vert_In_Face(f, v2) && v2 != BL(l->head.prev)->v 
36                     && v2 != BL(l->head.next)->v)
37                 {
38                         doub = l->v;
39                         split = 1;
40                         break;
41                 }
42         }
43
44         if (split && doub != v2) {
45                 BMLoop *nl;
46                 BMFace *f2 = BM_Split_Face(bm, f, doub, v2, &nl, NULL);
47
48                 remdoubles_splitface(f, bm, op);
49                 remdoubles_splitface(f2, bm, op);
50         }
51 }
52
53 #define ELE_DEL         1
54 #define EDGE_COL        2
55 #define FACE_MARK       2
56
57 #if 0
58 int remdoubles_face_overlaps(BMesh *bm, BMVert **varr, 
59                              int len, BMFace *exclude, 
60                              BMFace **overlapface)
61 {
62         BMIter vertfaces;
63         BMFace *f;
64         int i, amount;
65
66         if (overlapface) *overlapface = NULL;
67
68         for(i=0; i < len; i++){
69                 f = BMIter_New(&vertfaces, bm, BM_FACES_OF_VERT, varr[i] );
70                 while(f){
71                         amount = BM_Verts_In_Face(bm, f, varr, len);
72                         if(amount >= len){
73                                 if (overlapface) *overlapface = f;
74                                 return 1;                               
75                         }
76                         f = BMIter_Step(&vertfaces);
77                 }
78         }
79         return 0;
80 }
81 #endif
82
83 void bmesh_weldverts_exec(BMesh *bm, BMOperator *op)
84 {
85         BMIter iter, liter;
86         BMVert *v, *v2;
87         BMEdge *e, *e2, **edges = NULL;
88         V_DECLARE(edges);
89         BMLoop *l, *l2, **loops = NULL;
90         V_DECLARE(loops);
91         BMFace *f, *f2;
92         int a, b;
93
94         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
95                 if (BMO_Get_MapPointer(bm, op, "targetmap", v))
96                         BMO_SetFlag(bm, v, ELE_DEL);
97         }
98
99         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
100                 remdoubles_splitface(f, bm, op);
101         }
102         
103         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
104                 if (BMO_TestFlag(bm, e->v1, ELE_DEL) || BMO_TestFlag(bm, e->v2, ELE_DEL)) {
105                         v = BMO_Get_MapPointer(bm, op, "targetmap", e->v1);
106                         v2 = BMO_Get_MapPointer(bm, op, "targetmap", e->v2);
107                         
108                         if (!v) v = e->v1;
109                         if (!v2) v2 = e->v2;
110
111                         if (v == v2)
112                                 BMO_SetFlag(bm, e, EDGE_COL);
113                         else if (!BM_Edge_Exist(v, v2))
114                                 BM_Make_Edge(bm, v, v2, e, 1);
115
116                         BMO_SetFlag(bm, e, ELE_DEL);
117                 }
118         }
119
120         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
121                 BMINDEX_SET(f, 0);
122                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
123                         if (BMO_TestFlag(bm, l->v, ELE_DEL))
124                                 BMO_SetFlag(bm, f, FACE_MARK|ELE_DEL);
125                         if (BMO_TestFlag(bm, l->e, EDGE_COL)) 
126                                 BMINDEX_SET(f, BMINDEX_GET(f)+1);
127                 }
128         }
129
130         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
131                 if (!BMO_TestFlag(bm, f, FACE_MARK))
132                         continue;
133
134                 if (f->len - BMINDEX_GET(f) < 3) {
135                         BMO_SetFlag(bm, f, ELE_DEL);
136                         continue;
137                 }
138
139                 V_RESET(edges);
140                 V_RESET(loops);
141                 a = 0;
142                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
143                         v = l->v;
144                         v2 = BL(l->head.next)->v;
145                         if (BMO_TestFlag(bm, v, ELE_DEL)) 
146                                 v = BMO_Get_MapPointer(bm, op, "targetmap", v);
147                         if (BMO_TestFlag(bm, v2, ELE_DEL)) 
148                                 v2 = BMO_Get_MapPointer(bm, op, "targetmap", v2);
149                         
150                         e2 = v != v2 ? BM_Edge_Exist(v, v2) : NULL;
151                         if (e2) {
152                                 for (b=0; b<a; b++) {
153                                         if (edges[b] == e2)
154                                                 break;
155                                 }
156                                 if (b != a)
157                                         continue;
158
159                                 V_GROW(edges);
160                                 V_GROW(loops);
161
162                                 edges[a] = e2;
163                                 loops[a] = l;
164
165                                 a++;
166                         }
167                 }
168                 
169                 v = loops[0]->v;
170                 v2 = loops[1]->v;
171
172                 if (BMO_TestFlag(bm, v, ELE_DEL)) 
173                         v = BMO_Get_MapPointer(bm, op, "targetmap", v);
174                 if (BMO_TestFlag(bm, v2, ELE_DEL)) 
175                         v2 = BMO_Get_MapPointer(bm, op, "targetmap", v2);
176                 
177                 f2 = BM_Make_Ngon(bm, v, v2, edges, a, 0);
178                 if (f2) {
179                         BM_Copy_Attributes(bm, bm, f, f2);
180
181                         a = 0;
182                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f2) {
183                                 l2 = loops[a];
184                                 BM_Copy_Attributes(bm, bm, l2, l);
185
186                                 a++;
187                         }
188                 }
189         }
190
191         BMO_CallOpf(bm, "del geom=%fvef context=%i", ELE_DEL, DEL_ONLYTAGGED);
192
193         V_FREE(edges);
194         V_FREE(loops);
195 }
196
197 static int vergaverco(const void *e1, const void *e2)
198 {
199         const BMVert *v1 = *(void**)e1, *v2 = *(void**)e2;
200         float x1 = v1->co[0] + v1->co[1] + v1->co[2];
201         float x2 = v2->co[0] + v2->co[1] + v2->co[2];
202
203         if (x1 > x2) return 1;
204         else if (x1 < x2) return -1;
205         else return 0;
206 }
207
208 #define VERT_TESTED     1
209 #define VERT_DOUBLE     2
210 #define VERT_TARGET     4
211 #define VERT_KEEP       8
212 #define VERT_MARK       16
213
214 #define EDGE_MARK       1
215
216 void bmesh_pointmerge_facedata_exec(BMesh *bm, BMOperator *op)
217 {
218         BMOIter siter;
219         BMIter iter;
220         BMVert *v, *snapv;
221         BMLoop *l, *firstl = NULL;
222         float fac;
223         int i, tot;
224
225         snapv = BMO_IterNew(&siter, bm, op, "snapv", BM_VERT);  
226         tot = BM_Vert_FaceCount(snapv);
227
228         if (!tot)
229                 return;
230
231         fac = 1.0f / tot;
232         BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, snapv) {
233                 if (!firstl) {
234                         firstl = l;
235                 }
236                 
237                 for (i=0; i<bm->ldata.totlayer; i++) {
238                         if (CustomData_layer_has_math(&bm->ldata, i)) {
239                                 int type = bm->ldata.layers[i].type;
240                                 void *e1, *e2;
241
242                                 e1 = CustomData_bmesh_get_layer_n(&bm->ldata, firstl->head.data, i); 
243                                 e2 = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
244                                 
245                                 CustomData_data_multiply(type, e2, fac);
246
247                                 if (l != firstl)
248                                         CustomData_data_add(type, e1, e2);
249                         }
250                 }
251         }
252
253         BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
254                 BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) {
255                         if (l == firstl) 
256                                 continue;
257
258                         CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, firstl->head.data, &l->head.data);
259                 }
260         }
261 }
262
263 void bmesh_vert_average_facedata_exec(BMesh *bm, BMOperator *op)
264 {
265         BMOIter siter;
266         BMIter iter;
267         BMVert *v;
268         BMLoop *l, *firstl = NULL;
269         CDBlockBytes min, max;
270         void *block;
271         int i, type;
272
273         for (i=0; i<bm->ldata.totlayer; i++) {
274                 if (!CustomData_layer_has_math(&bm->ldata, i))
275                         continue;
276                 
277                 type = bm->ldata.layers[i].type;
278                 CustomData_data_initminmax(type, &min, &max);
279
280                 BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
281                         BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) {
282                                 block = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
283                                 CustomData_data_dominmax(type, block, &min, &max);      
284                         }
285                 }
286
287                 CustomData_data_multiply(type, &min, 0.5f);
288                 CustomData_data_multiply(type, &max, 0.5f);
289                 CustomData_data_add(type, &min, &max);
290
291                 BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
292                         BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) {
293                                 block = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
294                                 CustomData_data_copy_value(type, &min, block);
295                         }
296                 }
297         }
298 }
299
300 void bmesh_pointmerge_exec(BMesh *bm, BMOperator *op)
301 {
302         BMOperator weldop;
303         BMOIter siter;
304         BMVert *v, *snapv = NULL;
305         float vec[3];
306         
307         BMO_Get_Vec(op, "mergeco", vec);
308
309         //BMO_CallOpf(bm, "collapse_uvs edges=%s", op, "edges");
310         BMO_Init_Op(&weldop, "weldverts");
311         
312         BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
313                 if (!snapv) {
314                         snapv = v;
315                         VECCOPY(snapv->co, vec);
316                 } else {
317                         BMO_Insert_MapPointer(bm, &weldop, "targetmap", v, snapv);
318                 }               
319         }
320
321         BMO_Exec_Op(bm, &weldop);
322         BMO_Finish_Op(bm, &weldop);
323 }
324
325 void bmesh_collapse_exec(BMesh *bm, BMOperator *op)
326 {
327         BMOperator weldop;
328         BMWalker walker;
329         BMIter iter;
330         BMEdge *e, **edges = NULL;
331         V_DECLARE(edges);
332         float min[3], max[3];
333         int i, tot;
334         
335         BMO_CallOpf(bm, "collapse_uvs edges=%s", op, "edges");
336         BMO_Init_Op(&weldop, "weldverts");
337
338         BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE);   
339         BMW_Init(&walker, bm, BMW_SHELL, EDGE_MARK, 0);
340
341         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
342                 if (!BMO_TestFlag(bm, e, EDGE_MARK))
343                         continue;
344
345                 e = BMW_Begin(&walker, e->v1);
346                 V_RESET(edges);
347
348                 INIT_MINMAX(min, max);
349                 for (tot=0; e; tot++, e=BMW_Step(&walker)) {
350                         V_GROW(edges);
351                         edges[tot] = e;
352
353                         DO_MINMAX(e->v1->co, min, max);
354                         DO_MINMAX(e->v2->co, min, max);
355                 }
356
357                 VECADD(min, min, max);
358                 VECMUL(min, 0.5f);
359
360                 /*snap edges to a point.  for initial testing purposes anyway.*/
361                 for (i=0; i<tot; i++) {
362                         VECCOPY(edges[i]->v1->co, min);
363                         VECCOPY(edges[i]->v2->co, min);
364                         
365                         if (edges[i]->v1 != edges[0]->v1)
366                                 BMO_Insert_MapPointer(bm, &weldop, "targetmap", edges[i]->v1, edges[0]->v1);                    
367                         if (edges[i]->v2 != edges[0]->v1)
368                                 BMO_Insert_MapPointer(bm, &weldop, "targetmap", edges[i]->v2, edges[0]->v1);
369                 }
370         }
371         
372         BMO_Exec_Op(bm, &weldop);
373         BMO_Finish_Op(bm, &weldop);
374
375         BMW_End(&walker);
376         V_FREE(edges);
377 }
378
379 /*uv collapse function*/
380 void bmesh_collapsecon_do_layer(BMesh *bm, BMOperator *op, int layer)
381 {
382         BMIter iter, liter;
383         BMFace *f;
384         BMLoop *l, *l2;
385         BMWalker walker;
386         void **blocks = NULL;
387         V_DECLARE(blocks);
388         CDBlockBytes min, max;
389         int i, tot, type = bm->ldata.layers[layer].type;
390
391         BMO_Clear_Flag_All(bm, op, BM_ALL, 65535);
392
393         BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE);
394         BMW_Init(&walker, bm, BMW_LOOPDATA_ISLAND, EDGE_MARK, layer);
395
396         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
397                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
398                         if (BMO_TestFlag(bm, l->e, EDGE_MARK)) {
399                                 /*walk*/
400                                 V_RESET(blocks);
401                                 tot = 0;
402                                 l2 = BMW_Begin(&walker, l);
403
404                                 CustomData_data_initminmax(type, &min, &max);
405                                 for (tot=0; l2; tot++, l2=BMW_Step(&walker)) {
406                                         V_GROW(blocks);
407                                         blocks[tot] = CustomData_bmesh_get_layer_n(&bm->ldata, l2->head.data, layer);
408                                         CustomData_data_dominmax(type, blocks[tot], &min, &max);
409                                 }
410
411                                 if (tot) {
412                                         CustomData_data_multiply(type, &min, 0.5f);
413                                         CustomData_data_multiply(type, &max, 0.5f);
414                                         CustomData_data_add(type, &min, &max);
415
416                                         /*snap CD (uv, vcol) points to their centroid*/
417                                         for (i=0; i<tot; i++) {
418                                                 CustomData_data_copy_value(type, &min, blocks[i]);
419                                         }
420                                 }
421                         }
422                 }
423         }
424
425         BMW_End(&walker);
426         V_FREE(blocks);
427 }
428
429 void bmesh_collapsecon_exec(BMesh *bm, BMOperator *op)
430 {
431         int i;
432
433         for (i=0; i<bm->ldata.totlayer; i++) {
434                 if (CustomData_layer_has_math(&bm->ldata, i))
435                         bmesh_collapsecon_do_layer(bm, op, i);
436         }
437 }
438
439 void bmesh_removedoubles_exec(BMesh *bm, BMOperator *op)
440 {
441         BMOperator weldop;
442         BMOIter oiter;
443         BMVert *v, *v2;
444         BMVert **verts=NULL;
445         V_DECLARE(verts);
446         float dist, distsqr;
447         int i, j, len;
448
449         dist = BMO_Get_Float(op, "dist");
450         distsqr = dist*dist;
451
452         BMO_Init_Op(&weldop, "weldverts");
453         
454         i = 0;
455         BMO_ITER(v, &oiter, bm, op, "verts", BM_VERT) {
456                 V_GROW(verts);
457                 verts[i++] = v;
458         }
459
460         /*sort by vertex coordinates added together*/
461         qsort(verts, V_COUNT(verts), sizeof(void*), vergaverco);
462         
463         len = V_COUNT(verts);
464         for (i=0; i<len; i++) {
465                 v = verts[i];
466                 if (BMO_TestFlag(bm, v, VERT_TESTED)) continue;
467                 
468                 BMO_SetFlag(bm, v, VERT_TESTED);
469                 for (j=i+1; j<len; j++) {
470                         float vec[3];
471                         
472                         v2 = verts[j];
473                         if ((v2->co[0]+v2->co[1]+v2->co[2]) - (v->co[0]+v->co[1]+v->co[2])
474                              > distsqr) break;
475
476                         vec[0] = v->co[0] - v2->co[0];
477                         vec[1] = v->co[1] - v2->co[1];
478                         vec[2] = v->co[2] - v2->co[2];
479                         
480                         if (INPR(vec, vec) < distsqr) {
481                                 BMO_SetFlag(bm, v2, VERT_TESTED);
482                                 BMO_SetFlag(bm, v2, VERT_DOUBLE);
483                                 BMO_SetFlag(bm, v, VERT_TARGET);
484                         
485                                 BMO_Insert_MapPointer(bm, &weldop, "targetmap", v2, v);
486                         }
487                 }
488         }
489
490         V_FREE(verts);
491
492         BMO_Exec_Op(bm, &weldop);
493         BMO_Finish_Op(bm, &weldop);
494 }
495
496
497 void bmesh_finddoubles_exec(BMesh *bm, BMOperator *op)
498 {
499         BMOIter oiter;
500         BMVert *v, *v2;
501         BMVert **verts=NULL;
502         V_DECLARE(verts);
503         float dist, distsqr;
504         int i, j, len;
505
506         dist = BMO_Get_Float(op, "dist");
507         distsqr = dist*dist;
508
509         i = 0;
510         BMO_ITER(v, &oiter, bm, op, "verts", BM_VERT) {
511                 V_GROW(verts);
512                 verts[i++] = v;
513         }
514
515         /*sort by vertex coordinates added together*/
516         //qsort(verts, V_COUNT(verts), sizeof(void*), vergaverco);
517         
518         BMO_Flag_Buffer(bm, op, "keepverts", VERT_KEEP, BM_VERT);
519
520         len = V_COUNT(verts);
521         for (i=0; i<len; i++) {
522                 v = verts[i];
523                 if (BMO_TestFlag(bm, v, VERT_DOUBLE)) continue;
524                 
525                 //BMO_SetFlag(bm, v, VERT_TESTED);
526                 for (j=0; j<len; j++) {
527                         if (j == i) continue;
528
529                         //float vec[3];
530                         if (BMO_TestFlag(bm, v, VERT_KEEP)) continue;
531
532                         v2 = verts[j];
533                         //if ((v2->co[0]+v2->co[1]+v2->co[2]) - (v->co[0]+v->co[1]+v->co[2])
534                         //     > distsqr) break;
535
536                         //vec[0] = v->co[0] - v2->co[0];
537                         //vec[1] = v->co[1] - v2->co[1];
538                         //vec[2] = v->co[2] - v2->co[2];
539                         
540                         if (VecLenCompare(v->co, v2->co, dist)) {
541                                 BMO_SetFlag(bm, v2, VERT_DOUBLE);
542                                 BMO_SetFlag(bm, v, VERT_TARGET);
543                         
544                                 BMO_Insert_MapPointer(bm, op, "targetmapout", v2, v);
545                         }
546                 }
547         }
548
549         V_FREE(verts);
550 }