[Bf-blender-cvs] [19b1c644592] newboolean: Faster find_coplanar_parts.
Howard Trickey
noreply at git.blender.org
Mon Dec 2 15:06:03 CET 2019
Commit: 19b1c644592b52902519c749fa735091ef27ac5c
Author: Howard Trickey
Date: Wed Nov 27 08:48:33 2019 -0500
Branches: newboolean
https://developer.blender.org/rB19b1c644592b52902519c749fa735091ef27ac5c
Faster find_coplanar_parts.
===================================================================
M source/blender/bmesh/tools/bmesh_boolean.c
===================================================================
diff --git a/source/blender/bmesh/tools/bmesh_boolean.c b/source/blender/bmesh/tools/bmesh_boolean.c
index 06f3b866e99..1d712bed2eb 100644
--- a/source/blender/bmesh/tools/bmesh_boolean.c
+++ b/source/blender/bmesh/tools/bmesh_boolean.c
@@ -94,11 +94,15 @@ typedef struct IntIntMapIterator {
* Thus, editmesh and modifier can use the same
* code but without need to convert to BMesh (or Mesh).
*
+ * Some data structures to make for efficient search
+ * are also included in this structure.
+ *
* Exactly one of bm and me should be non-null.
*/
typedef struct IMesh {
BMesh *bm;
struct Mesh *me;
+ KDTree_3d *co_tree;
} IMesh;
/* MeshAdd holds an incremental addition to an IMesh.
@@ -860,11 +864,19 @@ static int isect_line_seg_epsilon_v3_db(const double line_v1[3],
/** IMesh functions. */
#pragma mark IMesh functions
+static KDTree_3d *make_im_co_tree(IMesh *im);
+
static void init_imesh_from_bmesh(IMesh *im, BMesh *bm)
{
im->bm = bm;
im->me = NULL;
BM_mesh_elem_table_ensure(bm, BM_VERT | BM_EDGE | BM_FACE);
+ im->co_tree = make_im_co_tree(im);
+}
+
+static void imesh_free_aux_data(IMesh *im)
+{
+ BLI_kdtree_3d_free(im->co_tree);
}
static int imesh_totvert(const IMesh *im)
@@ -980,30 +992,51 @@ static void imesh_get_vert_co_db(const IMesh *im, int v, double *r_coords)
}
}
+static KDTree_3d *make_im_co_tree(IMesh *im)
+{
+ KDTree_3d *tree;
+ int v, nv;
+ float co[3];
+
+ nv = imesh_totvert(im);
+ tree = BLI_kdtree_3d_new((uint)nv);
+ for (v = 0; v < nv; v++) {
+ imesh_get_vert_co(im, v, co);
+ BLI_kdtree_3d_insert(tree, v, co);
+ }
+ BLI_kdtree_3d_balance(tree);
+ return tree;
+}
+
/* Find a vertex in im eps-close to co, if it exists.
+ * If there are multiple, return the one with the lowest vertex index.
* Else return -1.
- * TODO: speed this up.
*/
+
+/* Callback to find min index vertex within eps range. */
+static bool find_co_cb(void *user_data, int index, const float co[3], float dist_sq)
+{
+ int *v = (int *)user_data;
+ if (*v == -1) {
+ *v = index;
+ }
+ else {
+ *v = min_ii(*v, index);
+ }
+ UNUSED_VARS(co, dist_sq);
+ return true;
+}
+
static int imesh_find_co_db(const IMesh *im, const double co[3], double eps)
{
int v;
- BMesh *bm = im->bm;
float feps = (float)eps;
float fco[3];
copy_v3fl_v3db(fco, co);
- if (bm) {
- for (v = 0; v < bm->totvert; v++) {
- BMVert *bmv = BM_vert_at_index(bm, v);
- if (compare_v3v3(fco, bmv->co, feps)) {
- return v;
- }
- }
- return -1;
- }
- else {
- return -1; /* TODO */
- }
+ v = -1;
+ BLI_kdtree_3d_range_search_cb(im->co_tree, fco, feps, find_co_cb, &v);
+ return v;
}
/* Find an edge in im between given two verts (either order ok), if it exists.
@@ -2280,12 +2313,28 @@ static void canonicalize_plane(float plane[4])
/** Intersection Algorithm functions. */
#pragma mark Intersection Algorithm functions
-static int find_coplanar_cb(void *user_data, int index, const float co[4], float dist_sq)
-{
- MeshPart **face_part = (MeshPart **)user_data;
+struct FindCoplanarCBData {
+ int near_f_with_part;
+ float eps;
+ float test_plane[4];
+ MeshPart **face_part;
+};
- UNUSED_VARS(co, dist_sq);
- return face_part[index] != NULL;
+/* See if co is a plane that is eps-close to test_plane. If there is already
+ * a MeshPart for such a plane, store the lowest such index in near_f_with_part.
+ */
+static bool find_coplanar_cb(void *user_data, int index, const float co[3], float UNUSED(dist_sq))
+{
+ struct FindCoplanarCBData *cb_data = user_data;
+ if (cb_data->face_part[index] != NULL) {
+ if (fabsf(cb_data->test_plane[3] - co[3]) <= cb_data->eps &&
+ fabsf(dot_v3v3(cb_data->test_plane, co) - 1.0f) <= cb_data->eps * M_2_PI) {
+ if (cb_data->near_f_with_part == -1 || index < cb_data->near_f_with_part) {
+ cb_data->near_f_with_part = index;
+ }
+ }
+ }
+ return true;
}
/* Fill partset with parts for each plane for which there is a face
@@ -2293,37 +2342,6 @@ static int find_coplanar_cb(void *user_data, int index, const float co[4], float
* Use bs->test_fn to check elements against test_val, to see whether or not it should be in the
* result.
*/
-/* Scratch notes to self on algorithm.
- Cf emitmesh_select_similar.c which uses kdtree for SIMFACE_COPLANAR.
-
- What I need is, for each face f in the part of the mesh given by test,
- either:
- 1) make a new MeshPart for f's plane and add f to it. Add that new
- MeshPart to partset.
- or
- 2) if there is already a MeshPart for that plane, add f to that MeshPart.
-
- A kdtree can be initialized with all the planes as indicated by the test,
- where planes are identified with corresponding f as index. This tree may
- have exact and near duplicates for plane.
-
- Suppose I keep a face_part[f] indexed by face index, holding MeshPart pointers,
- all initially NULL. The goal is to fill them all in with non-NULL values
- where faces will share a part when they are all near enough the canonical plane
- vector for the MeshPart.
-
- After making the kdtree as specified above, we can then do:
- for each f:
- find all entries in kdtree that are near enough to f.
- suppose these have face indices g1, g2, ..., gk.
- Choose gi for the lowest i such that (a) face_part[gi] != NULL and
- (b) the plane of face_part[gi] is close enough to that of f.
- If there is no such gi, then make a new part with only f in it
- and record that in face_part.
- Otherwise add f to face_part[gi].
- We can use a callback function version of the kdtree nearest neighbor
- search to stop when we find the first gi that works.
-*/
static void find_coplanar_parts(BoolState *bs,
MeshPartSet *partset,
int test_val,
@@ -2336,7 +2354,7 @@ static void find_coplanar_parts(BoolState *bs,
int near_f;
float plane[4];
KDTree_4d *tree;
- KDTreeNearest_4d kdnear;
+ struct FindCoplanarCBData cb_data;
float feps = (float)bs->eps;
#ifdef BOOLDEBUG
int dbg_level = 0;
@@ -2368,6 +2386,8 @@ static void find_coplanar_parts(BoolState *bs,
#endif
}
BLI_kdtree_4d_balance(tree);
+ cb_data.eps = feps;
+ cb_data.face_part = face_part;
for (f = 0; f < im_nf; f++) {
if (test_val != TEST_ALL) {
test = imesh_test_face(im, bs->test_fn, bs->test_fn_user_data, f);
@@ -2382,33 +2402,17 @@ static void find_coplanar_parts(BoolState *bs,
printf("find part for face %d, plane=(%f,%f,%f),%f\n", f, F4(plane));
}
#endif
- near_f = BLI_kdtree_4d_find_nearest_cb(tree, plane, find_coplanar_cb, face_part, &kdnear);
+ // near_f = BLI_kdtree_4d_find_nearest_cb(tree, plane, find_coplanar_cb, face_part, &kdnear);
+ cb_data.near_f_with_part = -1;
+ copy_v4_v4(cb_data.test_plane, plane);
+ /* Use bigger epsilon for range search because comparison function we want is a bit different from 4d distance. */
+ BLI_kdtree_4d_range_search_cb(tree, plane, feps * 10.0f, find_coplanar_cb, &cb_data);
+ near_f = cb_data.near_f_with_part;
#ifdef BOOLDEBUG
if (dbg_level > 1) {
printf(" near_f = %d\n", near_f);
}
#endif
- if (near_f != -1) {
-#ifdef BOOLDEBUG
- if (dbg_level > 1) {
- printf(
- " index=%d, dist=%f, co=(%f,%f,%f),%f\n", kdnear.index, kdnear.dist, F4(kdnear.co));
- }
-#endif
- if (fabsf(kdnear.co[3] - plane[3]) <= feps &&
- fabsf(dot_v3v3(kdnear.co, plane) - 1.0f) <= feps * M_2_PI) {
- add_face_to_part(bs, face_part[near_f], f);
- face_part[f] = face_part[near_f];
-#ifdef BOOLDEBUG
- if (dbg_level > 1) {
- printf(" add to existing part %d\n", near_f);
- }
-#endif
- }
- else {
- near_f = -1;
- }
- }
if (near_f == -1) {
part = BLI_memarena_alloc(bs->mem_arena, sizeof(*part));
init_meshpart(bs, part);
@@ -2420,6 +2424,15 @@ static void find_coplanar_parts(BoolState *bs,
if (dbg_level > 1) {
printf(" near_f = -1, so new part made for f=%d\n", f);
}
+#endif
+ }
+ else {
+ add_face_to_part(bs, face_part[near_f], f);
+ face_part[f] = face_part[near_f];
+#ifdef BOOLDEBUG
+ if (dbg_level > 1) {
+ printf(" add to existing part %d\n", near_f);
+ }
#endif
}
}
@@ -3506,13 +3519,7 @@ static void intersect_partset_pair(BoolState *bs,
tree_b = tree_a;
}
-#if 0
- /* The non-_ex version uses BVH_OVERLAP_USE_THREADING | BVH_OVERLAP_RETURN_PAIRS */
- overlap = BLI_bvhtree_overlap_ex(
- tree_a, tree_b, &tree_overlap_tot, NULL, NULL, BVH_OVERLAP_RETURN_PAIRS);
-#else
overlap = BLI_bvhtree_overlap(tree_a, tree_b, &tree_overlap_tot, NULL, NULL);
-#endif
# ifdef BOOLDEBUG
if (dbg_level > 0) {
@@ -3683,6 +3690,7 @@ bool BM_mesh_boolean(BMesh *bm,
do_boolean_op(&bs, boolean_mode, &both_side_faces);
}
+ imesh_free_aux_data(&bs.im);
BLI_memarena_free(bs.mem_arena);
#ifdef PERFDEBUG
dump_perfdata();
More information about the Bf-blender-cvs
mailing list