 Finding time of contact on 2d SAT between a sphere and a triangle

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

Recommended Posts

I implemented a 2D SAT for detecting collisions between a triangle and a sphere loselly based on the info found here, the static case works fine, as well as the continous one, but I need to gind the time "t" of collision besides whether or not the shapes collide. I take the triangle to be static and the circle moving (the check is 2D, but the circle is really the projection of a 3D sphere over the 3D triangle plane). Here is a picture of the problem: I marked as red and blue the 2 axes that (I think) have relevance on the calculation, one is the velocity vector and the other is a vector perpendicular to the edge against the circle collides, now, as you can see, if I take the minimum and maximum intervals to calculate "t" at the moment of first contact, I get wrong results, here represented by the outlined circles with it's respective axis color. So, the question is, given this configuration, how can I find t at the moment of first contact? Thanks!

Share on other sites
If you already know there is a collision I think you can handle it as a line-line intersection. Take the radius of the circle into account by move the triangle-line along axis A.

Share on other sites
Note that, I implemented that algo, and it's got accuracy issues sometimes, but that's with large displacements, and it's not massive.

ok, first off, you have 6 SAT axes to test.

- 3 directions perpendicular to the edges
- the vectors from each vertices towards the sphere centre

the basic algo is.

- Set two floats, tfirst = 0, tlast = 1 (in your case).
- For each axis
- find the tenter and texit for each axis, by projecting the sphere, velocity, and triangle on the axis. tenter and texit are the projected time of collision along that axis.
- if (tenter > tlast || texit < tfirst), no collision
- else, tlast = min(tlast, texit), tfirst = max(tfirst, tenter).
- End For.

tfirst and tlast are the time the sphere and triangle are in contact with each other.

- This algo is very similar to doing raytacing against a box, or slabs.
- Thsi algo also works, not only for spheres, but also for any convex polygons. The only difference with spheres is the SAT axis required.

in the end, if tfirst < 0, then you know you have an intersection (overlap, then you need to find the mtd). If tfirst > 0, then you have a collision.

- You can calculate the mtd (Minimum Translation Distance, which is the penetration depth, or overlap depth) when doing the usual calculations. Logically, it's a little bit of a pain, but in the end, you will end up with either, a time of collision, or a penetration depth. that also takes care of the case where the objects are static, and is similar to a static test.

Share on other sites
Quote:
 Original post by twanvlIf you already know there is a collision I think you can handle it as a line-line intersection. Take the radius of the circle into account by move the triangle-line along axis A

I thought of that, but I already have intervals for all axes computed, so before I take that route, I am looking for a solution that takes advantage of the calculations already made.

Quote:
 Original post by oliiiNote that, I implemented that algo, and it's got accuracy issues sometimes, but that's with large displacements, and it's not massive.

Oh, I am doing small displacements, this is for character movement, the circle is the character "space", and the triangles will be collision mesh triangles.

Quote:
 Original post by oliiiok, first off, you have 6 SAT axes to test. - 3 directions perpendicular to the edges- the vectors from each vertices towards the sphere centre

I am using a minimum of 3 for static, 4 for continous, and a maximum of 4 and 6 respectively:
- 3 directions perpendicular to the edges
- The perpendicular direction to the velocity vector.
- IF either circle/sphere center at the start or end is located in a Point Voronoi region of the triangle, add the vector from that point to the circle/sphere center normalized.

Is my Approach valid? like I said, it does work dead on for finding the collision, calculating tfirst and tlast is the thing I am having trouble with.

Quote:
 Original post by oliiithe basic algo is.- Set two floats, tfirst = 0, tlast = 1 (in your case).- For each axis- find the tenter and texit for each axis, by projecting the sphere, velocity, and triangle on the axis. tenter and texit are the projected time of collision along that axis.- if (tenter > tlast || texit < tfirst), no collision- else, tlast = min(tlast, texit), tfirst = max(tfirst, tenter).- End For.tfirst and tlast are the time the sphere and triangle are in contact with each other.

Could you be a bit more specific about which values are tenter and texit? I have a minimum and maximum for the projections of both shapes (4 floats), which is which?

Ok, I think I better post my code (obvously, the calculation of t is missing):

