Abstract

Today’s 3D games consumers are expecting more and more quality in their computer games. To enable high quality graphics at interactive rates, games programmers employ a technique known as hidden surface removal (HSR) or polygon culling. HSR is not just applicable to games; it may also be applied to any application that requires quality and interactive rates, including medical, military and building applications. One such commonly used technique for HSR is the binary space partition (BSP) tree, which is used for 3D “walk-throughs”, otherwise known as 3D static environments or first person shooters. Recent developments in 3D accelerated hardware technology do not mean that HSR is becoming redundant; in fact, HSR is increasingly becoming more important to the graphics pipeline.

The well established potentially visible sets (PVS) BSP tree algorithm is used as a platform for exploring three enhancement algorithms: View Space Linking, Solid Node Compression and hardware accelerated occlusion. View Space Linking, Solid Node Compression and hardware accelerated occlusion are shown to reducing the amounts of nodes that are traversed in a BSP tree, improving tree traversal efficiency. These algorithms are proven (in cases) to improve overall effeiciency.

"View Space Linking, Solid Node Compression and Binary Space Partitioning for Visibility Determination in 3D Walk-Throughs" by Joel Anderson, Honors Thesis, Edith Cowan University, 269 Pages, Adobe Acrobat (7.05MB)