Hidden Surface Removal

Hidden Surface Removal

Background
The topic of 3D graphics appears frequently. The publics desire for high quality 3D entertainment, such as video games, has driven the development of fast, real-time rendering systems. The hardware developers have created some amazing graphics cards that can render a blistering 25 million triangles per second. These advancements have made the software developer’s job somewhat easier. But even with the new hardware capability there is still a need for advanced rendering algorithms. The responsibility of a rendering engine is to allow for large world spaces and as the world’s size approaches infinity the engine should not slow down but remain at constant speed. This is where the extremely important topic of hidden surface removal comes in and will be the focus of this review.

Criteria
The criteria used for research material selection was that it had to contain information on hidden surface removal specific to 3D environments. I choose to pick quality articles that gave a good overview of an algorithm. This means that many articles were redundant, so the best one was selected and summarized. Articles that had redundant information but provided and extra insight or idea was included but only the new information was summarized. The reader is expected to have some understanding of software development and 3D in general. For general 3D knowledge the reader should of at least played some type of 3D game such as Quake.

Reviews

Simmons, Binary Space Partitioning Tutorial.
Binary Space partitioning has been around for along time but it became extremely popular when people found out that the developers of Quake and Doom used this algorithm to perform hidden surface removal and world rendering. It is still used today by most first person shooter games. During development a decision must be made on how world geometry will be rendered. The geometry or polygons must be rendered from back to front. In other words, the polygon that is the farthest away from the user will be drawn first and the polygon that is closest to the user will be drawn last. This must be done ever frame. The reason is that blended objects will not look right if this ordering is off. An average Quake level might have 10–20 thousand polygons. You could sort the order of all polygons each frame but you might as well take a smoke break before you move your character forward one step. And if 2 polygons overlap it is not clear which is in front or back so the simple sort wouldn’t work anyway. Also a 3D engine must perform collision detection to see if the user has run into any walls. Well if the polygons are not sorted you will have to test each one to see if there is a hit. So now you better go buy a cup of coffee to have with your smoke. This is just too slow. That is why a Binary Space Partition (BSP tree) algorithm was developed. The basic idea behind a BSP tree is a binary tree where each node contains a polygon and a pointer to a backlist and a pointer to a front list. So pick a polygon, call it the splitter and test all other polygons against it. If a polygon is in front of the splitter put it in the splitters front list, the back, send it to the backlist. If a polygon is both in front and in back of a splitter then split it in into 2 new polygons where by the back and front relationship will be created. If two polygons are parallel or in the same plane then they can be combined or the node can contain a list of polygons along with the front and back pointers. This process is continued until every polygon has it’s own node.

A BSP tree can solve all polygon order problems and even more importantly, it can be used to cull away geometry that is not currently visible. While rendering, a test can be performed if a polygon is behind the frustum then all of the geometry connected by its back pointer can be culled or not drawn. Also you can perform much fewer collision detection tests due to the ordering properties of a BSP tree. Since the BSP tree is built at compile time it is fast at render time.

Perez, Peeking Through Portals.

BSP trees are not an answer to everything. For instance, they are really only good for static scenes. Because a BSP is pre-built it is difficult to update them with dynamic moving polygons. Also there is not built in occlusion culling. An example of occlusion culling would be standing somewhere in the basement of a house and only being able to see the stairs leading up. The rooms upstairs are not visible so there is no need to render them. Quake used something called a PVS (potential visibility set) incorporated with a BSP tree. But a PVS really is a concept belonging to portal rendering.

Portal rendering, an alternative to BSP trees, has been around since 1971. It is now used in all kinds of games, like Descent, Unreal and Duke Nukem 3D just to name a few.

The concept is simple: if you are drawing two rooms that are connected by a doorway, drawing the room that you are currently in and then restrict drawing to the dimensions of the doorway for the second room. This leads to zero overdraw. The stipulation here is that the world must be a collection of convex hulls that are connected by portal polygons. A convex hull is a set of polygons with no concavities. It has the property that if you draw a line from anywhere inside the hull you cannot escape it. A cube is a good example of a convex hull. Then to render the world just draw the current cell and when a portal is encountered, recurs into its joining cell clipping the new portal with the current portal until you cannot see anymore portals.

