fixed some memory leaks, and made fkey only do one thing at a time.
[blender.git] / source / blender / bmesh / operators / createops.c
1 #include "MEM_guardedalloc.h"
2
3 #include "BKE_utildefines.h"
4
5 #include "BLI_memarena.h"
6 #include "BLI_mempool.h"
7 #include "BLI_heap.h"
8 #include "BLI_ghash.h"
9 #include "BLI_blenlib.h"
10 #include "BLI_arithb.h"
11
12 #include "bmesh.h"
13 #include "bmesh_operators_private.h"
14
15 #define ELE_NEW         1
16 #define ELE_OUT         2
17
18 typedef struct EPathNode {
19         struct EPathNode *next, *prev;
20         BMVert *v;
21         BMEdge *e;
22 } EPathNode;
23
24 typedef struct EPath {
25         ListBase nodes;
26         float weight;
27 } EPath;
28
29 typedef struct PathBase {
30         BLI_mempool *nodepool, *pathpool;
31 } PathBase;
32
33 typedef struct EdgeData {
34         int tag;
35         int ftag;
36 } EdgeData;
37
38 #define EDGE_MARK       1
39 #define EDGE_VIS        2
40
41 #define VERT_VIS        1
42
43 #define FACE_NEW        1
44
45 PathBase *edge_pathbase_new(void)
46 {
47         PathBase *pb = MEM_callocN(sizeof(PathBase), "PathBase");
48
49         pb->nodepool = BLI_mempool_create(sizeof(EPathNode), 1, 512);
50         pb->pathpool = BLI_mempool_create(sizeof(EPath), 1, 512);
51
52         return pb;
53 }
54
55 void edge_pathbase_free(PathBase *pathbase)
56 {
57         BLI_mempool_destroy(pathbase->nodepool);
58         BLI_mempool_destroy(pathbase->pathpool);
59         MEM_freeN(pathbase);
60 }
61
62 EPath *edge_copy_add_path(PathBase *pb, EPath *path, BMVert *appendv, BMEdge *e)
63 {
64         EPath *path2;
65         EPathNode *node, *node2;
66
67         path2 = BLI_mempool_calloc(pb->pathpool);
68         
69         for (node=path->nodes.first; node; node=node->next) {
70                 node2 = BLI_mempool_calloc(pb->nodepool);
71                 *node2 = *node;
72                 BLI_addtail(&path2->nodes, node2);
73         }
74
75         node2 = BLI_mempool_calloc(pb->nodepool);
76         node2->v = appendv;
77         node2->e = e;
78
79         BLI_addtail(&path2->nodes, node2);
80
81         return path2;
82 }
83
84 EPath *edge_path_new(PathBase *pb, BMVert *start)
85 {
86         EPath *path;
87         EPathNode *node;
88
89         path = BLI_mempool_calloc(pb->pathpool);
90         node = BLI_mempool_calloc(pb->nodepool);
91
92         node->v = start;
93         node->e = NULL;
94
95         BLI_addtail(&path->nodes, node);
96         path->weight = 0.0f;
97
98         return path;
99 }
100
101 float edge_weight_path(EPath *path, EdgeData *edata)
102 {
103         EPathNode *node;
104         float w;
105
106         for (node=path->nodes.first; node; node=node->next) {
107                 if (node->e) {
108                         w += edata[BMINDEX_GET(node->e)].ftag;
109                 }
110
111                 w += 1.0f;
112         }
113
114         return w;
115 }
116
117
118 void edge_free_path(PathBase *pathbase, EPath *path)
119 {
120         EPathNode *node, *next;
121
122         for (node=path->nodes.first; node; node=next) {
123                 next = node->next;
124                 BLI_mempool_free(pathbase->nodepool, node);
125         }
126
127         BLI_mempool_free(pathbase->pathpool, path);
128 }
129
130 EPath *edge_find_shortest_path(BMesh *bm, BMEdge *edge, EdgeData *edata, PathBase *pathbase)
131 {
132         BMIter iter;
133         BMEdge *e;
134         GHash *gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
135         BMVert *v1, *v2;
136         BMVert **verts = NULL;
137         V_DECLARE(verts);
138         Heap *heap = BLI_heap_new();
139         EPath *path = NULL, *path2;
140         EPathNode *node;
141         int i;
142
143         path = edge_path_new(pathbase, edge->v1);
144         BLI_heap_insert(heap, path->weight, path);
145         path = NULL;
146
147         while (BLI_heap_size(heap)) {
148                 if (path)
149                         edge_free_path(pathbase, path);
150                 path = BLI_heap_popmin(heap);
151                 v1 = ((EPathNode*)path->nodes.last)->v;
152                 
153                 if (v1 == edge->v2) {
154                         /*make sure this path loop doesn't already exist*/
155                         i = 0;
156                         V_RESET(verts);
157                         for (i=0, node = path->nodes.first; node; node=node->next, i++) {
158                                 V_GROW(verts);
159                                 verts[i] = node->v;
160                         }
161
162                         if (!BM_Face_Exists(bm, verts, i, NULL))
163                                 break;
164                         else
165                                 continue;
166                 }
167
168                 BM_ITER(e, &iter, bm, BM_EDGES_OF_VERT, v1) {
169                         if (e == edge || !BMO_TestFlag(bm, e, EDGE_MARK))
170                                 continue;
171                         
172                         v2 = BM_OtherEdgeVert(e, v1);
173                         
174                         if (BLI_ghash_haskey(gh, v2))
175                                 continue;
176
177                         BLI_ghash_insert(gh, v2, NULL);
178
179                         path2 = edge_copy_add_path(pathbase, path, v2, e);
180                         path2->weight = edge_weight_path(path2, edata);
181
182                         BLI_heap_insert(heap, path2->weight, path2);
183                 }
184
185                 if (BLI_heap_size(heap) == 0)
186                         path = NULL;
187         }
188
189         V_FREE(verts);
190         BLI_heap_free(heap, NULL);
191         BLI_ghash_free(gh, NULL, NULL);
192
193         return path;
194 }
195
196 void bmesh_edgenet_fill_exec(BMesh *bm, BMOperator *op)
197 {
198         BMIter iter, liter;
199         BMOIter siter;
200         BMEdge *e, *edge;
201         BMLoop *l;
202         BMFace *f;
203         EPath *path;
204         EPathNode *node;
205         EdgeData *edata;
206         BMEdge **edges = NULL;
207         PathBase *pathbase = edge_pathbase_new();
208         V_DECLARE(edges);
209         int i, j;
210
211         if (!bm->totvert || !bm->totedge)
212                 return;
213
214         edata = MEM_callocN(sizeof(EdgeData)*bm->totedge, "EdgeData");
215         BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE);
216
217         i = 0;
218         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
219                 BMINDEX_SET(e, i);
220                 
221                 if (!BMO_TestFlag(bm, e, EDGE_MARK)) {
222                         edata[i].tag = 2;
223                 }
224
225                 i += 1;
226         }
227
228         while (1) {
229                 edge = NULL;
230
231                 BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
232                         if (edata[BMINDEX_GET(e)].tag < 2) {
233                                 edge = e;
234                                 break;
235                         }
236                 }
237
238                 if (!edge)
239                         break;
240
241                 edata[BMINDEX_GET(edge)].tag += 1;
242
243                 path = edge_find_shortest_path(bm, edge, edata, pathbase);
244                 if (!path)
245                         continue;
246                 
247                 V_RESET(edges);
248                 i = 0;
249                 for (node=path->nodes.first; node; node=node->next) {
250                         if (!node->next)
251                                 continue;
252
253                         e = BM_Edge_Exist(node->v, node->next->v);
254                         
255                         /*this should never happen*/
256                         if (!e)
257                                 break;
258                         
259                         edata[BMINDEX_GET(e)].ftag++;
260                         V_GROW(edges);
261                         edges[i++] = e;
262                 }
263                 
264                 V_GROW(edges);
265                 edges[i++] = edge;
266
267                 f = BM_Make_Ngon(bm, edge->v1, edge->v2, edges, i, 1);
268                 if (f)
269                         BMO_SetFlag(bm, f, FACE_NEW);
270
271                 edge_free_path(pathbase, path);
272         }
273
274         BMO_Flag_To_Slot(bm, op, "faceout", FACE_NEW, BM_FACE);
275
276         V_FREE(edges);
277         edge_pathbase_free(pathbase);
278         MEM_freeN(edata);
279 }
280
281 /* evaluate if entire quad is a proper convex quad */
282 static int convex(float *v1, float *v2, float *v3, float *v4)
283 {
284         float nor[3], nor1[3], nor2[3], vec[4][2];
285         
286         /* define projection, do both trias apart, quad is undefined! */
287         CalcNormFloat(v1, v2, v3, nor1);
288         CalcNormFloat(v1, v3, v4, nor2);
289         nor[0]= ABS(nor1[0]) + ABS(nor2[0]);
290         nor[1]= ABS(nor1[1]) + ABS(nor2[1]);
291         nor[2]= ABS(nor1[2]) + ABS(nor2[2]);
292
293         if(nor[2] >= nor[0] && nor[2] >= nor[1]) {
294                 vec[0][0]= v1[0]; vec[0][1]= v1[1];
295                 vec[1][0]= v2[0]; vec[1][1]= v2[1];
296                 vec[2][0]= v3[0]; vec[2][1]= v3[1];
297                 vec[3][0]= v4[0]; vec[3][1]= v4[1];
298         }
299         else if(nor[1] >= nor[0] && nor[1]>= nor[2]) {
300                 vec[0][0]= v1[0]; vec[0][1]= v1[2];
301                 vec[1][0]= v2[0]; vec[1][1]= v2[2];
302                 vec[2][0]= v3[0]; vec[2][1]= v3[2];
303                 vec[3][0]= v4[0]; vec[3][1]= v4[2];
304         }
305         else {
306                 vec[0][0]= v1[1]; vec[0][1]= v1[2];
307                 vec[1][0]= v2[1]; vec[1][1]= v2[2];
308                 vec[2][0]= v3[1]; vec[2][1]= v3[2];
309                 vec[3][0]= v4[1]; vec[3][1]= v4[2];
310         }
311         
312         /* linetests, the 2 diagonals have to instersect to be convex */
313         if( IsectLL2Df(vec[0], vec[2], vec[1], vec[3]) > 0 ) return 1;
314         return 0;
315 }
316
317 /*this is essentially new fkey*/
318 void bmesh_contextual_create_exec(BMesh *bm, BMOperator *op)
319 {
320         BMOperator op2;
321         BMOIter oiter;
322         BMIter iter, liter;
323         BMHeader *h;
324         BMVert *v, *verts[4];
325         BMEdge *e;
326         BMLoop *l;
327         BMFace *f;
328         int totv=0, tote=0, totf=0, amount;
329
330         /*count number of each element type we were passed*/
331         BMO_ITER(h, &oiter, bm, op, "geom", BM_VERT|BM_EDGE|BM_FACE) {
332                 switch (h->type) {
333                         case BM_VERT: totv++; break;
334                         case BM_EDGE: tote++; break;
335                         case BM_FACE: totf++; break;
336                 }
337
338                 BMO_SetFlag(bm, h, ELE_NEW);
339         }
340         
341         /*first call dissolve faces*/
342         BMO_InitOpf(bm, &op2, "dissolvefaces faces=%ff", ELE_NEW);
343         BMO_Exec_Op(bm, &op2);
344         
345         /*if we dissolved anything, then return.*/
346         if (BMO_CountSlotBuf(bm, &op2, "regionout")) {
347                 BMO_CopySlot(&op2, op, "regionout", "faceout");
348                 BMO_Finish_Op(bm, &op2);
349                 return;
350         }
351
352         BMO_Finish_Op(bm, &op2);
353
354         /*call edgenet create*/
355         BMO_InitOpf(bm, &op2, "edgenet_fill edges=%fe", ELE_NEW);
356         BMO_Exec_Op(bm, &op2);
357
358         /*return if edge net create did something*/
359         if (BMO_CountSlotBuf(bm, &op2, "faceout")) {
360                 BMO_CopySlot(&op2, op, "faceout", "faceout");
361                 BMO_Finish_Op(bm, &op2);
362                 return;
363         }
364
365         BMO_Finish_Op(bm, &op2);
366         
367         /*now, count how many verts we have*/
368         amount = 0;
369         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
370                 if (BMO_TestFlag(bm, v, ELE_NEW)) {
371                         verts[amount] = v;
372                         amount++;
373
374                         if (amount > 4) break;
375                 }
376         }
377
378         if (amount == 2) {
379                 /*create edge*/
380                 e = BM_Make_Edge(bm, verts[0], verts[1], NULL, 1);
381                 BMO_SetFlag(bm, e, ELE_OUT);            
382         } else if (amount == 3) {
383                 /*create triangle*/
384                 BM_Make_QuadTri(bm, verts[0], verts[1], verts[2], NULL, NULL, 1);
385         } else if (amount == 4) {
386                 f = NULL;
387
388                 /* the order of vertices can be anything, 6 cases to check */
389                 if( convex(verts[0]->co, verts[1]->co, verts[2]->co, verts[3]->co) ) {
390                         f= BM_Make_QuadTri(bm, verts[0], verts[1], verts[2], verts[3], NULL, 1);
391                 }
392                 else if( convex(verts[0]->co, verts[2]->co, verts[3]->co, verts[1]->co) ) {
393                         f= BM_Make_QuadTri(bm, verts[0], verts[2], verts[3], verts[1], NULL, 1);
394                 }
395                 else if( convex(verts[0]->co, verts[2]->co, verts[1]->co, verts[3]->co) ) {
396                         f= BM_Make_QuadTri(bm, verts[0], verts[2], verts[1], verts[3], NULL, 1);
397                 }
398                 else if( convex(verts[0]->co, verts[1]->co, verts[3]->co, verts[2]->co) ) {
399                         f= BM_Make_QuadTri(bm, verts[0], verts[1], verts[3], verts[2], NULL, 1);
400                 }
401                 else if( convex(verts[0]->co, verts[3]->co, verts[2]->co, verts[1]->co) ) {
402                         f= BM_Make_QuadTri(bm, verts[0], verts[3], verts[2], verts[1], NULL, 1);
403                 }
404                 else if( convex(verts[0]->co, verts[3]->co, verts[1]->co, verts[2]->co) ) {
405                         f= BM_Make_QuadTri(bm, verts[0], verts[3], verts[1], verts[2], NULL, 1);
406                 }
407                 else {
408                         printf("cannot find nice quad from concave set of vertices\n");
409                 }
410
411                 if (f) BMO_SetFlag(bm, f, ELE_OUT);
412         }
413 }