Computation of Bounding Primitives on the GPU
by Philip Rideout

Introduction

The axis-aligned bounding box, or AABB, can be represented as 6 planes:

struct AABB
{
   float Left;
   float Right;
   float Top;
   float Bottom;
   float Near;
   float Far;
};

struct AABB
{
   Vector3 MinCorner;
   Vector3 MaxCorner;
};

AABB aabb;
aabb.MinCorner = (MaxFloat, MaxFloat, MaxFloat);
aabb.MaxCorner = (-MaxFloat, -MaxFloat, -MaxFloat);
for each vertex in buffer
{
   aabb.MinCorner.x = Min(vertex.x, aabb.MinCorner.x);
   aabb.MinCorner.y = Min(vertex.y, aabb.MinCorner.y);
   aabb.MinCorner.z = Min(vertex.z, aabb.MinCorner.z);

   aabb.MaxCorner.x = Max(vertex.x, aabb.MaxCorner.x);
   aabb.MaxCorner.y = Max(vertex.y, aabb.MaxCorner.y);
   aabb.MaxCorner.z = Max(vertex.z, aabb.MaxCorner.z);
}

Naïve GPU Approach: Leverage the Depth Buffer

The divide-and-conquer philosophy tells us to approach the problem by solving its sub-problems first. It can be helpful to think about only one dimension at a time. If we can simply compute the near plane, then we should be able to compute the other five planes via transformations.

Finding the “nearest” point is something fundamental to real-time graphics. Anyone familiar with OpenGL or D3D knows that where there is 3D rendering, a depth buffer lurks beneath:

Note that we are interested in only one depth value, while the depth buffer represents many depth values. The trick is to render to a 1x1 viewport. It’s difficult to visualize rendering an entire model into a 1x1 area, so it may help to think of it as the end of a continuously shrinking viewport:

Aside: Depth Buffer Visualization with Direct3D 10 To produce a grayscale visualization of the depth buffer similar to the pictures in this article, one approach using D3D10 is the following: Create a texture that has a color format equivalent to the depth buffer format. For example, if the depth buffer is DXGI_FORMAT_D32_FLOAT, then the texture should have a format of DXGI_FORMAT_R32_FLOAT. The texture should have the same width and height as the render target. After rendering the scene as you normally would, un-bind the depth buffer by passing null into the last argument of ID3D10Device::OMSetRenderTargets(). Use ID3D10Device::CopyResource() to copy the values from the real depth buffer into the grayscale texture from step 1. Bind the grayscale texture to a pixel shader resource and draw it to the screen using a full-screen quad. An example of this procedure can be found in the sample code attached to this article.

Since the nearest point always trumps the points that render behind it, the depth buffer of our 1x1 render target should hold the nearest Z value. Computing values for the other five planes can be achieved by simply rotating the model appropriately:

There are some caveats to using the depth buffer in this way:

• Be sure to use a high-precision depth buffer. In the case of D3D10, use DXGI_FORMAT_D32_FLOAT when creating your depth texture. Remember that the viewport is only 1x1, so the performance implication of this is relatively unimportant.
• Because we are rendering to a 1x1 viewport, each triangle takes up a screen area that is only a fraction of a pixel. This can lead to rendering only one interior point per triangle, which results in an incorrect bounding box. To bypass this issue, use point primitives rather than triangles. In the case of D3D10, set your primitive topology to D3D10_PRIMITIVE_TOPOLOGY_POINTLIST.

To achieve this with D3D10, set your DepthFunc to GREATER_EQUAL rather than the default LESS. Also be sure to change your clear value appropriately. So, your effect file would change as follows:

DepthStencilState MyDepthState
{
   DepthEnable = TRUE;
   DepthFunc = LESS GREATER_EQUAL;
   DepthWriteMask = ALL;
};

device->ClearDepthStencilView(depthView, D3D10_CLEAR_DEPTH, 1 0, 0);

Exploit the Blending Hardware

DirectX 9	DirectX 10	OpenGL
D3DBLENDOP_ADD	D3D10_BLEND_OP_ADD	GL_FUNC_ADD
D3DBLENDOP_SUBTRACT	D3D10_BLEND_OP_SUBTRACT	GL_FUNC_SUBTRACT
D3DBLENDOP_REVSUBTRACT	D3D10_BLEND_OP_REV_SUBTRACT	GL_FUNC_REVERSE_SUBTRACT
D3DBLENDOP_MIN	D3D10_BLEND_OP_MIN	GL_MIN
D3DBLENDOP_MAX	D3D10_BLEND_OP_MAX	GL_MAX

Those last two rows should catch your eye!

Before we can use these blending operations, we should make sure that we’re rendering into a floating-point render target. In D3D10, this can be done with DXGI_FORMAT_R32G32B32A32_FLOAT. Despite the fact that we’re exploiting the hardware’s blending stage, we actually will not be using the alpha channel. We specify alpha in our format only because it is typically required by the API when specifying a render target. So, by simply writing X Y Z into our R G B channels while using MIN blending for the first pass, and MAX blending for the second pass, we can compute a complete bounding box! The D3D10 HLSL for this technique follows.

struct VS_OUTPUT
{
   float4 Position : SV_POSITION;
   float4 Pretransformed : POSITIONT;
};

VS_OUTPUT FindBoundsVS(float4 Position : POSITION)
{
   VS_OUTPUT Output;
   Output.Position = float4(0, 0, 0, 1);
   Output.Pretransformed = Position;
   return Output;    
}

float4 FindBoundsPS(VS_OUTPUT In)  : SV_TARGET
{ 
   return In.Pretransformed;
}

1. Create two floating-point 2x1 textures with the following parameters:
• BindFlags = RENDER_TARGET, CPUAccessFlags = 0, Usage = DEFAULT
• BindFlags = 0, CPUAccessFlags = READ, Usage = STAGING
2. Bind the output merger stage to the 2x1 render target texture.
3. Set the viewport to 1x1 with TopLeft at (0, 0).
4. Set the blending state to use BlendOp = MIN, SrcBlend = SRC_COLOR, DestBlend = DEST_COLOR.
5. Render the geometry using the pass-through shaders described above.
6. Move the viewport’s TopLeft to (1,0)
7. Change the BlendOp to MAX.
8. Render the geometry again.
9. Unbind the output merger stage from the 2x1 render target.
10. Call ID3D10Device::CopyResource() to copy data from the render target texture to the staging texture.
11. Call ID3D10Texture2D::Map() on the staging texture to read the values of the two corners from the color buffer.