HappyCoder said:
The second is to allow any node, not just the leaf nodes, contain triangles in the quadtree. If a triangle crosses a separating boundary you move it up into the parent node until it is fully contained in a single node.
That’s bad, because many triangles then end up in the root node. In fact any triangle which spans the origin. And that’s just the worst case – many other triangles end up in internal nodes at high levels as well.
I know many tutorials propose this, but it’s really bad imo.
The proper solution is to use a ‘loose quadtree’, which allows to extend the quad bound of each node so the quad has twice the size and 4 times the area. This avoids the problem, but requires to traverse more (nearby) nodes in practice.
Still it’s usually a win, also because each triangle still goes only into one node, and the tree level of each triangle is defined only from triangle size, not it’s position.
That just said fyi. Obviously tabys triangles are already sliced by a grid, so no need for loose quadtree or BVH.
And even if the data can be sparse as shown in later images, i’d still use a simple regular grid. Trees likely take more memory than that and are expensive to build and traverse. It does not look like the advanced algorithms give us a win here.
taby said:
Thank you for your guidance, no matter what. I had never heard of BVHs before, so I’m learning as I go. LOL
Even if overkill, it’s opportunity to learn. Trees may be ‘slow’, but are still part of the solution of almost any serious performance problem, imo.
So i did a little BVH tutorial. But it’s an advanced one.
Usually we would start with recursive and branchy crap, generating nodes scattered in random order across memory, just to explain how it’s meant to work.
But for that you can look up any tutorial on the internet. I’ll rather show you a good solution avoiding those problems, even if it’s a bit harder to understand. ; )
You see many objects, and after we have built the tree, i have rendered them with color code from memory index, with the lines showing the next object.
Notice what we get looks like a Z curve. Objects close in space are also mostly close in memory. That’s a property we want for any tree, to minimize cache misses while traversing and processing it.
This is important but often not mentioned.
If you look at my code to build the tree, it looks like an in place sort algorithm, constantly reordering the objects in memory to refine spatial and memory order.
And while we do this, we also create a tree, which is like a record storing all the sorting decisions we made. This relationship also is rarely mentioned, but important.
Basically the build process is like this: Make all objects leaf nodes and children of the root node. Split the roots bounding box into 4 quadrants from it’s center, then make 4 new children from the quadrants, sorting in the leafs accordingly. Then we repeat this process for all the new children we have just created.
That’s almost the same process as building a quadtree, and there are many other variants. E.g. making a binary tree by splitting the longest side of the bounding box, or advanced methods like minimizing bounding volume or surface area.
Please ask if you have any questions.
The other thing you see is a white query box (hard to see), and all nodes we traverse while finding objects in that box.
When traversing the tree, we have a big difference to a basic quad tree: Because bounds of child nodes may overlap, we need to traverse multiple of them, so we need a stack. This holds even if we only did a simple point query.
However, due to the issues mentioned at the start of the post, we usually get the same ‘disadvantage’ also when using a quad/octtree in practice.
But there is one general advantage of BVH over quad/octree: Flexibility. If our objects move, we can keep the topology of the tree. We only need to update the bounds to reflect the changes. (‘refitting’)
Contrary, if we use a quadtree and our objects move, we need to rebuild the tree from scratch. Because the node bounds depend on global space and can not move with our objects.
But ofc. quadtree nodes do not need memory to define bounds or any spatial positions, which is a general advantage over BVH.
static bool testSimpleBVH = 1; ImGui::Checkbox("testSimpleBVH", &testSimpleBVH);
{
// make some random objects
struct Object
{
vec2 pos;
float radius;
Object()
{
pos = vec2( float(std::rand()) / float(RAND_MAX), float(std::rand()) / float(RAND_MAX));
radius = 0.01f + 0.03f * float(std::rand()) / float(RAND_MAX);
}
};
static std::vector<Object> objects(1000);
for (auto &obj : objects) RenderCircle(obj.radius, obj.pos, vec(0,0,1), 0,0,0);
// we use an axis aligned bounding box for our bounding volume
struct AABox
{
vec2 minmax[2];
void Init ()
{
minmax[0] = vec2 (FLT_MAX, FLT_MAX);
minmax[1] = vec2 (-FLT_MAX, -FLT_MAX);
}
void Extend (const AABox &b)
{
minmax[0][0] = min (minmax[0][0], b.minmax[0][0]);
minmax[0][1] = min (minmax[0][1], b.minmax[0][1]);
minmax[1][0] = max (minmax[1][0], b.minmax[1][0]);
minmax[1][1] = max (minmax[1][1], b.minmax[1][1]);
}
vec2 Center () const
{
return (minmax[0] + minmax[1]) * 0.5f;
}
bool BoundsPoint (const vec2 point) const
{
for (int i=0; i<2; i++)
{
if (point[i] < minmax[0][i] || point[i] > minmax[1][i])
return false;
}
return true;
}
bool IntersectsBox (const AABox &box) const
{
for (int i=0; i<2; i++)
{
if (box.minmax[1][i] < minmax[0][i] || box.minmax[0][i] > minmax[1][i])
return false; // disjoint
}
return true; // intersecting
}
static AABox& Empty()
{
static AABox empty = {vec2 (FLT_MAX, FLT_MAX), vec2 (-FLT_MAX, -FLT_MAX)};
return empty;
}
};
// BVH
struct BVHNode
{
AABox bound;
int firstChild; // if negative, it's an index to a triangle
int childCount;
};
// build BVH
const int levels = 4;
// create leaf per object, and make them all children of the root
std::vector<BVHNode> leafNodes (objects.size());
std::vector<BVHNode> tree (1);
constexpr int rootIndex = 0;
BVHNode &root = tree[rootIndex];
root.bound.Init();
for (int i=0; i<(int)objects.size(); i++)
{
Object &obj = objects[i];
BVHNode &leaf = leafNodes[i];
leaf.bound.minmax[0] = obj.pos - vec2(obj.radius, obj.radius);
leaf.bound.minmax[1] = obj.pos + vec2(obj.radius, obj.radius);
leaf.firstChild = -1 - i;
leaf.childCount = 0;
// extend root box
root.bound.Extend(leaf.bound);
}
root.firstChild = 0;
root.childCount = objects.size();
RenderAABBox (root.bound.minmax[0], root.bound.minmax[1], 1,0,0);
// build internal hierarchy
std::vector<int> stack;
stack.push_back(rootIndex); // add root to process
int head = 0;
int tail = 1;
std::vector<BVHNode> reorderedLeafs (objects.size()); // temporary buffer storing leafs in sorted order
for (int level=0; level<levels; level++) // for each iteration adding one new level of hierarchy
{
int sortedIndex = 0; // we use this to reorder leafs to the newly sorted state after adding the level
for (int i=head; i<tail; i++) // process all nodes of the current level, now becoming parents to subdivide
{
int parentIndex = stack[i];
BVHNode &parent = tree[parentIndex];
vec2 parentCenter = parent.bound.Center();
// we make a simple BVH4, so subdividing children into quadrants from the center of the parent bound
int qCount[4] = {0,0,0,0}; // for each quadrant, count how many leafs are in
AABox qBox[4] = {AABox::Empty(), AABox::Empty(), AABox::Empty(), AABox::Empty()}; // for each quadrant make a new bound
int firstChild = parent.firstChild;
int childCount = parent.childCount;
for (int n=0; n<childCount; n++)
{
int leafIndex = firstChild + n;
BVHNode &leaf = leafNodes[leafIndex];
vec2 diff = leaf.bound.Center() - parentCenter;
int quadrant = (diff[0] > 0) | ((diff[1] > 0)<<1);
leaf.childCount = (qCount[quadrant]<<2) | quadrant; // we alias this variable to store the leafs new subindex + quadrant
qCount[quadrant]++;
qBox[quadrant].Extend(leaf.bound);
}
// create new children from quadrants
int firstQuadrantIndex[4];
int newFirstChild = -1;
int newChildCount = 0;
for (int q=0; q<4; q++) if (qCount[q])
{
int newChildIndex = (int)tree.size();
if (newFirstChild == -1)
newFirstChild = newChildIndex;
newChildCount++;
tree.push_back(BVHNode());
BVHNode &newChild = tree.back();
newChild.bound = qBox[q];
newChild.childCount = qCount[q];
newChild.firstChild = sortedIndex;
firstQuadrantIndex[q] = sortedIndex;
sortedIndex += qCount[q];
stack.push_back(newChildIndex); // refine further
}
tree[parentIndex].firstChild = newFirstChild;
tree[parentIndex].childCount = newChildCount;
// iterate children again, to calculate their final newly sorted index and reordering them accordingly
for (int n=0; n<childCount; n++)
{
int leafIndex = firstChild + n;
BVHNode &leaf = leafNodes[leafIndex];
int quadrant = (leaf.childCount & 3);
int subIndex = (leaf.childCount)>>2;
int newIndex = firstQuadrantIndex[quadrant] + subIndex;
assert(newIndex < (int)leafNodes.size());
//leaf.childCount = newIndex; // alias again to store the leafs newly sorted index
reorderedLeafs[newIndex] = leaf;
}
}
// reorder the leafs
/*for (int i=0; i<(int)leafNodes.size(); i++)
{
BVHNode &leaf = leafNodes[i];
int newIndex = leaf.childCount;
assert(newIndex < (int)reorderedLeafs.size());
reorderedLeafs[newIndex] = leaf;
}*/
std::swap(reorderedLeafs, leafNodes);
head = tail;
tail = (int)stack.size();
ImGui::Text("build level %i completed. head %i tail %i", level, head, tail);
}
// add leafs to tree
int offset = (int)tree.size();
std::copy(leafNodes.begin(), leafNodes.end(), std::back_inserter(tree));
for (int i=head; i<tail; i++)
{
int parentIndex = stack[i];
BVHNode &parent = tree[parentIndex];
parent.firstChild += offset;
}
// visually proof sorted order from color pattern
vec2 prevCenter;
if (1) for (int i=0; i<(int)leafNodes.size(); i++)
{
BVHNode &leaf = leafNodes[i];
float t = float(i) / float(leafNodes.size()) * 0.66f;
vec2 center = leaf.bound.Center();
RenderPoint(center, Vis::RainbowR(t), Vis::RainbowG(t), Vis::RainbowB(t));
if (i) RenderLine(center, prevCenter, Vis::RainbowR(t), Vis::RainbowG(t), Vis::RainbowB(t));
prevCenter = center;
}
// do some range query using the BVH
AABox query;
query.minmax[0] = vec2(.5f, .6f);
query.minmax[1] = vec2(.6f, .8f);
stack.clear();
stack.push_back(rootIndex);
head = 0;
tail = 1;
for (int level=0; level<=levels; level++) // each iteration traverses one level of the hierarchy in breadth first order
{
ImGui::Text("traverse level %i...", level);
for (int i=head; i<tail; i++) // traverse all nodes of the current level
{
int parentIndex = stack[i];
const BVHNode &parent = tree[parentIndex];
int firstChild = parent.firstChild;
int childCount = parent.childCount;
ImGui::Text(" traverse %i children of node %i...", childCount, parentIndex);
for (int n=0; n<childCount; n++)
{
int childIndex = firstChild + n;
const BVHNode &child = tree[childIndex];
if(!child.bound.IntersectsBox(query))
continue;
float t = float(level) / float(levels) * 0.66f;
RenderAABBox (child.bound.minmax[0], child.bound.minmax[1], Vis::RainbowR(t), Vis::RainbowG(t), Vis::RainbowB(t));
if (level<levels)
stack.push_back(childIndex);
else
{
int objectIndex = -child.firstChild -1;
//ImGui::Text(" found object %i", objectIndex);
const Object &obj = objects[objectIndex];
RenderCircle(obj.radius, obj.pos, vec(0,0,1), 1,1,1);
}
}
}
head = tail;
tail = (int)stack.size();
}
RenderAABBox (query.minmax[0], query.minmax[1], 1,1,1);
}
