|
|
 |
 |
 | | | | |
 |
|||
 |
||||||
          |
 |
 |
||||
|
Rendering
the Great Outdoors: Node Volumes Every visual object in a scene hierarchy should have an asso-ciated bounding volume, so that with just a few math oper-ations, we’re able to say if each object is visible or not. As I mentioned previously, it wouldn’t be very efficient to test all the scene objects in each rendered frame. For example, in a racing game with 20 cars, you’d end up testing all the vehicle’s objects (wheels, doors, driver, driver’s fingers, and on and on) 20 times, which could easily make for upwards of 25 objects on each car multiplied by 20 cars. Why perform 25 tests when a single test for each car can accomplish the same result? With complex models or models used in a scene multiple times, finding a way to skip the processing of an entire model or models if they’re out of view would be highly desirable. For this reason, we’ll introduce a node bounding volume. This is the same bounding structure defined above, but it doesn’t enclose vertices; rather it encloses all bounding volumes of a group of objects, the child objects of the node (objects, models, and so on). Building and Maintaining Volumes Assuming you have static geometry, calculating a visual object’s extent is done once before starting rendering. The bounding box is axis-aligned (AABB) in the local coordinates of an object, defined by two extreme points of the box. Anytime a bounding box is used in computations, it must be transformed into world coordinates using the object’s transformation matrix, and thus changed to an oriented bounding box. Because OBBs cannot be specified by just two corner points, we’ll need to extract the two corner points of the AABB into the eight cor-ner points of the OBB, and transform all these points to world coordinates with the object’s transformation matrix (the same one that will be used to transform the object’s vertices to world coordinates). The bounding sphere is also in local coordinates, and must be transformed (position) and scaled (radius) to world coordinates before being used in computations. The situation with node bounding volumes is a bit more dif-ficult. Because the position of objects may change in real time, this bounding volume must be computed at run time whenever any object in the group moves. The best method is a lazy evalu-ation programming technique — in other words, computing the value when it’s needed. You may implement a system of invali-dation of a node’s bounding volume when the child’s matrix changes due to position, rotation, or scale. This system is hard-er to implement and debug, but it’s critical for fast 3D culling, both rendering and collision testing. By measurements I’ve made in our 3D system, the dynamic bounding volume update takes no more than 1 to 2 percent of total CPU time when the game is running. Convex Hull Computation Because it’s very easy to detect collision against it, a convex hull is another basic geometry object used in occlu-sion testing. During occlusion testing, we’ll detect a collision of a 3D point with a hull and a sphere with a hull. Since we must detect how the bounding volume of an object collides with viewing volumes (screen frustum and occlusion frustum), hidden-surface removal has much in common with collision detection. A hull is defined as a set of planes that forms the hull, with their normals pointing away from the hull. Any point in space is a part of the hull if it lies behind all the planes forming the hull. For our purposes, we’ll also use an open hull, which is a hull that represents an open 3D volume. All the information we need to compute the convex hull is a set of 3D points. During the computation, we’ll remove redun-dant points, which are inside the hull and do not lie on the skeleton of the hull. We’ll also need to compute the edge faces of the convex hull; these faces are not necessarily triangles, as they are in 3D meshes. We’ll utilize planes of these edge faces for our occlusion com-putations: for example, a fast check of whether a 3D point is inside of a convex hull. If a point in space is behind all the edge faces of the hull (assuming the planes’ normals point out from the hull), then it is inside of the hull (Listing 1).
Several algorithms exist for computing a convex hull from a set of points. Some commonly used ones include incremental, gift-wrapping, divide-and-conquer, and quick-hull. There is a nice Java applet demonstrating techniques of building convex hulls that is a good starting point for choosing and imple-menting the algorithm. It is available (with kind permission of its author) at www.cse.unsw.edu.au/~lambert/java/3d/hull.html. Speaking from my own experience, writing code for building convex hulls is quite a difficult task. Even when you implement the code properly, you’ll encounter problems with float-round-ing errors (using doubles won’t solve anything). Regardless of which algorithm you choose, with some point sets you’ll end up with hulls that are invalid after final validity checks are per-formed. Having multiple points placed close together on a plane is a common source of problems. After I struggled for months with code that computed it wrong, then spending another month writing my own convex-hull computation code, I finally switched to Qhull, a freeware package that utilizes the quick-hull algorithm. It’s available at www.geom.umn.edu/software/qhull. Although the QHull library is a robust, platform-independent package that can do many additional tasks, we will only be need-ing it to compute the convex hull using our structures. It handles rounding problems by joggling points; if computation fails, it shifts points randomly by a small value and recomputes until it gets a proper hull. If you decide to use this or any other available package, be prepared to spend a day or two reading its documentation and writing code to call it; you’ll save a month otherwise spent writing and debugging your own system. The final result we need after computation is a set of filtered points that form a skeleton of the hull, and a set of faces. Following is an example of what we get (faces are kept as indices in the point set):
struct S_vector{ Now we use the help of C++ STL vector class for storing our vertices and faces:
Note that when inserting into vector , a copy constructor of the class being inserted is called. Make sure you have imple-mented a copy constructor of S_face so that memory for indices is properly allocated and freed.
|
||||||||||||||
|
|
Features
