frustum culling not filtering out bboxes correctly

Question

I'm writing some frustum culling code ( once again ), and it's mostly working, but for some reason, some boxes are showing as intersecting the frustum when they really aren't. I setup a 10x10 grid of spheres on a XY plane, every 4 units, on Z=-3.

This is the snippet responsible for creating all those spheres, in case it matters

for ( int X = -20; X <= 20; X += 2 )
{
    for ( int Y = -20; Y <= 20; Y += 2 )
    {
        (...)
        SphereEntity->SetPosition ( glm::vec3 ( X * 2, Y * 2, -3 ) );
    }
}

The frustum is fixed at 0,0,0, with FOV of pi/2, near plane of 0.1, far plane of 10, and aspect ratio of 1, looking along the negative Z axis.

The result can be seen in this screenshot.

It's kind of hard to understand the image with no relative positions. The frustum is being drawn with those green->blue lines. near plane is to the left ( 4 green corners ), far plane to the right of the image, away from the viewer ( the 4 blue corners ). I've also drawn the plane points and normals, for debugging ( the white->red little lines ). They appear correct so far.

From the other side of the sphere wall, it looks like this.

For some reason, my culling code is letting a lot of spheres be detected as intersecting the frustum, when they're actually not. Green for inside, blue for intersecting, red for outside.

This is the frustum checking function:

CollisionResult CheckAABBFrustumCollision ( const BoundingBox &Box, const Frustum &ViewFrustum )
{
    glm::vec3 Corners[8];
    CalculateBoundingBoxCorners ( Box, Corners );
    const Geometry::Plane *Planes = ViewFrustum.GetPlanesReference ();
    for ( unsigned PlaneIndex = 0; PlaneIndex < 6; ++PlaneIndex )
    {
        unsigned Inside = 0, Outside = 0, Intersect = 0;
        for ( unsigned CornerIndex = 0; CornerIndex < 8; ++CornerIndex )
        {
            float Distance = GetDistanceFromPlaneToPoint ( Planes[PlaneIndex], Corners[CornerIndex] );
            if ( Distance < 0.0f )
                ++Outside;
            else if ( Distance > 0.0f )
                ++Inside;
            else
                ++Intersect;
            if ( ( ( Outside != 0 ) && ( Inside != 0 ) ) ||// Early exit. If there are points inside and outside the frustum, then it's automatically an intersection
                ( Intersect != 0 ) )
                return CollisionResult::Intersect;
        }
        if ( Outside == 8 ) // if all corners of the bounding box are outside this plane, then it's guaranteed the bounding box is outside the frustum
            return CollisionResult::Outside;
    }
    return CollisionResult::Inside;
}

float GetDistanceFromPlaneToPoint ( const Plane &OtherPlane, const glm::vec3 &OtherPoint )
{
    return glm::dot ( OtherPlane.GetNormal (), OtherPoint - OtherPlane.GetPoint () );
}

I know it can be REALLY optimized, but for now I want it to simply work. optimizations will come later on. I know that the Intersect variable is never increased ( never hits that line ). It returns intersection as a result because it determines some points in the bounding box are inside and others are outside the frustum.

Here's the frustum setup function:

