Sign in to follow this  
Hibbs

Frustrum Bounding Volume

Recommended Posts

Can anyone help me with calculating a Frustrum Bounding Volume, or obtaining the four corner vertex's. Im using directx. Thanks

Share this post


Link to post
Share on other sites
Aren't there 8 corner vertices?

But anyway assuming you do mean 8 and not 4 it's done as follows (well, I'm an OpenGL man but here's how I think it works in D3D): take your 3 matrices (world, view and projection), multiply them together in order (i.e. work out the overall transformation matrix), and then invert it. Then transform 8 vertices through that which are all the combinations of (-1/+1,-1/+1,-1/+1). This will give you the 8 points in world space. Which is which depends on whether you're using a left- or right-handed coordinate system (I seem to remember most D3D apps use left-handed in defiance of hundreds of years of science and maths, but I could well be wrong), and the matrix inversion will be different to OpenGL because the matrices are stored differently. If you want the viewer position, transform the vector (-1, 0, 0, 0) through that matrix.

Share this post


Link to post
Share on other sites
Finding the clipping planes didnt help me much becuase i want to check the frustrum volume against my octree & the clipping planes tell me if a point isnt in the frustrum where-as I want to check to see if the frustrum is inside a quad.

I coded up to find the eight points of the frustrum and created a virtual camera(world view projection) so that I could render it all on the screen. It draws a frustrum shaped pyramid on the screen :) - but changing the world matrix moves it in the opposite direction - obviously becuase of the invert - removing the invert and i dont get a pyramid frustrum. Inverting the world matrix before the multiplication works. Is this a correct behaviour?

Added: Somthing is deffinatley wrong, changing the farPlane increases the size of the frustrum but also moves its posiition. Am I multiplying the matrix's in the correct order?

Heres my code:

Matrix p = Matrix.PerspectiveFovLH((float)Math.PI / 4, 1, 1.0f, 2.0f);
Matrix v = Matrix.LookAtLH(new Vector3(0, 0, 0), new Vector3(0, 0, 2), new Vector3(0, 1, 0));
Matrix m = Matrix.Translation(-3, -1, -3);
Matrix M = m * v * p;
M.Invert();

fv[0] = new Vector3(-1, -1, -1);
fv[1] = new Vector3(1, -1, -1);
fv[2] = new Vector3(1, 1, -1);
fv[3] = new Vector3(-1, 1, -1);
fv[4] = new Vector3(-1, -1, 1);
fv[5] = new Vector3(1, -1, 1);
fv[6] = new Vector3(1, 1, 1);
fv[7] = new Vector3(-1, 1, 1);

for (int i = 0; i < 8; i++)
{
fv[i].TransformCoordinate(M);
}

Thanks

Share this post


Link to post
Share on other sites
Hm.. I'm not sure exactly why you would want to check if a frustum is in a quad or not. Normally if you want to perform frustum culling with an octree you check if the quad is inside, intersect or outside the frustum. If the quad is outside you can assume that all sub-quads are too, if inside you could assume that all sub-quads are inside, if intersecting you should perform intersection tests on the sub-quads.

Share this post


Link to post
Share on other sites
Quote:
Original post by Opwiz
Hm.. I'm not sure exactly why you would want to check if a frustum is in a quad or not. Normally if you want to perform frustum culling with an octree you check if the quad is inside, intersect or outside the frustum. If the quad is outside you can assume that all sub-quads are too, if inside you could assume that all sub-quads are inside, if intersecting you should perform intersection tests on the sub-quads.


Why do you see a distinction between the two checks?

Share this post


Link to post
Share on other sites
Hm, there is a difference between checking if frustum is inside a quad versus checking if quad is inside (or intersecting) the frustum.

Share this post


Link to post
Share on other sites
Quote:
Original post by Opwiz
Hm, there is a difference between checking if frustum is inside a quad versus checking if quad is inside (or intersecting) the frustum.


frustum inside quad == quad outside frustum

I dont see the difference.

Share this post


Link to post
Share on other sites
A traditional method for culling objects that are not visible to the camera is building the planes of the frustum volume, and test every bounding box to determine which are inside the volume.

In portal rendering method, this process is the main backbone, and when the view frustum hit a portal, it must be clipped by adding more planes builded from the portal polygon edges. But think about if there will be many successive portals, and the view frustum volume has gained a lot of planes, the frustum culling becomes expensive.

But if we transform the 3d axis aligned boxes to viewport coordinates, we only have to test if the projected box intersects the viewport box. This test is very cheap.

What do you think?

Share this post


Link to post
Share on other sites
Quote:
Original post by Opwiz
Hm, frustum inside quad means quad intersect frustum.


encapsulation does not equal intersection. I'm starting to think you are arguing for the sake of argument.

and stop saying "hm".


Share this post


Link to post
Share on other sites
Thanks for the replies,

The problem with the code i pasted earlier was that only the view * projection matrix's needed inverting - multiplying them and inverting then multiplying the world matrix worked.

