The Mechanics of Robust Stencil Shadows

The idea of using the stencil buffer to generate shadows has been around for over a decade, but only recently has 3D graphics hardware advanced to the point where using the stencil algorithm on a large scale has become practical. Not long ago, there existed some unsolved problems pertaining to stencil shadows that prevented the algorithm from working correctly under various conditions. Advances have now been made, however, so that stencil shadows can be robustly implemented to handle arbitrarily positioned point lights and infinite directional lights having any desired spatial relationship with the camera. This article presents the intricacies of the entire stencil shadow algorithm and covers every mathematical detail of its efficient implementation.

Algorithm Overview

The basic concept of the stencil shadow algorithm is to use the stencil buffer as a masking mechanism to prevent pixels in shadow from being drawn during the rendering pass for a particular light source. This is accomplished by rendering an invisible shadow volume for each shadow-casting object in a scene using stencil operations that leave nonzero values in the stencil buffer wherever light is blocked. Once the stencil buffer has been filled with the appropriate mask, a lighting pass only illuminates pixels where the value in the stencil buffer is zero.

As shown in Figure 1, an object’s shadow volume encloses the region of space for which light is blocked by the object. This volume is constructed by finding the edges in the object’s triangle mesh representing the boundary between lit triangles and unlit triangles and extruding those edges away from the light source. Such a collection of edges is called the object’s silhouette with respect to the light source. The shadow volume is rendered into the stencil buffer using operations that modify the stencil value at each pixel depending on whether the depth test passes or fails. Of course, this requires that the depth buffer has already been initialized to the correct values by a previous rendering pass. Thus, the scene is first rendered using a shader that applies surface attributes that do not depend on any light source, such as ambient illumination, emission, and environment mapping.

 

	Figure 1. An object’s shadow volume encloses the region of space for which light is blocked by the object.

The original stencil algorithm renders the shadow volume in two stages. In the first stage, the front faces of the shadow volume (with respect to the camera) are rendered using a stencil operation that increments the value in the stencil buffer whenever the depth test passes. In the second stage, the back faces of the shadow volume are rendered using a stencil operation that decrements the value in the stencil buffer whenever the depth test passes. As illustrated in Figure 2, this technique leaves nonzero values in the stencil buffer wherever the shadow volume intersects any surface in the scene, including the surface of the object casting the shadow.

 

	Figure 2. Numbers at the ends of rays emanating from the camera position C represent the values left in the stencil buffer for a variety of cases. The stencil value is incremented when front faces of the shadow volume pass the depth test, and the stencil value is decremented when back faces of the shadow volume pass the depth test. The stencil value does not change when the depth test fails.

There are two major problems with the method just described. The first is that no matter what finite distance we extrude an object’s silhouette away from a light source, it is still possible that it is not far enough to cast a shadow on every object in the scene that should intersect the shadow volume. The example shown in Figure 3 demonstrates how this problem arises when a light source is very close to a shadow-casting object. Fortunately, this problem can be elegantly solved by using a special projection matrix and extruding shadow volumes all the way to infinity.

 

	Figure 3. No matter what finite distance an object’s silhouette is extruded away from a light source, moving the light close enough to the object can result in a shadow volume that cannot reach other objects in the scene.

The second problem shows up when the camera lies inside the shadow volume or the shadow volume is clipped by the near plane. Either of these occurrences can leave incorrect values in the stencil buffer causing the wrong surfaces to be illuminated. The solution to this problem is to add caps to the shadow volume geometry, making it a closed surface, and using different stencil operations. The two caps added to the shadow volume are derived from the object’s triangle mesh as follows. A front cap is constructed using the unmodified vertices of triangles facing toward the light source. A back cap is constructed by projecting the vertices of triangles facing away from the light source to infinity. For the resulting closed shadow volume, we render back faces (with respect to the camera) using a stencil operation that increments the stencil value whenever the depth test fails, and we render front faces using a stencil operation that decrements the stencil value whenever the depth test fails. As shown in Figure 4, this technique leaves nonzero values in the stencil buffer for any surface intersecting the shadow volume for arbitrary camera positions. Rendering shadow volumes in this manner is more expensive than using the original technique, but we can determine when it’s safe to use the less-costly depth-pass method without having to worry about capping our shadow volumes.

 

	Figure 4. Using a capped shadow volume and depth-fail stencil operations allows the camera to be inside the shadow volume. The stencil value is incremented when back faces of the shadow volume fail the depth test, and the stencil value is decremented when front faces of the shadow volume fail the depth test. The stencil value does not change when the depth test passes.

The details of everything just described are discussed throughout the remainder of this article. In summary, the rendering algorithm for a single frame runs through the following steps.

A Clear the frame buffer and perform an ambient rendering pass. Render the visible scene using any surface shading attribute that does not depend on any particular light source.

B Choose a light source and determine what objects may cast shadows into the visible region of the world. If this is not the first light to be rendered, clear the stencil buffer.

C For each object, calculate the silhouette representing the boundary between triangles facing toward the light source and triangles facing away from the light source. Construct a shadow volume by extruding the silhouette away from the light source.

D Render the shadow volume using specific stencil operations that leave nonzero values in the stencil buffer where surfaces are in shadow.

E Perform a lighting pass using the stencil test to mask areas that are not illuminated by the light source.

F Repeat steps B through E for every light source that may illuminate the visible region of the world.

For a scene illuminated by n lights, this algorithm requires at least n+1 rendering passes. More than n+1 passes may be necessary if surface shading calculations for a single light source cannot be accomplished in a single pass. To efficiently render a large scene containing many lights, one must be careful during each pass to render only objects that could potentially be illuminated by a particular light source. An additional optimization using the scissor rectangle can also save a significant amount of rasterization work -- this optimization is discussed in the last section of this article.

One aspect of advanced rendering we haven't discussed yet is stenciling, a technique that can be useful for developing commercial applications. If you want your 3D applications to stand apart from the crowd, you'd be wise to combine stenciling with the texturing techniques you learned about in earlier chapters. This chapter will detail how to use stenciling and show you the different types of effects you can generate with it.

