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