Cylinder-Triangle Collision?

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

Recommended Posts

anyone have any good material for doing cylinder-triangle collision?

Share on other sites
While I cannot give a concrete answer, I can give a few pointers.

First of all, try doing a sphere/triangle collision first if you haven't. It is the easiest collision there is against a triangle and will help you learn some basics.

If you need a cylinder shape for the player I would recommend you use a capsule shape instead. A capsule is like a cylinder only with half spheres covering the caps. This is better for player collision because it allows the player to easily slide over small bumps in terrain where cylinder would get caught, and the capsule is also easier to do collision detection for. It turns out that the flat ends of the cylinder are a little difficult to deal with.

So before I start giving a more elaborate answer perhaps you could give some more context. Specifically, what do you plan on using this for? Would the capsule shape be better suited? Do you need to only detect IF they overlap or do you have to correct the overlap?

Share on other sites

I currently have ellipsoid collisions implemented . . . The problem is (which is also shared with capsules) is that, while, yes, it allows you to graze over slopes and hills easily - it doesn't do very well with actual "steps". Yes, it handles stairs, I understand -- But once you get "stairs" of a certain height, it can't overcome it . . .

More specifically, not "stairs", but various environmental obsticles that are actually practicle, for example... If you have an indoor building with a garden "island" in the center of the room, there may be a small "guard" surrounding it which should typically be able to be grazed over.

I have imported a map from quake into my engine with this exact architecture -- In quake, you're able to graze over these steps without any slowdown. I'm trying to make my collisions more like quake, and if that means using AABB (which quake uses) instead of cylinder, then I'd like to.

Another "hangup" of the ellipsoid/capsule path is how it "hangs" over when you approach an edge, slightly decreasing as you move away from the edge and inclining as you move back onto it.  Again, this is unlike quake in that you are either on the edge or falling down -- no variable height.

These couple issues don't bode well when aiming for a fast-paced/competative atmosphere akin to quake. It makes things feel very "sticky".

Share on other sites

that paper uses relatively cryptic high level math . . .

I wonder how swept cylinder collisions are different than a straight intersection test check . . Because, I think that's what i'm really trynig to do

Share on other sites

anyone have any good material for doing cylinder-triangle collision?

Hmm.

I agree with HappyCoder. It'd actually be easier if you use a capsule. What I'd do is: I'd turn it into a triangle-to-line-segment test. I'd shrink the capsule until it had a radius of zero (a line segment that extended from the base of each of the hemispheres on the end, going through the center of the capsule), and then find the minimum distance between that line segment to the triangle. Once you find that distance, you do a check to see if the radius of the capsule is larger than they distance between the capsule and triangle, just like you do with a cylinder-to-point test.

Also, I'd use an existing physics engine if I were you. It makes problems like these much simpler.

Edited by CulDeVu

Share on other sites

So I've figured out a proper collision test.

I used the plane-vs-cylinder collision from here:

http://www.geometrictools.com/LibMathematics/Intersection/Wm5IntrPlane3Cylinder3.cpp

Then once you know the triangle plane intersects the cylinder, you do a 2D x,z circle-vs-triangle test.

If both pass, then there is a collision . . .

I also have proper pushback on the normal...

But now I'm wondering if/how I can turn this into a swept test so that if the velocity is > cylinder height, it will still properly collide...

#define RADIANS_PER_DEGREE 0.017453292519943295

bool circleVsTriangle( float* center, float radius, float triangle[3][2] )
{
#define p0x triangle[0][0]
#define p0y triangle[0][1]
#define p1x triangle[1][0]
#define p1y triangle[1][1]
#define p2x triangle[2][0]
#define p2y triangle[2][1]

float A  = .5*(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);

int sign = A<0?-1:1;

float s = sign*(p0y*p2x - p0x*p2y + (p2y - p0y)*center[0] + (p0x - p2x)*center[1]);
float t = sign*(p0x*p1y - p0y*p1x + (p0y - p1y)*center[0] + (p1x - p0x)*center[1]);

if( s >= 0 && t >= 0 && s + t <= 2 * sign * A )
return true;

float a;
float b;

a = triangle[0][0] - center[0];
b = triangle[0][1] - center[1];
if( a * a + b * b <= radius * radius )
return true;

a = triangle[1][0] - center[0];
b = triangle[1][1] - center[1];
if( a * a + b * b <= radius * radius )
return true;

a = triangle[2][0] - center[0];
b = triangle[2][1] - center[1];
if( a * a + b * b <= radius * radius )
return true;

float dx;
float dy;
float dr2;
float D;

float c;
float d;

a = triangle[0][0] - center[0];
b = triangle[1][1] - center[1];
c = triangle[1][0] - center[0];
d = triangle[0][1] - center[1];
dx = triangle[1][0] - triangle[0][0];
dy = triangle[1][1] - triangle[0][1];
dr2 = dx * dx + dy * dy;
D = a * b - c * d;
if( r2 * dr2 - D * D >= 0 )
return true;

a = triangle[1][0] - center[0];
b = triangle[2][1] - center[1];
c = triangle[2][0] - center[0];
d = triangle[1][1] - center[1];
dx = triangle[2][0] - triangle[1][0];
dy = triangle[2][1] - triangle[1][1];
dr2 = dx * dx + dy * dy;
D = a * b - c * d;
if( r2 * dr2 - D * D >= 0 )
return true;

a = triangle[2][0] - center[0];
b = triangle[0][1] - center[1];
c = triangle[0][0] - center[0];
d = triangle[2][1] - center[1];
dx = triangle[0][0] - triangle[2][0];
dy = triangle[0][1] - triangle[2][1];
dr2 = dx * dx + dy * dy;
D = a * b - c * d;
if( r2 * dr2 - D * D >= 0 )
return true;

return false;
}

void checkTriangle( triangle* trianglePlane, float* start, float* end )
{
float n[3] = { 0, 1, 0 };

float absNdW = vectorDot( trianglePlane->normal, n );
float root = sqrt(fabsf(1 - absNdW*absNdW));
float term = RADIUS*root + 3.5*absNdW;

if( fabsf( vectorDot( start, trianglePlane->normal ) + trianglePlane->distance ) <= term ) // triangle plane collides cylinder
{

float center[2] = { start[0], start[2] };
float v[3][2] = {
{trianglePlane->P1[0],trianglePlane->P1[2]},
{trianglePlane->P2[0],trianglePlane->P2[2]},
{trianglePlane->P3[0],trianglePlane->P3[2]}
};

if( circleVsTriangle( center, RADIUS, v ) )
{
float end[3] = {*x,*y,*z};
float OQ[3]; vectorSubtraction( OQ, start, end );
float OQmag = vectorMagnitude( OQ );

#define angle acosf( vectorDotProduct( OQ, trianglePlane->normal ) / ( OQmag ) )

float a = OQmag * sinf( 90 * RADIANS_PER_DEGREE - angle );

if( a != a ){
printf( "a is NaN!\n" );
a = OQmag * sinf( 90 * RADIANS_PER_DEGREE );
}

end[0] += trianglePlane->normal[0] * a; // pushbash response
end[1] += trianglePlane->normal[1] * a;
end[2] += trianglePlane->normal[2] * a;
}
}
}



Would anyone possibly know how to modify/combine this code with the code in the following paper on swept ellipsoids to make it swept cylinder?

http://www.peroxide.dk/papers/collision/collision.pdf

Edited by 3TATUK2

• 18
• 29
• 11
• 23
• 16