Ray Tracing - Geometric Sphere Intersection - Intersection function returns true for all rays despite no intersection

Question

I am writing a ray tracing project with C++ and OpenGL and am running into some obstacles with my sphere intersection function: I've checked multiple sources and the math looks right, but for some reason for every single ray, the intersection method is returning true. Here is the code to the sphere intersection function as well as some other code for clarification:

bool intersect(Vertex & origin, Vertex & rayDirection, float intersection)
{
    bool insideSphere = false;
    Vertex oc = position - origin;
    float tca = 0.0;
    float thcSquared = 0.0;

    if (oc.length() < radius)
        insideSphere = true;

    tca = oc.dot(rayDirection);

    if (tca < 0 && !insideSphere)
        return false;

    thcSquared = pow(radius, 2) - pow(oc.length(), 2) + pow(tca, 2);

    if (thcSquared < 0)
        return false;

    insideSphere ? intersection = tca + sqrt(thcSquared) : intersection = tca - sqrt(thcSquared);

    return true;
}

Here is some context from the ray tracing function that calls the intersection function. FYI my camera is at (0, 0, 0) and that is what is in my "origin" variable in the ray tracing function:

#define WINDOW_WIDTH 640
#define WINDOW_HEIGHT 480

#define WINDOW_METERS_WIDTH 30
#define WINDOW_METERS_HEIGHT 20
#define FOCAL_LENGTH 25


rayDirection.z = FOCAL_LENGTH * -1;
for (int r = 0; r < WINDOW_HEIGHT; r++)
{
    rayDirection.y = (WINDOW_METERS_HEIGHT / 2 * -1) + (r * ((float)WINDOW_METERS_HEIGHT / (float)WINDOW_HEIGHT));
    for (int c = 0; c < WINDOW_WIDTH; c++)
    {
        intersection = false;
        t = 0.0;

        rayDirection.x = (WINDOW_METERS_WIDTH / 2 * -1) + (c * ((float)WINDOW_METERS_WIDTH / (float)WINDOW_WIDTH));

        rayDirection = rayDirection - origin;

        for (int i = 0; i < NUM_SPHERES; i++)
        {
            if (spheres[i].intersect(CAM_POS, rayDirection, t))
            {
                intersection = true;
            }
        }

Thanks for taking a look and let me know if there is any other code that may help!

Well, intersect() has two return trues in it, which one does your debugger say keeps getting hit? — genpfault
There should only be one "return true" statement; the other one just assigns "insideSphere" a true value. — jdark135
What's the point of assigning to intersection at the end of intersect? — JWWalker
But modifying a local variable at the end of a function has no effect after the function returns, so why do it? — JWWalker

Synxis Synxis · Accepted Answer · 2014-12-16T18:42:21

It seems you got your math a bit mixed. The first part of the function, ie until the first return false, is ok and will return false if the ray start outside of the sphere and don't go toward it. However, I think you put the camera outside all your spheres in such a manner that all spheres are visible, that's why this part never return false.

thcSquared is really wrong and I don't know what it is supposed to represent.

Let's do the intersection mathematically. We have:

origin : the start of the ray, let's call this A
rayDirection : the direction of the infinite ray, let's call this d.
position : the center of the sphere, called P
radius : self-explanatory, called r

What you want is a point on both the sphere and the line, let's call it M:

M = A + t * d because it is on the line
|M - P| = r because it is on the sphere

The second equation can be changed to be |A + t * d - P|² = r², which gives (A - P)² + 2 * t * (A - P).dot(d) + t²d² = r². This is a simple quadratic equation. Once solved, you have 0, 1 or 2 solutions, select the closest to the ray origin (but which is positive).

edit: You are forced to use another approach that I will detail here:

Compute the distance between the center of the sphere and the line (calling it l). This is done by 'projecting' the center on the line. So:

tca = ( (P - A) dot d ) / |d|, or with your variable names, tca = (OC dot rd) / |rd|. The projection is H = A + tca * d, and l = |H - P|.
If l > R then return false, there is no intersection.
Let's call M one intersection point. The triangle MHP have a right angle, so MH² + HP² = MP², in other terms thc² + l² = r², so we now have thc, the distance from H to the sphere.
With all that, t = tca +- thc, simply take the lowest non-negative of the two.

The paper you linked explain this, but without saying that it assumes the norm of the ray direction to be 1. I don't see a normalization in your code, that may be why your code fails (not verified).

Side note: the name Vertex for a 3d vector is really badly chosen, something like Vector3 or vec3 would be way better.

Ray Tracing - Geometric Sphere Intersection - Intersection function returns true for all rays despite no intersection

1 Answers