bool SAT2DDynamic(const CTriangle& a,const Sphere& b,
const CVector3& v,CVector3& out)
{
float MaxA,MinA,MaxB,MinB,temp;
CVector3 axis;
int axiscount=4;
float t=0;
CVector3 vTemp;
bool disjoint=false;
axis =Cross(*a.GetPoint2()-*a.GetPoint1(),a.Normal);
axis =Cross(*a.GetPoint3()-*a.GetPoint2(),a.Normal);
axis =Cross(*a.GetPoint1()-*a.GetPoint3(),a.Normal);
axis.Normalize();
axis.Normalize();
axis.Normalize();
CVector3 posSphere;
CVector3 posSphereLast;
CVector3 projection;
b.transform.GetTranslation(posSphere);
// Project Position onto triangle plane
posSphereLast=posSphere+v;
//a.GetClosestPointInPlane(posSphere,posSphere);
//a.GetClosestPointInPlane(posSphereLast,posSphereLast);

axis=Cross(v,a.Normal);
axis.Normalize();

if(a.IsPointInVertexVoronoiRegion(posSphere,vTemp))
{
axis[axiscount]=vTemp-posSphere;
axis[axiscount].Normalize();
axiscount++;
}
if(a.IsPointInVertexVoronoiRegion(posSphereLast,vTemp))
{
axis[axiscount]=vTemp-posSphereLast;
axis[axiscount].Normalize();
axiscount++;
}

for(int i=0;i<axiscount;++i)
{
// Compute Min,Max For the Triangle
GetProjection(*a.GetPoint1(),axis,projection);
MaxA=MinA=projection*axis;
GetProjection(*a.GetPoint2(),axis,projection);
temp=projection*axis;
MaxA=std::max(temp,MaxA);
MinA=std::min(temp,MinA);
GetProjection(*a.GetPoint3(),axis,projection);
temp=projection*axis;
MaxA=std::max(temp,MaxA);
MinA=std::min(temp,MinA);

// Compute Min,Max For the Sphere on the initial position
MaxB=MinB=projection*axis;
temp=projection*axis;
MaxB=std::max(temp,MaxB);
MinB=std::min(temp,MinB);

// at this point we could check the initial Sphere against the triangle
if(((MinA<MinB)&&(MaxA<MinB))||((MinA>MaxB)&&(MaxA>MaxB)))
{
// Calculate t here?
}

temp=projection*axis;
MaxB=std::max(temp,MaxB);
MinB=std::min(temp,MinB);
temp=projection*axis;
MaxB=std::max(temp,MaxB);
MinB=std::min(temp,MinB);

if(((MinA<MinB)&&(MaxA<MinB))||((MinA>MaxB)&&(MaxA>MaxB)))
{
return false;
}
}
// Collision detected
out=posSphere+((posSphereLast-posSphere)*t);
return true;
}

Share on other sites
OK, so it appears what you are doing is quite different from Kasper's algorithm (real SAT), and mine, which is exactly the same.

As I said, there is an analogy between the swept SAT and doing a particle vs AABBox. THe tests are performed similarly. So it's easier if you take this as a starting example.

Then you can extend the Particle-box to a AABBox-AABBox text, which then can be extended to Poly-Poly test, which then can be further extended to a sphere-polygon text. For sphere-sphere, a simple equaiton solving should be simple, and probably better performance wise (and algorithmically).

OK, the principle of testing a particle vs a AABBox, which is the simplest test.

1) The box is made of the intersection of two slabs

xmin xmax xmin xmax
| | ymax
| | -------------- ymax +---------+
| | | |
| | + = | |
| | | |
| | -------------- ymin +---------+
| | ymin
| |

to trace a point, and detect if the point collides, consider this.

//-------------------------------------------------
// box : [xmin, xmax, ymin, ymax]
// particle : start point : A, end point : B
//-------------------------------------------------

//-------------------------------------------------
// Here, we have a collision
//-------------------------------------------------

| |
A | |
\ | |
\ | |
\|xenter |
* |
|\ yenter
------+-*-----+-------- <-----
| \ | | [xenter, xexit] and [yenter, yexit]
| \yexit | intersect.
------+----*--+-------- <-----
| \ |
| \|
| * xexit
| |\
| | \
| | \
| | B

//-------------------------------------------------
// Here, it's a miss
//-------------------------------------------------

| |
A | |
\ | |
\| |
*xenter |
|\ |
| \ |
| \ |
| \ |
| \ |
| \ |
| \|
| *xexit <-------
| |\ |
| | \ | intervals [xenter, xexit] and
ymax | | \ yenter <------- [yenter, yexit] do not intersect.
---------+-------+---*----------
| | \
| | \
ymin | | \ yexit
---------+-------+-------*------
| | \
| | B
xmin xmax

The slab [xmin, xmax], when intersected against the segment [A, B], and projected along the X axis, produces the intersection interval [xenter, xexit].

The slab [ymin, ymax], when intersected against the segment [A, B], and projected along the Y axis, produces the intersection interval [yenter, yexit].

in the first example, in case of an intersection, the two intervals [xenter, xexit] and [yenter, yexit] intersect and produce the interval intersection [yenter, yexit].

the time the particle will hit the box will therefore be yenter, and the time the particle exit the slab will be, yexit.

in the second example, [xenter, xexit] and [yenter, yexit] do not intersect. The segment misses the box.

OK, the example above is not complete. YOu also have to check if the resulting [enter, exit] values also overlap the range of the segment, which is, in our case, [0, 1].

if the final [enter, exit] does not intersect the range [0, 1], then there is no intersection with the segment, although the infinite line intersects the box.

algo

.1) box [xmin, xmax, ymin, ymax]
.2) segment [A, B].
.3) tenter = 0, texit = 1.

.4) calculate xenter, xexit.
.5) if (xenter > texit || xexit < tenter) return no collision.
.5) tenter = max(tenter, xenter).
.6) texit = min(texit, xexit).

.7) calculate yenter, yexit.
.8) if (yenter > texit || yexit < tenter) return no collision.
.9) tenter = max(tenter, yenter).
10) texit = min(texit, yexit).

11) return first time of collision, tenter.

in code.

// box [min, max] // segment [a, b] // intersections[enter, exit]
bool SlabIntersection(flot bmin, float bmax, float a, float b, float& tenter, float& texit)
{
float denom = (smax - smin);

if (fabs(denom) < 1.0E-8f)
{
return (bmin < tmax && bmax > tmin);
}

float t0 = (bmin - smin) / denom;
float t1 = (bmax - smin) / denom;

if(t0 > t1)
{
swapf(t0, t1);
}

if (t0 > texit || t1 < tenter}
{
return false;
}
tenter = max(tenter, t0);
texit = min(texit , t1);

return true;
}

bool SegmentABBoxIntersect(CBox Box, CSegment Seg, float& t)
{
float tenter = 0.0f, texit = 1.0f;

if (!SlabIntersection(Box.Min.x, Box.Max.x, Seg.A.x, Seg.B.x, tenter, texit))
{
return false;
}

if (!SlabIntersection(Box.Min.y, Box.Max.y, Seg.A.y, Seg.B.y, tenter, texit))
{
return false;
}

t = tenter;
return true;
}

that's it. Segment - AABBox collision.

now, how does this realte to the next step, AABox-AABBox intersection (or collision).

Quite simply, doing a box-box collision is similar to a segment-box collision. In that sense, shrink the first box slowly, while at the same time expand the other box by the same amount, until the first box becomes a point. What you end up with is basically a segment, versus a box expanded by the first box's size.

If both boxes are moving, simply calculate the relative velocity of one boxto the other, thus making one appear static, while the other one will have a greater (or lower) speed. Basically, imagine decreasing velocities of A and B by the same amount. The resulting time of intersection will be the same, whatever the amount of change in velocity. So if you decrease velocity of box B and B by -A.Velocity, effectively, B.Velocity' = (B.Velocity +(-A.Velocity)), while A.velocity' = (A.Velocity +(-A.Velocity)) = 0.

bool AABBoxAABBoxIntersect(CBox A, CBox B, float& t)
{
Vector Bextent = (B.Max - B.Min) * 0.5f;
Vector Bcentre = (B.Max + B.Min) * 0.5f;
Vector Vrel = (B.Displacement - A.Displacement);

// static box, which is box A, expanded by box B's size
CBox C(A.Min, A.Max);
C.Min -= Bextent;
C.Max += Bextent;

// segment, which is box B, shrunk to a point, and with relative
// dispalcement (B.disp - A.disp).
CSegment S(BCentre, Bcentre + Vrel);

retrun SegmentABBoxIntersect(C, S, t);
}

and now the icing on the cake.