Some other advantages besides zero over draw is that it is easy to have dynamic scenes. This leads to all kinds of cool effects. A real time mirror can be achieved fairly easily. Instead of a portal, mark a polygon as a portal-mirror. Then instead of recursing into it’s joining cell you recurs back into the original cell but rendering with a reflected camera/frustum. This can produce a cool effect and to make it really stunning you can make light reflex off of the mirror. Using some similar techniques to the mirror effect a warp can be achieved. This would be where a portal simply warps the user into a completely different section of the world. Or this effect can be used to create the security camera effect where the user can view what is going on in a far off room.

The draw back of a portal engine is that the clipping of portals is computationally expensive. So in large open rooms with lots of portals things can slow down tremendously. It is also difficult for a level editor or some other type of software tool to find where all the necessary portals need to go.

Sutter, Introduction to Octrees.

Hidden surface removal is the largest and most difficult problem in developing a 3D engine. The ideal engine would allow for infinite data, highly dynamic worlds and zero overdraw. There is no easy solution to this but the octree offers a simple approach that meets the ideal engine criteria at some level.

A 3D world is nothing more than a bunch of polygons. All of the polygons in a 3D world can be contained within a large cube. This cube can be split into 8 smaller cubes and in turn, each of these can be split into 8 smaller cubes. This can go on until some predefined minimum cube size is reached or the number of polygons inside a cube is smaller than some fixed amount. What this amounts to is a tree data structure where each node has a list of pointers to all polygons within its bounds (fully or partially) and it’s 8 children.

To render the tree simply recursively test a node (cube) against the view frustum. If a node is completely within the frustum, render all of it’s polygons, if partially inside the frustum recurs on each of it’s children and if it is completely outside the frustum it can be culled along with all of it’s children. This data structure also helps with some types of collision detection. For a sphere to plane collision test simply find the smallest node that the collision bounding sphere is contained within and you only need to check against that node’s polygon list.

Octrees offer up an easier implementation and better structure than a BSP tree. The key point is that when a parent is discarded so are all of its children.

Ginsburg, Octree Construction.

To perform fast collision testing a set of neighbors can be added to each node in the octree data structure. Each node will contain six neighbors, which correspond to the six cube faces of the node. A neighbor is defined as follows: the neighbor of a face must be the same size as the cube face or larger and it has to touch the face. The neighbors are added after the tree has been constructed. The algorithm should search for the best-fit neighbor of each cube, where the best fit is the smallest possible neighbor that is not smaller than the cube face. Now that each node has neighbors, collision detection can be performed without having to check all geometry in a large node. We will consider a ray collision test. Two points define a collision ray: a start and end point. To begin collision detection we find the leaf node of where the start point lies. The ray segment is broken into smaller sub segments at each cube face it intersects. The sub segment is then tested against all geometry within its node. This culls away large portions of geometry to make collision detection much faster.

The octree can also be used to keep track of dynamic information. Each node could contain a list of dynamic objects. As an object moves in the world it could attach and detach itself from nodes. The only trick here is that that objects could span multiple nodes so a flag would need to be used to make sure the object was only rendered once per frame.

Abrash, Consider the Alternatives: Quakes Hidden-Surface Removal.

The developers at id Software decided to use a BSP tree with a pre-calucated potentially visible set PVS for rendering. This algorithm along with some advanced optimizations led to fast rendering of static geometry. So they still had to deal with moving objects like the infamous BOT.

A moving object can span multiple leaves of a BSP tree. This destroys the front to back order built into the data structure. Since a BSP tree is out they decided to use an old simple technique called z buffering. This algorithm is fairly straightforward. When drawing a polygon every pixel is compared with the matching pixel currently on the screen and the new pixel is drawn only if it’s z value is less than the current pixel.

So all static geometry (walls, ceilings, floors, ect.) is draw first with the fast BSP/PVS algorithm then all moving objects are drawn using the slower z-buffer algorithm.

This worked because there were few moving objects as compared to static objects.

So the slow down of z buffering was acceptable.

Round, Object Occlusion Culling.

