I'm working on the terrain portion of my engine at the moment, trying to implement walking on terrain surfaces. I have done some research and so far I've settled on using a ray trace to find the triangle that the character controller is currently hovering over. The problem is that my mesh has lots of triangles and it takes quite some time to go through every one of them to find a ray-triangle intersection. I've asked this in another forum on here and I was recommended to try and use a spacial partitioning structure, more specifically bounding volume hierarchy. I've done a few hours of research just reading through all the papers I could find, but most of them deal with multiple meshes. I was wondering if anyone could help me out with just a basic outline of the process involved of creating and using a BVH tree for a single terrain mesh. You don't really have to go into detail, I'll try to do the research on my part, but if you can just give me a breakdown of the steps I need to do in order to use it, It'd be really great. Also if you know any good, relevant resources/papers I'd like to know too (at the moment I'm reading a chapter on BVH in Christer Ericson's book Real-Time Collision Detection). Thanks in advance.

5 minutes ago, JoeJ said:

First, if your terrain has no overhangs / caves you don't need a tree but just a lookup into the height map.

 Second, even if it has, a 2D regular grid might still beat BVH because the geometry is mostly evenly distributed across the plane.

 (For a spherical planet just use 6 heighnmaps / grids in a cube map fashion.)

 

Building a binary BVH can work like this:

1. Calc bounding box over entire scene, make it the root node and link all triangles to it.

2. Split along the longest axis of the box. Assuming x axis is longest, you sort triangles along x axis. Then split into two sets of triangles so both sides have the same number of triangles, or (usually better) choose the split to minimize surface area of both resulting bounding boxes.

3. Make the 2 boxes child nodes of the parent and link triangles accordingly. (bounding boxes will overlap a bit, but that's no problem.)

 4. Repeat recursively with step 2 until no node has more triangles than a given constant number.

  

It is often better to have a BVH with more children than just two (MBVH). For example you can use 8 chaildren and choose the split point at the geometrical center of the parent box, or at the center of mass from all triangles, or minimaze surface area again, etc.

This gives tha advantage that all children of any parent can be linear in memory so less chache misses, and also less levels of the hierarchy.

Thanks, that's similar to what I've read so far. It seems pretty straight forward but I just have one thing that I'm not entirely sure about.

Lets say I have a mesh (as I do now) in this format:

	struct Object
	{
	Vertex* vertexList;
	int numVertices;
	std::vector<DWORD> indexList;
	}
	

For step 1 and 2 you say "link triangles" to the bounding volume, how would I do that? In other words how would I associate the triangles in one part of a mesh with a bounding a specific bounding volume?

On 8/14/2019 at 2:49 AM, JoeJ said:

The most efficient way might be to reorder the triangles in memory, so changing the mesh.

So e.g. we have initally 8 triangles in the mesh in order 12345678.

After the sorting and the split you may get (1325) (4687).

And after adding one more hierarchy level both sets become reordered again to something like ((12)(35)) ((47)(68)).

So the whole indexing shuffles, but in the end the triangles close in space are also close in memory, which is good to avoid cache misses. (For the MBVH with 8 children i get sets having Z-curve order in memory, which is the same layout GPUs use to optimize textures in memory to increase cache efficiency.)

If you do this you can link a node to its triangles just with two numbers (index to the first triangle and count).

  

The alternative would be to have a list of triangles per node, e.g. a start index per node and a next index per triangle.

(Assuming you build the tree just once offline, you can also use a std::vector of triangle indices per node to keep it slow but simple, and care for the triangle reordering after the tree has been built.)

 

I have never tried, but it may be even worth to store the triangles not as 3 indices to shared positions, but as just 3 positions directly. However, while raytracing you usually have much more ray-bbox tests than ray-triangle tests, so not sure if it's worth to spend so much more memory just to get rid of some indirection.

 

Thanks, this definitely puts me on the right track. I appreciate all your help!

@JoeJ

I was just wondering if you can answer another question. I'm now looking all your steps and comparing them to the Real-Time Collision Detection book chapter, and it appears you're using a top-down method of tree construction, and the "seperation method" would be median-cut since we're splitting the root bounding volume half way down, but the next question is exactly how would I judge if the triangles in this longest-axis box are "less-than" other triangles in order to organize them along the longest axis prior to the split? To illustrate what I'm confused about: Lets say the longest axis is x, so you said I have to organize the triangles on that axis. So would I just take the averages of all three vertices of the triangles like so (v0.x + v1.x + v2.x) / 3 and use that as the x position of the triangle and then compare that to the averages of other triangles to find their order? Or should I just use the vertex with the least x and then categorize based on that? Thanks.

5 hours ago, JoeJ said:

(Assuming your triangles have roughly the same size. If you had some very large triangles it could make sense to store them in internal nodes, and thinking about just points / centers no longer works. In contrast, thinking about boxes always works, no matter if your goal is raytracing or searcing for potential colliders, using BVH or octree, for triangles or capsules, etc.)

Thanks for sticking with me on this one, really appreciate your time. Looks like I'm ready to go!