for poly-poly collision, all the SAT does is, take the slab of the two polygons along a given axis, and find if the two slabs intersect, just like when doing a AABBox-AABBox collision. Except, the axes are different (X and Y for the AABoxes, and the edge normals for the other polygons).

bool PolyPolyIntersect(const CPoly& A, const CPoly& B, float& t)
{
float tenter = 0.0f, texit = 1.0f;

//-------------------------------------------------------------------------
// Test SAT of polygon (A)
//-------------------------------------------------------------------------
for(int i = 0; i < A.NumEdges; i ++)
{
Vector Axis(-A.Edge.y, A.Edge.x);

if (!SlabAxisIntersect(Axis, A, B, tenter, texit))
{
return false;
}
}

//-------------------------------------------------------------------------
// Test SAT of polygon (B)
//-------------------------------------------------------------------------
for(int i = 0; i < B.NumEdges; i ++)
{
Vector Axis(-B.Edge.y, B.Edge.x);

if (!SlabAxisIntersect(Axis, A, B, tenter, texit))
{
return false;
}
}

t = tenter;
return true;
}

SlabAxisIntersect(const Vector& Axis, const CPoly& A, const CPoly& B, float& tenter, float& texit)
{
//------------------------------------------------------------
// relative displacement.
// or you can also work with velocities,
// except, you ned to initialise texit to the frame timestep, instead
// of 1.0f.
// This is doing Avel - Bvel, since (A) is the one we consider for a
// particle.
//------------------------------------------------------------
Vector Vrel = A.Displacement - B.Displacement;
float v = Vrel.DotProduct(Axis); // the projected velocity along the axis.

// calculate the polygon slabs
float amin, amax;
float bmin, bmax;

//-------------------------------------------------------------------------
// the two 'slabs' along the axis of separation
// that is, the min and max of the polys, when projected along the axis
//-------------------------------------------------------------------------
A.FindSlab(Axis, amin, amax);
B.FindSlab(Axis, bmin, bmax);

//-------------------------------------------------------------------------
// convert the two slabs into a single particle-slab system.
// like switching from a AABBox-AABBox to a particle-AABBox algorithm.
//-------------------------------------------------------------------------
acen = (amax + amin) * 0.5f;
aext = (amax - amin) * 0.5f;

// the expanded slab
bmin -= aext;
bmax += aext;

// the slab reduced to a single particle
float start = acen;
float end = acen + v;

//-------------------------------------------------------------------------
// do the simple particle-slab intersection
//-------------------------------------------------------------------------
return SlabIntersection(bmin, bmax, start, end, tenter, texit);
}

the sphere-polygon intersection is the same as the polygon-polygon intersection, except for this

for(int i = 0; i < Poly.NumEdges; i ++)
{
Vector Axis(-Poly.Edge.y, Poly.Edge.x);

if (!SlabAxisIntersect(Axis, Poly, Sphere, tenter, texit))
{
return false;
}
}

for(int i = 0; i < Poly.NumVertices; i ++)
{
Vector Axis(Poly.Vertex - Sphere.Centre);

if (!SlabAxisIntersect(Axis, Poly, Sphere, tenter, texit))
{
return false;
}
}

Long post, but I hope it clears how the swept SAT is done, and how it's done for poly-spheres.

[Edited by - oliii on August 2, 2005 4:52:36 AM]

Share on other sites
Sorry about the delay, I was digesting the information [smile]

So, basically what I should do is expand the polygon(triangle) by moving the edges along their normals by the radius of the sphere, then treat the test as a line segment-vs-polygon test, and finally get tenter and texit by projecting the best axis overlaps over the velocity vector, right?

Share on other sites
gahh.... no!!!! [grin]

well, not quite anyway. Doing that would leave dry when you are suppose to collide with the vertices, not just the edges.

I'm not entirely sure you understand the concept of the SAT algorithm. Really, maybe you should look towards another algorithm, like a bog-standard moving circle-triangle test. The SAT is mostly suited for polygons on polygons collisions anyway. Spheres will not be that efficient (lots of normalisations).

I did that just to clarify how the SAT works. I think I failed. [lol]

What you want require a different approach. The one you suggest basically is a bad mix of the SAT and the moving circle-triangle test.

here is a 3D version of the sphere-triangle test. I should not post that, really, but...

