 Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki Blog Search Turing Chat Room Members
Triangle-cube collision.       Author Message
CodeMonkey2000 Posted: Sun Jul 27, 2008 4:21 pm   Post subject: Triangle-cube collision.

I'm trying to build an octree class to speed up the rendering for my game. One problem I ran into, and can't seem to solve is how to determine if a triangle and a cube is intersecting. I tried to work it out, initially I tested each line of the triangle with each line of the cube, but that wasn't including all possible ways of colliding. I tried to play around with the planar equation of the triangle and seeing which side of the plane each of the vertexes of the box lies in, that didn't work out either. Do you guys know a god way of determining whether or not a triangle and a cube are colliding?    richcash Posted: Sun Jul 27, 2008 7:39 pm   Post subject: Re: Triangle-cube collision.

The first thought that comes to mind is to project the triangle onto the plane of each square (of the cube) and check if the projected triangle is overlapping its corresponding square. If a triangle is inside a cube, then it must be intersecting all surfaces of the cube when projected along that surface's plane (so you could stop checking as soon as one projected triangle does not intersect its corresponding surface). Oh, are your cubes by any chance parallel to the axes? If so, projecting the triangles would be trivial, you would just have to use the right pairs of coordinates from each 3d point and this method would work wonderfully.

You could also check if any of the triangles' lines are intersecting with any of the cubes' surfaces. That would be 18 checks. Find the point of intersection (if there is one) between the line (of the triangles' line segments) and the plane (of the cube's squares) and check if that point of intersection is on the corresponding line and corresponding square. You wouldn't have an early-exit condition here, though, as above.

I don't have much time to think, I shall keep thinking and post later.   Posted: Mon Jul 28, 2008 7:02 am   Post subject: Re: Triangle-cube collision.

Some more information could make this alot easier to answer. Are the cubes axis aligned (as richcash said), also are the triangles axis aligned, or are the triangles treated as 2d. CodeMonkey2000 Posted: Mon Jul 28, 2008 11:25 am   Post subject: Re: Triangle-cube collision.

The cubes are axis aligned. The triangle are 3D, having 3 vertices and edges. They aren't necessarily axis-aligned since I'm reading them from a .obj file.

EDIT: I think richcash's solution will work, but I'm not sure on which pairs of coordinates to use for each plane. DemonWasp Posted: Mon Jul 28, 2008 1:26 pm   Post subject: RE:Triangle-cube collision.

Your easiest bet is going to be something like this:

1. Determine the point of intersection of each line segment in the triangle with the extended plane of each face in the cube (trivial arithmetic, given as the cubes are axis-aligned).

2. Determine whether that point is BOTH within the bounding square representing that face and within the boundaries of the two endpoints on the line segment. If both of these are true, then that line intersects that face --> collision.

3. Keep testing through the 18 possibilities until you have sufficient information to stop processing. CodeMonkey2000 Posted: Mon Jul 28, 2008 1:57 pm   Post subject: RE:Triangle-cube collision.

DemonWasp, the line segments don't necessarily have to be intersecting with the planes of the cube for a collision. If a cube's corner is poking through the triangle, none of the lines are intersecting within bounds of the cube planes, but it's still a collision. richcash Posted: Mon Jul 28, 2008 5:24 pm   Post subject: Re: Triangle-cube collision.

CodeMonkey2000 wrote:

DemonWasp, the line segments don't necessarily have to be intersecting with the planes of the cube for a collision. If a cube's corner is poking through the triangle, none of the lines are intersecting within bounds of the cube planes, but it's still a collision.

That is correct, so my second method (which is the same as DemonWasp's method) will not work without additional work.

CodeMonkey2000 wrote:

The cubes are axis aligned. The triangle are 3D, having 3 vertices and edges. They aren't necessarily axis-aligned since I'm reading them from a .obj file.

If you have a plane aligned with an axis (let's say, the z-axis) so that every point in that plane is at z = 5. To project three points onto that plane, you make all of their z-coordinates equal to 5. In this case, you don't even need to do that. You just take the appropriate coordinates from each point and the same coordinates from the points on the square and check for intersection.

e.g. a surface square with opposite corners (20, 20, 5) and (35, 35, 5). the triangle is (x1, y1, z1), (x2, y2, z2), (x3, y3, z3). Just check if the triangle (x1, y1), (x2, y2), (x3, y3) is intersecting the square (20, 20), (35, 35).

And I just thought of something. Because of the nature of a cube, I think you only have to check 2 non-parallel surfaces of the cube. If the triangle, projected onto the plane of two non-parallel surfaces of the cube, intersects each corresponding surface square, then there is a collision. That's pretty fast, that's probably the best method. It's just 2 triangle-square collision checks. CodeMonkey2000 Posted: Mon Jul 28, 2008 5:36 pm   Post subject: Re: Triangle-cube collision.

richcash @ Mon Jul 28, 2008 5:24 pm wrote:

And I just thought of something. Because of the nature of a cube, I think you only have to check 2 non-parallel surfaces of the cube. If the triangle, projected onto the plane of two non-parallel surfaces of the cube, intersects each corresponding surface square, then there is a collision. That's pretty fast, that's probably the best method. It's just 2 triangle-square collision checks.

Actually it would be 3 wouldn't it? So 9 checks at the worst case, which is still pretty fast. Thanks!    zylum  Posted: Mon Jul 28, 2008 6:18 pm   Post subject: RE:Triangle-cube collision.

If you are planning on using octrees for visibility determination / pruning then you must know that the object must be entirely bound for it to work. ie all vertices must be within the box. Thus this requires only 18 comparisons since your boxes are axis-aligned. Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First        Page 1 of 1  [ 9 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: