line segment triangular-prism intersection

Question

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).

Answer 1

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

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;
}

Answer 2

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.