bmesh decimator support for loop & edge customdata. (most importantly UVs and vertex colors).

4 files changed, 217 insertions, 43 deletions

diff --git a/source/blender/blenkernel/BKE_customdata.h b/source/blender/blenkernel/BKE_customdata.h
index 33361b9921c..883850d8dac 100644
--- a/source/blender/blenkernel/BKE_customdata.h
+++ b/source/blender/blenkernel/BKE_customdata.h
@@ -81,6 +81,11 @@ void customData_mask_layers__print(CustomDataMask mask);
  */
 int CustomData_layer_has_math(struct CustomData *data, int layer_n);
 
+/**
+ * Checks if any of the customdata layers has math.
+ */
+int CustomData_has_math(struct CustomData *data);
+
 /* copies the "value" (e.g. mloopuv uv or mloopcol colors) from one block to
  * another, while not overwriting anything else (e.g. flags).  probably only
  * implemented for mloopuv/mloopcol, for now.*/
@@ -205,8 +210,8 @@ void CustomData_free_elem(struct CustomData *data, int index, int count);
 void CustomData_interp(const struct CustomData *source, struct CustomData *dest,
                        int *src_indices, float *weights, float *sub_weights,
                        int count, int dest_index);
-void CustomData_bmesh_interp(struct CustomData *data, void **src_blocks, 
-                             float *weights, float *sub_weights, int count,
+void CustomData_bmesh_interp(struct CustomData *data, void **src_blocks,
+                             const float *weights, const float *sub_weights, int count,
                              void *dest_block);
 
 
diff --git a/source/blender/blenkernel/intern/customdata.c b/source/blender/blenkernel/intern/customdata.c
index 423bd93c70f..6c9cf510405 100644
--- a/source/blender/blenkernel/intern/customdata.c
+++ b/source/blender/blenkernel/intern/customdata.c
@@ -2477,10 +2477,24 @@ int CustomData_layer_has_math(struct CustomData *data, int layer_n)
 	if (typeInfo->equal && typeInfo->add && typeInfo->multiply && 
 	    typeInfo->initminmax && typeInfo->dominmax)
 	{
-		return 1;
+		return TRUE;
 	}
 	
-	return 0;
+	return FALSE;
+}
+
+int CustomData_has_math(struct CustomData *data)
+{
+	int i;
+
+	/* interpolates a layer at a time */
+	for (i = 0; i < data->totlayer; ++i) {
+		if (CustomData_layer_has_math(data, i)) {
+			return TRUE;
+		}
+	}
+
+	return FALSE;
 }
 
 /* copies the "value" (e.g. mloopuv uv or mloopcol colors) from one block to
@@ -2580,8 +2594,8 @@ void CustomData_bmesh_set_layer_n(CustomData *data, void *block, int n, void *so
 		memcpy(dest, source, typeInfo->size);
 }
 
-void CustomData_bmesh_interp(CustomData *data, void **src_blocks, float *weights,
-                             float *sub_weights, int count, void *dest_block)
+void CustomData_bmesh_interp(CustomData *data, void **src_blocks, const float *weights,
+                             const float *sub_weights, int count, void *dest_block)
 {
 	int i, j;
 	void *source_buf[SOURCE_BUF_SIZE];
diff --git a/source/blender/bmesh/intern/bmesh_decimate.c b/source/blender/bmesh/intern/bmesh_decimate.c
index 519bdba02a9..2b513f02d6b 100644
--- a/source/blender/bmesh/intern/bmesh_decimate.c
+++ b/source/blender/bmesh/intern/bmesh_decimate.c
@@ -36,6 +36,8 @@
 #include "BLI_quadric.h"
 #include "BLI_heap.h"
 
+#include "BKE_customdata.h"
+
 #include "bmesh.h"
 #include "bmesh_structure.h"
 #include "bmesh_decimate.h"
@@ -49,6 +51,12 @@
 
 #define BOUNDARY_PRESERVE_WEIGHT 100.0f
 
+typedef enum CD_UseFlag {
+	CD_DO_VERT,
+	CD_DO_EDGE,  /* not used yet */
+	CD_DO_LOOP
+} CD_UseFlag;
+
 
 /* BMesh Helper Functions
  * ********************** */
