# frustum culling with octrees

## Recommended Posts

Hello! I'm trying to use octrees to implement frustum culling for my c++/opengl game. First of all, I divide the space and I get the correct cubes of the octree. Then I need to determine which cubes are inside the view. To do that, I extract the planes of the frustum:
void extractPlanes()
{
float mv[4][4];
float p[4][4];
float pi[16], mvi[16], res[4][4];
int i, j;

glGetFloatv(GL_MODELVIEW_MATRIX, mvi);
glGetFloatv(GL_PROJECTION_MATRIX, pi);

//Transpose both matrices MODELVIEW & PROJECTION
int k = 0;
for(j=0;j&lt;4;j++)
{
for(i=0;i&lt;4;i++)
{
p[i][j] = pi[k];
mv[i][j] = mvi[k];
res[i][j] = 0;
k++;
}

}

//Multiply the 2 matrix MODELVIEW * PROJECTION
for(i=0;i&lt;4;i++)
{
for(j=0;j&lt;4;j++)
{
for(k=0;k&lt;4;k++)
res[i][j]+= mv[i][k]*p[k][j];
}
}

//Find the planes
//Left
planes[0][0] = res[3][0] + res[0][0];
planes[0][1] = res[3][1] + res[0][1];
planes[0][2] = res[3][2] + res[0][2];
planes[0][3] = res[3][3] + res[0][3];
normPlane(0);

//Right
planes[1][0] = res[3][0] - res[0][0];
planes[1][1] = res[3][1] - res[0][1];
planes[1][2] = res[3][2] - res[0][2];
planes[1][3] = res[3][3] - res[0][3];
normPlane(1);

//Bottom
planes[2][0] = res[3][0] + res[1][0];
planes[2][1] = res[3][1] + res[1][1];
planes[2][2] = res[3][2] + res[1][2];
planes[2][3] = res[3][3] + res[1][3];
normPlane(2);

//Top
planes[3][0] = res[3][0] - res[1][0];
planes[3][1] = res[3][1] - res[1][1];
planes[3][2] = res[3][2] - res[1][2];
planes[3][3] = res[3][3] - res[1][3];
normPlane(3);

//Near
planes[4][0] = res[3][0] + res[2][0];
planes[4][1] = res[3][1] + res[2][1];
planes[4][2] = res[3][2] + res[2][2];
planes[4][3] = res[3][3] + res[2][3];
normPlane(4);

//Far
planes[5][0] = res[3][0] - res[2][0];
planes[5][1] = res[3][1] - res[2][1];
planes[5][2] = res[3][2] - res[2][2];
planes[5][3] = res[3][3] - res[2][3];
normPlane(5);

}


Then for each cube of the octree, I try to determine if any of its vertices is inside the frustum view:
bool cubeInFrustum(V* v)
{
int i,j,count;

for(i=0;i&lt;6;i++)
{
count = 8;
for(j=0;j&lt;8;j++)
{
//If this point is outside this plane
if((planes[i][0]*v[j].x+planes[i][1]*v[j].y+planes[i][2]*v[j].z+planes[i][3]) &lt; 0)
count--;
}
//If the 8 points are outside the plane
if(count == 0)
return false;
}
return true;
}


Unfortunately, I don't get the expected results. Does anyone see something wrong? Thank you!

##### Share on other sites
What are the expected/unexpected results?

Also, your algorithm might not work quite as expected because it doesn't cater for the case where you can have all vertices of the cube outside the frustrum but still be able to see it because one of its faces intersects it.

##### Share on other sites
Quote:
 Also, your algorithm might not work quite as expected because it doesn't cater for the case where you can have all vertices of the cube outside the frustrum but still be able to see it because one of its faces intersects it.
I'm not sure that's the case. From looking at the code it looks like the box is culled if all eight vertices fall behind one of the frustum planes, in which case there shouldn't be any false negatives. (There are more direct ways to perform the AABB-plane test than checking all eight corners individually, but the 'eight corners' test should work.)

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628350
• Total Posts
2982211

• 10
• 9
• 24
• 11
• 9