style cleanup
[blender.git] / source / blender / bmesh / intern / bmesh_decimate.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/intern/bmesh_decimate.c
24  *  \ingroup bmesh
25  *
26  * BMesh decimator.
27  */
28
29 #include <stddef.h>
30
31 #include "MEM_guardedalloc.h"
32
33 #include "DNA_scene_types.h"
34
35 #include "BLI_math.h"
36 #include "BLI_quadric.h"
37 #include "BLI_heap.h"
38
39 #include "BKE_customdata.h"
40
41 #include "bmesh.h"
42 #include "bmesh_structure.h"
43 #include "bmesh_decimate.h"
44
45 /* defines for testing */
46 #define USE_CUSTOMDATA
47 #define USE_TRIANGULATE
48
49 /* these checks are for rare cases that we can't avoid since they are valid meshes still */
50 #define USE_SAFETY_CHECKS
51
52 #define BOUNDARY_PRESERVE_WEIGHT 100.0f
53
54 typedef enum CD_UseFlag {
55         CD_DO_VERT,
56         CD_DO_EDGE,
57         CD_DO_LOOP
58 } CD_UseFlag;
59
60
61 /* BMesh Helper Functions
62  * ********************** */
63
64 /**
65  * \param vquadrics must be calloc'd
66  */
67 static void bm_decim_build_quadrics(BMesh *bm, Quadric *vquadrics)
68 {
69         BMIter iter;
70         BMFace *f;
71         BMEdge *e;
72
73         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
74                 BMLoop *l_first;
75                 BMLoop *l_iter;
76
77                 const float *co = BM_FACE_FIRST_LOOP(f)->v->co;
78                 const float *no = f->no;
79                 const float offset = -dot_v3v3(no, co);
80                 Quadric q;
81
82                 BLI_quadric_from_v3_dist(&q, no, offset);
83
84                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
85                 do {
86                         BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(l_iter->v)], &q);
87                 } while ((l_iter = l_iter->next) != l_first);
88         }
89
90         /* boundary edges */
91         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
92                 if (UNLIKELY(BM_edge_is_boundary(e))) {
93                         float edge_vector[3];
94                         float edge_cross[3];
95                         sub_v3_v3v3(edge_vector, e->v2->co, e->v1->co);
96                         f = e->l->f;
97                         cross_v3_v3v3(edge_cross, edge_vector, f->no);
98
99                         if (normalize_v3(edge_cross) != 0.0f) {
100                                 Quadric q;
101                                 BLI_quadric_from_v3_dist(&q, edge_vector, -dot_v3v3(edge_cross, e->v1->co));
102                                 BLI_quadric_mul(&q, BOUNDARY_PRESERVE_WEIGHT);
103
104                                 BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(e->v1)], &q);
105                                 BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(e->v2)], &q);
106                         }
107                 }
108         }
109 }
110
111
112 static void bm_decim_calc_target_co(BMEdge *e, float optimize_co[3],
113                                     const Quadric *vquadrics)
114 {
115         /* compute an edge contration target for edge ei
116          * this is computed by summing it's vertices quadrics and
117          * optimizing the result. */
118         Quadric q;
119
120         BLI_quadric_add_qu_ququ(&q,
121                                 &vquadrics[BM_elem_index_get(e->v1)],
122                                 &vquadrics[BM_elem_index_get(e->v2)]);
123
124
125         if (BLI_quadric_optimize(&q, optimize_co)) {
126                 return;  /* all is good */
127         }
128         else {
129                 mid_v3_v3v3(optimize_co, e->v1->co, e->v2->co);
130         }
131 }
132
133 static void bm_decim_build_edge_cost_single(BMEdge *e,
134                                             const Quadric *vquadrics,
135                                             Heap *eheap, HeapNode **eheap_table)
136 {
137         const Quadric *q1, *q2;
138         float optimize_co[3];
139         float cost;
140
141         if (eheap_table[BM_elem_index_get(e)]) {
142                 BLI_heap_remove(eheap, eheap_table[BM_elem_index_get(e)]);
143         }
144
145         /* check we can collapse, some edges we better not touch */
146         if (BM_edge_is_boundary(e)) {
147                 if (e->l->f->len == 3) {
148                         /* pass */
149                 }
150                 else {
151                         /* only collapse tri's */
152                         eheap_table[BM_elem_index_get(e)] = NULL;
153                         return;
154                 }
155         }
156         else if (BM_edge_is_manifold(e)) {
157                 if ((e->l->f->len == 3) && (e->l->radial_next->f->len == 3)) {
158                         /* pass */
159                 }
160                 else {
161                         /* only collapse tri's */
162                         eheap_table[BM_elem_index_get(e)] = NULL;
163                         return;
164                 }
165         }
166         else {
167                 eheap_table[BM_elem_index_get(e)] = NULL;
168                 return;
169         }
170         /* end sanity check */
171
172
173         bm_decim_calc_target_co(e, optimize_co, vquadrics);
174
175         q1 = &vquadrics[BM_elem_index_get(e->v1)];
176         q2 = &vquadrics[BM_elem_index_get(e->v2)];
177
178         cost = (BLI_quadric_evaluate(q1, optimize_co) + BLI_quadric_evaluate(q2, optimize_co));
179
180         eheap_table[BM_elem_index_get(e)] = BLI_heap_insert(eheap, cost, e);
181 }
182
183 static void bm_decim_build_edge_cost(BMesh *bm,
184                                      const Quadric *vquadrics,
185                                      Heap *eheap, HeapNode **eheap_table)
186 {
187         BMIter iter;
188         BMEdge *e;
189         unsigned int i;
190
191         BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
192                 eheap_table[i] = NULL;  /* keep sanity check happy */
193                 bm_decim_build_edge_cost_single(e, vquadrics, eheap, eheap_table);
194         }
195 }
196
197 #ifdef USE_TRIANGULATE
198 /* Temp Triangulation
199  * ****************** */
200
201 /**
202  * To keep things simple we can only collapse edges on triangulated data
203  * (limitation with edge collapse and error calculation functions).
204  *
205  * But to avoid annoying users by only giving triangle results, we can
206  * triangulate, keeping a reference between the faces, then join after
207  * if the edges don't collapse, this will also allow more choices when
208  * collapsing edges so even has some advantage over decimating quads
209  * directly.
210  *
211  * \return TRUE if any faces were triangulated.
212  */
213
214 static int bm_decim_triangulate_begin(BMesh *bm)
215 {
216 #ifdef USE_SAFETY_CHECKS
217         const int check_double_edges = TRUE;
218 #else
219         const int check_double_edges = FALSE;
220 #endif
221
222         BMIter iter;
223         BMFace *f;
224         // int has_quad;  // could optimize this a little
225         int has_cut = FALSE;
226
227         BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);
228
229         /* first clear loop index values */
230         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
231                 BMLoop *l_iter;
232                 BMLoop *l_first;
233
234                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
235                 do {
236                         BM_elem_index_set(l_iter, -1);
237                 } while ((l_iter = l_iter->next) != l_first);
238
239                 // has_quad |= (f->len == 4)
240         }
241
242         /* adding new faces as we loop over faces
243          * is normally best avoided, however in this case its not so bad because any face touched twice
244          * will already be triangulated*/
245         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
246                 if (f->len == 4) {
247                         BMLoop *f_l[4];
248                         BMLoop *l_iter;
249                         BMLoop *l_a, *l_b;
250
251                         l_iter = BM_FACE_FIRST_LOOP(f);
252
253                         f_l[0] = l_iter; l_iter = l_iter->next;
254                         f_l[1] = l_iter; l_iter = l_iter->next;
255                         f_l[2] = l_iter; l_iter = l_iter->next;
256                         f_l[3] = l_iter; l_iter = l_iter->next;
257
258                         if (len_squared_v3v3(f_l[0]->v->co, f_l[2]->v->co) < len_squared_v3v3(f_l[1]->v->co, f_l[3]->v->co)) {
259                                 l_a = f_l[0];
260                                 l_b = f_l[2];
261                         }
262                         else {
263                                 l_a = f_l[1];
264                                 l_b = f_l[3];
265                         }
266
267                         {
268                                 BMFace *f_new;
269                                 BMLoop *l_new;
270
271                                 /* warning, NO_DOUBLE option here isn't handled as nice as it could be
272                                  * - if there is a quad that has a free standing edge joining it along
273                                  * where we want to split the face, there isnt a good way we can handle this.
274                                  * currently that edge will get removed when joining the tris back into a quad. */
275                                 f_new = BM_face_split(bm, f, l_a->v, l_b->v, &l_new, NULL, check_double_edges);
276
277                                 if (f_new) {
278                                         /* the value of this doesn't matter, only that the 2 loops match and have unique values */
279                                         const int f_index = BM_elem_index_get(f);
280
281                                         /* since we just split theres only ever 2 loops */
282                                         BLI_assert(BM_edge_is_manifold(l_new->e));
283
284                                         BM_elem_index_set(l_new, f_index);
285                                         BM_elem_index_set(l_new->radial_next, f_index);
286
287                                         has_cut = TRUE;
288                                 }
289                         }
290                 }
291         }
292
293         BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);
294
295         if (has_cut) {
296                 /* now triangulation is done we need to correct index values */
297                 BM_mesh_elem_index_ensure(bm, BM_EDGE | BM_FACE);
298         }
299
300         return has_cut;
301 }
302
303 static void bm_decim_triangulate_end(BMesh *bm)
304 {
305         /* decimation finished, now re-join */
306         BMIter iter;
307         BMEdge *e;
308
309         /* boundary edges */
310         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
311                 BMLoop *l_a, *l_b;
312                 if (BM_edge_loop_pair(e, &l_a, &l_b)) {
313                         const int l_a_index = BM_elem_index_get(l_a);
314                         if (l_a_index != -1) {
315                                 const int l_b_index = BM_elem_index_get(l_b);
316                                 if (l_a_index == l_b_index) {
317                                         /* highly unlikely to fail, but prevents possible double-ups */
318                                         if (l_a->f->len == 3 && l_b->f->len == 3) {
319                                                 BMFace *f[2] = {l_a->f, l_b->f};
320                                                 BM_faces_join(bm, f, 2, TRUE);
321                                         }
322                                 }
323                         }
324                 }
325         }
326 }
327
328 #endif  /* USE_TRIANGULATE */
329
330 /* Edge Collapse Functions
331  * *********************** */
332
333 #ifdef USE_CUSTOMDATA
334
335 /**
336  * \param v is the target to merge into.
337  */
338 static void bm_edge_collapse_loop_customdata(BMesh *bm, BMLoop *l, BMVert *v_clear, BMVert *v_other,
339                                              const float customdata_fac)
340 {
341         /* these don't need to be updated, since they will get removed when the edge collapses */
342         BMLoop *l_clear, *l_other;
343         const int is_manifold = BM_edge_is_manifold(l->e);
344         int side;
345
346         /* l defines the vert to collapse into  */
347
348         /* first find the loop of 'v_other' thats attached to the face of 'l' */
349         if (l->v == v_clear) {
350                 l_clear = l;
351                 l_other = l->next;
352         }
353         else {
354                 l_clear = l->next;
355                 l_other = l;
356         }
357
358         BLI_assert(l_clear->v == v_clear);
359         BLI_assert(l_other->v == v_other);
360
361         /* now we have both corners of the face 'l->f' */
362         for (side = 0; side < 2; side++) {
363                 int is_seam = FALSE;
364                 void *src[2];
365                 BMFace *f_exit = is_manifold ? l->radial_next->f : NULL;
366                 BMEdge *e_prev = l->e;
367                 BMLoop *l_first;
368                 BMLoop *l_iter;
369                 float w[2];
370
371                 if (side == 0) {
372                         l_iter = l_first = l_clear;
373                         src[0] = l_clear->head.data;
374                         src[1] = l_other->head.data;
375
376                         w[0] = customdata_fac;
377                         w[1] = 1.0f - customdata_fac;
378                 }
379                 else {
380                         l_iter = l_first = l_other;
381                         src[0] = l_other->head.data;
382                         src[1] = l_clear->head.data;
383
384                         w[0] = 1.0f - customdata_fac;
385                         w[1] = customdata_fac;
386                 }
387
388                 /* WATCH IT! - should NOT reference (_clear or _other) vars for this while loop */
389
390                 /* walk around the fan using 'e_prev' */
391                 while (((l_iter = BM_vert_step_fan_loop(l_iter, &e_prev)) != l_first) && (l_iter != NULL)) {
392                         int i;
393                         /* quit once we hit the opposite face, if we have one */
394                         if (f_exit && UNLIKELY(f_exit == l_iter->f)) {
395                                 break;
396                         }
397
398                         /* break out unless we find a match */
399                         is_seam = TRUE;
400
401                         /* ok. we have a loop. now be smart with it! */
402                         for (i = 0; i < bm->ldata.totlayer; i++) {
403                                 if (CustomData_layer_has_math(&bm->ldata, i)) {
404                                         const int offset = bm->ldata.layers[i].offset;
405                                         const int type = bm->ldata.layers[i].type;
406                                         void *cd_src, *cd_iter;
407
408                                         /* todo, make nicer macros for this */
409                                         cd_src = (char *)src[0] + offset;
410                                         // cd_dst = (char *)src[1] + offset;  // UNUSED
411                                         cd_iter  = (char *)l_iter->head.data  + offset;
412
413                                         /* detect seams */
414                                         if (CustomData_data_equals(type, cd_src, cd_iter)) {
415                                                 CustomData_bmesh_interp(&bm->ldata, src, w, NULL, 2, l_iter->head.data);
416                                                 is_seam = FALSE;
417                                         }
418                                 }
419                         }
420
421                         if (is_seam) {
422                                 break;
423                         }
424                 }
425         }
426 }
427 #endif  /* USE_CUSTOMDATA */
428
429 /**
430  * special, highly limited edge collapse function
431  * intended for speed over flexibiliy.
432  * can only collapse edges connected to (1, 2) tris.
433  *
434  * Important - dont add vert/edge/face data on collapsing!
435  *
436  * \param e_clear_other let caller know what edges we remove besides \a e_clear
437  * \param customdata_flag merge factor, scales from 0 - 1 ('v_clear' -> 'v_other')
438  */
439 static int bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e_clear_other[2],
440 #ifdef USE_CUSTOMDATA
441                             const CD_UseFlag customdata_flag,
442                             const float customdata_fac
443 #else
444                             const CD_UseFlag UNUSED(customdata_flag),
445                             const float UNUSED(customdata_fac)
446 #endif
447                             )
448 {
449         BMVert *v_other = BM_edge_other_vert(e_clear, v_clear);
450
451         BLI_assert(v_other != NULL);
452
453         if (BM_edge_is_manifold(e_clear)) {
454                 BMLoop *l_a, *l_b;
455                 BMEdge *e_a_other[2], *e_b_other[2];
456                 int ok;
457
458                 ok = BM_edge_loop_pair(e_clear, &l_a, &l_b);
459
460                 BLI_assert(ok == TRUE);
461                 BLI_assert(l_a->f->len == 3);
462                 BLI_assert(l_b->f->len == 3);
463
464                 /* keep 'v_clear' 0th */
465                 if (BM_vert_in_edge(l_a->prev->e, v_clear)) {
466                         e_a_other[0] = l_a->prev->e;
467                         e_a_other[1] = l_a->next->e;
468                 }
469                 else {
470                         e_a_other[1] = l_a->prev->e;
471                         e_a_other[0] = l_a->next->e;
472                 }
473
474                 if (BM_vert_in_edge(l_b->prev->e, v_clear)) {
475                         e_b_other[0] = l_b->prev->e;
476                         e_b_other[1] = l_b->next->e;
477                 }
478                 else {
479                         e_b_other[1] = l_b->prev->e;
480                         e_b_other[0] = l_b->next->e;
481                 }
482
483                 BLI_assert(BM_edge_share_vert(e_a_other[0], e_b_other[0]));
484                 BLI_assert(BM_edge_share_vert(e_a_other[1], e_b_other[1]));
485
486                 /* we could assert this case, but better just bail out */
487 #if 0
488                 BLI_assert(e_a_other[0] != e_b_other[0]);
489                 BLI_assert(e_a_other[0] != e_b_other[1]);
490                 BLI_assert(e_b_other[0] != e_a_other[0]);
491                 BLI_assert(e_b_other[0] != e_a_other[1]);
492 #endif
493                 /* not totally common but we want to avoid */
494                 if (ELEM(e_a_other[0], e_b_other[0], e_b_other[1]) ||
495                     ELEM(e_a_other[1], e_b_other[0], e_b_other[1]))
496                 {
497                         return FALSE;
498                 }
499
500                 r_e_clear_other[0] = BM_elem_index_get(e_a_other[0]);
501                 r_e_clear_other[1] = BM_elem_index_get(e_b_other[0]);
502
503 #ifdef USE_CUSTOMDATA
504                 /* before killing, do customdata */
505                 if (customdata_flag & CD_DO_VERT) {
506                         BM_data_interp_from_verts(bm, v_other, v_clear, v_other, customdata_fac);
507                 }
508                 if (customdata_flag & CD_DO_EDGE) {
509                         BM_data_interp_from_edges(bm, e_a_other[1], e_a_other[0], e_a_other[1], customdata_fac);
510                         BM_data_interp_from_edges(bm, e_b_other[1], e_b_other[0], e_b_other[1], customdata_fac);
511                 }
512                 if (customdata_flag & CD_DO_LOOP) {
513                         bm_edge_collapse_loop_customdata(bm, e_clear->l,              v_clear, v_other, customdata_fac);
514                         bm_edge_collapse_loop_customdata(bm, e_clear->l->radial_next, v_clear, v_other, customdata_fac);
515                 }
516 #endif
517
518                 BM_edge_kill(bm, e_clear);
519
520                 BM_vert_splice(bm, v_clear, v_other);
521
522                 BM_edge_splice(bm, e_a_other[0], e_a_other[1]);
523                 BM_edge_splice(bm, e_b_other[0], e_b_other[1]);
524
525                 // BM_mesh_validate(bm);
526
527                 return TRUE;
528         }
529         else if (BM_edge_is_boundary(e_clear)) {
530                 /* same as above but only one triangle */
531                 BMLoop *l_a;
532                 BMEdge *e_a_other[2];
533
534                 l_a = e_clear->l;
535
536                 BLI_assert(l_a->f->len == 3);
537
538                 /* keep 'v_clear' 0th */
539                 if (BM_vert_in_edge(l_a->prev->e, v_clear)) {
540                         e_a_other[0] = l_a->prev->e;
541                         e_a_other[1] = l_a->next->e;
542                 }
543                 else {
544                         e_a_other[1] = l_a->prev->e;
545                         e_a_other[0] = l_a->next->e;
546                 }
547
548                 r_e_clear_other[0] = BM_elem_index_get(e_a_other[0]);
549                 r_e_clear_other[1] = -1;
550
551 #ifdef USE_CUSTOMDATA
552                 /* before killing, do customdata */
553                 if (customdata_flag & CD_DO_VERT) {
554                         BM_data_interp_from_verts(bm, v_other, v_clear, v_other, customdata_fac);
555                 }
556                 if (customdata_flag & CD_DO_EDGE) {
557                         BM_data_interp_from_edges(bm, e_a_other[1], e_a_other[0], e_a_other[1], customdata_fac);
558                 }
559                 if (customdata_flag & CD_DO_LOOP) {
560                         bm_edge_collapse_loop_customdata(bm, e_clear->l, v_clear, v_other, customdata_fac);
561                 }
562 #endif
563
564                 BM_edge_kill(bm, e_clear);
565
566                 BM_vert_splice(bm, v_clear, v_other);
567
568                 BM_edge_splice(bm, e_a_other[0], e_a_other[1]);
569
570                 // BM_mesh_validate(bm);
571
572                 return TRUE;
573         }
574         else {
575                 return FALSE;
576         }
577 }
578
579
580 /* collapse e the edge, removing e->v2 */
581 static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e,
582                                    Quadric *vquadrics,
583                                    Heap *eheap, HeapNode **eheap_table,
584                                    const CD_UseFlag customdata_flag)
585 {
586         int e_clear_other[2];
587         BMVert *v = e->v1;
588         int v_clear_index = BM_elem_index_get(e->v2);  /* the vert is removed so only store the index */
589         float optimize_co[3];
590         float customdata_fac;
591
592         bm_decim_calc_target_co(e, optimize_co, vquadrics);
593
594         /* use for customdata merging */
595         customdata_fac = line_point_factor_v3(optimize_co, e->v1->co, e->v2->co);
596
597         if (bm_edge_collapse(bm, e, e->v2, e_clear_other, customdata_flag, customdata_fac)) {
598                 /* update collapse info */
599                 int i;
600
601                 e = NULL;  /* paranoid safety check */
602
603                 copy_v3_v3(v->co, optimize_co);
604
605                 /* remove eheap */
606                 for (i = 0; i < 2; i++) {
607                         /* highly unlikely 'eheap_table[ke_other[i]]' would be NULL, but do for sanity sake */
608                         if ((e_clear_other[i] != -1) && (eheap_table[e_clear_other[i]] != NULL)) {
609                                 BLI_heap_remove(eheap, eheap_table[e_clear_other[i]]);
610                                 eheap_table[e_clear_other[i]] = NULL;
611                         }
612                 }
613
614                 /* update vertex quadric, add kept vertex from killed vertex */
615                 BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(v)], &vquadrics[v_clear_index]);
616
617                 /* update connected normals */
618
619                 /* in fact face normals are not used for progressive updates, no need to update them */
620                 // BM_vert_normal_update_all(v);
621                 BM_vert_normal_update(v);
622
623                 /* update error costs and the eheap */
624                 if (LIKELY(v->e)) {
625                         BMEdge *e_iter;
626                         BMEdge *e_first;
627                         e_iter = e_first = v->e;
628                         do {
629                                 //BLI_assert(BM_edge_find_double(e_iter) == NULL);
630 #ifdef USE_SAFETY_CHECKS
631                                 /* note! - this check is slow, but we can't avoid it - Campbell */
632                                 BMEdge *e_double;
633
634                                 e_double = BM_edge_find_double(e_iter);
635
636                                 if (UNLIKELY(e_double != NULL)) {
637                                         int e_index = BM_elem_index_get(e_double);
638                                         if (BM_edge_splice(bm, e_double, e_iter)) {
639                                                 if (eheap_table[e_index]) {
640                                                         BLI_heap_remove(eheap, eheap_table[e_index]);
641                                                         eheap_table[e_index] = NULL;
642                                                 }
643                                         }
644                                 }
645
646                                 /* could get some extra quality out of this but its not really needed */
647                                 // BM_vert_normal_update(BM_edge_other_vert(e_iter, v));
648
649                                 /* if this happens, the e_double check could be put in a while loop,
650                                  * so as to keep removing doubles while they are found. so far this isnt needed */
651                                 BLI_assert(BM_edge_find_double(e_iter) == NULL);
652 #endif
653
654                                 bm_decim_build_edge_cost_single(e_iter, vquadrics, eheap, eheap_table);
655                         } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
656                 }
657         }
658 }
659
660
661 /* Main Decimate Function
662  * ********************** */
663
664 void BM_mesh_decimate(BMesh *bm, const float factor)
665 {
666         Heap *eheap;             /* edge heap */
667         HeapNode **eheap_table;  /* edge index aligned table pointing to the eheap */
668         Quadric *vquadrics;      /* vert index aligned quadrics */
669         int tot_edge_orig;
670         int face_tot_target;
671         int use_triangulate;
672
673         CD_UseFlag customdata_flag = 0;
674
675 #ifdef USE_TRIANGULATE
676         /* temp convert quads to triangles */
677         use_triangulate = bm_decim_triangulate_begin(bm);
678 #endif
679
680
681         /* alloc vars */
682         vquadrics = MEM_callocN(sizeof(Quadric) * bm->totvert, __func__);
683         eheap = BLI_heap_new_ex(bm->totedge);
684         eheap_table = MEM_callocN(sizeof(HeapNode *) * bm->totedge, __func__);
685         tot_edge_orig = bm->totedge;
686
687
688         /* build initial edge collapse cost data */
689         bm_decim_build_quadrics(bm, vquadrics);
690
691         bm_decim_build_edge_cost(bm, vquadrics, eheap, eheap_table);
692
693         face_tot_target = bm->totface * factor;
694         bm->elem_index_dirty |= BM_FACE | BM_EDGE | BM_VERT;
695
696
697 #ifdef USE_CUSTOMDATA
698         /* initialize customdata flag, we only need math for loops */
699         if (CustomData_has_interp(&bm->vdata))  customdata_flag |= CD_DO_VERT;
700         if (CustomData_has_interp(&bm->edata))  customdata_flag |= CD_DO_EDGE;
701         if (CustomData_has_math(&bm->ldata))    customdata_flag |= CD_DO_LOOP;
702 #endif
703
704         /* iterative edge collapse and maintain the eheap */
705         while ((bm->totface > face_tot_target) && (BLI_heap_empty(eheap) == FALSE)) {
706                 BMEdge *e = BLI_heap_popmin(eheap);
707                 BLI_assert(BM_elem_index_get(e) < tot_edge_orig);  /* handy to detect corruptions elsewhere */
708
709                 /* under normal conditions wont be accessed again,
710                  * but NULL just incase so we don't use freed node */
711                 eheap_table[BM_elem_index_get(e)] = NULL;
712
713                 bm_decim_edge_collapse(bm, e, vquadrics, eheap, eheap_table, customdata_flag);
714         }
715
716
717 #ifdef USE_TRIANGULATE
718         /* its possible we only had triangles, skip this step in that case */
719         if (LIKELY(use_triangulate)) {
720                 /* temp convert quads to triangles */
721                 bm_decim_triangulate_end(bm);
722         }
723 #endif
724
725         /* free vars */
726         MEM_freeN(vquadrics);
727         MEM_freeN(eheap_table);
728         BLI_heap_free(eheap, NULL);
729
730         /* testing only */
731         // BM_mesh_validate(bm);
732
733         (void)tot_edge_orig;  /* quiet release build warning */
734 }