Part B - Direct3D

Visibility

Identify the different types of surface culling
Describe the two popular methods of occlusion culling
Introduce viewing frustum culling

Sample | Framework | Coordinator | Display | Exercises



Visibility was one of the first geometric problems addressed in three-dimensional computer graphics.  Some parts of the graphics representations of drawable objects are hidden from view by virtue of their position, orientation, or other representations, while other are visible.  We call the techniques for identifying hidden surfaces or parts thereof culling techniques.  We use the term surface culling to describe the exclusion of any graphics primitive surface or part thereof from the set of surfaces sent to the drawing pipeline.  The types of surface culling that are commonly implemented in computer graphics include:

  1. back-surface culling - excludes the surface of any primitive that faces away from the viewpoint
  2. occlusion culling - excludes any surface that is hidden from view by another surface
  3. viewing frustum culling - excludes any surface that is completely outside the viewing frustum
  4. contribution culling - excludes any surface that does not contribute significantly to the final image

We call solutions to the visibility problem hidden surface determination algorithms.  The painter's algorithm and the depth-buffering algorithm are two solutions that address occlusion.

In this chapter, we implement the first three forms of surface culling.  We describe the painter's and depth-buffering alogrithms and show how to determine if a drawable object is within the viewing frustum.


Visibility Sample

The Visibility Sample uses the same model as the Graphics Sample, but replaces the occlusion algorithm used in that sample with the more elaborate depth-buffering algorithm, producing a more realistic view of the relative positioning of the objects in the scene. 

visibility sample

This sample includes support for two variations of depth buffering - z-buffering and w-buffering - and omits rendering drawable objects that are completely outside the viewing frustum.  The default key mappings for user-controlled actions are:

  • '8' - toggle z-buffering
  • '9' - toggle w-buffering

Framework

Two components are upgraded to accommodate the visibility algorithms:

  • Coordinator - implements view frustum culling as well as toggling between the two variations of depth buffering
  • Display - the APIDisplaySet class selects the configurations that support depth buffering, while the APIDisplay class implements depth buffering for the selected configuration.

Visibility Components

Topics

The topics addressed include:

  • the difference between the painter's and depth buffering algorithms
  • the implementation of the depth buffering algorithm
  • z-buffering versus w-buffering
  • Direct3D specific details

Painter's versus Depth Buffering Algorithms

The two popular algorithms for occlusion culling are the painter's algorithm and the depth buffering algorithm.  The painter's algorithm imitates the top-down technique used by artists in creating paintings.  This technique is independent of the drawing process: the painter simply paints one colour over another colour.  The algorithm is object based: the object drawn last covers all or parts of previously drawn objects.  The Graphics Sample implemented this algorithm.  Note how the blue box is completely visible, even though half of it should be permanently hidden inside the green parent.  This awkward representation is due to the blue box being drawn after the green box.  The same holds for the blue-green box with respect to the red square.

visibility sample     visibility sample

With the painter's algorithm, objects need to be ordered so that the farthest object is drawn first and the nearest object drawn last.  This strict ordering is not necessary with the depth buffering algorithm. 

Depth Buffering Algorithm

The depth buffer algorithm is integrated into the drawing pipeline itself.  This algorithm is pixel-based and tracks the distance into clipping space of the points represented by the pixels most recently drawn onto the backbuffer.  The algorithm uses a worksurface on video memory with the same dimensions as the target (backbuffer) surface to hold the distance into clipping space of the most recently drawn pixel for the corresponding location.  We call this worksurface the depth buffer

painters algorithm

The depth buffering algorithm draws a pixel only if the depth value in the workspace is greater than the depth value for that pixel.  If so, the algorithm replaces the depth value for the previously drawn pixel with the depth value for the newly drawn pixel.  The workspace only holds the distances to the most recently drawn pixels at the different pixel locations on the backbuffer.  Snce all other points in the scene are necessarily hidden, the distances to them are irrelevant. 

The workspace holds fractional values and can occupy a significant portion of video memory.  Depth buffers use 16 bits, 24 bits or 32 bits to store the depth values for the pixels on the backbuffer.  The more bits used, the more accurate are the values stored in the depth buffer.  Some hardware requires the same bit depth for the depth buffer as for the backbuffer, while other hardware allows differing bit depths.  16-bit formats, which are the most commonly implemented ones, may produce artifacts, especially where far to near clipping plane ratios are high. 

