correct problem with limited-dissolve not leaving the selection correctly (caused...
[blender.git] / 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                                   const BMO_Delimit delimit,
74                                   BMVert **vinput_arr, const int vinput_len,
75                                   BMEdge **einput_arr, const int einput_len,
76                                   const short oflag_out)
77 {
78         const float angle_max = (float)M_PI / 2.0f;
79         DissolveElemWeight *weight_elems = MEM_mallocN(max_ii(einput_len, vinput_len) *
80                                                        sizeof(DissolveElemWeight), __func__);
81         int i, tot_found;
82         BMIter iter;
83         BMEdge *e_iter;
84         BMEdge **earray;
85
86         int *vert_reverse_lookup;
87
88         /* --- first edges --- */
89
90         /* wire -> tag */
91         BM_ITER_MESH (e_iter, &iter, bm, BM_EDGES_OF_MESH) {
92                 BM_elem_flag_set(e_iter, BM_ELEM_TAG, BM_edge_is_wire(e_iter));
93         }
94
95         /* go through and split edge */
96         for (i = 0, tot_found = 0; i < einput_len; i++) {
97                 BMEdge *e = einput_arr[i];
98                 const bool is_contig = BM_edge_is_contiguous(e);
99                 float angle;
100
101                 angle = BM_edge_calc_face_angle(e);
102                 if (is_contig == false) {
103                         angle = (float)M_PI - angle;
104                 }
105
106                 if (angle < angle_limit) {
107                         tot_found++;
108                 }
109                 weight_elems[i].ele = (BMHeader *)e;
110                 weight_elems[i].weight = angle;
111         }
112
113         if (tot_found != 0) {
114                 qsort(weight_elems, einput_len, sizeof(DissolveElemWeight), dissolve_elem_cmp);
115
116                 for (i = 0; i < tot_found; i++) {
117                         BMEdge *e = (BMEdge *)weight_elems[i].ele;
118                         const bool is_contig = BM_edge_is_contiguous(e);
119                         float angle;
120
121                         /* may have become non-manifold */
122                         if (!BM_edge_is_manifold(e)) {
123                                 continue;
124                         }
125
126                         if ((delimit & BMO_DELIM_SEAM) &&
127                             (BM_elem_flag_test(e, BM_ELEM_SEAM)))
128                         {
129                                 continue;
130                         }
131
132                         if ((delimit & BMO_DELIM_MATERIAL) &&
133                             (e->l->f->mat_nr != e->l->radial_next->f->mat_nr))
134                         {
135                                 continue;
136                         }
137
138                         if ((delimit & BMO_DELIM_NORMAL) &&
139                             (is_contig == false))
140                         {
141                                 continue;
142                         }
143
144                         /* check twice because cumulative effect could dissolve over angle limit */
145                         angle = BM_edge_calc_face_angle(e);
146                         if (is_contig == false) {
147                                 angle = (float)M_PI - angle;
148                         }
149
150                         if (angle < angle_limit) {
151                                 BMFace *f_new = BM_faces_join_pair(bm, e->l->f,
152                                                                    e->l->radial_next->f,
153                                                                    e,
154                                                                    false); /* join faces */
155
156                                 /* there may be some errors, we don't mind, just move on */
157                                 if (f_new) {
158                                         BM_face_normal_update(f_new);
159                                         if (oflag_out) {
160                                                 BMO_elem_flag_enable(bm, f_new, oflag_out);
161                                         }
162                                 }
163                                 else {
164                                         BMO_error_clear(bm);
165                                 }
166                         }
167                 }
168         }
169
170         /* prepare for cleanup */
171         BM_mesh_elem_index_ensure(bm, BM_VERT);
172         vert_reverse_lookup = MEM_mallocN(sizeof(int) * bm->totvert, __func__);
173         fill_vn_i(vert_reverse_lookup, bm->totvert, -1);
174         for (i = 0, tot_found = 0; i < vinput_len; i++) {
175                 BMVert *v = vinput_arr[i];
176                 vert_reverse_lookup[BM_elem_index_get(v)] = i;
177         }
178
179         /* --- cleanup --- */
180         earray = MEM_mallocN(sizeof(BMEdge *) * bm->totedge, __func__);
181         BM_ITER_MESH_INDEX (e_iter, &iter, bm, BM_EDGES_OF_MESH, i) {
182                 earray[i] = e_iter;
183         }
184         /* remove all edges/verts left behind from dissolving, NULL'ing the vertex array so we dont re-use */
185         for (i = bm->totedge - 1; i != -1; i--) {
186                 e_iter = earray[i];
187
188                 if (BM_edge_is_wire(e_iter) && (BM_elem_flag_test(e_iter, BM_ELEM_TAG) == false)) {
189                         /* edge has become wire */
190                         int vidx_reverse;
191                         BMVert *v1 = e_iter->v1;
192                         BMVert *v2 = e_iter->v2;
193                         BM_edge_kill(bm, e_iter);
194                         if (v1->e == NULL) {
195                                 vidx_reverse = vert_reverse_lookup[BM_elem_index_get(v1)];
196                                 if (vidx_reverse != -1) vinput_arr[vidx_reverse] = NULL;
197                                 BM_vert_kill(bm, v1);
198                         }
199                         if (v2->e == NULL) {
200                                 vidx_reverse = vert_reverse_lookup[BM_elem_index_get(v2)];
201                                 if (vidx_reverse != -1) vinput_arr[vidx_reverse] = NULL;
202                                 BM_vert_kill(bm, v2);
203                         }
204                 }
205         }
206         MEM_freeN(vert_reverse_lookup);
207
208         MEM_freeN(earray);
209
210
211         /* --- second verts --- */
212         if (do_dissolve_boundaries) {
213                 /* simple version of the branch below, sincve we will dissolve _all_ verts that use 2 edges */
214                 for (i = 0; i < vinput_len; i++) {
215                         BMVert *v = vinput_arr[i];
216                         if (LIKELY(v != NULL) &&
217                             BM_vert_edge_count(v) == 2)
218                         {
219                                 BM_vert_collapse_edge(bm, v->e, v, true); /* join edges */
220                         }
221                 }
222         }
223         else {
224                 for (i = 0, tot_found = 0; i < vinput_len; i++) {
225                         BMVert *v = vinput_arr[i];
226                         const float angle = v ? bm_vert_edge_face_angle(v) : angle_limit;
227
228                         if (angle < angle_limit) {
229                                 weight_elems[i].ele = (BMHeader *)v;
230                                 weight_elems[i].weight = angle;
231                                 tot_found++;
232                         }
233                         else {
234                                 weight_elems[i].ele = NULL;
235                                 weight_elems[i].weight = angle_max;
236                         }
237                 }
238
239                 if (tot_found != 0) {
240                         qsort(weight_elems, vinput_len, sizeof(DissolveElemWeight), dissolve_elem_cmp);
241
242                         for (i = 0; i < tot_found; i++) {
243                                 BMVert *v = (BMVert *)weight_elems[i].ele;
244                                 if (LIKELY(v != NULL) &&
245                                     /* topology changes may cause this to be un-collapsable */
246                                     (BM_vert_edge_count(v) == 2) &&
247                                     /* check twice because cumulative effect could dissolve over angle limit */
248                                     bm_vert_edge_face_angle(v) < angle_limit)
249                                 {
250                                         BMEdge *e_new = BM_vert_collapse_edge(bm, v->e, v, true); /* join edges */
251
252                                         if (e_new && e_new->l) {
253                                                 BM_edge_normals_update(e_new);
254                                         }
255                                 }
256                         }
257                 }
258         }
259
260         MEM_freeN(weight_elems);
261 }
262
263 void BM_mesh_decimate_dissolve(BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries,
264                                const BMO_Delimit delimit)
265 {
266         int vinput_len;
267         int einput_len;
268
269         BMVert **vinput_arr = BM_iter_as_arrayN(bm, BM_VERTS_OF_MESH, NULL, &vinput_len, NULL, 0);
270         BMEdge **einput_arr = BM_iter_as_arrayN(bm, BM_EDGES_OF_MESH, NULL, &einput_len, NULL, 0);
271
272
273         BM_mesh_decimate_dissolve_ex(bm, angle_limit, do_dissolve_boundaries,
274                                      delimit,
275                                      vinput_arr, vinput_len,
276                                      einput_arr, einput_len,
277                                      0);
278
279         MEM_freeN(vinput_arr);
280         MEM_freeN(einput_arr);
281 }