Sign in to follow this  
ehsan2004

What is a good algorithm to test whether a triangle intersects cube

Recommended Posts

I'm implementing octrees which will contain a list of triangles. What is a good algorithm to test whether a triangle intersects an axis aligned cube? I've done quite a lot of googling, but every resource skips over this part!

In the following image, all the vertices of the triangle lie outside the cube. However, some parts of the triangle lie within the cube. How to solve this case?
[img]https://blufiles.storage.live.com/y1p6qTT9PWGj1Nc-TiywtFAZlGZCYCFyPpkKp5bK9aDvF4KvpLXhE0vCY6etFiphq4qun4YBAJVuQo/intersect.JPG?psid=1[/img]

Share this post


Link to post
Share on other sites
I posted in your other post. that shows an example both in 2d and 3d where no points from either object are inside the other object but are still intersecting. You will have to implement and edge collision detection rather than the more common point collision.

You could do something like the second image which makes the box a set of triangles and splits the triangle into more triangles. Now you can see there is a point intersection, and the more triangles you split it into the more accurate it is. In the second image you can clearly see compared to the first which had no point intersections that now there are 2 points intersecting. Image 2 has a higher polygon count.

Share this post


Link to post
Share on other sites
here is how i do it.
1. test box with triangles bounding box. if no intersection return 'false'
2. test box agains triangle plane. if no intersection return 'false'
3. perform 3 2d overlap tests in xy, yz, zx planes if no overlap of triangle projection with box projection is found in any plane return 'false'
4. return 'true'

this thing is equivalent to minkowski sum method but can be coded a bit easier.

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