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