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