How to sort and compare in a Bounding Volume Hierarchy

Question

I'm currently implementing a Bounding Volume Hierarchy for 3D-Triangles only. Sadly all explanations of BVH fall short on the part where you sort your Objects for splitting. For starters I want to aim for a balanced tree and use the median cut. This would require me to sort either the triangles or their bounding boxes(AABB) after a spatial criterion on the split axis of the current node. I'm really unsure if the maximum or minimum extend of a BB or triangle is enough for a proper separation as some triangles can be bigger. I'm also unsure if it's better to compare the bounding box or the triangle.

The second part of the problem is that sorting every step seems to be expensive. Other algorithms in computer-graphics employ presorted lists and then split those according to the splitting criterion. I don't see a way how you could efficiently compare triangles and assure that they belong to a list. Does that mean I have to sort the list every step?

Answer 1

You have multiple options, as you've discovered. The easiest to think about is to use the centroid of the bounding box. You could also sort by the min coordinate and separately by the max coordinate.

You can sort by each axis as a preprocess. Then each iteration is a partitioning that involves choosing which axis to split on and where to split, and storing the start/end points in that axis's sorted list.

See Ingo Wald's paper: http://www.sci.utah.edu/~wald/Publications/2007/FastBuild/download/fastbuild.pdf

The faster, lower quality approach is a linearized BVH - map each centroid to a coordinate on a space filling curve, such as a Morton code, then sort all the triangles by their Morton code, then split spans into boxes.

Answer 2

SAH (Surface Area Heuristic) is the most common way to evaluate where to split a set of triangles in BVH used for raytracing. You can find a good explanation on chapter 4 of PBRT book (http://www.pbrt.org). It is available for free here: http://pbrt.org/pbrt-2ed-chap4.pdf

If you have even a vague interest in raytracing, I suggest you to buy the complete book.