[Bf-blender-cvs] [5bceb00] master: Mesh API: replace octree mirror with kdtree
Campbell Barton
noreply at git.blender.org
Wed Mar 12 15:50:15 CET 2014
Commit: 5bceb00a61f1cd98c049cc11931550acf08426c7
Author: Campbell Barton
Date: Thu Mar 13 01:36:24 2014 +1100
https://developer.blender.org/rB5bceb00a61f1cd98c049cc11931550acf08426c7
Mesh API: replace octree mirror with kdtree
===================================================================
M source/blender/editors/include/ED_mesh.h
M source/blender/editors/mesh/meshtools.c
M source/blenderplayer/bad_level_call_stubs/stubs.c
===================================================================
diff --git a/source/blender/editors/include/ED_mesh.h b/source/blender/editors/include/ED_mesh.h
index 04f8dfc..2d7e558 100644
--- a/source/blender/editors/include/ED_mesh.h
+++ b/source/blender/editors/include/ED_mesh.h
@@ -300,7 +300,8 @@ void EDBM_redo_state_free(struct BMBackup *, struct BMEditMesh *em, int recalcte
int join_mesh_exec(struct bContext *C, struct wmOperator *op);
int join_mesh_shapes_exec(struct bContext *C, struct wmOperator *op);
-intptr_t mesh_octree_table(struct Object *ob, struct BMEditMesh *em, const float co[3], char mode);
+/* mirror lookup api */
+int mesh_octree_table(struct Object *ob, struct BMEditMesh *em, const float co[3], char mode);
int mesh_mirrtopo_table(struct Object *ob, char mode);
/* retrieves mirrored cache vert, or NULL if there isn't one.
diff --git a/source/blender/editors/mesh/meshtools.c b/source/blender/editors/mesh/meshtools.c
index 1d47d4c..8047959 100644
--- a/source/blender/editors/mesh/meshtools.c
+++ b/source/blender/editors/mesh/meshtools.c
@@ -47,6 +47,7 @@
#include "BLI_blenlib.h"
+#include "BLI_kdtree.h"
#include "BKE_context.h"
#include "BKE_depsgraph.h"
#include "BKE_deform.h"
@@ -657,245 +658,101 @@ int join_mesh_shapes_exec(bContext *C, wmOperator *op)
return OPERATOR_FINISHED;
}
-/* ********************* MESH VERTEX OCTREE LOOKUP ************* */
+/* -------------------------------------------------------------------- */
+/* Mesh Mirror (Spatial) */
-/* important note; this is unfinished, needs better API for editmode, and custom threshold */
+/** \name Mesh Spatial Mirror API
+ * \{ */
-#define MOC_RES 8
-#define MOC_NODE_RES 8
-#define MOC_THRESH 0.00002f
+#define KD_THRESH 0.00002f
-typedef struct MocNode {
- struct MocNode *next;
- intptr_t index[MOC_NODE_RES];
-} MocNode;
-
-static int mesh_octree_get_base_offs(const float co[3], const float offs[3], const float div[3])
-{
- int vx, vy, vz;
-
- vx = floor((co[0] - offs[0]) / div[0]);
- vy = floor((co[1] - offs[1]) / div[1]);
- vz = floor((co[2] - offs[2]) / div[2]);
-
- CLAMP(vx, 0, MOC_RES - 1);
- CLAMP(vy, 0, MOC_RES - 1);
- CLAMP(vz, 0, MOC_RES - 1);
-
- return (vx * MOC_RES * MOC_RES) + vy * MOC_RES + vz;
-}
-
-static void mesh_octree_add_node(MocNode **bt, intptr_t index)
-{
- if (*bt == NULL) {
- *bt = MEM_callocN(sizeof(MocNode), "MocNode");
- (*bt)->index[0] = index;
- }
- else {
- int a;
- for (a = 0; a < MOC_NODE_RES; a++) {
- if ((*bt)->index[a] == index)
- return;
- else if ((*bt)->index[a] == 0) {
- (*bt)->index[a] = index;
- return;
- }
- }
- mesh_octree_add_node(&(*bt)->next, index);
- }
-}
-
-static void mesh_octree_free_node(MocNode **bt)
-{
- if ( (*bt)->next) {
- mesh_octree_free_node(&(*bt)->next);
- }
- MEM_freeN(*bt);
-}
-
-
-/* temporal define, just to make nicer code below */
-#define MOC_INDEX(vx, vy, vz) (((vx) * MOC_RES * MOC_RES) + (vy) * MOC_RES + (vz))
-
-static void mesh_octree_add_nodes(MocNode **basetable, const float co[3], const float offs[3],
- const float div[3], intptr_t index)
-{
- float fx, fy, fz;
- int vx, vy, vz;
-
- if ((finite(co[0]) == false) ||
- (finite(co[1]) == false) ||
- (finite(co[2]) == false))
- {
- return;
- }
-
- fx = (co[0] - offs[0]) / div[0];
- fy = (co[1] - offs[1]) / div[1];
- fz = (co[2] - offs[2]) / div[2];
- CLAMP(fx, 0.0f, MOC_RES - MOC_THRESH);
- CLAMP(fy, 0.0f, MOC_RES - MOC_THRESH);
- CLAMP(fz, 0.0f, MOC_RES - MOC_THRESH);
-
- vx = (int)floorf(fx);
- vy = (int)floorf(fy);
- vz = (int)floorf(fz);
-
- mesh_octree_add_node(basetable + MOC_INDEX(vx, vy, vz), index);
-
- if (vx > 0)
- if (fx - ((float)vx) - MOC_THRESH < 0.0f)
- mesh_octree_add_node(basetable + MOC_INDEX(vx - 1, vy, vz), index);
- if (vx < MOC_RES - 2)
- if (fx - ((float)vx) + MOC_THRESH > 1.0f)
- mesh_octree_add_node(basetable + MOC_INDEX(vx + 1, vy, vz), index);
-
- if (vy > 0)
- if (fy - ((float)vy) - MOC_THRESH < 0.0f)
- mesh_octree_add_node(basetable + MOC_INDEX(vx, vy - 1, vz), index);
- if (vy < MOC_RES - 2)
- if (fy - ((float)vy) + MOC_THRESH > 1.0f)
- mesh_octree_add_node(basetable + MOC_INDEX(vx, vy + 1, vz), index);
-
- if (vz > 0)
- if (fz - ((float)vz) - MOC_THRESH < 0.0f)
- mesh_octree_add_node(basetable + MOC_INDEX(vx, vy, vz - 1), index);
- if (vz < MOC_RES - 2)
- if (fz - ((float)vz) + MOC_THRESH > 1.0f)
- mesh_octree_add_node(basetable + MOC_INDEX(vx, vy, vz + 1), index);
-
-}
-
-static intptr_t mesh_octree_find_index(MocNode **bt, MVert *mvert, const float co[3])
-{
- float *vec;
- int a;
-
- if (*bt == NULL)
- return -1;
-
- for (a = 0; a < MOC_NODE_RES; a++) {
- if ((*bt)->index[a]) {
- /* does mesh verts and editmode, code looks potential dangerous, octree should really be filled OK! */
- if (mvert) {
- vec = (mvert + (*bt)->index[a] - 1)->co;
- if (compare_v3v3(vec, co, MOC_THRESH))
- return (*bt)->index[a] - 1;
- }
- else {
- BMVert *eve = (BMVert *)((*bt)->index[a]);
- if (compare_v3v3(eve->co, co, MOC_THRESH))
- return (*bt)->index[a];
- }
- }
- else {
- return -1;
- }
- }
- if ( (*bt)->next)
- return mesh_octree_find_index(&(*bt)->next, mvert, co);
-
- return -1;
-}
-
-static struct {
- MocNode **table;
- float offs[3], div[3];
-} MeshOctree = {NULL, {0, 0, 0}, {0, 0, 0}};
+static struct { void *tree; } MirrKdStore = {NULL};
/* mode is 's' start, or 'e' end, or 'u' use */
/* if end, ob can be NULL */
-intptr_t mesh_octree_table(Object *ob, BMEditMesh *em, const float co[3], char mode)
+int mesh_octree_table(Object *ob, BMEditMesh *em, const float co[3], char mode)
{
- MocNode **bt;
-
if (mode == 'u') { /* use table */
- if (MeshOctree.table == NULL)
+ if (MirrKdStore.tree == NULL)
mesh_octree_table(ob, em, NULL, 's');
- if (MeshOctree.table) {
- Mesh *me = ob->data;
- bt = MeshOctree.table + mesh_octree_get_base_offs(co, MeshOctree.offs, MeshOctree.div);
- if (em)
- return mesh_octree_find_index(bt, NULL, co);
- else
- return mesh_octree_find_index(bt, me->mvert, co);
+ if (MirrKdStore.tree) {
+ KDTreeNearest nearest;
+
+ int i;
+
+ i = BLI_kdtree_find_nearest(MirrKdStore.tree, co, NULL, &nearest);
+
+ if (i != -1) {
+ if (nearest.dist < KD_THRESH) {
+ return i;
+ }
+ }
}
return -1;
}
else if (mode == 's') { /* start table */
Mesh *me = ob->data;
- float min[3], max[3];
+ int totvert;
- /* we compute own bounding box and don't reuse ob->bb because
- * we are using the undeformed coordinates*/
- INIT_MINMAX(min, max);
+ if (MirrKdStore.tree) /* happens when entering this call without ending it */
+ mesh_octree_table(ob, em, co, 'e');
if (em && me->edit_btmesh == em) {
- BMIter iter;
- BMVert *eve;
-
- BM_ITER_MESH (eve, &iter, em->bm, BM_VERTS_OF_MESH) {
- minmax_v3v3_v3(min, max, eve->co);
- }
+ totvert = em->bm->totvert;
}
else {
- MVert *mvert;
- int a;
-
- for (a = 0, mvert = me->mvert; a < me->totvert; a++, mvert++)
- minmax_v3v3_v3(min, max, mvert->co);
+ totvert = me->totvert;
}
-
- /* for quick unit coordinate calculus */
- copy_v3_v3(MeshOctree.offs, min);
- /* we offset it 1 threshold unit extra */
- add_v3_fl(MeshOctree.offs, -MOC_THRESH);
-
- sub_v3_v3v3(MeshOctree.div, max, min);
- /* and divide with 2 threshold unit more extra (try 8x8 unit grid on paint) */
- add_v3_fl(MeshOctree.div, 2.0f * MOC_THRESH);
-
- mul_v3_fl(MeshOctree.div, 1.0f / MOC_RES);
- if (MeshOctree.div[0] == 0.0f) MeshOctree.div[0] = 1.0f;
- if (MeshOctree.div[1] == 0.0f) MeshOctree.div[1] = 1.0f;
- if (MeshOctree.div[2] == 0.0f) MeshOctree.div[2] = 1.0f;
-
- if (MeshOctree.table) /* happens when entering this call without ending it */
- mesh_octree_table(ob, em, co, 'e');
-
- MeshOctree.table = MEM_callocN(MOC_RES * MOC_RES * MOC_RES * sizeof(void *), "sym table");
-
+
+ MirrKdStore.tree = BLI_kdtree_new(totvert);
+
if (em && me->edit_btmesh == em) {
+
BMVert *eve;
BMIter iter;
+ int i;
+
+ /* this needs to be valid for index lookups later (callers need) */
+ BM_mesh_elem_table_ensure(em->bm, BM_VERT);
- BM_ITER_MESH (eve, &iter, em->bm, BM_VERTS_OF_MESH) {
- mesh_octree_add_nodes(MeshOctree.table, eve->co, MeshOctree.offs, MeshOctree.div, (intptr_t)(eve));
+ BM_ITER_MESH_INDEX (eve, &iter, em->bm, BM_VERTS_OF_MESH, i) {
+ BLI_kdtree_insert(MirrKdStore.tree, i, eve->co, NULL);
}
}
else {
MVert *mvert;
- int a;
+ int i;
- for (a = 0, mvert = me->mvert; a < me->totvert; a++, mvert++)
- mesh_octree_add_nodes(MeshOctree.table, mvert->co, MeshOctree.offs, MeshOctree.div, a + 1);
+ for (i = 0, mvert = me->mvert; i < me->totvert; i++, mvert++) {
+ BLI_kdtree_insert(MirrKdStore.tree, i, mvert->co, NULL);
+ }
}
+
+ BLI_kdtree_balance(MirrKdStore.tree);
}
else if (mode == 'e') { /* end table */
- if (MeshOctree.table) {
- int a;
-
- for (a = 0, bt = MeshOctree.table; a < MOC_RES * MOC_RES * MOC_RES; a++, bt++) {
- if (*bt) mesh_octree_free_node(bt);
- }
- MEM_freeN(MeshOctree.table);
- MeshOctree.table = NULL;
+ if (MirrKdStore.tree) {
+ BLI_kdtree_free(MirrKdStore.tree);
+ MirrKdStore.tree = NULL;
}
}
+ else {
+ BLI_assert(0);
+ }
+
return 0;
}
+/** \} */
+
+
+/* -------------------------------------------------------------------- */
+/* Mesh Mirror (Topology) */
+
+/** \name Mesh Topology Mirror API
+ * \{ */
+
static MirrTopoStore_t mesh_topo_store = {NULL, -1. - 1, -1};
/* mode is 's' start, or 'e' end, or 'u' use */
@@ -914,9 +771,16 @@ int mesh_mirrtopo_table(Object *ob, char mode)
else if (mode == 'e') { /* end table */
ED_mesh_mirrtopo_free(&mesh_topo_store);
}
+ else {
+ BLI_assert(0);
+ }
+
return 0;
}
+/** \} */
+
+
static int mesh_get_x_mirror_vert_spatial(Object *ob, int index)
{
Mesh *me = ob->data;
@@ -952,7 +816,7 @@ int mesh_get_x_mirror_vert(Object *ob, int index, const bool use_topology)
static BMVert *editbmesh_get_x_mirror_vert_spatial(Object *ob, BMEditMesh *em, const float co[3])
{
float vec[3];
- intptr_t poinval;
+ int i;
/* ignore nan verts */
if ((finite(co[0]) == false) ||
@@ -
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list