# frustum culling with octrees

This topic is 3451 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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[j] = pi[k];
mv[j] = mvi[k];
res[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[j]+= mv[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[0]*v[j].x+planes[1]*v[j].y+planes[2]*v[j].z+planes[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.)

1. 1
Rutin
32
2. 2
3. 3
4. 4
5. 5

• 13
• 9
• 9
• 9
• 14
• ### Forum Statistics

• Total Topics
633318
• Total Posts
3011339
• ### Who's Online (See full list)

There are no registered users currently online

×