@@ -322,6 +330,109 @@ static void bm_decim_triangulate_end(BMesh *bm)
 /* 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);
+
+	/* 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;
+		}
+
+		/* 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)) {
+					int offset = bm->ldata.layers[i].offset;
+					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;
+			}
+		}
+	}
+
+	/* first walk around the fan until we hit a seam */
+
+
+
+	/* last, interpolate ourselves */
+
+
+}
+#endif  /* USE_CUSTOMDATA */
+
 /**
  * special, highly limited edge collapse function
  * intended for speed over flexibiliy.
@@ -329,33 +440,36 @@ static void bm_decim_triangulate_end(BMesh *bm)
  *
  * Important - dont add vert/edge/face data on collapsing!
  *
- * \param ke_other let caller know what edges we remove besides \a ke
+ * \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 *ke, BMVert *kv, int ke_other[2],
+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 = BM_edge_other_vert(ke, kv);
+	BMVert *v_other = BM_edge_other_vert(e_clear, v_clear);
 
 	BLI_assert(v_other != NULL);
 
-	if (BM_edge_is_manifold(ke)) {
+	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(ke, &l_a, &l_b);
+		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 'kv' 0th */
-		if (BM_vert_in_edge(l_a->prev->e, kv)) {
+		/* 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;
 		}
@@ -364,7 +478,7 @@ static int bm_edge_collapse(BMesh *bm, BMEdge *ke, BMVert *kv, int ke_other[2],
 			e_a_other[0] = l_a->next->e;
 		}
 
-		if (BM_vert_in_edge(l_b->prev->e, kv)) {
+		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;
 		}
@@ -390,20 +504,27 @@ static int bm_edge_collapse(BMesh *bm, BMEdge *ke, BMVert *kv, int ke_other[2],
 			return FALSE;
 		}
 
-		ke_other[0] = BM_elem_index_get(e_a_other[0]);
-		ke_other[1] = BM_elem_index_get(e_b_other[0]);
+		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
-		/* TODO, loops */
-		// const float w[2] = {customdata_fac, 1.0f - customdata_fac};
-
 		/* before killing, do customdata */
-		BM_data_interp_from_verts(bm, v_other, kv, v_other, customdata_fac);
+		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, ke);
+		BM_edge_kill(bm, e_clear);
 
-		BM_vert_splice(bm, kv, v_other);
+		BM_vert_splice(bm, v_clear, v_other);
 
 		BM_edge_splice(bm, e_a_other[0], e_a_other[1]);
 		BM_edge_splice(bm, e_b_other[0], e_b_other[1]);
@@ -412,17 +533,17 @@ static int bm_edge_collapse(BMesh *bm, BMEdge *ke, BMVert *kv, int ke_other[2],
 
 		return TRUE;
 	}
-	else if (BM_edge_is_boundary(ke)) {
+	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 = ke->l;
+		l_a = e_clear->l;
 
 		BLI_assert(l_a->f->len == 3);
 
-		/* keep 'kv' 0th */
-		if (BM_vert_in_edge(l_a->prev->e, kv)) {
+		/* 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;
 		}
@@ -431,20 +552,25 @@ static int bm_edge_collapse(BMesh *bm, BMEdge *ke, BMVert *kv, int ke_other[2],
 			e_a_other[0] = l_a->next->e;
 		}
 
-		ke_other[0] = BM_elem_index_get(e_a_other[0]);
-		ke_other[1] = -1;
+		r_e_clear_other[0] = BM_elem_index_get(e_a_other[0]);
+		r_e_clear_other[1] = -1;
 
 #ifdef USE_CUSTOMDATA
-		/* TODO, loops */
-		// const float w[2] = {customdata_fac, 1.0f - customdata_fac};
-
 		/* before killing, do customdata */
-		BM_data_interp_from_verts(bm, v_other, kv, v_other, customdata_fac);
+		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, ke);
+		BM_edge_kill(bm, e_clear);
 
-		BM_vert_splice(bm, kv, v_other);
+		BM_vert_splice(bm, v_clear, v_other);
 
 		BM_edge_splice(bm, e_a_other[0], e_a_other[1]);
 
@@ -461,11 +587,12 @@ static int bm_edge_collapse(BMesh *bm, BMEdge *ke, BMVert *kv, int ke_other[2],
 /* collapse e the edge, removing e->v2 */
 static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e,
                                    Quadric *vquadrics,
-                                   Heap *eheap, HeapNode **eheap_table)
+                                   Heap *eheap, HeapNode **eheap_table,
+                                   const CD_UseFlag customdata_flag)
 {
-	int ke_other[2];
+	int e_clear_other[2];
 	BMVert *v = e->v1;
-	int kv_index = BM_elem_index_get(e->v2);  /* the vert is removed so only store the index */
+	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;
 
@@ -474,7 +601,7 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e,
 	/* use for customdata merging */
 	customdata_fac = line_point_factor_v3(optimize_co, e->v1->co, e->v2->co);
 
-	if (bm_edge_collapse(bm, e, e->v2, ke_other, customdata_fac)) {
+	if (bm_edge_collapse(bm, e, e->v2, e_clear_other, customdata_flag, customdata_fac)) {
 		/* update collapse info */
 		int i;
 
@@ -485,14 +612,14 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e,
 		/* remove eheap */
 		for (i = 0; i < 2; i++) {
 			/* highly unlikely 'eheap_table[ke_other[i]]' would be NULL, but do for sanity sake */
-			if ((ke_other[i] != -1) && (eheap_table[ke_other[i]] != NULL)) {
-				BLI_heap_remove(eheap, eheap_table[ke_other[i]]);
-				eheap_table[ke_other[i]] = NULL;
+			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)], &vquadrics[kv_index]);
+		BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(v)], &vquadrics[v_clear_index]);
 
 		/* update connected normals */
 		BM_vert_normal_update_all(v);
