# Fast, Branchless Ray/Bounding Box Intersections, Part 2: NaNs

In part 1, I outlined an algorithm for computing intersections between rays and axis-aligned bounding boxes. The idea to eliminate branches by relying on IEEE 754 floating point properties goes back to Brian Smits in [1], and the implementation was fleshed out by Amy Williams. et al. in [2].

# Exact Bounding Boxes for Spheres/Ellipsoids

Finding the tightest axis-aligned bounding box for a sphere is trivial: the box extends from the center by the radius in all dimensions. But once the sphere is transformed, finding the minimal bounding box becomes trickier. Rotating a sphere, for example, shouldn't change its bounding box, but naïvely rotating the bounding box will expand it unnecessarily. Luckily there's a trick to computing minimal bounding boxes by representing the transformed sphere as a quadric surface.

# A Beautiful Ray/Mesh Intersection Algorithm

In my last post, I talked about a beautiful method for computing ray/triangle intersections. In this post, I will extend it to computing intersections with triangle fans. Since meshes are often stored in a corner table, which is simply an array of triangle fans, this gives an efficient algorithm for ray tracing triangle meshes.

# A Beautiful Ray/Triangle Intersection Method

3D ray/triangle intersections are obviously an important part of much of computer graphics. The Möller–Trumbore algorithm, for example, computes these intersections very quickly. But there is another method that I believe is more elegant, and in some cases allows you to compute the intersection for “free.”

# Collisions

This animation is of one of Dimension's test scenes, physically integrated with collision detection and gravity. Each collision is perfectly elastic. The 1000-sphere scene was integrated and collision-detected 100 times per frame. The integration and rendering took 30 minutes on 12 cores, or 3 hours of CPU time. Continue reading Collisions

# Ray / Priority R-Tree Intersection

These animations, rendered with Dimension, show the ray / bounding box intersections that occur when rendering a single pixel. The first video shows the regular search, and the second shows the faster case of a cache hit, as described in the previous post. Each ray/box intersection takes up one second in these videos, which aptly illustrates the difference between the cache miss and cache hit cases. For this pixel, the improvement is more than a factor of two. Continue reading Ray / Priority R-Tree Intersection

# Priority R-Trees

PR-trees, as used by Dimension, provide a bounding-volume hierarchy with the unique property of bounded query complexity. Combined with intersection caching, they work as a very efficient BVH, comparable to POV-Ray's performance. This is a rendering (using Dimension) of the PR-tree generated for one of its test scenes: Continue reading Priority R-Trees

# Fast, Branchless Ray/Bounding Box Intersections

(Update: part 2)

Axis-aligned bounding boxes (AABBs) are universally used to bound finite objects in ray-tracing. Ray/AABB intersections are usually faster to calculate than exact ray/object intersections, and allow the construction of bounding volume hierarchies (BVHs) which reduce the number of objects that need to be considered for each ray. (More on BVHs in a later post.) This means that a ray-tracer spends a lot of its time calculating ray/AABB intersections, and therefore this code ought to be highly optimised. Continue reading Fast, Branchless Ray/Bounding Box Intersections