   Problem with Frustum Culling Class!
  Hi AllI'm having some problems with my frustum culling class.  The function for testing a bounding sphere works fine, but the function for testing a bounding box doesn't seem to work at all as it doesn't cull anything.  Could someone take a look and point out the (probably obvious) mistake I've made?// Include the Maths Header#include <math.h>// Include some GL Stuff#include "GLee.h"// Include the Class Header#include "cFrustum.h"// Set the Singleton to ZerocFrustum *cFrustum::c_Frustum = 0;// Instance Return FunctioncFrustum *cFrustum::Instance(){if (c_Frustum == 0)c_Frustum = new cFrustum();return c_Frustum;}// Extract a Plane from a given Matrix and Row IDinline void ExtractPlane(Plane &plane, float *mat, int row){int scale = (row < 0) ? -1 : 1;row = abs(row) - 1;// Calculate the Plane Coefficients from the Matrixplane.A = mat[3] + scale * mat[row];plane.B = mat[7] + scale * mat[row + 4];plane.C = mat[11] + scale * mat[row + 8];plane.D = mat[15] + scale * mat[row + 12];// Normalise the Plane// Improved from original version by dividing length by one// and multiplying A, B, C & D by the new length value.float length = 1.0f / sqrtf(plane.A * plane.A + plane.B * plane.B + plane.C * plane.C);plane.A *= length;plane.B *= length;plane.C *= length;plane.D *= length;}// Calculate the Current View Frustum (do only ONCE per frame)void cFrustum::CalculateFrustum(){// Get the Projection and Modelview Matricesfloat mProjection[16];float mModelView[16];glGetFloatv(GL_PROJECTION_MATRIX, mProjection);glGetFloatv(GL_MODELVIEW_MATRIX, mModelView);// Do some Matrix Multiplication (with OpenGL)glPushMatrix();glLoadMatrixf(mProjection);glMultMatrixf(mModelView);glGetFloatv(GL_MODELVIEW_MATRIX, mModelView);glPopMatrix();// Extract the PlanesExtractPlane(s_Frustum.l, mModelView, 1);ExtractPlane(s_Frustum.r, mModelView, -1);ExtractPlane(s_Frustum.b, mModelView, 2);ExtractPlane(s_Frustum.t, mModelView, -2);ExtractPlane(s_Frustum.n, mModelView, 3);ExtractPlane(s_Frustum.f, mModelView, -3);}// Calculate the Bounding Spherevoid cFrustum::CalculateBoundingSphere(Sphere &sphere, float MinY, float MaxY){sphere.Centre.x = 0;sphere.Centre.y = (MinY + MaxY) * 0.5f;sphere.Centre.z = 0;sphere.Radius = MaxY - sphere.Centre.y;}// Determine whether a Point lies within a Planeinline bool PointInPlane(Plane plane, Vertex vertex){if ((plane.A * vertex.x + plane.B * vertex.y + plane.C * vertex.z + plane.D) <= 0)return false;else return true;}// Determine whether a Point lies within the View Frustumbool cFrustum::PointInFrustum(Vertex vertex){if (!PointInPlane(s_Frustum.b, vertex))return false;if (!PointInPlane(s_Frustum.f, vertex))return false;if (!PointInPlane(s_Frustum.l, vertex))return false;if (!PointInPlane(s_Frustum.n, vertex))return false;if (!PointInPlane(s_Frustum.r, vertex))return false;if (!PointInPlane(s_Frustum.t, vertex))return false;else return true;}// Determine whether a Sphere lies within the View Frustumbool cFrustum::SphereInFrustum(Sphere sphere){// Distance Variablefloat dist;// Check each Planedist =s_Frustum.b.A * sphere.Centre.x +s_Frustum.b.B * sphere.Centre.y +s_Frustum.b.C * sphere.Centre.z +s_Frustum.b.D;if (dist <= -sphere.Radius)return false;dist =s_Frustum.f.A * sphere.Centre.x +s_Frustum.f.B * sphere.Centre.y +s_Frustum.f.C * sphere.Centre.z +s_Frustum.f.D;if (dist <= -sphere.Radius)return false;dist =s_Frustum.l.A * sphere.Centre.x +s_Frustum.l.B * sphere.Centre.y +s_Frustum.l.C * sphere.Centre.z +s_Frustum.l.D;if (dist <= -sphere.Radius)return false;dist =s_Frustum.n.A * sphere.Centre.x +s_Frustum.n.B * sphere.Centre.y +s_Frustum.n.C * sphere.Centre.z +s_Frustum.n.D;if (dist <= -sphere.Radius)return false;dist =s_Frustum.r.A * sphere.Centre.x +s_Frustum.r.B * sphere.Centre.y +s_Frustum.r.C * sphere.Centre.z +s_Frustum.r.D;if (dist <= -sphere.Radius)return false;dist =s_Frustum.t.A * sphere.Centre.x +s_Frustum.t.B * sphere.Centre.y +s_Frustum.t.C * sphere.Centre.z +s_Frustum.t.D;if (dist <= -sphere.Radius)return false;return true;}bool cFrustum::BoxInFrustum(Box boundingBox){// Variablesint k, i, count = 0;// Add the Planes and Vertices into an Array for Easier CodingVertex vertices[] = {boundingBox.bA, boundingBox.bB,boundingBox.bC, boundingBox.bD,boundingBox.tA, boundingBox.tB,boundingBox.tC, boundingBox.tD };Plane planes[] = {s_Frustum.b, s_Frustum.f, s_Frustum.l,s_Frustum.n, s_Frustum.r, s_Frustum.t };// Loop Through and Check each Vertex against Each Planefor (k = 0; k < 8; k++){for (i = 0; i < 6; i++){if (PointInPlane(planes, vertices[k]))return true;}}return false;}and just for reference, the header is:#ifndef _CFRUSTUM_H_#define _CFRUSTUM_H_// Plane Structurestruct Plane{float A, B, C, D;};// Frustum Structurestruct Frustum{Plane t, b, l, r, n, f;};// Vertex Structurestruct Vertex{float x, y, z;};// Box Structurestruct Box{Vertex bA, bB, bC, bD;Vertex tA, tB, tC, tD;};// Sphere Structurestruct Sphere{Vertex Centre;float Radius;};class cFrustum{public:static cFrustum *Instance();void CalculateFrustum();void CalculateBoundingSphere(Sphere &sphere, float MinY, float MaxY);bool PointInFrustum(Vertex vertex);bool SphereInFrustum(Sphere sphere);bool BoxInFrustum(Box boundingBox);private:cFrustum() {}static cFrustum *c_Frustum;Frustum s_Frustum;};#endifThanks in advance!   
  Your logic is that if a single corner of the box is on the positive side of some plane, then the box is inside the frustum. If you think about it a bit, you'll realize that this will return true for any kind of box.The correct way is to check if all corners of the box are on the negative side of at least one plane. There's an implementation here.   ;  Excellent!  Thank you for clearing that up.  Got it working now.bool cFrustum::BoxInFrustum(Box boundingBox){// Variablesint k, i;// Add the Planes and Vertices into an Array for Easier CodingVertex vertices[] = {boundingBox.bA, boundingBox.bB,boundingBox.bC, boundingBox.bD,boundingBox.tA, boundingBox.tB,boundingBox.tC, boundingBox.tD };Plane planes[] = {s_Frustum.b, s_Frustum.f, s_Frustum.l,s_Frustum.n, s_Frustum.r, s_Frustum.t };// Loop Through and Check each Vertex against Each Planefor (i = 0; i < 6; i++){int InCount = 8;for (k = 0; k < 8; k++){if (!PointInPlane(planes, vertices[k]))--InCount;if (InCount == 0)return false;}}return true;}Thanks again sire!   ;Quote:Original post by AndyMillsExcellent!  Thank you for clearing that up.  Got it working now.bool cFrustum::BoxInFrustum(Box boundingBox){// Variablesint k, i;// Add the Planes and Vertices into an Array for Easier CodingVertex vertices[] = {boundingBox.bA, boundingBox.bB,boundingBox.bC, boundingBox.bD,boundingBox.tA, boundingBox.tB,boundingBox.tC, boundingBox.tD };Plane planes[] = {s_Frustum.b, s_Frustum.f, s_Frustum.l,s_Frustum.n, s_Frustum.r, s_Frustum.t };// Loop Through and Check each Vertex against Each Planefor (i = 0; i < 6; i++){int InCount = 8;for (k = 0; k < 8; k++){if (!PointInPlane(planes, vertices[k]))--InCount;if (InCount == 0)return false;}}return true;}Thanks again sire!It's worth noting that this test can be performed in a much more efficient manner than what's shown above. There's no need to test each corner individually; in fact, the test can be reduced to just a couple of dot products and a little arithmetic. (If you search the forum archives for 'aabb frustum', you should be able to find some discussion of the more efficient version of this algorithm.)If frustum culling isn't a bottleneck for you it probably won't matter, but if efficiency is a concern, it might be worth using the more efficient version of the test rather than the above.   