Archived

This topic is now archived and is closed to further replies.

helix

"Fat-ray" collision detection

Recommended Posts

I need to make a collision detection algorithm that does a ray (with a radius) to sphere collision. Here is my ray to sphere algorithm:
  
const bool Util::RaySphereTest( D3DXVECTOR3* vPofI, const D3DXVECTOR3* vSpherePos, const float fRadius, 
								const D3DXVECTOR3* vRayStartPos, const D3DXVECTOR3* vRayEndPos )
{
	// Ray''s direction

	D3DXVECTOR3 vRayNormal = *vRayEndPos - *vRayStartPos;
	Normalize( &vRayNormal, &vRayNormal );

	// Get distance of a vector from ray origin to sphere''s center pos projected on the ray

	D3DXVECTOR3 vRaySphere = *vSpherePos - *vRayStartPos;
	float dist = DotProd( &vRaySphere, &vRayNormal );

	// Find distance from point of intersection to vector perpendicular to ray and goes through sphere''s 

	//	center (that''s the idea anyway)

	float disc = (fRadius * fRadius) - (DotProd( &vRaySphere, &vRaySphere ) - (dist * dist) );
	if( disc < 0.0f ) 
		return false;	// No intersection


	// They intersect

	if( vPofI )
	{
		// Find point of intersection

		float d = (float)sqrt( disc );
		*vPofI = *vRayStartPos + ((dist - d) * vRayNormal);
	}

	return true;
}
  
How can I modify this to give the ray a radius?

Share this post


Link to post
Share on other sites
A friend of mine said that I might just be able to add the ray''s radius to the sphere''s radius. That seems to work... Is this a good way?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Hmmm... it''s not quite what you want. Adding the ray radius to the sphere radius technically makes this an intersection test between a sphere and a capsule (the swept locus of your ray)whereas you want an intersection test between a sphere and a cylinder.

Also note that there won''t be a single intersection point in this case, but an infinite amount of intersection points along the intersection curve.

*HOWEVER*. As with most collision stuff, I''ve found that tests like the one you''ve concocted, that "kindof work", are the perfect solution if the side effects are something you can live with.

But if you want to do it proper, check these out:

http://www.magic-software.com/Intersection3D.html

Share this post


Link to post
Share on other sites
If the extremities of the ray are a concern, you can always check if there is a collision between the sphere and the disks at the end if the collision point is behind the end of the ray.

Cédric

Share this post


Link to post
Share on other sites
Adding the radius of the ray to the sphere and treating the ray as infinitely thin is not a fudge, but in fact an efficient way of performing the collision computation IF you don''t care about knowing the point/curve of collision. If you do care, you can find the curve with some calculus. The result will be an ellipse if the ray fully penetrates the sphere or half and ellipse if the ray only partially penetrates the sphere. In the first instance, the centre of the ellipse is given by the collision point of the axis of the cyclinder and in the second case, the centre of the ellipse lies at the point where the vector orthogonal to the ray (that points toward the sphere''s origin) pierces the sphere. I.e., at the point on the sphere that is tangent to the ray. You can work out the minor axis of the ellipse from the width of the portion of the cyclinder that penetrates the sphere. The major axis is more difficult to determine and depends on where the cylinder''s axis penetrates the sphere, if it does at all.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
> Adding the radius of the ray to the sphere and
> treating the ray as infinitely thin is not a fudge

Fat Ray (for point X):
d = X - (O + tD)
dx^2 + dy^2 + dz^2 < r0^2
t >= 0
O = <0, 0, 0>
D = <0, 0, 1>
r0 = 1

Sphere (for point X):
d = X - O
dx^2 + dy^2 + dz^2 < r1^2
O = <0, 0, -0.5>
r1 = 1

Whether you want to call it a fudge or not it still gives an incorrect intersection test result if your ray is bounded (which, in the OP code, it is).

If you''re ray is not bounded then as you say, it''s perfect.

Share this post


Link to post
Share on other sites
> The result will be an ellipse if the ray fully penetrates the sphere or half and ellipse if the ray only partially penetrates the sphere.

Any evidence to support this claim? I was expecting the result to be a curve of degree 4.

Share this post


Link to post
Share on other sites
quote:

The result will be an ellipse if the ray fully penetrates the sphere or half and ellipse if the ray only partially penetrates the sphere.



Wrong wrong wrong!

Share this post


Link to post
Share on other sites
It IS an ellipse on the surface of the sphere (i.e., in the 2D space that has a spherical metric) ... my apologies for not making this clear. True, it is not an ellipse in Cartesian space... and I admit my posting is open to the interpretation that this is what I was saying... my apologies.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
> Adding the radius of the ray to the sphere and
> treating the ray as infinitely thin is not a fudge

Fat Ray (for point X):
d = X - (O + tD)
dx^2 + dy^2 + dz^2 < r0^2
t >= 0
O = <0, 0, 0>
D = <0, 0, 1>
r0 = 1

Sphere (for point X):
d = X - O
dx^2 + dy^2 + dz^2 < r1^2
O = <0, 0, -0.5>
r1 = 1



Would you mind explaining your symbols and vectors please... there's too many possiblities in this to offer a meaningful answer.


