Thread: Clipping

That clipping should have been done by DirectX or DirectDraw depending on your application. If not you need to check out the Sutherland-Hodgman algorithm for clipping polygons.

For clipping against the actual view frustrum a fast test is to check the angle between the normal to the polygon and the camera look vector. An easy way to do this is to normalize the camera look vector and then compute the dot product of the normal and the camera look vector. If the result is >0 then it is possible this object needs to be drawn. If it's <0 then you know that the object should not be drawn as it is behind the camera. The angle does not fall into the -90<0<90 range.

Another way to more accurate frustrum culling is to use the view frustrum as the bounding volume. You can either test against the bounding box in 2D or the bounding cube in 3D or you can tesselate the bounding box into tri's and test for intersections that way. If the bounding volume of your object does not intersect the bounding volume of the frustrum, or the frustrum itself, then don't add it to the list to be drawn. If it does intersect it then it is up to you to determine how much of the volume actually intersects the frustrum. You can then clip your geometry against that volume. However it has been my experience that the actual clipping of the object/model that is partially inside and partially outside of the frustrum is actually more expensive than just letting Direct3D or OpenGL decide what to do with it. As long as you are definitely eliminating objects that should not be drawn you will be ok.

There are several articles about this over at www.gamedev.net and www.gamasutra.com as well as in Moller and Haine's book Real Time Rendering available at www.amazon.com. You should also check out 3D Mathematics for Game Programming and Development, Fletcher Dunn and Ian Parberry. Both of them discuss several ways this can be done. The latter suggests the same as I - that you should not worry about objects that partially intersect the frustrum.

There are also several other culling methods out there and most of them come down to division of larger spaces into smaller spaces and doing tests on the smaller spaces.

A totally accurate cull would be to first run the model through trivial rejection (noted above). Then if it passes that you would run it through the more expensive trivial rejection portion (bounding volume against frustrum). If it passes that then you would perform a very expensive triangle to bounding volume instersection test for all FRONT FACING triangles. No need to perform this for back facing tri's since they won't be drawn. You can use the dot product again to determine facing for the tri's. Performing the dot product on each tri is probably not the best idea so you will have to optimize and pre-compute. Also you may want to break your model up into several smaller bounding volumes and use a octree-type setup to quickly eliminate tri's that absolutely do not intersect the edge of the frustrum. After you performed all the steps you would then pass all these vertices along to be rendered, lit, textured, etc.

It can be quite a complex process and your best bet is an approximation since little or no gain in visual quality is usually noticed between perfect culling and an approximation.