Style Cleanup: whitespace and some formatting.
[blender.git] / source / blender / bmesh / operators / removedoubles.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Joseph Eagar.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 #include "MEM_guardedalloc.h"
24
25 #include "DNA_meshdata_types.h"
26 #include "DNA_mesh_types.h"
27 #include "DNA_object_types.h"
28 #include "DNA_scene_types.h"
29
30 #include "BLI_utildefines.h"
31
32 #include "BLI_math.h"
33 #include "BLI_ghash.h"
34 #include "BLI_array.h"
35 #include "BLI_utildefines.h"
36
37 #include "bmesh.h"
38 #include "mesh_intern.h"
39 #include "bmesh_private.h"
40
41 #include <stdio.h>
42 #include <stdlib.h>
43 #include <string.h>
44
45 static void remdoubles_splitface(BMFace *f, BMesh *bm, BMOperator *op)
46 {
47         BMIter liter;
48         BMLoop *l;
49         BMVert *v2, *doub;
50         int split = 0;
51
52         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
53                 v2 = BMO_Get_MapPointer(bm, op, "targetmap", l->v);
54                 /* ok: if v2 is NULL (e.g. not in the map) then it's
55                  *     a target vert, otherwise it's a doubl */
56                 if (v2 && BM_Vert_In_Face(f, v2) && (v2 != ((BMLoop *)l->prev)->v) && (v2 != ((BMLoop *)l->next)->v)) {
57                         doub = l->v;
58                         split = 1;
59                         break;
60                 }
61         }
62
63         if (split && doub != v2) {
64                 BMLoop *nl;
65                 BMFace *f2 = BM_Split_Face(bm, f, doub, v2, &nl, NULL);
66
67                 remdoubles_splitface(f, bm, op);
68                 remdoubles_splitface(f2, bm, op);
69         }
70 }
71
72 #define ELE_DEL         1
73 #define EDGE_COL        2
74 #define FACE_MARK       2
75
76 #if 0
77 int remdoubles_face_overlaps(BMesh *bm, BMVert **varr,
78                              int len, BMFace *exclude,
79                              BMFace **overlapface)
80 {
81         BMIter vertfaces;
82         BMFace *f;
83         int i, amount;
84
85         if (overlapface) *overlapface = NULL;
86
87         for (i = 0; i < len; i++) {
88                 f = BMIter_New(&vertfaces, bm, BM_FACES_OF_VERT, varr[i]);
89                 while (f) {
90                         amount = BM_Verts_In_Face(bm, f, varr, len);
91                         if (amount >= len) {
92                                 if (overlapface) *overlapface = f;
93                                 return TRUE;
94                         }
95                         f = BMIter_Step(&vertfaces);
96                 }
97         }
98         return FALSE;
99 }
100 #endif
101
102 void bmesh_weldverts_exec(BMesh *bm, BMOperator *op)
103 {
104         BMIter iter, liter;
105         BMVert *v, *v2;
106         BMEdge *e, *e2, **edges = NULL;
107         BLI_array_declare(edges);
108         BMLoop *l, *l2, **loops = NULL;
109         BLI_array_declare(loops);
110         BMFace *f, *f2;
111         int a, b;
112
113         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
114                 if ((v2 = BMO_Get_MapPointer(bm, op, "targetmap", v))) {
115                         BMO_SetFlag(bm, v, ELE_DEL);
116
117                         /* merge the vertex flags, else we get randomly selected/unselected verts */
118                         BM_MergeHFlag(v, v2);
119                 }
120         }
121
122         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
123                 remdoubles_splitface(f, bm, op);
124         }
125         
126         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
127                 if (BMO_TestFlag(bm, e->v1, ELE_DEL) || BMO_TestFlag(bm, e->v2, ELE_DEL)) {
128                         v = BMO_Get_MapPointer(bm, op, "targetmap", e->v1);
129                         v2 = BMO_Get_MapPointer(bm, op, "targetmap", e->v2);
130                         
131                         if (!v) v = e->v1;
132                         if (!v2) v2 = e->v2;
133
134                         if (v == v2)
135                                 BMO_SetFlag(bm, e, EDGE_COL);
136                         else if (!BM_Edge_Exist(v, v2))
137                                 BM_Make_Edge(bm, v, v2, e, 1);
138
139                         BMO_SetFlag(bm, e, ELE_DEL);
140                 }
141         }
142
143         /* BMESH_TODO, stop abusing face index here */
144         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
145                 BM_SetIndex(f, 0); /* set_dirty! */
146                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
147                         if (BMO_TestFlag(bm, l->v, ELE_DEL)) {
148                                 BMO_SetFlag(bm, f, FACE_MARK|ELE_DEL);
149                         }
150                         if (BMO_TestFlag(bm, l->e, EDGE_COL)) {
151                                 BM_SetIndex(f, BM_GetIndex(f) + 1); /* set_dirty! */
152                         }
153                 }
154         }
155         bm->elem_index_dirty |= BM_FACE;
156
157         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
158                 if (!BMO_TestFlag(bm, f, FACE_MARK))
159                         continue;
160
161                 if (f->len - BM_GetIndex(f) < 3) {
162                         BMO_SetFlag(bm, f, ELE_DEL);
163                         continue;
164                 }
165
166                 BLI_array_empty(edges);
167                 BLI_array_empty(loops);
168                 a = 0;
169                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
170                         v = l->v;
171                         v2 = ((BMLoop *)l->next)->v;
172                         if (BMO_TestFlag(bm, v, ELE_DEL)) {
173                                 v = BMO_Get_MapPointer(bm, op, "targetmap", v);
174                         }
175                         if (BMO_TestFlag(bm, v2, ELE_DEL)) {
176                                 v2 = BMO_Get_MapPointer(bm, op, "targetmap", v2);
177                         }
178                         
179                         e2 = v != v2 ? BM_Edge_Exist(v, v2) : NULL;
180                         if (e2) {
181                                 for (b = 0; b < a; b++) {
182                                         if (edges[b] == e2) {
183                                                 break;
184                                         }
185                                 }
186                                 if (b != a) {
187                                         continue;
188                                 }
189
190                                 BLI_array_growone(edges);
191                                 BLI_array_growone(loops);
192
193                                 edges[a] = e2;
194                                 loops[a] = l;
195
196                                 a++;
197                         }
198                 }
199                 
200                 if (BLI_array_count(loops) < 3)
201                         continue;
202                 v = loops[0]->v;
203                 v2 = loops[1]->v;
204
205                 if (BMO_TestFlag(bm, v, ELE_DEL)) {
206                         v = BMO_Get_MapPointer(bm, op, "targetmap", v);
207                 }
208                 if (BMO_TestFlag(bm, v2, ELE_DEL)) {
209                         v2 = BMO_Get_MapPointer(bm, op, "targetmap", v2);
210                 }
211                 
212                 f2 = BM_Make_Ngon(bm, v, v2, edges, a, 1);
213                 if (f2 && (f2 != f)) {
214                         BM_Copy_Attributes(bm, bm, f, f2);
215
216                         a = 0;
217                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f2) {
218                                 l2 = loops[a];
219                                 BM_Copy_Attributes(bm, bm, l2, l);
220
221                                 a++;
222                         }
223                 }
224         }
225
226         BMO_CallOpf(bm, "del geom=%fvef context=%i", ELE_DEL, DEL_ONLYTAGGED);
227
228         BLI_array_free(edges);
229         BLI_array_free(loops);
230 }
231
232 static int vergaverco(const void *e1, const void *e2)
233 {
234         const BMVert *v1 = *(void **)e1, *v2 = *(void **)e2;
235         float x1 = v1->co[0] + v1->co[1] + v1->co[2];
236         float x2 = v2->co[0] + v2->co[1] + v2->co[2];
237
238         if      (x1 > x2) return  1;
239         else if (x1 < x2) return -1;
240         else return 0;
241 }
242
243 #define VERT_TESTED     1
244 #define VERT_DOUBLE     2
245 #define VERT_TARGET     4
246 #define VERT_KEEP       8
247 #define VERT_MARK       16
248 #define VERT_IN         32
249
250 #define EDGE_MARK       1
251
252 void bmesh_pointmerge_facedata_exec(BMesh *bm, BMOperator *op)
253 {
254         BMOIter siter;
255         BMIter iter;
256         BMVert *v, *snapv;
257         BMLoop *l, *firstl = NULL;
258         float fac;
259         int i, tot;
260
261         snapv = BMO_IterNew(&siter, bm, op, "snapv", BM_VERT);
262         tot = BM_Vert_FaceCount(snapv);
263
264         if (!tot)
265                 return;
266
267         fac = 1.0f / tot;
268         BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, snapv) {
269                 if (!firstl) {
270                         firstl = l;
271                 }
272                 
273                 for (i = 0; i < bm->ldata.totlayer; i++) {
274                         if (CustomData_layer_has_math(&bm->ldata, i)) {
275                                 int type = bm->ldata.layers[i].type;
276                                 void *e1, *e2;
277
278                                 e1 = CustomData_bmesh_get_layer_n(&bm->ldata, firstl->head.data, i);
279                                 e2 = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
280                                 
281                                 CustomData_data_multiply(type, e2, fac);
282
283                                 if (l != firstl)
284                                         CustomData_data_add(type, e1, e2);
285                         }
286                 }
287         }
288
289         BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
290                 BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) {
291                         if (l == firstl) {
292                                 continue;
293                         }
294
295                         CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, firstl->head.data, &l->head.data);
296                 }
297         }
298 }
299
300 void bmesh_vert_average_facedata_exec(BMesh *bm, BMOperator *op)
301 {
302         BMOIter siter;
303         BMIter iter;
304         BMVert *v;
305         BMLoop *l /* , *firstl = NULL */;
306         CDBlockBytes min, max;
307         void *block;
308         int i, type;
309
310         for (i = 0; i < bm->ldata.totlayer; i++) {
311                 if (!CustomData_layer_has_math(&bm->ldata, i))
312                         continue;
313                 
314                 type = bm->ldata.layers[i].type;
315                 CustomData_data_initminmax(type, &min, &max);
316
317                 BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
318                         BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) {
319                                 block = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
320                                 CustomData_data_dominmax(type, block, &min, &max);
321                         }
322                 }
323
324                 CustomData_data_multiply(type, &min, 0.5f);
325                 CustomData_data_multiply(type, &max, 0.5f);
326                 CustomData_data_add(type, &min, &max);
327
328                 BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
329                         BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) {
330                                 block = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
331                                 CustomData_data_copy_value(type, &min, block);
332                         }
333                 }
334         }
335 }
336
337 void bmesh_pointmerge_exec(BMesh *bm, BMOperator *op)
338 {
339         BMOperator weldop;
340         BMOIter siter;
341         BMVert *v, *snapv = NULL;
342         float vec[3];
343         
344         BMO_Get_Vec(op, "mergeco", vec);
345
346         //BMO_CallOpf(bm, "collapse_uvs edges=%s", op, "edges");
347         BMO_Init_Op(bm, &weldop, "weldverts");
348         
349         BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
350                 if (!snapv) {
351                         snapv = v;
352                         copy_v3_v3(snapv->co, vec);
353                 }
354                 else {
355                         BMO_Insert_MapPointer(bm, &weldop, "targetmap", v, snapv);
356                 }
357         }
358
359         BMO_Exec_Op(bm, &weldop);
360         BMO_Finish_Op(bm, &weldop);
361 }
362
363 void bmesh_collapse_exec(BMesh *bm, BMOperator *op)
364 {
365         BMOperator weldop;
366         BMWalker walker;
367         BMIter iter;
368         BMEdge *e, **edges = NULL;
369         BLI_array_declare(edges);
370         float min[3], max[3];
371         int i, tot;
372         
373         BMO_CallOpf(bm, "collapse_uvs edges=%s", op, "edges");
374         BMO_Init_Op(bm, &weldop, "weldverts");
375
376         BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE);
377
378         BMW_Init(&walker, bm, BMW_SHELL,
379                  BMW_MASK_NOP, EDGE_MARK, BMW_MASK_NOP, BMW_MASK_NOP,
380                  BMW_NIL_LAY);
381
382         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
383                 if (!BMO_TestFlag(bm, e, EDGE_MARK))
384                         continue;
385
386                 e = BMW_Begin(&walker, e->v1);
387                 BLI_array_empty(edges);
388
389                 INIT_MINMAX(min, max);
390                 for (tot = 0; e; tot++, e = BMW_Step(&walker)) {
391                         BLI_array_growone(edges);
392                         edges[tot] = e;
393
394                         DO_MINMAX(e->v1->co, min, max);
395                         DO_MINMAX(e->v2->co, min, max);
396                 }
397
398                 add_v3_v3v3(min, min, max);
399                 mul_v3_fl(min, 0.5f);
400
401                 /* snap edges to a point.  for initial testing purposes anyway */
402                 for (i = 0; i < tot; i++) {
403                         copy_v3_v3(edges[i]->v1->co, min);
404                         copy_v3_v3(edges[i]->v2->co, min);
405                         
406                         if (edges[i]->v1 != edges[0]->v1)
407                                 BMO_Insert_MapPointer(bm, &weldop, "targetmap", edges[i]->v1, edges[0]->v1);
408                         if (edges[i]->v2 != edges[0]->v1)
409                                 BMO_Insert_MapPointer(bm, &weldop, "targetmap", edges[i]->v2, edges[0]->v1);
410                 }
411         }
412         
413         BMO_Exec_Op(bm, &weldop);
414         BMO_Finish_Op(bm, &weldop);
415
416         BMW_End(&walker);
417         BLI_array_free(edges);
418 }
419
420 /* uv collapse functio */
421 static void bmesh_collapsecon_do_layer(BMesh *bm, BMOperator *op, int layer)
422 {
423         BMIter iter, liter;
424         BMFace *f;
425         BMLoop *l, *l2;
426         BMWalker walker;
427         void **blocks = NULL;
428         BLI_array_declare(blocks);
429         CDBlockBytes min, max;
430         int i, tot, type = bm->ldata.layers[layer].type;
431
432         BMO_Clear_Flag_All(bm, op, BM_ALL, 65535);
433
434         BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE);
435
436         BMW_Init(&walker, bm, BMW_LOOPDATA_ISLAND,
437                  BMW_MASK_NOP, EDGE_MARK, BMW_MASK_NOP, BMW_MASK_NOP,
438                  layer);
439
440         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
441                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
442                         if (BMO_TestFlag(bm, l->e, EDGE_MARK)) {
443                                 /* wal */
444                                 BLI_array_empty(blocks);
445                                 tot = 0;
446                                 l2 = BMW_Begin(&walker, l);
447
448                                 CustomData_data_initminmax(type, &min, &max);
449                                 for (tot = 0; l2; tot++, l2 = BMW_Step(&walker)) {
450                                         BLI_array_growone(blocks);
451                                         blocks[tot] = CustomData_bmesh_get_layer_n(&bm->ldata, l2->head.data, layer);
452                                         CustomData_data_dominmax(type, blocks[tot], &min, &max);
453                                 }
454
455                                 if (tot) {
456                                         CustomData_data_multiply(type, &min, 0.5f);
457                                         CustomData_data_multiply(type, &max, 0.5f);
458                                         CustomData_data_add(type, &min, &max);
459
460                                         /* snap CD (uv, vcol) points to their centroi */
461                                         for (i = 0; i < tot; i++) {
462                                                 CustomData_data_copy_value(type, &min, blocks[i]);
463                                         }
464                                 }
465                         }
466                 }
467         }
468
469         BMW_End(&walker);
470         BLI_array_free(blocks);
471 }
472
473 void bmesh_collapsecon_exec(BMesh *bm, BMOperator *op)
474 {
475         int i;
476
477         for (i = 0; i < bm->ldata.totlayer; i++) {
478                 if (CustomData_layer_has_math(&bm->ldata, i))
479                         bmesh_collapsecon_do_layer(bm, op, i);
480         }
481 }
482
483 void bmesh_finddoubles_common(BMesh *bm, BMOperator *op, BMOperator *optarget, const char *targetmapname)
484 {
485         BMOIter oiter;
486         BMVert *v, *v2;
487         BMVert **verts = NULL;
488         BLI_array_declare(verts);
489         float dist, dist3;
490         int i, j, len, keepvert = 0;
491
492         dist = BMO_Get_Float(op, "dist");
493         dist3 = dist * 3.0f;
494
495         i = 0;
496         BMO_ITER(v, &oiter, bm, op, "verts", BM_VERT) {
497                 BLI_array_growone(verts);
498                 verts[i++] = v;
499         }
500
501         /* Test whether keepverts arg exists and is non-empty */
502         if (BMO_HasSlot(op, "keepverts")) {
503                 keepvert = BMO_IterNew(&oiter, bm, op, "keepverts", BM_VERT) != NULL;
504         }
505
506         /* sort by vertex coordinates added togethe */
507         qsort(verts, BLI_array_count(verts), sizeof(void *), vergaverco);
508
509         /* Flag keepverts */
510         if (keepvert) {
511                 BMO_Flag_Buffer(bm, op, "keepverts", VERT_KEEP, BM_VERT);
512         }
513
514         len = BLI_array_count(verts);
515         for (i = 0; i < len; i++) {
516                 v = verts[i];
517                 if (BMO_TestFlag(bm, v, VERT_DOUBLE)) continue;
518                 
519                 for (j = i + 1; j < len; j++) {
520                         v2 = verts[j];
521
522                         /* Compare sort values of the verts using 3x tolerance (allowing for the tolerance
523                          * on each of the three axes). This avoids the more expensive length comparison
524                          * for most vertex pairs. */
525                         if ((v2->co[0]+v2->co[1]+v2->co[2])-(v->co[0]+v->co[1]+v->co[2]) > dist3)
526                                 break;
527
528                         if (keepvert) {
529                                 if (BMO_TestFlag(bm, v2, VERT_KEEP) == BMO_TestFlag(bm, v, VERT_KEEP))
530                                         continue;
531                         }
532
533                         if (compare_len_v3v3(v->co, v2->co, dist)) {
534
535                                 /* If one vert is marked as keep, make sure it will be the target */
536                                 if (BMO_TestFlag(bm, v2, VERT_KEEP)) {
537                                         SWAP(BMVert *, v, v2);
538                                 }
539
540                                 BMO_SetFlag(bm, v2, VERT_DOUBLE);
541                                 BMO_SetFlag(bm, v, VERT_TARGET);
542                         
543                                 BMO_Insert_MapPointer(bm, optarget, targetmapname, v2, v);
544                         }
545                 }
546         }
547
548         BLI_array_free(verts);
549 }
550
551 void bmesh_removedoubles_exec(BMesh *bm, BMOperator *op)
552 {
553         BMOperator weldop;
554
555         BMO_Init_Op(bm, &weldop, "weldverts");
556         bmesh_finddoubles_common(bm, op, &weldop, "targetmap");
557         BMO_Exec_Op(bm, &weldop);
558         BMO_Finish_Op(bm, &weldop);
559 }
560
561
562 void bmesh_finddoubles_exec(BMesh *bm, BMOperator *op)
563 {
564         bmesh_finddoubles_common(bm, op, op, "targetmapout");
565 }
566
567 void bmesh_automerge_exec(BMesh *bm, BMOperator *op)
568 {
569         BMOperator findop, weldop;
570         BMIter viter;
571         BMVert *v;
572
573         /* The "verts" input sent to this op is the set of verts that
574          * can be merged away into any other verts. Mark all other verts
575          * as VERT_KEEP. */
576         BMO_Flag_Buffer(bm, op, "verts", VERT_IN, BM_VERT);
577         BM_ITER(v, &viter, bm, BM_VERTS_OF_MESH, NULL) {
578                 if (!BMO_TestFlag(bm, v, VERT_IN)) {
579                         BMO_SetFlag(bm, v, VERT_KEEP);
580                 }
581         }
582
583         /* Search for doubles among all vertices, but only merge non-VERT_KEEP
584          * vertices into VERT_KEEP vertices. */
585         BMO_InitOpf(bm, &findop, "finddoubles verts=%av keepverts=%fv", VERT_KEEP);
586         BMO_CopySlot(op, &findop, "dist", "dist");
587         BMO_Exec_Op(bm, &findop);
588
589         /* weld the vertices */
590         BMO_Init_Op(bm, &weldop, "weldverts");
591         BMO_CopySlot(&findop, &weldop, "targetmapout", "targetmap");
592         BMO_Exec_Op(bm, &weldop);
593
594         BMO_Finish_Op(bm, &findop);
595         BMO_Finish_Op(bm, &weldop);
596 }