own cleanup commit in bmesh branch - removed last letters from ends of some comments.
[blender-staging.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
27 #include "MEM_guardedalloc.h"
28
29 #include "DNA_meshdata_types.h"
30
31 #include "BKE_customdata.h"
32
33 #include "BLI_math.h"
34 #include "BLI_array.h"
35
36 #include "bmesh.h"
37
38 #include "intern/bmesh_operators_private.h" /* own include */
39
40 /* assumes edges are validated before reaching this poin */
41 static float measure_facepair(BMVert *v1, BMVert *v2,
42                               BMVert *v3, BMVert *v4, float limit)
43 {
44         /* gives a 'weight' to a pair of triangles that join an edge to decide how good a join they would make */
45         /* Note: this is more complicated than it needs to be and should be cleaned up.. */
46         float n1[3], n2[3], measure = 0.0f, angle1, angle2, diff;
47         float edgeVec1[3], edgeVec2[3], edgeVec3[3], edgeVec4[3];
48         float minarea, maxarea, areaA, areaB;
49
50         /* First Test: Normal difference */
51         normal_tri_v3(n1, v1->co, v2->co, v3->co);
52         normal_tri_v3(n2, v1->co, v3->co, v4->co);
53
54         if (n1[0] == n2[0] && n1[1] == n2[1] && n1[2] == n2[2]) angle1 = 0.0f;
55         else angle1 = angle_v3v3(n1, n2);
56
57         normal_tri_v3(n1, v2->co, v3->co, v4->co);
58         normal_tri_v3(n2, v4->co, v1->co, v2->co);
59
60         if (n1[0] == n2[0] && n1[1] == n2[1] && n1[2] == n2[2]) angle2 = 0.0f;
61         else angle2 = angle_v3v3(n1, n2);
62
63         measure += (angle1 + angle2) * 0.5f;
64         if (measure > limit) {
65                 return measure;
66         }
67
68         /* Second test: Colinearity */
69         sub_v3_v3v3(edgeVec1, v1->co, v2->co);
70         sub_v3_v3v3(edgeVec2, v2->co, v3->co);
71         sub_v3_v3v3(edgeVec3, v3->co, v4->co);
72         sub_v3_v3v3(edgeVec4, v4->co, v1->co);
73
74         /* a completely skinny face is 'pi' after halving */
75         diff = 0.25f * (fabsf(angle_v3v3(edgeVec1, edgeVec2) - (float)M_PI_2) +
76                         fabsf(angle_v3v3(edgeVec2, edgeVec3) - (float)M_PI_2) +
77                         fabsf(angle_v3v3(edgeVec3, edgeVec4) - (float)M_PI_2) +
78                         fabsf(angle_v3v3(edgeVec4, edgeVec1) - (float)M_PI_2));
79
80         if (!diff) {
81                 return 0.0;
82         }
83
84         measure +=  diff;
85         if (measure > limit) {
86                 return measure;
87         }
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.005f
106 #define T2QCOL_LIMIT 3
107
108 static int bm_edge_faces_cmp(BMesh *bm, BMEdge *e, const int do_uv, const int do_tf, const int do_vcol)
109 {
110         /* first get loops */
111         BMLoop *l[4];
112
113         l[0] = e->l;
114         l[2] = e->l->radial_next;
115         
116         /* match up loops on each side of an edge corresponding to each vert */
117         if (l[0]->v == l[2]->v) {
118                 l[1] = l[0]->next;
119                 l[3] = l[1]->next;
120         }
121         else {
122                 l[1] = l[0]->next;
123
124                 l[3] = l[2];
125                 l[2] = l[3]->next;
126         }
127
128         /* Test UV's */
129         if (do_uv) {
130                 const MLoopUV *luv[4] = {
131                     CustomData_bmesh_get(&bm->ldata, l[0]->head.data, CD_MLOOPUV),
132                     CustomData_bmesh_get(&bm->ldata, l[1]->head.data, CD_MLOOPUV),
133                     CustomData_bmesh_get(&bm->ldata, l[2]->head.data, CD_MLOOPUV),
134                     CustomData_bmesh_get(&bm->ldata, l[3]->head.data, CD_MLOOPUV),
135                 };
136
137                 /* do UV */
138                 if (luv[0] && (!compare_v2v2(luv[0]->uv, luv[2]->uv, T2QUV_LIMIT) ||
139                                !compare_v2v2(luv[1]->uv, luv[3]->uv, T2QUV_LIMIT)))
140                 {
141                         return FALSE;
142                 }
143         }
144
145         if (do_tf) {
146                 const MTexPoly *tp[2] = {
147                     CustomData_bmesh_get(&bm->pdata, l[0]->f->head.data, CD_MTEXPOLY),
148                     CustomData_bmesh_get(&bm->pdata, l[1]->f->head.data, CD_MTEXPOLY),
149                 };
150
151                 if (tp[0] && (tp[0]->tpage != tp[1]->tpage)) {
152                         return FALSE;
153                 }
154         }
155
156         /* Test Vertex Colors */
157         if (do_vcol) {
158                 const MLoopCol *lcol[4] = {
159                     CustomData_bmesh_get(&bm->ldata, l[0]->head.data, CD_MLOOPCOL),
160                         CustomData_bmesh_get(&bm->ldata, l[1]->head.data, CD_MLOOPCOL),
161                         CustomData_bmesh_get(&bm->ldata, l[2]->head.data, CD_MLOOPCOL),
162                         CustomData_bmesh_get(&bm->ldata, l[3]->head.data, CD_MLOOPCOL),
163                 };
164
165                 if (lcol[0]) {
166                         if (!compare_rgb_uchar((unsigned char *)&lcol[0]->r, (unsigned char *)&lcol[2]->r, T2QCOL_LIMIT) ||
167                             !compare_rgb_uchar((unsigned char *)&lcol[1]->r, (unsigned char *)&lcol[3]->r, T2QCOL_LIMIT))
168                         {
169                                 return FALSE;
170                         }
171                 }
172         }
173
174         return TRUE;
175 }
176
177 typedef struct JoinEdge {
178         float weight;
179         BMEdge *e;
180 } JoinEdge;
181
182 #define EDGE_MARK       1
183 #define EDGE_CHOSEN     2
184
185 #define FACE_MARK       1
186 #define FACE_INPUT      2
187
188 static int fplcmp(const void *v1, const void *v2)
189 {
190         const JoinEdge *e1 = (JoinEdge *)v1, *e2 = (JoinEdge *)v2;
191
192         if (e1->weight > e2->weight) return 1;
193         else if (e1->weight < e2->weight) return -1;
194
195         return 0;
196 }
197
198 void bmo_join_triangles_exec(BMesh *bm, BMOperator *op)
199 {
200         BMIter iter, liter;
201         BMOIter siter;
202         BMFace *f;
203         BMLoop *l;
204         BMEdge *e;
205         BLI_array_declare(jedges);
206         JoinEdge *jedges = NULL;
207         int do_sharp = BMO_slot_bool_get(op->slots_in, "cmp_sharp");
208         int do_uv    = BMO_slot_bool_get(op->slots_in, "cmp_uvs");
209         int do_tf    = do_uv;  /* texture face, make make its own option eventually */
210         int do_vcol  = BMO_slot_bool_get(op->slots_in, "cmp_vcols");
211         int do_mat   = BMO_slot_bool_get(op->slots_in, "cmp_materials");
212         float limit  = BMO_slot_float_get(op->slots_in, "limit");
213         int i, totedge;
214
215         /* flag all edges of all input face */
216         BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
217                 BMO_elem_flag_enable(bm, f, FACE_INPUT);
218                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
219                         BMO_elem_flag_enable(bm, l->e, EDGE_MARK);
220                 }
221         }
222
223         /* unflag edges that are invalid; e.g. aren't surrounded by triangle */
224         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
225                 BMFace *f1, *f2;
226                 if (!BMO_elem_flag_test(bm, e, EDGE_MARK))
227                         continue;
228
229                 if (!BM_edge_face_pair(e, &f1, &f2)) {
230                         BMO_elem_flag_disable(bm, e, EDGE_MARK);
231                         continue;
232                 }
233
234                 if (f1->len != 3 || f2->len != 3) {
235                         BMO_elem_flag_disable(bm, e, EDGE_MARK);
236                         continue;
237                 }
238
239                 if (!BMO_elem_flag_test(bm, f1, FACE_INPUT) || !BMO_elem_flag_test(bm, f2, FACE_INPUT)) {
240                         BMO_elem_flag_disable(bm, e, EDGE_MARK);
241                         continue;
242                 }
243         }
244         
245         i = 0;
246         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
247                 BMVert *v1, *v2, *v3, *v4;
248                 BMFace *f1, *f2;
249                 float measure;
250
251                 if (!BMO_elem_flag_test(bm, e, EDGE_MARK))
252                         continue;
253
254                 f1 = e->l->f;
255                 f2 = e->l->radial_next->f;
256
257                 v1 = e->l->v;
258                 v2 = e->l->prev->v;
259                 v3 = e->l->next->v;
260                 v4 = e->l->radial_next->prev->v;
261
262                 if (do_sharp && !BM_elem_flag_test(e, BM_ELEM_SMOOTH))
263                         continue;
264
265                 if (do_mat && f1->mat_nr != f2->mat_nr)
266                         continue;
267
268                 if ((do_uv || do_tf || do_vcol) && (bm_edge_faces_cmp(bm, e, do_uv, do_tf, do_vcol) == FALSE))
269                         continue;
270
271                 measure = measure_facepair(v1, v2, v3, v4, limit);
272                 if (measure < limit) {
273                         BLI_array_grow_one(jedges);
274
275                         jedges[i].e = e;
276                         jedges[i].weight = measure;
277
278                         i++;
279                 }
280         }
281
282         if (!jedges)
283                 return;
284
285         qsort(jedges, BLI_array_count(jedges), sizeof(JoinEdge), fplcmp);
286
287         totedge = BLI_array_count(jedges);
288         for (i = 0; i < totedge; i++) {
289                 BMFace *f1, *f2;
290
291                 e = jedges[i].e;
292                 f1 = e->l->f;
293                 f2 = e->l->radial_next->f;
294
295                 if (BMO_elem_flag_test(bm, f1, FACE_MARK) || BMO_elem_flag_test(bm, f2, FACE_MARK))
296                         continue;
297
298                 BMO_elem_flag_enable(bm, f1, FACE_MARK);
299                 BMO_elem_flag_enable(bm, f2, FACE_MARK);
300                 BMO_elem_flag_enable(bm, e, EDGE_CHOSEN);
301         }
302
303         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
304                 BMFace *f1, *f2;
305
306                 if (!BMO_elem_flag_test(bm, e, EDGE_CHOSEN))
307                         continue;
308
309
310                 BM_edge_face_pair(e, &f1, &f2); /* checked above */
311                 BM_faces_join_pair(bm, f1, f2, e, TRUE);
312         }
313
314         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
315                 if (BMO_elem_flag_test(bm, e, EDGE_MARK)) {
316                         BMFace *f1, *f2;
317
318                         /* ok, this edge wasn't merged, check if it's
319                          * in a 2-tri-pair island, and if so merg */
320
321                         f1 = e->l->f;
322                         f2 = e->l->radial_next->f;
323                         
324                         if (f1->len != 3 || f2->len != 3)
325                                 continue;
326
327                         for (i = 0; i < 2; i++) {
328                                 BM_ITER_ELEM (l, &liter, i ? f2 : f1, BM_LOOPS_OF_FACE) {
329                                         if (l->e != e && BMO_elem_flag_test(bm, l->e, EDGE_MARK)) {
330                                                 break;
331                                         }
332                                 }
333                                 
334                                 /* if l isn't NULL, we broke out of the loop */
335                                 if (l) {
336                                         break;
337                                 }
338                         }
339
340                         /* if i isn't 2, we broke out of that loop */
341                         if (i != 2) {
342                                 continue;
343                         }
344
345                         BM_faces_join_pair(bm, f1, f2, e, TRUE);
346                 }
347         }
348
349         BLI_array_free(jedges);
350 }