//-------------------------------------------------------------------------------
// Sphere Triangle Collision Routine :
// -----------------------------------
// Triangle : Vertices : V (assuming counter clockwise vertex ordering (CCW))
// Normal : N (assuming right-handed system (and also CCW), and normalised)
// Sphere : Position : P
// Displacement : D
// Radius : r
// Radius Squared: r2
//
// Constraints : Time Bound : tmax
// DoubleSidedTest : bDoubleSided
// Collision Result : PointOfContact : Pcoll
// NormalOfCOntact : Ncoll
// TimeOfCollision : tcoll
// MTD (intersection): Dcoll
//
// Warning : Due to FP innacuracies, Dcoll should not be used in case of a collision.
// Dcoll, really, is for intersections only (it represents the MTD in that case).
//-------------------------------------------------------------------------------
//
// Algorithm :
// -----------
//
// 1) find Pplane, tplane : Point of collision of sphere on Triangle plane,
// and time of collision on plane
// 2) Find features collidable.
// 3) test collision with each features.
// 4) keep the earliest.
//-------------------------------------------------------------------------------
bool SphereTriangleCollide( const Vector* V, const Vector& N, // triangle
const Vector& P, const Vector& D, float r, float r2, // sphere
float tmax, bool double_sided_tests, // max time, and if we are doing double sided tests
Vector& Pcoll, Vector& Ncoll, Vector& Dcoll, float& tcoll) // intersection params