Occlusion culling provides a method for culling non-visible geometry. The geometry can be static or dynamic and the method works for indoor or outdoor scenes. The process is very similar to frustum culling.

Frustum culling is where you have six planes that form a bounding volume of the visible area. Then just take a bounding volume and compare it to the view frustum. If any part of the bounding volume is inside the view frustum then part, or all of the volume must be rendered.

Occlusion culling is almost identical to frustum culling. The difference is that the occlusion describes a hole. If the object is inside the occlusion volume it will not be rendered. An occlusion is created on the fly from a static occlusion plane. If an occlusion plane is determined to be inside the frustum then we create the bounding occlusion volume from the occlusion plane and the camera position information. Then all objects that fall into the frustum are tested against the occlusion. Also occlusions can be tested against each other to remove any occluded occlusion.

Occlusions can be used to cull objects, sounds and time-consuming effects like animation. Also, occlusions can be joined to form complex occlusion zones making them more efficient.

Conclusions

There are many different approaches to hidden surface removal, none of which can be characterized as being the best. The important thing is to determine the strengths and weaknesses of each approach. A BSP tree has several strengths. It gives you the polygons

in back to front order. This is important if you have translucent geometry or rendering is taking place in software. It can also provide HSR due to its ordering property and can be combined with a PVS or occlusion culling to make it perform much more effectively. The drawbacks are that it is difficult to implement. It requires the splitting of polygons. This splitting is going to make it difficult to develop a level editor because most likely some other type of core technology will have to be used in the editors rendering pipeline. Also this structure only works with static geometry.

The portal-rendering algorithm can provide for zero overdraw. It also can make for some nice special effects that would be difficult if not impossible in other approaches, collision detection can be minimized to the current sector geometry and it can handle dynamic objects. The problem with portals is that they only work for indoor scenes. A portal doesn’t make any sense in an outdoor view. Also, things can slow down in large rooms with lots of portals due to the computational complexity and difficulties arise when trying to determine where to place the portals in the scene. This could probably be overcome in some kind of editor but it makes for some extra coding.

The octree is a simple algorithm to construct. It is a nice easy to follow data structure that works well in indoor or outdoor scenes. It can be used to minimize collision-tested geometry and it can handle dynamic objects. The problem with the octree is that it provides no ordering information. This information is not needed with current graphics hardware and the absence of translucent geometry. Work arounds could be implemented to render translucent data accurately.

Occlusion culling is somewhat easy to construct and works for dynamic or static geometry. It could be used to complement the above algorithms but it isn’t really a stand-alone solution.

Recommendations

A recommended approach to engine design would be to decide what the engines capabilities will be. Will it have effects like warps? Will there be mostly indoor scenes, outdoor scenes or a combination of both? Will there be extensive amount of translucent geometry? After these questions have been answered an appropriate algorithm or combination of algorithms can be selected. Developers usually get creative and combine the above approaches into something that works for their required needs. For instance, you could have a portal engine in which each sector was stored as a BSP tree. This would provide the benefits of portals while allowing for translucent objects inside sectors, culling away individual sector geometry and providing in order collision detection. On the other hand you could quickly and accurately code up an octree and store any type of world.

Anything is possible. Just decide what functionality the engine must provide and the above algorithms, in some combination, should provide what is needed and then you can create the next Quake.

Reference List

Abrash, Michael “Consider Alternatives: Quake’s Hidden-Surface Removal” GameDev.

[Online] Available:

Accessed 10 December 2000).

Ginsburg, Dan. Game Programming Gems.

Rockland MA: Charles River Media Inc.,2000. 439-443

Perez, Adrian “Peeking Through Portals” Game Developer Magazine, march 1998.

[Online] Available:

Accessed 10 December 2000).

Round, Tim. Game Programming Gems.

Rockland MA: Charles River Media Inc.,2000. 421-425

Simmons, Gary “Binary Space Partitioning Tutorial” Mr-GameMaker, 1999.

[Online] Available:

Accessed 10 December 2000).

Suter, Jaap “Introduction to Octrees” Flip Code, 1999.

[Online] Available:

Accessed 10 December 2000).