MULTIMEDIA

# Programming with DirectX : Game Math - Bounding Geometry (part 1) - Bounding Boxes

2/26/2011 5:08:18 PM
##### Collision detection and response is a very important topic in 3D video games. Models and objects in a video game are usually made up of thousands of polygons. The environments themselves can be in the high thousands or millions of polygons. When detecting collision between triangles, the operation is usually a very CPU-expensive process, even for just a single triangle, let alone thousands upon thousands of them. What is needed is a way to quickly detect collisions between objects, along with other factors such as visibility determination. This is where bounding geometry comes into play. The idea behind bounding geometry is that the bounding geometry serves as a very simple representation of a more complex object. Bounding geometry is any simple shape that surrounds an object so that the object fits inside the bounding geometry’s volume as tightly as possible. These shapes include spheres, boxes, ellipsoids, and so forth. An example of a bounding box and sphere, the most common types of bounding geometry used, is shown in Figure 1. Figure 1. An example of a bounding box (left) and bounding sphere (right). The need to simplify various tests such as collision detection is extremely important in video games because everything has to run as efficiently and effectively as possible. This requires performing tests as fast as possible to avoid slowing down the CPU and to get the most out of the processing power of the machine. This is the purpose of using bounding geometry, which is significantly faster than working on the polygon level of models and objects. Mathematically, a box can be tested quickly for whether it is in view or is touching another box far faster than the triangles of a model, so using the simplified shape is a very fast substitution. The DirectX SDK includes functions to create a bounding box and bounding sphere around a piece of geometry. In this section we’ll discuss the DirectX bounding box and bounding sphere support. #### Bounding Boxes A box can be defined using two vectors, where the first vector stores the minimum X, Y, and Z values for the box and the second vector stores the maximum X, Y, and Z values. If you know the minimum X and maximum X, for example, you will be able to know where each of the box’s corners is along the X axis. If you also know the minimum and maximum Y and Z values, you can generate a box out of them. To test if a point or another object intersects (touches) the box, you can test if the point or object falls entirely within this minimum and maximum range that defines the bounding box. Looking at a 2D example, you can see that the object being tested falls within both the X and Y axes of the bounding box, meaning the object is inside of it. This is shown in Figure 2. Objects with volume, such as another box, touch the bounding box only if any part of it is on the surface of the bounding box or inside it. Figure 2. A 2D example of a point (left) and an object (right) falling within a box. A box can be any size along the width, height, and depth axes, which are defined by the two vectors that represent the box. A cube, on the other hand, is a box that has the same value for the width, height, and depth, forming a perfectly even shape along all axes. To represent a cube, you only need to know the center position and the size of the cube. This size is used for the width, height, and depth. To calculate the bounding box you can call the D3DXComputeBoundingBox() function. This function takes as parameters a list of points specified as D3DXVECTOR3 3D vectors, the total number of vertices in the list, the size of each vertex, and output addresses that will store the minimum and maximum values of the computed bounding box. The D3DXComputeBoundingBox() function has the following function prototype according to the DirectX SDK. `HRESULT D3DXComputeBoundingBox( CONST D3DXVECTOR3 *pFirstPosition, DWORD NumVertices, DWORD dwStride, D3DXVECTOR3 *pMin, D3DXVECTOR3 *pMax);` You can test if a ray hits the bounding box by calling the D3DXBoxBoundProbe() function. This function takes as parameters the minimum and maximum values of the bounding box, the position (origin) of the ray, and the direction vector of the ray. The function prototype for the D3DXBoxBoundProbe() function is as follows according to the DirectX SDK. `BOOL D3DXBoxBoundProbe( CONST D3DXVECTOR3 *pMin, CONST D3DXVECTOR3 *pMax, CONST D3DXVECTOR3 *pRayPosition, CONST D3DXVECTOR3 *pRayDirection);`
 Other

 Top 10
 -  Windows Server 2003 : Domain Name System - Command-Line Utilities
 -  Microsoft .NET : Design Principles and Patterns - From Principles to Patterns (part 2)
 -  Microsoft .NET : Design Principles and Patterns - From Principles to Patterns (part 1)
 -  Brother MFC-J4510DW - An Innovative All-In-One A3 Printer
 -  Computer Planet I7 Extreme Gaming PC
 -  All We Need To Know About Green Computing (Part 4)
 -  All We Need To Know About Green Computing (Part 3)
 -  All We Need To Know About Green Computing (Part 2)
 -  All We Need To Know About Green Computing (Part 1)
 -  Master Black-White Copying
 Most View
 -  Microsoft Tries To Flatten Competition With Surface (Part 3) - Dropbox drops Public Folders, SSD Prices Way Down, AMD Adopts Arm for Armor
 -  SQL Server 2008 R2 : Dropping Indexes, Online Indexing Operations, Indexes on Views
 -  NZXT Source 210 Elite - Finest Cases For Frugal Gamers
 -  OLED Me Be the One
 -  Toshiba Tecra R850
 -  Windows 8's Unexpected Features (Part 1)
 -  Computing Yourself Fit (Part 4)
 -  Crucial Ballistix Tactical LP 16GB Kit
 -  100 Windows Speed-Up Tips (Part 1) - Clean up your hard drive & Defrag your computer
 -  Organize Windows With Virtual Desktops
 -  Developing Applications for the Cloud on the Microsoft Windows Azure Platform : DNS Names, Certificates, and SSL in the Surveys Application
 -  Improve Your Mac (Part 2) - Add Music To You Movies
 -  LG Optimus L3 E400 Review (Part 1)
 -  Roku 2 XS