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