Many 3D games and simulations on the market use cinema-quality special effects to add to their dramatic impact. You can use stencil buffers to create effects such as composites, decals, dissolves, fades, outlines, silhouettes, swipes, and shadows. Stencil buffers determine whether the pixels in an image are drawn. To perform this function, stencil buffers let you enable or disable drawing to the render-target surface on a pixel-by-pixel basis. This means your software can "mask" portions of the rendered image so that they aren't displayed.

When the stenciling feature is enabled, Microsoft Direct3D performs a stencil test for each pixel that it plans to write to the render-target surface. The stencil test uses a stencil reference value, a stencil mask, a comparison function, and a pixel value from the stencil buffer that corresponds to the current pixel in the target surface. Here are the specific steps used in this test:

1. Perform a bitwise AND operation of the stencil reference value with the stencil mask.
2. Perform a bitwise AND operation on the stencil-buffer value for the current pixel with the stencil mask.
3. Compare the results of Step 1 and Step 2 by using the comparison function.

By controlling the comparison function, the stencil mask, the stencil reference value, and the action taken when the stencil test passes or fails, you can control how the stencil buffer works. As long as the test succeeds, the current pixel will be written to the target. The default comparison behavior (the value that the D3DCMPFUNC enumerated type defines for D3DCMP_ALWAYS) is to write the pixel without considering the contents of the stencil buffer. You can change the comparison function to any function you want by setting the value of the D3DRENDERSTATE_STENCILFUNC render state and passing one of the members of the D3DCMPFUNC enumerated type.

Creating a Stencil Buffer

Before creating a stencil buffer, you need to determine what stenciling capabilities the target system supports. To do this, call the IDirect3DDevice7::GetCaps method. The dwStencilCaps flags specify the stencil-buffer operations that the device supports. The reported flags are valid for all three stencil-buffer operation render states: D3DRENDERSTATE_STENCILFAIL, D3DRENDERSTATE_STENCILPASS, and D3DRENDERSTATE_STENCILZFAIL. Direct3D defines the following flags for dwStencilCaps:

• D3DSTENCILCAPS_DECR Indicates that the D3DSTENCILOP_DECR operation is supported
  
  
• D3DSTENCILCAPS_DECRSAT Indicates that the D3DSTENCILOP_DECRSAT operation is supported
  
  
• D3DSTENCILCAPS_INCR Indicates that the
  D3DSTENCILOP_INCR operation is supported
  
  
• D3DSTENCILCAPS_INCRSAT Indicates that the D3DSTENCILOP_INCRSAT operation is supported
  
  
• D3DSTENCILCAPS_INVERT Indicates that the D3DSTENCILOP_INVERT operation is supported
  
  
• D3DSTENCILCAPS_KEEP Indicates that the D3DSTENCILOP_KEEP operation is supported
  
  
• D3DSTENCILCAPS_REPLACE Indicates that the D3DSTENCILOP_REPLACE operation is supported
  
  
• D3DSTENCILCAPS_ZERO Indicates that the D3DSTENCILOP_ZERO operation is supported
  

Parameter	Description
riidDevice	A reference to a globally unique identifier (GUID) for the device whose depth-buffer formats you want enumerated
IpEnumCallback	The address of a D3DEnumPixelFormatsCallback function you want called for each supported depth-buffer format
IpContext	Application-defined data that is passed to the callback function

If the method succeeds, it returns the value D3D_OK. If it fails, the method returns one of these four values:

• DDERR_INVALIDOBJECT
  
  
• DDERR_INVALIDPARAMS
  
  
• DDER_NOZBUFFERHW
  
  
• DDERR_OUTOFMEMORY

The code in listing 1 determines what stencil buffer formats are available and what operations are supported and then creates a stencil buffer. As you can see, this code notes whether the stencil buffer supports more than 1-bit -- some stenciling techniques must be handled differently if only a 1-bit stencil buffer is available.

Clearing a Stencil Buffer

The IDirect3DDevice7 interface includes the Clear method, which you can use to simultaneously clear the render target's color buffer, depth buffer, and stencil buffer. Here's the declaration for the IDirect3DDevice7::Clear method:

    HRESULT IDirect3DDevice7::Clear(
       DWORD dwCount,
       LPD3DRECT lpRects,
       DWORD dwFlags,
       D3DVALUE dvZ,
       DWORD dwStencil
    );

Parameter	Description
dwCount	The number of rectangles in the array at lpRects.
IpRects	An array of D3DRECT structures defining the rectangles to be cleared. You can set a rectangle to the dimensions of the render-target surface to clear the entire surface. Each of these rectangles uses screen coordinates that correspond to points on the render-target surface. The coordinates are clipped to the bounds of the viewport rectangle.
dwFlags	Flags indicating which surfaces should be cleared. This parameter can be any combination of the following flags, but at least one flag must be used:
	D3DCLEAR_TARGET Clear the render-target surface to the color in the dwColor parameter. D3DCLEAR_STENCIL Clear the stencil buffer to the value in the dwStencil parameter.
	D3DCLEAR_ZBUFFER Clear the depth buffer to the value in the dvZ parameter.
dwColor	D3DCLEAR_ZBUFFER Clear the depth buffer to the value in the dvZ parameter..
dvZ	A 32-bit RGBA color value to which the render-target surface will be cleared.
dwStencil	The new z value that this method stores in the depth buffer. This parameter can range from 0.0 to 1.0, inclusive. The value of 0.0 represents the nearest distance to the viewer, and 1.0 represents the farthest distance.
	The integer value to store in each stencil-buffer entry. This parameter can range from 0 to 2n-1 inclusive, in which n is the bit depth of the stencil buffer.

The IDirect3DDevice7::Clear method still accepts the older D3DCLEAR_TARGET flag, which clears the render target using an RGBA color you provide in the dwColor parameter. This method also still accepts the D3DCLEAR_ZBUFFER flag, which clears the depth buffer to a depth you specify in dvZ (in which 0.0 is the closest distance and 1.0 is the farthest). DirectX 6 introduced the D3DCLEAR_STENCIL flag, which you can use to reset the stencil bits to the value you specify in the dwStencil parameter. This value can be an integer ranging from 0 to 2n-1, in which n is the bit depth of the stencil buffer.

