← Back to branch summary

~ubuntu-branches/ubuntu/trusty/blender/trusty

« back to all changes in this revision

Viewing changes to source/blender/bmesh/tools/bmesh_decimate_dissolve.c

  • Committer: Package Import Robot
  • Author(s): Jeremy Bicha
  • Date: 2013-03-06 12:08:47 UTC
  • mfrom: (1.5.1) (14.1.8 experimental)
  • Revision ID: package-import@ubuntu.com-20130306120847-frjfaryb2zrotwcg
Tags: 2.66a-1ubuntu1
https://launchpad.net/bugs/1076930
https://launchpad.net/bugs/1089256
https://launchpad.net/bugs/1052743
https://launchpad.net/bugs/999024
* Resynchronize with Debian (LP: #1076930, #1089256, #1052743, #999024,
  #1122888, #1147084)
* debian/control:
  - Lower build-depends on libavcodec-dev since we're not
    doing the libav9 transition in Ubuntu yet

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/blender/bmesh/tools/bmesh_decimate_dissolve.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): Campbell Barton
 
19
 *
 
20
 * ***** END GPL LICENSE BLOCK *****
 
21
 */
 
22
 
 
23
/** \file blender/bmesh/tools/bmesh_decimate_dissolve.c
 
24
 *  \ingroup bmesh
 
25
 *
 
26
 * BMesh decimator that dissolves flat areas into polygons (ngons).
 
27
 */
 
28
 
 
29
 
 
30
#include "MEM_guardedalloc.h"
 
31
 
 
32
#include "BLI_math.h"
 
33
 
 
34
#include "bmesh.h"
 
35
#include "bmesh_decimate.h"  /* own include */
 
36
 
 
37
#define UNIT_TO_ANGLE DEG2RADF(90.0f)
 
38
#define ANGLE_TO_UNIT (1.0f / UNIT_TO_ANGLE)
 
39
 
 
40
/* multiply vertex edge angle by face angle
 
41
 * this means we are not left with sharp corners between _almost_ planer faces
 
42
 * convert angles [0-PI/2] -> [0-1], multiply together, then convert back to radians. */
 
43
static float bm_vert_edge_face_angle(BMVert *v)
 
44
{
 
45
        const float angle = BM_vert_calc_edge_angle(v);
 
46
        /* note: could be either edge, it doesn't matter */
 
47
        if (v->e && BM_edge_is_manifold(v->e)) {
 
48
                return ((angle * ANGLE_TO_UNIT) * (BM_edge_calc_face_angle(v->e) * ANGLE_TO_UNIT)) * UNIT_TO_ANGLE;
 
49
        }
 
50
        else {
 
51
                return angle;
 
52
        }
 
53
}
 
54
 
 
55
#undef UNIT_TO_ANGLE
 
56
#undef ANGLE_TO_UNIT
 
57
 
 
58
typedef struct DissolveElemWeight {
 
59
        BMHeader *ele;
 
60
        float weight;
 
61
} DissolveElemWeight;
 
62
 
 
63
static int dissolve_elem_cmp(const void *a1, const void *a2)
 
64
{
 
65
        const struct DissolveElemWeight *d1 = a1, *d2 = a2;
 
66
 
 
67
        if      (d1->weight > d2->weight) return  1;
 
68
        else if (d1->weight < d2->weight) return -1;
 
69
        return 0;
 
70
}
 
71
 
 
72
void BM_mesh_decimate_dissolve_ex(BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries,
 
73
                                  BMVert **vinput_arr, const int vinput_len,
 
74
                                  BMEdge **einput_arr, const int einput_len)
 
75
{
 
76
        const float angle_max = (float)M_PI / 2.0f;
 
77
        DissolveElemWeight *weight_elems = MEM_mallocN(max_ii(einput_len, vinput_len) *
 
78
                                                       sizeof(DissolveElemWeight), __func__);
 
79
        int i, tot_found;
 
80
 
 
81
        BMIter iter;
 
82
        BMEdge *e_iter;
 
83
        BMEdge **earray;
 
84
 
 
85
        int *vert_reverse_lookup;
 
86
 
 
87
        /* --- first edges --- */
 
88
 
 
89
        /* wire -> tag */
 
90
        BM_ITER_MESH (e_iter, &iter, bm, BM_EDGES_OF_MESH) {
 
91
                BM_elem_flag_set(e_iter, BM_ELEM_TAG, BM_edge_is_wire(e_iter));
 
92
        }
 
93
 
 
94
        /* go through and split edge */
 
95
        for (i = 0, tot_found = 0; i < einput_len; i++) {
 
96
                BMEdge *e = einput_arr[i];
 
97
                const float angle = BM_edge_calc_face_angle(e);
 
98
 
 
99
                if (angle < angle_limit) {
 
100
                        tot_found++;
 
101
                }
 
102
                weight_elems[i].ele = (BMHeader *)e;
 
103
                weight_elems[i].weight = angle;
 
104
        }
 
105
 
 
106
        if (tot_found != 0) {
 
107
                qsort(weight_elems, einput_len, sizeof(DissolveElemWeight), dissolve_elem_cmp);
 
108
 
 
109
                for (i = 0; i < tot_found; i++) {
 
110
                        BMEdge *e = (BMEdge *)weight_elems[i].ele;
 
111
 
 
112
                        if (/* may have become non-manifold */
 
113
                            BM_edge_is_manifold(e) &&
 
114
                            /* check twice because cumulative effect could dissolve over angle limit */
 
115
                            (BM_edge_calc_face_angle(e) < angle_limit))
 
116
                        {
 
117
                                BMFace *nf = BM_faces_join_pair(bm, e->l->f,
 
118
                                                                e->l->radial_next->f,
 
119
                                                                e,
 
120
                                                                false); /* join faces */
 
121
 
 
122
                                /* there may be some errors, we don't mind, just move on */
 
123
                                if (nf) {
 
124
                                        BM_face_normal_update(nf);
 
125
                                }
 
126
                                else {
 
127
                                        BMO_error_clear(bm);
 
128
                                }
 
129
                        }
 
130
                }
 
131
        }
 
132
 
 
133
        /* prepare for cleanup */
 
134
        BM_mesh_elem_index_ensure(bm, BM_VERT);
 
135
        vert_reverse_lookup = MEM_mallocN(sizeof(int) * bm->totvert, __func__);
 
136
        fill_vn_i(vert_reverse_lookup, bm->totvert, -1);
 
137
        for (i = 0, tot_found = 0; i < vinput_len; i++) {
 
138
                BMVert *v = vinput_arr[i];
 
139
                vert_reverse_lookup[BM_elem_index_get(v)] = i;
 
140
        }
 
141
 
 
142
        /* --- cleanup --- */
 
143
        earray = MEM_mallocN(sizeof(BMEdge *) * bm->totedge, __func__);
 
144
        BM_ITER_MESH_INDEX (e_iter, &iter, bm, BM_EDGES_OF_MESH, i) {
 
145
                earray[i] = e_iter;
 
146
        }
 
147
        /* remove all edges/verts left behind from dissolving, NULL'ing the vertex array so we dont re-use */
 
148
        for (i = bm->totedge - 1; i != -1; i--) {
 
149
                e_iter = earray[i];
 
150
 
 
151
                if (BM_edge_is_wire(e_iter) && (BM_elem_flag_test(e_iter, BM_ELEM_TAG) == false)) {
 
152
                        /* edge has become wire */
 
153
                        int vidx_reverse;
 
154
                        BMVert *v1 = e_iter->v1;
 
155
                        BMVert *v2 = e_iter->v2;
 
156
                        BM_edge_kill(bm, e_iter);
 
157
                        if (v1->e == NULL) {
 
158
                                vidx_reverse = vert_reverse_lookup[BM_elem_index_get(v1)];
 
159
                                if (vidx_reverse != -1) vinput_arr[vidx_reverse] = NULL;
 
160
                                BM_vert_kill(bm, v1);
 
161
                        }
 
162
                        if (v2->e == NULL) {
 
163
                                vidx_reverse = vert_reverse_lookup[BM_elem_index_get(v2)];
 
164
                                if (vidx_reverse != -1) vinput_arr[vidx_reverse] = NULL;
 
165
                                BM_vert_kill(bm, v2);
 
166
                        }
 
167
                }
 
168
        }
 
169
        MEM_freeN(vert_reverse_lookup);
 
170
 
 
171
        MEM_freeN(earray);
 
172
 
 
173
 
 
174
        /* --- second verts --- */
 
175
        if (do_dissolve_boundaries) {
 
176
                /* simple version of the branch below, sincve we will dissolve _all_ verts that use 2 edges */
 
177
                for (i = 0; i < vinput_len; i++) {
 
178
                        BMVert *v = vinput_arr[i];
 
179
                        if (LIKELY(v != NULL) &&
 
180
                            BM_vert_edge_count(v) == 2)
 
181
                        {
 
182
                                BM_vert_collapse_edge(bm, v->e, v, true); /* join edges */
 
183
                        }
 
184
                }
 
185
        }
 
186
        else {
 
187
                for (i = 0, tot_found = 0; i < vinput_len; i++) {
 
188
                        BMVert *v = vinput_arr[i];
 
189
                        const float angle = v ? bm_vert_edge_face_angle(v) : angle_limit;
 
190
 
 
191
                        if (angle < angle_limit) {
 
192
                                weight_elems[i].ele = (BMHeader *)v;
 
193
                                weight_elems[i].weight = angle;
 
194
                                tot_found++;
 
195
                        }
 
196
                        else {
 
197
                                weight_elems[i].ele = NULL;
 
198
                                weight_elems[i].weight = angle_max;
 
199
                        }
 
200
                }
 
201
 
 
202
                if (tot_found != 0) {
 
203
                        qsort(weight_elems, vinput_len, sizeof(DissolveElemWeight), dissolve_elem_cmp);
 
204
 
 
205
                        for (i = 0; i < tot_found; i++) {
 
206
                                BMVert *v = (BMVert *)weight_elems[i].ele;
 
207
                                if (LIKELY(v != NULL) &&
 
208
                                    /* topology changes may cause this to be un-collapsable */
 
209
                                    (BM_vert_edge_count(v) == 2) &&
 
210
                                    /* check twice because cumulative effect could dissolve over angle limit */
 
211
                                    bm_vert_edge_face_angle(v) < angle_limit)
 
212
                                {
 
213
                                        BMEdge *ne = BM_vert_collapse_edge(bm, v->e, v, true); /* join edges */
 
214
 
 
215
                                        if (ne && ne->l) {
 
216
                                                BM_edge_normals_update(ne);
 
217
                                        }
 
218
                                }
 
219
                        }
 
220
                }
 
221
        }
 
222
 
 
223
        MEM_freeN(weight_elems);
 
224
}
 
225
 
 
226
void BM_mesh_decimate_dissolve(BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries)
 
227
{
 
228
        int vinput_len;
 
229
        int einput_len;
 
230
 
 
231
        BMVert **vinput_arr = BM_iter_as_arrayN(bm, BM_VERTS_OF_MESH, NULL, &vinput_len, NULL, 0);
 
232
        BMEdge **einput_arr = BM_iter_as_arrayN(bm, BM_EDGES_OF_MESH, NULL, &einput_len, NULL, 0);
 
233
 
 
234
        BM_mesh_decimate_dissolve_ex(bm, angle_limit, do_dissolve_boundaries,
 
235
                                     vinput_arr, vinput_len,
 
236
                                     einput_arr, einput_len);
 
237
 
 
238
        MEM_freeN(vinput_arr);
 
239
        MEM_freeN(einput_arr);
 
240
}