[Bf-blender-cvs] [22931f2] master: BMesh: symmetry aware decimate
Campbell Barton
noreply at git.blender.org
Wed Nov 18 01:00:38 CET 2015
Commit: 22931f2f9f35c2f227639a534ced53fece57a8a6
Author: Campbell Barton
Date: Wed Nov 18 07:50:07 2015 +1100
Branches: master
https://developer.blender.org/rB22931f2f9f35c2f227639a534ced53fece57a8a6
BMesh: symmetry aware decimate
Support for decimating while maintaining symmetry on a single axis.
===================================================================
M release/scripts/startup/bl_ui/properties_data_modifier.py
M source/blender/bmesh/tools/bmesh_decimate.h
M source/blender/bmesh/tools/bmesh_decimate_collapse.c
M source/blender/makesdna/DNA_modifier_types.h
M source/blender/makesrna/intern/rna_modifier.c
M source/blender/modifiers/intern/MOD_decimate.c
===================================================================
diff --git a/release/scripts/startup/bl_ui/properties_data_modifier.py b/release/scripts/startup/bl_ui/properties_data_modifier.py
index f0040c9..58896e8 100644
--- a/release/scripts/startup/bl_ui/properties_data_modifier.py
+++ b/release/scripts/startup/bl_ui/properties_data_modifier.py
@@ -281,6 +281,10 @@ class DATA_PT_modifiers(ModifierButtonsPanel, Panel):
row.prop(md, "vertex_group_factor")
col.prop(md, "use_collapse_triangulate")
+ row = col.split(percentage=0.75)
+ row.prop(md, "use_symmetry")
+ row.prop(md, "symmetry_axis", text="")
+
elif decimate_type == 'UNSUBDIV':
layout.prop(md, "iterations")
diff --git a/source/blender/bmesh/tools/bmesh_decimate.h b/source/blender/bmesh/tools/bmesh_decimate.h
index 6415da9..42d90cb 100644
--- a/source/blender/bmesh/tools/bmesh_decimate.h
+++ b/source/blender/bmesh/tools/bmesh_decimate.h
@@ -30,7 +30,8 @@
void BM_mesh_decimate_collapse(
BMesh *bm, const float factor,
float *vweights, float vweight_factor,
- const bool do_triangulate);
+ const bool do_triangulate,
+ const int symmetry_axis, const float symmetry_eps);
void BM_mesh_decimate_unsubdivide_ex(BMesh *bm, const int iterations, const bool tag_only);
void BM_mesh_decimate_unsubdivide(BMesh *bm, const int iterations);
diff --git a/source/blender/bmesh/tools/bmesh_decimate_collapse.c b/source/blender/bmesh/tools/bmesh_decimate_collapse.c
index 43a3433..ddcbe34 100644
--- a/source/blender/bmesh/tools/bmesh_decimate_collapse.c
+++ b/source/blender/bmesh/tools/bmesh_decimate_collapse.c
@@ -42,6 +42,11 @@
#include "../intern/bmesh_structure.h"
+#define USE_SYMMETRY
+#ifdef USE_SYMMETRY
+#include "BLI_kdtree.h"
+#endif
+
/* defines for testing */
#define USE_CUSTOMDATA
#define USE_TRIANGULATE
@@ -343,6 +348,107 @@ static void bm_decim_build_edge_cost(
}
}
+#ifdef USE_SYMMETRY
+
+struct KD_Symmetry_Data {
+ /* pre-flipped coords */
+ float e_v1_co[3], e_v2_co[3];
+ /* Use to compare the correct endpoints incase v1/v2 are swapped */
+ float e_dir[3];
+
+ int e_found_index;
+
+ /* same for all */
+ BMEdge **etable;
+ float limit_sq;
+};
+
+static bool bm_edge_symmetry_check_cb(void *user_data, int index, const float UNUSED(co[3]), float UNUSED(dist_sq))
+{
+ struct KD_Symmetry_Data *sym_data = user_data;
+ BMEdge *e_other = sym_data->etable[index];
+ float e_other_dir[3];
+
+ sub_v3_v3v3(e_other_dir, e_other->v2->co, e_other->v1->co);
+
+ if (dot_v3v3(e_other_dir, sym_data->e_dir) > 0.0f) {
+ if ((len_squared_v3v3(sym_data->e_v1_co, e_other->v1->co) > sym_data->limit_sq) ||
+ (len_squared_v3v3(sym_data->e_v2_co, e_other->v2->co) > sym_data->limit_sq))
+ {
+ return true;
+ }
+ }
+ else {
+ if ((len_squared_v3v3(sym_data->e_v1_co, e_other->v2->co) > sym_data->limit_sq) ||
+ (len_squared_v3v3(sym_data->e_v2_co, e_other->v1->co) > sym_data->limit_sq))
+ {
+ return true;
+ }
+ }
+
+ /* exit on first-hit, this is OK since the search range is very small */
+ sym_data->e_found_index = index;
+ return false;
+}
+
+static int *bm_edge_symmetry_map(BMesh *bm, unsigned int symmetry_axis, float limit)
+{
+ struct KD_Symmetry_Data sym_data;
+ BMIter iter;
+ BMEdge *e, **etable;
+ unsigned int i;
+ int *edge_symmetry_map;
+ const float limit_sq = SQUARE(limit);
+ KDTree *tree;
+
+ tree = BLI_kdtree_new(bm->totedge);
+
+ etable = MEM_mallocN(sizeof(BMEdge **) * bm->totedge, __func__);
+ edge_symmetry_map = MEM_mallocN(sizeof(*edge_symmetry_map) * bm->totedge, __func__);
+
+ BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
+ float co[3];
+ mid_v3_v3v3(co, e->v1->co, e->v2->co);
+ BLI_kdtree_insert(tree, i, co);
+ etable[i] = e;
+ edge_symmetry_map[i] = -1;
+ }
+
+ BLI_kdtree_balance(tree);
+
+ sym_data.etable = etable;
+ sym_data.limit_sq = limit_sq;
+
+ BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
+ if (edge_symmetry_map[i] == -1) {
+ float co[3];
+ mid_v3_v3v3(co, e->v1->co, e->v2->co);
+ co[symmetry_axis] *= -1.0f;
+
+ copy_v3_v3(sym_data.e_v1_co, e->v1->co);
+ copy_v3_v3(sym_data.e_v2_co, e->v2->co);
+ sym_data.e_v1_co[symmetry_axis] *= -1.0f;
+ sym_data.e_v2_co[symmetry_axis] *= -1.0f;
+ sub_v3_v3v3(sym_data.e_dir, sym_data.e_v2_co, sym_data.e_v1_co);
+ sym_data.e_found_index = -1;
+
+ BLI_kdtree_range_search_cb(tree, co, limit, bm_edge_symmetry_check_cb, &sym_data);
+
+ if (sym_data.e_found_index != -1) {
+ const int i_other = sym_data.e_found_index;
+ edge_symmetry_map[i] = i_other;
+ edge_symmetry_map[i_other] = i;
+ }
+ }
+ }
+
+ MEM_freeN(etable);
+ BLI_kdtree_free(tree);
+
+ return edge_symmetry_map;
+}
+#endif /* USE_SYMMETRY */
+
#ifdef USE_TRIANGULATE
/* Temp Triangulation
* ****************** */
@@ -763,6 +869,9 @@ static bool bm_edge_collapse_is_degenerate_topology(BMEdge *e_first)
*/
static bool bm_edge_collapse(
BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e_clear_other[2],
+#ifdef USE_SYMMETRY
+ int *edge_symmetry_map,
+#endif
#ifdef USE_CUSTOMDATA
const CD_UseFlag customdata_flag,
const float customdata_fac
@@ -853,6 +962,18 @@ static bool bm_edge_collapse(
BM_edge_splice(bm, e_a_other[1], e_a_other[0]);
BM_edge_splice(bm, e_b_other[1], e_b_other[0]);
+#ifdef USE_SYMMETRY
+ /* update mirror map */
+ if (edge_symmetry_map) {
+ if (edge_symmetry_map[r_e_clear_other[0]] != -1) {
+ edge_symmetry_map[edge_symmetry_map[r_e_clear_other[0]]] = BM_elem_index_get(e_a_other[1]);
+ }
+ if (edge_symmetry_map[r_e_clear_other[1]] != -1) {
+ edge_symmetry_map[edge_symmetry_map[r_e_clear_other[1]]] = BM_elem_index_get(e_b_other[1]);
+ }
+ }
+#endif
+
// BM_mesh_validate(bm);
return true;
@@ -900,6 +1021,15 @@ static bool bm_edge_collapse(
e_a_other[1]->head.hflag |= e_a_other[0]->head.hflag;
BM_edge_splice(bm, e_a_other[1], e_a_other[0]);
+#ifdef USE_SYMMETRY
+ /* update mirror map */
+ if (edge_symmetry_map) {
+ if (edge_symmetry_map[r_e_clear_other[0]] != -1) {
+ edge_symmetry_map[edge_symmetry_map[r_e_clear_other[0]]] = BM_elem_index_get(e_a_other[1]);
+ }
+ }
+#endif
+
// BM_mesh_validate(bm);
return true;
@@ -910,19 +1040,27 @@ static bool bm_edge_collapse(
}
-/* collapse e the edge, removing e->v2 */
-static void bm_decim_edge_collapse(
+/**
+ * Collapse e the edge, removing e->v2
+ *
+ * \return true when the edge was collapsed.
+ */
+static bool bm_decim_edge_collapse(
BMesh *bm, BMEdge *e,
Quadric *vquadrics,
float *vweights, const float vweight_factor,
Heap *eheap, HeapNode **eheap_table,
- const CD_UseFlag customdata_flag)
+#ifdef USE_SYMMETRY
+ int *edge_symmetry_map,
+#endif
+ const CD_UseFlag customdata_flag,
+ float optimize_co[3], bool optimize_co_calc
+ )
{
int e_clear_other[2];
BMVert *v_other = e->v1;
const int v_other_index = BM_elem_index_get(e->v1);
const 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
@@ -930,18 +1068,21 @@ static void bm_decim_edge_collapse(
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;
- }
+ /* when false, use without degenerate checks */
+ if (optimize_co_calc) {
+ /* 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 false;
+ }
- bm_decim_calc_target_co(e, optimize_co, vquadrics);
+ 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;
+ /* 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 false;
+ }
}
/* use for customdata merging */
@@ -950,7 +1091,7 @@ static void bm_decim_edge_collapse(
#if 0
/* simple test for stupid collapse */
if (customdata_fac < 0.0 - FLT_EPSILON || customdata_fac > 1.0f + FLT_EPSILON) {
- return;
+ return false;
}
#endif
}
@@ -959,7 +1100,13 @@ static void bm_decim_edge_collapse(
customdata_fac = 0.5f;
}
- if (bm_edge_collapse(bm, e, e->v2, e_clear_other, customdata_flag, customdata_fac)) {
+ if (bm_edge_collapse(
+ bm, e, e->v2, e_clear_other,
+#ifdef USE_SYMMETRY
+ edge_symmetry_map,
+#endif
+ customdata_flag, customdata_fac))
+ {
/* update collapse info */
int i;
@@ -1031,11 +1178,13 @@ static void bm_decim_edge_collapse(
}
}
/* end optional update */
+ return true;
#endif
}
else {
/* add back with a high cost */
bm_decim_invalid_edge_cost_single(e, eheap, eheap_table);
+ return false;
}
}
@@ -1049,12 +1198,14 @@ static void bm_decim_edge_collapse(
* \param factor face count multiplier [0 - 1]
* \param vweights Optional array of vertex aligned weights [0 - 1],
* a vertex group is the usual source for this.
+ * \param axis: Axis of symmetry, -1 to disable mirror decimate.
*/
void BM_mesh_decimate_collapse(
BMesh *bm,
const float factor,
float *vweights, float vweight_factor,
- const bool do_triangulate)
+ const bool do_triangulate,
+ const int symmetry_axis, const float symmetry_eps)
{
Heap *eheap; /* edge heap */
HeapNode **eheap_table; /* edge index aligned table pointing to the eheap */
@@ -1065,6 +1216,11 @@ void BM_mesh_decimate_collapse(
CD_UseFlag customdata_flag = 0;
+#ifdef USE_SYMMETRY
+ bool use_symmetry = (symmetry_axis != -1);
+ int *edge_symmetry_
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list