Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Results 1 to 6 of 6

Thread: AABB-Triangle intersection point

  1. #1
    Intern Newbie
    Join Date
    Feb 2014
    Posts
    38

    AABB-Triangle intersection point

    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.

  2. #2
    Intern Contributor Brokenmind's Avatar
    Join Date
    Feb 2014
    Location
    Aachen / Germany
    Posts
    71
    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

  3. #3
    Intern Newbie
    Join Date
    Feb 2014
    Posts
    38
    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.

  4. #4
    Intern Contributor
    Join Date
    Mar 2014
    Location
    San Jose, CA
    Posts
    58
    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.

  5. #5
    Intern Contributor Brokenmind's Avatar
    Join Date
    Feb 2014
    Location
    Aachen / Germany
    Posts
    71
    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.

  6. #6
    Intern Contributor
    Join Date
    Mar 2014
    Location
    San Jose, CA
    Posts
    58
    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •