# Optimized algorithm for line-sphere intersection in GLSL

Well, hello then!

I need to find intersection between line and sphere in GLSL. Right now my solution is based on Paul Bourke's page and was ported to GLSL this way:

// The line passes through p1 and p2:
vec3 p1 = (...);
vec3 p2 = (...);

// Sphere center is p3, radius is r:
vec3 p3 = (...);
float r = ...;

float x1 = p1.x; float y1 = p1.y; float z1 = p1.z;
float x2 = p2.x; float y2 = p2.y; float z2 = p2.z;
float x3 = p3.x; float y3 = p3.y; float z3 = p3.z;

float dx = x2 - x1;
float dy = y2 - y1;
float dz = z2 - z1;

float a = dx*dx + dy*dy + dz*dz;
float b = 2.0 * (dx * (x1 - x3) + dy * (y1 - y3) + dz * (z1 - z3));
float c = x3*x3 + y3*y3 + z3*z3 + x1*x1 + y1*y1 + z1*z1 - 2.0 * (x3*x1 + y3*y1 + z3*z1) - r*r;

float test = b*b - 4.0*a*c;

if (test >= 0.0) {
// Hit (according to Treebeard, "a fine hit").
float u = (-b - sqrt(test)) / (2.0 * a);
vec3 hitp = p1 + u * (p2 - p1);
// Now use hitp.
}


It works perfectly! But it seems slow... I'm new at GLSL. You can answer this questions in two ways:

1. Tell me there is no solution, showing some proof or strong evidence.
2. Tell me about GLSL features (vector APIs, primitive operations) that makes the above algorithm faster, showing some example.

Thanks a lot!

• How often are you calling this code? Is your framerate still low with this code removed?
– House
Apr 20 '12 at 16:31
• Then, may I ask why you need to perform such a test in the pixel shader? I don't get the general idea, you can render the sphere with nice results in the PS, but why do you need to perform collision/hit detection in the PS as well? Apr 20 '12 at 17:09
• Photo-realistic ray-traced animation with mirrors, smoke and shadows, and you want better than 20fps?
– House
Apr 20 '12 at 17:17
• Actually, I only want to make that algorithm faster. That's a very simple question. I don't understand why people can't be more direct and objective in these forums. I don't want to tell my entire doomed history. I don't want to replace my work with 3rd party. I just want to know if that algorithm can be faster using some sort of GLSL primitives, like vector APIs! Tell me, GLSL experts, is that so hard to answer? Apr 20 '12 at 17:23
• @fernacolo: "I don't understand why people can't be more direct and objective in these forums." Because most of the time, when people ask 'make my code faster,' they're doing it out of a misplaced sense belief that taking the time to do so is actually worthwhile for their application. Plus, there's the simple fact that GLSL doesn't define performance. Various things might increase performance, but there's no guarantee of it for any particular compiler. So your question is basically unanswerable in the general case. Apr 20 '12 at 18:50

There is no need for these separate x1, x2 etc. variables. You can compute a, b and c in fewer instructions using vector operations:

vec3 d = p2 - p1;

float a = dot(d, d);
float b = 2.0 * dot(d, p1 - p3);
float c = dot(p3, p3) + dot(p1, p1) - 2.0 * dot(p3, p1) - r*r;


It is possible the compiler will notice this, but there is no reason to make it harder than it already is to optimise GLSL compilation.

• Very good! From 16fps, I got 19fps! Thanks a lot! Apr 21 '12 at 0:00