{
// signed distance of sphere centre to plane
float dist_to_plane = (P - V) * N;

// impact velocity
float dn = D * N;

// plane - sphere collision parameters
float tplane;
Vector Pplane;

// is the sphere cut by plane
bool sphere_cut_by_plane = false;

// is the sphere centre back-facing the plane
bool sphere_back_facing = (dist_to_plane < -r);

// the plane offset for time of collision
float plane_offset = (sphere_back_facing)? -r : r;

// sphere behind the plane, and no double sided test
if (sphere_back_facing && !double_sided_tests)
{
return false;
}

//-----------------------------------------------------------
// sphere cut by the triangle plane
//-----------------------------------------------------------
if(fabs(dist_to_plane) < r)
{
sphere_cut_by_plane = true;
tplane = 0.0f;
Pplane = P - dist_to_plane * N;
}
//-----------------------------------------------------------
// Sphere outside the triangle plane
//-----------------------------------------------------------
else
{
// Sphere not mivong, and not in plane. no collision
if(fabs(dn) < 1.0E-8f)
{
return false;
}

// Sphere is moving

// time of intersection with the plane
tplane = (plane_offset - dist_to_plane) / dn;

// time of collision out of bounds.
if (tplane < 0.0f || tplane > tmax)
return false;

// point of collision on plane at time of impact.
Pplane = P + D * tplane - (plane_offset * N);
}

// sphere too far away from plane
if (tplane < 0.0f || tplane > tmax)
{
return false;
}

//-----------------------------------------------------------
// Test edge collisions one by one
//-----------------------------------------------------------
// Is the sphere found outside the triangle?
bool outside_of_triangle = false;

// have we collided with an edge?
bool collided = false;

int i = 2;
int ip1 = 0;
for(; ip1 < 3; i = ip1, ip1++)
{
// edge direction
Vector E = V[ip1] - V;

// edge length squared
float e2 = E * E;

// edge normal (perpendicular to edge, and triangle plane)
Vector En = E ^ N;

// relative position to edge start.
Vector H = Pplane - V;

// distance of P to edge plane
float hn = H * En;

// Found the point outside the edge
// Need to test against the edge
if (hn > 0.0f)
{
outside_of_triangle = true;

// distance of P along the edge
float he = (H * E);

//-------------------------------------------------------------------
// test collision with the first vertex of the edge
//-------------------------------------------------------------------
if(he < 0.0f)
{
// relative position f sphere centre
H = P - V;

// do a vertex-sphere collision time calculation
// find root of second order equation [P + D.t - Vi]^2 - r^2 = 0
float a = (D * D);
float b = 2.0f * (D * H);
float c = (H * H) - r2;
float d = b*b - 4 * a * c;

// missed the vertex. edge does not collide
if (d < 0.0f)
{
continue;
}
// possible intersection.
// calculate the times of collision
d = sqrt(d);

float t0 = (-b - d) / (2.0f * a);
float t1 = (-b + d) / (2.0f * a);

// sort the times of collision
if(t0 > t1)
{
float t= t0;
t0 = t1;
t1 = t;
}

// vertex is too far away
// go to next edge
if (t0 > tmax || t1 < 0.0f)
{
continue;
}

// found the sphere embedded in the vertex
if(t0 <= 0.0f)
{
// report a sphere-vertex collision
float dist = H.Normalise();
tcoll = 0.0f;
Pcoll = V;
Ncoll = H;
Dcoll = (r - dist) * Ncoll;

// no need to continue further
collided = true;
break;
}

// move sphere to time of collision, and calculate the
// relative positon from vertex
H += D * t0;

// distance to vertex at time of collision
float dist = H.Normalise();

tmax = t0; // our new maximum time of collision found
tcoll = t0;
Pcoll = V;
Ncoll = H;
Dcoll = (r - dist) * Ncoll; // hopefully, 0.

// continue teh search, in case
// another collision is closer.
collided = true;
continue;
}
//-------------------------------------------------------------------
// Test collsion with the end vertex
//-------------------------------------------------------------------
else if (he > e2)
{
// no need to test the end vertex. This will be done on the next edge
// as a start vertex collision.
// a end vertex is always a start vertex of another edge
/// due to the inherent edge loop in a closed polygon.
continue;
}
//-------------------------------------------------------------------
// Test collsion with the edge itself
//-------------------------------------------------------------------
else
{
// relative position f sphere centre
H = P - V;

// do a vertex-sphere collision time calculation
// find root of second order equation [(P + D.t - Vi) x E]^2 - r^2 = 0
Vector DxE = D ^ E;
Vector HxE = H ^ E;

float a = DxE * DxE;
float b = 2.0f * (DxE * HxE);
float c = (HxE * HxE) - r2 * e2;
float d = b*b - 4 * a * c;

// missed the vertex. edge does not collide
if (d < 0.0f)
{
continue;
}

// possible intersection.
// calculate the times of collision
d = sqrt(d);

float t0 = (-b - d) / (2.0f * a);
float t1 = (-b + d) / (2.0f * a);

// sort the times of collision
if(t0 > t1)
{
float t = t0;
t0 = t1;
t1 = t;
}

// vertex is too far away
if (t0 > tmax || t1 < 0.0f)
{
continue;
}

// found the sphere embedded in the vertex
if(t0 < 0.0f)
{
// H is now perpendicular to edge direction
H -= E * (he / e2);

// report a sphere-vertex collision
float dist = H.Normalise();
tcoll = 0.0f;
Pcoll = V;
Ncoll = H;
Dcoll = (r - dist) * Ncoll;

// no need to continue further
collided = true;
break;
}

// found a collision
// move sphere to time of collision, and calculate the
// relative positon from vertex
H += D * t0;

// H is now perpendicular to edge direction
H -= E * (he / e2);

// distance to vertex at time of collision
float dist = H.Normalise();

tmax = t0; // our new maximum time of collision found
tcoll = t0;
Ncoll = H;
Pcoll = V + E * (he / e2);
Dcoll = (r - dist) * Ncoll; // hopefully, 0.

// continue teh search, in case
// another collision is closer.
collided = true;
continue;
}
}
}

// deemed outside the triangle
if(outside_of_triangle)
{
// no edge-vertex collision found, maybe.
return collided;
}

// sphere inside triangle.
// report a plane collision
tcoll = tplane;
Pcoll = Pplane;
Ncoll = (sphere_back_facing)? -N : N;
Dcoll = (sphere_cut_by_plane)? N * (plane_offset - dist_to_plane) : Vector(0, 0, 0);
collided = true;
return collided;
}

Share on other sites
Ok, Thanks Oliii,

Actually I do understand SAT, I think I am applying it to the wrong problem though [lol], It seems more suited for Broad phase than Narrow, which is what I am trying to use it for.

Thanks for the code, hope posting it doesn't get you into trouble (or is it a "give a man a fish" dilema? [smile]).

Quote:
 The one you suggest basically is a bad mix of the SAT and the moving circle-triangle test.

Darn! for a moment there, I though I had come up with a new algo of my own.[sad][lol]

I think maybe what twanvl sugested should not be too computationally expensive, but there may be issues when hitting a vertice head on.

Thanks.

• Game Developer Survey We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 16
• 30
• 9
• 16
• 22