skip assigning vars for inline bmesh flag funcs, just cast.
[blender.git] / source / blender / bmesh / operators / join_triangles.c
1 #if 1
2 #include "MEM_guardedalloc.h"
3 #include "BKE_customdata.h" 
4 #include "DNA_listBase.h"
5 #include "DNA_customdata_types.h"
6 #include "DNA_mesh_types.h"
7 #include "DNA_meshdata_types.h"
8 #include "DNA_object_types.h"
9 #include "DNA_scene_types.h"
10 #include <string.h>
11 #include "BKE_utildefines.h"
12 #include "BKE_mesh.h"
13 #include "BKE_global.h"
14 #include "BKE_DerivedMesh.h"
15 #include "BKE_cdderivedmesh.h"
16
17 #include "BLI_editVert.h"
18 #include "mesh_intern.h"
19 #include "ED_mesh.h"
20
21 #include "BLI_math.h"
22 #include "BLI_array.h"
23 #include "BLI_blenlib.h"
24 #include "BLI_edgehash.h"
25
26 #include "BLI_heap.h"
27
28 #include "bmesh.h"
29
30 #include "bmesh_operators_private.h" /* own include */
31
32 /*
33  * JOIN_TRIANGLES.C
34  *
35  * utility bmesh operators, e.g. transform, 
36  * translate, rotate, scale, etc.
37  *
38 */
39
40 /*Bitflags for edges.*/
41 #define T2QDELETE       1
42 #define T2QCOMPLEX      2
43 #define T2QJOIN         4
44
45 /*assumes edges are validated before reaching this point*/
46 static float measure_facepair(BMesh *UNUSED(bm), BMVert *v1, BMVert *v2,
47                                                           BMVert *v3, BMVert *v4, float limit)
48 {
49         /*gives a 'weight' to a pair of triangles that join an edge to decide how good a join they would make*/
50         /*Note: this is more complicated than it needs to be and should be cleaned up...*/
51         float n1[3], n2[3], measure = 0.0f, angle1, angle2, diff;
52         float edgeVec1[3], edgeVec2[3], edgeVec3[3], edgeVec4[3];
53         float minarea, maxarea, areaA, areaB;
54
55         /*First Test: Normal difference*/
56         normal_tri_v3(n1, v1->co, v2->co, v3->co);
57         normal_tri_v3(n2, v1->co, v3->co, v4->co);
58
59         if(n1[0] == n2[0] && n1[1] == n2[1] && n1[2] == n2[2]) angle1 = 0.0f;
60         else angle1 = angle_v3v3(n1, n2);
61
62         normal_tri_v3(n1, v2->co, v3->co, v4->co);
63         normal_tri_v3(n2, v4->co, v1->co, v2->co);
64
65         if(n1[0] == n2[0] && n1[1] == n2[1] && n1[2] == n2[2]) angle2 = 0.0f;
66         else angle2 = angle_v3v3(n1, n2);
67
68         measure += angle1 + angle2;
69         if(measure > limit) return measure;
70
71         /*Second test: Colinearity*/
72         sub_v3_v3v3(edgeVec1, v1->co, v2->co);
73         sub_v3_v3v3(edgeVec2, v2->co, v3->co);
74         sub_v3_v3v3(edgeVec3, v3->co, v4->co);
75         sub_v3_v3v3(edgeVec4, v4->co, v1->co);  
76
77         diff = 0.0;
78
79         diff = (
80                 fabs(angle_v3v3(edgeVec1, edgeVec2) - M_PI/2) +
81                 fabs(angle_v3v3(edgeVec2, edgeVec3) - M_PI/2) +
82                 fabs(angle_v3v3(edgeVec3, edgeVec4) - M_PI/2) +
83                 fabs(angle_v3v3(edgeVec4, edgeVec1) - M_PI/2));
84         if(!diff) return 0.0;
85
86         measure +=  diff;
87         if(measure > limit) return measure;
88
89         /*Third test: Concavity*/
90         areaA = area_tri_v3(v1->co, v2->co, v3->co) + area_tri_v3(v1->co, v3->co, v4->co);
91         areaB = area_tri_v3(v2->co, v3->co, v4->co) + area_tri_v3(v4->co, v1->co, v2->co);
92
93         if(areaA <= areaB) minarea = areaA;
94         else minarea = areaB;
95
96         if(areaA >= areaB) maxarea = areaA;
97         else maxarea = areaB;
98
99         if(!maxarea) measure += 1;
100         else measure += (1 - (minarea / maxarea));
101
102         return measure;
103 }
104
105 #define T2QUV_LIMIT 0.005
106 #define T2QCOL_LIMIT 3
107
108 static int compareFaceAttribs(BMesh *bm, BMEdge *e, int douvs, int dovcols)
109 {
110         MTexPoly *tp1, *tp2;
111         MLoopCol *lcol1, *lcol2, *lcol3, *lcol4;
112         MLoopUV *luv1, *luv2, *luv3, *luv4;
113         BMLoop *l1, *l2, *l3, *l4;
114         int mergeok_uvs=!douvs, mergeok_vcols=!dovcols;
115         
116         l1 = e->l;
117         l3 = (BMLoop*)e->l->radial_next;
118         
119         /*match up loops on each side of an edge corrusponding to each vert*/
120         if (l1->v == l3->v) {
121                 l2 = (BMLoop*)l1->next;
122                 l4 = (BMLoop*)l2->next;
123         } else {
124                 l2 = (BMLoop*)l1->next;
125
126                 l4 = l3;
127                 l3 = (BMLoop*)l4->next;
128         }
129
130         lcol1 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPCOL);
131         lcol2 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPCOL);
132         lcol3 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPCOL);
133         lcol4 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPCOL);
134
135         luv1 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPUV);
136         luv2 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPUV);
137         luv3 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPUV);
138         luv4 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPUV);
139
140         tp1 = CustomData_bmesh_get(&bm->pdata, l1->f->head.data, CD_MTEXPOLY);
141         tp2 = CustomData_bmesh_get(&bm->pdata, l2->f->head.data, CD_MTEXPOLY);
142
143         if (!lcol1)
144                 mergeok_vcols = 1;
145
146         if (!luv1)
147                 mergeok_uvs = 1;
148
149         /*compare faceedges for each face attribute. Additional per face attributes can be added later*/
150
151         /*do VCOLs*/
152         if(lcol1 && dovcols){
153                 char *cols[4] = {(char*)lcol1, (char*)lcol2, (char*)lcol3, (char*)lcol4};
154                 int i;
155
156                 for (i=0; i<3; i++) {
157                         if (cols[0][i] + T2QCOL_LIMIT < cols[3][i] - T2QCOL_LIMIT)
158                                 break;
159                         if (cols[1][i] + T2QCOL_LIMIT < cols[4][i] - T2QCOL_LIMIT)
160                                 break;
161                 }
162
163                 if (i == 3)
164                         mergeok_vcols = 1;
165         }
166
167         /*do UVs*/
168         if (luv1 && douvs) {
169                 if(tp1->tpage != tp2->tpage); /*do nothing*/
170                 else {
171                         int i;
172
173                         for(i = 0; i < 2; i++) {
174                                 if(luv1->uv[0] + T2QUV_LIMIT > luv3->uv[0] && luv1->uv[0] - T2QUV_LIMIT < luv3->uv[0] &&
175                                         luv1->uv[1] + T2QUV_LIMIT > luv3->uv[1] && luv1->uv[1] - T2QUV_LIMIT < luv3->uv[1])
176                                 {
177                                         if(luv2->uv[0] + T2QUV_LIMIT > luv4->uv[0] && luv2->uv[0] - T2QUV_LIMIT < luv4->uv[0] &&
178                                                 luv2->uv[1] + T2QUV_LIMIT > luv4->uv[1] && luv2->uv[1] - T2QUV_LIMIT < luv4->uv[1])
179                                         {
180                                                 mergeok_uvs = 1;
181                                         }
182                                 }
183                         }
184                 }
185         }
186
187         if (douvs == mergeok_uvs && dovcols == mergeok_vcols)
188                 return 1;
189         return 0;
190 }
191
192 typedef struct JoinEdge {
193         float weight;
194         BMEdge *e;
195 } JoinEdge;
196
197 #define EDGE_MARK       1
198 #define EDGE_CHOSEN     2
199
200 #define FACE_MARK       1
201 #define FACE_INPUT      2
202
203 static int fplcmp(const void *v1, const void *v2)
204 {
205         const JoinEdge *e1= ((JoinEdge*)v1), *e2=((JoinEdge*)v2);
206
207         if( e1->weight > e2->weight) return 1;
208         else if( e1->weight < e2->weight) return -1;
209
210         return 0;
211 }
212
213 void bmesh_jointriangles_exec(BMesh *bm, BMOperator *op)
214 {
215         BMIter iter, liter;
216         BMOIter siter;
217         BMFace *f1, *f2;
218         BMLoop *l;
219         BMEdge *e;
220         BLI_array_declare(jedges);
221         JoinEdge *jedges = NULL;
222         int dosharp = BMO_Get_Int(op, "compare_sharp"), douvs=BMO_Get_Int(op, "compare_uvs");
223         int dovcols = BMO_Get_Int(op, "compare_vcols"), domat=BMO_Get_Int(op, "compare_materials");
224         float limit = BMO_Get_Float(op, "limit")/180.0f*M_PI;
225         int i, totedge;
226
227         /*flag all edges of all input faces*/
228         BMO_ITER(f1, &siter, bm, op, "faces", BM_FACE) {
229                 BMO_SetFlag(bm, f1, FACE_INPUT); 
230                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f1) {
231                         BMO_SetFlag(bm, l->e, EDGE_MARK);
232                 }
233         }
234
235         /*unflag edges that are invalid; e.g. aren't surrounded by triangles*/
236         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
237                 if (!BMO_TestFlag(bm, e, EDGE_MARK))
238                         continue;
239
240                 if (BM_Edge_FaceCount(e) < 2) {
241                         BMO_ClearFlag(bm, e, EDGE_MARK);
242                         continue;
243                 }
244
245                 f1 = e->l->f;
246                 f2 = ((BMLoop*)e->l->radial_next)->f;
247
248                 if (f1->len != 3 || f2->len != 3) {
249                         BMO_ClearFlag(bm, e, EDGE_MARK);
250                         continue;
251                 }
252
253                 if (!BMO_TestFlag(bm, f1, FACE_INPUT) || !BMO_TestFlag(bm, f2, FACE_INPUT)) {
254                         BMO_ClearFlag(bm, e, EDGE_MARK);
255                         continue;
256                 }
257         }
258         
259         i = 0;
260         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
261                 BMVert *v1, *v2, *v3, *v4;
262                 BMFace *f1, *f2;
263                 float measure;
264
265                 if (!BMO_TestFlag(bm, e, EDGE_MARK))
266                         continue;
267
268                 f1 = e->l->f;
269                 f2 = ((BMLoop*)e->l->radial_next)->f;
270
271                 v1 = e->l->v;
272                 v2 = ((BMLoop*)e->l->prev)->v;
273                 v3 = ((BMLoop*)e->l->next)->v;
274                 v4 = ((BMLoop*)((BMLoop*)e->l->radial_next)->prev)->v;
275
276                 if (dosharp && BM_TestHFlag(e, BM_SHARP))
277                         continue;
278                 
279                 if ((douvs || dovcols) && compareFaceAttribs(bm, e, douvs, dovcols))
280                         continue;
281
282                 if (domat && f1->mat_nr != f2->mat_nr)
283                         continue;
284
285                 measure = measure_facepair(bm, v1, v2, v3, v4, limit);
286                 if(measure < limit) {
287                         BLI_array_growone(jedges);
288
289                         jedges[i].e = e;
290                         jedges[i].weight = measure;
291         
292                         i++;
293                 }
294         }
295
296         if (!jedges)
297                 return;
298
299         qsort(jedges, BLI_array_count(jedges), sizeof(JoinEdge), fplcmp);
300
301         totedge = BLI_array_count(jedges);
302         for (i=0; i<totedge; i++) {
303                 BMFace *f1, *f2;
304
305                 e = jedges[i].e;
306                 f1 = e->l->f;
307                 f2 = ((BMLoop*)e->l->radial_next)->f;
308
309                 if (BMO_TestFlag(bm, f1, FACE_MARK) || BMO_TestFlag(bm, f2, FACE_MARK))
310                         continue;
311
312                 BMO_SetFlag(bm, f1, FACE_MARK);
313                 BMO_SetFlag(bm, f2, FACE_MARK);
314                 BMO_SetFlag(bm, e, EDGE_CHOSEN);
315         }
316
317         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
318                 if (!BMO_TestFlag(bm, e, EDGE_CHOSEN))
319                         continue;
320
321                 f1 = e->l->f;
322                 f2 = ((BMLoop*)e->l->radial_next)->f;
323
324                 BM_Join_TwoFaces(bm, f1, f2, e);
325         }
326
327         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
328                 if (BMO_TestFlag(bm, e, EDGE_MARK)) {
329                         /*ok, this edge wasn't merged, check if it's 
330                           in a 2-tri-pair island, and if so merge*/
331
332                         f1 = e->l->f;
333                         f2 = ((BMLoop*)e->l->radial_next)->f;
334                         
335                         if (f1->len != 3 || f2->len != 3)
336                                 continue;
337
338                         for (i=0; i<2; i++) {
339                                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, i ? f2 : f1) {
340                                         if (l->e != e && BMO_TestFlag(bm, l->e, EDGE_MARK))
341                                                 break;
342                                 }
343                                 
344                                 /*if l isn't NULL, we broke out of the loop*/
345                                 if (l)
346                                         break;
347                         }
348
349                         /*if i isn't 2, we broke out of that loop*/
350                         if (i != 2)
351                                 continue;
352                 
353                         BM_Join_TwoFaces(bm, f1, f2, e);
354                 }
355         }
356
357         BLI_array_free(jedges);
358 }
359
360 #endif