The viewing frustum created by the perspective projection has a far clipping plane with a z value of 1 and a near clipping plane with a z value of 0 (or -1).  The depth value associated with each pixel scales between these limits and is interpolated from the actual depths of the vertices that define the position and orientation of the graphics primitive that contains the pixel.  If the pixel's depth is outside the z range of the viewing frustum, the pipeline does not draw that pixel.  If the pixel's depth is greater than the depth currently stored in the depth buffer, the pipeline does not draw that pixel either.  The pipeline only draws the pixel if its depth is within the range of the viewing frustum and less than the depth currently stored in the depth buffer.  In this case, the pipeline updates the value for that location in the depth buffer as illustrated in the figure below. 

depth buffering

Z Buffering and W Buffering

The pipeline can store depth values in either of two ways: z buffering and w buffering.  Z-buffering is the more common.  The 'z' refers to the out-of-plane direction with respect to the target surface.  Z-buffering minimizes the workspace and keeps the interpolation across a graphics primitive straightforward and inexpensive.  W-buffering is less widely implemented in hardware and uses interpolation across a graphics primitive that is more complex: the algorithm is not as straightforward. 

Not all drivers support both types of buffering.  Those that don't fall back to the type they do support or disable depth buffering altogether. 

Z-buffering shows disadvantages over w-buffering in the rendering of exterior scenes.  Z-buffer values are unevenly distributed across the range of depths within the viewing frustum and the ratio of the distances to the near and far clipping planes affects their distribution.  Exterior scenes often require ratios in the order of 1,000 and can result in 1% of the model depth spanning 50% of the depth buffer range.  The table shown below lists depth buffer values for a viewing frustum with a near clipping plane of 10 and a far clipping plane of 1000.  The high non-linearity of z-buffering produces rendering artifacts with objects that are at a large distance from the camera.

Model z coordinateZ-Depth
100.00
200.50
1000.91
2000.95
5000.98
10001.00

W-buffering, on the other hand, produces a linear distribution across the viewing frustum.  W-buffering is not always the preferred algorithm.  Where high-resolution of near objects is important, z-buffering may be preferable. 

Z-buffers typically store depth values in fixed-point format, while w-buffers store values in either scaled integer or floating-point formats.  For proper scaling, the z coordinate in the fourth column of the projection matrix should be a unit value. 

Direct3D Implementation

Direct3D supports both z-buffering and w-buffering and provides a two-tier method of determining the type of buffering available:

  • general interrogation for depth buffer support
  • specific interrogation for w-buffering support

The CheckDeviceFormat() method on the Direct3D COM object reports whether or not the driver supports a specific depth buffering surface.  An application, by calling this method several times in order from most desirable to least desirable format, can choose the optimal surface for the selected adapter and pass that selection to the CreateDevice()method when retrieving an interface to the display device.

Z-buffering is the default setting for depth-buffering in Direct3D if the configuration includes a depth buffer surface.  No depth-buffering is the alternative. 

The D3DPRASTERCAPS_WBUFFER flag on the RasterCaps member of the D3DCAPS9 struct returned by the GetDeviceCaps() method on the Direct3D COM object indicates whether the selected configuration supports w-buffering.

The framework sets depth buffering through the SetRenderState() method on the display device.  The render state enumeration constant is D3DRS_ZENABLE.  The constants for turning on z-buffering, turning on w-buffering, and turning off depth buffering are D3DZB_TRUE, D3DZB_USEW, and D3DZB_FALSE respectively. 

Translation Layer Settings

The framework defines enumeration constants and macros for toggling z-buffering and w-buffering:

 // Translation.h
 // ...
 typedef enum Action {
     // ...
     Z_BUFFERING_SELECT,
     W_BUFFERING_SELECT,
 } Action;

 #define ACTION_DESCRIPTIONS {\
     // ...
     L"Toggle Z-Buffering Mode", \
     L"Toggle W-Buffering Mode", \
 }

 #define ACTION_KEY_MAP {\
     // ...
     KEY_X , KEY_COMMA, KEY_8, KEY_9 \
 }

 // ...
 typedef enum RenderState {
     ALPHA_BLEND    = 1,
     LIGHTING       = 2,
     WIRE_FRAME     = 3,
     Z_BUFFERING    = 4,
     W_BUFFERING    = 5,
 } RenderState;
 // ...

Viewing Frustum

The viewing frustum is the volume bounded by six planes that encloses the entire space that is visible to the current viewer.  If any vertex of the graphics primitive that represents an object is within this frustum, that object or part of it is visible, and the framework needs to draw that object. 

