Cannot find bug in frustum culling code

Question

I've written some code for frustum culling, but for some reason, it is not working, and i can't find the bug in it... Maybe a bug in the math, somewhere? So, i'm asking you if anyone could check these values, or give me an idea... Sorry for the lengthy post, but i'm fresh out of ideas, so i'm giving you all available data.

Basically, i have a bounding box centered at (0, 10, 0), with a side of ( 2, 2, 2 ). Corners are correctly calculated to be at ( -1, 9, 1 ), ( 1, 9, 1 ), (-1, 11, 1), ( 1, 11, 1), (-1, 9, -1), (1, 9, -1), (-1, 11, -1), (1, 11, -1).

The camera is at ( 0, 3, 10 ), set up with FOV=60, AspectRatio=800/600, near clip = 1, far clip = 50.

The planes are set up with this function:

void CPlane::SetFrom3Points ( const Vector3f &In_P0, const Vector3f &In_P1, const Vector3f &In_P2 )
    {
    CPlane Plane;
    Vector3f V0, V1;

    // Creates vectors between all three points
    Point = In_P0;
    V0 = In_P1 - In_P0;
    V1 = In_P2 - In_P0;

    // Taking the cross-product of these two vectors, i get the normal to the plane
    Normal = CrossProduct ( V0, V1 );
    Normal.Normalize();
    A = Normal.X;
    B = Normal.Y;
    C = Normal.Z;
    D = - DotProduct ( Normal, Point );
    }

The extracted top plane is: A = 0 B ~= -0.86 C = -0.5 D ~= 7.59

I'm using these 3 first values as the plane's normal. It fails right at the first ( top ) plane, so i'm only presenting that.

Then, there's the check function:

int CFrustum::BoundingBoxInFrustum ( SBoundingBox In_Box )
    {
    int result = FRUSTUM_INSIDE, out,in;

    // for each plane do ...
    for ( int i=0; i < 6; i++ )
        {
        // reset counters for corners in and out
        out=0;
        in=0;
        // for each corner of the box do ...
        // get out of the cycle as soon as a box as corners
        // both inside and out of the frustum
        for ( int k = 0; k < 8 && ( in==0 || out==0 ); k++ )
            {

            // is the corner outside or inside
            float D = Planes[i].GetDistance ( In_Box.Corners[k] );
            if ( Planes[i].GetDistance ( In_Box.Corners[k] ) < 0 )
                out++;
            else
                in++;
            }
        //if all corners are out
        if ( !in )
            return ( FRUSTUM_OUTSIDE );
        // if some corners are out and others are in
        else if ( out )
            return FRUSTUM_INTERSECT;
        }
    return ( result );
    }

and Plane::GetDistance

float CPlane::GetDistance ( Vector3f In_Point )
    {
    return ( D + DotProduct ( Normal, In_Point ) );
    }

In the first iteration in the checking function the point is incorrectly categorized as being outside the plane ( so, above the top plane ), and as such, the bounding box will be categorized as intersecting.

what could be wrong here?

EDIT:Here's an animation showing what's wrong...

That yellow sphere should be considered completely inside the frustum. It's not.

This is what happens with a "field" of spheres so i can check the frustum code...

Don't know if you can see, but most of the spheres inside the frustum are colored yellow ( meaning intersection ), and the whole first row too...

EDIT2: ok, so i re-wrote the code a bit, and came up with this:

int CFrustum::BoundingBoxInFrustum ( SBoundingBox In_Box )
    {
    unsigned Counters[3] = {0, 0, 0};

    for ( int plane = 0; plane < 6; ++plane )
        {
        unsigned PlaneNegative = 0;
        for ( int corner = 0; corner < 8; ++corner )
            {
            Math::CPlane::EHalfspace PointResult = ClassifyPoint ( Planes[plane],     In_Box.Corners[corner] );
            ++Counters[PointResult];
            }
        if ( Counters[Math::CPlane::NEGATIVE] == 8 ) // If all points are on the         negative side of this plane, then the bounding box is not visible
            return FRUSTUM_OUTSIDE;
        Counters[Math::CPlane::NEGATIVE] = 0;
        }
    if ( Counters[Math::CPlane::POSITIVE] == 8 * 6 )
        return FRUSTUM_INSIDE;
    return FRUSTUM_INTERSECT;
    }

CPlane::EHalfspace ClassifyPoint ( const CPlane &In_Plane, const Vector3f &In_Point )
    {
    float Result = In_Plane.D + DotProduct ( In_Plane.Normal, In_Point );
    if ( Result < 0 ) return CPlane::NEGATIVE;
    if ( Result > 0 ) return CPlane::POSITIVE;

//     float d;
//     d = Plane.A * Point.X + Plane.B * Point.Y + Plane.C * Point.Z + Plane.D;
//     if ( d < 0 ) return CPlane::NEGATIVE;
//     if ( d > 0 ) return CPlane::POSITIVE;
    return CPlane::ON_PLANE;
    }

