# SAT sphere triangle test, calculating response

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

## Recommended Posts

Hello, I have been looking for a simple method that I understand to test a sphere to a triangle in 3d, so I found this article http://realtimecollisiondetection.net/blog/?p=103 which I was able to implement and works well. I just can't seem to grasp how should I generate a response to the collision, specifically the penetration depth. In concept it should be the least overlap on all axis? How would I go about calculating the response?

##### Share on other sites

The penetration depth is the distance between the closest points minus the sphere radius.

The collision normal is the separating axis.

If the triangle is static and you want a positional response then you can shift the sphere center by the penetration depth along the collision normal. Assume p2 is the closest point on the triangle to the sphere center. You can shift the sphere like this:

penetration = dot(p2 - center, normal) - radius

center = center + penetration * normal

Edited by Irlan Robson

##### Share on other sites

Yes the triangle is static. I understand your reply perfectly, only im not sure on how to calculate the closest points.

##### Share on other sites

You can use Barycentric coordinates to find the closest point on the triangle to the sphere center. Here's some personal code of mine you can use:

// Convert a point Q from Cartesian coordinates to Barycentric coordinates (u, v)
// with respect to a segment AB.
// The last output value is the divisor.
static B3_FORCE_INLINE void b3Barycentric(float32 out[3],
const b3Vec3& A, const b3Vec3& B,
const b3Vec3& Q)
{
b3Vec3 AB = B - A;
b3Vec3 QA = A - Q;
b3Vec3 QB = B - Q;

float32 divisor = b3Dot(AB, AB);

out[0] = b3Dot(QB, AB);
out[1] = -b3Dot(QA, AB);
out[2] = divisor;
}

// Convert a point Q from Cartesian coordinates to Barycentric coordinates (u, v, w)
// with respect to a triangle ABC.
// The last output value is the divisor.
static B3_FORCE_INLINE void b3Barycentric(float32 out[4],
const b3Vec3& A, const b3Vec3& B, const b3Vec3& C,
const b3Vec3& Q)
{
b3Vec3 AB = B - A;
b3Vec3 AC = C - A;

b3Vec3 QA = A - Q;
b3Vec3 QB = B - Q;
b3Vec3 QC = C - Q;

b3Vec3 QB_x_QC = b3Cross(QB, QC);
b3Vec3 QC_x_QA = b3Cross(QC, QA);
b3Vec3 QA_x_QB = b3Cross(QA, QB);

b3Vec3 AB_x_AC = b3Cross(AB, AC);

float32 divisor = b3Dot(AB_x_AC, AB_x_AC);

out[0] = b3Dot(QB_x_QC, AB_x_AC);
out[1] = b3Dot(QC_x_QA, AB_x_AC);
out[2] = b3Dot(QA_x_QB, AB_x_AC);
out[3] = divisor;
}

// Return the closest point on a triangle ABC to a point Q.
b3Vec3 Solve3(const b3Vec3& A, const b3Vec3& C, const b3Vec3& C, const b3Vec3& Q)
{
// Test vertex regions
float32 wAB[3], wBC[3], wCA[3];
b3Barycentric(wAB, A, B, Q);
b3Barycentric(wBC, B, C, Q);
b3Barycentric(wCA, C, A, Q);

// R A
if (wAB[1] <= 0.0f && wCA[0] <= 0.0f)
{
return A;
}

// R B
if (wAB[0] <= 0.0f && wBC[1] <= 0.0f)
{
return B;
}

// R C
if (wBC[0] <= 0.0f && wCA[1] <= 0.0f)
{
return C;
}

// Test edge regions
float32 wABC[4];
b3Barycentric(wABC, A.point, B.point, C.point, Q);

// This is used to help testing if the face degenerates
// into an edge.
float32 area = wABC[3];

// R AB
if (wAB[0] > 0.0f && wAB[1] > 0.0f && area * wABC[2] <= 0.0f)
{
float32 s = wAB[2];
B3_ASSERT(s > 0.0f);
return (wAB[0] * A + wAB[1] * B) / s;
}

// R BC
if (wBC[0] > 0.0f && wBC[1] > 0.0f && area * wABC[0] <= 0.0f)
{
float32 s = wBC[2];
B3_ASSERT(s > 0.0f);
return (wBC[0] * B + wBC[1] * C) / s;
}

// R CA
if (wCA[0] > 0.0f && wCA[1] > 0.0f && area * wABC[1] <= 0.0f)
{
float32 s = wCA[2];
B3_ASSERT(s > 0.0f);
return (wCA[0] * C + wCA[1] * A) / s;
}

// R ABC/ACB
float32 s = wABC[3];
if (s <= 0.0f)
{
// Give up. Triangle is degenerate.
// You should handle all cases correctly in production code.
return;
}

B3_ASSERT(s > 0.0f);
return (wABC[0] * A + wABC[1] * B + wABC[2] * C) / s;
}

If you want to learn the math read Real-Time Collision Detection book.

Edited by Irlan Robson

##### Share on other sites

Thank you, it works I will have to get that book. When I first tried it did not work, playing around I realized it seem to be the winding on the triangles so I inverted it and it works well, although if 2 triangles make a corner it doesn't behave well. My first thought was that it was pushing the sphere to a place where it would be interpenetrating another triangle so I did a little recursion when a collision is found to solve other collisions and on most cases it's smoother, but I will get jitter on any corner that faces outward. Any resources on how to get rid of this jitter problem?

##### Share on other sites
You can implement a position based constraint solver for this. Sharp corners requires a large number of solver iterations. Erin Catto (Box2D) described this algorithm at the end of his presentation:

It should be pretty easy to simplify it to your case and a great exercise. This is a very good resource with no lack of mathematical foundation.

Sorry, I cannot list you all the edge cases because I haven't taken the time to implement a robust character controller. But that is not a difficult problem we can tell you.

If your engine supports double side collision the order of the triangle vertices doesn't matter.

Edited by Irlan Robson

1. 1
Rutin
24
2. 2
3. 3
JoeJ
18
4. 4
5. 5

• 38
• 23
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631710
• Total Posts
3001846
×