The MathDecl.h file defines the Plane and ViewFrustum structs:

 // MathDecl.h

 // ...
 struct Plane {
     Vector n;
     float  d;
     Plane() : d(0) { }
     Plane(const Vector& v, float c) : n(v), d(c) { }
     bool onPositiveSide(const Vector& v) { return dot(n, v) + d < 0; }
     bool onPositiveSide(const Vector& v, float r) { return dot(n, v) + d <=
      - r; }
     Vector normal() const  { return n; }
     float constant() const { return d; }
 };

 void normalize(Plane& p);

 struct ViewFrustum {
     Plane plane[6];
     ViewFrustum(const Matrix& viewProjection);

     bool contains(const Vector& centre, float radius) {
         for ( int i = 0; i < 6; i++ )
             if (plane[i].onPositiveSide(centre, radius))
                 return false;
         return true;
     }
 };

The MathDef.h file implements the normalize() helper and the ViewFrustum constructor:

 // MathDef.h

 // ...
 inline void normalize(Plane& plane) {
     float length = plane.n.length();
     plane.n.x /= length;
     plane.n.y /= length;
     plane.n.z /= length;
     plane.d   /= length;
 }

 inline ViewFrustum::ViewFrustum(const Matrix& viewProj) {
     Vector centre(viewProj.m14, viewProj.m24, viewProj.m34);
     Vector width (viewProj.m11, viewProj.m21, viewProj.m31);
     Vector height(viewProj.m12, viewProj.m22, viewProj.m32);

     // Left plane
     plane[0].n = centre + width;
     plane[0].d = viewProj.m44 + viewProj.m41;
     // Right plane
     plane[1].n = centre - width;
     plane[1].d = viewProj.m44 - viewProj.m41;
     // Top plane
     plane[2].n = centre - height;
     plane[2].d = viewProj.m44 - viewProj.m42;
     // Bottom plane
     plane[3].n = centre + height;
     plane[3].d = viewProj.m44 + viewProj.m42;
     // Near plane
     plane[4].n = Vector(viewProj.m13, viewProj.m23, viewProj.m33);
     plane[4].d = viewProj.m43;
     // Far plane
     plane[5].n = centre - Vector(viewProj.m13, viewProj.m23, viewProj.m33);
     plane[5].d = viewProj.m44 - viewProj.m43;

     // Normalize planes
     for ( int i = 0; i < 6; i++ )
         normalize(plane[i]);
 }

Coordinator

The Coordinator component incorporates the two depth buffering options and toggling between those options. 

The Coordinator class defines flags that identify z-buffering and w-buffering states:

 // Coordinator.h

 class Coordinator : public iCoordinator {
     // ...
     bool wBuffering; // w-buffering is on
     bool zBuffering; // depth-buffering is on
     // ...
 };

Implementation

Construct

The constructor initializes the depth buffering flags:

 Coordinator::Coordinator(void* hinst, int show) {
     // ...
     wireFrame  = false;
     wBuffering = false;
     zBuffering = true;
     // ...
 }

Update

The update() method responds to toggles in and out of z-buffering or w-buffering mode:

 void Coordinator::update() {
     if (camera.size() && userInput->pressed(CAMERA_SELECT) &&
         now - lastCameraToggle > KEY_LATENCY) {
         lastCameraToggle = now;
         currentCam++;
         if (currentCam == camera.size())
             currentCam = 0;
     }
     if (camera.size() && camera[currentCam]) {
         camera[currentCam]->update();
     }
     if (now - lastWFrameToggle > KEY_LATENCY && (pressed(WIRE_FRAME_SELECT)
      || pressed(Z_BUFFERING_SELECT) || pressed(W_BUFFERING_SELECT))) {
         lastWFrameToggle = now;
         if (pressed(WIRE_FRAME_SELECT)) {
             wireFrame = !wireFrame;
             display->set(WIRE_FRAME,  wireFrame);
         }
         if (pressed(Z_BUFFERING_SELECT)) {
             zBuffering = !zBuffering;
             display->set(Z_BUFFERING, zBuffering);
         }
         if (pressed(W_BUFFERING_SELECT)) {
             wBuffering = !wBuffering;
             display->set(W_BUFFERING, wBuffering);
         }
     }
 }

Render

The single-argument render() method draws the objects that belong to the specified category only if the object is not completely outside the viewing frustum or if the object's representation is a sprite:

 void Coordinator::render(Category category) {
     ViewFrustum viewFrustum(view * projection);

     for (unsigned i = 0; i < object.size(); i++)
         if (object[i] && object[i]->belongsTo(category) &&
          (category == SPRITE || viewFrustum.contains(object[i]->position(),
          object[i]->radius()))) object[i]->render();
 }

Display

