Jump to content
  • Advertisement
Sign in to follow this  
ne0_kamen

Ray to Sphere test not working properly[SOLVED]

This topic is 3915 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi,folks,I have been struggling with this all day,so I decided not to waste more time and ask here.I have been trying to implement a simple ray to sphere collision detection in my engine,but it's giving me headache.I found the algorithm at Graphics Gems 1 and decided to try and create it myself instead of copying someone else's code over the net. Here is the code :
/* Algorithm can be found at Graphics Gems 1 (388 page) */
T3DMATH_API bool T3D::rayIntersectSphere(T3D::Ray& ray,T3D::Vector3f& center,float radius,T3D::Vector3f& intersect_point)
{
	Vector3f V = ray.dir().normalize();
	Vector3f c = center-ray.pos();
	float v = c * V;
	float disc = radius*radius - (c*c - v*v);

	if(disc < 0)
		return false;
	else
	{
		float d = sqrt(disc);
		intersect_point = ray.pos() + (V*(v-d));
		return true;
	}
}



The problem is that the function sometimes return incorrect results.Here is what I mean : The sphere is centered at [0,0,0] with a radius of 4 units. If I raytrace it with a ray with origin [0,-5,0] and direction [0,1,0] it correctly returns the point[0,-4,0](bottom of the sphere).But if the I apply the same ray,but with a direction [0,-1,0] it returns the point[0,4,0](top of the sphere),while it have to return that there is not collision at all. I hope someone can solve it :) EDIT: Forgot to mention that vector*vector is actually a dot product in my code,while vector*value is just multiplying that vector by the value. [Edited by - ne0_kamen on October 27, 2007 5:48:23 AM]

Share this post


Link to post
Share on other sites
Advertisement
If you want to implement your own ray-sphere intersection test, then all you need to do is plug the equation of the ray into the equation of the sphere, shown here, and you'll arrive at a solution that you just implement straight in code.

If you'd rather try to get your different solution working, then explain your thought process step by step and we can help you spot where you went wrong.

Share this post


Link to post
Share on other sites
A line extends infinitely in both directions, however a ray is bounded on one side. You are not doing a check for this, so effectively your implementation is a line - sphere test.
I've not checked your implementation thoroughly but you can try this:
if (v-d)< 0 there is no collision as the ray would have to be reversed.

Share this post


Link to post
Share on other sites
Thanks for the help,chand,it worked :).Zipster I bookmarked the page for later reference and source for possible optimizations,etc...Now I'll post the function with my comments for the sake of completeness :

/* Algorithm can be found at Graphics Gems 1 (page 388).For implementation
* details and naming convections look at figure 1 on page 389 */

T3DMATH_API bool T3D::rayIntersectSphere(T3D::Ray& ray,T3D::Vector3f& center,float radius,T3D::Vector3f& intersect_point)
{

/* First we normalize the direction vector */
Vector3f V = ray.dir().normalize();
/* The EO vector (from the ray's orign to the center of the sphere) */
Vector3f c = center-ray.pos();
/* The dot product of the direction vector and the EO vector */
float v = c * V;
/* Now we have build a right-angled triangle with a hypotenuse c and sides b and v.
We also have an inner right-angled triangle with a hypotenuse the radius of the
sphere and sides b and d(d is from the intersection point to the perpendicular of
point 0.So now we can put this in a system by the pith&#1072;gorian theorem :
c*c = b*b+v*v and r*r = b*b+d*d => b*b = c*c - v*v and d*d = r*r-b*b =>
d*d = r*r - (c*c* - v*v). */

float disc = radius*radius - (c*c - v*v);

/* If the desc is lower than zero we have no collision */
if(disc < 0)
return false;

/* d*d = r*r - (c*c* - v*v) => d = sqrt(r*r - (c*c* - v*v)) */
float d = sqrt(disc);

/* Check if the ray dir is not inversed :) */
if(v-d < 0)
return false;

/* Actually at this stage there one or two collision point's(depending if the ray is
inside the sphere),but we get only the closest one */

intersect_point = ray.pos()+(V*(v-d));
return true;
}


Now I'm wondering if I want to get the second point of intersection - I'm logically thinking that it is the inverse of intersection_point 1 ? i.e if point one is [1,2,3] then the ray would leave the sphere at [-1,-2,-3],correct ?

Thanks again for the help,folks !

Share this post


Link to post
Share on other sites
Quote:
Original post by ne0_kamen
Now I'm wondering if I want to get the second point of intersection - I'm logically thinking that it is the inverse of intersection_point 1 ? i.e if point one is [1,2,3] then the ray would leave the sphere at [-1,-2,-3],correct ?


Correct! But only for the special case when the sphere is centered at the origin and ray passes through the origin.

The answer to your question is not too difficult...
Hint:
Let x^2 = y
Then, also
(-x)^2 = y
Square root can have 2 solutions....

Share this post


Link to post
Share on other sites
Quote:
Original post by ne0_kamen
Thanks for the help,chand,it worked :).Zipster I bookmarked the page for later reference and source for possible optimizations,etc...Now I'll post the function with my comments for the sake of completeness :
*** Source Snippet Removed ***
Now I'm wondering if I want to get the second point of intersection - I'm logically thinking that it is the inverse of intersection_point 1 ? i.e if point one is [1,2,3] then the ray would leave the sphere at [-1,-2,-3],correct ?

Thanks again for the help,folks !

Now that you included comments, I was able to work out the algorithm on paper and it does appear to work when the ray is on the outside of the sphere. But when the ray is inside the sphere the math changes and d > v. There's only one solution, and it's at v + d. That's actually the answer to your original question as well, you would do v + d instead of v - d to get the second intersection point.

I still urge you to go with the link I posted, since it presents a mathematically robust solution in all cases where both intersection points are readily available from the quadratic.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!