void Frustum::Calculate ( void )
{
    const glm::vec3 XVector = glm::normalize ( Transform.Orientation * glm::vec3 ( 1.0f, 0.0f, 0.0f ) );
    const glm::vec3 YVector = glm::normalize ( Transform.Orientation * glm::vec3 ( 0.0f, 1.0f, 0.0f ) );
    const glm::vec3 ZVector = glm::normalize ( Transform.Orientation * glm::vec3 ( 0.0f, 0.0f, 1.0f ) );

    const float Tangent = (float) tan ( 0.5f * Perspective.FOV );
    const float HalfNearHeight = Perspective.Near * Tangent;
    const float HalfFarHeight = Perspective.Far * Tangent;
    const float HalfNearWidth = HalfNearHeight * Perspective.AspectRatio;
    const float HalfFarWidth = HalfFarHeight * Perspective.AspectRatio;

    glm::vec3 NearClip = -ZVector * Perspective.Near;
    glm::vec3 FarClip = -ZVector * Perspective.Far;

    /*
    .     6---7
    .    /.  /|
    .   2---3 |
    .   | 4.|.5
    .   |.  |/
    .   0---1
    */
    Corners[0] = Transform.Position + NearClip - YVector * HalfNearHeight - XVector * HalfNearWidth;//NearBottomLeft
    Corners[1] = Transform.Position + NearClip - YVector * HalfNearHeight + XVector * HalfNearWidth;//NearBottomRight
    Corners[2] = Transform.Position + NearClip + YVector * HalfNearHeight - XVector * HalfNearWidth;//NearTopLeft
    Corners[3] = Transform.Position + NearClip + YVector * HalfNearHeight + XVector * HalfNearWidth;//NearTopRight

    Corners[4] = Transform.Position + FarClip - YVector * HalfFarHeight - XVector * HalfFarWidth;//FarBottomLeft 
    Corners[5] = Transform.Position + FarClip - YVector * HalfFarHeight + XVector * HalfFarWidth;//FarBottomRight 
    Corners[6] = Transform.Position + FarClip + YVector * HalfFarHeight - XVector * HalfFarWidth;//FarTopLeft 
    Corners[7] = Transform.Position + FarClip + YVector * HalfFarHeight + XVector * HalfFarWidth;//FarTopRight 

    // Doing all these extra calculations just for debug purposes. This way the point is exactly at the center of the frustum plane
#if 1
    glm::vec3 MidPoint[6];
    glm::vec3 Normal[6];
    MidPoint[0] = ( ( ( Corners[2] + Corners[3] ) / 2 ) + ( ( Corners[6] + Corners[7] ) / 2 ) ) / 2;
    Normal[0] = glm::normalize ( glm::cross ( Corners[2] - Corners[3], Corners[6] - Corners[3] ) );
    MidPoint[1] = ( ( ( Corners[0] + Corners[1] ) / 2 ) + ( ( Corners[4] + Corners[5] ) / 2 ) ) / 2;
    Normal[1] = glm::normalize ( glm::cross ( Corners[1] - Corners[0], Corners[5] - Corners[0] ) );
    MidPoint[2] = ( ( ( Corners[0] + Corners[2] ) / 2 ) + ( ( Corners[4] + Corners[6] ) / 2 ) ) / 2;
    Normal[2] = glm::normalize ( glm::cross ( Corners[4] - Corners[0], Corners[6] - Corners[0] ) );
    MidPoint[3] = ( ( ( Corners[1] + Corners[3] ) / 2 ) + ( ( Corners[5] + Corners[7] ) / 2 ) ) / 2;
    Normal[3] = glm::normalize ( glm::cross ( Corners[1] - Corners[5], Corners[3] - Corners[5] ) );
    MidPoint[4] = ( ( ( Corners[0] + Corners[1] ) / 2 ) + ( ( Corners[2] + Corners[3] ) / 2 ) ) / 2;
    Normal[4] = glm::normalize ( glm::cross ( Corners[2] - Corners[0], Corners[3] - Corners[0] ) );
    MidPoint[5] = ( ( ( Corners[4] + Corners[5] ) / 2 ) + ( ( Corners[6] + Corners[7] ) / 2 ) ) / 2;
    Normal[5] = glm::normalize ( glm::cross ( Corners[6] - Corners[7], Corners[4] - Corners[7] ) );

    Planes[0].SetFromNormalAndPoint ( Normal[0], MidPoint[0]);// Top
    Planes[1].SetFromNormalAndPoint ( Normal[1], MidPoint[1] );// Bottom
    Planes[2].SetFromNormalAndPoint ( Normal[2], MidPoint[2] );// Left
    Planes[3].SetFromNormalAndPoint ( Normal[3], MidPoint[3] );// Right
    Planes[4].SetFromNormalAndPoint ( Normal[4], MidPoint[4] );// Near
    Planes[5].SetFromNormalAndPoint ( Normal[5], MidPoint[5] );// Far
#else
    Planes[0].SetFrom3Points (Corners[3], Corners[2], Corners[6]);// Top
    Planes[1].SetFrom3Points ( Corners[0], Corners[1], Corners[5] );// Bottom
    Planes[2].SetFrom3Points ( Corners[0], Corners[4], Corners[6] );// Left
    Planes[3].SetFrom3Points ( Corners[5], Corners[1], Corners[3] );// Right
    Planes[4].SetFrom3Points ( Corners[0], Corners[2], Corners[3] );// Near
    Planes[5].SetFrom3Points ( Corners[7], Corners[6], Corners[4] );// Far
#endif
}

I've checked this function so many times, I think I may be blind to any errors already.

This whole thing results in the following data for defining the frustum, in case someone is crazy enough to do the math or spots some error I'm missing :D

The first sphere that is said to be intersecting is the tenth sphere down, counting from the top. its bounding box has the following values: Corners 0 and 1 are determined to be outside, but corner 2 returns inside ( which is wrong ), so the whole sphere is said to be intersecting the frustum.

EDIT: Solved!

Answer 1

Ok, found the issue. The problem was a matter of logic in CheckAABBFrustumCollision I was returning intersect as soon as I checked that a BBox intersected a plane, and not checking the other planes, which would have shown that it was completely outside.

CollisionResult CheckAABBFrustumCollision ( const BoundingBox &Box, const Frustum &ViewFrustum )
    {
    glm::vec3 Corners[8];
    unsigned Inside = 0, Outside = 0, Intersect = 0;
    CalculateBoundingBoxCorners ( Box, Corners );
    const Geometry::Plane *Planes = ViewFrustum.GetPlanesReference ();
    for ( unsigned PlaneIndex = 0; PlaneIndex < 6; ++PlaneIndex )
        {
        unsigned PlaneOutside = 0;
        for ( unsigned CornerIndex = 0; CornerIndex < 8; ++CornerIndex )
            {
            float Distance = GetDistanceFromPlaneToPoint ( Planes[PlaneIndex], Corners[CornerIndex] );
            if ( Distance < 0.0f )
                ++PlaneOutside;
            else if ( Distance > 0.0f )
                ++Inside;
            else
                ++Intersect;
            }
        if ( PlaneOutside == 8 ) // if all corners of the bounding box are outside this plane, then it's guaranteed the bounding box is outside the frustum
            return CollisionResult::Outside;
        Outside += PlaneOutside;
        }
    assert ( ( Outside + Inside + Intersect ) == 6*8 );
    if ( Outside != 0 )// If there are points outside and inside, then it's intersecting...
        return CollisionResult::Intersect;
    return CollisionResult::Inside;
    }

It now works beautifully :)