求Frustrum六个面的方程http://www.game798.com/html/2007-05/3465.htm
首先计算6个裁减面的方程系数
// Name: calculateFrustumPlanes()
// Desc:
//-----------------------------------------------------------------------------
void calculateFrustumPlanes( void )
{
float p[16]; // projection matrix
float mv[16]; // model-view matrix
float mvp[16]; // model-view-projection matrix
float t;
glGetFloatv( GL_PROJECTION_MATRIX, p );
glGetFloatv( GL_MODELVIEW_MATRIX, mv );
//
// Concatenate the projection matrix and the model-view matrix to produce
// a combined model-view-projection matrix.
//
mvp[ 0] = mv[ 0] * p[ 0] + mv[ 1] * p[ 4] + mv[ 2] * p[ 8] + mv[ 3] * p[12];
mvp[ 1] = mv[ 0] * p[ 1] + mv[ 1] * p[ 5] + mv[ 2] * p[ 9] + mv[ 3] * p[13];
mvp[ 2] = mv[ 0] * p[ 2] + mv[ 1] * p[ 6] + mv[ 2] * p[10] + mv[ 3] * p[14];
mvp[ 3] = mv[ 0] * p[ 3] + mv[ 1] * p[ 7] + mv[ 2] * p[11] + mv[ 3] * p[15];
mvp[ 4] = mv[ 4] * p[ 0] + mv[ 5] * p[ 4] + mv[ 6] * p[ 8] + mv[ 7] * p[12];
mvp[ 5] = mv[ 4] * p[ 1] + mv[ 5] * p[ 5] + mv[ 6] * p[ 9] + mv[ 7] * p[13];
mvp[ 6] = mv[ 4] * p[ 2] + mv[ 5] * p[ 6] + mv[ 6] * p[10] + mv[ 7] * p[14];
mvp[ 7] = mv[ 4] * p[ 3] + mv[ 5] * p[ 7] + mv[ 6] * p[11] + mv[ 7] * p[15];
mvp[ 8] = mv[ 8] * p[ 0] + mv[ 9] * p[ 4] + mv[10] * p[ 8] + mv[11] * p[12];
mvp[ 9] = mv[ 8] * p[ 1] + mv[ 9] * p[ 5] + mv[10] * p[ 9] + mv[11] * p[13];
mvp[10] = mv[ 8] * p[ 2] + mv[ 9] * p[ 6] + mv[10] * p[10] + mv[11] * p[14];
mvp[11] = mv[ 8] * p[ 3] + mv[ 9] * p[ 7] + mv[10] * p[11] + mv[11] * p[15];
mvp[12] = mv[12] * p[ 0] + mv[13] * p[ 4] + mv[14] * p[ 8] + mv[15] * p[12];
mvp[13] = mv[12] * p[ 1] + mv[13] * p[ 5] + mv[14] * p[ 9] + mv[15] * p[13];
mvp[14] = mv[12] * p[ 2] + mv[13] * p[ 6] + mv[14] * p[10] + mv[15] * p[14];
mvp[15] = mv[12] * p[ 3] + mv[13] * p[ 7] + mv[14] * p[11] + mv[15] * p[15];
//
// Extract the frustum's right clipping plane and normalize it.
//
g_frustumPlanes[0][0] = mvp[ 3] - mvp[ 0];
g_frustumPlanes[0][1] = mvp[ 7] - mvp[ 4];
g_frustumPlanes[0][2] = mvp[11] - mvp[ 8];
g_frustumPlanes[0][3] = mvp[15] - mvp[12];
t = (float) sqrt( g_frustumPlanes[0][0] * g_frustumPlanes[0][0] +
g_frustumPlanes[0][1] * g_frustumPlanes[0][1] +
g_frustumPlanes[0][2] * g_frustumPlanes[0][2] );
g_frustumPlanes[0][0] /= t;
g_frustumPlanes[0][1] /= t;
g_frustumPlanes[0][2] /= t;
g_frustumPlanes[0][3] /= t;
//
// Extract the frustum's left clipping plane and normalize it.
//
g_frustumPlanes[1][0] = mvp[ 3] + mvp[ 0];
g_frustumPlanes[1][1] = mvp[ 7] + mvp[ 4];
g_frustumPlanes[1][2] = mvp[11] + mvp[ 8];
g_frustumPlanes[1][3] = mvp[15] + mvp[12];
t = (float) sqrt( g_frustumPlanes[1][0] * g_frustumPlanes[1][0] +
g_frustumPlanes[1][1] * g_frustumPlanes[1][1] +
g_frustumPlanes[1][2] * g_frustumPlanes[1][2] );
g_frustumPlanes[1][0] /= t;
g_frustumPlanes[1][1] /= t;
g_frustumPlanes[1][2] /= t;
g_frustumPlanes[1][3] /= t;
//
// Extract the frustum's bottom clipping plane and normalize it.
//
g_frustumPlanes[2][0] = mvp[ 3] + mvp[ 1];
g_frustumPlanes[2][1] = mvp[ 7] + mvp[ 5];
g_frustumPlanes[2][2] = mvp[11] + mvp[ 9];
g_frustumPlanes[2][3] = mvp[15] + mvp[13];
t = (float) sqrt( g_frustumPlanes[2][0] * g_frustumPlanes[2][0] +
g_frustumPlanes[2][1] * g_frustumPlanes[2][1] +
g_frustumPlanes[2][2] * g_frustumPlanes[2][2] );
g_frustumPlanes[2][0] /= t;
g_frustumPlanes[2][1] /= t;
g_frustumPlanes[2][2] /= t;
g_frustumPlanes[2][3] /= t;
//
// Extract the frustum's top clipping plane and normalize it.
//
g_frustumPlanes[3][0] = mvp[ 3] - mvp[ 1];
g_frustumPlanes[3][1] = mvp[ 7] - mvp[ 5];
g_frustumPlanes[3][2] = mvp[11] - mvp[ 9];
g_frustumPlanes[3][3] = mvp[15] - mvp[13];
t = (float) sqrt( g_frustumPlanes[3][0] * g_frustumPlanes[3][0] +
g_frustumPlanes[3][1] * g_frustumPlanes[3][1] +
g_frustumPlanes[3][2] * g_frustumPlanes[3][2] );
g_frustumPlanes[3][0] /= t;
g_frustumPlanes[3][1] /= t;
g_frustumPlanes[3][2] /= t;
g_frustumPlanes[3][3] /= t;
//
// Extract the frustum's far clipping plane and normalize it.
//
g_frustumPlanes[4][0] = mvp[ 3] - mvp[ 2];
g_frustumPlanes[4][1] = mvp[ 7] - mvp[ 6];
g_frustumPlanes[4][2] = mvp[11] - mvp[10];
g_frustumPlanes[4][3] = mvp[15] - mvp[14];
t = (float) sqrt( g_frustumPlanes[4][0] * g_frustumPlanes[4][0] +
g_frustumPlanes[4][1] * g_frustumPlanes[4][1] +
g_frustumPlanes[4][2] * g_frustumPlanes[4][2] );
g_frustumPlanes[4][0] /= t;
g_frustumPlanes[4][1] /= t;
g_frustumPlanes[4][2] /= t;
g_frustumPlanes[4][3] /= t;
//
// Extract the frustum's near clipping plane and normalize it.
//
g_frustumPlanes[5][0] = mvp[ 3] + mvp[ 2];
g_frustumPlanes[5][1] = mvp[ 7] + mvp[ 6];
g_frustumPlanes[5][2] = mvp[11] + mvp[10];
g_frustumPlanes[5][3] = mvp[15] + mvp[14];
t = (float) sqrt( g_frustumPlanes[5][0] * g_frustumPlanes[5][0] +
g_frustumPlanes[5][1] * g_frustumPlanes[5][1] +
g_frustumPlanes[5][2] * g_frustumPlanes[5][2] );
g_frustumPlanes[5][0] /= t;
g_frustumPlanes[5][1] /= t;
g_frustumPlanes[5][2] /= t;
g_frustumPlanes[5][3] /= t;
}
球形包围盒判断
{
for( int i = 0; i < 6; ++i )
{
if( g_frustumPlanes[i][0] * x +
g_frustumPlanes[i][1] * y +
g_frustumPlanes[i][2] * z +
g_frustumPlanes[i][3] <= -fRadius )
return false;
}
}
return true;
I抦 always amazed by the fact that most neophyte 3D engine programmers still do not realize the simple principal and benefits of frustum culling. I often frequent the forums on flipcode and I find that there are a ton of questions regarding this subject despite the plethora of information freely available. So I抳e decided to put together this simple document outlining my frustum culling procedures that I use in my current quad-tree culled engine. There are variations and perhaps much better ways of doing some of the culling techniques but the methods presented here should suffice for learning. Before I start I want to mention one thing. I previously have used the term frustrum but I was constantly beleaguered by the denizens of the forums for this incorrect moniker. As it turns out, frustum is the correct term. I apologize to anyone whom I抳e offended... you nit-picky twits. Most people already know what the viewing frustum is. For those who don抰, it抯 simply the area of your world visible to your current camera. The shape of the frustum is a pyramid with the nearest peak truncated at what is deemed the 憂ear� clipping plane (see The maximum benefit of frustum culling comes from a hierarchy culling method. This means that our world is broken down into a tree-like structure. Once we cull a top level node, we don抰 have to cull lower level nodes since they cannot be visible anyway. This For this example I am going to use a quad-tree for my hierarchal culling method. An octree or binary tree or any other structure could be used. In fact, most of the code will easily carry over. I choose a quad-tree since it抯 inherently easy to visualize. A |
Fundamental Methods 1 |
The first step in planning a system like this is making sure you have the basic methods of culling up and running. This means that we want to be able to construct the 6 planes of the frustum from our view/projection matrices as well as check whether a sphere is outside the frustum and whether a bounding box is outside the frustum. To be more concise, we want to know whether a sphere and box either is contained entirely within the frustum, entirely outside or intersecting the frustum. This will allow us to make more 憈weaks� to our hierarchal culling system later on. These are the methods we will look at in this section. First let抯 try to define our frustum. The 6 planes of the frustum can be defined from the view/projection matrix which form our camera system in our rendering API. Constructing these are a bit different for Direct3D and OpenGL. I could try to explain both or http://www2.ravensoft.com/users/ggribb/plane%20extraction.pdf Now I assume that you have a frustum class built that simply contains the 6 planes that define it. Make sure that you reconstruct this frustum and store it in your camera class each time the view or projection matrix changes and NOT each time you perform an C = center of sphere Distance = DotProduct(C, N) + D So like I said previously, all we need to do now is to compare this distance to the radius of the sphere to determine the status of the intersection of the sphere in regards to the frustum. Here is the code that I use to perform this action:
Our next step is to determine (in the case of a quad-tree) the status of an axis-aligned bounding box in regards to the frustum. There are a few ways of going about this operation. In this case I simply define my bounding box as a series of 3 minimum values Testing if a point is within the frustum is a simple procedure. All we need to do is to compare it to all 6 planes to make sure that it is on the front side of all of them (remember, all our planes face inwards into the frustum). Classifying a point relative
We now have all the tools necessary to do frustum culling. So far so good right? |
Optimizations 1 |
The first optimization for the above methods is very straightforward. If you study the two intersection methods you will most unquestionably notice that the sphere intersection method is significantly faster than the box intersection method. What this means is that we should perform sphere checks either instead of the box methods or at least before we check the box methods. In certain cases having a box as a bounding volume around our object can be much better since it will fit it more tightly. In these cases I would first check the bounding sphere of the object and then the bounding box. In fact, in my current engine each of my objects contains both a bounding sphere and a bounding box. The same goes for each node of my quad-tree. This way I can quickly reject objects/nodes using the sphere first and only if it passes that test do I check the box method. This is a very undemanding optimization and worth doing. All it requires is storing both a bounding sphere and box in each node/object that will be frustum culled. The next optimization has to do with correctly traversing your hierarchal structure. In the case of the quad-tree the general method is to start at the top node and check if it抯 visible. If it is, then we then proceed to check each of the children of that node. The third optimization is to not check for an intersection if the camera is within the bound volume. In a case such as this we know that the bound volume intersects the frustum. We should check this node抯 children however since as I抳e said previously. For this
|
Fundamental Methods 2 |
If you抳e already implemented all the previously mentioned material and profiled you application you may have noticed that the intersection code is still occupying a fairly large percentage of your cpu. Of course this depends on your application as well as the number of objects, the depth of your quad-tree, and various other factors. Even without profiling you have probably noticed that the intersection methods are fairly intensive. Even the fastest method of testing the sphere against the frustum requires testing each and every sphere against the 6 planes of the frustum, assuming no quick-outs. There are some improvements to be made. Before I get into them lets check out the methods that we will need in order to perform them. The first is a sphere-sphere intersection test. This is a very easy and fast method to implement. Basically the code computes the distance between the centers of the spheres and if this distance is less than the sum of the radii of the spheres, then we have
The next method is to determine if a sphere and a cone intersect. This is a bit more involved method than the sphere-sphere check. Again, I could explain it but luckily for us both there is a great document by Dave Eberly explaining it on his site Magic-Software.com. http://www.magic-software.com/Documentation/IntersectionSphereCone.pdf I find this site to be a great source of information, both on documents and on code. I highly recommend it to everyone. While the information in this article is more involved than what I presented so far, it surely isn抰 hard to understand and it抯 very easy |
Optimizations 2 |
Yep, you guessed it. Those last two methods are used for a couple supplementary optimizations. As I mentioned at the beginning of the last section, doing checks against the frustum can be quite costly so it抯 best to avoid them if possible. You抣l notice that the sphere-sphere intersection test and the sphere-cone intersection tests are quite a bit zippier than the frustum intersection methods. So we can put those to use as a first level culling method to reduce the number of cull calls sent to the slower methods. What we need to do is to construct both a sphere and a cone around the current frustum. Then we can check our bounding spheres against this frustum sphere and then the frustum cone to grossly reject objects that are just plainly out of view. This is a very fast method (or methods) and depending on the layout of your world can result in some nice speed improvements. Constructing a sphere around the frustum isn抰 that hard but it is more work than constructing the cone oddly enough. What we want with the sphere is to have it situated in the middle of the frustum with a radius that extends from the center of the sphere to
Constructing the cone that surrounds the frustum is much simpler. If you read the previous paper then you understand that the cone is basically defined by a vertex (origin of the cone), an axis ray (facing direction of the cone) and an angle that defines the
Having constructed this sphere and cone we can use these to quickly reject objects/nodes based on the intersection (or lack thereof) between their bounding spheres and this frustum sphere/cone. (You抣l notice that I don抰 bother to cull nodes that are beyond
|
Conclusion |
This pretty much sums up a good introduction to frustum culling that I hope many newbie engine programmers will find practical and helpful. As you can see by reading this, none of the concepts are hard and the math is very simple. There are of course many more optimizations that can be done to further enhance the culling procedure but this should serve as a good starting point. If anything sounds vague in the document, please let me know and I抣l try to write an update to clarify. I would like to thank Gil Gribb and Klaus Hartmann for their excellent article on plane extraction. I would also like to thank Dave Eberly for his excellent resources for this cone/sphere intersection description as well as the full site he maintains. It has And remember... Go vegan and exercise like hell - it WILL make you smarter or your money back. I guarantee it (not a guarantee). |