I have question about AABB of view frustum calculation, I tried a way that transform 8 vertices with view projection matrix(actually, tansform a unit cube with view projection matrix), then uses 8 loops to find out AABB from these transformed vertices. I think this way is very costly , 8 vertices transformations and 8 loops just for find out AABB, does here has a way that more fast and more simple? please help me ! thanks I am sorry for my poor english.

You shouldn't need 8 loops. Once you have the 8 vertices of the frustum, you just need one loop (across each of the 8 vertices) to store the min and max values for x, y, z. Then you can easily assemble the AABB from those values.

Quote:Original post by strtok
You shouldn't need 8 loops. Once you have the 8 vertices of the frustum, you just need one loop (across each of the 8 vertices) to store the min and max values for x, y, z. Then you can easily assemble the AABB from those values.

thanks for your reply.

First, I simply descript my way for AABB calculation:

Vector3  unit_cube[8], view_frustum[8], min, max;// create an unit cubecreate_unit_cube( unit_cube );min.x = 9999.0f;min.y = 9999.0f;min.z = 9999.0f;max.x = -9999.0f;max.y = -9999.0f;max.z = -9999.0f;for( int i = 0; i < 8; ++ i ){   transform( unit_cube, view_frustum, ViewProj );  }for( int i = 0; i < 8; ++ i ){  if( min.x > view_frustum.x )  {    min.x = view_frustum.x;  }     if( min.y > view_frustum.y)  {    min.y = view_frustum.y;  }  if( min.z > view_frustum.z )  {    min.z = view_frustum.z;  }  if( max.x < view_frustum.x )  {    max.x = view_frustum.x;  }     if( max.y < view_frustum.y)  {    max.y = view_frustum.y;  }  if( max.z < view_frustum.z )  {    max.z = view_frustum.z;  }}

Your meaning is combine two loops in one loops? the code I thinked:

for( int i = 0; i < 8; ++ i ){   transform( unit_cube, view_frustum, ViewProj );    if( min.x > view_frustum.x )  {    min.x = view_frustum.x;  }     if( min.y > view_frustum.y)  {    min.y = view_frustum.y;  }  if( min.z > view_frustum.z )  {    min.z = view_frustum.z;  }  if( max.x < view_frustum.x )  {    max.x = view_frustum.x;  }     if( max.y < view_frustum.y)  {    max.y = view_frustum.y;  }  if( max.z < view_frustum.z )  {    max.z = view_frustum.z;  }}

is that your meaning? if I am wrong , please correct me, thanks.

Either of those should work just fine. Mine looks like your first example. That's a total of 2 loops (and I don't see why your second example, with only 1 loop, would work as well). So, maybe I was confused when you said 8 loops. Did you really start with 8 loops, or just 1-2 loops over the 8 vertices?

Quote:Original post by alpha_blending
I think this way is very costly , 8 vertices transformations and 8 loops just for find out AABB, does here has a way that more fast and more simple?

Regarding the cost of the transforms, since you have a unit cube, it is pretty easy to work out what the result of one of the points times the matrix will be.

Are you sure the calculation of the view frustum points works though? Perhaps I am confused what you are doing, but I would think you'd want to multiply points on the NDC cube by the inverse projection matrix (instead of the view-proj matrix). And then you'd have the points in view space. And you could do lots of simplifications (as mentioned above) if you wanted it to be faster.

EDIT:
I am not completely sure what space you want this AABB in. If its view space, you could just compute the points on the far plane for 4 of the AABB points (by the method above). Then for the other 4 points, I would just take the points on the far plane and set their z-components to the "near" value (whatever that may be).

Also, if you knew you didn't have an off-center projection, you could make some further optimizations (only back-project 2 points perhaps), but this sounds like a little too much premature optimization (at least to me).

Quote:Original post by strtok
Either of those should work just fine. Mine looks like your first example. That's a total of 2 loops (and I don't see why your second example, with only 1 loop, would work as well). So, maybe I was confused when you said 8 loops. Did you really start with 8 loops, or just 1-2 loops over the 8 vertices?

My english is not good, perhaps I am wrong on concept of 'loop'. :)

thank you!

Quote:
Are you sure the calculation of the view frustum points works though? Perhaps I am confused what you are doing, but

I would think you'd want to multiply points on the NDC cube by the inverse projection matrix ....

My purpose of AABB of view frustum is to speed up Entity Culling before Entity Rendering.

my thinking:

// First, use AABB intersection to quickly culls unvisible entity for( int i = 0; i < entity_count; ++ i ){  if( AABB_Intersect( entity_list.AABB,  AABB_of_VF )  {    visible_set.push_back( entity_list );  }  }// Second, do exact culling for( size_t i = 0; i < visible_set.size(); ++ i ){  if( !AABB_Frustum_intersect( visible_set.size.AABB,  ViewFrustum )  {    visible_set.erase( visible_set.begin() + i );  }  }

Quote:
EDIT:
I am not completely sure what space you want this AABB in.

I want to retrieve AABB of view frustum in world space, my thinking of AABB calculation come from MS SDK 8.1b sample( its name is 'Cull' )


thanks for your reply!

[Edited by - alpha_blending on October 29, 2007 1:12:30 AM]

Quote:Original post by alpha_blending
I want to retrieve AABB of view frustum in world space, my thinking of AABB calculation come from MS SDK 8.1b sample( its name is 'Cull' )

I don't have the 8.1 SDK installed, but if you want the view frustum in world space I think the easiest way to do that would be to take the points on the unit cube in NDC space and multiply them by the inverse view-proj matrix (ie, ViewMat^(-1) * ProjMat^(-1), assuming multiply on the right). Then you could build the AABB using the 8 pts in world space.

In your pseudo-code it looked like you were multiplying by the view-proj matrix. I think that would transform the points on a unit cube in world space to projective space, which doesn't seem to be what you want.

Quote:Original post by wyrzy

Quote:Original post by alpha_blending
I want to retrieve AABB of view frustum in world space, my thinking of AABB calculation come from MS SDK 8.1b sample( its name is 'Cull' )

I don't have the 8.1 SDK installed, but if you want the view frustum in world space I think the easiest way to do that would be to take the points on the unit cube in NDC space and multiply them by the inverse view-proj matrix (ie, ViewMat^(-1) * ProjMat^(-1), assuming multiply on the right). Then you could build the AABB using the 8 pts in world space.

In your pseudo-code it looked like you were multiplying by the view-proj matrix. I think that would transform the points on a unit cube in world space to projective space, which doesn't seem to be what you want.

yes, I made a mistake on transformation!
thank you very much!