The Display component identifies the configurations that support depth-buffering while interrogating the host and implements depth buffering when setting up the selected display device.  This involves two separate classes: the APIDisplaySet class for the interrogation and the APIDisplay class for the implementation. 

APIDisplaySet Class

The interrogate() method on the APIDisplaySet object retrieves the availability of 16-bit and 32-bit depth buffering work surfaces with both hardware acceleration (HAL) and software emulation (REF).  This method only adds each configuration that supports such buffering to the set of available configurations for subsequent reporting to the user:

 bool APIDisplaySet::interrogate(void* hwnd) {
     // ...
     // enumerate and set all descriptions
     for (int id = 0; id < nAdapters; id++) {
         if (SUCCEEDED(d3d->GetAdapterIdentifier(id, 0, &d3di))) {
             rc = false;
             for (int ip = 0; ip < nPixelFormats; ip++) {
                 // ...
                 for (int ir = 0; ir < nr; ir++) {
                     if (SUCCEEDED(d3d->EnumAdapterModes(id, Format[ip], ir,
                      &mode)) &&
                      mode.Width >= WND_WIDTH && mode.Height >= WND_HEIGHT &&
                      (D3D_OK == d3d->CheckDeviceFormat(id, D3DDEVTYPE_HAL,
                      mode.Format,
                      D3DUSAGE_DEPTHSTENCIL, D3DRTYPE_SURFACE,  D3DFMT_D32) ||
                      D3D_OK == d3d->CheckDeviceFormat(id, D3DDEVTYPE_HAL,
                      mode.Format,
                      D3DUSAGE_DEPTHSTENCIL, D3DRTYPE_SURFACE, D3DFMT_D16) ||
                      D3D_OK == d3d->CheckDeviceFormat(id, D3DDEVTYPE_REF,
                      mode.Format,
                      D3DUSAGE_DEPTHSTENCIL, D3DRTYPE_SURFACE, D3DFMT_D32) ||
                      D3D_OK == d3d->CheckDeviceFormat(id, D3DDEVTYPE_REF,
                      mode.Format,
                      D3DUSAGE_DEPTHSTENCIL, D3DRTYPE_SURFACE, D3DFMT_D16))) {
                         // ...
                     }
                 }
             }
             // ...
         }
     }
     return rc;
 }

The CheckDeviceFormat() method on the Direct3D COM object reports whether the specified adapter supports depth-buffering at the specified mode and pixel format.  The first argument in a call to this method identifies the display adapter.  The second argument identifies the device type: the hardware rasterizer - D3DDEVTYPE_HAL - or the software emulator - D3DDEVTYPE_REF.  The third argument identifies the pixel format.  The fourth argument - D3DUSAGE_DEPTHSTENCIL - requests a depth buffer.  The fifth argument identifies the requested resource as a work surface (D3DRTYPE_SURFACE).  The sixth argument identifies the surface's format (D3DFMT_D32 for 32 bit and D3DFMT_D16 for 16 bit).  This method returns D3D_OK if the specifications support depth buffering. 

APIDisplay Class

The APIDisplay class includes instance flag that holds the selected device's ability to support w-buffering: 

 class APIDisplay : public iAPIDisplay, public APIBase {
     // ...
     bool hasWBuffering;         // has w-buffering?
     // ...
 };

Setup

The setup() method on the APIDisplay object checks for the availability of any HAL configuration, first a 32-bit buffer, then a 16-bit buffer, and, only if neither one is available, checks for a 32-bit buffer using software emulation.  This method selects the most advanced format available.  As the worst case scenario, it selects software emulation with a 16-bit depth buffer.  It also determines whether w-buffering is available on the selected configuration.

Having selected the best configuration possible, this method creates the depth buffer while retrieving an interface to the Direct3DDisplay COM object.  This method passes the values describing the depth buffer through the D3DPRESENT_PARAMETERS struct.  It identifies use of a depth buffer through the EnableAutoDepthStencil member (set to TRUE) and its bit format through the AutoDepthStencilFormat member. 

 bool APIDisplay::setup() {
     // ...
     d3dpp.EnableAutoDepthStencil = TRUE;
     // ...
     // find the best format for depth buffering and stenciling
     D3DDEVTYPE devtype;
     if (D3D_OK == d3d->CheckDeviceFormat(adapter, D3DDEVTYPE_HAL,
      d3dFormat, D3DUSAGE_DEPTHSTENCIL, D3DRTYPE_SURFACE, D3DFMT_D32)) {
         d3dpp.AutoDepthStencilFormat = D3DFMT_D32; // depth buffer
         devtype = D3DDEVTYPE_HAL;                  // HAL device
     }
     else if (D3D_OK == d3d->CheckDeviceFormat(adapter, D3DDEVTYPE_HAL,
      d3dFormat, D3DUSAGE_DEPTHSTENCIL, D3DRTYPE_SURFACE, D3DFMT_D16)) {
         d3dpp.AutoDepthStencilFormat = D3DFMT_D16;  // depth buffer
         devtype = D3DDEVTYPE_HAL;                   // HAL Device
     }
     // if the above attempts fail, use the REF (software emulation) device
     // with a 32-bit depth buffer rather than the HAL (hardware accelerated)
     // device
     else if (D3D_OK == d3d->CheckDeviceFormat(adapter, D3DDEVTYPE_REF,
      d3dFormat, D3DUSAGE_DEPTHSTENCIL, D3DRTYPE_SURFACE, D3DFMT_D32)) {
         d3dpp.AutoDepthStencilFormat = D3DFMT_D32;   // depth buffer
         devtype = D3DDEVTYPE_REF;                    // REF Device
     }
     // if all else fails, use the REF (software emulation) with a 16-bit
     // depth buffer, hoping that it will work. (If it doesn't, we are out
     // of luck anyway.)
     else {
         d3dpp.AutoDepthStencilFormat = D3DFMT_D16;   // depth buffer
         devtype = D3DDEVTYPE_REF;                    // REF Device
     }

     // extract the device capabilities and configure the limits
     D3DCAPS9 caps;
     d3d->GetDeviceCaps(adapter, devtype, &caps);
     hasWBuffering = (caps.RasterCaps & D3DPRASTERCAPS_WBUFFER) != 0L;

     // ...
     else if (FAILED(d3d->CreateDevice(adapter, devtype, (HWND)hwnd,
      behaviorFlags, &d3dpp, &d3dd)))
         error(L"APIDisplay::12 Failed to create Direct3D device");
     else {
         // ...
         rc = true;
     }
     // ...
     return rc;
 }

The CreateDevice() method on the Direct3D COM object accepts the device type - D3DDEVTYPE_HAL or D3DDEVTYPE_REF - through the second argument and the format of the depth buffer through the fifth argument. 

Begin Draw Frame

The beginDrawFrame() method on the APIDisplay object initializes the depth buffer so that each pixel on the target surface is associated with the far clipping plane: 

 void APIDisplay::beginDrawFrame(const void* view) {
     // ...
     if (d3dd) {
         d3dd->Clear(0, NULL, D3DCLEAR_TARGET | D3DCLEAR_ZBUFFER,
          D3DCOLOR_XRGB(BGROUND_R, BGROUND_G, BGROUND_B), 1.0, 0);
         d3dd->BeginScene();
     }
 }

The Clear() method on the display device initializes depth buffer values to the value received in its fifth parameter.  The D3DCLEAR_ZBUFFER flag specifically requests initialization of the depth-buffer.  The value of the fifth argument is in z clipping coordinates and may be in the range [0,1]

Set

The set() method sets the type of depth buffering to be used in rendering the frame: 

 void APIDisplay::set(RenderState state, bool b) {

     if (d3dd) {
         switch (state) {
             case ALPHA_BLEND:
                 d3dd->SetRenderState(D3DRS_ALPHABLENDENABLE, b);
                 break;
             case LIGHTING:
                 d3dd->SetRenderState(D3DRS_LIGHTING, b);
                 break;
             case WIRE_FRAME:
                 d3dd->SetRenderState(D3DRS_FILLMODE, b ? D3DFILL_WIREFRAME
                  : D3DFILL_SOLID);
             case Z_BUFFERING:
                 d3dd->SetRenderState(D3DRS_ZENABLE, b ? D3DZB_TRUE
                  : D3DZB_FALSE);
                 break;
             case W_BUFFERING:
                 if (hasWBuffering) d3dd->SetRenderState(D3DRS_ZENABLE,
                  b ? D3DZB_USEW : D3DZB_FALSE);
                 break;
         }
     }
 }

The D3DRS_TRUE flag turns on z-buffering, the D3DRS_USEW flag turns on w-buffering, and the D3DRS_FALSE flag turns off either type of depth buffering. 


Exercises

  • Read the Wikipedia article on Depth Buffering
  • Read the GameDev article on Geometry Culling
  • Read the DirectX Documentation on Depth Buffers
  • Rearrange the order in which the boxes are created in the Design::initialize() and review their representations on the screen.  Repeat the same exercise with the Graphics Primitive Sample and review their representation.