Jump to content
  • Advertisement
Sign in to follow this  
ehsan2004

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

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement
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
Hidden

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.


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?
intersect.JPG?psid=1

Share this post


Link to post
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

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.


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

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.

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

[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.

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.
http://www.gamedev.net/topic/608676-what-is-a-good-algorithm-to-test-whether-a-triangle-intersects-cube/

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!