quote:
Original post by Anonymous Poster
Whether you want to call it a fudge or not it still gives an incorrect intersection test result if your ray is bounded.



From my understanding of intersection implementations, the ray length is always set to be the length of the component of the point-sphere displacement vector, in the direction of the ray. Therefore, the ray terminates at a point such that if you added an appropriately rotated vector (that was orthognal to the ray), at the end of the ray, it would pass through the origin of the sphere. In this case, the fat_ray/sphere intersection is a circle-circle intersection in the plane defined by rotating the orthogonal vector around the ray. If I have a fundamental misunderstanding of this, could you please point it out and provide the correct answer?

Checking whether two circles of given sizes r1 and r2 intersect is equivalent to checking any two circles ra and rb, such that ra+rb=r1+r2. In which case, you can legitimately make ra=0 and rb=r1+r2.

Cheers,

Timkin


[edited by - Timkin on October 17, 2002 10:31:58 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Timkin
It IS an ellipse on the surface of the sphere (i.e., in the 2D space that has a spherical metric) ...

A 2D space that has spherical metric? Could you explain that? I keep looking at MathWorld''s picture (the first link I gave), and I fail to see how it could be an ellipse... There seems to be a discontinuity in the slope of the curve at the top of the sphere.

Thank you,

Cédric

Share this post


Link to post
Share on other sites
quote:
Original post by cedricl
A 2D space that has spherical metric?



Imagine that you are a very flat ant living on the surface of a sphere. The world looks flat to you and you can identify two dimensions. However, if you try and do things like measure distances between two points, you find that the shortest distance is not given by the length of a straight line between those points. In fact, it's given by the length of the arc of the Great Circle between those two points. Additionally, if you add up the angles inside a triangle, they don't add to 180 degrees. All of these results can be predicted by applying a non-Cartesian (in this case, spherical) metric to the space... just as we apply a spherical metric to 4D space time to arrive at a curved space (without gravity) that has the same properties as a Cartesian space with gravity.

Cheers,

Timkin

[edited by - Timkin on October 17, 2002 10:49:29 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
> From my understanding of intersection implementations,
> the ray length is always set to be the length of the
> component of the point-sphere displacement vector, in the
> direction of the ray.

This is a good answer. I think things need clarifying: Are you assuming that a "fat ray" is a cylinder? This is what I''m doing. From your explanation, you are also saying that there is no explicit upper bound on ray length. It is implicitly calculated as being the length of the point-sphere vector. This is good because it will catch all forward facing intersections (from the outside).

My point was that explicit bounds on the ray would give incorrect results. Which should still hold true. An explicit bound would be t<=0. If your ray is close to the surface of the sphere pointing away from it, and the radius of the ray is such that it intersects with the sphere (if the ray is treated as a capsule) then that is an incorrect result (if the ray is to be treated as a cylinder).

Of course, just treat it as a capsule and all my nonsensical rambling disappears.

Share this post


Link to post
Share on other sites
quote:
It IS an ellipse on the surface of the sphere (i.e., in the 2D space that has a spherical metric)


The definitions I have for ellipse don''t support your claim.

Would you mind defining ellipse in a differentiable manifold with a metric? I still think that the intersection of a sphere and a cillinder is a 4th degree curve (that link in MathWorld doesn''t prove me wrong) and that any sensible definition of ellipse will not include those.

Share this post


Link to post
Share on other sites
Ok, another question: if I have
r = f(theta) = 2theta

Does it mean that this is a line, because its equation has the form of a line, in polar coordinates (even though it''s a spiral in the cartesian plane)?

Cédric

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:

It IS an ellipse on the surface of the sphere (i.e., in the 2D space that has a spherical metric) ... my apologies for not making this clear. True, it is not an ellipse in Cartesian space... and I admit my posting is open to the interpretation that this is what I was saying... my apologies.



Timkin try demonstrating where you can see an equation of an ellipse with the following case:

Sphere centered at (0,y0,z0) with radius r:

x=r*cos(theta)*cos(phi)
y=y0+r*cos(theta)*sin(phi)
z=z0+r*sin(theta)

cylinder around x-axis with radius R:

y*y+z+z=R*R

You mean that when you combine these two equation systems you''ll get something theta=f(phi) which plots an ellipse????? I don''t think so, but please go on with a demonstration...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Of course I meant
y*y+z*z=R*R
not
y*y+z+z=R*R

Share this post


Link to post
Share on other sites
My apologies... I was wrong. Given the strong objections I went back and checked my working for the initial solution I derived and I found that I had made an error in setting up the problem. I derived a solution that was actually only valid when the ray axis intersected the origin of the sphere (so the intersection curve was an ellipsoid... but actually a perfect circle). The result in this situation is that the semi-major axis of the ellipse is a constant, wherease in the correct solution it is a function of phi (azimuthal angle) and the point of intersection of the ray axis. Thus, the true curve looks like an egg.

My sincere apologies for my stupidity and for proposing an answer that was incorrect. I''ll just go hide in the corner now and keep my mouth shut for a while!

Regards,

Timkin

Share this post


Link to post
Share on other sites