Ray Tracing

[nabulsr2]

Hi,

I'm trying to use ray tracing to detect whether a ray projected from some point intersects with a sphere. I have looked at many resources to get me started, this is the main one:

http://www.codeproject.com/netcf/cfrt_article.asp

This is how I calculate each of the points on the ray:

To shoot a ray from origin to endpoint, it helps to think of it as linear movement (i.e. constant velocity) in time. I define the point at time t as:

P(t) is the vector at time t
P(0) is the vector at time 0, which is the starttime
P(T) is the vector at time T, which is the endtime.
V is the velocity vector

V = (P(T)-P(0))/T
P(t) = P(0)+V*t

I want a fixed number of steps, so I set T to 1 and let t step from 0 to 1.0 (this simplifies the formula). By calculating the velocity from end point and startpoint there is no need for special cases (i.e. no need to worry about the direction of the ray, or whether it is going towards or away from the origin).

Now, this works fine, what I'm actually having trouble with is the actual detection of intersection between the ray and the sphere. The problem is that it's only half working at the moment. I have spent many hours going through the code and can't see what's wrong. Here is a quick summary of what I'm doing:

1. Substitute the equation of the ray into the equation of the sphere

2. You end up with a quadratic equation which can be solved (via (-b +/- (b^2 - 4ac)^0.5)/(2a))

3. If the discriminant (i.e. b^2 - 4ac) is negative then you know that there is no intersection between the ray and the sphere

4. Otherwise, the intersection points are the two solutions

This approach is all taken from the URL link posted above (see the 'Sphere' section). Here is my code:


************************************************** ************
//calculate a, b & c for quadratic equation
a = pow(x_velocity, 2) + pow(y_velocity, 2)
+ pow(z_velocity, 2);

b = 2 * x_velocity * (x_begin - x_sphere)
+ 2 * y_velocity * (y_begin - y_sphere)
+ 2 * z_velocity * (z_begin - z_sphere);

c = pow(x_sphere, 2) + pow(y_sphere, 2)
+ pow(z_sphere, 2) + pow(x_begin, 2)
+ pow(y_begin, 2) + pow(z_begin, 2)
+ 2*(-(x_sphere*x_velocity)
-(y_sphere*y_velocity)
-(z_sphere*z_velocity))
- pow(sphere_radius, 2);

// check the value of the discriminator, if negative then there is no intersection
if ( ( (pow(b, 2) - (4*a*c) ) >= 0.0) )
{
//calculate the two intersection points
t0 = (-b + pow(pow(b, 2) - (4*a*c), 0.5))/(2*a);
t1 = (-b - pow(pow(b, 2) - (4*a*c), 0.5))/ (2*a);

if (t0 < t1) clostest_intersection = t0;
else closest_intersection = t1;

// calculate the coordinates of the closest intersection point
x_int = x_begin + x_velocity*intersection;
y_int = y_begin + y_velocity*intersection;
z_int = z_begin + z_velocity*intersection;
}
else printf("NO INTERSECTION\n");
************************************************** ************

x,y,z_begin are the start coords of the ray.
x,y,z_velocity is the velocity of the ray and equals x,y,z_end - x,y,z_begin.
x,y,z_sphere are the coords of the sphere's centre.
x,y,z_int is the closest intersection point (if any)

Now, the above code works fine for a sphere that is positioned at the origin (with a ray starting at any point and ending at the origin, i.e. one that is travelling towards the sphere). It also works fine when the sphere has been translated to be at a position behind the starting point of the ray (i.e. the ray is travelling away from the sphere). Things seem to be going wrong when:

1. The sphere is positioned on the ray (e.g. half way along the ray). The algorithm doesn't pick up the intersection.

2. Positioned either side of the ray. Sometimes it considers this an intersection, others it doesn't (depends on the coords supplied).

3. Positioned a little ahead (but still in line with) of the ray end point. This is considered to be an intersection.

I know that I have correctly applied the formulae manipulation because I've done a few test ones by hand and then compared it to the values of t0 and t1 produced in my code. I suspect that the problem is to do with the fact that I am translating the sphere to different positions, but I thought that the above algorithm should work for all sphere positions?
Can anyone spot what is going wrong with my code?

Thanks,
Ramsey

[Leisure Suit Lurie]

I am half asleep, so some of the following may be gibberish, but if the discriminant is 0, I believe there is exactly 1 intersection point.

Also, t0 or t1 can be a negative number meaning there is an intersection if the ray went backwards. It seems you don't check is t0 or t1 are negative. Only if both t0 and t1 are positive, can you take the lower of the two.

[belthaczar]

Your equation for c looks wrong to me. It should be
c = (begin - sphere) . (begin - sphere) - r^2

Also your ubiquituous use of pow() is really annoying to me for some reason.
pow(x, 2) = x*x
pow(x,0.5) = sqrt(x)
In both cases above, I find the right-hand-side more soothing.

Also if you normalize the "velocity" before you start, you can simplify the other computations somewhat.

[nabulsr2]

Okay, managed to fix it. I changed the calculation for c to the following:

c = pow(x_begin - x_sphere,2) + pow(y_begin -
y_sphere,2) + pow(z_begin - z_sphere,2) -
pow(sphere_radius,2);

It now properly detects whether or not there is intersection with the sphere, regardless of where the sphere is positioned. The only remaining concern is that it still counts a sphere placed ahead of, and in line with, the ray end point as being an intersection. No idea why...

[Leisure Suit Lurie]

You also are checking that t is btw 0 and 1? If t is greater than 1, there is no intersection.

[nabulsr2]

Yep, that did the trick, I wasn't checking if t was less than or equal to 1.0. Basically if t exceeds 1.0 then you know that it is beyond the end of the ray. Thanks for your help!