56382d18b0060a54ac3f83af5bd079797b5e2a1e
[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 FACE_NEW        1
42
43 PathBase *edge_pathbase_new(void)
44 {
45         PathBase *pb = MEM_callocN(sizeof(PathBase), "PathBase");
46
47         pb->nodepool = BLI_mempool_create(sizeof(EPathNode), 1, 512);
48         pb->pathpool = BLI_mempool_create(sizeof(EPath), 1, 512);
49
50         return pb;
51 }
52
53 void edge_pathbase_free(PathBase *pathbase)
54 {
55         BLI_mempool_destroy(pathbase->nodepool);
56         BLI_mempool_destroy(pathbase->pathpool);
57         MEM_freeN(pathbase);
58 }
59
60 EPath *edge_copy_add_path(PathBase *pb, EPath *path, BMVert *appendv, BMEdge *e)
61 {
62         EPath *path2;
63         EPathNode *node, *node2;
64
65         path2 = BLI_mempool_calloc(pb->pathpool);
66         
67         for (node=path->nodes.first; node; node=node->next) {
68                 node2 = BLI_mempool_calloc(pb->nodepool);
69                 *node2 = *node;
70                 BLI_addtail(&path2->nodes, node2);
71         }
72
73         node2 = BLI_mempool_calloc(pb->nodepool);
74         node2->v = appendv;
75         node2->e = e;
76
77         BLI_addtail(&path2->nodes, node2);
78
79         return path2;
80 }
81
82 EPath *edge_path_new(PathBase *pb, BMVert *start)
83 {
84         EPath *path;
85         EPathNode *node;
86
87         path = BLI_mempool_calloc(pb->pathpool);
88         node = BLI_mempool_calloc(pb->nodepool);
89
90         node->v = start;
91         node->e = NULL;
92
93         BLI_addtail(&path->nodes, node);
94         path->weight = 0.0f;
95
96         return path;
97 }
98
99 float edge_weight_path(EPath *path, EdgeData *edata)
100 {
101         EPathNode *node;
102         float w;
103
104         for (node=path->nodes.first; node; node=node->next) {
105                 if (node->e) {
106                         w += edata[BMINDEX_GET(node->e)].ftag;
107                 }
108
109                 w += 1.0f;
110         }
111
112         return w;
113 }
114
115
116 void edge_free_path(PathBase *pathbase, EPath *path)
117 {
118         EPathNode *node, *next;
119
120         for (node=path->nodes.first; node; node=next) {
121                 next = node->next;
122                 BLI_mempool_free(pathbase->nodepool, node);
123         }
124
125         BLI_mempool_free(pathbase->pathpool, path);
126 }
127
128 EPath *edge_find_shortest_path(BMesh *bm, BMEdge *edge, EdgeData *edata, PathBase *pathbase)
129 {
130         BMIter iter;
131         BMEdge *e;
132         GHash *gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
133         BMVert *v1, *v2;
134         BMVert **verts = NULL;
135         V_DECLARE(verts);
136         Heap *heap = BLI_heap_new();
137         EPath *path = NULL, *path2;
138         EPathNode *node;
139         int i;
140
141         path = edge_path_new(pathbase, edge->v1);
142         BLI_heap_insert(heap, path->weight, path);
143         path = NULL;
144
145         while (BLI_heap_size(heap)) {
146                 if (path)
147                         edge_free_path(pathbase, path);
148                 path = BLI_heap_popmin(heap);
149                 v1 = ((EPathNode*)path->nodes.last)->v;
150                 
151                 if (v1 == edge->v2) {
152                         /*make sure this path loop doesn't already exist*/
153                         i = 0;
154                         V_RESET(verts);
155                         for (i=0, node = path->nodes.first; node; node=node->next, i++) {
156                                 V_GROW(verts);
157                                 verts[i] = node->v;
158                         }
159
160                         if (!BM_Face_Exists(bm, verts, i, NULL))
161                                 break;
162                         else
163                                 continue;
164                 }
165
166                 BM_ITER(e, &iter, bm, BM_EDGES_OF_VERT, v1) {
167                         if (e == edge || !BMO_TestFlag(bm, e, EDGE_MARK))
168                                 continue;
169                         
170                         v2 = BM_OtherEdgeVert(e, v1);
171                         
172                         if (BLI_ghash_haskey(gh, v2))
173                                 continue;
174
175                         BLI_ghash_insert(gh, v2, NULL);
176
177                         path2 = edge_copy_add_path(pathbase, path, v2, e);
178                         path2->weight = edge_weight_path(path2, edata);
179
180                         BLI_heap_insert(heap, path2->weight, path2);
181                 }
182
183                 if (BLI_heap_size(heap) == 0)
184                         path = NULL;
185         }
186
187         V_FREE(verts);
188         BLI_heap_free(heap, NULL);
189         BLI_ghash_free(gh, NULL, NULL);
190
191         return path;
192 }
193
194 void bmesh_edgenet_fill_exec(BMesh *bm, BMOperator *op)
195 {
196         BMIter iter;
197         BMOIter siter;
198         BMEdge *e, *edge;
199         BMFace *f;
200         EPath *path;
201         EPathNode *node;
202         EdgeData *edata;
203         BMEdge **edges = NULL;
204         PathBase *pathbase = edge_pathbase_new();
205         V_DECLARE(edges);
206         int i;
207
208         if (!bm->totvert || !bm->totedge)
209                 return;
210
211         edata = MEM_callocN(sizeof(EdgeData)*bm->totedge, "EdgeData");
212         BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE);
213
214         i = 0;
215         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
216                 BMINDEX_SET(e, i);
217                 
218                 if (!BMO_TestFlag(bm, e, EDGE_MARK)) {
219                         edata[i].tag = 2;
220                 }
221
222                 i += 1;
223         }
224
225         while (1) {
226                 edge = NULL;
227
228                 BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
229                         if (edata[BMINDEX_GET(e)].tag < 2) {
230                                 edge = e;
231                                 break;
232                         }
233                 }
234
235                 if (!edge)
236                         break;
237
238                 edata[BMINDEX_GET(edge)].tag += 1;
239
240                 path = edge_find_shortest_path(bm, edge, edata, pathbase);
241                 if (!path)
242                         continue;
243                 
244                 V_RESET(edges);
245                 i = 0;
246                 for (node=path->nodes.first; node; node=node->next) {
247                         if (!node->next)
248                                 continue;
249
250                         e = BM_Edge_Exist(node->v, node->next->v);
251                         
252                         /*this should never happen*/
253                         if (!e)
254                                 break;
255                         
256                         edata[BMINDEX_GET(e)].ftag++;
257                         V_GROW(edges);
258                         edges[i++] = e;
259                 }
260                 
261                 V_GROW(edges);
262                 edges[i++] = edge;
263
264                 f = BM_Make_Ngon(bm, edge->v1, edge->v2, edges, i, 1);
265                 if (f)
266                         BMO_SetFlag(bm, f, FACE_NEW);
267
268                 edge_free_path(pathbase, path);
269         }
270
271         BMO_Flag_To_Slot(bm, op, "faceout", FACE_NEW, BM_FACE);
272
273         V_FREE(edges);
274         edge_pathbase_free(pathbase);
275         MEM_freeN(edata);
276 }
277
278 /* evaluate if entire quad is a proper convex quad */
279 static int convex(float *v1, float *v2, float *v3, float *v4)
280 {
281         float nor[3], nor1[3], nor2[3], vec[4][2];
282         
283         /* define projection, do both trias apart, quad is undefined! */
284         CalcNormFloat(v1, v2, v3, nor1);
285         CalcNormFloat(v1, v3, v4, nor2);
286         nor[0]= ABS(nor1[0]) + ABS(nor2[0]);
287         nor[1]= ABS(nor1[1]) + ABS(nor2[1]);
288         nor[2]= ABS(nor1[2]) + ABS(nor2[2]);
289
290         if(nor[2] >= nor[0] && nor[2] >= nor[1]) {
291                 vec[0][0]= v1[0]; vec[0][1]= v1[1];
292                 vec[1][0]= v2[0]; vec[1][1]= v2[1];
293                 vec[2][0]= v3[0]; vec[2][1]= v3[1];
294                 vec[3][0]= v4[0]; vec[3][1]= v4[1];
295         }
296         else if(nor[1] >= nor[0] && nor[1]>= nor[2]) {
297                 vec[0][0]= v1[0]; vec[0][1]= v1[2];
298                 vec[1][0]= v2[0]; vec[1][1]= v2[2];
299                 vec[2][0]= v3[0]; vec[2][1]= v3[2];
300                 vec[3][0]= v4[0]; vec[3][1]= v4[2];
301         }
302         else {
303                 vec[0][0]= v1[1]; vec[0][1]= v1[2];
304                 vec[1][0]= v2[1]; vec[1][1]= v2[2];
305                 vec[2][0]= v3[1]; vec[2][1]= v3[2];
306                 vec[3][0]= v4[1]; vec[3][1]= v4[2];
307         }
308         
309         /* linetests, the 2 diagonals have to instersect to be convex */
310         if( IsectLL2Df(vec[0], vec[2], vec[1], vec[3]) > 0 ) return 1;
311         return 0;
312 }
313
314 BMEdge *edge_next(BMesh *bm, BMEdge *e)
315 {
316         BMIter iter;
317         BMEdge *e2;
318         int i;
319
320         for (i=0; i<2; i++) {
321                 BM_ITER(e2, &iter, bm, BM_EDGES_OF_VERT, i?e->v2:e->v1) {
322                         if (BMO_TestFlag(bm, e2, EDGE_MARK) 
323                             && !BMO_TestFlag(bm, e2, EDGE_VIS) && e2 != e)
324                         {
325                                 return e2;
326                         }
327                 }
328         }
329
330         return NULL;
331 }
332
333 void bmesh_edgenet_prepare(BMesh *bm, BMOperator *op)
334 {
335         BMOIter siter;
336         BMIter iter;
337         BMEdge *e, *e2;
338         BMEdge **edges1 = NULL, **edges2 = NULL, **edges;
339         V_DECLARE(edges1);
340         V_DECLARE(edges2);
341         V_DECLARE(edges);
342         int ok = 1;
343         int i, count;
344
345         BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE);
346         
347         /*validate that each edge has at most one other tagged edge in the
348           disk cycle around each of it's vertices*/
349         BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
350                 for (i=0; i<2; i++) {
351                         count = BMO_Vert_CountEdgeFlags(bm, i?e->v2:e->v1, EDGE_MARK);
352                         if (count > 2) {
353                                 ok = 0;
354                                 break;
355                         }
356                 }
357
358                 if (!ok) break;
359         }
360
361         /*we don't have valid edge layouts, return*/
362         if (!ok)
363                 return;
364
365
366         /*find connected loops within the input edges*/
367         count = 0;
368         while (1) {
369                 BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
370                         if (!BMO_TestFlag(bm, e, EDGE_VIS)) {
371                                 if (BMO_Vert_CountEdgeFlags(bm, e->v1, EDGE_MARK)==1)
372                                         break;
373                                 if (BMO_Vert_CountEdgeFlags(bm, e->v2, EDGE_MARK)==1)
374                                         break;
375                         }
376                 }
377                 
378                 if (!e) break;
379                 
380                 if (!count)
381                         edges = edges1;
382                 else if (count==1)
383                         edges = edges2;
384                 else break;
385                 
386                 i = 0;
387                 while (e) {
388                         BMO_SetFlag(bm, e, EDGE_VIS);
389                         V_GROW(edges);
390                         edges[i] = e;
391
392                         e = edge_next(bm, e);
393                         i++;
394                 }
395
396                 if (!count) {
397                         edges1 = edges;
398                         V_SETCOUNT(edges1, V_COUNT(edges));
399                 } else {
400                         edges2 = edges;
401                         V_SETCOUNT(edges2, V_COUNT(edges));
402                 }
403
404                 V_RESET(edges);
405                 count++;
406         }
407
408 #define EDGECON(e1, e2) (e1->v1 == e2->v1 || e1->v2 == e2->v2 || e1->v1 == e2->v2)
409
410         if (edges1 && V_COUNT(edges1) > 2 && EDGECON(edges1[0], edges1[V_COUNT(edges1)-1])) {
411                 if (edges2 && V_COUNT(edges2) > 2 && EDGECON(edges2[0], edges2[V_COUNT(edges2)-1])) {
412                         V_FREE(edges1);
413                         V_FREE(edges2);
414                         return;
415                 } else {
416                         edges1 = edges2;
417                         edges2 = NULL;
418                 }
419         }
420
421         if (edges2 && V_COUNT(edges2) > 2 && EDGECON(edges2[0], edges2[V_COUNT(edges2)-1])) {
422                 edges2 = NULL;
423         }
424
425         /*two unconnected loops, connect them*/
426         if (edges1 && edges2) {
427                 BMVert *v1, *v2, *v3, *v4;
428
429                 if (V_COUNT(edges1)==1) {
430                         v1 = edges1[0]->v1;
431                         v2 = edges1[0]->v2;
432                 } else {
433                         if (BM_Vert_In_Edge(edges1[1], edges1[0]->v1))
434                                 v1 = edges1[0]->v2;
435                         else v1 = edges1[0]->v1;
436
437                         i = V_COUNT(edges1)-1;
438                         if (BM_Vert_In_Edge(edges1[i-1], edges1[i]->v1))
439                                 v2 = edges1[i]->v2;
440                         else v2 = edges1[i]->v1;
441                 }
442
443                 if (V_COUNT(edges2)==1) {
444                         v3 = edges2[0]->v1;
445                         v4 = edges2[0]->v2;
446                 } else {
447                         if (BM_Vert_In_Edge(edges2[1], edges2[0]->v1))
448                                 v3 = edges2[0]->v2;
449                         else v3 = edges2[0]->v1;
450
451                         i = V_COUNT(edges2)-1;
452                         if (BM_Vert_In_Edge(edges2[i-1], edges2[i]->v1))
453                                 v4 = edges2[i]->v2;
454                         else v4 = edges2[i]->v1;
455                 }
456
457                 if (VecLenf(v1->co, v3->co) > VecLenf(v1->co, v4->co)) {
458                         BMVert *v;
459                         v = v3;
460                         v3 = v4;
461                         v4 = v;
462                 }
463
464                 e = BM_Make_Edge(bm, v1, v3, NULL, 1);
465                 BMO_SetFlag(bm, e, ELE_NEW);
466                 e = BM_Make_Edge(bm, v2, v4, NULL, 1);
467                 BMO_SetFlag(bm, e, ELE_NEW);
468         } else if (edges1) {
469                 BMVert *v1, *v2;
470                 
471                 if (V_COUNT(edges1) > 1) {
472                         if (BM_Vert_In_Edge(edges1[1], edges1[0]->v1))
473                                 v1 = edges1[0]->v2;
474                         else v1 = edges1[0]->v1;
475
476                         i = V_COUNT(edges1)-1;
477                         if (BM_Vert_In_Edge(edges1[i-1], edges1[i]->v1))
478                                 v2 = edges1[i]->v2;
479                         else v2 = edges1[i]->v1;
480
481                         e = BM_Make_Edge(bm, v1, v2, NULL, 1);
482                         BMO_SetFlag(bm, e, ELE_NEW);
483                 }
484         }
485         
486         BMO_Flag_To_Slot(bm, op, "edgeout", ELE_NEW, BM_EDGE);
487
488         V_FREE(edges1);
489         V_FREE(edges2);
490
491 #undef EDGECON
492 }
493
494 /*this is essentially new fkey*/
495 void bmesh_contextual_create_exec(BMesh *bm, BMOperator *op)
496 {
497         BMOperator op2;
498         BMOIter oiter;
499         BMIter iter;
500         BMHeader *h;
501         BMVert *v, *verts[4];
502         BMEdge *e;
503         BMFace *f;
504         int totv=0, tote=0, totf=0, amount;
505
506         /*count number of each element type we were passed*/
507         BMO_ITER(h, &oiter, bm, op, "geom", BM_VERT|BM_EDGE|BM_FACE) {
508                 switch (h->type) {
509                         case BM_VERT: totv++; break;
510                         case BM_EDGE: tote++; break;
511                         case BM_FACE: totf++; break;
512                 }
513
514                 BMO_SetFlag(bm, h, ELE_NEW);
515         }
516         
517         /*call edgenet create*/
518         /*  call edgenet prepare op so additional face creation cases work*/
519         BMO_InitOpf(bm, &op2, "edgenet_prepare edges=%fe", ELE_NEW);
520         BMO_Exec_Op(bm, &op2);
521         BMO_Flag_Buffer(bm, &op2, "edgeout", ELE_NEW, BM_EDGE);
522         BMO_Finish_Op(bm, &op2);
523
524         BMO_InitOpf(bm, &op2, "edgenet_fill edges=%fe", ELE_NEW);
525         BMO_Exec_Op(bm, &op2);
526
527         /*return if edge net create did something*/
528         if (BMO_CountSlotBuf(bm, &op2, "faceout")) {
529                 BMO_CopySlot(&op2, op, "faceout", "faceout");
530                 BMO_Finish_Op(bm, &op2);
531                 return;
532         }
533
534         BMO_Finish_Op(bm, &op2);
535         
536         /*now call dissolve faces*/
537         BMO_InitOpf(bm, &op2, "dissolvefaces faces=%ff", ELE_NEW);
538         BMO_Exec_Op(bm, &op2);
539         
540         /*if we dissolved anything, then return.*/
541         if (BMO_CountSlotBuf(bm, &op2, "regionout")) {
542                 BMO_CopySlot(&op2, op, "regionout", "faceout");
543                 BMO_Finish_Op(bm, &op2);
544                 return;
545         }
546
547         BMO_Finish_Op(bm, &op2);
548
549         /*now, count how many verts we have*/
550         amount = 0;
551         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
552                 if (BMO_TestFlag(bm, v, ELE_NEW)) {
553                         verts[amount] = v;
554                         amount++;
555
556                         if (amount > 4) break;
557                 }
558         }
559
560         if (amount == 2) {
561                 /*create edge*/
562                 e = BM_Make_Edge(bm, verts[0], verts[1], NULL, 1);
563                 BMO_SetFlag(bm, e, ELE_OUT);            
564         } else if (amount == 3) {
565                 /*create triangle*/
566                 BM_Make_QuadTri(bm, verts[0], verts[1], verts[2], NULL, NULL, 1);
567         } else if (amount == 4) {
568                 f = NULL;
569
570                 /* the order of vertices can be anything, 6 cases to check */
571                 if( convex(verts[0]->co, verts[1]->co, verts[2]->co, verts[3]->co) ) {
572                         f= BM_Make_QuadTri(bm, verts[0], verts[1], verts[2], verts[3], NULL, 1);
573                 }
574                 else if( convex(verts[0]->co, verts[2]->co, verts[3]->co, verts[1]->co) ) {
575                         f= BM_Make_QuadTri(bm, verts[0], verts[2], verts[3], verts[1], NULL, 1);
576                 }
577                 else if( convex(verts[0]->co, verts[2]->co, verts[1]->co, verts[3]->co) ) {
578                         f= BM_Make_QuadTri(bm, verts[0], verts[2], verts[1], verts[3], NULL, 1);
579                 }
580                 else if( convex(verts[0]->co, verts[1]->co, verts[3]->co, verts[2]->co) ) {
581                         f= BM_Make_QuadTri(bm, verts[0], verts[1], verts[3], verts[2], NULL, 1);
582                 }
583                 else if( convex(verts[0]->co, verts[3]->co, verts[2]->co, verts[1]->co) ) {
584                         f= BM_Make_QuadTri(bm, verts[0], verts[3], verts[2], verts[1], NULL, 1);
585                 }
586                 else if( convex(verts[0]->co, verts[3]->co, verts[1]->co, verts[2]->co) ) {
587                         f= BM_Make_QuadTri(bm, verts[0], verts[3], verts[1], verts[2], NULL, 1);
588                 }
589                 else {
590                         printf("cannot find nice quad from concave set of vertices\n");
591                 }
592
593                 if (f) BMO_SetFlag(bm, f, ELE_OUT);
594         }
595 }