move decimator into tools/ dir

4 files changed, 1673 insertions, 0 deletions

diff --git a/source/blender/bmesh/tools/bmesh_decimate.h b/source/blender/bmesh/tools/bmesh_decimate.h
new file mode 100644
index 00000000000..04dc0cfd2ea
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_decimate.h
@@ -0,0 +1,41 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Campbell Barton
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_DECIMATE_H__
+#define __BMESH_DECIMATE_H__
+
+/** \file blender/bmesh/intern/bmesh_decimate.h
+ *  \ingroup bmesh
+ */
+
+void BM_mesh_decimate_collapse(BMesh *bm, const float factor, float *vweights, const int do_triangulate);
+
+void BM_mesh_decimate_unsubdivide_ex(BMesh *bm, const int iterations, const int tag_only);
+void BM_mesh_decimate_unsubdivide(BMesh *bm, const int iterations);
+
+void BM_mesh_decimate_dissolve_ex(BMesh *bm, const float angle_limit, const int do_dissolve_boundaries,
+                                  BMVert **vinput_arr, const int vinput_len,
+                                  BMEdge **einput_arr, const int einput_len);
+void BM_mesh_decimate_dissolve(BMesh *bm, const float angle_limit, const int do_dissolve_boundaries);
+
+
+#endif /* __BMESH_DECIMATE_H__ */
diff --git a/source/blender/bmesh/tools/bmesh_decimate_collapse.c b/source/blender/bmesh/tools/bmesh_decimate_collapse.c
new file mode 100644
index 00000000000..c38b9f54a33
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_decimate_collapse.c
@@ -0,0 +1,1045 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Campbell Barton
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/bmesh/intern/bmesh_decimate_collapse.c
+ *  \ingroup bmesh
+ *
+ * BMesh decimator that uses an edge collapse method.
+ */
+
+#include <stddef.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_scene_types.h"
+
+#include "BLI_math.h"
+#include "BLI_quadric.h"
+#include "BLI_heap.h"
+
+#include "BKE_customdata.h"
+
+#include "bmesh.h"
+#include "bmesh_decimate.h"  /* own include */
+
+#include "../intern/bmesh_structure.h"
+
+/* defines for testing */
+#define USE_CUSTOMDATA
+#define USE_TRIANGULATE
+#define USE_VERT_NORMAL_INTERP  /* has the advantage that flipped faces don't mess up vertex normals */
+
+/* these checks are for rare cases that we can't avoid since they are valid meshes still */
+#define USE_SAFETY_CHECKS
+
+#define BOUNDARY_PRESERVE_WEIGHT 100.0f
+#define OPTIMIZE_EPS 0.01f  /* FLT_EPSILON is too small, see [#33106] */
+#define COST_INVALID FLT_MAX
+
+typedef enum CD_UseFlag {
+	CD_DO_VERT = (1 << 0),
+	CD_DO_EDGE = (1 << 1),
+	CD_DO_LOOP = (1 << 2)
+} CD_UseFlag;
+
+
+/* BMesh Helper Functions
+ * ********************** */
+
+/**
+ * \param vquadrics must be calloc'd
+ */
+static void bm_decim_build_quadrics(BMesh *bm, Quadric *vquadrics)
+{
+	BMIter iter;
+	BMFace *f;
+	BMEdge *e;
+
+	BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
+		BMLoop *l_first;
+		BMLoop *l_iter;
+
+		const float *co = BM_FACE_FIRST_LOOP(f)->v->co;
+		const float *no = f->no;
+		const float offset = -dot_v3v3(no, co);
+		Quadric q;
+
+		BLI_quadric_from_v3_dist(&q, no, offset);
+
+		l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+		do {
+			BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(l_iter->v)], &q);
+		} while ((l_iter = l_iter->next) != l_first);
+	}
+
+	/* boundary edges */
+	BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+		if (UNLIKELY(BM_edge_is_boundary(e))) {
+			float edge_vector[3];
+			float edge_cross[3];
+			sub_v3_v3v3(edge_vector, e->v2->co, e->v1->co);
+			f = e->l->f;
+			cross_v3_v3v3(edge_cross, edge_vector, f->no);
+
+			if (normalize_v3(edge_cross) > FLT_EPSILON) {
+				Quadric q;
+				BLI_quadric_from_v3_dist(&q, edge_cross, -dot_v3v3(edge_cross, e->v1->co));
+				BLI_quadric_mul(&q, BOUNDARY_PRESERVE_WEIGHT);
+
+				BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(e->v1)], &q);
+				BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(e->v2)], &q);
+			}
+		}
+	}
+}
+
+
+static void bm_decim_calc_target_co(BMEdge *e, float optimize_co[3],
+                                    const Quadric *vquadrics)
+{
+	/* compute an edge contration target for edge 'e'
+	 * this is computed by summing it's vertices quadrics and
+	 * optimizing the result. */
+	Quadric q;
+
+	BLI_quadric_add_qu_ququ(&q,
+	                        &vquadrics[BM_elem_index_get(e->v1)],
+	                        &vquadrics[BM_elem_index_get(e->v2)]);
+
+
+	if (BLI_quadric_optimize(&q, optimize_co, OPTIMIZE_EPS)) {
+		return;  /* all is good */
+	}
+	else {
+		mid_v3_v3v3(optimize_co, e->v1->co, e->v2->co);
+	}
+}
+
+static int bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_co[3])
+{
+	BMIter liter;
+	BMLoop *l;
+	unsigned int i;
+
+	for (i = 0; i < 2; i++) {
+		/* loop over both verts */
+		BMVert *v = *((&e->v1) + i);
+
+		BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
+			if (l->e != e && l->prev->e != e) {
+				float *co_prev = l->prev->v->co;
+				float *co_next = l->next->v->co;
+				float cross_exist[3];
+				float cross_optim[3];
+
+#if 1
+				float vec_other[3];  /* line between the two outer verts, re-use for both cross products */
+				float vec_exist[3];  /* before collapse */
+				float vec_optim[3];  /* after collapse */
+
+				sub_v3_v3v3(vec_other, co_prev, co_next);
+				sub_v3_v3v3(vec_exist, co_prev, v->co);
+				sub_v3_v3v3(vec_optim, co_prev, optimize_co);
+
+				cross_v3_v3v3(cross_exist, vec_other, vec_exist);
+				cross_v3_v3v3(cross_optim, vec_other, vec_optim);
+
+				/* normalize isn't really needed, but ensures the value at a unit we can compare against */
+				normalize_v3(cross_exist);
+				normalize_v3(cross_optim);
+#else
+				normal_tri_v3(cross_exist, v->co,       co_prev, co_next);
+				normal_tri_v3(cross_optim, optimize_co, co_prev, co_next);
+#endif
+
+				/* use a small value rather then zero so we don't flip a face in multiple steps
+				 * (first making it zero area, then flipping again)*/
+				if (dot_v3v3(cross_exist, cross_optim) <= FLT_EPSILON) {
+					//printf("no flip\n");
+					return TRUE;
+				}
+			}
+		}
+	}
+
+	return FALSE;
+}
+
+static void bm_decim_build_edge_cost_single(BMEdge *e,
+                                            const Quadric *vquadrics, const float *vweights,
+                                            Heap *eheap, HeapNode **eheap_table)
+{
+	const Quadric *q1, *q2;
+	float optimize_co[3];
+	float cost;
+
+	if (eheap_table[BM_elem_index_get(e)]) {
+		BLI_heap_remove(eheap, eheap_table[BM_elem_index_get(e)]);
+	}
+
+	/* check we can collapse, some edges we better not touch */
+	if (BM_edge_is_boundary(e)) {
+		if (e->l->f->len == 3) {
+			/* pass */
+		}
+		else {
+			/* only collapse tri's */
+			eheap_table[BM_elem_index_get(e)] = NULL;
+			return;
+		}
+	}
+	else if (BM_edge_is_manifold(e)) {
+		if ((e->l->f->len == 3) && (e->l->radial_next->f->len == 3)) {
+			/* pass */
+		}
+		else {
+			/* only collapse tri's */
+			eheap_table[BM_elem_index_get(e)] = NULL;
+			return;
+		}
+	}
+	else {
+		eheap_table[BM_elem_index_get(e)] = NULL;
+		return;
+	}
+
+	if (vweights) {
+		if ((vweights[BM_elem_index_get(e->v1)] < FLT_EPSILON) &&
+		    (vweights[BM_elem_index_get(e->v2)] < FLT_EPSILON))
+		{
+			/* skip collapsing this edge */
+			eheap_table[BM_elem_index_get(e)] = NULL;
+			return;
+		}
+	}
+	/* end sanity check */
+
+
+	bm_decim_calc_target_co(e, optimize_co, vquadrics);
+
+	q1 = &vquadrics[BM_elem_index_get(e->v1)];
+	q2 = &vquadrics[BM_elem_index_get(e->v2)];
+
+	if (vweights == NULL) {
+		cost = (BLI_quadric_evaluate(q1, optimize_co) +
+		        BLI_quadric_evaluate(q2, optimize_co));
+	}
+	else {
+		cost = ((BLI_quadric_evaluate(q1, optimize_co) * vweights[BM_elem_index_get(e->v1)]) +
+		        (BLI_quadric_evaluate(q2, optimize_co) * vweights[BM_elem_index_get(e->v2)]));
+	}
+	// print("COST %.12f\n");
+
+	eheap_table[BM_elem_index_get(e)] = BLI_heap_insert(eheap, cost, e);
+}
+
+
+/* use this for degenerate cases - add back to the heap with an invalid cost,
+ * this way it may be calculated again if surrounding geometry changes */
+static void bm_decim_invalid_edge_cost_single(BMEdge *e,
+                                              Heap *eheap, HeapNode **eheap_table)
+{
+	BLI_assert(eheap_table[BM_elem_index_get(e)] == NULL);
+	eheap_table[BM_elem_index_get(e)] = BLI_heap_insert(eheap, COST_INVALID, e);
+}
+
+static void bm_decim_build_edge_cost(BMesh *bm,
+                                     const Quadric *vquadrics, const float *vweights,
+                                     Heap *eheap, HeapNode **eheap_table)
+{
+	BMIter iter;
+	BMEdge *e;
+	unsigned int i;
+
+	BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
+		eheap_table[i] = NULL;  /* keep sanity check happy */
+		bm_decim_build_edge_cost_single(e, vquadrics, vweights, eheap, eheap_table);
+	}
+}
+
+#ifdef USE_TRIANGULATE
+/* Temp Triangulation
+ * ****************** */
+
+/**
+ * To keep things simple we can only collapse edges on triangulated data
+ * (limitation with edge collapse and error calculation functions).
+ *
+ * But to avoid annoying users by only giving triangle results, we can
+ * triangulate, keeping a reference between the faces, then join after
+ * if the edges don't collapse, this will also allow more choices when
+ * collapsing edges so even has some advantage over decimating quads
+ * directly.
+ *
+ * \return TRUE if any faces were triangulated.
+ */
+
+static int bm_decim_triangulate_begin(BMesh *bm)
+{
+	BMIter iter;
+	BMFace *f;
+	// int has_quad;  // could optimize this a little
+	int has_cut = FALSE;
+
+	BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);
+
+	/* first clear loop index values */
+	BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
+		BMLoop *l_iter;
+		BMLoop *l_first;
+
+		l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+		do {
+			BM_elem_index_set(l_iter, -1);
+		} while ((l_iter = l_iter->next) != l_first);
+
+		// has_quad |= (f->len == 4)
+	}
+
+	/* adding new faces as we loop over faces
+	 * is normally best avoided, however in this case its not so bad because any face touched twice
+	 * will already be triangulated*/
+	BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
+		if (f->len == 4) {
+			BMLoop *f_l[4];
+			BMLoop *l_a, *l_b;
+
+			{
+				BMLoop *l_iter = BM_FACE_FIRST_LOOP(f);
+
+				f_l[0] = l_iter; l_iter = l_iter->next;
+				f_l[1] = l_iter; l_iter = l_iter->next;
+				f_l[2] = l_iter; l_iter = l_iter->next;
+				f_l[3] = l_iter;
+			}
+
+			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))
+			{
+				l_a = f_l[0];
+				l_b = f_l[2];
+			}
+			else {
+				l_a = f_l[1];
+				l_b = f_l[3];
+			}
+
+#ifdef USE_SAFETY_CHECKS
+			if (BM_edge_exists(l_a->v, l_b->v) == FALSE)
+#endif
+			{
+				BMFace *f_new;
+				BMLoop *l_new;
+
+				/* warning, NO_DOUBLE option here isn't handled as nice as it could be
+				 * - if there is a quad that has a free standing edge joining it along
+				 * where we want to split the face, there isnt a good way we can handle this.
+				 * currently that edge will get removed when joining the tris back into a quad. */
+				f_new = BM_face_split(bm, f, l_a->v, l_b->v, &l_new, NULL, FALSE);
+
+				if (f_new) {
+					/* the value of this doesn't matter, only that the 2 loops match and have unique values */
+					const int f_index = BM_elem_index_get(f);
+
+					/* since we just split theres only ever 2 loops */
+					BLI_assert(BM_edge_is_manifold(l_new->e));
+
+					BM_elem_index_set(l_new, f_index);
+					BM_elem_index_set(l_new->radial_next, f_index);
+
+					BM_face_normal_update(f);
+					BM_face_normal_update(f_new);
+
+					has_cut = TRUE;
+				}
+			}
+		}
+	}
+
+	BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);
+
+	if (has_cut) {
+		/* now triangulation is done we need to correct index values */
+		BM_mesh_elem_index_ensure(bm, BM_EDGE | BM_FACE);
+	}
+
+	return has_cut;
+}
+
+static void bm_decim_triangulate_end(BMesh *bm)
+{
+	/* decimation finished, now re-join */
+	BMIter iter;
+	BMEdge *e;
+
+	/* boundary edges */
+	BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+		BMLoop *l_a, *l_b;
+		if (BM_edge_loop_pair(e, &l_a, &l_b)) {
+			const int l_a_index = BM_elem_index_get(l_a);
+			if (l_a_index != -1) {
+				const int l_b_index = BM_elem_index_get(l_b);
+				if (l_a_index == l_b_index) {
+					if (LIKELY(l_a->f->len == 3 && l_b->f->len == 3)) {
+						if (l_a->v != l_b->v) {  /* if this is the case, faces have become flipped */
+							/* check we are not making a degenerate quad */
+							BMVert *vquad[4] = {
+								e->v1,
+								BM_vert_in_edge(e, l_a->next->v) ? l_a->prev->v : l_a->next->v,
+								e->v2,
+								BM_vert_in_edge(e, l_b->next->v) ? l_b->prev->v : l_b->next->v,
+							};
+
+							BLI_assert(ELEM3(vquad[0], vquad[1], vquad[2], vquad[3]) == FALSE);
+							BLI_assert(ELEM3(vquad[1], vquad[0], vquad[2], vquad[3]) == FALSE);
+							BLI_assert(ELEM3(vquad[2], vquad[1], vquad[0], vquad[3]) == FALSE);
+							BLI_assert(ELEM3(vquad[3], vquad[1], vquad[2], vquad[0]) == FALSE);
+
+							if (is_quad_convex_v3(vquad[0]->co, vquad[1]->co, vquad[2]->co, vquad[3]->co)) {
+								/* highly unlikely to fail, but prevents possible double-ups */
+								BMFace *f[2] = {l_a->f, l_b->f};
+								BM_faces_join(bm, f, 2, TRUE);
+							}
+						}
+					}
+				}
+			}
+		}
+	}
+}
+
+#endif  /* USE_TRIANGULATE */
+
+/* Edge Collapse Functions
+ * *********************** */
+
+#ifdef USE_CUSTOMDATA
+
+/**
+ * \param v is the target to merge into.
+ */
+static void bm_edge_collapse_loop_customdata(BMesh *bm, BMLoop *l, BMVert *v_clear, BMVert *v_other,
+                                             const float customdata_fac)
+{
+	/* these don't need to be updated, since they will get removed when the edge collapses */
+	BMLoop *l_clear, *l_other;
+	const int is_manifold = BM_edge_is_manifold(l->e);
+	int side;
+
+	/* l defines the vert to collapse into  */
+
+	/* first find the loop of 'v_other' thats attached to the face of 'l' */
+	if (l->v == v_clear) {
+		l_clear = l;
+		l_other = l->next;
+	}
+	else {
+		l_clear = l->next;
+		l_other = l;
+	}
+
+	BLI_assert(l_clear->v == v_clear);
+	BLI_assert(l_other->v == v_other);
+	(void)v_other;  /* quiet warnings for release */
+
+	/* now we have both corners of the face 'l->f' */
+	for (side = 0; side < 2; side++) {
+		int is_seam = FALSE;
+		void *src[2];
+		BMFace *f_exit = is_manifold ? l->radial_next->f : NULL;
+		BMEdge *e_prev = l->e;
+		BMLoop *l_first;
+		BMLoop *l_iter;
+		float w[2];
+
+		if (side == 0) {
+			l_iter = l_first = l_clear;
+			src[0] = l_clear->head.data;
+			src[1] = l_other->head.data;
+
+			w[0] = customdata_fac;
+			w[1] = 1.0f - customdata_fac;
+		}
+		else {
+			l_iter = l_first = l_other;
+			src[0] = l_other->head.data;
+			src[1] = l_clear->head.data;
+
+			w[0] = 1.0f - customdata_fac;
+			w[1] = customdata_fac;
+		}
+
+		// print_v2("weights", w);
+
+		/* WATCH IT! - should NOT reference (_clear or _other) vars for this while loop */
+
+		/* walk around the fan using 'e_prev' */
+		while (((l_iter = BM_vert_step_fan_loop(l_iter, &e_prev)) != l_first) && (l_iter != NULL)) {
+			int i;
+			/* quit once we hit the opposite face, if we have one */
+			if (f_exit && UNLIKELY(f_exit == l_iter->f)) {
+				break;
+			}
+
+			/* break out unless we find a match */
+			is_seam = TRUE;
+
+			/* ok. we have a loop. now be smart with it! */
+			for (i = 0; i < bm->ldata.totlayer; i++) {
+				if (CustomData_layer_has_math(&bm->ldata, i)) {
+					const int offset = bm->ldata.layers[i].offset;
+					const int type = bm->ldata.layers[i].type;
+					void *cd_src, *cd_iter;
+
+					/* todo, make nicer macros for this */
+					cd_src = (char *)src[0] + offset;
+					// cd_dst = (char *)src[1] + offset;  // UNUSED
+					cd_iter  = (char *)l_iter->head.data  + offset;
+
+					/* detect seams */
+					if (CustomData_data_equals(type, cd_src, cd_iter)) {
+						CustomData_bmesh_interp(&bm->ldata, src, w, NULL, 2, l_iter->head.data);
+						is_seam = FALSE;
+					}
+				}
+			}
+
+			if (is_seam) {
+				break;
+			}
+		}
+	}
+}
+#endif  /* USE_CUSTOMDATA */
+
+/**
+ * Check if the collapse will result in a degenerate mesh,
+ * that is - duplicate edges or faces.
+ *
+ * This situation could be checked for when calculating collapse cost
+ * however its quite slow and a degenerate collapse could eventuate
+ * after the cost is calculated, so instead, check just before collapsing.
+ */
+
+static void bm_edge_tag_enable(BMEdge *e)
+{
+	BM_elem_flag_enable(e->v1, BM_ELEM_TAG);
+	BM_elem_flag_enable(e->v2, BM_ELEM_TAG);
+	if (e->l) {
+		BM_elem_flag_enable(e->l->f, BM_ELEM_TAG);
+		if (e->l != e->l->radial_next) {
+			BM_elem_flag_enable(e->l->radial_next->f, BM_ELEM_TAG);
+		}
+	}
+}
+
+static void bm_edge_tag_disable(BMEdge *e)
+{
+	BM_elem_flag_disable(e->v1, BM_ELEM_TAG);
+	BM_elem_flag_disable(e->v2, BM_ELEM_TAG);
+	if (e->l) {
+		BM_elem_flag_disable(e->l->f, BM_ELEM_TAG);
+		if (e->l != e->l->radial_next) {
+			BM_elem_flag_disable(e->l->radial_next->f, BM_ELEM_TAG);
+		}
+	}
+}
+
+static int bm_edge_tag_test(BMEdge *e)
+{
+	/* is the edge or one of its faces tagged? */
+	return (BM_elem_flag_test(e->v1, BM_ELEM_TAG) ||
+	        BM_elem_flag_test(e->v2, BM_ELEM_TAG) ||
+	        (e->l && (BM_elem_flag_test(e->l->f, BM_ELEM_TAG) ||
+	                  (e->l != e->l->radial_next &&
+	                  BM_elem_flag_test(e->l->radial_next->f, BM_ELEM_TAG))))
+	        );
+}
+
+/* takes the edges loop */
+BLI_INLINE int bm_edge_is_manifold_or_boundary(BMLoop *l)
+{
+#if 0
+	/* less optimized version of check below */
+	return (BM_edge_is_manifold(l->e) || BM_edge_is_boundary(l->e);
+#else
+	/* if the edge is a boundary it points to its self, else this must be a manifold */
+	return LIKELY(l) && LIKELY(l->radial_next->radial_next == l);
+#endif
+}
+
+static int bm_edge_collapse_is_degenerate_topology(BMEdge *e_first)
+{
+	/* simply check that there is no overlap between faces and edges of each vert,
+	 * (excluding the 2 faces attached to 'e' and 'e' its self) */
+
+	BMEdge *e_iter;
+
+	/* clear flags on both disks */
+	e_iter = e_first;
+	do {
+		if (!bm_edge_is_manifold_or_boundary(e_iter->l)) {
+			return TRUE;
+		}
+		bm_edge_tag_disable(e_iter);
+	} while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v1)) != e_first);
+
+	e_iter = e_first;
+	do {
+		if (!bm_edge_is_manifold_or_boundary(e_iter->l)) {
+			return TRUE;
+		}
+		bm_edge_tag_disable(e_iter);
+	} while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v2)) != e_first);
+
+	/* now enable one side... */
+	e_iter = e_first;
+	do {
+		bm_edge_tag_enable(e_iter);
+	} while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v1)) != e_first);
+
+	/* ... except for the edge we will collapse, we know thats shared,
+	 * disable this to avoid false positive. We could be smart and never enable these
+	 * face/edge tags in the first place but easier to do this */
+	// bm_edge_tag_disable(e_first);
+	/* do inline... */
+	{
+#if 0
+		BMIter iter;
+		BMIter liter;
+		BMLoop *l;
+		BMVert *v;
+		BM_ITER_ELEM (l, &liter, e_first, BM_LOOPS_OF_EDGE) {
+			BM_elem_flag_disable(l->f, BM_ELEM_TAG);
+			BM_ITER_ELEM (v, &iter, l->f, BM_VERTS_OF_FACE) {
+				BM_elem_flag_disable(v, BM_ELEM_TAG);
+			}
+		}
+#else
+		/* we know each face is a triangle, no looping/iterators needed here */
+
+		BMLoop *l_radial;
+		BMLoop *l_face;
+
+		l_radial = e_first->l;
+		l_face = l_radial;
+		BLI_assert(l_face->f->len == 3);
+		BM_elem_flag_disable(l_face->f, BM_ELEM_TAG);
+		BM_elem_flag_disable((l_face = l_radial)->v,     BM_ELEM_TAG);
+		BM_elem_flag_disable((l_face = l_face->next)->v, BM_ELEM_TAG);
+		BM_elem_flag_disable((         l_face->next)->v, BM_ELEM_TAG);
+		l_face = l_radial->radial_next;
+		if (l_radial != l_face) {
+			BLI_assert(l_face->f->len == 3);
+			BM_elem_flag_disable(l_face->f, BM_ELEM_TAG);
+			BM_elem_flag_disable((l_face = l_radial->radial_next)->v, BM_ELEM_TAG);
+			BM_elem_flag_disable((l_face = l_face->next)->v,          BM_ELEM_TAG);
+			BM_elem_flag_disable((         l_face->next)->v,          BM_ELEM_TAG);
+		}
+#endif
+	}
+
+	/* and check for overlap */
+	e_iter = e_first;
+	do {
+		if (bm_edge_tag_test(e_iter)) {
+			return TRUE;
+		}
+	} while ((e_iter = bmesh_disk_edge_next(e_iter, e_first->v2)) != e_first);
+
+	return FALSE;
+}
+
+/**
+ * special, highly limited edge collapse function
+ * intended for speed over flexibiliy.
+ * can only collapse edges connected to (1, 2) tris.
+ *
+ * Important - dont add vert/edge/face data on collapsing!
+ *
+ * \param e_clear_other let caller know what edges we remove besides \a e_clear
+ * \param customdata_flag merge factor, scales from 0 - 1 ('v_clear' -> 'v_other')
+ */
+static int bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e_clear_other[2],
+#ifdef USE_CUSTOMDATA
+                            const CD_UseFlag customdata_flag,
+                            const float customdata_fac
+#else
+                            const CD_UseFlag UNUSED(customdata_flag),
+                            const float UNUSED(customdata_fac)
+#endif
+                            )
+{
+	BMVert *v_other;
+
+	v_other = BM_edge_other_vert(e_clear, v_clear);
+	BLI_assert(v_other != NULL);
+
+	if (BM_edge_is_manifold(e_clear)) {
+		BMLoop *l_a, *l_b;
+		BMEdge *e_a_other[2], *e_b_other[2];
+		int ok;
+
+		ok = BM_edge_loop_pair(e_clear, &l_a, &l_b);
+
+		BLI_assert(ok == TRUE);
+		BLI_assert(l_a->f->len == 3);
+		BLI_assert(l_b->f->len == 3);
+
+		/* keep 'v_clear' 0th */
+		if (BM_vert_in_edge(l_a->prev->e, v_clear)) {
+			e_a_other[0] = l_a->prev->e;
+			e_a_other[1] = l_a->next->e;
+		}
+		else {
+			e_a_other[1] = l_a->prev->e;
+			e_a_other[0] = l_a->next->e;
+		}
+
+		if (BM_vert_in_edge(l_b->prev->e, v_clear)) {
+			e_b_other[0] = l_b->prev->e;
+			e_b_other[1] = l_b->next->e;
+		}
+		else {
+			e_b_other[1] = l_b->prev->e;
+			e_b_other[0] = l_b->next->e;
+		}
+
+		BLI_assert(BM_edge_share_vert(e_a_other[0], e_b_other[0]));
+		BLI_assert(BM_edge_share_vert(e_a_other[1], e_b_other[1]));
+
+		/* we could assert this case, but better just bail out */
+#if 0
+		BLI_assert(e_a_other[0] != e_b_other[0]);
+		BLI_assert(e_a_other[0] != e_b_other[1]);
+		BLI_assert(e_b_other[0] != e_a_other[0]);
+		BLI_assert(e_b_other[0] != e_a_other[1]);
+#endif
+		/* not totally common but we want to avoid */
+		if (ELEM(e_a_other[0], e_b_other[0], e_b_other[1]) ||
+		    ELEM(e_a_other[1], e_b_other[0], e_b_other[1]))
+		{
+			return FALSE;
+		}
+
+		r_e_clear_other[0] = BM_elem_index_get(e_a_other[0]);
+		r_e_clear_other[1] = BM_elem_index_get(e_b_other[0]);
+
+#ifdef USE_CUSTOMDATA
+		/* before killing, do customdata */
+		if (customdata_flag & CD_DO_VERT) {
+			BM_data_interp_from_verts(bm, v_other, v_clear, v_other, customdata_fac);
+		}
+		if (customdata_flag & CD_DO_EDGE) {
+			BM_data_interp_from_edges(bm, e_a_other[1], e_a_other[0], e_a_other[1], customdata_fac);
+			BM_data_interp_from_edges(bm, e_b_other[1], e_b_other[0], e_b_other[1], customdata_fac);
+		}
+		if (customdata_flag & CD_DO_LOOP) {
+			bm_edge_collapse_loop_customdata(bm, e_clear->l,              v_clear, v_other, customdata_fac);
+			bm_edge_collapse_loop_customdata(bm, e_clear->l->radial_next, v_clear, v_other, customdata_fac);
+		}
+#endif
+
+		BM_edge_kill(bm, e_clear);
+
+		v_other->head.hflag |= v_clear->head.hflag;
+		BM_vert_splice(bm, v_clear, v_other);
+
+		e_a_other[1]->head.hflag |= e_a_other[0]->head.hflag;
+		e_b_other[1]->head.hflag |= e_b_other[0]->head.hflag;
+		BM_edge_splice(bm, e_a_other[0], e_a_other[1]);
+		BM_edge_splice(bm, e_b_other[0], e_b_other[1]);
+
+		// BM_mesh_validate(bm);
+
+		return TRUE;
+	}
+	else if (BM_edge_is_boundary(e_clear)) {
+		/* same as above but only one triangle */
+		BMLoop *l_a;
+		BMEdge *e_a_other[2];
+
+		l_a = e_clear->l;
+
+		BLI_assert(l_a->f->len == 3);
+
+		/* keep 'v_clear' 0th */
+		if (BM_vert_in_edge(l_a->prev->e, v_clear)) {
+			e_a_other[0] = l_a->prev->e;
+			e_a_other[1] = l_a->next->e;
+		}
+		else {
+			e_a_other[1] = l_a->prev->e;
+			e_a_other[0] = l_a->next->e;
+		}
+
+		r_e_clear_other[0] = BM_elem_index_get(e_a_other[0]);
+		r_e_clear_other[1] = -1;
+
+#ifdef USE_CUSTOMDATA
+		/* before killing, do customdata */
+		if (customdata_flag & CD_DO_VERT) {
+			BM_data_interp_from_verts(bm, v_other, v_clear, v_other, customdata_fac);
+		}
+		if (customdata_flag & CD_DO_EDGE) {
+			BM_data_interp_from_edges(bm, e_a_other[1], e_a_other[0], e_a_other[1], customdata_fac);
+		}
+		if (customdata_flag & CD_DO_LOOP) {
+			bm_edge_collapse_loop_customdata(bm, e_clear->l, v_clear, v_other, customdata_fac);
+		}
+#endif
+
+		BM_edge_kill(bm, e_clear);
+
+		v_other->head.hflag |= v_clear->head.hflag;
+		BM_vert_splice(bm, v_clear, v_other);
+
+		e_a_other[1]->head.hflag |= e_a_other[0]->head.hflag;
+		BM_edge_splice(bm, e_a_other[0], e_a_other[1]);
+
+		// BM_mesh_validate(bm);
+
+		return TRUE;
+	}
+	else {
+		return FALSE;
+	}
+}
+
+
+/* collapse e the edge, removing e->v2 */
+static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e,
+                                   Quadric *vquadrics, float *vweights,
+                                   Heap *eheap, HeapNode **eheap_table,
+                                   const CD_UseFlag customdata_flag)
+{
+	int e_clear_other[2];
+	BMVert *v_other = e->v1;
+	int v_clear_index = BM_elem_index_get(e->v2);  /* the vert is removed so only store the index */
+	float optimize_co[3];
+	float customdata_fac;
+
+#ifdef USE_VERT_NORMAL_INTERP
+	float v_clear_no[3];
+	copy_v3_v3(v_clear_no, e->v2->no);
+#endif
+
+	/* disallow collapsing which results in degenerate cases */
+	if (UNLIKELY(bm_edge_collapse_is_degenerate_topology(e))) {
+		bm_decim_invalid_edge_cost_single(e, eheap, eheap_table);  /* add back with a high cost */
+		return;
+	}
+
+	bm_decim_calc_target_co(e, optimize_co, vquadrics);
+
+	/* check if this would result in an overlapping face */
+	if (UNLIKELY(bm_edge_collapse_is_degenerate_flip(e, optimize_co))) {
+		bm_decim_invalid_edge_cost_single(e, eheap, eheap_table);  /* add back with a high cost */
+		return;
+	}
+
+	/* use for customdata merging */
+	if (LIKELY(compare_v3v3(e->v1->co, e->v2->co, FLT_EPSILON) == FALSE)) {
+		customdata_fac = line_point_factor_v3(optimize_co, e->v1->co, e->v2->co);
+#if 0
+		/* simple test for stupid collapse */
+		if (customdata_fac < 0.0 - FLT_EPSILON || customdata_fac > 1.0f + FLT_EPSILON) {
+			return;
+		}
+#endif
+	}
+	else {
+		/* avoid divide by zero */
+		customdata_fac = 0.5f;
+	}
+
+	if (bm_edge_collapse(bm, e, e->v2, e_clear_other, customdata_flag, customdata_fac)) {
+		/* update collapse info */
+		int i;
+
+		if (vweights) {
+			const int fac = CLAMPIS(customdata_fac, 0.0f, 1.0f);
+			vweights[BM_elem_index_get(v_other)] = (vweights[v_clear_index]              * (1.0f - fac)) +
+			                                       (vweights[BM_elem_index_get(v_other)] * fac);
+		}
+
+		e = NULL;  /* paranoid safety check */
+
+		copy_v3_v3(v_other->co, optimize_co);
+
+		/* remove eheap */
+		for (i = 0; i < 2; i++) {
+			/* highly unlikely 'eheap_table[ke_other[i]]' would be NULL, but do for sanity sake */
+			if ((e_clear_other[i] != -1) && (eheap_table[e_clear_other[i]] != NULL)) {
+				BLI_heap_remove(eheap, eheap_table[e_clear_other[i]]);
+				eheap_table[e_clear_other[i]] = NULL;
+			}
+		}
+
+		/* update vertex quadric, add kept vertex from killed vertex */
+		BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(v_other)], &vquadrics[v_clear_index]);
+
+		/* update connected normals */
+
+		/* in fact face normals are not used for progressive updates, no need to update them */
+		// BM_vert_normal_update_all(v);
+#ifdef USE_VERT_NORMAL_INTERP
+		interp_v3_v3v3(v_other->no, v_other->no, v_clear_no, customdata_fac);
+		normalize_v3(v_other->no);
+#else
+		BM_vert_normal_update(v_other);
+#endif
+
+
+		/* update error costs and the eheap */
+		if (LIKELY(v_other->e)) {
+			BMEdge *e_iter;
+			BMEdge *e_first;
+			e_iter = e_first = v_other->e;
+			do {
+				BLI_assert(BM_edge_find_double(e_iter) == NULL);
+				bm_decim_build_edge_cost_single(e_iter, vquadrics, vweights, eheap, eheap_table);
+			} while ((e_iter = bmesh_disk_edge_next(e_iter, v_other)) != e_first);
+		}
+
+		/* this block used to be disabled,
+		 * but enable now since surrounding faces may have been
+		 * set to COST_INVALID because of a face overlap that no longer occurs */
+#if 1
+		/* optional, update edges around the vertex face fan */
+		{
+			BMIter liter;
+			BMLoop *l;
+			BM_ITER_ELEM (l, &liter, v_other, BM_LOOPS_OF_VERT) {
+				if (l->f->len == 3) {
+					BMEdge *e_outer;
+					if (BM_vert_in_edge(l->prev->e, l->v))
+						e_outer = l->next->e;
+					else
+						e_outer = l->prev->e;
+
+					BLI_assert(BM_vert_in_edge(e_outer, l->v) == FALSE);
+
+					bm_decim_build_edge_cost_single(e_outer, vquadrics, vweights, eheap, eheap_table);
+				}
+			}
+		}
+		/* end optional update */
+#endif
+	}
+	else {
+		/* add back with a high cost */
+		bm_decim_invalid_edge_cost_single(e, eheap, eheap_table);
+	}
+}
+
+
+/* Main Decimate Function
+ * ********************** */
+
+/**
+ * \brief BM_mesh_decimate
+ * \param bm The mesh
+ * \param factor face count multiplier [0 - 1]
+ * \param vertex_weights Optional array of vertex  aligned weights [0 - 1],
+ *        a vertex group is the usual source for this.
+ */
+void BM_mesh_decimate_collapse(BMesh *bm, const float factor, float *vweights, const int do_triangulate)
+{
+	Heap *eheap;             /* edge heap */
+	HeapNode **eheap_table;  /* edge index aligned table pointing to the eheap */
+	Quadric *vquadrics;      /* vert index aligned quadrics */
+	int tot_edge_orig;
+	int face_tot_target;
+	int use_triangulate;
+
+	CD_UseFlag customdata_flag = 0;
+
+#ifdef USE_TRIANGULATE
+	/* temp convert quads to triangles */
+	use_triangulate = bm_decim_triangulate_begin(bm);
+#endif
+
+
+	/* alloc vars */
+	vquadrics = MEM_callocN(sizeof(Quadric) * bm->totvert, __func__);
+	/* since some edges may be degenerate, we might be over allocing a little here */
+	eheap = BLI_heap_new_ex(bm->totedge);
+	eheap_table = MEM_callocN(sizeof(HeapNode *) * bm->totedge, __func__);
+	tot_edge_orig = bm->totedge;
+
+
+	/* build initial edge collapse cost data */
+	bm_decim_build_quadrics(bm, vquadrics);
+
+	bm_decim_build_edge_cost(bm, vquadrics, vweights, eheap, eheap_table);
+
+	face_tot_target = bm->totface * factor;
+	bm->elem_index_dirty |= BM_FACE | BM_EDGE | BM_VERT;
+
+
+#ifdef USE_CUSTOMDATA
+	/* initialize customdata flag, we only need math for loops */
+	if (CustomData_has_interp(&bm->vdata))  customdata_flag |= CD_DO_VERT;
+	if (CustomData_has_interp(&bm->edata))  customdata_flag |= CD_DO_EDGE;
+	if (CustomData_has_math(&bm->ldata))    customdata_flag |= CD_DO_LOOP;
+#endif
+
+	/* iterative edge collapse and maintain the eheap */
+	while ((bm->totface > face_tot_target) &&
+	       (BLI_heap_is_empty(eheap) == FALSE) &&
+	       (BLI_heap_node_value(BLI_heap_top(eheap)) != COST_INVALID))
+	{
+		// const float value = BLI_heap_node_value(BLI_heap_top(eheap));
+		BMEdge *e = BLI_heap_popmin(eheap);
+		BLI_assert(BM_elem_index_get(e) < tot_edge_orig);  /* handy to detect corruptions elsewhere */
+
+		// printf("COST %.10f\n", value);
+
+		/* under normal conditions wont be accessed again,
+		 * but NULL just incase so we don't use freed node */
+		eheap_table[BM_elem_index_get(e)] = NULL;
+
+		bm_decim_edge_collapse(bm, e, vquadrics, vweights, eheap, eheap_table, customdata_flag);
+	}
+
+
+#ifdef USE_TRIANGULATE
+	if (do_triangulate == FALSE) {
+		/* its possible we only had triangles, skip this step in that case */
+		if (LIKELY(use_triangulate)) {
+			/* temp convert quads to triangles */
+			bm_decim_triangulate_end(bm);
+		}
+	}
+#endif
+
+	/* free vars */
+	MEM_freeN(vquadrics);
+	MEM_freeN(eheap_table);
+	BLI_heap_free(eheap, NULL);
+
+	/* testing only */
+	// BM_mesh_validate(bm);
+
+	(void)tot_edge_orig;  /* quiet release build warning */
+}
diff --git a/source/blender/bmesh/tools/bmesh_decimate_dissolve.c b/source/blender/bmesh/tools/bmesh_decimate_dissolve.c
new file mode 100644
index 00000000000..fb78050988d
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_decimate_dissolve.c
@@ -0,0 +1,243 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Campbell Barton
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/bmesh/intern/bmesh_decimate_dissolve.c
+ *  \ingroup bmesh
+ *
+ * BMesh decimator that dissolves flat areas into polygons (ngons).
+ */
+
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_math.h"
+
+#include "bmesh.h"
+#include "bmesh_decimate.h"  /* own include */
+
+#define UNIT_TO_ANGLE DEG2RADF(90.0f)
+#define ANGLE_TO_UNIT (1.0f / UNIT_TO_ANGLE)
+
+/* multiply vertex edge angle by face angle
+ * this means we are not left with sharp corners between _almost_ planer faces
+ * convert angles [0-PI/2] -> [0-1], multiply together, then convert back to radians. */
+static float bm_vert_edge_face_angle(BMVert *v)
+{
+	const float angle = BM_vert_calc_edge_angle(v);
+	/* note: could be either edge, it doesn't matter */
+	if (v->e && BM_edge_is_manifold(v->e)) {
+		return ((angle * ANGLE_TO_UNIT) * (BM_edge_calc_face_angle(v->e) * ANGLE_TO_UNIT)) * UNIT_TO_ANGLE;
+	}
+	else {
+		return angle;
+	}
+}
+
+#undef UNIT_TO_ANGLE
+#undef ANGLE_TO_UNIT
+
+typedef struct DissolveElemWeight {
+	BMHeader *ele;
+	float weight;
+} DissolveElemWeight;
+
+static int dissolve_elem_cmp(const void *a1, const void *a2)
+{
+	const struct DissolveElemWeight *d1 = a1, *d2 = a2;
+
+	if      (d1->weight > d2->weight) return  1;
+	else if (d1->weight < d2->weight) return -1;
+	return 0;
+}
+
+/**
+ * \param do_all_verts Collapse all verts between 2 faces - don't check their edge angle.
+ */
+void BM_mesh_decimate_dissolve_ex(BMesh *bm, const float angle_limit, const int do_dissolve_boundaries,
+                                  BMVert **vinput_arr, const int vinput_len,
+                                  BMEdge **einput_arr, const int einput_len)
+{
+	const float angle_max = (float)M_PI / 2.0f;
+	DissolveElemWeight *weight_elems = MEM_mallocN(max_ii(einput_len, vinput_len) *
+	                                               sizeof(DissolveElemWeight), __func__);
+	int i, tot_found;
+
+	BMIter iter;
+	BMEdge *e_iter;
+	BMEdge **earray;
+
+	int *vert_reverse_lookup;
+
+	/* --- first edges --- */
+
+	/* wire -> tag */
+	BM_ITER_MESH (e_iter, &iter, bm, BM_EDGES_OF_MESH) {
+		BM_elem_flag_set(e_iter, BM_ELEM_TAG, BM_edge_is_wire(e_iter));
+	}
+
+	/* go through and split edge */
+	for (i = 0, tot_found = 0; i < einput_len; i++) {
+		BMEdge *e = einput_arr[i];
+		const float angle = BM_edge_calc_face_angle(e);
+
+		if (angle < angle_limit) {
+			tot_found++;
+		}
+		weight_elems[i].ele = (BMHeader *)e;
+		weight_elems[i].weight = angle;
+	}
+
+	if (tot_found != 0) {
+		qsort(weight_elems, einput_len, sizeof(DissolveElemWeight), dissolve_elem_cmp);
+
+		for (i = 0; i < tot_found; i++) {
+			BMEdge *e = (BMEdge *)weight_elems[i].ele;
+
+			if (/* may have become non-manifold */
+			    BM_edge_is_manifold(e) &&
+			    /* check twice because cumulative effect could dissolve over angle limit */
+			    (BM_edge_calc_face_angle(e) < angle_limit))
+			{
+				BMFace *nf = BM_faces_join_pair(bm, e->l->f,
+				                                e->l->radial_next->f,
+				                                e,
+				                                FALSE); /* join faces */
+
+				/* there may be some errors, we don't mind, just move on */
+				if (nf) {
+					BM_face_normal_update(nf);
+				}
+				else {
+					BMO_error_clear(bm);
+				}
+			}
+		}
+	}
+
+	/* prepare for cleanup */
+	BM_mesh_elem_index_ensure(bm, BM_VERT);
+	vert_reverse_lookup = MEM_mallocN(sizeof(int) * bm->totvert, __func__);
+	fill_vn_i(vert_reverse_lookup, bm->totvert, -1);
+	for (i = 0, tot_found = 0; i < vinput_len; i++) {
+		BMVert *v = vinput_arr[i];
+		vert_reverse_lookup[BM_elem_index_get(v)] = i;
+	}
+
+	/* --- cleanup --- */
+	earray = MEM_mallocN(sizeof(BMEdge *) * bm->totedge, __func__);
+	BM_ITER_MESH_INDEX (e_iter, &iter, bm, BM_EDGES_OF_MESH, i) {
+		earray[i] = e_iter;
+	}
+	/* remove all edges/verts left behind from dissolving, NULL'ing the vertex array so we dont re-use */
+	for (i = bm->totedge - 1; i != -1; i--) {
+		e_iter = earray[i];
+
+		if (BM_edge_is_wire(e_iter) && (BM_elem_flag_test(e_iter, BM_ELEM_TAG) == FALSE)) {
+			/* edge has become wire */
+			int vidx_reverse;
+			BMVert *v1 = e_iter->v1;
+			BMVert *v2 = e_iter->v2;
+			BM_edge_kill(bm, e_iter);
+			if (v1->e == NULL) {
+				vidx_reverse = vert_reverse_lookup[BM_elem_index_get(v1)];
+				if (vidx_reverse != -1) vinput_arr[vidx_reverse] = NULL;
+				BM_vert_kill(bm, v1);
+			}
+			if (v2->e == NULL) {
+				vidx_reverse = vert_reverse_lookup[BM_elem_index_get(v2)];
+				if (vidx_reverse != -1) vinput_arr[vidx_reverse] = NULL;
+				BM_vert_kill(bm, v2);
+			}
+		}
+	}
+	MEM_freeN(vert_reverse_lookup);
+
+	MEM_freeN(earray);
+
+
+	/* --- second verts --- */
+	if (do_dissolve_boundaries) {
+		/* simple version of the branch below, sincve we will dissolve _all_ verts that use 2 edges */
+		for (i = 0; i < vinput_len; i++) {
+			BMVert *v = vinput_arr[i];
+			if (LIKELY(v != NULL) &&
+			    BM_vert_edge_count(v) == 2)
+			{
+				BM_vert_collapse_edge(bm, v->e, v, TRUE); /* join edges */
+			}
+		}
+	}
+	else {
+		for (i = 0, tot_found = 0; i < vinput_len; i++) {
+			BMVert *v = vinput_arr[i];
+			const float angle = v ? bm_vert_edge_face_angle(v) : angle_limit;
+
+			if (angle < angle_limit) {
+				weight_elems[i].ele = (BMHeader *)v;
+				weight_elems[i].weight = angle;
+				tot_found++;
+			}
+			else {
+				weight_elems[i].ele = NULL;
+				weight_elems[i].weight = angle_max;
+			}
+		}
+
+		if (tot_found != 0) {
+			qsort(weight_elems, vinput_len, sizeof(DissolveElemWeight), dissolve_elem_cmp);
+
+			for (i = 0; i < tot_found; i++) {
+				BMVert *v = (BMVert *)weight_elems[i].ele;
+				if (LIKELY(v != NULL) &&
+				    /* topology changes may cause this to be un-collapsable */
+				    (BM_vert_edge_count(v) == 2) &&
+				    /* check twice because cumulative effect could dissolve over angle limit */
+				    bm_vert_edge_face_angle(v) < angle_limit)
+				{
+					BMEdge *ne = BM_vert_collapse_edge(bm, v->e, v, TRUE); /* join edges */
+
+					if (ne && ne->l) {
+						BM_edge_normals_update(ne);
+					}
+				}
+			}
+		}
+	}
+
+	MEM_freeN(weight_elems);
+}
+
+void BM_mesh_decimate_dissolve(BMesh *bm, const float angle_limit, const int do_dissolve_boundaries)
+{
+	int vinput_len;
+	int einput_len;
+
+	BMVert **vinput_arr = BM_iter_as_arrayN(bm, BM_VERTS_OF_MESH, NULL, &vinput_len, NULL, 0);
+	BMEdge **einput_arr = BM_iter_as_arrayN(bm, BM_EDGES_OF_MESH, NULL, &einput_len, NULL, 0);
+
+	BM_mesh_decimate_dissolve_ex(bm, angle_limit, do_dissolve_boundaries,
+	                             vinput_arr, vinput_len,
+	                             einput_arr, einput_len);
+
+	MEM_freeN(vinput_arr);
+	MEM_freeN(einput_arr);
+}
diff --git a/source/blender/bmesh/tools/bmesh_decimate_unsubdivide.c b/source/blender/bmesh/tools/bmesh_decimate_unsubdivide.c
new file mode 100644
index 00000000000..1ec13010d80
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_decimate_unsubdivide.c
@@ -0,0 +1,344 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Campbell Barton
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/bmesh/intern/bmesh_decimate_unsubdivide.c
+ *  \ingroup bmesh
+ *
+ * BMesh decimator that uses a grid un-subdivide method.
+ */
+
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_math.h"
+
+#include "bmesh.h"
+
+#include "intern/bmesh_operators_private.h" /* own include */
+
+
+static int bm_vert_dissolve_fan_test(BMVert *v)
+{
+	/* check if we should walk over these verts */
+	BMIter iter;
+	BMEdge *e;
+
+	unsigned int tot_edge = 0;
+	unsigned int tot_edge_boundary = 0;
+	unsigned int tot_edge_manifold = 0;
+	unsigned int tot_edge_wire     = 0;
+
+	BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
+		if (BM_edge_is_boundary(e)) {
+			tot_edge_boundary++;
+		}
+		else if (BM_edge_is_manifold(e)) {
+			tot_edge_manifold++;
+		}
+		else if (BM_edge_is_wire(e)) {
+			tot_edge_wire++;
+		}
+		tot_edge++;
+	}
+
+	if ((tot_edge == 4) && (tot_edge_boundary == 0) && (tot_edge_manifold == 4)) {
+		return TRUE;
+	}
+	else if ((tot_edge == 3) && (tot_edge_boundary == 0) && (tot_edge_manifold == 3)) {
+		return TRUE;
+	}
+	else if ((tot_edge == 3) && (tot_edge_boundary == 2) && (tot_edge_manifold == 1)) {
+		return TRUE;
+	}
+	else if ((tot_edge == 2) && (tot_edge_wire == 2)) {
+		return TRUE;
+	}
+	return FALSE;
+}
+
+static int bm_vert_dissolve_fan(BMesh *bm, BMVert *v)
+{
+	/* collapse under 2 conditions.
+	 * - vert connects to 4 manifold edges (and 4 faces).
+	 * - vert connecrs to 1 manifold edge, 2 boundary edges (and 2 faces).
+	 *
+	 * This covers boundary verts of a quad grid and center verts.
+	 * note that surrounding faces dont have to be quads.
+	 */
+
+	BMIter iter;
+	BMEdge *e;
+
+	unsigned int tot_loop = 0;
+	unsigned int tot_edge = 0;
+	unsigned int tot_edge_boundary = 0;
+	unsigned int tot_edge_manifold = 0;
+	unsigned int tot_edge_wire     = 0;
+
+	BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
+		if (BM_edge_is_boundary(e)) {
+			tot_edge_boundary++;
+		}
+		else if (BM_edge_is_manifold(e)) {
+			tot_edge_manifold++;
+		}
+		else if (BM_edge_is_wire(e)) {
+			tot_edge_wire++;
+		}
+		tot_edge++;
+	}
+
+	if (tot_edge == 2) {
+		/* check for 2 wire verts only */
+		if (tot_edge_wire == 2) {
+			return (BM_vert_collapse_edge(bm, v->e, v, TRUE) != NULL);
+		}
+	}
+	else if (tot_edge == 4) {
+		/* check for 4 faces surrounding */
+		if (tot_edge_boundary == 0 && tot_edge_manifold == 4) {
+			/* good to go! */
+			tot_loop = 4;
+		}
+	}
+	else if (tot_edge == 3) {
+		/* check for 2 faces surrounding at a boundary */
+		if (tot_edge_boundary == 2 && tot_edge_manifold == 1) {
+			/* good to go! */
+			tot_loop = 2;
+		}
+		else if (tot_edge_boundary == 0 && tot_edge_manifold == 3) {
+			/* good to go! */
+			tot_loop = 3;
+		}
+	}
+
+	if (tot_loop) {
+		BMLoop *f_loop[4];
+		unsigned int i;
+
+		/* ensure there are exactly tot_loop loops */
+		BLI_assert(BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v, tot_loop) == NULL);
+		BM_iter_as_array(bm, BM_LOOPS_OF_VERT, v, (void **)f_loop, tot_loop);
+
+		for (i = 0; i < tot_loop; i++) {
+			BMLoop *l = f_loop[i];
+			if (l->f->len > 3) {
+				BMLoop *l_new;
+				BLI_assert(l->prev->v != l->next->v);
+				BM_face_split(bm, l->f, l->prev->v, l->next->v, &l_new, NULL, TRUE);
+				BM_elem_flag_merge_into(l_new->e, l->e, l->prev->e);
+			}
+		}
+
+		return BM_vert_dissolve(bm, v);
+	}
+
+	return FALSE;
+}
+
+enum {
+	VERT_INDEX_DO_COLLAPSE  = -1,
+	VERT_INDEX_INIT         =  0,
+	VERT_INDEX_IGNORE       =  1
+};
+
+// #define USE_WALKER  /* gives uneven results, disable for now */
+
+/* - BMVert.flag & BM_ELEM_TAG:  shows we touched this vert
+ * - BMVert.index == -1:         shows we will remove this vert
+ */
+
+/**
+ * \param tag_only so we can call this from an operator */
+void BM_mesh_decimate_unsubdivide_ex(BMesh *bm, const int iterations, const int tag_only)
+{
+#ifdef USE_WALKER
+#  define ELE_VERT_TAG 1
+#else
+	BMVert **vert_seek_a = MEM_mallocN(sizeof(BMVert *) * bm->totvert, __func__);
+	BMVert **vert_seek_b = MEM_mallocN(sizeof(BMVert *) * bm->totvert, __func__);
+	unsigned vert_seek_a_tot = 0;
+	unsigned vert_seek_b_tot = 0;
+#endif
+
+	BMVert *v;
+	BMIter iter;
+
+	const unsigned int offset = 0;
+	const unsigned int nth = 2;
+
+	int iter_step;
+
+	/* if tag_only is set, we assyme the caller knows what verts to tag
+	 * needed for the operator */
+	if (tag_only == FALSE) {
+		BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
+			BM_elem_flag_enable(v, BM_ELEM_TAG);
+		}
+	}
+
+	for (iter_step = 0; iter_step < iterations; iter_step++) {
+		int iter_done;
+
+		BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
+			if (BM_elem_flag_test(v, BM_ELEM_TAG) && bm_vert_dissolve_fan_test(v)) {
+#ifdef USE_WALKER
+				BMO_elem_flag_enable(bm, v, ELE_VERT_TAG);
+#endif
+				BM_elem_index_set(v, VERT_INDEX_INIT);  /* set_dirty! */
+			}
+			else {
+				BM_elem_index_set(v, VERT_INDEX_IGNORE);  /* set_dirty! */
+			}
+		}
+		/* done with selecting tagged verts */
+
+
+		/* main loop, keep tagging until we can't tag any more islands */
+		while (TRUE) {
+#ifdef USE_WALKER
+			BMWalker walker;
+#else
+			unsigned int depth = 1;
+			unsigned int i;
+#endif
+			BMVert *v_first = NULL;
+			BMVert *v;
+
+			/* we could avoid iterating from the start each time */
+			BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
+				if (v->e && (BM_elem_index_get(v) == VERT_INDEX_INIT)) {
+#ifdef USE_WALKER
+					if (BMO_elem_flag_test(bm, v, ELE_VERT_TAG))
+#endif
+					{
+						/* check again incase the topology changed */
+						if (bm_vert_dissolve_fan_test(v)) {
+							v_first = v;
+						}
+						break;
+					}
+				}
+			}
+			if (v_first == NULL) {
+				break;
+			}
+
+#ifdef USE_WALKER
+			/* Walk over selected elements starting at active */
+			BMW_init(&walker, bm, BMW_CONNECTED_VERTEX,
+			         ELE_VERT_TAG, BMW_MASK_NOP, BMW_MASK_NOP,
+			         BMW_FLAG_NOP, /* don't use BMW_FLAG_TEST_HIDDEN here since we want to desel all */
+			         BMW_NIL_LAY);
+
+			BLI_assert(walker.order == BMW_BREADTH_FIRST);
+			for (v = BMW_begin(&walker, v_first); v != NULL; v = BMW_step(&walker)) {
+				/* Deselect elements that aren't at "nth" depth from active */
+				if (BM_elem_index_get(v) == VERT_INDEX_INIT) {
+					if ((offset + BMW_current_depth(&walker)) % nth) {
+						/* tag for removal */
+						BM_elem_index_set(v, VERT_INDEX_DO_COLLAPSE);  /* set_dirty! */
+					}
+					else {
+						/* works better to allow these verts to be checked again */
+						//BM_elem_index_set(v, VERT_INDEX_IGNORE);  /* set_dirty! */
+					}
+				}
+			}
+			BMW_end(&walker);
+#else
+
+			BM_elem_index_set(v_first, (offset + depth) % nth ? VERT_INDEX_IGNORE : VERT_INDEX_DO_COLLAPSE);  /* set_dirty! */
+
+			vert_seek_b_tot = 0;
+			vert_seek_b[vert_seek_b_tot++] = v_first;
+
+			while (TRUE) {
+				BMEdge *e;
+
+				if ((offset + depth) % nth) {
+					vert_seek_a_tot = 0;
+					for (i = 0; i < vert_seek_b_tot; i++) {
+						v = vert_seek_b[i];
+						BLI_assert(BM_elem_index_get(v) == VERT_INDEX_IGNORE);
+						BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
+							BMVert *v_other = BM_edge_other_vert(e, v);
+							if (BM_elem_index_get(v_other) == VERT_INDEX_INIT) {
+								BM_elem_index_set(v_other, VERT_INDEX_DO_COLLAPSE);  /* set_dirty! */
+								vert_seek_a[vert_seek_a_tot++] = v_other;
+							}
+						}
+					}
+					if (vert_seek_a_tot == 0) {
+						break;
+					}
+				}
+				else {
+					vert_seek_b_tot = 0;
+					for (i = 0; i < vert_seek_a_tot; i++) {
+						v = vert_seek_a[i];
+						BLI_assert(BM_elem_index_get(v) == VERT_INDEX_DO_COLLAPSE);
+						BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
+							BMVert *v_other = BM_edge_other_vert(e, v);
+							if (BM_elem_index_get(v_other) == VERT_INDEX_INIT) {
+								BM_elem_index_set(v_other, VERT_INDEX_IGNORE);  /* set_dirty! */
+								vert_seek_b[vert_seek_b_tot++] = v_other;
+							}
+						}
+					}
+					if (vert_seek_b_tot == 0) {
+						break;
+					}
+				}
+
+				depth++;
+			}
+#endif  /* USE_WALKER */
+
+		}
+
+		/* now we tagged all verts -1 for removal, lets loop over and rebuild faces */
+		iter_done = FALSE;
+		BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
+			if (BM_elem_index_get(v) == VERT_INDEX_DO_COLLAPSE) {
+				iter_done |= bm_vert_dissolve_fan(bm, v);
+			}
+		}
+
+		if (iter_done == FALSE) {
+			break;
+		}
+	}
+
+	bm->elem_index_dirty |= BM_VERT;
+
+#ifndef USE_WALKER
+	MEM_freeN(vert_seek_a);
+	MEM_freeN(vert_seek_b);
+#endif
+}
+
+void BM_mesh_decimate_unsubdivide(BMesh *bm, const int iterations)
+{
+	BM_mesh_decimate_unsubdivide_ex(bm, iterations, FALSE);
+}