Conservative From-Point Visibility.
GUMMERUS, SAMPSA (2004)
2004
Tietojenkäsittelyoppi - Computer Science
Informaatiotieteiden tiedekunta - Faculty of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2004-05-12
Julkaisun pysyvä osoite on
http://urn.fi/urn:nbn:fi:uta-1-13031
http://urn.fi/urn:nbn:fi:uta-1-13031
Sisällysluettelo
1. Introduction.............................................................................................................1 2. Visibility Problem...................................................................................................3 3. Scene Organization...............................................................................................10 3.1. Bounding Volume Hierarchies and Scene Graphs.................................10 3.2. Spatial Data Structures ...............................................................................13 3.3. Regular Grids...............................................................................................14 3.4. Quadtrees and Octrees ...............................................................................15 3.5. KD-Trees.......................................................................................................20 3.6. BSP-Trees......................................................................................................23 3.7. Exploiting Spatial and Temporal Coherence ..........................................27 3.8. Dynamic Scenes...........................................................................................30 3.9. Summary ......................................................................................................34 4. View Frustum Culling .........................................................................................35 4.1. View Frustum Construction ......................................................................36 4.2. View Frustum Test......................................................................................37 4.3. Hierarchical View Frustum Culling .........................................................41 4.4. Optimizations ..............................................................................................42 4.5. Summary ......................................................................................................44 5. Occlusion Culling .................................................................................................45 5.1. Fundamental Concepts...............................................................................45 5.2. Occluder Selection.......................................................................................46 5.3. Hardware Occlusion Queries....................................................................49 5.4. Object-Space Methods ................................................................................50 5.5. Image-Space Methods ................................................................................55 5.6. Summary ......................................................................................................64 6. Conclusion.............................................................................................................66 References .................................................................................................................... 70
Tiivistelmä
Visibility determination has been an important part of the computer graphics
research for several decades. First studies of the visibility were hidden line
removal algorithms, and later hidden surface removal algorithms. Today’s
visibility determination is mainly concentrated on conservative, object level
visibility determination techniques. Conservative methods are used to
accelerate the rendering process when some exact visibility determination
algorithm is present. The Z-buffer is a typical exact visibility determination
algorithm. The Z-buffer algorithm is implemented in practically every modern
graphics chip.
This thesis concentrates on a subset of conservative visibility
determination techniques. These techniques are sometimes called from-point
visibility algorithms. They attempt to estimate a set of visible objects as seen
from the current viewpoint. These techniques are typically used with real-time
graphics applications such as games and virtual environments. Concentration is
on the view frustum culling and occlusion culling. View frustum culling
discards objects that are outside of the viewable volume. Occlusion culling
algorithms try to identify objects that are not visible because they are behind
some other objects. Also spatial data structures behind the efficient
implementations of view frustum culling and occlusion culling are reviewed.
Spatial data structure techniques like maintaining of dynamic scenes and
exploiting spatial and temporal coherences are reviewed.
research for several decades. First studies of the visibility were hidden line
removal algorithms, and later hidden surface removal algorithms. Today’s
visibility determination is mainly concentrated on conservative, object level
visibility determination techniques. Conservative methods are used to
accelerate the rendering process when some exact visibility determination
algorithm is present. The Z-buffer is a typical exact visibility determination
algorithm. The Z-buffer algorithm is implemented in practically every modern
graphics chip.
This thesis concentrates on a subset of conservative visibility
determination techniques. These techniques are sometimes called from-point
visibility algorithms. They attempt to estimate a set of visible objects as seen
from the current viewpoint. These techniques are typically used with real-time
graphics applications such as games and virtual environments. Concentration is
on the view frustum culling and occlusion culling. View frustum culling
discards objects that are outside of the viewable volume. Occlusion culling
algorithms try to identify objects that are not visible because they are behind
some other objects. Also spatial data structures behind the efficient
implementations of view frustum culling and occlusion culling are reviewed.
Spatial data structure techniques like maintaining of dynamic scenes and
exploiting spatial and temporal coherences are reviewed.