Trianglecube collision.
Author 
Message 
CodeMonkey2000

Posted: Sun Jul 27, 2008 4:21 pm Post subject: Trianglecube 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?






Sponsor Sponsor



richcash

Posted: Sun Jul 27, 2008 7:39 pm Post subject: Re: Trianglecube 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 earlyexit condition here, though, as above.
I don't have much time to think, I shall keep thinking and post later.






Saad

Posted: Mon Jul 28, 2008 7:02 am Post subject: Re: Trianglecube 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: Trianglecube collision. 


The cubes are axis aligned. The triangle are 3D, having 3 vertices and edges. They aren't necessarily axisaligned 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:Trianglecube 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 axisaligned).
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:Trianglecube 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: Trianglecube 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 axisaligned since I'm reading them from a .obj file.
If you have a plane aligned with an axis (let's say, the zaxis) so that every point in that plane is at z = 5. To project three points onto that plane, you make all of their zcoordinates 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 nonparallel surfaces of the cube. If the triangle, projected onto the plane of two nonparallel 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 trianglesquare collision checks.






CodeMonkey2000

Posted: Mon Jul 28, 2008 5:36 pm Post subject: Re: Trianglecube 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 nonparallel surfaces of the cube. If the triangle, projected onto the plane of two nonparallel 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 trianglesquare 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:Trianglecube 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 axisaligned.







