← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to source/blender/bmesh/operators/bmo_join_triangles.c

  • Committer: Package Import Robot
  • Author(s): Matteo F. Vescovi
  • Date: 2012-07-23 08:54:18 UTC
  • mfrom: (14.2.16 sid)
  • mto: (14.2.19 sid)
  • mto: This revision was merged to the branch mainline in revision 42.
  • Revision ID: package-import@ubuntu.com-20120723085418-9foz30v6afaf5ffs
Tags: 2.63a-2
http://bugs.debian.org/658075
* debian/: Cycles support added (Closes: #658075)
  For now, this top feature has been enabled only
  on [any-amd64 any-i386] architectures because
  of OpenImageIO failing on all others
* debian/: scripts installation path changed
  from /usr/lib to /usr/share:
  + debian/patches/: patchset re-worked for path changing
  + debian/control: "Breaks" field added on yafaray-exporter

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
/* Bitflags for edges */
 
41
#define T2QDELETE       1
 
42
#define T2QCOMPLEX      2
 
43
#define T2QJOIN         4
 
44
 
 
45
/* assumes edges are validated before reaching this poin */
 
46
static float measure_facepair(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) * 0.5f;
 
69
        if (measure > limit) {
 
70
                return measure;
 
71
        }
 
72
 
 
73
        /* Second test: Colinearity */
 
74
        sub_v3_v3v3(edgeVec1, v1->co, v2->co);
 
75
        sub_v3_v3v3(edgeVec2, v2->co, v3->co);
 
76
        sub_v3_v3v3(edgeVec3, v3->co, v4->co);
 
77
        sub_v3_v3v3(edgeVec4, v4->co, v1->co);
 
78
 
 
79
        /* a completely skinny face is 'pi' after halving */
 
80
        diff = 0.25f * (fabsf(angle_v3v3(edgeVec1, edgeVec2) - (float)M_PI_2) +
 
81
                        fabsf(angle_v3v3(edgeVec2, edgeVec3) - (float)M_PI_2) +
 
82
                        fabsf(angle_v3v3(edgeVec3, edgeVec4) - (float)M_PI_2) +
 
83
                        fabsf(angle_v3v3(edgeVec4, edgeVec1) - (float)M_PI_2));
 
84
 
 
85
        if (!diff) {
 
86
                return 0.0;
 
87
        }
 
88
 
 
89
        measure +=  diff;
 
90
        if (measure > limit) {
 
91
                return measure;
 
92
        }
 
93
 
 
94
        /* Third test: Concavity */
 
95
        areaA = area_tri_v3(v1->co, v2->co, v3->co) + area_tri_v3(v1->co, v3->co, v4->co);
 
96
        areaB = area_tri_v3(v2->co, v3->co, v4->co) + area_tri_v3(v4->co, v1->co, v2->co);
 
97
 
 
98
        if (areaA <= areaB) minarea = areaA;
 
99
        else minarea = areaB;
 
100
 
 
101
        if (areaA >= areaB) maxarea = areaA;
 
102
        else maxarea = areaB;
 
103
 
 
104
        if (!maxarea) measure += 1;
 
105
        else measure += (1 - (minarea / maxarea));
 
106
 
 
107
        return measure;
 
108
}
 
109
 
 
110
#define T2QUV_LIMIT 0.005f
 
111
#define T2QCOL_LIMIT 3
 
112
 
 
113
static int compareFaceAttribs(BMesh *bm, BMEdge *e, int douvs, int dovcols)
 
114
{
 
115
        MTexPoly *tp1, *tp2;
 
116
        MLoopCol *lcol1, *lcol2, *lcol3, *lcol4;
 
117
        MLoopUV *luv1, *luv2, *luv3, *luv4;
 
118
        BMLoop *l1, *l2, *l3, *l4;
 
119
        int mergeok_uvs = !douvs, mergeok_vcols = !dovcols;
 
120
        
 
121
        l1 = e->l;
 
122
        l3 = e->l->radial_next;
 
123
        
 
124
        /* match up loops on each side of an edge corresponding to each ver */
 
125
        if (l1->v == l3->v) {
 
126
                l2 = l1->next;
 
127
                l4 = l2->next;
 
128
        }
 
129
        else {
 
130
                l2 = l1->next;
 
131
 
 
132
                l4 = l3;
 
133
                l3 = l4->next;
 
134
        }
 
135
 
 
136
        lcol1 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPCOL);
 
137
        lcol2 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPCOL);
 
138
        lcol3 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPCOL);
 
139
        lcol4 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPCOL);
 
140
 
 
141
        luv1 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPUV);
 
142
        luv2 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPUV);
 
143
        luv3 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPUV);
 
144
        luv4 = CustomData_bmesh_get(&bm->ldata, l1->head.data, CD_MLOOPUV);
 
145
 
 
146
        tp1 = CustomData_bmesh_get(&bm->pdata, l1->f->head.data, CD_MTEXPOLY);
 
147
        tp2 = CustomData_bmesh_get(&bm->pdata, l2->f->head.data, CD_MTEXPOLY);
 
148
 
 
149
        if (!lcol1)
 
150
                mergeok_vcols = 1;
 
151
 
 
152
        if (!luv1)
 
153
                mergeok_uvs = 1;
 
154
 
 
155
        /* compare faceedges for each face attribute. Additional per face attributes can be added late */
 
156
 
 
157
        /* do VCOL */
 
158
        if (lcol1 && dovcols) {
 
159
                char *cols[4] = {(char *)lcol1, (char *)lcol2, (char *)lcol3, (char *)lcol4};
 
160
                int i;
 
161
 
 
162
                for (i = 0; i < 3; i++) {
 
163
                        if (cols[0][i] + T2QCOL_LIMIT < cols[2][i] - T2QCOL_LIMIT)
 
164
                                break;
 
165
                        if (cols[1][i] + T2QCOL_LIMIT < cols[3][i] - T2QCOL_LIMIT)
 
166
                                break;
 
167
                }
 
168
 
 
169
                if (i == 3)
 
170
                        mergeok_vcols = 1;
 
171
        }
 
172
 
 
173
        /* do UV */
 
174
        if (luv1 && douvs) {
 
175
                if (tp1->tpage != tp2->tpage) {
 
176
                        /* do nothing */
 
177
                }
 
178
                else {
 
179
                        int i;
 
180
 
 
181
                        for (i = 0; i < 2; i++) {
 
182
                                if (luv1->uv[0] + T2QUV_LIMIT > luv3->uv[0] && luv1->uv[0] - T2QUV_LIMIT < luv3->uv[0] &&
 
183
                                    luv1->uv[1] + T2QUV_LIMIT > luv3->uv[1] && luv1->uv[1] - T2QUV_LIMIT < luv3->uv[1])
 
184
                                {
 
185
                                        if (luv2->uv[0] + T2QUV_LIMIT > luv4->uv[0] && luv2->uv[0] - T2QUV_LIMIT < luv4->uv[0] &&
 
186
                                            luv2->uv[1] + T2QUV_LIMIT > luv4->uv[1] && luv2->uv[1] - T2QUV_LIMIT < luv4->uv[1])
 
187
                                        {
 
188
                                                mergeok_uvs = 1;
 
189
                                        }
 
190
                                }
 
191
                        }
 
192
                }
 
193
        }
 
194
 
 
195
        if (douvs == mergeok_uvs && dovcols == mergeok_vcols) {
 
196
                return TRUE;
 
197
        }
 
198
 
 
199
        return FALSE;
 
200
}
 
201
 
 
202
typedef struct JoinEdge {
 
203
        float weight;
 
204
        BMEdge *e;
 
205
} JoinEdge;
 
206
 
 
207
#define EDGE_MARK       1
 
208
#define EDGE_CHOSEN     2
 
209
 
 
210
#define FACE_MARK       1
 
211
#define FACE_INPUT      2
 
212
 
 
213
static int fplcmp(const void *v1, const void *v2)
 
214
{
 
215
        const JoinEdge *e1 = (JoinEdge *)v1, *e2 = (JoinEdge *)v2;
 
216
 
 
217
        if (e1->weight > e2->weight) return 1;
 
218
        else if (e1->weight < e2->weight) return -1;
 
219
 
 
220
        return 0;
 
221
}
 
222
 
 
223
void bmo_join_triangles_exec(BMesh *bm, BMOperator *op)
 