I'm wondering if i may have messed up my plane calculation, since the frustum drawing is so off.. Also, the bounding boxes seem to sometimes disappear on certain positions, and re-appear, so i'm definitely miscalculating something... Can you please double-check my results? For a 60 degree FOV, 1.(3) aspect ratio, 1 and 100 for near and far planes, positioned at (0, 3, 10), this is what got calculated: Planes:

Top 0, -0.866025388, -0.5, 7.59807587

Bottom 0, 0.866025388, -0.5, 2.40192366

Left 0.792405784, 0, -0.609994292, 6.09994316

Right -0.792405784, 0, -0.609994292, 6.09994316

Near 0, 0, -1, 9

Far 0, 0, 1, 90

The frustum corners are then at: ( -0.769800365, 2.42264986, 9 ) ( 0.769800365, 2.42264986, 9 ) ( -0.769800365, 3.57735014, 9 ) ( 0.769800365, 3.57735014, 9 ) ( -76.9800415, -54.7350273, -90 ) ( 76.9800415, -54.7350273, -90 ) (-76.9800415, 60.7350273, -90 ) ( 76.9800415, 60.7350273, -90 )

The code to calculate the planes and corners is this:

float Tangent = ( float ) tan ( DegToRad ( 0.5 * FOV ) ) ;
float NearHeight = Near * Tangent;
float NearWidth = NearHeight * AspectRatio;
float FarHeight = Far * Tangent;
float FarWidth = FarHeight * AspectRatio;

Math::Vector3f NearClip = -ZVector * Near;
Math::Vector3f FarClip = -ZVector * Far;

Corners[SBoundingBox::TOP_NEAR_LEFT] = Position + NearClip +  YVector * NearHeight  - XVector * NearWidth;
Corners[SBoundingBox::TOP_NEAR_RIGHT] = Position + NearClip + YVector * NearHeight +  XVector * NearWidth ;
Corners[SBoundingBox::BOTTOM_NEAR_LEFT] = Position + NearClip - YVector * NearHeight  - XVector * NearWidth;
Corners[SBoundingBox::BOTTOM_NEAR_RIGHT] = Position + NearClip - YVector * NearHeight + XVector * NearWidth;

Corners[SBoundingBox::TOP_FAR_LEFT] = Position + FarClip + YVector * FarHeight - XVector * FarWidth;
Corners[SBoundingBox::TOP_FAR_RIGHT] = Position + FarClip + YVector * FarHeight + XVector * FarWidth;
Corners[SBoundingBox::BOTTOM_FAR_LEFT] = Position + FarClip - YVector * FarHeight - XVector * FarWidth;
Corners[SBoundingBox::BOTTOM_FAR_RIGHT] = Position + FarClip - YVector * FarHeight + XVector * FarWidth;

Planes[FRUSTUM_TOP].SetFrom3Points ( Corners[SBoundingBox::TOP_NEAR_RIGHT], Corners[SBoundingBox::TOP_NEAR_LEFT], Corners[SBoundingBox::TOP_FAR_LEFT] );
Planes[FRUSTUM_BOTTOM].SetFrom3Points ( Corners[SBoundingBox::BOTTOM_NEAR_LEFT], Corners[SBoundingBox::BOTTOM_NEAR_RIGHT], Corners[SBoundingBox::BOTTOM_FAR_RIGHT] );
Planes[FRUSTUM_LEFT].SetFrom3Points ( Corners[SBoundingBox::TOP_NEAR_LEFT], Corners[SBoundingBox::BOTTOM_NEAR_LEFT], Corners[SBoundingBox::BOTTOM_FAR_LEFT] );
Planes[FRUSTUM_RIGHT].SetFrom3Points ( Corners[SBoundingBox::BOTTOM_NEAR_RIGHT], Corners[SBoundingBox::TOP_NEAR_RIGHT], Corners[SBoundingBox::BOTTOM_FAR_RIGHT] );
Planes[FRUSTUM_NEAR].SetFrom3Points ( Corners[SBoundingBox::TOP_NEAR_LEFT], Corners[SBoundingBox::TOP_NEAR_RIGHT], Corners[SBoundingBox::BOTTOM_NEAR_RIGHT] );
Planes[FRUSTUM_FAR].SetFrom3Points ( Corners[SBoundingBox::TOP_FAR_RIGHT], Corners[SBoundingBox::TOP_FAR_LEFT], Corners[SBoundingBox::BOTTOM_FAR_LEFT] );

Answer 1

The bounding box you described is intersecting the frustum, even if your visualisation isn't making it apparent.

At a position of 0, 10, 0, and the camera's position at 0, 3, 10, the difference in position is 0, 7, 10.

Further, the difference of position from the camera to the top-most near corner of the 2x2x2 box is actually 0, 8, 9.

With a FOV of 60 degrees, the camera has 30 degrees between the horizon and the top plane. Over a horizontal distance of 9 units, the frustum will certainly fall short of the 8 units it needs to rise (atan(8/9) = ~42 degrees).

I hope that makes sense. I can't imagine what would bring about the problems in your second picture -- especially the whole first row "intersecting" the frustum, but perhaps it's another issue altogether.