@@ -545,6 +672,7 @@ void BM_mesh_decimate(BMesh *bm, const float factor)
 	int face_tot_target;
 	int use_triangulate;
 
+	CD_UseFlag customdata_flag = 0;
 
 #ifdef USE_TRIANGULATE
 	/* temp convert quads to triangles */
@@ -568,6 +696,13 @@ void BM_mesh_decimate(BMesh *bm, const float factor)
 	bm->elem_index_dirty |= BM_FACE | BM_EDGE | BM_VERT;
 
 
+#ifdef USE_CUSTOMDATA
+	/* initialize customdata flag */
+	if (CustomData_has_math(&bm->vdata)) customdata_flag |= CD_DO_VERT;
+	if (CustomData_has_math(&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_empty(eheap) == FALSE)) {
 		BMEdge *e = BLI_heap_popmin(eheap);
@@ -577,7 +712,7 @@ void BM_mesh_decimate(BMesh *bm, const float factor)
 		 * 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, eheap, eheap_table);
+		bm_decim_edge_collapse(bm, e, vquadrics, eheap, eheap_table, customdata_flag);
 	}
 
 
diff --git a/source/blender/modifiers/intern/MOD_decimate.c b/source/blender/modifiers/intern/MOD_decimate.c
index 171d601ea6d..765e264365b 100644
--- a/source/blender/modifiers/intern/MOD_decimate.c
+++ b/source/blender/modifiers/intern/MOD_decimate.c
@@ -51,6 +51,8 @@
 
 /* testing only! - Campbell */
 // #define USE_DECIMATE_BMESH
+// #include "PIL_time.h"
+
 
 #ifdef WITH_MOD_DECIMATE
 #include "LOD_decimation.h"
@@ -87,16 +89,30 @@ static DerivedMesh *applyModifier(ModifierData *md, Object *UNUSED(ob),
 	BMEditMesh *em;
 	BMesh *bm;
 
+	// TIMEIT_START(decim);
+
+	if (dmd->percent == 1.0f) {
+		return dm;
+	}
+	else if (dm->getNumPolys(dm) <= 3) {
+		modifier_setError(md, "%s", TIP_("Modifier requires more than 3 input faces."));
+		return dm;
+	}
+
 	em = DM_to_editbmesh(dm, NULL, FALSE);
 	bm = em->bm;
 
 	BM_mesh_decimate(bm, dmd->percent);
 
+	dmd->faceCount = bm->totface;
+
 	BLI_assert(em->looptris == NULL);
 	result = CDDM_from_BMEditMesh(em, NULL, TRUE, FALSE);
 	BMEdit_Free(em);
 	MEM_freeN(em);
 
+	// TIMEIT_END(decim);
+
 	return result;
 }
 
@@ -113,6 +129,8 @@ static DerivedMesh *applyModifier(ModifierData *md, Object *UNUSED(ob),
 	int totvert, totface;
 	int a, numTris;
 
+	// TIMEIT_START(decim);
+
 	DM_ensure_tessface(dm); /* BMESH - UNTIL MODIFIER IS UPDATED FOR MPoly */
 
 	mvert = dm->getVertArray(dm);
@@ -214,6 +232,8 @@ static DerivedMesh *applyModifier(ModifierData *md, Object *UNUSED(ob),
 	MEM_freeN(lod.vertex_normal_buffer);
 	MEM_freeN(lod.triangle_index_buffer);
 
+	// TIMEIT_END(decim);
+
 	if (result) {
 		CDDM_tessfaces_to_faces(result); /*builds ngon faces from tess (mface) faces*/