Question about performance for raytracing algorithm intersection test

Question

I'm currently building a basic raytracing algorithm and need to figure out which system of handling the intersections would be best performance-wise.

In the method I'm checking for a intersection of the ray and the object I'm returning a struct with the distance of the ray traveled to the hit, the position vector of the hit and the normal vector or -1 for the distance if there is no intersection.

For the next step I have to find the shortest distance of all intersections and exclude the ones with a negative distance.

I even thought about having 2 structs, one with only negative distances and one full struct to reduce the amount of space needed, but thought this wouldn't really make a difference.

My options so far: first go over the array of the intersections and exclude the ones with negative distances, then find the shortest distance from the remainings via a sorting algorithm (probably insertion sort due to quick implementation).

Or put them together in one algorithm and test in each sort step if the distance is negative.

typedef Point3f float[3];
typedef struct {
    float distance;
    Point3f point;
    Point3f normal;
} Intersection;

Intersection intersectObject (Ray-params, object) {
    Intersection intersection;
    //...
    if (hit) {
        intersection.distance = distance;
        intersection.point = point;
        intersection.normal = normal;
    } else {
        intersection.distance = -1.0f;
    }
    return intersection;
}

//loop over screen pixel
    Intersection* intersections;
    int amountIntersections;
    //loop over all objects
    //here I would handle the intersections
    if (amountIntersections) {
        //cast additional rays
    }

I can't really figure out what would be the best way to handle this, since this would be called a lot of times. The intersection array will probably be a dynamic array with the amountIntersections as the length variable or an array with the most expected amount of intersections which then have intersections in it with negative distances.

Answer 1

Here is the approach I've succesfully used for a huge number of objects. (Especially for ball-and-stick atomic models; see my Wikipedia user page for the equations I used for those.)

First, transform the objects to a coordinate system where the eye is at origin, and the projected plane is parallel to the xy plane, with center on the positive z axis. This simplifies the equations needed a lot, as you can see from the above linked page.

As an example, if you have a unit ray n (so n·n = 1) and a sphere of radius r centered at c, the ray intersects the sphere if and only if h ≥ 0,

h = (n·c)² + r² - (c·c)

and if so, at distance d,

d = n·c ± sqrt(h)

If you work out the necessary code, and use sensible temprary variables, you'll see that you can reject non-intersecting spheres using eight multiplications and six additions or subtractions, and that this vectorizes across objects easily using SSE2/AVX intrinsics (#include <x86intrin.h>). (That is, do not try to use an XMM/YMM vector register for n or c, and instead use each register component for a different object, calculating h for 2/4/8 objects at a time.)

For each ray, sort/choose the objects to be tested according to their known minimum z coordinate (say, c_z - r for spheres). This way, when you find an intersection at distance d, you can ignore all objects with minimum z coordinate larger than d, because the intersection point would necessarily be further out, behind the already known intersection.

Similarly, you should ignore all intersections where the distance is smaller than the distance to the projection plane (which is z_d / n_z, if the plane is at z = z_d, and only needs to be computed once per ray), because those intersections are between the eye and the projection plane. (Technically, you've "crashed into" something then, if you think of the projection plane as a camera.)