Hibbs 126 Report post Posted June 21, 2005 Can anyone help me with calculating a Frustrum Bounding Volume, or obtaining the four corner vertex's. Im using directx. Thanks 0 Share this post Link to post Share on other sites
ZQJ 496 Report post Posted June 21, 2005 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. 0 Share this post Link to post Share on other sites
Opwiz 348 Report post Posted June 21, 2005 You usually describe the frustum volume with six clipping planes. Here is details about extracting the planes in opengl and directx:Fast Extraction of Viewing Frustum Planes from the World-View-Projection Matrix 0 Share this post Link to post Share on other sites
Hibbs 126 Report post Posted June 23, 2005 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 0 Share this post Link to post Share on other sites
Opwiz 348 Report post Posted June 23, 2005 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. 0 Share this post Link to post Share on other sites
bit64 218 Report post Posted June 23, 2005 Quote:Original post by OpwizHm.. 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? 0 Share this post Link to post Share on other sites
Opwiz 348 Report post Posted June 23, 2005 Hm, there is a difference between checking if frustum is inside a quad versus checking if quad is inside (or intersecting) the frustum. 0 Share this post Link to post Share on other sites
bit64 218 Report post Posted June 23, 2005 Quote:Original post by OpwizHm, 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 frustumI dont see the difference. 0 Share this post Link to post Share on other sites
Opwiz 348 Report post Posted June 23, 2005 Hm, frustum inside quad means quad intersect frustum. 0 Share this post Link to post Share on other sites
Mr Grinch 318 Report post Posted June 24, 2005 Check out Mark Morley's frustum culling tutorial. I found it to be very clear and extremely helpful, but then his site just went down. I managed to save a copy from the google cache. Does anyone know what happened to him? 0 Share this post Link to post Share on other sites
leoptimus 106 Report post Posted June 24, 2005 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? 0 Share this post Link to post Share on other sites
bit64 218 Report post Posted June 25, 2005 Quote:Original post by OpwizHm, 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". 0 Share this post Link to post Share on other sites
Hibbs 126 Report post Posted June 25, 2005 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? 0 Share this post Link to post Share on other sites
Opwiz 348 Report post Posted June 25, 2005 Quote:Original post by bit64Quote:Original post by OpwizHm, 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] 0 Share this post Link to post Share on other sites
Opwiz 348 Report post Posted June 25, 2005 Quote:Original post by Hibbsthis 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. 0 Share this post Link to post Share on other sites
Hibbs 126 Report post Posted June 25, 2005 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. 0 Share this post Link to post Share on other sites