________________________________________________________

Configuring the Stenciling State

Configuring the Stenciling State
You control the various settings for the stencil buffer using the IDirect3DDevice7::
SetRenderState method. Listing 2 shows the stencil-related members of the D3DRENDERSTATETYPE enumerated type.

      These are the definitions for the stencil-related render states:

• D3DRENDERSTATE_STENCILENABLE Use this member to enable or disable stenciling. To enable stenciling, use this member with TRUE; to disable stenciling, use it with FALSE. The default value is FALSE.
  
  
• D3DRENDERSTATE_STENCILFAIL Use this member to indicate the stencil operation to perform if the stencil test fails. The stencil operation can be one of the members of the D3DSTENCILOP enumerated type. The default value is D3DSTENCILOP_KEEP.
  
  
• D3DRENDERSTATE_STENCILZFAIL Use this member to indicate the stencil operation to perform if the stencil test passes and the depth test (z-test) fails. The operation can be one of the members of the D3DSTENCILOP enumerated type. The default value is D3DSTENCILOP_KEEP.
  
  
• D3DRENDERSTATE_STENCILPASS Use this member to indicate the stencil operation to perform if both the stencil test and the depth test (z-test) pass. The operation can be one of the members of the D3DSTENCILOP enumerated type. The default value is D3DSTENCILOP_KEEP.
  
  
• D3DRENDERSTATE_STENCILFUNC Use this member to indicate the comparison function for the stencil test. The comparison function can be one of the members of the D3DCMPFUNC enumerated type. The default value is D3DCMP_ALWAYS. This function compares the reference value to a stencil-buffer entry and applies only to the bits in the reference value and stencil-buffer entry that are set in the stencil mask. (The D3DRENDERSTATE_STENCILMASK render state sets the stencil mask.) If the comparison is true, the stencil test passes.
  
  
• D3DRENDERSTATE_STENCILREF Use this member to indicate the integer reference value for the stencil test. The default value is 0.
  
  
• D3DRENDERSTATE_STENCILMASK Use this member to specify the mask to apply to the reference value and each stencil-buffer entry to determine the significant bits for the stencil test. The default mask is 0xFFFFFFFF.
  
  
• D3DRENDERSTATE_STENCILWRITEMASK Use this member to specify the mask to apply to values written into the stencil buffer. The default mask is 0xFFFFFFFF.
  
  

The D3DSTENCILOP enumerated type describes the stencil operations for the D3DRENDERSTATE_STENCILFAIL, D3DRENDERSTATE_STENCILZFAIL, and D3DRENDERSTATE_STENCILPASS render states. Here's the definition of D3DSTENCILOP:

    //--------------------------------------------------
    // Name: RenderShadow
    // Desc:
    //------------------------------------------------
    HRESULT CMyD3DApplication::RenderShadow()
    {
        // Turn off depth buffer and turn on
           stencil buffer.
        m_pd3dDevice->SetRenderState(
                           D3DRENDERSTATE_ZWRITEENABLE,
                                     FALSE );
        m_pd3dDevice->SetRenderState(
                           D3DRENDERSTATE_STENCILENABLE,
                                     TRUE );

Next the code sets the comparison function that performs the stencil test by calling the IDirect3DDevice7::SetRenderState method and setting the first parameter to D3DRENDERSTATE_STENCILFUNC. The second parameter is set to a member of the D3DCMPFUNC enumerated type. In this code, we want to update the stencil buffer everywhere a primitive is rendered, so we use D3DCMP_ALWAYS:

     //
    // Set up stencil comparison function,
       reference value, and masks.
    // Stencil test passes if ((ref & mask)
       cmpfn (stencil & mask))
    // is true.
    //
    m_pd3dDevice->SetRenderState(
                           D3DRENDERSTATE_STENCILFUNC,
                                 D3DCMP_ALWAYS );

In this sample, we don't want the stencil buffer to change if either the stencil buffer test or the depth buffer test fails, so we set the appropriate states to D3DSTENCILOP_KEEP:

     m_pd3dDevice->SetRenderState(
                          D3DRENDERSTATE_STENCILZFAIL,
                                  D3DSTENCILOP_KEEP );
     m_pd3dDevice->SetRenderState(
                          D3DRENDERSTATE_STENCILFAIL,
                                  D3DSTENCILOP_KEEP );

The settings in listing 3 are different depending on whether a 1-bit or a multibit stencil buffer is present. If the stencil buffer has only 1 bit, the value 1 is stored in the stencil buffer whenever the stencil test passes. Otherwise, an increment operation (either D3DSTENCILOP_INCR or D3DSTENCILOP_INCRSAT) is applied if the stencil test passes. At this point, the stencil state is configured and the code is ready to render some primitives.

________________________________________________________

Creating Effects

Creating Effects
Now that you've seen how to create stencil buffers and configure how they work, let's look at some of the effects you can render with them. The following sections describe several ways Microsoft recommends using stencil buffers. Each of these approaches produces impressive results, but a few of them have drawbacks.

Composites

You can use stencil buffers for compositing 2D or 3D images onto a 3D scene. By using a mask in the stencil buffer to occlude a portion of the render-target surface, you can write stored 2D information (such as text or bitmaps). You can also render 3D primitives -- or for that matter a complete scene -- to the area of the render-target surface that you specify in a stencil mask.

Developers often use this effect to composite several scenes in simulations and games. Many driving games feature a rear view mirror that displays the scene behind the driver. You can composite this second 3D scene with the driver's view forward by using a stencil to block the portion to which you want the mirror image rendered. You can also use composites to create 2D "cockpits" for vehicle simulations by combining a 2D, bitmapped image of the cockpit with the final, rendered 3D scene.

Decals

You can use decals to control which pixels form a primitive image you draw to a render-target surface. When you apply a texture to an object (for example, applying scratch marks to a floor), you need the texture (the scratch marks) to appear immediately on top of the object (the floor). Because the z values of the scratch marks and the floor are equal, the depth buffer might not yield consistent results, meaning that some pixels in the back primitive might be rendered on top of those in the front primitive. This overlap, which is commonly known as z-fighting or flimmering, can cause the final image to shimmer as you animate from one frame to the next.

