Original Post
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
