merge with 2.5 (not trunk, last merge message said that on accident) at r22252
[blender.git] / source / blender / bmesh / operators / createops.c
1 #include "MEM_guardedalloc.h"
2
3 #include "BKE_utildefines.h"
4
5 #include "BLI_ghash.h"
6 #include "BLI_memarena.h"
7 #include "BLI_blenlib.h"
8 #include "BLI_arithb.h"
9
10 #include "bmesh.h"
11 #include "bmesh_operators_private.h"
12
13 #define ELE_NEW         1
14 #define ELE_OUT         2
15
16 void bmesh_edgenet_fill_exec(BMesh *bm, BMOperator *op)
17 {
18         /*unimplemented, need to think on how to do this.  probably are graph
19           theory stuff that could help with this problem.*/
20 }
21
22 /* evaluate if entire quad is a proper convex quad */
23 static int convex(float *v1, float *v2, float *v3, float *v4)
24 {
25         float nor[3], nor1[3], nor2[3], vec[4][2];
26         
27         /* define projection, do both trias apart, quad is undefined! */
28         CalcNormFloat(v1, v2, v3, nor1);
29         CalcNormFloat(v1, v3, v4, nor2);
30         nor[0]= ABS(nor1[0]) + ABS(nor2[0]);
31         nor[1]= ABS(nor1[1]) + ABS(nor2[1]);
32         nor[2]= ABS(nor1[2]) + ABS(nor2[2]);
33
34         if(nor[2] >= nor[0] && nor[2] >= nor[1]) {
35                 vec[0][0]= v1[0]; vec[0][1]= v1[1];
36                 vec[1][0]= v2[0]; vec[1][1]= v2[1];
37                 vec[2][0]= v3[0]; vec[2][1]= v3[1];
38                 vec[3][0]= v4[0]; vec[3][1]= v4[1];
39         }
40         else if(nor[1] >= nor[0] && nor[1]>= nor[2]) {
41                 vec[0][0]= v1[0]; vec[0][1]= v1[2];
42                 vec[1][0]= v2[0]; vec[1][1]= v2[2];
43                 vec[2][0]= v3[0]; vec[2][1]= v3[2];
44                 vec[3][0]= v4[0]; vec[3][1]= v4[2];
45         }
46         else {
47                 vec[0][0]= v1[1]; vec[0][1]= v1[2];
48                 vec[1][0]= v2[1]; vec[1][1]= v2[2];
49                 vec[2][0]= v3[1]; vec[2][1]= v3[2];
50                 vec[3][0]= v4[1]; vec[3][1]= v4[2];
51         }
52         
53         /* linetests, the 2 diagonals have to instersect to be convex */
54         if( IsectLL2Df(vec[0], vec[2], vec[1], vec[3]) > 0 ) return 1;
55         return 0;
56 }
57
58 /*this is essentially new fkey*/
59 void bmesh_contextual_create_exec(BMesh *bm, BMOperator *op)
60 {
61         BMOperator op2;
62         BMOIter oiter;
63         BMIter iter, liter;
64         BMHeader *h;
65         BMVert *v, *verts[4];
66         BMEdge *e;
67         BMLoop *l;
68         BMFace *f;
69         int totv=0, tote=0, totf=0, amount;
70
71         /*count number of each element type we were passed*/
72         BMO_ITER(h, &oiter, bm, op, "geom", BM_VERT|BM_EDGE|BM_FACE) {
73                 switch (h->type) {
74                         case BM_VERT: totv++; break;
75                         case BM_EDGE: tote++; break;
76                         case BM_FACE: totf++; break;
77                 }
78
79                 BMO_SetFlag(bm, h, ELE_NEW);
80         }
81         
82         /*first call dissolve faces*/
83         BMO_InitOpf(bm, &op2, "dissolvefaces faces=%ff", ELE_NEW);
84         BMO_Exec_Op(bm, &op2);
85         BMO_ITER(f, &oiter, bm, &op2, "regionout", BM_FACE) {
86                 BMO_SetFlag(bm, f, ELE_OUT);
87
88                 /*unflag verts associated with dissolved faces*/
89                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
90                         BMO_ClearFlag(bm, l->v, ELE_NEW);
91                 }
92         }
93         BMO_Finish_Op(bm, &op2);
94
95         /*then call edgenet create, which may still be unimplemented, heh*/
96         BMO_InitOpf(bm, &op2, "edgenet_fill edges=%fe", ELE_NEW);
97         BMO_Exec_Op(bm, &op2);
98         BMO_ITER(f, &oiter, bm, &op2, "faceout", BM_FACE) {
99                 BMO_SetFlag(bm, f, ELE_OUT);
100
101                 /*unflag verts associated with the output faces*/
102                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
103                         BMO_ClearFlag(bm, l->v, ELE_NEW);
104                 }
105         }
106         BMO_Finish_Op(bm, &op2);
107         
108         /*now, count how many verts we have*/
109         amount = 0;
110         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
111                 if (BMO_TestFlag(bm, v, ELE_NEW)) {
112                         verts[amount] = v;
113                         amount++;
114
115                         if (amount > 4) break;
116                 }
117         }
118
119         if (amount == 2) {
120                 /*create edge*/
121                 e = BM_Make_Edge(bm, verts[0], verts[1], NULL, 1);
122                 BMO_SetFlag(bm, e, ELE_OUT);            
123         } else if (amount == 3) {
124                 /*create triangle*/
125                 BM_Make_QuadTri(bm, verts[0], verts[1], verts[2], NULL, NULL, 1);
126         } else if (amount == 4) {
127                 f = NULL;
128
129                 /* the order of vertices can be anything, 6 cases to check */
130                 if( convex(verts[0]->co, verts[1]->co, verts[2]->co, verts[3]->co) ) {
131                         f= BM_Make_QuadTri(bm, verts[0], verts[1], verts[2], verts[3], NULL, 1);
132                 }
133                 else if( convex(verts[0]->co, verts[2]->co, verts[3]->co, verts[1]->co) ) {
134                         f= BM_Make_QuadTri(bm, verts[0], verts[2], verts[3], verts[1], NULL, 1);
135                 }
136                 else if( convex(verts[0]->co, verts[2]->co, verts[1]->co, verts[3]->co) ) {
137                         f= BM_Make_QuadTri(bm, verts[0], verts[2], verts[1], verts[3], NULL, 1);
138                 }
139                 else if( convex(verts[0]->co, verts[1]->co, verts[3]->co, verts[2]->co) ) {
140                         f= BM_Make_QuadTri(bm, verts[0], verts[1], verts[3], verts[2], NULL, 1);
141                 }
142                 else if( convex(verts[0]->co, verts[3]->co, verts[2]->co, verts[1]->co) ) {
143                         f= BM_Make_QuadTri(bm, verts[0], verts[3], verts[2], verts[1], NULL, 1);
144                 }
145                 else if( convex(verts[0]->co, verts[3]->co, verts[1]->co, verts[2]->co) ) {
146                         f= BM_Make_QuadTri(bm, verts[0], verts[3], verts[1], verts[2], NULL, 1);
147                 }
148                 else {
149                         printf("cannot find nice quad from concave set of vertices\n");
150                 }
151
152                 if (f) BMO_SetFlag(bm, f, ELE_OUT);
153         }
154
155         BMO_Flag_To_Slot(bm, op, "faceout", ELE_OUT, BM_FACE);
156 }