Bounding Volume Hierarchy, how to handle out out volume positions?

Recommended Posts

I'm trying to implement walking on a polygonal mesh terrain. I've chosen to use the ray-trace method (by shooting a ray from the player position downward until it hits a terrain triangle) to find out the height of the terrain at that point. I'm using BVH approach to segment the space around the level so that I only have to ray-trace a small number of triangles.

However I'm having trouble conceptualizing the following scenario (see the image for an illustration). Lets say the player jumps up over the bounding volumes (or dives off a cliff or out of plane). If you look at Player Position 1 in the image I've attached, the player is located in the largest bounding volume of the word, meaning that I'd still have to iterate over every triangle in the world to find the position. Also if you look at Player Position 2, how would I even handle that? Since the player is completely outside of the terrain bounding box.

I

Share on other sites

Presumably there is a root bounding box.  If you are out of the tree you just start checking at the top. Also with a hierarchy not everything is supposed to be directly under the root.  By your description it sounds like that's your issue.  Your hierarchy should be several levels deep otherwise, what's the point.  So as an example if you were using an octree, you have a root and that has 8 children. Then each child may have 8 children and so forth.  There are some variations with this. Sometimes triangles are only stored in leaf nodes of the tree.  In other implementations they are stored at all levels.

I will also add, in the long run doing collision this way may be a dead end (depending on how for you want to go with it).  First doing proper collision response might be tricky. Second, once you get things like trees and houses into your world which are no longer really height mapped, you're method won't be able to handle it.

Share on other sites
1 hour ago, Gnollrunner said:

Presumably there is a root bounding box.  If you are out of the tree you just start checking at the top. Also with a hierarchy not everything is supposed to be directly under the root.  By your description it sounds like that's your issue.  Your hierarchy should be several levels deep otherwise, what's the point.  So as an example if you were using an octree, you have a root and that has 8 children. Then each child may have 8 children and so forth.  There are some variations with this. Sometimes triangles are only stored in leaf nodes of the tree.  In other implementations they are stored at all levels.

I will also add, in the long run doing collision this way may be a dead end (depending on how for you want﻿ to go with it).  ﻿﻿First﻿ doing proper collision response might be tricky. Second, once you ﻿get things like trees and houses﻿ into your world which﻿ are no﻿﻿ longer really﻿ height mapped﻿﻿﻿﻿﻿, you're method wo﻿n't﻿ be able to handle it. ﻿﻿﻿

There is a root bounding box, in the image you see it as the navy blue box that surrounds the red bounding boxes (which are bounding boxes for individual triangles). But if the player is located only in the root bounding box and not in any of it's children bounding boxes (as Player Position is in the image), doesn't that mean I have to check every triangle in the terrain for collision? Also I'm using a binary tree, and I store triangles in every level of the tree.

Also can you elaborate why this wouldn't work for things like houses and trees? I'm not using heightmaps, so I'd imagine the triangles of a house or a tree (if it's a part of the terrain) would just get mapped to the bvh tree like the rest of the terrain, or that wouldn't work for some reason? If not what would be a more wholesome approach that would work in every case?

Share on other sites
Posted (edited)
1 hour ago, VanillaSnake21 said:

doesn't that mean I have to check every triangle in the terrain for collision?

No, it can not happen you have to check all triangles. There are usually 2 things that you do with a tree (BVH or octree does not matter):

Raytracing: Usually you have a stack per ray, and you begin with putting the root node on the stack if it intersects the ray. Then, recursively pop a node from stack, test its child bounding boxes for ray intersection, and push them to the stack as well if they interect.

So you process only the nodes if their boxes intersect the ray, and no matter what ray origin / direction, it will never be the whole scene (Assuming the scene has higher complexity than the image that justifies using a tree.)

Neighbour search / box queries: Here you want to find all triangles/objects in a givien region, usually defined by a bounding box. Usuful for example for broadphase collision detection to find potential colliding pairs. You would make the query box from the object in question extruded by its velocity.

Algorithm is the same, just replace ray-box intersection test with querybox-boundingbox overlap test. The stack finally contains all overlapping nodes from the tree, but again not the whole scene.

Seems what you're missing is the recursive / subdividing / hierarchical nature of the process?

1 hour ago, VanillaSnake21 said:

Also can you elaborate why this wouldn't work for things like houses and trees? I'm not using heightmaps, so I'd imagine the triangles of a house or a tree (if it's a part of the terrain) would just get mapped to the bvh tree like the rest of the terrain

