Raytracer - What are the standard approaches for finding the the next ray intersection point and what are their pros and cons

Question

I am not asking how to compute the intersection point of a ray with a specific primitive, I am asking what the current approaches are to determining as quickly as possible which of the millions of primitives in the scene is the next one the ray intersects.

I have heard that octtrees and kd-trees are commmonly used. I don't know whether there are other methods that are also current contenders.

If octrees are used, does one simply allow each cube to keep track of whether any of its 8 subcubes intersects any goemetry? Any that don't get no corresponding branch and each subcube that does gets a branch. Thus one descends down the tree until one finds a final node which gives a limited number of primitives that it intersects? If one builds such an octree one can trace rays by moving one's ray from its starting point through the cubes descending in each to the point where one can either verify the ray meets no geometry in the cube or descend to the point where one can check against a small number of primitives (which the ray might miss, requiring one to move on to the next cube)?

Anyway, the question of how one finds the next intersection looks like a huge performance factor so what are the top approaches currently and what are their pros and cons?

Answer 1

The most widely used acceleration structure today are BVH (*B*ounding *V*olume *H*ierarchies), and they are the subject of much current research (2 of the top 3 best papers from High Performance Graphics 2013 are on BVHs: HPG Best Papers).

The wikipedia page on BVHs is a good starting point. The concept is very simple, group clusters of primitives into a bounding volume (often a bounding box), then group clusters of said bounding volumes into larger volumes, and repeat until at the highest level there is a single bounding volume for the whole scene. BVHs are fast to build, easy to implement, and are widely used.

Another, previously popular, alternative is k-d trees, however they take up to an order of magnitude longer to build than BVHs and tend to require more memory; octrees work, but are not widely used.

Recently there have been a family of approaches to incoherent ray tracing called divide-and-conquer, which basically do the primitive partitioning normally done in k-d tree or BVH construction on the fly during ray traversal. This can be a bit faster than building the full acceleration structure then tracing, if some parts of the scene don't have any rays intersecting them (since in the divide-and-conquer approach, those primitives would never need to be partitioned), but you then have to repeat the process every time you have a new batch of rays you wish to trace. For coherent rays or a mostly static scene, this approach is not a great idea, and its questionable whether its worth it even on scenarios tailored to play to the algorithms strengths.

Personal recommendation: use a BVH.

Answer 2

This is a very large topic. You can find some information on tis website www.scratchapixel.com. Look at the lesson on acceleration techniques. Ray tracing is slow (computers are actually), thus doing a naive ray-triangle intersection tests in which you test all the triangles of the scene, becomes quickly prohibitively expensive. To leverage the problem you can use acceleration structures and you mentioned some techniques in your post (octrees, k-d trees). The performance of one vs the other is very subjective, depends on your implementation, what you need it for, etc. Both BVH and k-d trees are considered good. You can easily find papers on the web in which the authors reviews the different type of acceleration structures, their pros and cons, etc. Such for acceleration structure survey. The trend these days are techniques where the acceleration structures are not stored in memory but created on the fly as the rays are cast.