1
\$\begingroup\$

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

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

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] );
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – mklingen Apr 15 '15 at 14:56
  • \$\begingroup\$ 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... \$\endgroup\$ – Joao Pincho Apr 15 '15 at 15:13
  • \$\begingroup\$ 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. \$\endgroup\$ – mklingen Apr 15 '15 at 17:05
  • \$\begingroup\$ 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. \$\endgroup\$ – Jibb Smart Apr 16 '15 at 2:50
  • \$\begingroup\$ @jibb. That was just so i could put a watch on D, while debugging. \$\endgroup\$ – Joao Pincho Apr 16 '15 at 9:35
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Hmm. You may be onto something here. I did the math on pen and paper, and you're right. That bounding box SHOULD indeed be intersecting. That means my frustum drawing is wrong, for some reason. Still, the frustum culling is still not working. Objects disappear while in plain view.. \$\endgroup\$ – Joao Pincho Apr 16 '15 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.