224
{
 
225
        BMIter iter, liter;
 
226
        BMOIter siter;
 
227
        BMFace *f1, *f2;
 
228
        BMLoop *l;
 
229
        BMEdge *e;
 
230
        BLI_array_declare(jedges);
 
231
        JoinEdge *jedges = NULL;
 
232
        int dosharp = BMO_slot_bool_get(op, "cmp_sharp");
 
233
        int douvs =   BMO_slot_bool_get(op, "cmp_uvs");
 
234
        int dovcols = BMO_slot_bool_get(op, "cmp_vcols");
 
235
        int domat =   BMO_slot_bool_get(op, "cmp_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_ELEM (l, &liter, f1, BM_LOOPS_OF_FACE) {
 
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_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
 
249
                if (!BMO_elem_flag_test(bm, e, EDGE_MARK))
 
250
                        continue;
 
251
 
 
252
                if (!BM_edge_face_pair(e, &f1, &f2)) {
 
253
                        BMO_elem_flag_disable(bm, e, EDGE_MARK);
 
254
                        continue;
 
255
                }
 
256
 
 
257
                if (f1->len != 3 || f2->len != 3) {
 
258
                        BMO_elem_flag_disable(bm, e, EDGE_MARK);
 
259
                        continue;
 
260
                }
 
261
 
 
262
                if (!BMO_elem_flag_test(bm, f1, FACE_INPUT) || !BMO_elem_flag_test(bm, f2, FACE_INPUT)) {
 
263
                        BMO_elem_flag_disable(bm, e, EDGE_MARK);
 
264
                        continue;
 
265
                }
 
266
        }
 
267
        
 
268
        i = 0;
 
269
        BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
 
270
                BMVert *v1, *v2, *v3, *v4;
 
271
                BMFace *f1, *f2;
 
272
                float measure;
 
273
 
 
274
                if (!BMO_elem_flag_test(bm, e, EDGE_MARK))
 
275
                        continue;
 
276
 
 
277
                f1 = e->l->f;
 
278
                f2 = e->l->radial_next->f;
 
279
 
 
280
                v1 = e->l->v;
 
281
                v2 = e->l->prev->v;
 
282
                v3 = e->l->next->v;
 
283
                v4 = e->l->radial_next->prev->v;
 
284
 
 
285
                if (dosharp && !BM_elem_flag_test(e, BM_ELEM_SMOOTH))
 
286
                        continue;
 
287
                
 
288
                if ((douvs || dovcols) && compareFaceAttribs(bm, e, douvs, dovcols))
 
289
                        continue;
 
290
 
 
291
                if (domat && f1->mat_nr != f2->mat_nr)
 
292
                        continue;
 
293
 
 
294
                measure = measure_facepair(v1, v2, v3, v4, limit);
 
295
                if (measure < limit) {
 
296
                        BLI_array_growone(jedges);
 
297
 
 
298
                        jedges[i].e = e;
 
299
                        jedges[i].weight = measure;
 
300
 
 
301
                        i++;
 
302
                }
 
303
        }
 
304
 
 
305
        if (!jedges)
 
306
                return;
 
307
 
 
308
        qsort(jedges, BLI_array_count(jedges), sizeof(JoinEdge), fplcmp);
 
309
 
 
310
        totedge = BLI_array_count(jedges);
 
311
        for (i = 0; i < totedge; i++) {
 
312
                BMFace *f1, *f2;
 
313
 
 
314
                e = jedges[i].e;
 
315
                f1 = e->l->f;
 
316
                f2 = e->l->radial_next->f;
 
317
 
 
318
                if (BMO_elem_flag_test(bm, f1, FACE_MARK) || BMO_elem_flag_test(bm, f2, FACE_MARK))
 
319
                        continue;
 
320
 
 
321
                BMO_elem_flag_enable(bm, f1, FACE_MARK);
 
322
                BMO_elem_flag_enable(bm, f2, FACE_MARK);
 
323
                BMO_elem_flag_enable(bm, e, EDGE_CHOSEN);
 
324
        }
 
325
 
 
326
        BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
 
327
                if (!BMO_elem_flag_test(bm, e, EDGE_CHOSEN))
 
328
                        continue;
 
329
 
 
330
 
 
331
                BM_edge_face_pair(e, &f1, &f2); /* checked above */
 
332
                BM_faces_join_pair(bm, f1, f2, e, TRUE);
 
333
        }
 
334
 
 
335
        BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
 
336
                if (BMO_elem_flag_test(bm, e, EDGE_MARK)) {
 
337
                        /* ok, this edge wasn't merged, check if it's
 
338
                         * in a 2-tri-pair island, and if so merg */
 
339
 
 
340
                        f1 = e->l->f;
 
341
                        f2 = e->l->radial_next->f;
 
342
                        
 
343
                        if (f1->len != 3 || f2->len != 3)
 
344
                                continue;
 
345
 
 
346
                        for (i = 0; i < 2; i++) {
 
347
                                BM_ITER_ELEM (l, &liter, i ? f2 : f1, BM_LOOPS_OF_FACE) {
 
348
                                        if (l->e != e && BMO_elem_flag_test(bm, l->e, EDGE_MARK)) {
 
349
                                                break;
 
350
                                        }
 
351
                                }
 
352
                                
 
353
                                /* if l isn't NULL, we broke out of the loo */
 
354
                                if (l) {
 
355
                                        break;
 
356
                                }
 
357
                        }
 
358
 
 
359
                        /* if i isn't 2, we broke out of that loo */
 
360
                        if (i != 2) {
 
361
                                continue;
 
362
                        }
 
363
 
 
364
                        BM_faces_join_pair(bm, f1, f2, e, TRUE);
 
365
                }
 
366
        }
 
367
 
 
368
        BLI_array_free(jedges);
 
369
}