3

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?

Vertexwahn
  • 7,709
  • 6
  • 64
  • 90
funkysash
  • 198
  • 2
  • 12

2 Answers2

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.

All The Rage
  • 743
  • 5
  • 24
  • Thanks for you answer. The binning and cost calculation done in the paper seems to be to much for what I wanted to do. I'm still unsure on what to choose. Centroids seem to be a good idea, but I don't see the downsides or advantages compared to sorting by min and max. I also don't understand how storing the start/end point would help me. – funkysash Feb 24 '13 at 15:31
  • 1
    Use centroids. Min and max are squirrely if you have the general case of long, oriented triangles but don't want the special logic of both min and max. The start/end indices into a sorted list represent the span that belongs to one box. You subdivide the span as you recurse. – All The Rage Mar 05 '13 at 03:57
1

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.

Dade916
  • 305
  • 1
  • 4