merge with 2.5 at r21568
[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 && doub != v2) {
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, *l2, **loops = NULL;
83         V_DECLARE(loops);
84         BMFace *f, *f2;
85         int a;
86
87         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
88                 if (BMO_Get_MapPointer(bm, op, "targetmap", v))
89                         BMO_SetFlag(bm, v, ELE_DEL);
90         }
91
92         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
93                 remdoubles_splitface(f, bm, op);
94         }
95         
96         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
97                 v = BMO_Get_MapPointer(bm, op, "targetmap", e->v1);
98                 v2 = BMO_Get_MapPointer(bm, op, "targetmap", e->v2);
99                 
100                 if (!v) v = e->v1;
101                 if (!v2) v2 = e->v2;
102
103                 if ((e->v1 != v) || (e->v2 != v2)) {
104                         if (v == v2) BMO_SetFlag(bm, e, EDGE_COL);
105                         else BM_Make_Edge(bm, v, v2, e, 1);
106
107                         BMO_SetFlag(bm, e, ELE_DEL);
108                 }
109         }
110
111         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
112                 BMINDEX_SET(f, 0);
113                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
114                         if (BMO_TestFlag(bm, l->v, ELE_DEL))
115                                 BMO_SetFlag(bm, f, FACE_MARK);
116                         if (BMO_TestFlag(bm, l->e, EDGE_COL)) 
117                                 BMINDEX_SET(f, BMINDEX_GET(f)+1);
118                 }
119         }
120
121         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
122                 if (!BMO_TestFlag(bm, f, FACE_MARK)) continue;
123                 if (f->len - BMINDEX_GET(f) < 3) {
124                         BMO_SetFlag(bm, f, ELE_DEL);
125                         continue;
126                 }
127
128                 V_RESET(edges);
129                 V_RESET(loops);
130                 a = 0;
131                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
132                         v = l->v;
133                         v2 = BL(l->head.next)->v;
134                         if (BMO_TestFlag(bm, v, ELE_DEL)) 
135                                 v = BMO_Get_MapPointer(bm, op, "targetmap", v);
136                         if (BMO_TestFlag(bm, v2, ELE_DEL)) 
137                                         v2 = BMO_Get_MapPointer(bm, op, "targetmap", v2);
138                         
139                         e2 = v != v2 ? BM_Edge_Exist(v, v2) : NULL;
140                         if (e2) {
141                                 V_GROW(edges);
142                                 V_GROW(loops);
143
144                                 edges[a] = e2;
145                                 loops[a] = l;
146
147                                 a++;
148                         }
149                 }
150                 
151                 v = loops[0]->v;
152                 v2 = loops[1]->v;
153
154                 if (BMO_TestFlag(bm, v, ELE_DEL)) 
155                         v = BMO_Get_MapPointer(bm, op, "targetmap", v);
156                 if (BMO_TestFlag(bm, v2, ELE_DEL)) 
157                         v2 = BMO_Get_MapPointer(bm, op, "targetmap", v2);
158                 
159
160                 f2 = BM_Make_Ngon(bm, v, v2, edges, a, 0);
161                 if (f2) {
162                         BM_Copy_Attributes(bm, bm, f, f2);
163                         BMO_SetFlag(bm, f, ELE_DEL);
164
165                         a = 0;
166                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f2) {
167                                 l2 = loops[a];
168                                 BM_Copy_Attributes(bm, bm, l2, l);
169
170                                 a++;
171                         }
172                 }
173
174                 /*need to still copy customdata stuff here, will do later*/
175         }
176
177         BMO_CallOpf(bm, "del geom=%fvef context=%i", ELE_DEL, DEL_ONLYTAGGED);
178
179         V_FREE(edges);
180 }
181
182 static int vergaverco(const void *e1, const void *e2)
183 {
184         const BMVert *v1 = *(void**)e1, *v2 = *(void**)e2;
185         float x1 = v1->co[0] + v1->co[1] + v1->co[2];
186         float x2 = v2->co[0] + v2->co[1] + v2->co[2];
187
188         if (x1 > x2) return 1;
189         else if (x1 < x2) return -1;
190         else return 0;
191 }
192
193 #define VERT_TESTED     1
194 #define VERT_DOUBLE     2
195 #define VERT_TARGET     4
196 #define VERT_KEEP       8
197
198 void bmesh_removedoubles_exec(BMesh *bm, BMOperator *op)
199 {
200         BMOperator weldop;
201         BMOIter oiter;
202         BMVert *v, *v2;
203         BMVert **verts=NULL;
204         V_DECLARE(verts);
205         float dist, distsqr;
206         int i, j, len;
207
208         dist = BMO_Get_Float(op, "dist");
209         distsqr = dist*dist;
210
211         BMO_Init_Op(&weldop, "weldverts");
212         
213         i = 0;
214         BMO_ITER(v, &oiter, bm, op, "verts", BM_VERT) {
215                 V_GROW(verts);
216                 verts[i++] = v;
217         }
218
219         /*sort by vertex coordinates added together*/
220         qsort(verts, V_COUNT(verts), sizeof(void*), vergaverco);
221         
222         len = V_COUNT(verts);
223         for (i=0; i<len; i++) {
224                 v = verts[i];
225                 if (BMO_TestFlag(bm, v, VERT_TESTED)) continue;
226                 
227                 BMO_SetFlag(bm, v, VERT_TESTED);
228                 for (j=i+1; j<len; j++) {
229                         float vec[3];
230                         
231                         v2 = verts[j];
232                         if ((v2->co[0]+v2->co[1]+v2->co[2]) - (v->co[0]+v->co[1]+v->co[2])
233                              > distsqr) break;
234
235                         vec[0] = v->co[0] - v2->co[0];
236                         vec[1] = v->co[1] - v2->co[1];
237                         vec[2] = v->co[2] - v2->co[2];
238                         
239                         if (INPR(vec, vec) < distsqr) {
240                                 BMO_SetFlag(bm, v2, VERT_TESTED);
241                                 BMO_SetFlag(bm, v2, VERT_DOUBLE);
242                                 BMO_SetFlag(bm, v, VERT_TARGET);
243                         
244                                 BMO_Insert_MapPointer(bm, &weldop, "targetmap", v2, v);
245                         }
246                 }
247         }
248
249         V_FREE(verts);
250
251         BMO_Exec_Op(bm, &weldop);
252         BMO_Finish_Op(bm, &weldop);
253 }
254
255
256 void bmesh_finddoubles_exec(BMesh *bm, BMOperator *op)
257 {
258         BMOIter oiter;
259         BMVert *v, *v2;
260         BMVert **verts=NULL;
261         V_DECLARE(verts);
262         float dist, distsqr;
263         int i, j, len;
264
265         dist = BMO_Get_Float(op, "dist");
266         distsqr = dist*dist;
267
268         i = 0;
269         BMO_ITER(v, &oiter, bm, op, "verts", BM_VERT) {
270                 V_GROW(verts);
271                 verts[i++] = v;
272         }
273
274         /*sort by vertex coordinates added together*/
275         //qsort(verts, V_COUNT(verts), sizeof(void*), vergaverco);
276         
277         BMO_Flag_Buffer(bm, op, "keepverts", VERT_KEEP);
278
279         len = V_COUNT(verts);
280         for (i=0; i<len; i++) {
281                 v = verts[i];
282                 if (BMO_TestFlag(bm, v, VERT_DOUBLE)) continue;
283                 
284                 //BMO_SetFlag(bm, v, VERT_TESTED);
285                 for (j=0; j<len; j++) {
286                         if (j == i) continue;
287
288                         //float vec[3];
289                         if (BMO_TestFlag(bm, v, VERT_KEEP)) continue;
290
291                         v2 = verts[j];
292                         //if ((v2->co[0]+v2->co[1]+v2->co[2]) - (v->co[0]+v->co[1]+v->co[2])
293                         //     > distsqr) break;
294
295                         //vec[0] = v->co[0] - v2->co[0];
296                         //vec[1] = v->co[1] - v2->co[1];
297                         //vec[2] = v->co[2] - v2->co[2];
298                         
299                         if (VecLenCompare(v->co, v2->co, dist)) {
300                                 BMO_SetFlag(bm, v2, VERT_DOUBLE);
301                                 BMO_SetFlag(bm, v, VERT_TARGET);
302                         
303                                 BMO_Insert_MapPointer(bm, op, "targetmapout", v2, v);
304                         }
305                 }
306         }
307
308         V_FREE(verts);
309 }