36c8fa402111bafd8e73ebdc2ec851bade27cf33
[blender.git] / source / blender / bmesh / operators / triangulateop.c
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 #include "MEM_guardedalloc.h"
6
7 #include "BKE_utildefines.h"
8
9 #include "BLI_scanfill.h"
10 #include "BLI_math.h"
11 #include "BLI_array.h"
12 #include "BLI_editVert.h"
13 #include "BLI_smallhash.h"
14
15 #include "bmesh.h"
16 #include "bmesh_private.h"
17
18 #define EDGE_NEW        1
19 #define FACE_NEW        1
20
21 #define ELE_NEW         1
22 #define FACE_MARK       2
23 #define EDGE_MARK       4
24
25 void triangulate_exec(BMesh *bm, BMOperator *op)
26 {
27         BMOIter siter;
28         BMFace *face, **newfaces = NULL;
29         BLI_array_declare(newfaces);
30         float (*projectverts)[3] = NULL;
31         BLI_array_declare(projectverts);
32         int i, lastlen=0 /* , count = 0 */;
33         
34         face = BMO_IterNew(&siter, bm, op, "faces", BM_FACE);
35         for (; face; face=BMO_IterStep(&siter)) {
36                 if (lastlen < face->len) {
37                         BLI_array_empty(projectverts);
38                         BLI_array_empty(newfaces);
39                         for (lastlen=0; lastlen<face->len; lastlen++) {
40                                 BLI_array_growone(projectverts);
41                                 BLI_array_growone(projectverts);
42                                 BLI_array_growone(projectverts);
43                                 BLI_array_growone(newfaces);
44                         }
45                 }
46                 
47                 BM_Triangulate_Face(bm, face, projectverts, EDGE_NEW, 
48                                     FACE_NEW, newfaces);
49
50                 BMO_Insert_MapPointer(bm, op, "facemap", 
51                                       face, face);
52                 for (i=0; newfaces[i]; i++) {
53                         BMO_Insert_MapPointer(bm, op, "facemap", 
54                                               newfaces[i], face);
55
56                 }
57         }
58         
59         BMO_Flag_To_Slot(bm, op, "edgeout", EDGE_NEW, BM_EDGE);
60         BMO_Flag_To_Slot(bm, op, "faceout", FACE_NEW, BM_FACE);
61         
62         BLI_array_free(projectverts);
63         BLI_array_free(newfaces);
64 }
65
66 void bmesh_beautify_fill_exec(BMesh *bm, BMOperator *op)
67 {
68         BMOIter siter;
69         BMIter iter;
70         BMFace *f;
71         BMEdge *e;
72         int stop=0;
73         
74         BMO_Flag_Buffer(bm, op, "constrain_edges", EDGE_MARK, BM_EDGE);
75         
76         BMO_ITER(f, &siter, bm, op, "faces", BM_FACE) {
77                 if (f->len == 3)
78                         BMO_SetFlag(bm, f, FACE_MARK);
79         }
80
81         while (!stop) {
82                 stop = 1;
83                 
84                 BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
85                         BMVert *v1, *v2, *v3, *v4, *d1, *d2;
86                         float len1, len2, len3, len4, len5, len6, opp1, opp2, fac1, fac2;
87                         int ok;
88                         
89                         if (BM_Edge_FaceCount(e) != 2 || BMO_TestFlag(bm, e, EDGE_MARK))
90                                 continue;
91                         if (!BMO_TestFlag(bm, e->l->f, FACE_MARK) || !BMO_TestFlag(bm, e->l->radial_next->f, FACE_MARK))
92                                 continue;
93                         
94                         v1 = e->l->prev->v;
95                         v2 = e->l->v;
96                         v3 = e->l->radial_next->prev->v;
97                         v4 = e->l->next->v;
98                         
99                         if (is_quad_convex_v3(v1->co, v2->co, v3->co, v4->co)) {
100                                 /* testing rule:
101                                 * the area divided by the total edge lengths
102                                 */
103                                 len1= len_v3v3(v1->co, v2->co);
104                                 len2= len_v3v3(v2->co, v3->co);
105                                 len3= len_v3v3(v3->co, v4->co);
106                                 len4= len_v3v3(v4->co, v1->co);
107                                 len5= len_v3v3(v1->co, v3->co);
108                                 len6= len_v3v3(v2->co, v4->co);
109         
110                                 opp1= area_tri_v3(v1->co, v2->co, v3->co);
111                                 opp2= area_tri_v3(v1->co, v3->co, v4->co);
112         
113                                 fac1= opp1/(len1+len2+len5) + opp2/(len3+len4+len5);
114         
115                                 opp1= area_tri_v3(v2->co, v3->co, v4->co);
116                                 opp2= area_tri_v3(v2->co, v4->co, v1->co);
117         
118                                 fac2= opp1/(len2+len3+len6) + opp2/(len4+len1+len6);
119                                 ok = 0;
120                                 
121                                 if (fac1 > fac2) {
122                                         e = BM_Rotate_Edge(bm, e, 0);
123                                         BMO_SetFlag(bm, e, ELE_NEW);
124                                         
125                                         BMO_SetFlag(bm, e->l->f, FACE_MARK|ELE_NEW);
126                                         BMO_SetFlag(bm, e->l->radial_next->f, FACE_MARK|ELE_NEW);
127                                         stop = 0;
128                                 }
129                         }
130                 }
131         }
132         
133         BMO_Flag_To_Slot(bm, op, "geomout", ELE_NEW, BM_EDGE|BM_FACE);
134 }
135
136 void bmesh_triangle_fill_exec(BMesh *bm, BMOperator *op)
137 {
138         BMOIter siter;
139         BMEdge *e;
140         BMOperator bmop;
141         EditEdge *eed;
142         EditVert *eve, *v1, *v2;
143         EditFace *efa;
144         SmallHash hash;
145
146         BLI_smallhash_init(&hash);
147         
148         BLI_begin_edgefill();
149         
150         BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
151                 BMO_SetFlag(bm, e, EDGE_MARK);
152                 
153                 if (!BLI_smallhash_haskey(&hash, (uintptr_t)e->v1)) {
154                         eve = BLI_addfillvert(e->v1->co);
155                         eve->tmp.p = e->v1;
156                         BLI_smallhash_insert(&hash, (uintptr_t)e->v1, eve);
157                 }
158                 
159                 if (!BLI_smallhash_haskey(&hash, (uintptr_t)e->v2)) {
160                         eve = BLI_addfillvert(e->v2->co);
161                         eve->tmp.p = e->v2;
162                         BLI_smallhash_insert(&hash, (uintptr_t)e->v2, eve);
163                 }
164                 
165                 v1 = BLI_smallhash_lookup(&hash, (uintptr_t)e->v1);
166                 v2 = BLI_smallhash_lookup(&hash, (uintptr_t)e->v2);
167                 eed = BLI_addfilledge(v1, v2);
168                 eed->tmp.p = e;
169         }
170         
171         BLI_edgefill(0);
172         
173         for (efa=fillfacebase.first; efa; efa=efa->next) {
174                 BMFace *f = BM_Make_QuadTri(bm, efa->v1->tmp.p, efa->v2->tmp.p, efa->v3->tmp.p, NULL, NULL, 1);
175                 BMLoop *l;
176                 BMIter liter;
177                 
178                 BMO_SetFlag(bm, f, ELE_NEW);
179                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
180                         if (!BMO_TestFlag(bm, l->e, EDGE_MARK)) {
181                                 BMO_SetFlag(bm, l->e, ELE_NEW);
182                         }
183                 }
184         }
185         
186         BLI_end_edgefill();
187         BLI_smallhash_release(&hash);
188         
189         /*clean up fill*/
190         BMO_InitOpf(bm, &bmop, "beautify_fill faces=%ff constrain_edges=%fe", ELE_NEW, EDGE_MARK);
191         BMO_Exec_Op(bm, &bmop);
192         BMO_Flag_Buffer(bm, &bmop, "geomout", ELE_NEW, BM_FACE|BM_EDGE);
193         BMO_Finish_Op(bm, &bmop);
194         
195         BMO_Flag_To_Slot(bm, op, "geomout", ELE_NEW, BM_EDGE|BM_FACE);
196 }