# Cannot find bug in frustum culling code

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] );

• for some debugging help, try drawing the normals of all the planes, and determine which planes each object is inside. Usually this kind of bug comes from having your plane normals pointed the wrong way. – mklingen Apr 15 '15 at 14:56
• I already did. The normals seem ok. As I mentioned in the post, the normals for the top plane seem to point mainly downwards, and slightly to the negative Z ( which is correct, in OpenGL ). Unfortunately, that whole GetDistance call is the part where it says the point is outside, so something is wrong... – Joao Pincho Apr 15 '15 at 15:13
• GetDistance will be positive whenever the point is in the same direction as the plane's normal, negative when it is in the other direction. Your check seems to be reversed. If the normal of the top plane is pointing down, then points inside will have positive dot product, not negative. – mklingen Apr 15 '15 at 17:05
• Just a minor note: float D ... the result isn't getting used, but instead being immediately recalculated afterwards. Not that it affects the logic. Still thinking on your actual question. – Jibb Smart Apr 16 '15 at 2:50
• @jibb. That was just so i could put a watch on D, while debugging. – Joao Pincho Apr 16 '15 at 9:35