[Bf-blender-cvs] [8148d083207] temp-angavrilov: BVH: implement an optimized self-overlap traversal.
Alexander Gavrilov
noreply at git.blender.org
Thu Dec 29 16:09:28 CET 2022
Commit: 8148d0832072e97b36a6610380f8b9d27f2673f9
Author: Alexander Gavrilov
Date: Wed Dec 28 22:19:36 2022 +0200
Branches: temp-angavrilov
https://developer.blender.org/rB8148d0832072e97b36a6610380f8b9d27f2673f9
BVH: implement an optimized self-overlap traversal.
Previously cloth self-collision and other code that wants self-overlap
data was using an ordinary BVH overlap utility function. This works,
but is suboptimal because it fails to take advantage of the fact that
it is comparing two identical trees.
The standard traversal for self-collision essentially devolves into
enumerating all elements of the tree, and then matching them to the
tree starting at the root. However, the tree itself naturally partitions
the space, so overlapping elements are likely to be mostly placed nearby
in the tree structure as well.
Instead, self-overlap can be computed by recursively computing ordinary
overlap between siblings within each subtree. This still only considers
each pair of leaves once, and provides significantly better locality.
It also avoids outputting every overlap pair twice in different order.
In addition, the generic traversal probably should recurse into the
spatially bigger node first to achieve a similar locality effect.
===================================================================
M source/blender/blenkernel/intern/collision.c
M source/blender/blenlib/BLI_kdopbvh.h
M source/blender/blenlib/intern/BLI_kdopbvh.c
M source/blender/draw/intern/mesh_extractors/extract_mesh_vbo_mesh_analysis.cc
M source/blender/editors/uvedit/uvedit_select.c
===================================================================
diff --git a/source/blender/blenkernel/intern/collision.c b/source/blender/blenkernel/intern/collision.c
index 2acdc6543b5..cd34ae29efb 100644
--- a/source/blender/blenkernel/intern/collision.c
+++ b/source/blender/blenkernel/intern/collision.c
@@ -1521,8 +1521,9 @@ static bool cloth_bvh_obj_overlap_cb(void *userdata,
static bool cloth_bvh_self_overlap_cb(void *userdata, int index_a, int index_b, int UNUSED(thread))
{
- /* No need for equal combinations (eg. (0,1) & (1,0)). */
- if (index_a < index_b) {
+ /* This shouldn't happen, but just in case. Note that equal combinations
+ * (eg. (0,1) & (1,0)) would be filtered out by BLI_bvhtree_overlap_self. */
+ if (index_a != index_b) {
ClothModifierData *clmd = (ClothModifierData *)userdata;
struct Cloth *clothObject = clmd->clothObject;
const MVertTri *tri_a, *tri_b;
@@ -1599,8 +1600,8 @@ int cloth_bvh_collision(
if (clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_SELF) {
bvhtree_update_from_cloth(clmd, false, true);
- overlap_self = BLI_bvhtree_overlap(
- cloth->bvhselftree, cloth->bvhselftree, &coll_count_self, cloth_bvh_self_overlap_cb, clmd);
+ overlap_self = BLI_bvhtree_overlap_self(
+ cloth->bvhselftree, &coll_count_self, cloth_bvh_self_overlap_cb, clmd);
}
do {
diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h
index 17759b6a8ac..8516bccd0d4 100644
--- a/source/blender/blenlib/BLI_kdopbvh.h
+++ b/source/blender/blenlib/BLI_kdopbvh.h
@@ -73,9 +73,11 @@ typedef struct BVHTreeRayHit {
} BVHTreeRayHit;
enum {
- /* Use a priority queue to process nodes in the optimal order (for slow callbacks) */
BVH_OVERLAP_USE_THREADING = (1 << 0),
BVH_OVERLAP_RETURN_PAIRS = (1 << 1),
+ /* Optimize self-overlap to only test and output every pair once,
+ * rather than twice in different order as usual. */
+ BVH_OVERLAP_SELF = (1 << 2),
};
enum {
/* Use a priority queue to process nodes in the optimal order (for slow callbacks) */
@@ -163,6 +165,9 @@ bool BLI_bvhtree_update_node(
BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints);
/**
* Call #BLI_bvhtree_update_node() first for every node/point/triangle.
+ *
+ * Note that this does not rebalance the tree, so if the shape of the mesh changes
+ * too much, operations on the tree may become suboptimal.
*/
void BLI_bvhtree_update_tree(BVHTree *tree);
@@ -191,6 +196,12 @@ BVHTreeOverlap *BLI_bvhtree_overlap(const BVHTree *tree1,
unsigned int *r_overlap_num,
BVHTree_OverlapCallback callback,
void *userdata);
+/** Compute overlaps of the tree with itself. This is faster than BLI_bvhtree_overlap
+ * because it only tests and returns each symmetrical pair once. */
+BVHTreeOverlap *BLI_bvhtree_overlap_self(const BVHTree *tree,
+ unsigned int *r_overlap_num,
+ BVHTree_OverlapCallback callback,
+ void *userdata);
int *BLI_bvhtree_intersect_plane(BVHTree *tree, float plane[4], uint *r_intersect_num);
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index de71147f015..e8de19bb7c5 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -95,6 +95,7 @@ BLI_STATIC_ASSERT((sizeof(void *) == 8 && sizeof(BVHTree) <= 48) ||
typedef struct BVHOverlapData_Shared {
const BVHTree *tree1, *tree2;
axis_t start_axis, stop_axis;
+ bool use_self;
/* use for callbacks */
BVHTree_OverlapCallback callback;
@@ -448,6 +449,15 @@ static void node_join(BVHTree *tree, BVHNode *node)
break;
}
}
+
+ /* Update the main axis and reorder children along it.
+ * The expectation is that the coordinates change slowly and thus
+ * no changes are required in most of the cases. */
+ const char split_axis = get_largest_axis(node->bv);
+
+ node->main_axis = split_axis / 2;
+
+ bvh_insertionsort(node->children, 0, node->node_num, split_axis);
}
#ifdef USE_PRINT_TREE
@@ -1090,6 +1100,13 @@ static bool tree_overlap_test(const BVHNode *node1,
return 1;
}
+/** Dimension of the node along the main axis. */
+MINLINE float tree_node_main_dimension(const BVHNode *node)
+{
+ const float *bv = node->bv + (node->main_axis << 1);
+ return bv[1] - bv[0];
+}
+
static void tree_overlap_traverse(BVHOverlapData_Thread *data_thread,
const BVHNode *node1,
const BVHNode *node2)
@@ -1121,6 +1138,14 @@ static void tree_overlap_traverse(BVHOverlapData_Thread *data_thread,
}
}
}
+ else if (node2->node_num &&
+ tree_node_main_dimension(node2) > tree_node_main_dimension(node1)) {
+ for (j = 0; j < data->tree2->tree_type; j++) {
+ if (node2->children[j]) {
+ tree_overlap_traverse(data_thread, node1, node2->children[j]);
+ }
+ }
+ }
else {
for (j = 0; j < data->tree1->tree_type; j++) {
if (node1->children[j]) {
@@ -1168,6 +1193,14 @@ static void tree_overlap_traverse_cb(BVHOverlapData_Thread *data_thread,
}
}
}
+ else if (node2->node_num &&
+ tree_node_main_dimension(node2) > tree_node_main_dimension(node1)) {
+ for (j = 0; j < data->tree2->tree_type; j++) {
+ if (node2->children[j]) {
+ tree_overlap_traverse_cb(data_thread, node1, node2->children[j]);
+ }
+ }
+ }
else {
for (j = 0; j < data->tree1->tree_type; j++) {
if (node1->children[j]) {
@@ -1231,6 +1264,62 @@ static bool tree_overlap_traverse_num(BVHOverlapData_Thread *data_thread,
return false;
}
+/** Calls the appropriate recursive overlap traversal function. */
+static void tree_overlap_invoke_traverse(BVHOverlapData_Thread *data,
+ const BVHNode *node1,
+ const BVHNode *node2)
+{
+ if (data->max_interactions) {
+ tree_overlap_traverse_num(data, node1, node2);
+ }
+ else if (data->shared->callback) {
+ tree_overlap_traverse_cb(data, node1, node2);
+ }
+ else {
+ tree_overlap_traverse(data, node1, node2);
+ }
+}
+
+/** Self-overlap traversal with callback. */
+static void tree_overlap_traverse_self_cb(BVHOverlapData_Thread *data_thread, const BVHNode *node)
+{
+ for (int i = 0; i < node->node_num; i++) {
+ /* Recursively compute self-overlap within each child. */
+ tree_overlap_traverse_self_cb(data_thread, node->children[i]);
+
+ /* Compute overlap of pairs of children, testing each one only once (assume symmetry). */
+ for (int j = i + 1; j < node->node_num; j++) {
+ tree_overlap_traverse_cb(data_thread, node->children[i], node->children[j]);
+ }
+ }
+}
+
+/** Self-overlap traversal without callback. */
+static void tree_overlap_traverse_self(BVHOverlapData_Thread *data_thread, const BVHNode *node)
+{
+ for (int i = 0; i < node->node_num; i++) {
+ /* Recursively compute self-overlap within each child. */
+ tree_overlap_traverse_self(data_thread, node->children[i]);
+
+ /* Compute overlap of pairs of children, testing each one only once (assume symmetry). */
+ for (int j = i + 1; j < node->node_num; j++) {
+ tree_overlap_traverse(data_thread, node->children[i], node->children[j]);
+ }
+ }
+}
+
+/** Calls the appropriate recursive self-overlap traversal. */
+static void tree_overlap_invoke_traverse_self(BVHOverlapData_Thread *data_thread,
+ const BVHNode *node)
+{
+ if (data_thread->shared->callback) {
+ tree_overlap_traverse_self_cb(data_thread, node);
+ }
+ else {
+ tree_overlap_traverse_self(data_thread, node);
+ }
+}
+
int BLI_bvhtree_overlap_thread_num(const BVHTree *tree)
{
return (int)MIN2(tree->tree_type, tree->nodes[tree->leaf_num]->node_num);
@@ -1243,20 +1332,20 @@ static void bvhtree_overlap_task_cb(void *__restrict userdata,
BVHOverlapData_Thread *data = &((BVHOverlapData_Thread *)userdata)[j];
BVHOverlapData_Shared *data_shared = data->shared;
- if (data->max_interactions) {
- tree_overlap_traverse_num(data,
- data_shared->tree1->nodes[data_shared->tree1->leaf_num]->children[j],
- data_shared->tree2->nodes[data_shared->tree2->leaf_num]);
- }
- else if (data_shared->callback) {
- tree_overlap_traverse_cb(data,
- data_shared->tree1->nodes[data_shared->tree1->leaf_num]->children[j],
- data_shared->tree2->nodes[data_shared->tree2->leaf_num]);
+ const BVHNode *root1 = data_shared->tree1->nodes[data_shared->tree1->leaf_num];
+
+ if (data_shared->use_self) {
+ /* This code matches one outer loop iteration within traverse_self. */
+ tree_overlap_invoke_traverse_self(data, root1->children[j]);
+
+ for (int k = j + 1; k < root1->node_num; k++) {
+ tree_overlap_invoke_traverse(data, root1->children[j], root1->children[k]);
+ }
}
else {
- tree_overlap_traverse(data,
- data_shared->tree1->nodes[data_shared->tree1->leaf_num]->children[j],
- data_shared->tree2->nodes[data_shared->tree2->leaf_num]);
+ const BVHNode *root2 = data_shared->tree2->nodes[data_shared->tree2->leaf_num];
+
+ tree_overlap_invoke_traverse(data, root1->children[j], root2);
}
}
@@ -1273,9 +1362,12 @@ BVHTreeOverlap *BLI_bvhtree_overlap_ex(
bool overlap_pairs = (flag & BVH_OVERLAP_RETURN_PAIRS) != 0;
bool use_threading = (flag & BVH_OVERLAP_USE_THREADING) != 0 &&
(tree1->leaf_num > KDOPBVH_THREAD_LEAF_THRESHOLD);
+ bool use_self = (flag & BVH_OVERLAP_SELF) != 0;
/* 'RETURN_PAIRS' was not implemented without 'max_interactions'. */
BLI_assert(overlap_pairs || max_interactions);
+ /* Self-overlap does not support max interactions (it's not symmetrical). */
+ BLI_assert(!use_self || tree1 == tree2 && !max_interactions);
const int root_node_len = BLI_
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list