You're right. Likely @Gnollrunner assumed your terrain would be just a height map? (No tree would be necessary in that case).

Some details: Physics engine usually support hight maps as a special case. But still it is possible to put them in to a BVH like any other object.

In raytracing it is common to sort the intersecting children by ray distance before putting tham on the stack, so closer intersections can be found first. This shortens the ray and will cull nodes behind that for a spped up. (It's also possible to RT without a stack using per node skip pointer which permits that option).

Edited by JoeJ

Share on other sites
19 minutes ago, JoeJ said:

You're right. Likely @Gnollrunner assumed your terrain would be just a height map?

Not exactly. I know it's not stored as a hightmap ,but essentially right now it looks like height mapped terrain.

2 hours ago, VanillaSnake21 said:

Also can you elaborate why this wouldn't work for things like houses and trees?﻿

Characters aren't single points. They should have some bounding volume associated with them. If you walk over a small crack in the terrain. You don't fall through it just like in real life.  As another example, If you're walking along, your head may run into a overhanging branch. It shouldn't go though it. Also how do you intend to go up stairs?  Most of the time some sort of bounding volume is used that can slide along the mesh.  This can be a ellipsoid, multiple spheres or a pill. It can be other shapes too but these are commonly used because the calculation is easier.  The only time I've seen casting a ray downward being used, is when you are only on an (essentially)  hightmapped surface and you simply move your character forward and then set his feet at the new height.  But this is pretty crude and not really suitable for most games.

As for the BVH tree, that parts fine. You just need to use it the right way.  You don't really need to cast a ray downward.  You have the point where you are, and you have the point where you are tying to get to.  That means you have a vector. You need to take that vector  and go through your tree and see what triangles collide with it. When you find the nearest one you do collision response and generate a new movement vector.  But again using a single point isn't realy going to work very well. You need some bounding volume around it if you intend to have any semblance of realism.

You can of course use your method right now with the terrain you have if you just want to get something basic working.  I'm just explaining there are some limitations with it.

Share on other sites
12 minutes ago, Gnollrunner said:

I'm just explaining there are some limitations with it.

Ah ok, i get what you mean.

Personally i have also used spheres / capsules for vehicle wheels or characters and queries mentioned above to find a set of triangles for penetration tests. Not easy to make robust, but worked for my simple needs. I agree raytracing won't work well if the terrains are not pretty flat.

(I have no experience with ray traced collision detection using minkovski sums and could not help with this. Also i don't know if such approaches are used for concave stuff like terrain at all in practice... would be a topic for the physics experts here.)

Share on other sites

@Gnollrunner I see what you mean, I actually do have a collision box associated with a character, I suppose I can just check the triangles inside the BVH volume that my character is in for collision instead of just using a ray? At this moment I'm just using a single point to see if I can get the BVH to work correctly.

Quote

No, it can not happen you have to check all triangles. There are usually 2 things that you do with a tree (BVH or octree does not matter﻿😞

Quote

Seems what you're missi﻿ng is the r﻿ecursive / subdividing / hierarchical nature of the process?

Yea I think I'm missing some part of the process of building the tree. This is my current approach:

1. I go through every triangle in the terrain and generate a bounding box around that triangle

2. I sort all the triangles and their respective bounding boxes along the longest axis of the terrain

3. I find a bounding box surrounding the entire terrain, essentially the bounding box that contains all the bounding boxes of the triangles, and assign that to the root node

4. I split list of organized triangles in half and find a bounding box that covers that split, I assign the one half of the list to the left branch of the binary tree and the other side of the list to the right branch.

5. I go on splitting the list until each leaf contains about 100 triangles

I don't want to overwhelm with code but I'll try to keep it as short as possible, this is those 5 steps as I have them in code right now:

struct _node
{
//pretty much the start and end index of the trianlges contained in this node
//in actuality they are the start and end indices of the bounding boxes that surround the triangles
//the bounding boxes themselves have indices to actual triangles
UINT start_box_index;
UINT end_box_index;

//the bounding volume surrounding the triangles defined by the indices above
_bounding_box bounding_box;

_node* leftChild;
_node* rightChild;

bool isRoot;
};

//I pass this method the root of an empty tree and the list of bounding boxes around each triangle, this list is organized according to
//the longest axis
void midpoint_split(_node* tree, const _bounding_box* const boundingBoxList, UINT numBoxesInList, UINT unitsPerLeaf = 100)
{
if (tree->isRoot)
{

//the root holds all the triangles in the terrain ( 0 to number_of_triangles )
tree->start_box_index = 0;
tree->end_box_index = numBoxesInList;

//find the volume of all the triangles the terrain
tree->bounding_box = FindBoundingBox(boundingBoxList, tree->start_box_index, tree->end_box_index);

//generate a left branch
tree->leftChild = new _node;
tree->leftChild->isRoot = false;

//split the list of triangles in half (0 to 1/2 list)
tree->leftChild->start_box_index = 0;
tree->leftChild->end_box_index = UINT(float(numBoxesInList) / 2.0f + 0.5f);

//just set the leaf nodes to null
tree->leftChild->leftChild = nullptr;
tree->leftChild->rightChild = nullptr;

//find the bounding box around that split half
tree->leftChild->bounding_box = FindBoundingBox(boundingBoxList, tree->leftChild->start_box_index, tree->leftChild->end_box_index);

//descend in order to generate the entire left branch
midpoint_split(tree->leftChild, boundingBoxList, numBoxesInList);

//generate the right branch
tree->rightChild = new _node;
tree->rightChild->isRoot = false;

//assign the other half to the right branch (1/2 list + 1 to end)
tree->rightChild->start_box_index = UINT(float(numBoxesInList) / 2.0f + 1 + 0.5f);
tree->rightChild->end_box_index = numBoxesInList;

tree->rightChild->leftChild = nullptr;
tree->rightChild->rightChild = nullptr;

tree->rightChild->bounding_box = FindBoundingBox(boundingBoxList, tree->rightChild->start_box_index, tree->rightChild->end_box_index);

midpoint_split(tree->rightChild, boundingBoxList, numBoxesInList);

}
else // this is done when the node passed in recursively is no longer the root
{
//find how many triangles are in this node
UINT numTrianglesInRange = tree->end_box_index - tree->start_box_index;

//if less than the set minimum then don't split further
if (numTrianglesInRange <= unitsPerLeaf)
return;

tree->leftChild = new _node;
tree->leftChild->isRoot = false;

//split the node in half
tree->leftChild->start_box_index = tree->start_box_index;
tree->leftChild->end_box_index = UINT(float(numTrianglesInRange) / 2.0f + 0.5f) + tree->start_box_index;

tree->leftChild->leftChild = nullptr;
tree->leftChild->rightChild = nullptr;

tree->leftChild->bounding_box = FindBoundingBox(boundingBoxList, tree->leftChild->start_box_index, tree->leftChild->end_box_index);

midpoint_split(tree->leftChild, boundingBoxList, numBoxesInList);

tree->rightChild = new _node;
tree->rightChild->isRoot = false;

tree->rightChild->start_box_index = tree->leftChild->end_box_index + 1;
tree->rightChild->end_box_index = tree->end_box_index;

tree->rightChild->leftChild = nullptr;
tree->rightChild->rightChild = nullptr;

tree->rightChild->bounding_box = FindBoundingBox(boundingBoxList, tree->rightChild->start_box_index, tree->rightChild->end_box_index);

midpoint_split(tree->rightChild, boundingBoxList, numBoxesInList);

}

}

Share on other sites
12 minutes ago, VanillaSnake21 said:

Yea I think I'm missing some part of the process of building the tree. This is my current approach:

No, what i mean is the process of traversing the tree (for trcing or queries), not how to build it.

But 'ill respond in more detail later the day, i see some issues with your building as well...

Share on other sites
1 minute ago, JoeJ said:

No, what i mean is the process of traversing the tree ﻿﻿(for ﻿trcing ﻿or queries), not how to build it.

﻿ But 'ill respond in more detail later the day, i see some issues﻿ with your building as well.﻿﻿..﻿﻿

Oh traversing? I use this method:

//outIndexStart and End are passed with -1 in the beginning to signify they're empty
void FindPointInTree(XMVECTOR point, const _node* tree, int* outIndexStart, int* outIndexEnd)
{

//check if the point is in the root node at all
if (tree->isRoot)
if (IsPointInBox(point, tree->bounding_box) == false)
return;

//if a left node exists see if the point belongs in that volume, then decend
if (tree->leftChild != nullptr)
if (IsPointInBox(point, tree->leftChild->bounding_box))
FindPointInTree(point, tree->leftChild, outIndexStart, outIndexEnd);

//outIndexStart and End are passed with -1 in the beginning to signify they're empty
//if we set them already then the point is already found and so no reason to test further
if (!(*outIndexStart == -1 && *outIndexEnd == -1))
return;

//otherwise search the right side
if(tree->rightChild != nullptr)
if (IsPointInBox(point, tree->rightChild->bounding_box))
FindPointInTree(point, tree->rightChild, outIndexStart, outIndexEnd);

//this part of code is only reached when the last leaf node is found
//at which point, just pass out the triangle indices caontined in that node
if (*outIndexStart == -1 && *outIndexEnd == -1)
{
*outIndexStart = tree->start_box_index;
*outIndexEnd = tree->end_box_index;
}

}

Thanks for looking over the code, I know it's a lot.

Share on other sites
Posted (edited)
5 hours ago, VanillaSnake21 said:

Oh traversing? I use this method:

Ok, so i see this is clear to you. Then maybe the reason for the initial confusion must me something else, but there is no reason for that anyways.

About your tree construction code, there is the problem you sort just once, but you have to select the splitting axis for each individual split and resort.

Here an 2D example with 3 levels:

1. Box is wider than high so choose X axis to split the root.

2. Both childs are now higher than wide, so choose Y now for both.

3. After calculating the bounding boxes, we see that 3 children are wider than high, but one became higher because there are no triangles in the top right area. So 3 children will use X, but one Y for the next split.

This is why you have to alternate splitting axis, and for the same reason the contained triangles need to be resorted again for each split as well along that changing axis.

The approach you seem to use would work only in the 1D case, but it's not enough for 2D/3D.

Some other, minor things:

There should be no need to handle the root node with special code neither for building nor for traversal (can be simplified).

Allocating new nodes with new (assuming there is no overloaeded momory management by your side here) can place them in fragmented memory positions. Instead you may want to write them just to an array or std::vector, so the nodes keep together. Order will be fine automatically. Both child nodes can be stored one after another, and you could use indices instead pointers. But you can care later for such optimizations.

Casting to float for rounding is not better than just numTrianglesInRange/2

Again no need to handle root node differently.

Bug: You return after the query point has been found to be in one of the children. But BVH bounds will overlap! So you still have to test and process the other child as well!

Example, bloe bot is the query point, if you would return after assigning it to theleft green child node, you would miss the collision with the box contained in right green child.

So, unfortunately with BVH or loose octree you have to traverse multiple branches because of overlaps.

Minor, but worth to mention: You use recursion for both traversal and build, this way the programming language manages the stack for you. I started with this too, but it may be not the best way to learn it, and it is not the most efficient way either. Managing the stack yourself lets you see what happens better. Difference between breath first / depth first becomes more clear, caching is better, dynamic allocation can be avoided.

The point query would look like this, as an example:

	std::vector<int> stack (totalNumberOfNodes); // don't need the stack to be so huge, but to keep it simple
stack[0] = root;
int tail = 1;
for (int i=0; i<tail; i++)
{
int current = stack[i]; // pop current node from stack, initially the root
int child = nodes[current].child; // left child
if (child == -1) continue; // skip if there are no children (i assume there are alwayes either both or none)
if (nodes[child].bBox.Contains(queryPoint)) stack[tail++] = child; // push child to stack
child++; // make it the right child
if (nodes[child].bBox.Contains(queryPoint)) stack[tail++] = child;
}


I hope i did that correctly. If so, after the traversal has completed the stack contains all nodes that enclose the query point. Just to show going without recusrion is not more complex or difficult, and having access to the stack is useful. Notice this is breadth first while your recursion leads to depth first. For RT the latter can be better.

But just to say - make it work first the way it's easiest for you and care for such things later.

5 hours ago, VanillaSnake21 said:

@Gnollrunner I see what you mean, I actually do have a collision box associated with a character, I suppose I can just check the triangles inside the BVH volume that my character is in for collision instead of just using a ray? At this moment I'm just using a single point to see if I can get the BVH to work correctly.

Not quite. If your character is more than just a point, it will end up being in multiple nodes (even if node bounds would not overlap). So you need to find all nodes that intersect, and test against all contained triangles.

But otherwise you are right, and if your character is made by a capsule it would work like so: Calc bounding box over the capsule, use it as query box to find all overlapping BVH nodes and test all triangles from that for intersection with the capsule.

Edited by JoeJ

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

• Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 12
• 14
• 10
• 33
• 23