Sign in to follow this  
Spa8nky

Problem with following collision detection method [C#] - From C Ericson Book

Recommended Posts

Hi folks, I have come across the following problem when using Christer Ericson's collision detection method between a sphere and a triangle (found on page 168 of his orange collision detection book). The problem I am having is testing the sphere against the triangle edges, which are calculated as rays. So basically it boils down to 3 sphere ray intersection tests. When creating a ray I have an origin and a normalized direction vector. However when using the following from the code the method does not work:
            // Test if edge (p.v[j], p.v[i]) intersects sphere (s)
            ray_Current = new CD_Ray(tri.C, tri.A - tri.C);         // Origin, Direction
            result_Temp = ray_Current.Intersects(this, result_Temp);

            if (result_Temp.isColliding == true && result_Temp.distance <= 1.0f)
            {
                Console.WriteLine("A - C: " + result_Temp.distance);
                result.isColliding = true;
                return result;
            }
The problem is that when only returning true when the result_Temp.distance (t in book) is less than 1 means that the statement is only ever true when the ray is intersected near within a distance of 1.0f from its origin. If I set the distance to equal that of the length of the triangle edge (tri.C + (tri.A - tri.C)) then the algorithm works correctly. If it is stated in the book as 1.0f then I can only imagine that I am doing something incorrect here but all my ray/sphere intersections work out perfectly besides this. So, can someone more in the know point out where I might have gone wrong here? Thanks.

Share this post


Link to post
Share on other sites
if you have the points on a triangle A,B,C and are making rays (really line segments since you are testing for distance < some number) make sure that you don't normalize your vectors.

So... wrong way:

AB = B - A;
Normalize(AB);

Right way:

AB = B - A;

The reason is because you want to preserve the length of the vector, and when you compare the result, it isn't "distance", it's actually "time".

The idea is that you pretend it takes one unit of time to get from A to B, and then you see how long it takes to go from A towards B and intersect the sphere.

If that time is < 1.0 you know that your line segment has intersected the sphere.

hope that helps!

EDIT: speaking of which i notice now that you are doing this:

result_Temp.distance <= 1.0f

If my above comments don't help you go "AHA!" i think what you should be doing is...

result_Temp.distance / ray_Current.distance <= 1.0f

that division could be slow if you use this test a lot, and there are ways to optimize it, but the mantra is: functionality first, then optimization! (:

Share this post


Link to post
Share on other sites
By ray_Current.distance do you mean the following method:

ray_Current.Direction.Length() [I.E. Vector's Length/Magnitude]

Which returns sqrt(x*x+y*y+z*z)?

If so, that method doesn't work as it is saying that I am always colliding with the triangle, even when outside the triangle. It only happens on the same plane as the ray though.

Share this post


Link to post
Share on other sites
Hrm it sounds like maybe there's a typo somewhere or something.

You could paste the whole relevant source code, or you could try and re-implement it and maybe this time you'll see something you missed or not make the same mistake as before (assuming thats what happened!)

Share this post


Link to post
Share on other sites
The test for sphere/triangle intersection is as follows:


private Contact IntersectTriangle(CD_Triangle tri, Contact result) // (P 168)
{
Contact result_Temp = new Contact();

// No intersection if sphere not intersecting plane of triangle
result_Temp = this.IntersectPlane(tri.Plane, result_Temp);

if (result_Temp.isColliding == false)
{
return result;
}

// Reset isColliding for the following tests
result_Temp.isColliding = false;

// Test to see if any one of the triangle edges pierces the sphere (Ray Sphere test)
CD_Ray ray_Current;

// Test if edge (p.v[j], p.v[i]) intersects sphere (s)
ray_Current = new CD_Ray(tri.C, tri.A - tri.C); // Origin, Direction
result_Temp = ray_Current.Intersects(this, result_Temp);

if (result_Temp.isColliding == true && result_Temp.distance <= 1.0f)
{
Console.WriteLine(ray_Current.Direction.Length());
Console.WriteLine("A - C: " + result_Temp.distance);
result.isColliding = true;
return result;
}

ray_Current = new CD_Ray(tri.A, tri.B - tri.A); // Origin, Direction

result_Temp = ray_Current.Intersects(this, result_Temp);

if (result_Temp.isColliding == true && result_Temp.distance <= 1.0f)
{
Console.WriteLine("B - A: " + result_Temp.distance);
result.isColliding = true;
return result;
}

ray_Current = new CD_Ray(tri.B, tri.C - tri.B); // Origin, Direction
result_Temp = ray_Current.Intersects(this, result_Temp);

if (result_Temp.isColliding == true && result_Temp.distance <= 1.0f)
{
Console.WriteLine("C - B: " + result_Temp.distance);
result.isColliding = true;
return result;
}

// Test if the orthogonal projection (q) of the sphere centre onto m is inside p
Vector3 q = tri.Plane.ClosestPtPointPlane(this.Centre);

if (tri.PointInTriangle(q))
{
result.contact_Point = q;
result.isColliding = true;
}

return result;
}



The test for ray/sphere collision detection always works great apart from when used in the above method.

The ray/sphere intersection test is as follows:


private Contact IntersectSphere(CD_BoundingSphere sphere, Contact result)
{
Vector3 m = this.Origin - sphere.Centre;
float c = Vector3.Dot(m, m) - sphere.Radius * sphere.Radius;
float b = Vector3.Dot(m, this.Direction);

// Early exit if:
// - Ray origin outside Sphere (c > 0) AND
// - Ray pointing away from Sphere (b > 0)
if (c > 0.0f && b > 0.0f)
{
return result;
}

float discr = b * b - c; // Discriminant (Quadratic equation) = b [Squared] - c
// A negative discriminant corresponds to Ray missing Sphere
if (discr < 0.0f)
{
return result;
}

// Now Ray must hit Sphere
result.isColliding = true;

// Compute smallest value of intersection (t)
float t = -b - (float)Math.Sqrt(discr);

// If (t) is negative, Ray started inside Sphere so clamp (t) to zero
if (t < 0.0f)
{
t = 0.0f;
}

// Compute intersection point (q)
Vector3 point_Intersection = this.Origin + t * this.Direction;

//Console.WriteLine("Distance to Sphere: " + t);
//Console.WriteLine("Intersection Point: " + point_Intersection);

result.distance = t;
result.contact_Point = point_Intersection;

return result;
}



Thanks for helping with this predicament.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this