View Full Version : AABB-Triangle intersection point

overTaker

04-16-2014, 10:09 AM

Hello.

I'm in need of testing if an axis oriented bounding box collides with a triangle (set of triangles as a terrain), and if it does - in which point. I found few algorithms on the internet, but I can't determine the intersection point, which is essential for me here.

Is there an algorithm to achieve what I need? Or maybe is there some method that suits this task better?

Thanks.

Brokenmind

04-16-2014, 12:30 PM

First, you need to better define what you need. The intersection of a triangle and a bounding box rarely has only one point; most of the times, its an edge.

In case you do this without predefined methods:

You could simply write some algorithms that test whether one point is in the box and the other points are out of it, then an intersection is quaranteed (the intersection point can then easily be calculated). If all points are outside the box but the triangle cuts it nevertheless, you need to split the triangle in its edges and the boxes in its squares and do edge-plane-intersections. Those routines are fairly easy to code once you know the underlying maths ;)

overTaker

04-16-2014, 12:43 PM

I got it, I just wanted to simplify the question, and it went in wrong direction :)

What I understood, good thing would be to check ray-triangle intersection, where there are three rays - for the triangle edges, that would check for intersection with each of box's rectangles?

I already got pretty good ray-triangle intersection method, so it can be good idea, but won't checking it every time the object moves, be kind of bottleneck? Well, I will implement it first, and then check it's performance. Thanks for pointing me the right way! I will surely post more here.

reto.koradi

04-16-2014, 11:16 PM

The triangle and the box could intersect even if none of the triangle edges intersects the box. Picture a large triangle, and a small box sitting in the middle of the triangle.

Brokenmind: Wouldn't the intersection typically be a polygon? At least that's the case if you look at the triangle as a 2D area, and the cube as a 3D volume. The intersection is then a subset of the triangle.

At first sight, I would probably solve this with a clipping algorithm. Start with the original triangle, and clip it with the 6 planes that define the box, one by one.

Brokenmind

04-17-2014, 12:12 AM

You're right, I forgot to mention that each of the tests that was done with the triangle edges and the quad must also be done with the quad edges and the triangle.

The intersection would be a polygon or at least a line strip if you look at the triangle - cube intersection. For simplicity, I would suggest to divide it into the triangle - quad intersection which then only gets an edge as intersection, given the two faces don't intersect coplanarly (then it gets ugly ;) ).

@OP: Depending on the field of use, you could also use a tree to resemble your geometry (BBtree, KDtree or such) to get rid of the O(nē) bottleneck. This doesn't help with the pure intersection mathematics, though.

reto.koradi

04-17-2014, 08:41 AM

I still think that anything based on edges is going to be very cumbersome to implement. Picture the triangle completely inside the cube. No triangle edge intersects a face of the cube. No cube edge intersects the triangle. Yet, the triangle and the cube intersect. You could handle this case with additional conditions, but it's going to get painful.

The clipping approach I suggested seems much simpler. It's just like clipping of a triangle against the view volume if you implement an OpenGL style renderer in software.

Powered by vBulletin® Version 4.2.3 Copyright © 2018 vBulletin Solutions, Inc. All rights reserved.