You can prevent flimmering by using a stencil to mask the section of the back primitive on which you want the decal to appear. You can then turn off z-buffering and render the image of the front primitive into the masked area of the render-target surface.

Dissolves

You can use dissolves to gradually replace an image by displaying a series of frames that transition from one image to another. In Chapter 8, you saw how to use multiple-texture blending to create this effect by gradually blending two textures together. Stencil buffers allow you to produce similar dissolves, except that a stencil-based dissolve looks more pixelated than a multiple-texture blending one. However, stencil buffers let you use texture-blending capabilities for other effects while performing a dissolve. This capability enables you to efficiently produce more complex effects than you could by using texture blending alone.

A stencil buffer can perform a dissolve by controlling which pixels you draw from two different images to the render-target surface. You can perform a dissolve by defining a base stencil mask for the first frame and altering it incrementally or by defining a series of stencil masks and copying them into the stencil buffer on successive frames.

To start a dissolve, set the stencil function and stencil mask so that most of the pixels from the starting image pass the stencil test and most of the ending image's pixels fail. For each subsequent frame, update the stencil mask to allow fewer pixels in the starting image to pass the test and more pixels in the ending image to pass. By controlling the stencil mask, you can create a variety of dissolve effects.

Although this approach can produce some fantastic effects, it can be a bit slow on some systems. You should test the performance on your target systems to verify that this approach works efficiently for your application.

Fades

You can fade in or out using a form of dissolving. To perform this effect, use any dissolve pattern you want. To fade in, use a stencil buffer to dissolve from a black or white image to a rendered 3D scene. To fade out, start with a rendered 3D scene and dissolve to black or white. As with dissolves, you should check the performance of fades on the target systems to verify that their speed and appearance is acceptable.

Outlines

You can apply a stencil mask to a primitive that's the same shape but slightly smaller than the primitive. The resulting image will contain only the primitive's outline. You can then fill this stencil-masked area of the primitive with a color or set of colors to produce an outline around the image.

Silhouettes

When you set the stencil mask to the same size and shape as the primitive you're rendering, Direct3D produces a final image containing a "black hole" where the primitive should be. By coloring this hole, you can produce a silhouette of the primitive.

Swipes

A swipe makes an image appear as though it's sliding into the scene over another image. You can use stencil masks to disable the writing of pixels from the starting image and enable the writing of pixels from the ending image. To perform a swipe, you can define a series of stencil masks that Direct3D will load into the stencil buffer in a succession of frames, or you can change the starting stencil mask for a series of successive frames. Both methods cause the final image to look as though it's gradually sliding on top of the starting image from right to left, left to right, top to bottom, and so on.

To handle a swipe, remember to read the pixels from the ending image in the reverse order in which you're performing the swipe. For example, if you're performing a swipe from left to right, you need to read pixels from the ending image from right to left. As with dissolves, this effect can render somewhat slowly. Therefore, you should test its performance on your target systems.

Shadows

Shadow volumes, which allow an arbitrarily shaped object to cast a shadow onto another arbitrarily shaped object, can produce some incredibly realistic effects. To create shadows with stencil buffers, take an object you want to cast a shadow. Using this object and the light source, build a set of polygonal faces (a shadow volume) to represent the shadow.

You can compute the shadow volume by projecting the vertices of the shadow-casting object onto a plane that's perpendicular to the direction of light from the light source, finding the 2D convex hull of the projected vertices (that is, a polygon that "wraps around" all the projected vertices), and extruding the 2D convex hull in the light direction to form the 3D shadow volume. The shadow volume must extend far enough so that it covers any objects that will be shadowed. To simplify computation, you might want the shadow caster to be a convex object.

To render a shadow, you must first render the geometry and then render the shadow volume without writing to the depth buffer or the color buffer. Use alpha blending to avoid having to write to the color buffer. Each place that the shadow volume appears will be marked in the stencil buffer. You can then reverse the cull and render the backfaces of the shadow volume, unmarking all the pixels that are covered in the stencil buffer. All these pixels will have passed the z-test, so they'll be visible behind the shadow volume. Therefore, they won't be in shadow. The pixels that are still marked are the ones lying inside the front and back boundaries of the shadow volume-these pixels will be in shadow. You can blend these pixels with a large black rectangle that covers the viewport to generate the shadow.

The ShadowVol and ShadowVol2 Demos

The ShadowVol sample on the companion CD in the \mssdk\Samples\Multimedia\D3dim\Src\ShadowVol directory contains a project that shows how to create and use stencil buffers to implement shadow volumes. The code illustrates how to use shadow volumes to cast the shadow of an arbitrarily shaped object onto another arbitrarily shaped object. The ShadowVol2 sample, which the Microsoft DirectX 7 SDK setup program on the companion CD installs in the \mssdk\Samples\Multimedia\D3dim\Src\ShadowVol2 directory on your hard disk, provides some additional capabilities for producing shadows with stencils.

The sample application provides these features in its Shadow Modes menu:

• Draw Shadows: Allows you to turn on and off shadow rendering.
  
  
• Show Shadow Volumes: Draws the shadow volumes used to compute the shadows rather than drawing the shadows themselves.
  
  
• Draw Shadow Volume Caps: When you turn this item off, some "extra" shadows might become visible where the far caps of the cylindrical shadow volumes happen to be visible.
  
  
• 1-Bit Stencil Buffer Mode: Tells the code to use a different algorithm that uses only 1 bit of stencil buffer, which won't allow overlapping shadows. If the device supports only 1-bit stencils, you'll be forced to use this mode.
  
  
• Z-Order Shadow Vols in 1-Bit Stencil Buffer Mode: The shadow volumes must be rendered front to back, which means that if you don't check this option, rendering might be incorrect.

<<"F12xi01.eps">>

Figure 12-1. Shadow cast

<<"F12xi02.eps">>

Figure 12-2. Shadow volumes

<<"F12xi03.eps">>

Figure 12-3. Another view of the rendered shadows

The Code So Far

In this chapter, we didn't add any new code to the RoadRage project. To see these effects in action, refer to the ShadowVol and ShadowVol2 demo projects included in the DirectX samples.

Conclusion

In this chapter, you learned about stencil buffers and the exciting effects they can produce. In today's market, making your code stand out is a requisite if you want it to sell your applications and keep your users coming back for more. Incorporating strategic stencil-buffer effects into the introduction and into the body of a 3D real-time game might help you win over even the most discriminating game players.

In Chapter 13, we'll discuss how to load and animate 3D models. Creating animated, lifelike characters that your users can interact with is one of the most powerful capabilities you can add to any game.

Peter Kovach has been involved in computer software and hardware development since the mid-1970s. After 11 years in various levels of development and project management, he was eager to being pushing the envelope in 3D virtual world development. He currently words at Medtronic, where he is the project lead developming programmable, implantable medical devices that use a next-generation graphical user interface.

Collision detection

From Wikipedia, the free encyclopedia

Jump to: navigation, search

For collision detection on networks see CSMA/CD

In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given solids. Simulating what happens once a collision is detected is sometimes referred to as "collision response", for which see physics engine and ragdoll physics. Collision detection algorithms are a basic component of 3D video games. Without them, characters could go through walls and other obstacles.

Contents [hide] 1 Overview 2 Collision detection in physical simulation 2.1 A posteriori versus a priori 3 Optimization 3.1 Exploiting temporal coherence 3.2 Pairwise pruning 3.3 Exact pairwise collision detection 3.4 A priori pruning 3.5 Spatial partitioning 4 Video games 5 Open Source Collision Detection 6 References 7 See also 8 External links

[edit] Overview

Billiards balls hitting each other are a classic example applicable within the science of collision detection.

In physical simulation, we wish to conduct experiments, such as playing billiards. The physics of bouncing billiard balls are well understood, under the umbrella of rigid body motion and elastic collisions. An initial description of the situation would be given, with a very precise physical description of the billiard table and balls, as well as initial positions of all the balls. Given a certain impulsion on the cue ball (probably resulting from a player hitting the ball with his cue stick), we want to calculate the trajectories, precise motion, and eventual resting places of all the balls with a computer program. A program to simulate this game would consist of several portions, one of which would be responsible for calculating the precise impacts between the billiard balls. This particular example also turns out to be numerically unstable: a small error in any calculation will cause drastic changes in the final position of the billiard balls.

Video games have similar requirements, with some crucial differences. While physical simulation needs to simulate real-world physics as precisely as possible, video games need to simulate real-world physics in an acceptable way, in real time and robustly. Compromises are allowed, so long as the resulting simulation is satisfying to the game player.

[edit] Collision detection in physical simulation

Physical simulators differ in the way they react on a collision. Some use the softness of the material to calculate a force, which will resolve the collision in the following time steps like it is in reality. Due to the low softness of some materials this is very CPU intensive. Some simulators estimate the time of collision by linear interpolation, roll back the simulation, and calculate the collision by the more abstract methods of conservation laws.

Some iterate the linear interpolation (Newton's method) to calculate the time of collision with a much higher precision than the rest of the simulation. Collision detection utilizes time coherence to allow ever finer time steps without much increasing CPU demand, such as in air traffic control.

After an inelastic collision, special states of sliding and resting can occur and, for example, the Open Dynamics Engine uses constrains to simulate them. Constrains avoid inertia and thus instability. Implementation of rest by means of a scene graph avoids drift.

In other words, physical simulators usually function one of two ways, where the collision is detected a posteriori (after the collision occurs) or a priori (before the collision occurs). In addition to the a posteriori and a priori distinction, almost all modern collision detection algorithms are broken into a hierarchy of algorithms.

[edit] A posteriori versus a priori

In the a posteriori case, we advance the physical simulation by a small time step, then check if any objects are intersecting, or are somehow so close to each other that we deem them to be intersecting. At each simulation step, a list of all intersecting bodies is created, and the positions and trajectories of these objects are somehow "fixed" to account for the collision. We say that this method is a posteriori because we typically miss the actual instant of collision, and only catch the collision after it has actually happened.

In the a priori methods, we write a collision detection algorithm which will be able to predict very precisely the trajectories of the physical bodies. The instants of collision are calculated with high precision, and the physical bodies never actually interpenetrate. We call this a priori because we calculate the instants of collision before we update the configuration of the physical bodies.

The main benefits of the a posteriori methods are as follows. In this case, the collision detection algorithm need not be aware of the myriad physical variables; a simple list of physical bodies is fed to the algorithm, and the program returns a list of intersecting bodies. The collision detection algorithm doesn't need to understand friction, elastic collisions, or worse, nonelastic collisions and deformable bodies. In addition, the a posteriori algorithms are in effect one dimension simpler than the a priori algorithms. Indeed, an a priori algorithm must deal with the time variable, which is absent from the a posteriori problem.

On the other hand, a posteriori algorithms cause problems in the "fixing" step, where intersections (which aren't physically correct) need to be corrected. In fact, there are some^[who?] who believe that such an algorithm is inherently flawed and unstable^{[citation needed]}.

The benefits of the a priori algorithms are increased fidelity and stability. It is difficult (but not completely impossible) to separate the physical simulation from the collision detection algorithm. However, in all but the simplest cases, the problem of determining ahead of time when two bodies will collide (given some initial data) has no closed form solution -- a numerical root finder is usually involved.

Some objects are in resting contact, that is, in collision, but neither bouncing off, nor interpenetrating, such as a vase resting on a table. In all cases, resting contact requires special treatment: If two objects collide (a posteriori) or slide (a priori) and their relative motion is below a threshold, friction becomes stiction and both objects are arranged in the same branch of the scene graph; however, some believe that it poses special problems in a posteriori algorithm^{[citation needed]}.

[edit] Optimization

The obvious approaches to collision detection for multiple objects are very slow. Checking every object against every other object will, of course, work, but is too inefficient to be used when the number of objects is at all large. Checking objects with complex geometry against each other in the obvious way, by checking each face against each other face, is itself quite slow. Thus, considerable research has been applied to speeding up the problem.

[edit] Exploiting temporal coherence

In many applications, the configuration of physical bodies from one time step to the next changes very little. Many of the objects may not move at all. Algorithms have been designed so that the calculations done in a preceding time step can be reused in the current time step, resulting in faster algorithms.

At the coarse level of collision detection, the objective is to find pairs of objects which might potentially intersect. Those pairs will require further analysis. An early high performance algorithm for this was developed by M. C. Lin at U.C. Berkley [1], who suggested using axis-aligned bounding boxes for all n bodies in the scene.

Each box is represented by the product of three intervals (i.e., a box would be .) A common algorithm for collision detection of bounding boxes is sweep and prune. We observe that two such boxes, and intersect if, and only if, I₁ intersects J₁, I₂ intersects J₂ and I₃ intersects J₃. We suppose that, from one time step to the next, I_k and J_k intersect, then it is very likely that at the next time step, they will still intersect. Likewise, if they did not intersect in the previous time step, then they are very likely to continue not to.

So we reduce the problem to that of tracking, from frame to frame, which intervals do intersect. We have three lists of intervals (one for each axis) and all lists are the same length (since each list has length n, the number of bounding boxes.) In each list, each interval is allowed to intersect all other intervals in the list. So for each list, we will have an matrix M = (m_ij) of zeroes and ones: m_ij is 1 if intervals i and j intersect, and 0 if they do not intersect.

By our assumption, the matrix M associated to a list of intervals will remain essentially unchanged from one time step to the next. To exploit this, the list of intervals is actually maintained as a list of labeled endpoints. Each element of the list has the coordinate of an endpoint of an interval, as well as a unique integer identifying that interval. Then, we sort the list by coordinates, and update the matrix M as we go. It's not so hard to believe that this algorithm will work relatively quickly if indeed the configuration of bounding boxes does not change significantly from one time step to the next.

In the case of deformable bodies such as cloth simulation, it may not be possible to use a more specific pairwise pruning algorithm as discussed below, and an n-body pruning algorithm is the best that can be done.

If an upper bound can be placed on the velocity of the physical bodies in a scene, then pairs of objects can be pruned based on their initial distance and the size of the time step.

[edit] Pairwise pruning

Once we've selected a pair of physical bodies for further investigation, we need to check for collisions more carefully. However, in many applications, individual objects (if they are not too deformable) are described by a set of smaller primitives, mainly triangles. So now, we have two sets of triangles, and (for simplicity, we will assume that each set has the same number of triangles.)

The obvious thing to do is to check all triangles S_j against all triangles T_k for collisions, but this involves n² comparisons, which is highly inefficient. If possible, it is desirable to use a pruning algorithm to reduce the number of pairs of triangles we need to check.

The most widely used family of algorithms is known as the hierarchical bounding volumes method. As a preprocessing step, for each object (in our example, S and T) we will calculate a hierarchy of bounding volumes. Then, at each time step, when we need to check for collisions between S and T, the hierarchical bounding volumes are used to reduce the number of pairs of triangles under consideration. For the sake of simplicity, we will give an example using bounding spheres, although it has been noted that spheres are undesirable in many cases.^{[citation needed]}

If E is a set of triangles, we can precalculate a bounding sphere B(E). There are many ways of choosing B(E), we only assume that B(E) is a sphere that completely contains E and is as small as possible.

Ahead of time, we can compute B(S) and B(T). Clearly, if these two spheres do not intersect (and that is very easy to test,) then neither do S and T. This is not much better than an n-body pruning algorithm, however.

If is a set of triangles, then we can split it into two halves and . We can do this to S and T, and we can calculate (ahead of time) the bounding spheres B(L(S)),B(R(S)) and B(L(T)),B(R(T)). The hope here is that these bounding spheres are much smaller than B(S) and B(T). And, if, for instance, B(S) and B(L(T)) do not intersect, then there is no sense in checking any triangle in S against any triangle in L(T).

As a precomputation, we can take each physical body (represented by a set of triangles) and recursively decompose it into a binary tree, where each node N represents a set of triangles, and its two children represent L(N) and R(N). At each node in the tree, as a we can precompute the bounding sphere B(N).

When the time comes for testing a pair of objects for collision, their bounding sphere tree can be used to eliminate many pairs of triangles.

Many variants of the algorithms are obtained by choosing something other than a sphere for B(T). If one chooses axis-aligned bounding boxes, one gets AABBTrees. Oriented bounding box trees are called OBBTrees. Some trees are easier to update if the underlying object changes. Some trees can accommodate higher order primitives such as splines instead of simple triangles.

[edit] Exact pairwise collision detection

Once we're done pruning, we are left with a number of candidate pairs to check for exact collision detection.

A basic observation is that for any two convex objects which are disjoint, one can find a plane in space so that one object lies completely on one side of that plane, and the other object lies on the opposite side of that plane. This allows the development of very fast collision detection algorithms for convex objects.

Early work in this area involved "separating plane" methods. Two triangles collide essentially only when they can not be separated by a plane going through three vertices. That is, if the triangles are v₁,v₂,v₃ and v₄,v₅,v₆ where each v_j is a vector in , then we can take three vertices, v_i,v_j,v_k, find a plane going through all three vertices, and check to see if this is a separating plane. If any such plane is a separating plane, then the triangles are deemed to be disjoint. On the other hand, if none of these planes are separating planes, then the triangles are deemed to intersect. There are twenty such planes.

If the triangles are coplanar, this test is not entirely successful. One can either add some extra planes, for instance, planes that are normal to triangle edges, to fix the problem entirely. In other cases, objects that meet at a flat face must necessarily also meet at an angle elsewhere, hence the overall collision detection will be able to find the collision.

Better methods have since been developed. Very fast algorithms are available for finding the closest points on the surface of two convex polyhedral objects. Early work by M. C. Lin ^[1] used a variation on the simplex algorithm from linear programming. The Gilbert-Johnson-Keerthi distance algorithm has superseded that approach. These algorithms approach constant time when applied repeatedly to pairs of stationary or slow-moving objects, when used with starting points from the previous collision check.

The end result of all this algorithmic work is that collision detection can be done efficiently for thousands of moving objects in real time on typical personal computers and game consoles.

[edit] A priori pruning

Where most of the objects involved are fixed, as is typical of video games, a priori methods using precomputation can be used to speed up execution.

Pruning is also desirable here, both n-body pruning and pairwise pruning, but the algorithms must take time and the types of motions used in the underlying physical system into consideration.

When it comes to the exact pairwise collision detection, this is highly trajectory dependent, and one almost has to use a numerical root-finding algorithm to compute the instant of impact.

As an example, consider two triangles moving in time v₁(t),v₂(t),v₃(t) and v₄(t),v₅(t),v₆(t). At any point in time, the two triangles can be checked for intersection using the twenty planes previously mentioned. However, we can do better, since these twenty planes can all be tracked in time. If P(u,v,w) is the plane going through points u,v,w in then there are twenty planes P(v_i(t),v_j(t),v_k(t)) to track. Each plane needs to be tracked against three vertices, this gives sixty values to track. Using a root finder on these sixty functions produces the exact collision times for the two given triangles and the two given trajectory. We note here that if the trajectories of the vertices are assumed to be linear polynomials in t then the final sixty functions are in fact cubic polynomials, and in this exceptional case, it is possible to locate the exact collision time using the formula for the roots of the cubic. Some numerical analysts suggest that using the formula for the roots of the cubic is not as numerically stable as using a root finder for polynomials.^{[citation needed]}

[edit] Spatial partitioning

Alternative algorithms are grouped under the spatial partitioning umbrella, which includes octrees, binary space partitioning (or BSP trees) and other, similar approaches. If one splits space into a number of simple cells, and if two objects can be shown not to be in the same cell, then they need not be checked for intersection. Since BSP trees can be precomputed, that approach is well suited to handling walls and fixed obstacles in games. These algorithms are generally older than the algorithms described above.

[edit] Video games

Video games have to split their very limited computing time between several tasks. Despite this resource limit, and the use of relatively primitive collision detection algorithms, programmers have been able to create believeable, if inexact, systems for use in games.

For a long time, video games had a very limited number of objects to treat, and so checking all pairs was not a problem. In two-dimensional games, in some cases, the hardware was able to efficiently detect and report overlapping pixels between sprites on the screen. In other cases, simply tiling the screen and binding each sprite into the tiles it overlaps provides sufficient pruning, and for pairwise checks, bounding rectangles or circles are used and deemed sufficiently accurate.

Three dimensional games have used spatial partitioning methods for n-body pruning, and for a long time used one or a few spheres per actual 3D object for pairwise checks. Exact checks are very rare, except in games attempting to simulate reality closely. Even then, exact checks are not necessarily used in all cases.

Because games use simplified physics, stability is not as much of an issue.^{[citation needed]} Almost all games use a posteriori collision detection, and collisions are often resolved using very simple rules. For instance, if a character becomes embedded in a wall, he might be simply moved back to his last known good location. Some games will calculate the distance the character can move before getting embedded into a wall, and only allow him to move that far.

A slightly more sophisticated and striking effect is ragdoll physics. If a video game character is disabled, instead of playing a preset animation, a simplified skeleton of the character is animated as if it were a rag doll. This rag doll falls limp, and might collide with itself and the environment, in which case it should behave appropriately.

In many cases for video games, approximating the characters by a point is sufficient for the purpose of collision detection with the environment. In this case, binary space partition trees provide a viable, efficient and simple algorithm for checking if a point is embedded in the scenery or not. Such a data structure can also be used to handle "resting position" situation gracefully when a character is running along the ground. Collisions between characters, and collisions with projectiles and hazards, are treated separately.

A robust simulator is one that will react to any input in a reasonable way. For instance, if we imagine a high speed racecar video game, from one simulation step to the next, it is conceivable that the cars would advance a substantial distance along the race track. If there is a shallow obstacle on the track (such as a brick wall), it is not entirely unlikely that the car will completely leap over it, and this is very undesirable. In other instances, the "fixing" that the a posteriori algorithms require isn't implemented correctly, and characters find themselves embedded in walls, or falling off into a deep black void. These are the hallmarks of a mediocre collision detection and physical simulation system.

[edit] Open Source Collision Detection

• GJKD A 2D implementation of the Gilbert-Johnson-Keerthi (GJK) algorithm, written in D.
• MPR2D A 2D implementation of the Minkowski Portal Refinement (MPR) Algorithm, written in D.

[edit] References

1. ^ Lin, Ming C. "Efficient Collision Detection for Animation and Robotics (thesis)". University of California, Berkeley.

[edit] See also

• Bounding volume
• Game physics
• Gilbert–Johnson–Keerthi distance algorithm
• Physics engine
• Ragdoll physics

[edit] External links

• University of California, Berkeley collision detection research web site
• Prof. Steven Cameron (Oxford University) web site on collision detection
• How to Avoid a Collision by George Beck, The Wolfram Demonstrations Project.
• Basic collision detection in OpenGL.

Retrieved from "http://en.wikipedia.org/wiki/Collision_detection"

Bounding volume

From Wikipedia, the free encyclopedia

  (Redirected from K-DOP)

Jump to: navigation, search

A bounding box for a three dimensional model

For building code compliance, see Bounding.

In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operations by using simple volumes to contain more complex objects. Normally, simpler volumes have simpler ways to test for overlap.

A bounding volume for a set of objects is also a bounding volume for the single object consisting of their union, and the other way around. Therefore it is possible to confine the description to the case of a single object, which is assumed to be non-empty and bounded (finite).

Contents [hide] 1 Uses of bounding volumes 2 Common types of bounding volume 3 Basic intersection checks 4 See also 5 External links

[edit] Uses of bounding volumes

Bounding volumes are most often used to accelerate certain kinds of tests.

In ray tracing, bounding volumes are used in ray-intersection tests, and in many rendering algorithms, they are used for viewing frustum tests. If the ray or viewing frustum does not intersect the bounding volume, it cannot intersect the object contained in the volume. These intersection tests produce a list of objects that must be displayed. Here, displayed means rendered or rasterized.

In collision detection, when two bounding volumes do not intersect, then the contained objects cannot collide, either.

Testing against a bounding volume is typically much faster than testing against the object itself, because of the bounding volume's simpler geometry. This is because an 'object' is typically composed of polygons or data structures that are reduced to polygonal approximations. In either case, it is computationally wasteful to test each polygon against the view volume if the object is not visible. (Onscreen objects must be 'clipped' to the screen, regardless of whether their surfaces are actually visible.)

To obtain bounding volumes of complex objects, a common way is to break the objects/scene down using a scene graph or more specifically bounding volume hierarchies like e.g. OBB trees. The basic idea behind this is to organize a scene in a tree-like structure where the root comprises the whole scene and each leaf contains a smaller subpart.

[edit] Common types of bounding volume

The choice of the type of bounding volume for a given application is determined by a variety of factors: the computational cost of computing a bounding volume for an object, the cost of updating it in applications in which the objects can move or change shape or size, the cost of determining intersections, and the desired precision of the intesection test. It is common to use several types in conjunction, such as a cheap one for a quick but rough test in conjunction with a more precise but also more expensive type.

The types treated here all give convex bounding volumes. If the object being bounded is known to be convex, this is not a restriction. If non-convex bounding volumes are required, an approach is to represent them as a union of a number of convex bounding volumes. Unfortunately, intersection tests become quickly more expensive as the bounding boxes become more sophisticated.

A bounding sphere is a sphere containing the object. In 2-D graphics, this is a circle. Bounding spheres are represented by centre and radius. They are very quick to test for collision with each other: two spheres intersect when the distance between their centres does not exceed the sum of their radii. This makes bounding spheres appropriate for objects that can move in any number of dimensions.

A bounding ellipsoid is an ellipsoid containing the object. Ellipsoids usually provide tighter fitting than a sphere. Intersections with ellipsoids are done by scaling the other object along the principal axes of the ellipsoid by an amount equal to the multiplicative inverse of the radii of the ellipsoid, thus reducing the problem to intersecting the scaled object with a unit sphere. Care should be taken to avoid problems if the applied scaling introduces skew. Skew can make the usage of ellipsoids impractical in certain cases, for example collision between two arbitrary ellipsoids.

A bounding cylinder is a cylinder containing the object. In most applications the axis of the cylinder is aligned with the vertical direction of the scene. Cylinders are appropriate for 3-D objects that can only rotate about a vertical axis but not about other axes, and are otherwise constrained to move by translation only. Two vertical-axis-aligned cylinders intersect when, simultaneously, their projections on the vertical axis intersect – which are two line segments – as well their projections on the horizontal plane – two circular disks. Both are easy to test. In video games, bounding cylinders are often used as bounding volumes for people standing upright.

A bounding capsule is a swept sphere (i.e. the volume that a sphere takes as it moves along a straight line segment) containing the object. Capsules can be represented by the radius of the swept sphere and the segment that the sphere is swept across). It has traits similar to a cylinder, but is easier to use, because the intersection test is simpler. A capsule and another object intersect if the distance between the capsule's defining segment and some feature of the other object is smaller than the capsule's radius. For example, two capsules intersect if the distance between the capsules' segments is smaller than the sum of their radii. This holds for arbitrarily rotated capsules, which is why they're more appealing than cylinders in practice.

A bounding box is a cuboid, or in 2-D a rectangle, containing the object. In dynamical simulation, bounding boxes are preferred to other shapes of bounding volume such as bounding spheres or cylinders for objects that are roughly cuboid in shape when the intersection test needs to be fairly accurate. The benefit is obvious, for example, for objects that rest upon other, such as a car resting on the ground: a bounding sphere would show the car as possibly intersecting with the ground, which then would need to be rejected by a more expensive test of the actual model of the car; a bounding box immediately shows the car as not intersecting with the ground, saving the more expensive test.

In many applications the bounding box is aligned with the axes of the co-ordinate system, and it is then known as an axis-aligned bounding box (AABB). To distinguish the general case from an AABB, an arbitrary bounding box is sometimes called an oriented bounding box (OBB). AABBs are much simpler to test for intersection than OBBs, but have the disadvantage that when the model is rotated they cannot be simply rotated with it, but need to be recomputed.

A minimum bounding rectangle or MBR – the least AABB in 2-D – is frequently used in the description of geographic (or "geospatial") data items, serving as a simplified proxy for a dataset's spatial extent (see geospatial metadata) for the purpose of data search (including spatial queries as applicable) and display. It is also a basic component of the R-tree method of spatial indexing.

A discrete oriented polytope (DOP) generalizes the AABB. A DOP is a convex polytope containing the object (in 2-D a polygon; in 3-D a polyhedron), constructed by taking a number of suitably oriented planes at infinity and moving them until they collide with the object. The DOP is then the convex polytope resulting from intersection of the half-spaces bounded by the planes. Popular choices for constructing DOPs in 3-D graphics include the axis-aligned bounding box, made from 6 axis-aligned planes, and the beveled bounding box, made from 10 (if beveled only on vertical edges, say) 18 (if beveled on all edges), or 26 planes (if beveled on all edges and corners). A DOP constructed from k planes is called a k-DOP; the actual number of faces can be less than k, since some can become degenerate, shrunk to an edge or a vertex.

A convex hull is the smallest convex volume containing the object. If the object is the union of a finite set of points, its convex hull is a polytope, and in fact the smallest possible containing polytope.

[edit] Basic intersection checks

For some types of bounding volume (OBB and convex polyhedra), an effective check is that of the separating axis theorem. The idea here is that, if there exists an axis by which the objects do not overlap, then the objects do not intersect. Usually the axes checked are those of the basic axes for the volumes (the unit axes in the case of an AABB, or the 3 base axes from each OBB in the case of OBBs). Often, this is followed by also checking the cross-products of the previous axes (one axis from each object).

In the case of an AABB, this tests becomes a simple set of overlap tests in terms of the unit axes. For an AABB defined by M,N against one defined by O,P they do not intersect if (M_x>P_x) or (O_x>N_x) or (M_y>P_y) or (O_y>N_y) or (M_z>P_z) or (O_z>N_z).

An AABB can also be projected along an axis, for example, if it has edges of length L and is centered at C, and is being projected along the axis N:
, and or , and where m and n are the minimum and maximum extents.

An OBB is similar in this respect, but is slightly more complicated. For an OBB with L and C as above, and with I, J, and K as the OBB's base axes, then: