Accelerated occlusion culling using shadow frusta
Published 1 January 1997
Tom Hudson, Dinesh Manocha, Jonathan Cohen, Ming C. Lin, K. Hoff, H. Zhang
Citations128
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A conservative culling stage is added to the rendering pipeline, attempting to identify and avoid processing of occluded polygons, and is applicable to all polygonal models, and can be easily implemented on top of view-frustum culling.
Abstract
: Many applications in computer graphics and virtual environments need to render datasets with large numbers of primitives and high depth complexityatinteractive rates. However, standard techniques like view frustum culling and a hardware z-bu#er are unable to display datasets composed of hundred of thousands of polygons at interactive frame rates on current high-end graphics systems. We add a #conservative" visibility culling stage to the rendering pipeline, attempting to identify and avoid processing of occluded polygons. Given a moving viewpoint, the algorithm dynamically chooses a set of occluders. Each occluder is used to compute a shadow frustum, and all primitives contained within this frustum are culled. The algorithm hierarchicallytraverses the model, culling out parts not visible from the current viewpoint using e#cient, robust, and in some cases specialized interference detection algorithms. The algorithm's performance varies with the location of the viewpoint and the depth...
Keywords
Computer ScienceEngineering
Choice Reviews OnlineComputer graphics: principles and practice
4,665 Citations2013
This chapter discusses the development of Hardware and Software for Computer Graphics, and the design methodology of User-Computer Dialogues, which led to the creation of the Simple Raster Graphics Package.
OBBTree
2,044 Citations1996S. Gottschalk, Ming C. Lin +1 more
A data structure and an algorithm for efficient and exact interference detection amongst complex models undergoing rigid motion that can robustly and accurately detect all the contacts between large complex geometries composed of hundreds of thousands of polygons at interactive rates are presented.
IEEE Journal on Robotics and AutomationA fast procedure for computing the distance between complex objects in three-dimensional space
1,472 Citations1988Éric Gilbert, Daniel Johnson +1 more
An algorithm for computing the Euclidean distance between a pair of convex sets in R/sup m/ has special features which makes its application in a variety of robotics problems attractive.
Applications of random sampling in computational geometry, II
932 Citations1988Kenneth L. Clarkson
Asymptotically tight bounds for (≤k)-sets are given, which are certain halfspace partitions of point sets, and a simple proof of Lee's bounds for high-order Voronoi diagrams is given.
ACM Computing SurveysA Characterization of Ten Hidden-Surface Algorithms
863 Citations1974Ivan E. Sutherland, Robert F. Sproull +1 more
The paper shows that the order of sorting and the types of sorting used form differences among the existing hidden-surface algorithms.
Communications of the ACMHierarchical geometric models for visible surface algorithms
774 Citations1976James H. Clark
On visible surface generation by a priori tree structures
695 Citations1980Henry Fuchs, Zvi M. Kedem +1 more
A new algorithm for solving the hidden surface (or line) problem is described, to more rapidly generate realistic images of 3-D scenes composed of polygons, and the development of theoretical foundations in the area are presented.
I-COLLIDE
619 Citations1995Jonathan D. Cohen, Ming C. Lin +2 more
An exact and interactive collision detection system for large-scale environments, I-COLLIDE, based on pruning multiple-object pairs using bounding boxes and performing exact collision detection between selected pairs of polyhedral models.
Shadow algorithms for computer graphics
533 Citations1977Franklin C. Crow
A classification of shadow algorithms delineates three approaches: shadow computation during scanout; division of object surfaces into shadowed and unshadowed areas prior to removal of hidden surfaces; and inclusion of shadow volumes in the object data.
Hierarchical Z-buffer visibility
494 Citations1993Ned Greene, Michael Kass +1 more
A hierarchical Z-buffer scan-conversion algorithm that does well on both criteria, and is well suited to models with high depth complexity, achieving orders of magnitude acceleration in some cases compared to ordinary Z-buffer scan conversion.
ACM SIGGRAPH Computer GraphicsRay tracing complex scenes
463 Citations1986Timothy L. Kay, James T. Kajiya
Visibility preprocessing for interactive walkthroughs
403 Citations1991Seth Teller, Carlo H. Séquin
A method of visibility preprocessing that is efficient and effective for axis-aligned or axial architectural models and tests on moderately complex 2-D and 3-D axial models reveal substantially reduced rendering loads.
Towards image realism with interactive update rates in complex virtual building environments
350 Citations1990John Airey, John H. Rohlf +1 more
Two strategies, pre-computation before display and adaptive refinement during display, are used to combine interactivity with high image quality in a virtual building simulation.
Visibility culling using hierarchical occlusion maps
343 Citations1997Hansong Zhang, Dinesh Manocha +2 more
HOM for visibility culling on complex models with high depth complexity uses an object space bounding volume hierarchy and a hierarchy of image space occlusion maps to cull away a portion of the model not visible from the current viewpoint.
Portals and mirrors
206 Citations1995David Luebke, Chris Georges
This work describes an approach for determining potentially visible sets in dynamic architectural models, which divides the models into cells and portals, computing a conservative estimate of which cells are visible at render time.
Real-time occlusion culling for models with large occluders
202 Citations1997S. Coorg, Seth Teller
This paper exploits the presence of large occluders in urban and architectural models to design a real-time occlusion culling algorithm that is conservative, i.e., it overestimates the set of visible polygons; it exploits spatial coherence by using a hierarchical data structure; and it exploits temporalCoherence by reusing visibility information computed for previous viewpoints.
Linear programming and convex hulls made easy
162 Citations1990Raimund Seidel
Two randomized algorithms that solve linear programs involving constraints in d variables in expected time and construct convex hulls of n points in Rsupscrpt (3) with dependence of the time bound on d.
IEEE Transactions on Pattern Analysis and Machine IntelligenceEfficiently computing and representing aspect graphs of polyhedral objects
149 Citations1991Z. Gigus, John Canny +1 more
Computer Graphics ForumBOXTREE: A Hierarchical Representation for Surfaces in 3D
144 Citations1996Gill Barequet, Bernard Chazelle +3 more
This work introduces the boxtree, a versatile data structure for representing triangulated or meshed surfaces in 3D that is simple and robust, and requires minimal space.
ACM Transactions on GraphicsWorst-case optimal hidden-surface removal
144 Citations1987Michael McKenna
Two corollaries to the result are (1) hidden-lines can be removed in optimal O(n2) time, and (2) the portion of a 3-D polyhedron visible from a given interior point is constructible in optimal S(n-2) time.
Evaluation of Collision Detection Methods for Virtual Reality Fly-Throughs
112 Citations1995Martin Held, James T. Klosowski +1 more
IEEE Computer Graphics and ApplicationsRobust set operations on polyhedral solids
101 Citations1989Christoph M. Hoffmann, John E. Hopcroft +1 more
An algorithm for performing regularized Boolean operation on polyhedral solids is described, with experience with an implementation of the algorithm using a unit-cube example as a simple test object for robustness.
An efficient algorithm for hidden surface removal
54 Citations1989Ketan Mulmuley
An efficient, randomized hidden surface removal algorithm, with the best time complexity so far, which provably holds for any input, regardless of the way in which faces are located in the scene.
Temporally coherent conservative visibility (extended abstract)
52 Citations1996S. Coorg, Seth Teller
A visibility algorithm is presented that implicitly constructs and maintains a linearized portion of an aspect graph, a data structure for representing visual events, that could achieve fast frame rates while viewing geometric models with many polygons.
Interactive solid geometry via partitioning trees
48 Citations1992Bruce Naylor
This work has constructed an elementary interactive solid geometry system which can execute effectively on workstations with no graphics acceleration hardware and is the first interactive system based on partitioning trees that fully supports set operations, collision detection and transparency for arbitrary polyhedral objects.
AlgorithmicaVisibility with a moving point of view
46 Citations1994Marshall Bern, David Dobkin +2 more
This work investigates three-dimensional visibility problems in which the viewing position moves along a straight flightpath, determining the points along the flightpath at which the topology of the viewed scene changes, and answering ray-shooting queries for rays with origin on the flight path.
International Journal of Computational Geometry & ApplicationsA SURVEY OF OBJECT-SPACE HIDDEN SURFACE REMOVAL
38 Citations1994Susan E. Dorward
A survey of the hidden surface removal literature, focusing on object-space algorithms, is presented, with a brief definition and history of the problem, followed by a discussion of problems and algorithms associated with the priority ordering of faces.
PRESENCE Virtual and Augmented RealityVisibility Computation for Efficient Walkthrough of Complex Environments
38 Citations1996Roni Yagel, William C. Ray
A culling mechanism that is based on regular space subdivision into cells followed by cell classification into interior, exterior, and wall cells is reported on, which means only the objects in the potentially visible set of cells are actually submitted to the hidden object removal algorithm.
ACM SIGGRAPH Computer GraphicsAn efficient algorithm for hidden surface removal
36 Citations1989K. Mulmuley
An optimal algorithm for intersecting three-dimensional convex polyhedra
31 Citations1989Bernard Chazelle
A linear algorithm for intersecting two convex polyhedra in 3-space is described and a number of optimal algorithms for other problems are obtained directly from this result.
Finding the optimal shadows of a convex polytope
19 Citations1985Michael McKenna, Raimund Seidel
The problem of placing a light source at infinity so as to minimize or maximize the shadow area of the polytope is discussed and two algorithms for finding the optimal placement of the light source are exhibited.