[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

7.6.7.7 In-Sector Visibility

For a normal sector which has no octree in-sector visibility is really very simple. Everything which is not culled by the view frustum or the portal/sector visibility system is visible.

If a sector has an octree then the situation is vastly different. Here is where the main work of the visibility algorithm happens. In-sector visibility is also 2D based (screen coordinates). This is why the discussion for detail objects in the previous section (Portal/Sector Visibility) is relevant here too. In general we will try to avoid to do as little culling work as possible while still trying to cull as much as possible.

The above comment is why it is important to have a good world design. World geometry (which is at the basis of visibility culling) should contain as little polygons as possible but they should be as big as possible and also potentially cull lots of geometry. Culling objects should be found for all large detail objects which can potentially cull large numbers of other objects or portals.

The current culler works with the c-buffer. For every scanline we have a list of not rendered spans (i.e. the Crystal Space c-buffer keeps empty spans instead of full spans). Initially we will have a list of H spans with H being the number of scanlines on the screen. Every span will have a width of W with W being the number of horizontal screen pixels. When a polygon is added to the c-buffer it will be scan-converted and every scan of the polygon will be inserted at the appropriate line of the c-buffer.

An important issue with the c-buffer is that it doesn't have Z information. So adjacent empty or full spans can be merged. This is in contrast with the s-buffer which keeps Z information for every span. This keeps complexity down enormously and also improves efficiently. The downside of this method is that it requires perfect front to back sorting in order to work properly (more on ways to solve that later).

So given an octree and the c-buffer we can explain how the basic visibility algorithm works.

We start by initializing the c-buffer to empty. Then we traverse all nodes and polygons from front to back. Every polygon that is encountered is fed to the c-buffer and added to it. This means projecting the polygon to camera space and then perspective projecting it. If the c-buffer indicates that a polygon is not visible it will be culled at this stage already. This is called polygon culling. More important than polygon culling is node culling. Before traversing into a new octree node we take the convex outline of the node box and test if that convex outline is visible to the c-buffer. This is the main reason that the c-buffer culling is in Crystal Space. Culling octree nodes can be a huge speed benefit as they can often contain thousands of polygons and also other child nodes.

This is the basic idea behind c-buffer culling. But here we have several choices on what to do with individual polygons and detail objects.

Let's first focus on individual polygons. In the discussion above we told you that we can cull individual polygons by feeding them to the c-buffer and seeing if they are actually visible or not. We cannot get around the fact that we need to put them in the c-buffer (we're talking about world geometry here, not detail objects). And since we do that the test to see if the c-buffer was modified (i.e. the polygon is visible) is trivial. On the other hand, in order to be able to use this visibility test for individual polygons we need strict front to back order. This is provided by the BSP trees. Traversing the BSP tree itself involves some overhead. First of all because it does some processing with regards to testing on which side of every splitter the camera is and also before the BSP tree itself caused polygons to be split so there are actually more polygons to consider. So we could consider rendering and feeding the polygons from the octree node in original unsorted order. This way we would not be able to use visibility information for the polygons themselves but the c-buffer would still be correctly filled. This will cause a big number of overdraw so this should only be done on hardware that is fast enough. Also this approach may mean that it would be better to lower the number of polygons at which the octree reverts to BSP trees (i.e. 150 right now). This means we'll get smaller octree nodes and thus reduce overdraw that way. This is an area where some experimentation is needed.

Detail objects are another issue. Similar to what was discussed in the portal/sector visibility section we have several options here. First we could just say that all detail objects that are in some node are visible when the node itself is visible. This is easy to do and would give little overhead with regards to the c-buffer. On the other hand it can cause considerable overdraw and if the detail objects are complex it may be too slow.

The other option is to test a bounding box (or the convex outline of the bounding box) against the c-buffer. There is even the option of a hybrid approach. i.e. simple detail objects can be considered as visible if the parent node is visible while complex objects will have a bounding box that is tested.

So again, there is much room for experimentation to see what approach works best. It may be that we will have to make things configurable depending on the selected hardware.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

This document was generated using texi2html