0
\$\begingroup\$

What is the best way how to perform intersection test between triangular-prism (used as bounding "box") and line-segment (NOT ray)? The triangular prism is not axis-aligned and it is stored as a triangle (3x 3D coordinates) and the height of the triangle?

If you advise me some "mathematicaly" optimalized solution (not just simple geometric but something like Moller-Trumbore for simple triangle) I will be grateful. I don't need the distance, just bool value (intersect/not intersect).

\$\endgroup\$
1
\$\begingroup\$

You could try decomposing the prism into triangles and then test line against each triangle:

enter image description here

as you say Moller-Trumbore triangle intersection can be used for this, for example:

bool rayIntersectTriangle(vector3 line_a, vector line_b, vector tri_a, vector tri_b, vector tri_c)
{
    vector edge1 = tri_b - tri_a;
    vector edge2 = tri_c - tri_a;
    vector line  = line_a - line_b;

    vector tri_normal = cross(edge1,edge2);

    // if d<=0 line pointing away for tri, no intersection
    float d = dot(line,tri_normal);
    if(d<=0.0f)
        return false;

    // if parametric intersection t if <0.0f or >d then segment does not intersect
    vector aa = line_a - tri_a;
    float t = dot(aa,tri_normal);
    if(t<0.0f || t>d)
        return false;

    // calculate barycentric coords to check if segment within bounds
    vector e = cross(line,aa);
    float v = dot(edge2,e);
    if(v<0.0f || v>d)
        return false;
    float w = -dot(edge1,e);
    if(w<0.0f || v+w>d)
        return false;

    // we must have intersection...
    return true;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ That wouldn't cover the case of the line segment being fully inside the triangular prism \$\endgroup\$ – Torious Jan 26 '17 at 22:22
  • 1
    \$\begingroup\$ ah good catch... you probably need to do a points behind every plane test for that case. \$\endgroup\$ – Biggy Smith Jan 26 '17 at 22:35
1
\$\begingroup\$

As far as I know the only somewhat efficient way is to take the line segment, iterate over the 5 planes of the triangular prism (one for each side), and "cut" the line segment by each plane. You keep the part of the line segment that is inside the shape. If, after one of the cuts, there is nothing left of your line segment, you have determined the line segment does NOT intersect the volume of the prism. Note that this doesn't work for concave 3D shapes.

\$\endgroup\$
  • \$\begingroup\$ This sound's like an interesting solution. I try to implement it... Maybe, I had an another idea to solve this using projections: project the triangle and segment to xy-plane and check the intersection. If intersect then project to xz-plane and simply check if segment z-values are in bottom and top threshold (height of triangle). Do you think that this is possible or it's not the right way? \$\endgroup\$ – user283474 Jan 27 '17 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.