1bbb222d67e41224c6a2e4414c198f5841a357ec
[blender.git] / source / blender / bmesh / operators / removedoubles.c
1 #include "MEM_guardedalloc.h"
2
3 #include "BKE_utildefines.h"
4
5 #include "bmesh.h"
6 #include "mesh_intern.h"
7 #include "bmesh_private.h"
8 #include "BLI_arithb.h"
9 #include "BLI_ghash.h"
10
11 #include <stdio.h>
12 #include <stdlib.h>
13 #include <string.h>
14
15 #define BL(ptr) ((BMLoop*)(ptr))
16
17 void remdoubles_splitface(BMFace *f, BMesh *bm, BMOperator *op)
18 {
19         BMIter liter;
20         BMLoop *l;
21         BMVert *v2, *doub;
22         int split=0;
23
24         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
25                 v2 = BMO_Get_MapPointer(bm, op, "targetmap", l->v);
26                 /*ok: if v2 is NULL (e.g. not in the map) then it's
27                       a target vert, otherwise it's a double*/
28                 if (v2 && BM_Vert_In_Face(f, v2) && v2 != BL(l->head.prev)->v 
29                     && v2 != BL(l->head.next)->v)
30                 {
31                         doub = l->v;
32                         split = 1;
33                         break;
34                 }
35         }
36
37         if (split) {
38                 BMLoop *nl;
39                 BMFace *f2 = BM_Split_Face(bm, f, doub, v2, &nl, NULL);
40
41                 remdoubles_splitface(f, bm, op);
42                 remdoubles_splitface(f2, bm, op);
43         }
44 }
45
46 #define ELE_DEL         1
47 #define EDGE_COL        2
48 #define FACE_MARK       2
49
50 #if 0
51 int remdoubles_face_overlaps(BMesh *bm, BMVert **varr, 
52                              int len, BMFace *exclude, 
53                              BMFace **overlapface)
54 {
55         BMIter vertfaces;
56         BMFace *f;
57         int i, amount;
58
59         if (overlapface) *overlapface = NULL;
60
61         for(i=0; i < len; i++){
62                 f = BMIter_New(&vertfaces, bm, BM_FACES_OF_VERT, varr[i] );
63                 while(f){
64                         amount = BM_Verts_In_Face(bm, f, varr, len);
65                         if(amount >= len){
66                                 if (overlapface) *overlapface = f;
67                                 return 1;                               
68                         }
69                         f = BMIter_Step(&vertfaces);
70                 }
71         }
72         return 0;
73 }
74 #endif
75
76 void bmesh_weldverts_exec(BMesh *bm, BMOperator *op)
77 {
78         BMIter iter, liter;
79         BMVert *v, *v2;
80         BMEdge *e, *e2, **edges = NULL;
81         V_DECLARE(edges);
82         BMLoop *l;
83         BMFace *f, *f2;
84         int a;
85
86         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
87                 if (BMO_Get_MapPointer(bm, op, "targetmap", v))
88                         BMO_SetFlag(bm, v, ELE_DEL);
89         }
90
91         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
92                 remdoubles_splitface(f, bm, op);
93         }
94         
95         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
96                 v = BMO_Get_MapPointer(bm, op, "targetmap", e->v1);
97                 v2 = BMO_Get_MapPointer(bm, op, "targetmap", e->v2);
98                 
99                 if (!v) v = e->v1;
100                 if (!v2) v2 = e->v2;
101
102                 if ((e->v1 != v) || (e->v2 != v2)) {
103                         if (v == v2) BMO_SetFlag(bm, e, EDGE_COL);
104                         else BM_Make_Edge(bm, v, v2, e, 1);
105
106                         BMO_SetFlag(bm, e, ELE_DEL);
107                 }
108         }
109
110         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
111                 BMINDEX_SET(f, 0);
112                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
113                         if (BMO_TestFlag(bm, l->v, ELE_DEL))
114                                 BMO_SetFlag(bm, f, FACE_MARK);
115                         if (BMO_TestFlag(bm, l->e, EDGE_COL)) 
116                                 BMINDEX_SET(f, BMINDEX_GET(f)+1);
117                 }
118         }
119
120         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
121                 if (!BMO_TestFlag(bm, f, FACE_MARK)) continue;
122                 if (f->len - BMINDEX_GET(f) + 1 < 3) {
123                         BMO_SetFlag(bm, f, ELE_DEL);
124                         continue;
125                 }
126
127                 V_RESET(edges);
128                 a = 0;
129                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
130                         v = l->v;
131                         v2 = BL(l->head.next)->v;
132                         if (BMO_TestFlag(bm, v, ELE_DEL)) 
133                                 v = BMO_Get_MapPointer(bm, op, "targetmap", v);
134                         if (BMO_TestFlag(bm, v2, ELE_DEL)) 
135                                         v2 = BMO_Get_MapPointer(bm, op, "targetmap", v2);
136                         
137                         e2 = BM_Edge_Exist(v, v2);
138                         if (e2) {
139                                 V_GROW(edges);
140                                 edges[a++] = e2;
141                         }
142                 }
143                 
144                 f2 = BM_Make_Ngon(bm, v, v2, edges, a, 0);
145                 if (f2) {
146                         BM_Copy_Attributes(bm, bm, f, f2);
147                         BMO_SetFlag(bm, f, ELE_DEL);
148                 }
149
150                 /*need to still copy customdata stuff here, will do later*/
151         }
152
153         BMO_CallOpf(bm, "del geom=%fvef context=%i", ELE_DEL, DEL_ONLYTAGGED);
154
155         V_FREE(edges);
156 }
157
158 static int vergaverco(const void *e1, const void *e2)
159 {
160         const BMVert *v1 = *(void**)e1, *v2 = *(void**)e2;
161         float x1 = v1->co[0] + v1->co[1] + v1->co[2];
162         float x2 = v2->co[0] + v2->co[1] + v2->co[2];
163
164         if (x1 > x2) return 1;
165         else if (x1 < x2) return -1;
166         else return 0;
167 }
168
169 #define VERT_TESTED     1
170 #define VERT_DOUBLE     2
171 #define VERT_TARGET     4
172
173 void bmesh_removedoubles_exec(BMesh *bm, BMOperator *op)
174 {
175         BMOperator weldop;
176         BMOIter oiter;
177         BMVert *v, *v2;
178         BMVert **verts=NULL;
179         V_DECLARE(verts);
180         float dist, distsqr;
181         int i, j, len;
182
183         dist = BMO_Get_Float(op, "dist");
184         distsqr = dist*dist;
185
186         BMO_Init_Op(&weldop, "weldverts");
187         
188         i = 0;
189         BMO_ITER(v, &oiter, bm, op, "verts", BM_VERT) {
190                 V_GROW(verts);
191                 verts[i++] = v;
192         }
193
194         /*sort by vertex coordinates added together*/
195         qsort(verts, V_COUNT(verts), sizeof(void*), vergaverco);
196         
197         len = V_COUNT(verts);
198         for (i=0; i<len; i++) {
199                 v = verts[i];
200                 if (BMO_TestFlag(bm, v, VERT_TESTED)) continue;
201                 
202                 BMO_SetFlag(bm, v, VERT_TESTED);
203                 for (j=i+1; j<len; j++) {
204                         float vec[3];
205                         
206                         v2 = verts[j];
207                         if ((v2->co[0]+v2->co[1]+v2->co[2]) - (v->co[0]+v->co[1]+v->co[2])
208                              > distsqr) break;
209
210                         vec[0] = v->co[0] - v2->co[0];
211                         vec[1] = v->co[1] - v2->co[1];
212                         vec[2] = v->co[2] - v2->co[2];
213                         
214                         if (INPR(vec, vec) < distsqr) {
215                                 BMO_SetFlag(bm, v2, VERT_TESTED);
216                                 BMO_SetFlag(bm, v2, VERT_DOUBLE);
217                                 BMO_SetFlag(bm, v, VERT_TARGET);
218                         
219                                 BMO_Insert_MapPointer(bm, &weldop, "targetmap", v2, v);
220                         }
221                 }
222         }
223
224         V_FREE(verts);
225
226         BMO_Exec_Op(bm, &weldop);
227         BMO_Finish_Op(bm, &weldop);
228 }