fix [#36923] Merge / Delete vertices crashes for some meshes
[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 /** \file blender/bmesh/operators/bmo_join_triangles.c
24  *  \ingroup bmesh
25  *
26  * Convert triangle to quads.
27  *
28  * TODO
29  * - convert triangles to any sided faces, not just quads.
30  */
31
32 #include "MEM_guardedalloc.h"
33
34 #include "DNA_meshdata_types.h"
35
36 #include "BLI_math.h"
37 #include "BLI_sort_utils.h"
38
39 #include "BKE_customdata.h"
40
41 #include "bmesh.h"
42
43 #include "intern/bmesh_operators_private.h" /* own include */
44
45 #define FACE_OUT (1 << 0)
46
47 /* assumes edges are validated before reaching this poin */
48 static float measure_facepair(const float v1[3], const float v2[3],
49                               const float v3[3], const float v4[3], float limit)
50 {
51         /* gives a 'weight' to a pair of triangles that join an edge to decide how good a join they would make */
52         /* Note: this is more complicated than it needs to be and should be cleaned up.. */
53         float n1[3], n2[3], measure = 0.0f, angle1, angle2, diff;
54         float edgeVec1[3], edgeVec2[3], edgeVec3[3], edgeVec4[3];
55         float minarea, maxarea, areaA, areaB;
56
57         /* First Test: Normal difference */
58         normal_tri_v3(n1, v1, v2, v3);
59         normal_tri_v3(n2, v1, v3, v4);
60         angle1 = (compare_v3v3(n1, n2, FLT_EPSILON)) ? 0.0f : angle_normalized_v3v3(n1, n2);
61
62         normal_tri_v3(n1, v2, v3, v4);
63         normal_tri_v3(n2, v4, v1, v2);
64         angle2 = (compare_v3v3(n1, n2, FLT_EPSILON)) ? 0.0f : angle_normalized_v3v3(n1, n2);
65
66         measure += (angle1 + angle2) * 0.5f;
67         if (measure > limit) {
68                 return measure;
69         }
70
71         /* Second test: Colinearity */
72         sub_v3_v3v3(edgeVec1, v1, v2);
73         sub_v3_v3v3(edgeVec2, v2, v3);
74         sub_v3_v3v3(edgeVec3, v3, v4);
75         sub_v3_v3v3(edgeVec4, v4, v1);
76
77         normalize_v3(edgeVec1);
78         normalize_v3(edgeVec2);
79         normalize_v3(edgeVec3);
80         normalize_v3(edgeVec4);
81
82         /* a completely skinny face is 'pi' after halving */
83         diff = 0.25f * (fabsf(angle_normalized_v3v3(edgeVec1, edgeVec2) - (float)M_PI_2) +
84                         fabsf(angle_normalized_v3v3(edgeVec2, edgeVec3) - (float)M_PI_2) +
85                         fabsf(angle_normalized_v3v3(edgeVec3, edgeVec4) - (float)M_PI_2) +
86                         fabsf(angle_normalized_v3v3(edgeVec4, edgeVec1) - (float)M_PI_2));
87
88         if (!diff) {
89                 return 0.0;
90         }
91
92         measure +=  diff;
93         if (measure > limit) {
94                 return measure;
95         }
96
97         /* Third test: Concavity */
98         areaA = area_tri_v3(v1, v2, v3) + area_tri_v3(v1, v3, v4);
99         areaB = area_tri_v3(v2, v3, v4) + area_tri_v3(v4, v1, v2);
100
101         if (areaA <= areaB) minarea = areaA;
102         else minarea = areaB;
103
104         if (areaA >= areaB) maxarea = areaA;
105         else maxarea = areaB;
106
107         if (!maxarea) measure += 1;
108         else measure += (1 - (minarea / maxarea));
109
110         return measure;
111 }
112
113 #define T2QUV_LIMIT 0.005f
114 #define T2QCOL_LIMIT 3
115
116 static bool bm_edge_faces_cmp(BMesh *bm, BMEdge *e, const bool do_uv, const bool do_tf, const bool do_vcol)
117 {
118         /* first get loops */
119         BMLoop *l[4];
120
121         l[0] = e->l;
122         l[2] = e->l->radial_next;
123         
124         /* match up loops on each side of an edge corresponding to each vert */
125         if (l[0]->v == l[2]->v) {
126                 l[1] = l[0]->next;
127                 l[3] = l[1]->next;
128         }
129         else {
130                 l[1] = l[0]->next;
131
132                 l[3] = l[2];
133                 l[2] = l[3]->next;
134         }
135
136         /* Test UV's */
137         if (do_uv) {
138                 const MLoopUV *luv[4] = {
139                     CustomData_bmesh_get(&bm->ldata, l[0]->head.data, CD_MLOOPUV),
140                     CustomData_bmesh_get(&bm->ldata, l[1]->head.data, CD_MLOOPUV),
141                     CustomData_bmesh_get(&bm->ldata, l[2]->head.data, CD_MLOOPUV),
142                     CustomData_bmesh_get(&bm->ldata, l[3]->head.data, CD_MLOOPUV),
143                 };
144
145                 /* do UV */
146                 if (luv[0] && (!compare_v2v2(luv[0]->uv, luv[2]->uv, T2QUV_LIMIT) ||
147                                !compare_v2v2(luv[1]->uv, luv[3]->uv, T2QUV_LIMIT)))
148                 {
149                         return false;
150                 }
151         }
152
153         if (do_tf) {
154                 const MTexPoly *tp[2] = {
155                     CustomData_bmesh_get(&bm->pdata, l[0]->f->head.data, CD_MTEXPOLY),
156                     CustomData_bmesh_get(&bm->pdata, l[1]->f->head.data, CD_MTEXPOLY),
157                 };
158
159                 if (tp[0] && (tp[0]->tpage != tp[1]->tpage)) {
160                         return false;
161                 }
162         }
163
164         /* Test Vertex Colors */
165         if (do_vcol) {
166                 const MLoopCol *lcol[4] = {
167                     CustomData_bmesh_get(&bm->ldata, l[0]->head.data, CD_MLOOPCOL),
168                         CustomData_bmesh_get(&bm->ldata, l[1]->head.data, CD_MLOOPCOL),
169                         CustomData_bmesh_get(&bm->ldata, l[2]->head.data, CD_MLOOPCOL),
170                         CustomData_bmesh_get(&bm->ldata, l[3]->head.data, CD_MLOOPCOL),
171                 };
172
173                 if (lcol[0]) {
174                         if (!compare_rgb_uchar((unsigned char *)&lcol[0]->r, (unsigned char *)&lcol[2]->r, T2QCOL_LIMIT) ||
175                             !compare_rgb_uchar((unsigned char *)&lcol[1]->r, (unsigned char *)&lcol[3]->r, T2QCOL_LIMIT))
176                         {
177                                 return false;
178                         }
179                 }
180         }
181
182         return true;
183 }
184
185
186 #define EDGE_MARK       1
187 #define EDGE_CHOSEN     2
188
189 #define FACE_MARK       1
190 #define FACE_INPUT      2
191
192
193
194 void bmo_join_triangles_exec(BMesh *bm, BMOperator *op)
195 {
196         const bool do_sharp = BMO_slot_bool_get(op->slots_in, "cmp_sharp");
197         const bool do_uv    = BMO_slot_bool_get(op->slots_in, "cmp_uvs");
198         const bool do_tf    = do_uv;  /* texture face, make make its own option eventually */
199         const bool do_vcol  = BMO_slot_bool_get(op->slots_in, "cmp_vcols");
200         const bool do_mat   = BMO_slot_bool_get(op->slots_in, "cmp_materials");
201         const float limit   = BMO_slot_float_get(op->slots_in, "limit");
202
203         BMIter iter;
204         BMOIter siter;
205         BMFace *f;
206         BMEdge *e, *e_next;
207         /* data: edge-to-join, sort_value: error weight */
208         struct SortPointerByFloat *jedges;
209         unsigned i, totedge;
210         unsigned int totedge_tag = 0;
211
212         /* flag all edges of all input face */
213         BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
214                 if (f->len == 3) {
215                         BMO_elem_flag_enable(bm, f, FACE_INPUT);
216                 }
217         }
218
219         /* flag edges surrounded by 2 flagged triangles */
220         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
221                 BMFace *f_a, *f_b;
222                 if (BM_edge_face_pair(e, &f_a, &f_b) &&
223                     (BMO_elem_flag_test(bm, f_a, FACE_INPUT) && BMO_elem_flag_test(bm, f_b, FACE_INPUT)))
224                 {
225                         BMO_elem_flag_enable(bm, e, EDGE_MARK);
226                         totedge_tag++;
227                 }
228         }
229
230         if (totedge_tag == 0) {
231                 return;
232         }
233
234         /* over alloc, some of the edges will be delimited */
235         jedges = MEM_mallocN(sizeof(*jedges) * totedge_tag, __func__);
236
237         i = 0;
238         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
239                 BMVert *v1, *v2, *v3, *v4;
240                 BMFace *f_a, *f_b;
241                 float measure;
242
243                 if (!BMO_elem_flag_test(bm, e, EDGE_MARK))
244                         continue;
245
246                 f_a = e->l->f;
247                 f_b = e->l->radial_next->f;
248
249                 if (do_sharp && !BM_elem_flag_test(e, BM_ELEM_SMOOTH))
250                         continue;
251
252                 if (do_mat && f_a->mat_nr != f_b->mat_nr)
253                         continue;
254
255                 if ((do_uv || do_tf || do_vcol) && (bm_edge_faces_cmp(bm, e, do_uv, do_tf, do_vcol) == false))
256                         continue;
257
258                 v1 = e->l->v;
259                 v2 = e->l->prev->v;
260                 v3 = e->l->next->v;
261                 v4 = e->l->radial_next->prev->v;
262
263                 measure = measure_facepair(v1->co, v2->co, v3->co, v4->co, limit);
264                 if (measure < limit) {
265                         jedges[i].data = e;
266                         jedges[i].sort_value = measure;
267                         i++;
268                 }
269         }
270
271         totedge = i;
272         qsort(jedges, totedge, sizeof(*jedges), BLI_sortutil_cmp_float);
273
274         for (i = 0; i < totedge; i++) {
275                 BMFace *f_a, *f_b;
276
277                 e = jedges[i].data;
278                 f_a = e->l->f;
279                 f_b = e->l->radial_next->f;
280
281                 /* check if another edge already claimed this face */
282                 if ((BMO_elem_flag_test(bm, f_a, FACE_MARK) == false) ||
283                     (BMO_elem_flag_test(bm, f_b, FACE_MARK) == false))
284                 {
285                         BMO_elem_flag_enable(bm, f_a, FACE_MARK);
286                         BMO_elem_flag_enable(bm, f_b, FACE_MARK);
287                         BMO_elem_flag_enable(bm, e, EDGE_CHOSEN);
288                 }
289         }
290
291         MEM_freeN(jedges);
292
293         /* join best weighted */
294         BM_ITER_MESH_MUTABLE (e, e_next, &iter, bm, BM_EDGES_OF_MESH) {
295                 BMFace *f_new;
296                 BMFace *f_a, *f_b;
297
298                 if (!BMO_elem_flag_test(bm, e, EDGE_CHOSEN))
299                         continue;
300
301                 BM_edge_face_pair(e, &f_a, &f_b); /* checked above */
302                 if ((f_a->len == 3 && f_b->len == 3)) {
303                         f_new = BM_faces_join_pair(bm, f_a, f_b, e, true);
304                         if (f_new) {
305                                 BMO_elem_flag_enable(bm, f_new, FACE_OUT);
306                         }
307                 }
308         }
309
310         /* join 2-tri islands */
311         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
312                 if (BMO_elem_flag_test(bm, e, EDGE_MARK)) {
313                         BMLoop *l_a, *l_b;
314                         BMFace *f_a, *f_b;
315
316                         /* ok, this edge wasn't merged, check if it's
317                          * in a 2-tri-pair island, and if so merge */
318                         l_a = e->l;
319                         l_b = e->l->radial_next;
320
321                         f_a = l_a->f;
322                         f_b = l_b->f;
323                         
324                         /* check the other 2 edges in both tris are untagged */
325                         if ((f_a->len == 3 && f_b->len == 3) &&
326                             (BMO_elem_flag_test(bm, l_a->next->e, EDGE_MARK) == false) &&
327                             (BMO_elem_flag_test(bm, l_a->prev->e, EDGE_MARK) == false) &&
328                             (BMO_elem_flag_test(bm, l_b->next->e, EDGE_MARK) == false) &&
329                             (BMO_elem_flag_test(bm, l_b->prev->e, EDGE_MARK) == false))
330                         {
331                                 BMFace *f_new;
332                                 f_new = BM_faces_join_pair(bm, f_a, f_b, e, true);
333                                 if (f_new) {
334                                         BMO_elem_flag_enable(bm, f_new, FACE_OUT);
335                                 }
336                         }
337                 }
338         }
339
340         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT);
341 }