c8d3b883f5d0e320a334e496bb7f8f15dc9a5009
[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                 if (V_COUNT(loops) < 3)
170                         continue;
171
172                 v = loops[0]->v;
173                 v2 = loops[1]->v;
174
175                 if (BMO_TestFlag(bm, v, ELE_DEL)) 
176                         v = BMO_Get_MapPointer(bm, op, "targetmap", v);
177                 if (BMO_TestFlag(bm, v2, ELE_DEL)) 
178                         v2 = BMO_Get_MapPointer(bm, op, "targetmap", v2);
179                 
180                 f2 = BM_Make_Ngon(bm, v, v2, edges, a, 0);
181                 if (f2) {
182                         BM_Copy_Attributes(bm, bm, f, f2);
183
184                         a = 0;
185                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f2) {
186                                 l2 = loops[a];
187                                 BM_Copy_Attributes(bm, bm, l2, l);
188
189                                 a++;
190                         }
191                 }
192         }
193
194         BMO_CallOpf(bm, "del geom=%fvef context=%i", ELE_DEL, DEL_ONLYTAGGED);
195
196         V_FREE(edges);
197         V_FREE(loops);
198 }
199
200 static int vergaverco(const void *e1, const void *e2)
201 {
202         const BMVert *v1 = *(void**)e1, *v2 = *(void**)e2;
203         float x1 = v1->co[0] + v1->co[1] + v1->co[2];
204         float x2 = v2->co[0] + v2->co[1] + v2->co[2];
205
206         if (x1 > x2) return 1;
207         else if (x1 < x2) return -1;
208         else return 0;
209 }
210
211 #define VERT_TESTED     1
212 #define VERT_DOUBLE     2
213 #define VERT_TARGET     4
214 #define VERT_KEEP       8
215 #define VERT_MARK       16
216
217 #define EDGE_MARK       1
218
219 void bmesh_pointmerge_facedata_exec(BMesh *bm, BMOperator *op)
220 {
221         BMOIter siter;
222         BMIter iter;
223         BMVert *v, *snapv;
224         BMLoop *l, *firstl = NULL;
225         float fac;
226         int i, tot;
227
228         snapv = BMO_IterNew(&siter, bm, op, "snapv", BM_VERT);  
229         tot = BM_Vert_FaceCount(snapv);
230
231         if (!tot)
232                 return;
233
234         fac = 1.0f / tot;
235         BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, snapv) {
236                 if (!firstl) {
237                         firstl = l;
238                 }
239                 
240                 for (i=0; i<bm->ldata.totlayer; i++) {
241                         if (CustomData_layer_has_math(&bm->ldata, i)) {
242                                 int type = bm->ldata.layers[i].type;
243                                 void *e1, *e2;
244
245                                 e1 = CustomData_bmesh_get_layer_n(&bm->ldata, firstl->head.data, i); 
246                                 e2 = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
247                                 
248                                 CustomData_data_multiply(type, e2, fac);
249
250                                 if (l != firstl)
251                                         CustomData_data_add(type, e1, e2);
252                         }
253                 }
254         }
255
256         BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
257                 BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) {
258                         if (l == firstl) 
259                                 continue;
260
261                         CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, firstl->head.data, &l->head.data);
262                 }
263         }
264 }
265
266 void bmesh_vert_average_facedata_exec(BMesh *bm, BMOperator *op)
267 {
268         BMOIter siter;
269         BMIter iter;
270         BMVert *v;
271         BMLoop *l, *firstl = NULL;
272         CDBlockBytes min, max;
273         void *block;
274         int i, type;
275
276         for (i=0; i<bm->ldata.totlayer; i++) {
277                 if (!CustomData_layer_has_math(&bm->ldata, i))
278                         continue;
279                 
280                 type = bm->ldata.layers[i].type;
281                 CustomData_data_initminmax(type, &min, &max);
282
283                 BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
284                         BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) {
285                                 block = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
286                                 CustomData_data_dominmax(type, block, &min, &max);      
287                         }
288                 }
289
290                 CustomData_data_multiply(type, &min, 0.5f);
291                 CustomData_data_multiply(type, &max, 0.5f);
292                 CustomData_data_add(type, &min, &max);
293
294                 BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
295                         BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) {
296                                 block = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
297                                 CustomData_data_copy_value(type, &min, block);
298                         }
299                 }
300         }
301 }
302
303 void bmesh_pointmerge_exec(BMesh *bm, BMOperator *op)
304 {
305         BMOperator weldop;
306         BMOIter siter;
307         BMVert *v, *snapv = NULL;
308         float vec[3];
309         
310         BMO_Get_Vec(op, "mergeco", vec);
311
312         //BMO_CallOpf(bm, "collapse_uvs edges=%s", op, "edges");
313         BMO_Init_Op(&weldop, "weldverts");
314         
315         BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
316                 if (!snapv) {
317                         snapv = v;
318                         VECCOPY(snapv->co, vec);
319                 } else {
320                         BMO_Insert_MapPointer(bm, &weldop, "targetmap", v, snapv);
321                 }               
322         }
323
324         BMO_Exec_Op(bm, &weldop);
325         BMO_Finish_Op(bm, &weldop);
326 }
327
328 void bmesh_collapse_exec(BMesh *bm, BMOperator *op)
329 {
330         BMOperator weldop;
331         BMWalker walker;
332         BMIter iter;
333         BMEdge *e, **edges = NULL;
334         V_DECLARE(edges);
335         float min[3], max[3];
336         int i, tot;
337         
338         BMO_CallOpf(bm, "collapse_uvs edges=%s", op, "edges");
339         BMO_Init_Op(&weldop, "weldverts");
340
341         BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE);   
342         BMW_Init(&walker, bm, BMW_SHELL, EDGE_MARK, 0);
343
344         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
345                 if (!BMO_TestFlag(bm, e, EDGE_MARK))
346                         continue;
347
348                 e = BMW_Begin(&walker, e->v1);
349                 V_RESET(edges);
350
351                 INIT_MINMAX(min, max);
352                 for (tot=0; e; tot++, e=BMW_Step(&walker)) {
353                         V_GROW(edges);
354                         edges[tot] = e;
355
356                         DO_MINMAX(e->v1->co, min, max);
357                         DO_MINMAX(e->v2->co, min, max);
358                 }
359
360                 VECADD(min, min, max);
361                 VECMUL(min, 0.5f);
362
363                 /*snap edges to a point.  for initial testing purposes anyway.*/
364                 for (i=0; i<tot; i++) {
365                         VECCOPY(edges[i]->v1->co, min);
366                         VECCOPY(edges[i]->v2->co, min);
367                         
368                         if (edges[i]->v1 != edges[0]->v1)
369                                 BMO_Insert_MapPointer(bm, &weldop, "targetmap", edges[i]->v1, edges[0]->v1);                    
370                         if (edges[i]->v2 != edges[0]->v1)
371                                 BMO_Insert_MapPointer(bm, &weldop, "targetmap", edges[i]->v2, edges[0]->v1);
372                 }
373         }
374         
375         BMO_Exec_Op(bm, &weldop);
376         BMO_Finish_Op(bm, &weldop);
377
378         BMW_End(&walker);
379         V_FREE(edges);
380 }
381
382 /*uv collapse function*/
383 void bmesh_collapsecon_do_layer(BMesh *bm, BMOperator *op, int layer)
384 {
385         BMIter iter, liter;
386         BMFace *f;
387         BMLoop *l, *l2;
388         BMWalker walker;
389         void **blocks = NULL;
390         V_DECLARE(blocks);
391         CDBlockBytes min, max;
392         int i, tot, type = bm->ldata.layers[layer].type;
393
394         BMO_Clear_Flag_All(bm, op, BM_ALL, 65535);
395
396         BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE);
397         BMW_Init(&walker, bm, BMW_LOOPDATA_ISLAND, EDGE_MARK, layer);
398
399         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
400                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
401                         if (BMO_TestFlag(bm, l->e, EDGE_MARK)) {
402                                 /*walk*/
403                                 V_RESET(blocks);
404                                 tot = 0;
405                                 l2 = BMW_Begin(&walker, l);
406
407                                 CustomData_data_initminmax(type, &min, &max);
408                                 for (tot=0; l2; tot++, l2=BMW_Step(&walker)) {
409                                         V_GROW(blocks);
410                                         blocks[tot] = CustomData_bmesh_get_layer_n(&bm->ldata, l2->head.data, layer);
411                                         CustomData_data_dominmax(type, blocks[tot], &min, &max);
412                                 }
413
414                                 if (tot) {
415                                         CustomData_data_multiply(type, &min, 0.5f);
416                                         CustomData_data_multiply(type, &max, 0.5f);
417                                         CustomData_data_add(type, &min, &max);
418
419                                         /*snap CD (uv, vcol) points to their centroid*/
420                                         for (i=0; i<tot; i++) {
421                                                 CustomData_data_copy_value(type, &min, blocks[i]);
422                                         }
423                                 }
424                         }
425                 }
426         }
427
428         BMW_End(&walker);
429         V_FREE(blocks);
430 }
431
432 void bmesh_collapsecon_exec(BMesh *bm, BMOperator *op)
433 {
434         int i;
435
436         for (i=0; i<bm->ldata.totlayer; i++) {
437                 if (CustomData_layer_has_math(&bm->ldata, i))
438                         bmesh_collapsecon_do_layer(bm, op, i);
439         }
440 }
441
442 void bmesh_removedoubles_exec(BMesh *bm, BMOperator *op)
443 {
444         BMOperator weldop;
445         BMOIter oiter;
446         BMVert *v, *v2;
447         BMVert **verts=NULL;
448         V_DECLARE(verts);
449         float dist, distsqr;
450         int i, j, len;
451
452         dist = BMO_Get_Float(op, "dist");
453         distsqr = dist*dist;
454
455         BMO_Init_Op(&weldop, "weldverts");
456         
457         i = 0;
458         BMO_ITER(v, &oiter, bm, op, "verts", BM_VERT) {
459                 V_GROW(verts);
460                 verts[i++] = v;
461         }
462
463         /*sort by vertex coordinates added together*/
464         qsort(verts, V_COUNT(verts), sizeof(void*), vergaverco);
465         
466         len = V_COUNT(verts);
467         for (i=0; i<len; i++) {
468                 v = verts[i];
469                 if (BMO_TestFlag(bm, v, VERT_TESTED)) continue;
470                 
471                 BMO_SetFlag(bm, v, VERT_TESTED);
472                 for (j=i+1; j<len; j++) {
473                         float vec[3];
474                         
475                         v2 = verts[j];
476                         if ((v2->co[0]+v2->co[1]+v2->co[2]) - (v->co[0]+v->co[1]+v->co[2])
477                              > distsqr) break;
478
479                         vec[0] = v->co[0] - v2->co[0];
480                         vec[1] = v->co[1] - v2->co[1];
481                         vec[2] = v->co[2] - v2->co[2];
482                         
483                         if (INPR(vec, vec) < distsqr) {
484                                 BMO_SetFlag(bm, v2, VERT_TESTED);
485                                 BMO_SetFlag(bm, v2, VERT_DOUBLE);
486                                 BMO_SetFlag(bm, v, VERT_TARGET);
487                         
488                                 BMO_Insert_MapPointer(bm, &weldop, "targetmap", v2, v);
489                         }
490                 }
491         }
492
493         V_FREE(verts);
494
495         BMO_Exec_Op(bm, &weldop);
496         BMO_Finish_Op(bm, &weldop);
497 }
498
499
500 void bmesh_finddoubles_exec(BMesh *bm, BMOperator *op)
501 {
502         BMOIter oiter;
503         BMVert *v, *v2;
504         BMVert **verts=NULL;
505         V_DECLARE(verts);
506         float dist, distsqr;
507         int i, j, len, keepvert;
508
509         dist = BMO_Get_Float(op, "dist");
510         distsqr = dist*dist;
511
512         i = 0;
513         BMO_ITER(v, &oiter, bm, op, "verts", BM_VERT) {
514                 V_GROW(verts);
515                 verts[i++] = v;
516         }
517
518         keepvert = BMO_IterNew(&oiter, bm, op, "keepverts", BM_VERT) != NULL;
519
520         /*sort by vertex coordinates added together*/
521         qsort(verts, V_COUNT(verts), sizeof(void*), vergaverco);
522         
523         BMO_Flag_Buffer(bm, op, "keepverts", VERT_KEEP, BM_VERT);
524
525         len = V_COUNT(verts);
526         for (i=0; i<len; i++) {
527                 v = verts[i];
528                 if (BMO_TestFlag(bm, v, VERT_DOUBLE)) continue;
529                 
530                 for (j=i+1; j<len; j++) {
531                         v2 = verts[j];
532                         if ((v2->co[0]+v2->co[1]+v2->co[2]) - (v->co[0]+v->co[1]+v->co[2])
533                              > distsqr) break;
534                         
535                         if (keepvert) {
536                                 if (BMO_TestFlag(bm, v2, VERT_KEEP) == BMO_TestFlag(bm, v, VERT_KEEP))
537                                         continue;
538                         }
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 }