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