[Bf-blender-cvs] [ff4f28e15dc] newboolean: Use BVH for partset pair intersection tests.
Howard Trickey
noreply at git.blender.org
Mon Dec 2 15:05:58 CET 2019
Commit: ff4f28e15dca3880bd03f794cd01ba1102ea7896
Author: Howard Trickey
Date: Tue Nov 26 07:49:43 2019 -0500
Branches: newboolean
https://developer.blender.org/rBff4f28e15dca3880bd03f794cd01ba1102ea7896
Use BVH for partset pair intersection tests.
All regression tests pass.
===================================================================
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 b2605e1de56..8d6d99b7682 100644
--- a/source/blender/bmesh/tools/bmesh_boolean.c
+++ b/source/blender/bmesh/tools/bmesh_boolean.c
@@ -32,6 +32,7 @@
#include "BLI_alloca.h"
#include "BLI_bitmap.h"
#include "BLI_delaunay_2d.h"
+#include "BLI_kdopbvh.h"
#include "BLI_kdtree.h"
#include "BLI_linklist.h"
#include "BLI_math.h"
@@ -48,11 +49,6 @@
#define BOOLDEBUG
// #define PERFDEBUG
-/* NOTE: Work in progress. Initial implementation using slow data structures and algorithms
- * just to get the correct calculations down. After that, will replace data structures with
- * faster-lookup versions (hash tables, kd-trees, bvh structures) and will parallelize.
- */
-
/* A set of integers. TODO: faster structure. */
typedef struct IntSet {
LinkNode *list;
@@ -2096,11 +2092,6 @@ static bool parts_may_intersect(const MeshPart *part1, const MeshPart *part2)
return isect_aabb_aabb_v3_db(part1->bbmin, part1->bbmax, part2->bbmin, part2->bbmax);
}
-static bool part_may_intersect_partset(const MeshPart *part, const MeshPartSet *partset)
-{
- return isect_aabb_aabb_v3_db(part->bbmin, part->bbmax, partset->bbmin, partset->bbmax);
-}
-
/* Return true if a_plane and b_plane are the same plane, to within eps.
* Assume normal part of plane is normalized. */
static bool planes_are_coplanar(const double a_plane[4], const double b_plane[4], double eps)
@@ -2293,7 +2284,7 @@ static int find_coplanar_cb(void *user_data, int index, const float co[4], float
{
MeshPart **face_part = (MeshPart **)user_data;
- UNUSED_VARS(co,dist_sq);
+ UNUSED_VARS(co, dist_sq);
return face_part[index] != NULL;
}
@@ -2351,7 +2342,6 @@ static void find_coplanar_parts(BoolState *bs,
int dbg_level = 0;
#endif
-
#ifdef BOOLDEBUG
if (dbg_level > 0) {
printf("\nFIND_COPLANAR_PARTS %s, test_val=%d\n", label, test_val);
@@ -2400,23 +2390,24 @@ static void find_coplanar_parts(BoolState *bs,
#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));
- }
+ 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];
+ 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 (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));
@@ -3421,6 +3412,31 @@ static PartPartIntersect *part_part_intersect(BoolState *bs,
return ans;
}
+/* Lexicographic sort of two BVHTreeOverlap. */
+static int bool_overlap_sort_fn(const void *v_1, const void *v_2)
+{
+ const BVHTreeOverlap *o1 = v_1;
+ const BVHTreeOverlap *o2 = v_2;
+
+ if (o1->indexA < o2->indexA) {
+ return -1;
+ }
+ else if (o1->indexA > o2->indexA) {
+ return 1;
+ }
+ else {
+ if (o1->indexB < o2->indexB) {
+ return -1;
+ }
+ else if (o1->indexB > o2->indexB) {
+ return 1;
+ }
+ else {
+ return 0;
+ }
+ }
+}
+
/* Intersect all parts of a_partset with all parts of b_partset.
*/
static void intersect_partset_pair(BoolState *bs,
@@ -3428,7 +3444,8 @@ static void intersect_partset_pair(BoolState *bs,
MeshPartSet *b_partset,
MeshChange *meshchange)
{
- int a_index, b_index, tot_part_a, tot_part_b, bstart;
+ int a_index, b_index, tot_part_a, tot_part_b;
+ uint overlap_index;
MeshPart *part_a, *part_b;
MemArena *arena = bs->mem_arena;
bool same_partsets = (a_partset == b_partset);
@@ -3436,11 +3453,16 @@ static void intersect_partset_pair(BoolState *bs,
LinkNodePair *b_isects; /* Array of List of PairPartIntersect. */
PartPartIntersect *isect;
BLI_bitmap *bpart_coplanar_with_apart;
-#ifdef BOOLDEBUG
+ BVHTree *tree_a, *tree_b;
+ uint tree_overlap_tot;
+ BVHTreeOverlap *overlap;
+ float feps_margin = 20.0f * ((float)bs->eps);
+ float bbpts[6];
+# ifdef BOOLDEBUG
int dbg_level = 0;
-#endif
+# endif
-#ifdef BOOLDEBUG
+# ifdef BOOLDEBUG
if (dbg_level > 0) {
printf("\nINTERSECT_PARTSET_PAIR\n\n");
if (dbg_level > 0) {
@@ -3448,41 +3470,89 @@ static void intersect_partset_pair(BoolState *bs,
dump_partset(b_partset);
}
}
-#endif
+# endif
tot_part_a = a_partset->tot_part;
tot_part_b = b_partset->tot_part;
a_isects = BLI_memarena_calloc(arena, (size_t)tot_part_a * sizeof(a_isects[0]));
b_isects = BLI_memarena_calloc(arena, (size_t)tot_part_b * sizeof(b_isects[0]));
bpart_coplanar_with_apart = BLI_BITMAP_NEW_MEMARENA(arena, tot_part_b);
-#ifdef BOOLDEBUG
+# ifdef BOOLDEBUG
if (dbg_level > 0) {
- printf("\nIntersect_partset_pair: do all part - part preliminary intersections\n\n");
+ printf(
+ "\nIntersect_partset_pair: do all part - part preliminary intersections (using bvh)\n\n");
}
-#endif
+# endif
+ /* Tree type is 8 => octtree; axis = 6 => using XYZ axes only. */
+ tree_a = BLI_bvhtree_new(tot_part_a, feps_margin, 8, 6);
for (a_index = 0; a_index < tot_part_a; a_index++) {
part_a = partset_part(a_partset, a_index);
- if (!part_may_intersect_partset(part_a, b_partset)) {
- continue;
+ copy_v3fl_v3db(bbpts, part_a->bbmin);
+ copy_v3fl_v3db(bbpts + 3, part_a->bbmax);
+ BLI_bvhtree_insert(tree_a, a_index, bbpts, 2);
+ }
+ BLI_bvhtree_balance(tree_a);
+ if (!same_partsets) {
+ tree_b = BLI_bvhtree_new(tot_part_b, feps_margin, 8, 6);
+ for (b_index = 0; b_index < tot_part_b; b_index++) {
+ part_b = partset_part(b_partset, b_index);
+ copy_v3fl_v3db(bbpts, part_b->bbmin);
+ copy_v3fl_v3db(bbpts + 3, part_b->bbmax);
+ BLI_bvhtree_insert(tree_b, b_index, bbpts, 2);
}
- bstart = same_partsets ? a_index + 1 : 0;
- for (b_index = bstart; b_index < tot_part_b; b_index++) {
+ BLI_bvhtree_balance(tree_b);
+ }
+ else {
+ 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) {
+ printf("process %u overlaps\n\n", tree_overlap_tot);
+ }
+# endif
+
+ if (overlap) {
+ /* For stable results in the face of, especially, multithreaded bvhtree overlap, sort the overlaps. */
+ qsort(overlap, tree_overlap_tot, sizeof(overlap[0]), bool_overlap_sort_fn);
+ for (overlap_index = 0; overlap_index < tree_overlap_tot; overlap_index++) {
+ a_index = overlap[overlap_index].indexA;
+ b_index = overlap[overlap_index].indexB;
+# ifdef BOOLDEBUG
+ if (dbg_level > 1) {
+ printf("overlap: a%d and b%d\n", a_index, b_index);
+ }
+# endif
+ part_a = partset_part(a_partset, a_index);
part_b = partset_part(b_partset, b_index);
- if (!same_partsets) {
+ if (same_partsets) {
+ if (b_index <= a_index) {
+ continue;
+ }
+ }
+ else {
if (planes_are_coplanar(part_a->plane, part_b->plane, bs->eps)) {
BLI_BITMAP_ENABLE(bpart_coplanar_with_apart, b_index);
}
}
isect = part_part_intersect(bs, part_a, a_index, part_b, b_index, meshchange);
if (isect != NULL) {
-#ifdef BOOLDEBUG
- if (dbg_level > 0) {
+# ifdef BOOLDEBUG
+ if (false && dbg_level > 0) { /*DEBUG!!*/
printf("Part a%d intersects part b%d\n", a_index, b_index);
dump_partpartintersect(isect, "");
printf("\n");
dump_meshchange(meshchange, "incremental");
}
-#endif
+# endif
BLI_linklist_append_arena(&a_isects[a_index], isect, arena);
BLI_linklist_append_arena(&b_isects[b_index], isect, arena);
if (same_partsets) {
@@ -3491,52 +3561,53 @@ static void intersect_partset_pair(BoolState *bs,
}
}
}
+ MEM_freeN(overlap);
}
-#ifdef BOOLDEBUG
+# ifdef BOOLDEBUG
if (dbg_level > 0) {
printf("\nintersect_partset_pair: do self intersections\n\n");
}
-#endif
+# endif
/* Now self-intersect the parts with their lists of isects. */
for (a_index = 0; a_index < tot_part_a; a_index++) {
part_a = partset_part(a_partset, a_index);
-#ifdef BOOLDEBUG
+# ifdef BOOLDEBUG
if (dbg_level > 0) {
printf("\nSELF INTERSECT part a%d with its ppis\n", a_index);
}
-#endif
+# endif
isect = self_intersect_part_and_ppis(bs, part_a, &a_isects[a_index], meshchange);
-#ifdef BOOLDEBUG
+# ifdef BOOLDEBUG
if (isect && dbg_level > 0) {
dump_partpartintersect(isect, "after self intersect");
dump_meshchange(meshchange, "after self intersect");
}
-#endif
+# endif
}
if (!same_partsets) {
for (b_index = 0; b_index < tot_part_b; b_index++) {
part_b = partset_part(b_partset, b_index);
-#ifdef BOOLDEBUG
+# ifdef BOOLDEBUG
if (dbg_level > 0) {
printf("\nSELF INTERSECT part b%d with its ppis\n", b_index);
}
-#endif
+# endif
if (BLI_BITMAP_TEST_BOOL(bpart_coplanar_with_apart, b_index)) {
-#ifdef BOOLDEBUG
+# ifdef BOOLDEBUG
if (dbg_level > 0) {
printf("skipping self_intersect because coplanar with some a part\n");
}
-#endif
+# endif
continue
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list