Anyway indeed i was looking at it the wrong way.

Ive tried converting the code for the "cube in frustrum" test from mark's tutorial (which was just the sort of test i was after thanks) into directx but it dosnt seem to be working, heres my code:

This get the frustrum planes:

Matrix M = w * v * p;

//Left Clip Plane
cp[0] = new Plane(M.M14 + M.M11, M.M24 + M.M21, M.M34 + M.M31, M.M44 + M.M41);
//Right Clip Plane
cp[1] = new Plane(M.M14 - M.M11, M.M24 - M.M21, M.M34 - M.M31, M.M44 - M.M41);
//Top Clip Plane
cp[2] = new Plane(M.M14 - M.M12, M.M24 - M.M22, M.M34 - M.M32, M.M44 - M.M42);
//Bottom Clip Plane
cp[3] = new Plane(M.M14 + M.M12, M.M24 + M.M22, M.M34 + M.M32, M.M44 + M.M42);
//Near Clip Plane
cp[4] = new Plane(M.M13, M.M23, M.M33, M.M43);
//Far Clip Plane
cp[5] = new Plane(M.M14 - M.M13, M.M24 - M.M23, M.M34 - M.M33, M.M44 - M.M43);

for (int i = 0; i < 6; i++)
{
cp[i].Normalize();
}

this is the cube test function:

private static int cubeInFrustum(float x, float y, float z, float size)
{
int c;
int c2 = 0;

for (short p = 0; p < 6; p++)
{
c = 0;
if (cp[p].A * (x - size) + cp[p].B * (y - size) + cp[p].C * (z - size) + cp[p].D > 0)
c++;
if (cp[p].A * (x + size) + cp[p].B * (y - size) + cp[p].C * (z - size) + cp[p].D > 0)
c++;
if (cp[p].A * (x - size) + cp[p].B * (y + size) + cp[p].C * (z - size) + cp[p].D > 0)
c++;
if (cp[p].A * (x + size) + cp[p].B * (y + size) + cp[p].C * (z - size) + cp[p].D > 0)
c++;
if (cp[p].A * (x - size) + cp[p].B * (y - size) + cp[p].C * (z + size) + cp[p].D > 0)
c++;
if (cp[p].A * (x + size) + cp[p].B * (y - size) + cp[p].C * (z + size) + cp[p].D > 0)
c++;
if (cp[p].A * (x - size) + cp[p].B * (y + size) + cp[p].C * (z + size) + cp[p].D > 0)
c++;
if (cp[p].A * (x + size) + cp[p].B * (y + size) + cp[p].C * (z + size) + cp[p].D > 0)
c++;
if (c == 0)
return 0;
if (c == 8)
c2++;
}
return (c2 == 6) ? 2 : 1;
}


Any ideas what im doing wrong?

Share this post


Link to post
Share on other sites
Quote:
Original post by bit64
Quote:
Original post by Opwiz
Hm, frustum inside quad means quad intersect frustum.


encapsulation does not equal intersection. I'm starting to think you are arguing for the sake of argument.

and stop saying "hm".

First of all, there is a difference between intersection and containment testing. I'm not sure which one you assume I'm talking about. If you do a intersection test it does not matter if the quad encapsulate the frustum they still intersect. If you do a containment test you check if the quad encapsulate the frustum or vice versa. However, testing if frustum contains quad and testing if quad contains frustum is _not_ the same. E.g. you can't assume the frustum contains the quad if the quad does not contain the frustum.

The original poster talked about doing frustum culling with octree so assume he would like to do both containment and intersection test. Testing if frustum intersect or is encapsulated by the quad is different from checking if quad intersect or is encapsulated by the frustum. You can't assume with the former that if the test returns INTERSECT that the quad is'nt encapsulated by the frustum.

[Edited by - Opwiz on June 25, 2005 9:58:10 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Hibbs
this is the cube test function:
...
Any ideas what im doing wrong?

Ok. You loop through each plane and check if the distance to each corner of the box is greater than zero (is inside the plane so to speak). If all corners are beind the plane you return zero (we know for sure that the cube is outside the frustum). If all the corners are inside all of the planes we return two (cube inside frustum), otherwize you return one (cube intersect frustum). Looks fine to me. Depending on how you represent the plane (Ax + By + Cz + D = 0 or Ax + By + Cz = D) you might want to change cp[p].D to -cp[p].D in the algorithm. Otherwize I'm not sure what is wrong..

I suggest you draw the box, draw the result of the cubeInFrustum() test on the screen and implement simple camera movements and see what happens.. I've spend lot of time my self trying to get my intersection code to work and it helps alot.

Share this post


Link to post
Share on other sites
I think its to do with the perspective - does opengl use Right Hand coords and in directx im using left hand, becuase the test returns the opposite box as the intersecting box, and if I reverse the frustrum xyz it returns the correct box.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this