Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


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


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 ehsan2004   Members   -  Reputation: 157

Like
0Likes
Like

Posted 16 August 2011 - 05:02 PM

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?
Posted Image

Sponsor:

#2 Trienco   Crossbones+   -  Reputation: 2207

Like
0Likes
Like

Posted 16 August 2011 - 10:33 PM

You will simply have to do a lot of edge/polygon tests in BOTH directions (triangle edges vs cube faces and cube edges vs triangle).
f@dzhttp://festini.device-zero.de

#3 0Circle0   Members   -  Reputation: 343

Like
1Likes
Like

Posted 17 August 2011 - 06:37 AM

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.

Attached Thumbnails

  • example1.jpg
  • example2.jpg

Sprite Creator 3 VX & XP

WARNING: I edit my posts constantly.


#4 Eric Lengyel   Crossbones+   -  Reputation: 2389

Like
0Likes
Like

Posted 17 August 2011 - 01:37 PM

The best way to do this is to clip the triangle against the six planes bounding the cube. If there's anything left of the triangle at the end, then it intersects the cube. If everything gets clipped away at any step, then the triangle is completely outside the cube.

#5 biki_   Members   -  Reputation: 223

Like
0Likes
Like

Posted 19 August 2011 - 06:08 AM

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.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS