Sign in to follow this  
ehsan2004

What is a good algorithm to test whether a triangle is inside a cube?

Recommended Posts

ehsan2004    178
I'm implementing octrees which will contain a list of triangles. What is a good algorithm to test whether a triangle is inside a cube? I've done quite a lot of googling, but every resource skips over this part!
EDIT: I moved this topic to the math and physics forum.

Share this post


Link to post
Share on other sites
Sirisian    2263
A triangle is fully contained if all 3 points are in the cube. if (x > cube.minX && x < cube.maxX && ... same for y and z)

If you want to know if a triangle is in or intersects a cube then it's tricker. Looking at the inverse might be easier. When isn't a triangle in/intersecting a cube. Off the top of my head a triangle isn't in the cube when the 3 points aren't in the cube. Also if all 8 points of the cube are on one side of the triangle.

Share this post


Link to post
Share on other sites
ehsan2004    178
Hidden
[quote name='Sirisian' timestamp='1313532977' post='4850062']
A triangle is fully contained if all 3 points are in the cube. if (x > cube.minX && x < cube.maxX && ... same for y and z)

Off the top of my head a triangle isn't in the cube when the 3 points aren't in the cube.
[/quote]

It's not that easy. In the following diagram,p1,p2 and p3 are the vertices of the triangle. non of the vertices lie within 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
alnite    3438
For a triangle intersecting a cube, you can just check if one of the points of the triangle is inside the cube?

If you want to check if the triangle is entirely inside the cube, then check for all three points.

Share this post


Link to post
Share on other sites
BrianJensen    343
[quote name='alnite' timestamp='1313580585' post='4850250']
For a triangle intersecting a cube, you can just check if one of the points of the triangle is inside the cube?

If you want to check if the triangle is entirely inside the cube, then check for all three points.
[/quote]

Easier said than done, there is more math to it than that, as you can see from the simple image. Obviously the triangle is intersecting the cube but no point from the triangle is inside the cube nor is any point from the cube inside the triangle.Sorry I can't draw it in 3d. :) but imagine the triangle stays on top with each edge outside the box.

EDIT: Best I can do with 3d...eh I cannot draw to save my life.

Share this post


Link to post
Share on other sites
lauris71    841
[quote name='alnite' timestamp='1313580585' post='4850250']
For a triangle intersecting a cube, you can just check if one of the points of the triangle is inside the cube?

If you want to check if the triangle is entirely inside the cube, then check for all three points.
[/quote]
No - for example big triangle may intersect with cube even if all points are outside cube.


I think you could use a simplified version of separating axis theorem - project all corners of cube to the triangle normal and check, whether all ot these projections are at the same side from triangle.

Share this post


Link to post
Share on other sites
BrianJensen    343
[quote name='Lauris Kaplinski' timestamp='1313582979' post='4850272']
[quote name='alnite' timestamp='1313580585' post='4850250']
For a triangle intersecting a cube, you can just check if one of the points of the triangle is inside the cube?

If you want to check if the triangle is entirely inside the cube, then check for all three points.
[/quote]
No - for example big triangle may intersect with cube even if all points are outside cube.


I think you could use a simplified version of separating axis theorem - project all corners of cube to the triangle normal and check, whether all ot these projections are at the same side from triangle.


[/quote]

Right when I read that, I though that exactly, tried drawing an example. I was going to suggest raycasting; however I know there is a mathematical formula somewhere for it.

This is OP's post in the math section.
[url]http://www.gamedev.net/topic/608676-what-is-a-good-algorithm-to-test-whether-a-triangle-intersects-cube/[/url]

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