Check if line segment or triangle intersects a frustum

Question

I have a frustum made of six planes, normals all pointing inwards. I can check if a point is inside the frustum with this function:

char ClassifyPoint(float x, float y, float z, char thePlane)
    {
        Vector& aPos=mPlane[thePlane].mPos;
        Vector& aNorm=mPlane[thePlane].mNormal;
        float aD=(aPos.mX-x)*aNorm.mX+(aPos.mY-y)*aNorm.mY+(aPos.mZ-z)*aNorm.mZ;
        if (aD<-0.0005f) return 1;if (aD>0.0005f) return -1;return 0;
    }

Which gives me -1, 0, 1 for if the point is front, on, or behind each plane. This works fine for a single point, but a line segment or a triangle could have ALL points outside the frustum but still be intersecting it.

What's the right way to judge if a line or triangle intersects? Everything I've tried always produces false positives because checking against six planes.

Edit, more info:

So to classify a line, I tried this:

inline char ClassifyLine(Vector theL1, Vector theL2, char thePlane) 
    {
        return ClassifyPoint(theL1,thePlane)+ClassifyPoint(theL2,thePlane);
    }

Which should produce "2" if both points are in front of the plane, 0 if it's straddling the plane, or any negative number if both points are behind the plane-- right?

But then I try this function to see if the frustum contains a line:

inline bool ContainsLine(Vector theLine1, Vector theLine2)
    {
        if (ClassifyLine(theLine1,theLine2,0)<0) return false;
        if (ClassifyLine(theLine1,theLine2,1)<0) return false;
        if (ClassifyLine(theLine1,theLine2,2)<0) return false;
        if (ClassifyLine(theLine1,theLine2,3)<0) return false;
        if (ClassifyLine(theLine1,theLine2,4)<0) return false;
        if (ClassifyLine(theLine1,theLine2,5)<0) return false;
        return true;
    }

And I get both false positives and false negatives with certain lines that straddle. What am I doing wrong here?

Answer 1

Clip the line segment to each of the six half-spaces defined by the six planes. The line segment intersects the frustum if and only if anything remains after that:

• let (a, b) be the line segment between points a and b
• for each plane P:
  • if a and b are both on the "inside" side of P, continue
  • if a and b are both on the "outside" side of P, return false
  • find the intersection x between P and (a, b)
  • if a is on the "inside" side of P, assign b := x
  • else (b is on the "inside" side of P), assign a := x
• return true

Note that this does not work for triangles, just for line segments (what you call "lines", but in mathematics a line is infinite).