BMesh: add ability not to delete vertex when collapsing
[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 #include "BLI_heap.h"
34
35 #include "bmesh.h"
36 #include "bmesh_decimate.h"  /* own include */
37
38 #define COST_INVALID FLT_MAX
39
40
41 /* multiply vertex edge angle by face angle
42  * this means we are not left with sharp corners between _almost_ planer faces
43  * convert angles [0-PI/2] -> [0-1], multiply together, then convert back to radians. */
44 static float bm_vert_edge_face_angle(BMVert *v)
45 {
46 #define UNIT_TO_ANGLE DEG2RADF(90.0f)
47 #define ANGLE_TO_UNIT (1.0f / UNIT_TO_ANGLE)
48
49         const float angle = BM_vert_calc_edge_angle(v);
50         /* note: could be either edge, it doesn't matter */
51         if (v->e && BM_edge_is_manifold(v->e)) {
52                 return ((angle * ANGLE_TO_UNIT) * (BM_edge_calc_face_angle(v->e) * ANGLE_TO_UNIT)) * UNIT_TO_ANGLE;
53         }
54         else {
55                 return angle;
56         }
57
58 #undef UNIT_TO_ANGLE
59 #undef ANGLE_TO_UNIT
60 }
61
62 static float bm_edge_calc_dissolve_error(const BMEdge *e, const BMO_Delimit delimit)
63 {
64         const bool is_contig = BM_edge_is_contiguous(e);
65         float angle;
66
67         if (!BM_edge_is_manifold(e)) {
68                 goto fail;
69         }
70
71         if ((delimit & BMO_DELIM_SEAM) &&
72             (BM_elem_flag_test(e, BM_ELEM_SEAM)))
73         {
74                 goto fail;
75         }
76
77         if ((delimit & BMO_DELIM_MATERIAL) &&
78             (e->l->f->mat_nr != e->l->radial_next->f->mat_nr))
79         {
80                 goto fail;
81         }
82
83         if ((delimit & BMO_DELIM_NORMAL) &&
84             (is_contig == false))
85         {
86                 goto fail;
87         }
88
89         angle = BM_edge_calc_face_angle(e);
90         if (is_contig == false) {
91                 angle = (float)M_PI - angle;
92         }
93
94         return angle;
95
96 fail:
97         return COST_INVALID;
98 }
99
100
101 void BM_mesh_decimate_dissolve_ex(BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries,
102                                   const BMO_Delimit delimit,
103                                   BMVert **vinput_arr, const int vinput_len,
104                                   BMEdge **einput_arr, const int einput_len,
105                                   const short oflag_out)
106 {
107         const int eheap_table_len = do_dissolve_boundaries ? einput_len : max_ii(einput_len, vinput_len);
108         void *_heap_table = MEM_mallocN(sizeof(HeapNode *) * eheap_table_len, __func__);
109
110         int i;
111
112         /* --- first edges --- */
113         if (1) {
114                 BMEdge **earray;
115                 Heap *eheap;
116                 HeapNode **eheap_table = _heap_table;
117                 HeapNode *enode_top;
118                 int *vert_reverse_lookup;
119                 BMIter iter;
120                 BMEdge *e_iter;
121
122                 /* --- setup heap --- */
123                 eheap = BLI_heap_new_ex(einput_len);
124                 eheap_table = _heap_table;
125
126                 /* wire -> tag */
127                 BM_ITER_MESH (e_iter, &iter, bm, BM_EDGES_OF_MESH) {
128                         BM_elem_flag_set(e_iter, BM_ELEM_TAG, BM_edge_is_wire(e_iter));
129                         BM_elem_index_set(e_iter, -1);  /* set dirty */
130                 }
131                 bm->elem_index_dirty |= BM_EDGE;
132
133                 /* build heap */
134                 for (i = 0; i < einput_len; i++) {
135                         BMEdge *e = einput_arr[i];
136                         const float cost = bm_edge_calc_dissolve_error(e, delimit);
137                         eheap_table[i] = BLI_heap_insert(eheap, cost, e);
138                         BM_elem_index_set(e, i);  /* set dirty */
139                 }
140
141                 while ((BLI_heap_is_empty(eheap) == false) &&
142                        (BLI_heap_node_value((enode_top = BLI_heap_top(eheap))) < angle_limit))
143                 {
144                         BMFace *f_new = NULL;
145                         BMEdge *e;
146
147                         e = BLI_heap_node_ptr(enode_top);
148                         i = BM_elem_index_get(e);
149
150                         if (BM_edge_is_manifold(e)) {
151                                 f_new = BM_faces_join_pair(bm, e->l->f,
152                                                            e->l->radial_next->f, e,
153                                                            false); /* join faces */
154
155                                 if (f_new) {
156                                         BMLoop *l_first, *l_iter;
157
158                                         BLI_heap_remove(eheap, enode_top);
159                                         eheap_table[i] = NULL;
160
161                                         /* update normal */
162                                         BM_face_normal_update(f_new);
163                                         if (oflag_out) {
164                                                 BMO_elem_flag_enable(bm, f_new, oflag_out);
165                                         }
166
167                                         /* re-calculate costs */
168                                         l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
169                                         do {
170                                                 const int j = BM_elem_index_get(l_iter->e);
171                                                 if (j != -1 && eheap_table[j]) {
172                                                         const float cost = bm_edge_calc_dissolve_error(l_iter->e, delimit);
173                                                         BLI_heap_remove(eheap, eheap_table[j]);
174                                                         eheap_table[j] = BLI_heap_insert(eheap, cost, l_iter->e);
175                                                 }
176                                         } while ((l_iter = l_iter->next) != l_first);
177                                 }
178                                 else {
179                                         BMO_error_clear(bm);
180                                 }
181                         }
182
183                         if (UNLIKELY(f_new == NULL)) {
184                                 BLI_heap_remove(eheap, enode_top);
185                                 eheap_table[i] = BLI_heap_insert(eheap, COST_INVALID, e);
186                         }
187                 }
188
189                 /* prepare for cleanup */
190                 BM_mesh_elem_index_ensure(bm, BM_VERT);
191                 vert_reverse_lookup = MEM_mallocN(sizeof(int) * bm->totvert, __func__);
192                 fill_vn_i(vert_reverse_lookup, bm->totvert, -1);
193                 for (i = 0; i < vinput_len; i++) {
194                         BMVert *v = vinput_arr[i];
195                         vert_reverse_lookup[BM_elem_index_get(v)] = i;
196                 }
197
198                 /* --- cleanup --- */
199                 earray = MEM_mallocN(sizeof(BMEdge *) * bm->totedge, __func__);
200                 BM_ITER_MESH_INDEX (e_iter, &iter, bm, BM_EDGES_OF_MESH, i) {
201                         earray[i] = e_iter;
202                 }
203                 /* remove all edges/verts left behind from dissolving, NULL'ing the vertex array so we dont re-use */
204                 for (i = bm->totedge - 1; i != -1; i--) {
205                         e_iter = earray[i];
206
207                         if (BM_edge_is_wire(e_iter) && (BM_elem_flag_test(e_iter, BM_ELEM_TAG) == false)) {
208                                 /* edge has become wire */
209                                 int vidx_reverse;
210                                 BMVert *v1 = e_iter->v1;
211                                 BMVert *v2 = e_iter->v2;
212                                 BM_edge_kill(bm, e_iter);
213                                 if (v1->e == NULL) {
214                                         vidx_reverse = vert_reverse_lookup[BM_elem_index_get(v1)];
215                                         if (vidx_reverse != -1) vinput_arr[vidx_reverse] = NULL;
216                                         BM_vert_kill(bm, v1);
217                                 }
218                                 if (v2->e == NULL) {
219                                         vidx_reverse = vert_reverse_lookup[BM_elem_index_get(v2)];
220                                         if (vidx_reverse != -1) vinput_arr[vidx_reverse] = NULL;
221                                         BM_vert_kill(bm, v2);
222                                 }
223                         }
224                 }
225                 MEM_freeN(vert_reverse_lookup);
226                 MEM_freeN(earray);
227
228                 BLI_heap_free(eheap, NULL);
229         }
230
231
232         /* --- second verts --- */
233         if (do_dissolve_boundaries) {
234                 /* simple version of the branch below, since we will dissolve _all_ verts that use 2 edges */
235                 for (i = 0; i < vinput_len; i++) {
236                         BMVert *v = vinput_arr[i];
237                         if (LIKELY(v != NULL) &&
238                             BM_vert_edge_count(v) == 2)
239                         {
240                                 BM_vert_collapse_edge(bm, v->e, v, true, true);  /* join edges */
241                         }
242                 }
243         }
244         else {
245                 Heap *vheap;
246                 HeapNode **vheap_table = _heap_table;
247                 HeapNode *vnode_top;
248
249                 BMVert *v_iter;
250                 BMIter iter;
251
252                 BM_ITER_MESH (v_iter, &iter, bm, BM_VERTS_OF_MESH) {
253                         BM_elem_index_set(v_iter, -1);  /* set dirty */
254                 }
255                 bm->elem_index_dirty |= BM_VERT;
256
257                 vheap = BLI_heap_new_ex(vinput_len);
258
259                 for (i = 0; i < vinput_len; i++) {
260                         BMVert *v = vinput_arr[i];
261                         if (LIKELY(v != NULL)) {
262                                 const float cost = bm_vert_edge_face_angle(v);
263                                 vheap_table[i] = BLI_heap_insert(vheap, cost, v);
264                                 BM_elem_index_set(v, i);  /* set dirty */
265                         }
266                 }
267
268                 while ((BLI_heap_is_empty(vheap) == false) &&
269                        (BLI_heap_node_value((vnode_top = BLI_heap_top(vheap))) < angle_limit))
270                 {
271                         BMEdge *e_new = NULL;
272                         BMVert *v;
273
274                         v = BLI_heap_node_ptr(vnode_top);
275                         i = BM_elem_index_get(v);
276
277                         if (BM_vert_edge_count(v) == 2) {
278                                 e_new = BM_vert_collapse_edge(bm, v->e, v, true, true);  /* join edges */
279
280                                 if (e_new) {
281
282                                         BLI_heap_remove(vheap, vnode_top);
283                                         vheap_table[i] = NULL;
284
285                                         /* update normal */
286                                         if (e_new->l) {
287                                                 BMLoop *l_first, *l_iter;
288                                                 l_iter = l_first = e_new->l;
289                                                 do {
290                                                         BM_face_normal_update(l_iter->f);
291                                                 } while ((l_iter = l_iter->radial_next) != l_first);
292
293                                         }
294
295                                         /* re-calculate costs */
296                                         BM_ITER_ELEM (v_iter, &iter, e_new, BM_VERTS_OF_EDGE) {
297                                                 const int j = BM_elem_index_get(v_iter);
298                                                 if (j != -1 && vheap_table[j]) {
299                                                         const float cost = bm_vert_edge_face_angle(v_iter);
300                                                         BLI_heap_remove(vheap, vheap_table[j]);
301                                                         vheap_table[j] = BLI_heap_insert(vheap, cost, v_iter);
302                                                 }
303                                         }
304                                 }
305                         }
306
307                         if (UNLIKELY(e_new == NULL)) {
308                                 BLI_heap_remove(vheap, vnode_top);
309                                 vheap_table[i] = BLI_heap_insert(vheap, COST_INVALID, v);
310                         }
311                 }
312
313                 BLI_heap_free(vheap, NULL);
314         }
315
316         MEM_freeN(_heap_table);
317 }
318
319 void BM_mesh_decimate_dissolve(BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries,
320                                const BMO_Delimit delimit)
321 {
322         int vinput_len;
323         int einput_len;
324
325         BMVert **vinput_arr = BM_iter_as_arrayN(bm, BM_VERTS_OF_MESH, NULL, &vinput_len, NULL, 0);
326         BMEdge **einput_arr = BM_iter_as_arrayN(bm, BM_EDGES_OF_MESH, NULL, &einput_len, NULL, 0);
327
328
329         BM_mesh_decimate_dissolve_ex(bm, angle_limit, do_dissolve_boundaries,
330                                      delimit,
331                                      vinput_arr, vinput_len,
332                                      einput_arr, einput_len,
333                                      0);
334
335         MEM_freeN(vinput_arr);
336         MEM_freeN(einput_arr);
337 }