Sign in to follow this  
aslangsfma

triangle cylinder intersection test

Recommended Posts

hi I want to find a cylinder and triangle intersection. I only need are they intersected.It must be very fast. I have start and finish points of cylinder's axis and cylinder's radius is always 1.and I have triangle's 3 points.Thanks for helps.

Share this post


Link to post
Share on other sites
I'll venture a solution, but Cylinders are known to be problematic.

This is just speculation though, I'm not sure if this would work, but I dont see why not. And it would be straight forward to implement and test. Ok, so here goes...



cylinder (A, B, r)
triangle (V0, V1, V2)

1) find closest point from triangle and segment [AB] :
-----------------------------------------------------
. find closest point on triangle from infinite line (AB).
. if point in the segment boundaries of [AB], use it.
. if point before A :
-> find closest on triangle from A, and use it.
. if point after B :
-> find closest on triangle from B, and use it.

2) check if closest point is in cylinder :
------------------------------------------
. well, just a point in cylinder check, easy.


Note that going through the steps, you could optimise it relatively by quite a lot (instead of writing each step as a function).

EDIT : Ignore all that. It's a bit more complicated.

[Edited by - oliii on January 19, 2009 5:10:49 AM]

Share this post


Link to post
Share on other sites
it's actually more complicated, as there could be an infinite number of points closest to the triangle (if the infinite line is parallel to the triangle).

so theoretically, you would have to find the segment / point on the triangle the closest to the line / segment.

I suppose using an iterative solution (GJK / MPR) would work better. MPR probably the easiest, it stands for Minkowsky Portal Refinement and works through support functions like GJK.

Molly Rocket, XenoCollide developped and used the MPR. It is quite a (relatively) simple algorithm. I cant give you the code right now, I suppose I'd have to write a demo, something I'm keen on.

Share this post


Link to post
Share on other sites
if you need something quick, I can give you a moving sphere algorithm, which can be converted to a capsule test (basically a cylinder with rounded ends).

http://members.gamedev.net/oliii/satpost/3DSpherePolygonCollision.cpp

Share this post


Link to post
Share on other sites
the MPR is in Game Programming Gems 7 (the MollyRocket chapter).

I suppose you can give this a shot though.

http://jgt.akpeters.com/papers/KarabassiEtAl99/collision.html

as you can see the cylinder test is NASTY.

a blob is basically a capsule test. They seem to use a capsule test, and then constrain the test to cylinder caps.

Share this post


Link to post
Share on other sites
Thank you for link.I want to know a triangle's closest point is one of its angle or on one
of its line segments.And it can be parallel like your told.I learnt find the closest point
between line and point.But I don't have any idea for find the closest point when its parallel.

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