81edc727ad3b5aa581655e0b80eb13d27d52f43a
[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                                         int offset = bm->ldata.layers[i].offset;
405                                         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         /* first walk around the fan until we hit a seam */
428
429
430
431         /* last, interpolate ourselves */
432
433
434 }
435 #endif  /* USE_CUSTOMDATA */
436
437 /**
438  * special, highly limited edge collapse function
439  * intended for speed over flexibiliy.
440  * can only collapse edges connected to (1, 2) tris.
441  *
442  * Important - dont add vert/edge/face data on collapsing!
443  *
444  * \param e_clear_other let caller know what edges we remove besides \a e_clear
445  * \param customdata_flag merge factor, scales from 0 - 1 ('v_clear' -> 'v_other')
446  */
447 static int bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e_clear_other[2],
448 #ifdef USE_CUSTOMDATA
449                             const CD_UseFlag customdata_flag,
450                             const float customdata_fac
451 #else
452                             const CD_UseFlag UNUSED(customdata_flag),
453                             const float UNUSED(customdata_fac)
454 #endif
455                             )
456 {
457         BMVert *v_other = BM_edge_other_vert(e_clear, v_clear);
458
459         BLI_assert(v_other != NULL);
460
461         if (BM_edge_is_manifold(e_clear)) {
462                 BMLoop *l_a, *l_b;
463                 BMEdge *e_a_other[2], *e_b_other[2];
464                 int ok;
465
466                 ok = BM_edge_loop_pair(e_clear, &l_a, &l_b);
467
468                 BLI_assert(ok == TRUE);
469                 BLI_assert(l_a->f->len == 3);
470                 BLI_assert(l_b->f->len == 3);
471
472                 /* keep 'v_clear' 0th */
473                 if (BM_vert_in_edge(l_a->prev->e, v_clear)) {
474                         e_a_other[0] = l_a->prev->e;
475                         e_a_other[1] = l_a->next->e;
476                 }
477                 else {
478                         e_a_other[1] = l_a->prev->e;
479                         e_a_other[0] = l_a->next->e;
480                 }
481
482                 if (BM_vert_in_edge(l_b->prev->e, v_clear)) {
483                         e_b_other[0] = l_b->prev->e;
484                         e_b_other[1] = l_b->next->e;
485                 }
486                 else {
487                         e_b_other[1] = l_b->prev->e;
488                         e_b_other[0] = l_b->next->e;
489                 }
490
491                 BLI_assert(BM_edge_share_vert(e_a_other[0], e_b_other[0]));
492                 BLI_assert(BM_edge_share_vert(e_a_other[1], e_b_other[1]));
493
494                 /* we could assert this case, but better just bail out */
495 #if 0
496                 BLI_assert(e_a_other[0] != e_b_other[0]);
497                 BLI_assert(e_a_other[0] != e_b_other[1]);
498                 BLI_assert(e_b_other[0] != e_a_other[0]);
499                 BLI_assert(e_b_other[0] != e_a_other[1]);
500 #endif
501                 /* not totally common but we want to avoid */
502                 if (ELEM(e_a_other[0], e_b_other[0], e_b_other[1]) ||
503                     ELEM(e_a_other[1], e_b_other[0], e_b_other[1]))
504                 {
505                         return FALSE;
506                 }
507
508                 r_e_clear_other[0] = BM_elem_index_get(e_a_other[0]);
509                 r_e_clear_other[1] = BM_elem_index_get(e_b_other[0]);
510
511 #ifdef USE_CUSTOMDATA
512                 /* before killing, do customdata */
513                 if (customdata_flag & CD_DO_VERT) {
514                         BM_data_interp_from_verts(bm, v_other, v_clear, v_other, customdata_fac);
515                 }
516                 if (customdata_flag & CD_DO_EDGE) {
517                         BM_data_interp_from_edges(bm, e_a_other[1], e_a_other[0], e_a_other[1], customdata_fac);
518                         BM_data_interp_from_edges(bm, e_b_other[1], e_b_other[0], e_b_other[1], customdata_fac);
519                 }
520                 if (customdata_flag & CD_DO_LOOP) {
521                         bm_edge_collapse_loop_customdata(bm, e_clear->l,              v_clear, v_other, customdata_fac);
522                         bm_edge_collapse_loop_customdata(bm, e_clear->l->radial_next, v_clear, v_other, customdata_fac);
523                 }
524 #endif
525
526                 BM_edge_kill(bm, e_clear);
527
528                 BM_vert_splice(bm, v_clear, v_other);
529
530                 BM_edge_splice(bm, e_a_other[0], e_a_other[1]);
531                 BM_edge_splice(bm, e_b_other[0], e_b_other[1]);
532
533                 // BM_mesh_validate(bm);
534
535                 return TRUE;
536         }
537         else if (BM_edge_is_boundary(e_clear)) {
538                 /* same as above but only one triangle */
539                 BMLoop *l_a;
540                 BMEdge *e_a_other[2];
541
542                 l_a = e_clear->l;
543
544                 BLI_assert(l_a->f->len == 3);
545
546                 /* keep 'v_clear' 0th */
547                 if (BM_vert_in_edge(l_a->prev->e, v_clear)) {
548                         e_a_other[0] = l_a->prev->e;
549                         e_a_other[1] = l_a->next->e;
550                 }
551                 else {
552                         e_a_other[1] = l_a->prev->e;
553                         e_a_other[0] = l_a->next->e;
554                 }
555
556                 r_e_clear_other[0] = BM_elem_index_get(e_a_other[0]);
557                 r_e_clear_other[1] = -1;
558
559 #ifdef USE_CUSTOMDATA
560                 /* before killing, do customdata */
561                 if (customdata_flag & CD_DO_VERT) {
562                         BM_data_interp_from_verts(bm, v_other, v_clear, v_other, customdata_fac);
563                 }
564                 if (customdata_flag & CD_DO_EDGE) {
565                         BM_data_interp_from_edges(bm, e_a_other[1], e_a_other[0], e_a_other[1], customdata_fac);
566                 }
567                 if (customdata_flag & CD_DO_LOOP) {
568                         bm_edge_collapse_loop_customdata(bm, e_clear->l, v_clear, v_other, customdata_fac);
569                 }
570 #endif
571
572                 BM_edge_kill(bm, e_clear);
573
574                 BM_vert_splice(bm, v_clear, v_other);
575
576                 BM_edge_splice(bm, e_a_other[0], e_a_other[1]);
577
578                 // BM_mesh_validate(bm);
579
580                 return TRUE;
581         }
582         else {
583                 return FALSE;
584         }
585 }
586
587
588 /* collapse e the edge, removing e->v2 */
589 static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e,
590                                    Quadric *vquadrics,
591                                    Heap *eheap, HeapNode **eheap_table,
592                                    const CD_UseFlag customdata_flag)
593 {
594         int e_clear_other[2];
595         BMVert *v = e->v1;
596         int v_clear_index = BM_elem_index_get(e->v2);  /* the vert is removed so only store the index */
597         float optimize_co[3];
598         float customdata_fac;
599
600         bm_decim_calc_target_co(e, optimize_co, vquadrics);
601
602         /* use for customdata merging */
603         customdata_fac = line_point_factor_v3(optimize_co, e->v1->co, e->v2->co);
604
605         if (bm_edge_collapse(bm, e, e->v2, e_clear_other, customdata_flag, customdata_fac)) {
606                 /* update collapse info */
607                 int i;
608
609                 e = NULL;  /* paranoid safety check */
610
611                 copy_v3_v3(v->co, optimize_co);
612
613                 /* remove eheap */
614                 for (i = 0; i < 2; i++) {
615                         /* highly unlikely 'eheap_table[ke_other[i]]' would be NULL, but do for sanity sake */
616                         if ((e_clear_other[i] != -1) && (eheap_table[e_clear_other[i]] != NULL)) {
617                                 BLI_heap_remove(eheap, eheap_table[e_clear_other[i]]);
618                                 eheap_table[e_clear_other[i]] = NULL;
619                         }
620                 }
621
622                 /* update vertex quadric, add kept vertex from killed vertex */
623                 BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(v)], &vquadrics[v_clear_index]);
624
625                 /* update connected normals */
626
627                 /* in fact face normals are not used for progressive updates, no need to update them */
628                 // BM_vert_normal_update_all(v);
629                 BM_vert_normal_update(v);
630
631                 /* update error costs and the eheap */
632                 if (LIKELY(v->e)) {
633                         BMEdge *e_iter;
634                         BMEdge *e_first;
635                         e_iter = e_first = v->e;
636                         do {
637                                 //BLI_assert(BM_edge_find_double(e_iter) == NULL);
638 #ifdef USE_SAFETY_CHECKS
639                                 /* note! - this check is slow, but we can't avoid it - Campbell */
640                                 BMEdge *e_double;
641
642                                 e_double = BM_edge_find_double(e_iter);
643
644                                 if (UNLIKELY(e_double != NULL)) {
645                                         int e_index = BM_elem_index_get(e_double);
646                                         if (BM_edge_splice(bm, e_double, e_iter)) {
647                                                 if (eheap_table[e_index]) {
648                                                         BLI_heap_remove(eheap, eheap_table[e_index]);
649                                                         eheap_table[e_index] = NULL;
650                                                 }
651                                         }
652                                 }
653
654                                 /* could get some extra quality out of this but its not really needed */
655                                 // BM_vert_normal_update(BM_edge_other_vert(e_iter, v));
656
657                                 /* if this happens, the e_double check could be put in a while loop,
658                                  * so as to keep removing doubles while they are found. so far this isnt needed */
659                                 BLI_assert(BM_edge_find_double(e_iter) == NULL);
660 #endif
661
662                                 bm_decim_build_edge_cost_single(e_iter, vquadrics, eheap, eheap_table);
663                         } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
664
665                 }
666         }
667 }
668
669
670 /* Main Decimate Function
671  * ********************** */
672
673 void BM_mesh_decimate(BMesh *bm, const float factor)
674 {
675         Heap *eheap;             /* edge heap */
676         HeapNode **eheap_table;  /* edge index aligned table pointing to the eheap */
677         Quadric *vquadrics;      /* vert index aligned quadrics */
678         int tot_edge_orig;
679         int face_tot_target;
680         int use_triangulate;
681
682         CD_UseFlag customdata_flag = 0;
683
684 #ifdef USE_TRIANGULATE
685         /* temp convert quads to triangles */
686         use_triangulate = bm_decim_triangulate_begin(bm);
687 #endif
688
689
690         /* alloc vars */
691         vquadrics = MEM_callocN(sizeof(Quadric) * bm->totvert, __func__);
692         eheap = BLI_heap_new_ex(bm->totedge);
693         eheap_table = MEM_callocN(sizeof(HeapNode *) * bm->totedge, __func__);
694         tot_edge_orig = bm->totedge;
695
696
697         /* build initial edge collapse cost data */
698         bm_decim_build_quadrics(bm, vquadrics);
699
700         bm_decim_build_edge_cost(bm, vquadrics, eheap, eheap_table);
701
702         face_tot_target = bm->totface * factor;
703         bm->elem_index_dirty |= BM_FACE | BM_EDGE | BM_VERT;
704
705
706 #ifdef USE_CUSTOMDATA
707         /* initialize customdata flag, we only need math for loops */
708         if (CustomData_has_interp(&bm->vdata))  customdata_flag |= CD_DO_VERT;
709         if (CustomData_has_interp(&bm->edata))  customdata_flag |= CD_DO_EDGE;
710         if (CustomData_has_math(&bm->ldata))    customdata_flag |= CD_DO_LOOP;
711 #endif
712
713         /* iterative edge collapse and maintain the eheap */
714         while ((bm->totface > face_tot_target) && (BLI_heap_empty(eheap) == FALSE)) {
715                 BMEdge *e = BLI_heap_popmin(eheap);
716                 BLI_assert(BM_elem_index_get(e) < tot_edge_orig);  /* handy to detect corruptions elsewhere */
717
718                 /* under normal conditions wont be accessed again,
719                  * but NULL just incase so we don't use freed node */
720                 eheap_table[BM_elem_index_get(e)] = NULL;
721
722                 bm_decim_edge_collapse(bm, e, vquadrics, eheap, eheap_table, customdata_flag);
723         }
724
725
726 #ifdef USE_TRIANGULATE
727         /* its possible we only had triangles, skip this step in that case */
728         if (LIKELY(use_triangulate)) {
729                 /* temp convert quads to triangles */
730                 bm_decim_triangulate_end(bm);
731         }
732 #endif
733
734         /* free vars */
735         MEM_freeN(vquadrics);
736         MEM_freeN(eheap_table);
737         BLI_heap_free(eheap, NULL);
738
739         /* testing only */
740         // BM_mesh_validate(bm);
741
742         (void)tot_edge_orig;  /* quiet release build warning */
743 }