@TechReport{Hillesland02, author = "Karl Hillesland and Brian Salomon and Anselmo Lastra and Dinesh Manocha", title = "Fast and Simple Occlusion Culling Using Hardware-Based Depth Queries", institution = "Department of Computer Science, University of North Carolina - Chapel Hill", number = "TR02-039", month = sep # " 12", year = "2002", URL = "ftp://ftp.cs.unc.edu/pub/publications/techreports/02-039.pdf", } @Article{Staneker:2004:OCO, author = "Dirk Staneker and Dirk Bartz and Wolfgang Stra{\ss}er", title = "Occlusion Culling in {OpenSG PLUS}", journal = "Computers and Graphics", volume = "28", number = "1", pages = "87--92", month = feb, year = "2004", CODEN = "COGRD2", ISSN = "0097-8493", bibdate = "Tue Jan 27 12:04:28 MST 2004", acknowledgement = ack-nhfb, } @Article{Staneker:2004:EMO, AUTHOR = "Dirk Staneker and Dirk Bartz and Wolfgang Strasser", TITLE = "Efficient Multiple Occlusion Queries for Scene Graph Systems", JOURNAL = "WSI Report (WSI-2004-6)", INSTITUTION = {Wilhelm Schickard Institute for Computer Science, Graphical Interactive Systems (WSI/GRIS), University of T{\"u}bingen}, YEAR = "2004", KEYWORDS = {GRIS} } @InProceedings{Meissner01, author = "Michael Meissner and Dirk Bartz and Gordon Mueller and Tobias Huettner and Jens Einighammer", title = "Generation of Decomposition Hierarchies for Efficient Occlusion Culling of Large Polygonal Models", pages = "225--232", booktitle = "Proceedings of the Vision Modeling and Visualization Conference 2001", month = nov # " ~21--23", year = "2001", } @Article{Scott:1998:OVF, author = "N. D. Scott and D. M. Olsen and E. W. Gannett", title = "An Overview of the {VISUALIZE fx} Graphics Accelerator Hardware", journal = "Hew\-lett-Pack\-ard Journal: technical information from the laboratories of Hew\-lett-Pack\-ard Company", volume = "49", number = "2", pages = "28--34", month = may, year = "1998", CODEN = "HPJOAX", ISSN = "0018-1153", bibdate = "Thu Nov 5 16:08:50 MST 1998", URL = "http://www.hp.com/hpj/98may/tc-05-98.htm", acknowledgement = ack-nhfb, } @Article{Leyvand:2003:RSF, author = "Tommer Leyvand and Olga Sorkine and Daniel Cohen-Or", title = "Ray space factorization for from-region visibility", journal = "ACM Transactions on Graphics (Proceedings of SIGGRAPH '03)", volume = "22", number = "3", pages = "595--604", month = jul, year = "2003", } @InProceedings{Chrysanthou:97, author = "M. Slater and Y. Chrysanthou", title = "View Volume Culling Using a Probabilistic Caching Scheme", pages = "71--78", booktitle = "Proceedings of the {ACM} Symposium on Virtual Reality Software and Technology ({VRST}'97)", optmonth = sep # "15--17~", publisher = "ACM Press", optaddress = "New York", year = "1997", } @InProceedings{stamminger02, pages = "557--562", year = "2002", title = "Perspective Shadow Maps", author = "Marc Stamminger and George Drettakis", abstract = "Shadow maps are probably the most widely used means for the generation of shadows, despite their well known aliasing problems. In this paper we introduce perspective shadow maps, which are generated in normalized device coordinate space, i.e., after perspective transformation. This results in important reduction of shadow map aliasing with almost no overhead. We correctly treat light source transformations and show how to include all objects which cast shadows in the transformed space. Perspective shadow maps can directly replace standard shadow maps for interactive hardware accelerated rendering as well as in high-quality, offline renderers.", keywords = "Frame Buffer Algorithms, Graphics Hardware, Illumination, Level of Detail Algorithms, Rendering, Shadow Algorithms", booktitle = "SIGGRAPH 2002 Conference Proceedings", publisher = "ACM Press/ ACM SIGGRAPH", } @Article{vazquez99, author = "C. Saona-V{\'a}zquez and I. Navazo and P. Brunet", title = "The visibility octree: a data structure for {$3$D} navigation", journal = "Computers and Graphics", volume = "23", number = "5", pages = "635--643", month = oct, year = "1999", coden = "COGRD2", ISSN = "0097-8493", bibdate = "Sat Oct 21 14:27:20 MDT 2000", url = "http://www.elsevier.nl/gej-ng/10/13/20/24/34/28/abstract.html; http://www.elsevier.nl/gej-ng/10/13/20/24/32/28/article.pdf", acknowledgement = ack-nhfb, } @inproceedings{lloyd02, author = {Brandon Lloyd and Parris Egbert}, title = {Horizon occlusion culling for real-time rendering of hierarchical terrains}, booktitle = {Proceedings of the conference on Visualization '02}, year = {2002}, isbn = {0-7803-7498-3}, pages = {403--410}, location = {Boston, Massachusetts}, publisher = {IEEE Press}, } @InCollection{wald01_eg, pages = "153--164", year = "2001", title = "Interactive Rendering with Coherent Ray Tracing", url = "http://visinfo.zib.de/EVlib/Show?EVL-2001-174", author = "Ingo Wald and Philipp Slusallek and Carsten Benthin and Markus Wagner", abstract = "For almost two decades researchers have argued that ray tracing will eventually become faster than the rasterization technique that completely dominates todays graphics hardware. However, this has not happened yet. Ray tracing is still exclusively being used for off-line rendering of photorealistic images and it is commonly believed that ray tracing is simply too costly to ever challenge rasterization-based algorithms for interactive use. However, there is hardly any scientific analysis that supports either point of view. In particular there is no evidence of where the crossover point might be, at which ray tracing would eventually become faster, or if such a point does exist at all. This paper provides several contributions to this discussion: We first present a highly optimized implementation of a ray tracer that improves performance by more than an order of magnitude compared to currently available ray tracers. The new algorithm make better use of computational resources such as caches and SIMD instructions and better exploits image and object space coherence. Secondly, we show that this software implementation can challenge and even outperform high-end graphics hardware in interactive rendering performance for complex environments. We also provide an brief overview of the benefits of ray tracing over rasterization algorithms and point out the potential of interactive ray tracing both in hardware and software.", editor = "A. Chalmers and T.-M. Rhyne", volume = "20(3)", series = "Computer Graphics Forum", booktitle = "EG 2001 Proceedings", publisher = "Blackwell Publishing", } @InProceedings{purcell02, pages = "703--712", year = "2002", title = "Ray Tracing on Programmable Graphics Hardware", url = "http://visinfo.zib.de/EVlib/Show?EVL-2002-222", author = "Timothy J. Purcell and Ian Buck and William R. Mark and Pat Hanrahan", abstract = "Recently a breakthrough has occurred in graphics hardware: fixed function pipelines have been replaced with programmable vertex and fragment processors. In the near future, the graphics pipeline is likely to evolve into a general programmable stream processor capable of more than simply feed-forward triangle rendering. In this paper, we evaluate these trends in programmability of the graphics pipeline and explain how ray tracing can be mapped to graphics hardware. Using our simulator, we analyze the performance of a ray casting implementation on next generation programmable graphics hardware. In addition, we compare the performance difference between non-branching programmable hardware using a multipass implementation and an architecture that supports branching. We also show how this approach is applicable to other ray tracing algorithms such as Whitted ray tracing, path tracing, and hybrid rendering algorithms. Finally, we demonstrate that ray tracing on graphics hardware could prove to be faster than CPU based implementations as well as competitive with traditional hardware accelerated feed-forward triangle rendering.", keywords = "Programmable Graphics Hardware, Ray Tracing", booktitle = "Computer Graphics (SIGGRAPH '02 Proceedings)", } @InProceedings{Gortler:1996:L, author = "Steven J. Gortler and Radek Grzeszczuk and Richard Szeliski and Michael F. Cohen", title = "The Lumigraph", series = "Annual Conference Series", pages = "43--54", booktitle = "Computer Graphics (SIGGRAPH '96 Proceedings)", year = "1996", publisher = "Addison Wesley", month = aug, annote = "This paper discusses a new method for capturing the complete appearance of both synthetic and real world objects and scenes, representing this information, and then using this representation to render images of the object from new camera positions. Unlike the shape capture process traditionally used in computer vision and the rendering process traditionally used in computer graphics, our approach does not rely on geometric representations. Instead we sample and reconstruct a 4D function, which we call a Lumigraph. The Lumigraph is a subset of the complete plenoptic function that describes the flow of light at all positions in all directions. With the Lumigraph, new images of the object can be generated very quickly, independent of the geometric or illumination complexity of the scene or object. The paper discusses a complete working system including the capture of samples, the construction of the Lumigraph, and the subsequent rendering of images from this new representation.", } @Article{Gotsman:1999:OOC, author = "Craig Gotsman and Oded Sudarsky and Jeffrey A. Fayman", title = "Optimized occlusion culling using five-dimensional subdivision", journal = "Computers and Graphics", volume = "23", number = "5", pages = "645--654", month = oct, year = "1999", coden = "COGRD2", ISSN = "0097-8493", bibdate = "Sat Oct 21 14:27:20 MDT 2000", url = "http://www.elsevier.nl/gej-ng/10/13/20/24/34/29/abstract.html; http://www.elsevier.nl/gej-ng/10/13/20/24/32/29/article.pdf", acknowledgement = ack-nhfb, } @article{Pag94, author = {David W. Paglieroni and Sidney M. Petersen}, title = {Height distributional distance transform methods for height field ray tracing}, journal = {ACM Transactions on Graphics (TOG)}, volume = {13}, number = {4}, year = {1994}, issn = {0730-0301}, pages = {376--399}, doi = {http://doi.acm.org/10.1145/195826.197312}, publisher = {ACM Press}, } @article{lee97, author = "Cheol-Hi Lee and Yeong Gil Shin", title = "A Terrain Rendering Method using Vertical Ray Coherence", journal = "The Journal of Visualization and Computer Animation", volume = "8", number = "2", pages = "97--114", year = "1997", } @TechReport{mcmillan:97:phd, type = "Ph.D. Thesis", number = "TR97-013", institution = "University of North Carolina, Chapel Hill", title = "An Image-Based Approach to Three-Dimensional Computer Graphics", month = may, year = "1997", bibdate = "June 9, 1997", url = "ftp://ftp.cs.unc.edu/pub/publications/techreports/97-013.pdf.Z", author = "Leonard McMillan", } @MastersThesis{aila:00:msc, author = {Timo Aila}, title = {SurRender Umbra: A Visibility Determination Framework for Dynamic Environments}, school = {Helsinki University of Technology}, year = {2000}, } @Article{duguet:02:sig, year = "2002", title = "Robust Epsilon Visibility", author = "Florent Duguet and George Drettakis", journal = "To appear in Computer Graphics (SIGGRAPH'02 Proceedings)", publisher = "ACM SIGGRAPH", } @InProceedings{wand:01:sig, pages = "361--370", year = "2001", title = "The Randomized z-Buffer Algorithm: Interactive Rendering of Highly Complex Scenes", url = "http://visinfo.zib.de/EVlib/Show?EVL-2001-125", author = "Michael Wand and Matthias Fischer and Ingmar Peter and Friedhelm Meyer auf der Heide and Wolfgang Stra{\ss{}}er", abstract = "We present a new output-sensitive rendering algorithm, the randomized z-buffer algorithm. It renders an image of an arbitrary three-dimensional scene consisting of triangular primitives by reconstruction from a dynamically chosen set of random surface sample points. This approach is independent of mesh connectivity and topology. The resulting rendering time grows only logarithmically with the numbers of triangles in the scene. We were able to render walkthroughs of scenes of up to 1014 triangles at interactive frame rates. Automatic identification of low detail scene components ensures that the rendering speed of the randomized z-buffer cannot drop below that of conventional z-buffer rendering. Experimental and analytical evidence is given that the image quality is comparable to that of common approaches like z-buffer rendering. The precomputed data structures employed by the randomized z-buffer allow for interactive dynamic updates of the scene. Their memory requirements grow only linearly with the number of triangles and allow for a scene graph based instantiation scheme to further reduce memory consumption.", keywords = "Rendering Systems, Level of Detail Algorithms, Monte Carlo Techniques", booktitle = "Computer Graphics (Proceedings of SIGGRAPH 2001)", publisher = "ACM SIGGRAPH", } @Book{berg:97, year = "1997", title = "Computational Geometry: Algorithms and Applications", author = "{Mark de} Berg and {Marc van} Kreveld and Mark Overmars and Otfried Schwarzkopf", url = "http://visinfo.zib.de/EVlib/Show?EVL-1997-230", language = "en", abstract = "Computational geometry emerged from the field of algorithms design and analysis in the late 1970s. It has grown into a recognized discipline with its own journals, conferences, and a large community of active researchers. The success of the field as a research discipline can on the one hand be explained from the beauty of the problems studied and the solutions obtained, and, on the other hand, by the many application domains---computer graphics, geographic information systems (GIS), robotics, and others---in which geometric algorithms play a fundamental role. For many geometric problems the early algorithmic solutions were either slow or difficult to understand and implement. In recent years a number of new algorithmic techniques have been developed that improved and simplified many of the previous approaches. In this textbook we have tried to make these modern algorithmic solutions accessible to a large audience. The book has been written as a textbook for a course in computational geometry, but it can also be used for self study. Each of the sixteen chapters, except the introductory chapter, starts with a problem arising in one of the application domains. This problem is then transformed into a purely geometric one, which is solved using techniques from computational geometry. The geometric problem and the concepts and techniques needed to solve it are the real topic of each chapter. The choice of the applications was guided by the topics in computational geometry we wanted to cover; they are not meant to provide a good coverage of the application domains. The purpose of the applications is to motivate the reader; the goal of the chapters is not to provide ready-to-use solutions for them. Having said this, we believe that knowledge of computational geometry is important to solve geometric problems in application areas efficiently. We hope that our book will not only raise the interest of people from the algorithms community, but also from people in the application areas. For most geometric problems treated we give just one solution, even when a number of different solutions exist. In general we have chosen the solution that is most easy to understand and implement. This is not necessarily the most efficient solution. We also took care that the book contains a good mixture of techniques like divide-and-conquer, plane sweep, and randomized algorithms. We decided not to treat all sorts of variations to the problems; we felt it is more important to introduce all main topics in computational geometry than to give more detailed information about a smaller number of topics.", address = "Berlin, Heidelberg, New York", copyright = "Springer-Verlag", publisher = "Springer-Verlag", } @InProceedings{Appel:1968:STS, author = "Arthur Appel", title = "Some Techniques for Shading Machine Renderings of Solids", booktitle = "AFIPS 1968 Spring Joint Computer Conf.", pages = "37--45", volume = "32", year = "1968", keywords = "visible", annote = "first ray tracing paper, light ray tracing, black and white pictures on Calcomp plotter This paper presents some recent experimental results in the automatic shading of line drawings. The purpose of these experiments was to generate pictures of objects consisting of flat surfaces on a digital plotter and to evaluate the cost of generating such pictures and the resultant graphical quality.", } @Article{floriani:95:vc, author = "L. De Floriani and P. Magillo", title = "Horizon Computation on a Hierarchical Terrain Model", journal = "The Visual Computer: An International Journal of Computer Graphics", volume = "11", year = "1995", publisher = "Springer Verlag, New York", pages = "134--149", topic = "visibility", } @InProceedings{nirenstein:02:egwr, year = "2002", title = "Exact {From-Region} Visibility Culling", author = "Shaun Nirenstein and Edwin Blake and James Gain", booktitle = "Proceedings of EUROGRAPHICS Workshop on Rendering", pages = "199--210", } @InCollection{Klosowski:2000:PLP, pages = "108--123", year = "2000", title = "The Prioritized-Layered Projection Algorithm for Visible Set Estimation", url = "http://visinfo.zib.de/EVlib/Show?EVL-2000-206", author = "J. T. Klosowski and C. T. Silva", abstract = "Prioritized-Layered Projection (PLP) is a technique for fast rendering of high depth complexity scenes. It works by estimating the visible polygons of a scene from a given viewpoint incrementally, one primitive at a time. It is not a conservative technique, instead PLP is suitable for the computation of partially correct images for use as part of time-critical rendering systems. From a very high level, PLP amounts to a modification of a simple view-frustum culling algorithm, however, it requires the computation of a special occupancy-based tessellation and the assignment to each cell of the tessellation a solidity value, which is used to compute a special ordering on how primitives get projected. In this paper, we detail the PLP algorithm, its main components, and implementation. We also provide experimental evidence of its performance, including results on two types of spatial tessellation (using octree- and Delaunay-based tessellations), and several datasets. We also discuss several extensions of our technique.", editor = "Hans Hagen and David S. Ebert", keywords = "Visibility, time-critical rendering, occlusion culling, visible set, spatial tessellation", volume = "6 (2)", booktitle = "IEEE Transactions on Visualization and Computer Graphics", publisher = "IEEE Computer Society", } @Article{Klosowski:2001:ECV, author = "James T. Klosowski and Cl{\'a}udio T. Silva.", title = "Efficient Conservative Visibility Culling Using the Prioritized-Layered Projection Algorithm", journal = "IEEE Transactions on Visualization and Computer Graphics", volume = "7", number = "4", pages = "365--379", month = oct, year = "2001", coden = "ITVGEA", ISSN = "1077-2626", bibdate = "Sat Feb 23 09:10:10 MST 2002", url = "http://www.computer.org/tvcg/tg2001/v0365abs.htm; http://dlib.computer.org/tg/books/tg2001/pdf/v0365.pdf", acknowledgement = ack-nhfb, } @InProceedings{hey:01:egwr, author = "Heinrich Hey and Robert F. Tobler and Werner Purgathofer", title = "{Real-Time} Occlusion Culling with a Lazy Occlusion Grid", pages = "217--222", year= "2001", booktitle = "Proceedings of EUROGRAPHICS Workshop on Rendering", } @InProceedings{wonka:01:eg, pages = "411--421", year = "2001", title = "Instant Visibility", author = "Peter Wonka and Michael Wimmer and Fran{\c{c}}ois X. Sillion", url = "http://visinfo.zib.de/EVlib/Show?EVL-2001-201", abstract = "We present an online occlusion culling system which computes visibility in parallel to the rendering pipeline. We show how to use point visibility algorithms to quickly calculate a tight potentially visible set (PVS) which is valid for several frames, by shrinking the occluders used in visibility calculations by an adequate amount. These visibility calculations can be performed on a visibility server, possibly a distinct computer communicating with the display host over a local network. The resulting system essentially combines the advantages of online visibility processing and region-based visibility calculations, allowing asynchronous processing of visibility and display operations. We analyze two different types of hardware-based point visibility algorithms and address the problem of bounded calculation time which is the basis for true real-time behavior. Our results show reliable, sustained 60 Hz performance in a walkthrough with an urban environment of nearly 2 million polygons, and a terrain flyover.", booktitle = "Computer Graphics Forum (Proceedings of EUROGRAPHICS '01)", optpublisher = "Blackwell Publishing", } @InProceedings{fernando:01:sig, pages = "387--390", year = "2001", title = "Adaptive Shadow Maps", url = "http://visinfo.zib.de/EVlib/Show?EVL-2001-128", author = "Randima Fernando and Sebastian Fernandez and Kavita Bala and Donald P. Greenberg", abstract = "Shadow maps provide a fast and convenient method of identifying shadows in scenes but can introduce aliasing. This paper introduces the Adaptive Shadow Map (ASM) as a solution to this problem. An ASM removes aliasing by resolving pixel size mismatches between the eye view and the light source view. It achieves this goal by storing the light source view (i.e., the shadow map for the light source) as a hierarchical grid structure as opposed to the conventional flat structure. As pixels are transformed from the eye view to the light source view, the ASM is refined to create higher-resolution pieces of the shadow map when needed. This is done by evaluating the contributions of shadow map pixels to the overall image quality. The improvement process is view-driven, progressive, and confined to a user-specifiable memory footprint. We show that ASMs enable dramatic improvements in shadow quality while maintaining interactive rates.", keywords = "Rendering, Shadow Algorithms", booktitle = "Computer Graphics (Proceedings of SIGGRAPH '01)", publisher = "ACM SIGGRAPH", } @InProceedings{rusinkiewicz:00:sig, pages = "343--352", year = "2000", title = "{QS}plat: {A} Multiresolution Point Rendering System for Large Meshes", url = "http://visinfo.zib.de/EVlib/Show?EVL-2000-73", author = "Szymon Rusinkiewicz and Marc Levoy", abstract = "Advances in 3D scanning technologies have enabled the practical creation of meshes with hundreds of millions of polygons. Traditional algorithms for display, simplification, and progressive transmission of meshes are impractical for data sets of this size. We describe a system for representing and progressively displaying these meshes that combines a multiresolution hierarchy based on bounding spheres with a rendering system based on points. A single data structure is used for view frustum culling, backface culling, level-of-detail selection, and rendering. The representation is compact and can be computed quickly, making it suitable for large data sets. Our implementation, written for use in a large-scale 3D digitization project, launches quickly, maintains a user-settable interactive frame rate regardless of object complexity or camera position, yields reasonable image quality during motion, and refines progressively when idle to a high final image quality. We have demonstrated the system on scanned models containing hundreds of millions of samples.", keywords = "Rendering systems, Spatial data structures, Level of detail algorithms, Compression algorithms", booktitle = "Computer Graphics (Proceedings of SIGGRAPH 2000)", publisher = "ACM SIGGRAPH / Addison Wesley Longman", } @InProceedings{pfister:00:sig, pages = "335--342", year = "2000", title = "Surfels: Surface Elements as Rendering Primitives", url = "http://visinfo.zib.de/EVlib/Show?EVL-2000-69", author = "Hanspeter Pfister and Matthias Zwicker and Jeroen van Baar and Markus Gross", abstract = "Surface elements (surfels) are a powerful paradigm to efficiently render complex geometric objects at interactive frame rates. Unlike classical surface discretizations, i.e., triangles or quadrilateral meshes, surfels are point primitives without explicit connectivity. Surfel attributes comprise depth, texture color, normal, and others. As a pre-process, an octree-based surfel representation of a geometric object is computed. During sampling, surfel positions and normals are optionally perturbed, and different levels of texture colors are prefiltered and stored per surfel. During rendering, a hierarchical forward warping algorithm projects surfels to a z-buffer. A novel method called visibility splatting determines visible surfels and holes in the z-buffer. Visible surfels are shaded using texture filtering, Phong illumination, and environment mapping using per-surfel normals. Several methods of image reconstruction, including supersampling, offer flexible speed-quality tradeoffs. Due to the simplicity of the operations, the surfel rendering pipeline is amenable for hardware implementation. Surfel objects offer complex shape, low rendering cost and high image quality, which makes them specifically suited for low-cost, real-time graphics, such as games.", keywords = "Rendering Systems, Texture Mapping", booktitle = "Computer Graphics (Proceedings of SIGGRAPH 2001)", publisher = "ACM SIGGRAPH / Addison Wesley Longman", } @InProceedings{Grossman:rend98-181, booktitle = "Rendering Techniques '98 (Proceedings of Eurographics Rendering Workshop)", year = "1998", publisher = "Springer-Verlag Wien New York", author = "J. P. Grossman and William J. Dally", title = "Point Sample Rendering", pages = "181--192", abstract = "We present an algorithm suitable for real-time, high quality rendering of complex objects. Objects are represented as a dense set of surface point samples which contain colour, depth and normal infocmation. These point samples are obtained by sampling orthographic views on an equilateral triangle lattice. They are rendered directly and independently without any knowledge of surface topology. We introduce a novel solution to the problem of surface reconstruction using a hierarchy of Z-buffers to detect tears. Our algorithm is fast and requires only modest resources.", } @Article{Bartz:1999:OAO, author = "Dirk Bartz and Michael Mei{\ss}ner and Tobias H{\"u}ttner", title = "Open{GL}-assisted occlusion culling for large polygonal models", journal = "Computers and Graphics", volume = "23", number = "5", pages = "667--679", month = oct, year = "1999", coden = "COGRD2", ISSN = "0097-8493", bibdate = "Sat Oct 21 14:27:20 MDT 2000", url = "http://www.elsevier.nl/gej-ng/10/13/20/24/34/31/abstract.html; http://www.elsevier.nl/gej-ng/10/13/20/24/32/31/article.pdf", acknowledgement = ack-nhfb, } @InProceedings{popescu:98:viz, author = "V. Popescu and A. Lastra and D. Aliaga and M. de Oliveira Neto", title = "Efficient warping for architectural walkthroughs using layered depth images", pages = "211--216", booktitle = "{IEEE} Visualization '98 ({VIS} '98)", ISBN = "0-8186-9176-X", month = oct, publisher = "IEEE", address = "Washington - Brussels - Tokyo", year = "1998", } @InProceedings{aliaga:99:sig, author = "Daniel G. Aliaga and Anselmo Lastra", title = "Automatic Image Placement to Provide a Guaranteed Frame Rate", pages = "307--316", ISBN = "0-201-48560-5", editor = "Alyn Rockwood", booktitle = "Proceedings of the Conference on Computer Graphics (Siggraph99)", month = aug # "8--13", publisher = "ACM Press", address = "N.Y.", year = "1999", } @InProceedings{aliaga:99:i3dg, author = "Daniel Aliaga and Jon Cohen and Andrew Wilson and Eric Baker and Hansong Zhang and Carl Erikson and Keny Hoff and Tom Hudson and Wolfgang St{\"u}rzlinger and Rui Bastos and Mary Whitton and Fred Brooks and Dinesh Manoclia", title = "{MMR}: An Interactive Massive Model Rendering System Using Geometric and Image-Based Acceleration (Color Plate {S}. 237)", pages = "199--206", ISBN = "1-58113-082-1", editor = "Stephen N. Spencer", booktitle = "Proceedings of the Conference on the 1999 Symposium on interactive {3D} Graphics", month = apr # " ~26--28", publisher = "ACM Press", address = "New York", year = "1999", } @InProceedings{wimmer:01:egwr, author = "Michael Wimmer and Peter Wonka and Francois Sillion", title = "{Point-Based} Impostors for {Real-Time} Visualization", pages = "163--176", crossref = "RENDERING TECHNIQUES`01", } @InProceedings{Jeschke:LEM:2002, title = "{Layered Environment-Map Impostors for Arbitrary Scenes}", author = "Stefan Jeschke and Michael Wimmer and Heidrun Schuman", booktitle = "Proc. Graphics Interface", year = "2002", month = may, location = "Calgary, Alberta", pages = "1--8", } @Book{Neider93, author = "Jackie Neider and Tom Davis and Mason Woo", title = "{OpenGL} Programming Guide", publisher = "Addison-Wesley", address = "Reading MA", year = "1993", keywords = "computer graphics, graphics workstation, SGI", annote = "shadows on a plane p. 401", } @PhdThesis{Havran2000:PhD, author = "Vlastimil Havran", title = "Heuristic Ray Shooting Algorithms", school = "Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague", type = "Ph.D. Thesis", year = "2000", month = "November", url = "http://www.cgg.cvut.cz/~havran/phdthesis.html", annote = "Global illumination research aiming at the photo-realistic image synthesis pushes forward research in computer graphics as a whole. The computation of visually plausible images is time-consuming and far from being realtime at present. A significant part of computation in global illumination algorithms involves repetitive computing of visibility queries. In the thesis, we describe our results in ray shooting, which is a well-known problem in the field of visibility. The problem is difficult in spite of its simple definition: For a given oriented half-line and a set of objects, find out the first object intersected by the half-line if such an object exists. A naive algorithm has the time complexity O(N), where N is the number of objects. The naive algorithm is practically inapplicable in global illumination applications for a scene with a high number of objects, due its huge time requirements. In this thesis we deal with heuristic ray shooting algorithms that use additional spatial data structures. We put stress on average-case complexity and we particularly investigate the ray shooting algorithms based on spatial hierarchies. In the thesis we deal with two major topics. In the first part of the thesis, we introduce a ray shooting computation model and performance model. Based on these two models we develop a methodology for comparing various ray shooting algorithms for a set of experiments performed on a set of scenes. Consecutively, we compare common heuristic ray shooting algorithms based on BSP trees, kd-trees, octrees, bounding volume hierarchies, uniform grids, and three types of hierarchical grids using a set of 30 scenes from Standard Procedural Database. We show that for this set of scenes the ray shooting algorithm based on the kd-tree is the winning candidate among all tested ray shooting algorithms. The second and major part of the thesis presents several techniques for decreasing the time and space complexity for ray shooting algorithms based on kd-tree. We deal with both kd-tree construction and ray traversal algorithms. In the context of kd-tree construction, we present new methods for adaptive construction of the kd-tree using empty spatial regions in the scene, termination criteria, general cost model for the kd-tree, and modified surface area heuristics for a restricted set of rays. Further, we describe a new version of the recursive ray traversal algorithm. In context of the recursive ray traversal algorithm based on the kd-tree, we develop the concept of the largest common traversal sequence. This reduces the number of hierarchical traversal steps in the kd-tree for certain ray sets. We also describe one technique closely related to computer architecture, namely mapping kd-tree nodes to memory to increase the cache hit ratio for processors with a large cache line. Most of the techniques proposed in the thesis can be used in combination. In practice, the average time complexity of the ray shooting algorithms based on the kd-tree, as presented in this thesis, is about $O(log N)$, where the hidden multiplicative factor depends on the input data. However, at present it is not known to have been proved theoretically for scenes with general distribution of objects. For these reasons our findings are supported by a set of experiments for the above-mentioned set of 30 scenes.", } @InProceedings{goral84a, author = "Cindy M. Goral and Kenneth K. Torrance and Donald P. Greenberg and Bennett Battaile", title = "Modelling the Interaction of Light Between Diffuse Surfaces", pages = "213--222", booktitle = "Computer Graphics (SIGGRAPH '84 Proceedings)", volume = "18", number = "3", year = "1984", month = jul, conference = "held in Minneapolis, Minnesota; 23--27 July 1984", keywords = "radiosity method, diffuse surfaces, I37 Lighting Interaction", annote = "The classic reference on radiosity. Early work on radiosity method. See Hemi Cube paper for more in depth description of implementation.", } @InProceedings{Heidrich:00:EGWR, author = "Wolfgang Heidrich and Stefan Brabec and {Hans-Peter} Seidel", title = "Soft Shadow Maps for Linear Lights", pages = "269--280", year = "2000", booktitle = "Proceedings of EUROGRAPHICS Workshop on Rendering", } @Article{Heidmann91, author = "Tim Heidmann", title = "Real Shadows, Real Time", journal = "Iris Universe", note = "Silicon Graphics, Inc.", volume = "18", year = "1991", pages = "28--31", keywords = "soft shadow, SGI Reality Engine, stencil buffer, shadow volume", annote = "includes C, GL code", } @InProceedings{Heidrich:99:IDG, year = "1999", title = "Applications of Pixel Textures in Visualization and Realistic Image Synthesis", author = "W. Heidrich and R. Westermann and H.-P. Seidel and T. Ertl", url = "http://visinfo.zib.de/EVlib/Show?EVL-1999-121", organization = "ACM/Siggraph", booktitle = "ACM Symposium on Interactive 3D Graphics", } @Article{Segal92, author = "Mark Segal and Carl Korobkin and Rolf van Widenfelt and Jim Foran and Paul Haeberli", title = "Fast Shadows and Lighting Effects using Texture Mapping", journal = "Computer Graphics (SIGGRAPH '92 Proceedings)", volume = "26", number = "2", month = jul, year = "1992", pages = "249--252", keywords = "perspective, scan conversion", } @InProceedings{Williams78, AUTHOR={Lance Williams}, TITLE={Casting Curved Shadows on Curved Surfaces}, booktitle={Computer Graphics (SIGGRAPH '78 Proceedings)}, MONTH={Aug.}, YEAR={1978}, PAGES={270-274}, } @InProceedings{Hoppe:98:LOD, pages = "35--42", year = "1998", title = "Smooth View-Dependent Level-Of-Detail Control and its Application to Terrain Rendering", url = "http://visinfo.zib.de/EVlib/Show?EVL-1998-124", author = "Hugues Hoppe", language = "en", abstract = "The key to real-time rendering of large-scale surfaces is to locally adapt surface geometric complexity to changing view parameters. Several schemes have been developed to address this problem of view-dependent level-of-detail control. Among these, the view-dependent progressive mesh (VDPM) framework represents an arbitrary triangle mesh as a hierarchy of geometrically optimized refinement transformations, from which accurate approximating meshes can be efficiently retrieved. In this paper we extend the general VDPM framework to provide temporal coherence through the runtime creation of geomorphs. These geomorphs eliminate {"}popping{"} artifacts by smoothly interpolating geometry. Their implementation requires new output-sensitive data structures, which have the added benefit of reducing memory use. We specialize the VDPM framework to the important case of terrain rendering. To handle huge terrain grids, we introduce a block-based simplification scheme that constructs a progressive mesh as a hierarchy of block refinements. We demonstrate the need for an accurate approximation metric during simplification. Our contributions are highlighted in a real-time flyover of a large, rugged terrain. Notably, the use of geomorphs results in visually smooth rendering even at 72 frames/sec on a graphics workstation.", organization = "IEEE", copyright = "IEEE", booktitle = "Proceedings IEEE Visualization'98", } @InProceedings{Hoppe:1997:VDR, author = "Hugues Hoppe", title = "View-Dependent Refinement of Progressive Meshes", booktitle = "SIGGRAPH 97 Conference Proceedings", editor = "Turner Whitted", series = "Annual Conference Series", year = "1997", organization = "ACM SIGGRAPH", publisher = "Addison Wesley", month = aug, pages = "189--198", note = "ISBN 0-89791-896-7", keywords = "mesh simplification, level-of-detail, multiresolution representations, dynamic tessellation, shape interpolation", annote = "Level-of-detail (LOD) representations are an important tool for real-time rendering of complex geometric environments. The previously introduced progressive mesh representation defines for an arbitrary triangle mesh a sequence of approximating meshes optimized for view-independent LOD. In this paper, we introduce a framework for selectively refining an arbitrary progressive mesh according to changing view parameters. We define efficient refinement criteria based on the view frustum, surface orientation, and screen-space geometric error, and develop a real-time algorithmfor incrementally refining and coarsening the mesh according to these criteria. The algorithm exploits view coherence, supports frame rate regulation, and is found to require less than 15% of total frame time on a graphics workstation. Moreover, for continuous motions this work can be amortized over consecutive frames. In addition, smooth visual transitions (geomorphs) can be constructed between any two selectively refined meshes. A number of previous schemes create view-dependent LOD meshes for height fields (e.g. terrains) and parametric surfaces (e.g. NURBS). Our framework also performs well for these special cases. Notably, the absence of a rigid subdivision structure allows more accurate approximations than with existing schemes. We include results for these cases as well as for general meshes.", } @InProceedings{Hoppe:1996:PM, author = "Hugues Hoppe", title = "Progressive Meshes", editor = "Holly Rushmeier", series = "Annual Conference Series", pages = "99--108", booktitle = "SIGGRAPH 96 Conference Proceedings", year = "1996", organization = "ACM SIGGRAPH", publisher = "Addison Wesley", month = aug, note = "held in New Orleans, Louisiana, 04-09 August 1996", annote = "Highly detailed geometric models are rapidly becoming commonplace in computer graphics. These models, often represented as complex triangle meshes, challenge rendering performance, transmission bandwidth, and storage capacities. This paper introduces the progressive mesh (PM) representation, a new scheme for storing and transmitting arbitrary triangle meshes. This efficient, lossless, continuous-resolution representation addresses several practical problems in graphics: smooth geomorphing of level-of-detail approximations, progressive transmission, mesh compression, and selective refinement. In addition, we present a new mesh simplification procedure for constructing a PM representation from an arbitrary mesh. The goal of this optimization procedure is to preserve not just the geometry of the original mesh, but more importantly its overall appearance as defined by its discrete and scalar appearance attributes such as material identifiers, color values, normals, and texture coordinates. We demonstrate construction of the PM representation and its applications using several practical models.", } @InProceedings{andujar:2000:HVS, author = {Carlos And\'ujar, Carlos Saona-V\'azquez, Isabel Navazo and Pere Brunet}, title = {Integrating Occlusion Culling with Levels of Detail through Hardly-Visible Sets}, booktitle = {Computer Graphics Forum (Proceedings of Eurographics 2000)}, year = {2000}, volume = "19", number="3", pages="499--506", } @InProceedings{downs:2001:I3DG, author = "Laura Downs and Tomas M{\"o}ller and Carlo H. S{\'e}quin", title = "Occlusion Horizons for Driving through Urban Scenes", booktitle = "Symposium on Interactive {3D} Graphics", year = "2001", organization = "ACM SIGGRAPH", pages = "121--124", } @PhdThesis{zhang_phd, author = {Hansong Zhang}, title = {Effective Occlusion Culling for the Interactive Display of Arbitrary Models}, school = {Department of Computer Science, UNC-Chapel Hill}, year = {1998}, } @PhdThesis{wonka_phd, author = {Peter Wonka}, title = {Occlusion Culling for Real-Time Rendering of Urban Environments}, school = {Institute of Computer Graphics, Vienna University of Technology}, year = {2001}, } @TechReport{Schumacker69, author = "R. A. Schumacker and R. Brand and M. Gilliland and W. Sharp", title = "Study for Applying Computer-Generated Images to Visual Simulation", institution = "U.S. Air Force Human Resources Laboratory", year = "1969", number = "AFHRL--TR--69--14", } @InProceedings{Carpenter:1984:BAH, author = "Loren Carpenter", title = "The {A}-buffer, an Antialiased Hidden Surface Method", pages = "103--108", booktitle = "Computer Graphics (SIGGRAPH '84 Proceedings)", volume = "18", year = "1984", month = jul, editor = "Hank Christiansen", conference = "held in Minneapolis, Minnesota; 23--27 July 1984", keywords = "z-buffer, a-buffer, antialiasing, I33 Anti-Aliasing, I37 Hidden-Surface Removal", annote = "Carpenter presents a method of constructing antialiased images in a method which allows transparency. If flavor, it is very similar to z-buffer, but subsamples pixels and maintains coverage masks to allow effective antialiasing.", } @InProceedings{Newell:1972:SHS, author = "Martin E. Newell and R. G. Newell and T. L. Sancha", title = "A Solution to the Hidden Surface Problem", year = "1972", booktitle = "Proceedings of ACM National Conference", keywords = "hidden surface", } @TechReport{Warnock:1969:HSA, author = "J. Warnock", title = "A Hidden-Surface Algorithm for Computer Generated Half-Tone Pictures", number = "TR 4--15, NTIS AD-733 671", year = "1969", institution = "University of Utah, Computer Science Department", keywords = "visible", } @InProceedings{Weiler:1977:HSR, author = "Kevin Weiler and Peter Atherton", title = "Hidden Surface Removal Using Polygon Area Sorting", booktitle = "Computer Graphics (SIGGRAPH '77 Proceedings)", conference = "held in San Jose, California; 20 -- 22 July 1977", month = jul, year = "1977", pages = "214--222", keywords = "hidden surface removal, hidden line removal", } @InProceedings{iones:1998:CGI, author = "A. Iones and S. Zhukov and A. Krupkin", title = "On Optimality of {OBBs} for Visibility Tests for Frustum Culling, Ray Shooting and Collision Detection", pages = "256--263", ISBN = "0-8186-8445-3", editor = "Franz-Erich Wolter and Nicholas M. Patrikalakis", booktitle = "Proceedings of the Conference on Computer Graphics International 1998 ({CGI}-98)", month = jun # " ~22--26", publisher = "IEEE Computer Society", address = "Los Alamitos, California", year = "1998", } @Article{Assarsson:2000:OVF, author = "Ulf Assarsson and Tomas M{\"o}ller", title = "Optimized View Frustum Culling Algorithms for Bounding Boxes", journal = "Journal of Graphics Tools: JGT", volume = "5", number = "1", pages = "9--22", year = "2000", coden = "JGTOFD", ISSN = "1086-7651", bibdate = "Thu Oct 12 17:08:13 2000", url = "http://www.acm.org/jgt/papers/AssarssonMoller00/", abstract = "This paper presents optimizations for faster view frustum culling (VFC) for axis-aligned bounding box (AABB) and oriented bounding box (OBB) hierarchies. We exploit frame-to-frame coherency by caching and by comparing against previous distances and rotation angles. By using an octant test, we potentially halve the number of plane tests needed, and we also evaluate masking, which is a well-known technique. The optimizations can be used for arbitrary bounding volumes, but we present only results for ABBs and OBBs. In particular, we provide solutions which are 2-11 times faster than other VFC algorithms for AABBs and OBBs, depending on the circumstances.", acknowledgement = ack-nhfb, } @InProceedings{Wonka:1999:OSF, author = "Peter Wonka and Dieter Schmalstieg", title = "Occluder Shadows for Fast Walkthroughs of Urban Environments", booktitle = "Computer Graphics Forum (Proceedings of EUROGRAPHICS '99)", month = sep, year = "1999", optpublisher = "Blackwell Publishers", pages = "51--60", annote = "This paper describes a new algorithm that employs image-based rendering for fast occlusion culling in complex urban environments. It exploits graphics hardware to render and automatically combine a relatively large set of occluders. The algorithm is fast to calculate and therefore also useful for scenes of moderate complexity and walkthroughs with over 20 frames per second. Occlusion is calculated dynamically and does not rely on any visibility precalculation or occluder preselection. Speed-ups of one order of magnitude can be obtained.", } @Book{Moller99-RTR, author = "Tomas M{\"o}ller and Eric Haines", year = "1999", title = "Real-Time Rendering", publisher = "A. K. Peters Limited", } @InProceedings{Chrysanthou:1995:SVB, author = "Yiorgos Chrysanthou and Mel Slater", title = "Shadow Volume {BSP} Trees for Computation of Shadows in Dynamic Scenes", editor = "Pat Hanrahan and Jim Winget", pages = "45--50", booktitle = "1995 Symposium on Interactive {3D} Graphics", year = "1995", organization = "ACM SIGGRAPH", month = apr, note = "ISBN 0-89791-736-7", } @ARTICLE{Crow77, AUTHOR={Franklin C. Crow}, TITLE={Shadow Algorithms for Computer Graphics}, JOURNAL={Computer Graphics (SIGGRAPH '77 Proceedings)}, VOLUME={11}, NUMBER={2}, MONTH={Summer}, YEAR={1977}, } @InProceedings{GTHP99, author ="J\'erome Grasset and Olivier Terraz and Jean-Marc Hasenfratz and Dimitri Plemenos", title ="Accurate Scene Display by Using Visibility Maps", booktitle ="Spring Conference on Computer Graphics and its Applications", year ="1999", url ="http://www-imagis.imag.fr/Publications/1999/GTHP99" } @Unpublished{cdd_site, author = {Komei Fukuda}, title = {Cdd home page}, note = {http://www.ifor.math.ethz.ch}, } % note = "http://www.ifor.math.ethz.ch/fukuda/cdd_home/cdd.html", @Unpublished{nvidia_site, author = {NVIDIA corp.}, title = {Graphics hardware specifications.}, note = {http://www.nvidia.com}, } @Unpublished{ati_site, author = {ATI corp.}, title = {Graphics hardware specifications.}, note = {http://www.ati.com}, } %See remarks \cite{Pavlidis:1990:RCS,Wold:1990:RCS}. @Article{Cook:1986:SSC, author = "Robert L. Cook", title = "Stochastic Sampling in Computer Graphics", journal = "ACM Transactions on Graphics", volume = "5", number = "1", pages = "51--72", month = jan, year = "1986", coden = "ATGRDF", ISSN = "0730-0301", bibdate = "Thu Aug 25 23:39:28 1994", note = " Also in Tutorial: Computer Graphics: Image Synthesis, Computer Society Press, Washington, 1988, pp. 283--304.", url = "http://www.acm.org/pubs/toc/Abstracts/0730-0301/8927.html", acknowledgement = ack-nhfb, keywords = "algorithms; antialiasing; depth of field; filtering; image synthesis; Monte Carlo integration; motion blur; raster graphics; ray tracing; stochastic sampling", review = "ACM CR 8709-0784", subject = "{\bf I.3.3}: Computing Methodologies, COMPUTER GRAPHICS, Picture/Image Generation, Viewing algorithms. {\bf G.3}: Mathematics of Computing, PROBABILITY AND STATISTICS, Probabilistic algorithms (including Monte Carlo).", } @ARTICLE{Cohen85, AUTHOR={Michael F. Cohen and Donald P. Greenberg}, TITLE={The Hemi-Cube: A Radiosity Solution for Complex Environments}, JOURNAL={Computer Graphics (SIGGRAPH '85 Proceedings)}, VOLUME={19}, NUMBER={3}, MONTH={July}, YEAR={1985}, PAGES={31-40}, KEYWORDS={shading, diffuse reflection}, } @Article{Sutherland:1974:CTH, author = "Ivan E. Sutherland and Robert F. Sproull and Robert A. Schumacker", title = "A Characterization of Ten Hidden-Surface Algorithms", journal = "ACM Computing Surveys", volume = "6", number = "1", pages = "1--55", month = mar, year = "1974", coden = "CMSVAN", ISSN = "0010-4892", bibdate = "Mon Sep 26 21:02:43 1994", annote = "A classic paper; describes all the major hidden surface algorithms of the time, and gives a classification scheme.", keywords = "parallel processing; survey; visible surfaces", } @Article{Cohen:2002:survey, author = "D. Cohen-Or and Y. Chrysanthou and C. Silva and F. Durand", title = " A Survey of Visibility for Walkthrough Applications", year = "2003", journal = "IEEE Transactions on Visualization and Computer Graphics", volume = "9", number = "3", pages = "412--431" } % note = "Also available as http://www.cs.ucy.ac.cy/\~yiorgos/publications/survey_draft.pdf", @InProceedings{Whitted:1979:IIM, author = "T. Whitted", title = "An improved illumination model for shaded display", pages = "1--14", booktitle = "Computer Graphics (Special SIGGRAPH '79 Issue)", volume = "13", number = "3", year = "1979", month = aug, keywords = "algorithmic aspects, shading, animation/dynamic graphics, shaded images, raster graphics", } @Book{Szirmay-Kalos:1995a, author = "L{\'a}szl{\'o} {Szirmay-Kalos ed.} and G{\'a}bor M{\'a}rton and B. Dobos and T. Horv{\'a}th and P. Risztics and E. Kov{\'a}cs", title = "Theory of Three-Dimensional Computer Graphics", note = "English revision by Ian A. Stroud", publisher = "Akad{\'e}miai Kiad{\'o}", address = "Budapest, Hungary", month = sep, year = "1995", series = "Technical Sciences: Advances in Electronics", volume = "13", ISBN = "963-05-6911-6", library = "Uni of Newcastle, Auchmuty Library - 006.6 SZIR", citedby = "\cite{00000192}", } @InProceedings{Catmull:1975:CDC, author = "Edwin E. Catmull", title = "Computer Display of Curved Surfaces", booktitle = "Proceedings of the IEEE Conference on Computer Graphics, Pattern Recognition, and Data Structure", pages = "11--17", year = "1975", month = may, conference = "held in Los Angeles; 14-16 May 1975", keywords = "curves and surfaces, design and modeling, graphics, algorithms", } @Book{Weisstein:1999:CCE, author = "Eric W. Weisstein", title = "The {CRC} Concise Encyclopedia of Mathematics", publisher = "CRC Press", address = "2000 N.W. Corporate Blvd., Boca Raton, FL 33431-9868, USA", pages = "1969", year = "1999", ISBN = "0-8493-9640-9", LCCN = "QA5.W45 1999", bibdate = "Tue Apr 13 06:58:01 1999", price = "US\$79.95", acknowledgement = ack-mg, annote = "From Michel Goossens: ``This is a marvelous book for all (of us) who like mathematics. It might be interesting to note the quote from the start of the Acknowledgements, where the author spends a whole paragraph thanking Knuth for inventing \TeX{} (he started his book some ten years ago in Word \ldots{}), without which he could never have published his book. He also thanks Trevorrow (for Oz\TeX) and Drakos and Ross (for \LaTeX2HTML). His whole book is on the Web (with {\tt l2h}) \path=http://www.astro.virginia.edu/~eww6n/math/= (Eric's Treasure Troves of Science), although often the site is unavailable due to the many downlaod requests.''", } @InProceedings{EVL-2001-66, year = "2001", title = "Searching Triangle Strips Guided by Simplification Criterion", author = "O. Belmonte and J. Ribelles and I. Remolar and M. Chover", url = "http://visinfo.zib.de/EVlib/Show?EVL-2001-66", abstract = "Triangle strips are widely used as a method to accelerate the visualisation process of polygon models in interactive graphics applications. Another widely used method to improve drawing speed is the utilisation of multiresolution models. These models are constructed based on simplification algorithms. None of the current algorithms for searching strips contemplates the posterior simplification of the initial model. In this paper an algorithm for searching strips is presented. The triangles forming a strip are selected based on a simplification criterion according to the average quadratic error associated with the contraction of edges so that the model is simplified. In this manner the strips encountered are conserved as the model is being simplified. The strips generated in this way may be used to draw the polygon model in an incremental form or to transmit it progressively within a computer network.", editor = "V. Skala", keywords = "Triangle strip searching, interactive visualisation, simplification algorithms, multiresolution models.", booktitle = "WSCG 2001 Conference Proceedings", } @InProceedings{EVL-2001-262, pages = "91--100", year = "2001", title = "Tunneling for Triangle Strips in Continuous Level-of-Detail Meshes", author = "A. James Stewart", url = "http://visinfo.zib.de/EVlib/Show?EVL-2001-262", abstract = "This paper describes a method of building and maintaining a good set of triangle strips for both static and continuous level-of-detail (CLOD) meshes. For static meshes, the strips are better than those computed by the classic SGI and STRIPE algorithms. For CLOD meshes, the strips are maintained incrementally as the mesh topology changes. The incremental changes are fast and the number of strips is kept very small.", editor = "B. Watson and J. W. Buchanan", booktitle = "Proceedings of Graphics Interface", } @InProceedings{EVL-1996-290, pages = "319--326", year = "1996", title = "Optimizing Triangle Strips for Fast Rendering", author = "Francine Evans and Steven S. Skiena and Amitabh Varshney", url = "http://visinfo.zib.de/EVlib/Show?EVL-1996-290", abstract = "Almost all scientific visualization involving surfaces is currently do ne via triangles. The speed at which such triangulated surfaces can be displayed is crucial to interactive visualization and is bounded by the rate at which triangulated data can be sent to the graphics subsystem for rendering. Partitioning polygonal models into triangle strips can significantly reduce rendering times over transmitting each triangle individually. In this paper, we present new and efficient algorithms for constructing triangle strips from partially triangulated models, and experimental results showing these strips are 10--30\% better than those from previous codes. Further, we study the impact of larger buffer sizes and various queuing disciplines on the effectiveness of triangle strips.", organization = "IEEE", editor = "Roni Yagel and Gregory M. Nielson", booktitle = "IEEE Visualization '96", } @TechReport{ESV_triangle96, author = {F. Evans and S. Skiena and A. Varshney}, title = {Completing sequential triangulations is hard}, institution = {Dept. of Computer Science, State University of New York at Stony Brook}, year = {1996}, } @Article{Jones:1971:NAL, author = "C. B. Jones", title = "A New Approach to the `Hidden Line' Problem", year = "1971", month = aug, journal = "Computer Journal", volume = "14", number = "3", pages = "232--237", keywords = "hidden surface", } @InProceedings{Durand_CVPUEP2000, author = "Fr{\´{e}}do Durand and George Drettakis and Jo{\"e}lle Thollot and Claude Puech", title = "Conservative Visibility Preprocessing Using Extended Projections", pages = "239--248", editor = "Sheila Hoffmeyer", booktitle = "Proceedings of the Computer Graphics Conference 2000 ({SIGGRAPH}-00)", month = jul # " ~23--28", publisher = "ACMPress", address = "New York", year = "2000", } @InProceedings{Hudson97, author = "T. Hudson and D. Manocha and J. Cohen and M. Lin and K. Hoff and H. Zhang", title = "Accelerated Occlusion Culling using Shadow Frusta", year = "1997", booktitle = "Proceedings of the Thirteenth ACM Symposium on Computational Geometry", pages = "1--10", publisher = "ACM Press" } @InProceedings{Greene:1996:HPT, author = "Ned Greene", title = "Hierarchical Polygon Tiling with Coverage Masks", pages = "65--74", booktitle = "Proceedings of SIGGRAPH '96", year = "1996", month = aug, abstract = "We present a novel polygon tiling algorithm in which recursive subdivision of image space is driven by coverage masks that classify a convex polygon as inside, outside, or intersecting cells in an image hierarchy. This approach permits Warnock-style subdivision with its logarithmic search properties to be driven very efficiently by bit-mask operations. The resulting hierarchical polygon tiling algorithm performs subdivision and visibility computations very rapidly while only visiting cells in the image hierarchy that are crossed by visible edges in the output image. Visible samples are never overwritten. At 512x512 resolution, the algorithm tiles as rapidly as traditional incremental scan conversion, and at high resolution (e.g. 4096x4096) it is much faster, making it well suited to antialiasing by oversampling and filtering. For densely occluded scenes, we combine hierarchical tiling with the {\"h}ierarchical visibility{\" }algorithm to enable hierarchical object-space culling. When we tested this combination on a densely occluded model, it computed visibility on a 4096x4096 grid as rapidly as hierarchical z-buffering tiled a 512x512 grid, and it effectively antialiased scenes containing hundreds of thousands of visible polygons. The algorithm requires strict front-to-back traversal of polygons, so we represent a scene as a BSP tree or as an octree of BSP trees. When maintaining depth order of polygons is not convenient, we combine hierarchical tiling with hierarchical z-buffering, resorting to z-buffering only in regions of the screen where the closest object is not encountered first.", } @InProceedings{thibault87a, author = "William C. Thibault and Bruce F. Naylor", title = "Set Operations on Polyhedra Using Binary Space Partitioning Trees", pages = "153--162", booktitle = "Proceedings of SIGGRAPH '87", volume = "21", year = "1987", month = jul, keywords = "polyhedra, set operations, geometric modeling, geometric search, point location", } @Article{Plantinga85, author = "W. H. Plantinga and C. R. Dyer", title = "An Algorithm for Constructing the Aspect Graph", journal = "CS TR", volume = "627", publisher = "UNIV of Wisconsin --- Madison", month = dec, year = "1985", } @InProceedings{Crawford85, author = "C. G. Crawford", title = "Aspect Graphs and Robot Vision", year = "1985", booktitle = "Proceedings, {CVPR} '85 ({IEEE} Computer Society Conference on Computer Vision and Pattern Recognition, San Francisco, {CA}, June 10--13, 1985)", publisher = "IEEE", organization = "IEEE", series = "IEEE Publ. 85CH2145-1.", institution = "USNA", pages = "382--384", keywords = "IMAGE PART FORM, LARGE DIMENSIONALITY", } @Article{PLA90, author = "H. Plantinga and C. Dyer", title = "Visibility, Occlusion, and the Aspect Graph", journal = "International Journal of Computer Vision", volume = "5", number = "2", year = "1990", pages = "137--160", } @InProceedings{FOCS86*123, author = "W. H. Plantinga and C. R. Dyer", title = "An Algorithm for Constructing the Aspect Graph", pages = "123--131", booktitle = "27th Annual Symposium on Foundations of Computer Science", ISBN = "0-8186-0740-8", month = oct, publisher = "IEEE Computer Society Press", address = "Los Angeles, Ca., USA", year = "1986", } @InProceedings{egger92, title = "The scale space aspect graph", author = "D. W. Eggert and K. W. Bowyer and C. R. Dyer and H. I. Christensen and D. B. Goldgof", booktitle = "Proceedings. 1992 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No.92CH3168-2)", pages = "335--40", publisher = "IEEE Comput. Soc. Press Los Alamitos, CA, USA", year = "1992", organization = "IEEE", } @Article{EggertDavi1993a, author = "David W. Eggert and Kevin W. Bowyer and Charles R. Dyer and Henrik I. Christensen and Dmitry B. Goldgof", journal = "Pattern Analysis and Machine Intelligence", title = "The Scale Space Aspect Graph", year = "1993", document-size = "359.5 kbytes", url = "ftp://ftp.cs.wisc.edu/computer-vision/pami93-eggert.ps.Z", month = nov, number = "11", pages = "1114--1130", volume = "15", scope = "model", } @TechReport{MIT-LCS//MIT/LCS/TR-612, author = "S. Teng", title = "Combinational Aspects of Geometric Graphs", institution = "Massachusetts Institute of Technology, Laboratory for Computer Science", type = "Technical Report", number = "MIT-LCS//MIT/LCS/TR-612", pages = "13", month = may, year = "1994", abstract = "As a special case of our main result, we show that for all L$>$0, each k-nearest neighborhood graph in d dimensions excludes Kh as a depth in L minor if h=W (Ld-1). More generally, we prove that the overlap graphs defined by Miller, Teng, Thurston and Vavais [18] have this combinatorial property. By a construction of Plotkin, Rao and Smith [23], our result implies that overlap graphs have {"}good{"} cut-covers, answering an open question of Kaklamanis, Krizanc and Rao [12]. Consequently, overlap graphs can be emulated on hypercube graphs with a constant factor of slow down and on butterfly graphs with a factor of O(log*n) slow down. Therefore, computations on overlap graphs, such as finite-element and finite-difference methods on {"}well-conditioned{"} meshes and image processing on k- nearest neighborhood graphs, can be performed on hypercubic parallel machines with linear speed-up. Our result, in conjunction with a result of Plotkin, Rao and Smith, also yields a combinatorial proof to that overlap graphs have separators of sublinear size. We also show that with high probability, the Delaunay diagram, the relative neighborhood graph and the k-nearest neighborhood graph of a random point set exclude Kh as a depth L minor if h=W(L d/2 log n).", note = "Cost is \$12.", } @Book{Heckbert94-GGF, editor = "Paul Heckbert", year = "1994", title = "Graphics {Gems} {IV}", publisher = "Academic Press Professional", address = "Boston, MA", keywords = "Delaunay triangulation, finite elements, meshing, pixel luminance scaling", comments = "includes useful C and C++ code related to radiosity algorithms (Delaunay triangulation and pixel luminance scaling)", } @InCollection{Greene:1994:DIR, author = "Ned Greene", booktitle = "Graphics Gems IV", title = "Detecting Intersection of a Rectangular Solid and a Convex Polyhedron", publisher = "Academic Press", address = "Boston", pages = "74--82", year = "1994", keywords = "collision detection, octree, computational geometry", summary = "Presents an optimized technique to test for intersection between a convex polyhedron and a box. This is useful when comparing bounding boxes against a viewing frustum in a rendering program, for instance. Contains pseudocode.", } @InProceedings{Chen:1996:FPA, author = "{Han-Ming} Chen and {Wen-Teng} Wang", title = "The Feudal Priority Algorithm on Hidden-Surface Removal", pages = "55--64", booktitle = "Proceedings of SIGGRAPH '96", year = "1996", month = aug, abstract = "Development of a real-time shaded rendering approach for a frequently changing viewpoint or view vector is very important in the simulation of 3-D objects in Computer-Aided Design. A new approach is proposed in this paper to meet this demand in a very efficient manner. A pre-processing phase, in which a feudal priority tree is established for all polygons of an object, and a post-processing phase, in which a rendering priority list is searched for from the feudal priority tree for a new viewpoint or view vector, are included in our approach. The most time-consuming work is finished in the pre-processing phase which only has to be executed once for an object, and the relatively simple task is left to the post-processing phase, which is repeated when the viewpoint or view vector is changed. For the pre-processing phase, a static version and a dynamic version are proposed in this paper. The one-way priority relations of all polygons are computed in the former part of the dynamic pre-processing in a more efficient way than that in the static pre-processing, but the latter part of the dynamic pre-processing is still based on the static pre-processing. A new concept of {\"a}bsolute priority{\" }is introduced to systematically reduce the polygons in which a separating plane is to be searched for so the probability of finding the separating plane is much increased. This is the basis to implement another important concept of {\"s}eparating before splitting{\" }by which the polygon splittings are much reduced. Hence the efficiency in the pre-processing and the post-processing phases is highly increased.", } @InProceedings{Zhang97, title = "Visibility Culling Using Hierarchical Occlusion Maps", language = "en", month = aug, editor = "Turner Whitted", series = "Annual Conference Series", booktitle = "SIGGRAPH 97 Conference Proceedings", publisher = "Addison Wesley", pages = "77--88", year = "1997", url = "http://visinfo.zib.de/EVlib/Show?EVL-1997-147", author = "Hansong Zhang and Dinesh Manocha and Thomas Hudson and Kenneth E. {Hoff III}", abstract = "We present hierarchical occlusion maps (HOM) for visibility culling on complex models with high depth complexity. The culling algorithm uses an object space bounding volume hierarchy and a hierarchy of image space occlusion maps. Occlusion maps represent the aggregate of projections of the occluders onto the image plane. For each frame, the algorithm selects a small set of objects from the model as occluders and renders them to form an initial occlusion map, from which a hierarchy of occlusion maps is built. The occlusion maps are used to cull away a portion of the model not visible from the current viewpoint. The algorithm is applicable to all models and makes no assumptions about the size, shape, or type of occluders. It supports approximate culling in which small holes in or among occluders can be ignored. The algorithm has been implemented on current graphics systems and has been applied to large models composed of hundreds of thousands of polygons. In practice, it achieves significant speedup in interactive walkthroughs of models with high depth complexity.", organization = "ACM SIGGRAPH", note = "ISBN 0-89791-896-7", keywords = "visibility culling, interactive display, image pyramid, occlusion culling, hierarchical data structures", } @PhdThesis{Durand99-phd, author = "Fr{\'{e}}do Durand", month = jul, year = "1999", title = "3{D} Visibility: Analytical Study and Applications", address = "Grenoble, France", school = "Universite Joseph Fourier", } @InProceedings{EVL-2000-60, pages = "239--248", year = "2000", title = "Conservative Visibility Preprocessing Using Extended Projections", url = "http://visinfo.zib.de/EVlib/Show?EVL-2000-60", author = "Fr{\'{e}}do Durand and George Drettakis and Jo{\"{e}}lle Thollot and Claude Puech", abstract = "Visualization of very complex scenes can be significantly accelerated using occlusion culling. In this paper we present a visibility preprocessing method which efficiently computes potentially visible geometry for volumetric viewing cells. We introduce novel extended projection operators, which permits efficient and conservative occlusion culling with respect to all viewpoints within a cell, and takes into account the combined occlusion effect of multiple occluders. We use extended projection of occluders onto a set of projection planes to create extended occlusion maps; we show how to efficiently test occludees against these occlusion maps to determine occlusion with respect to the entire cell. We also present an improved projection operator for certain specific but important configurations. An important advantage of our approach is that we can re-project extended projections onto a series of projection planes (via an occlusion sweep), and accumulate occlusion information from multiple blockers. This new approach allows the creation of effective occlusion maps for previously hard-to-treat scenes such as leaves of trees in a forest. Graphics hardware is used to accelerate both the extended projection and reprojection operations. We present a complete implementation demonstrating significant speedup with respect to view-frustum culling only, without the computational overhead of on-line occlusion culling", keywords = "Occlusion culling, visibility determination, PVS", booktitle = "Computer Graphics (Proceedings of SIGGRAPH 2000)", } @InProceedings{scg97*421, author = "S. Rivi{\`e}re", title = "Dynamic visibility in polygonal scenes with the visibility complex", pages = "421--423", ISBN = "0-89791-878-9", booktitle = "Proceedings of the 13th International Annual Symposium on Computational Geometry ({SCG}-97)", month = jun # "~4--6", publisher = "ACM Press", address = "New York", year = "1997", } @InProceedings{SWAT::Vegter1990, title = "The Visibility Diagram: a Data Structure for Visibility Problems and Motion Planning", author = "Gert Vegter", booktitle = "{SWAT} 90, 2nd Scandinavian Workshop on Algorithm Theory", year = "1990", series = "Lecture Notes in Computer Science", volume = "447", publisher = "Springer", pages = "97--110", } @Article{Welzl:1985:CVG, author = "Emo Welzl", title = "Constructing the Visibility Graph for $n$-Line Segments in ${O}(n^2)$ Time", journal = "Information Processing Letters", volume = "20", number = "4", pages = "167--171", day = "10", month = may, year = "1985", coden = "IFPLAT", ISSN = "0020-0190", mrclass = "68U05", mrnumber = "86m:68135", bibdate = "Wed Nov 11 12:16:26 MST 1998", acknowledgement = ack-nhfb, affiliation = "Leiden State Univ, Inst of Applied Mathematics \& Computer Science, Leiden, Neth", affiliationaddress = "Leiden State Univ, Inst of Applied Mathematics \& Computer Science, Leiden, Neth", classification = "723; 921; C1160 (Combinatorial mathematics); C4190 (Other numerical methods)", corpsource = "Inst. for Inf. Proc., Tech. Univ. of Graz, Austria", journalabr = "Inf Process Lett", keywords = "computational geometry; computer programming --- Algorithms; Graph Theory; graph theory; line segments; mathematical techniques; n-line segments; nontransparent obstacles; O(n/sup 2/) time; shortest path; undirected graph; visibility graph", pubcountry = "Netherlands A01", treatment = "T Theoretical or Mathematical", } @InProceedings{EVL-2000-59, pages = "229--238", year = "2000", title = "Conservative Volumetric Visibility with Occluder Fusion", author = "Gernot Schaufler and Julie Dorsey and Xavier Decoret and Fran{\c{c}}ois X. Sillion", url = "http://visinfo.zib.de/EVlib/Show?EVL-2000-59", abstract = "Visibility determination is a key requirement in a wide range of graphics algorithms. This paper introduces a new approach to the computation of volume visibility, the detection of occluded portions of space as seen from a given region. The method is conservative and classifies regions as occluded only when they are guaranteed to be invisible. It operates on a discrete representation of space and uses the opaque interior of objects as occluders. This choice of occluders facilitates their extension into adjacent opaque regions of space, in essence maximizing their size and impact. Our method efficiently detects and represents the regions of space hidden by such occluders. It is the first one to use the property that occluders can also be extended into empty space provided this space is itself occluded from the viewing volume. This proves extremely effective for computing the occlusion by a set of occluders, effectively realizing occluder fusion. An auxiliary data structure represents occlusion in the scene and can then be queried to answer volume visibility questions. We demonstrate the applicability to visibility preprocessing for real-time walkthroughs and to shadow-ray acceleration for extended light sources in ray tracing, with significant acceleration in both cases.", booktitle = "Computer Graphics (Proceedings of SIGGRAPH 2000)", } @Book{Stolfi:1991:OPG, author = "J. Stolfi", title = "Oriented Projective Geometry: {A} Framework for Geometric Computations", publisher = "Academic Press", year = "1991", } @InProceedings{wonka00, pages = "71--82", year = "2000", title = "Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs", author = "Peter Wonka and Michael Wimmer and Dieter Schmalstieg", booktitle = "Proceedings of EUROGRAPHICS Workshop on Rendering", } @InProceedings{koltun00, year = "2000", title = "Virtual Occluders: An Efficient Intermediate PVS Representation", author = "Vladlen Koltun and Yiorgos Chrysanthou and Daniel Cohen-Or", booktitle = "Proceedings of EUROGRAPHICS Workshop on Rendering", } @Article{Cho:1999:IRT, author = "Franklin S. Cho and David Forsyth", title = "Interactive ray tracing with the visibility complex", journal = "Computers and Graphics", volume = "23", number = "5", pages = "703--717", month = oct, year = "1999", coden = "COGRD2", ISSN = "0097-8493", bibdate = "Sat Oct 21 14:27:20 MDT 2000", url = "http://www.elsevier.nl/gej-ng/10/13/20/24/34/34/abstract.html; http://www.elsevier.nl/gej-ng/10/13/20/24/32/34/article.pdf", acknowledgement = ack-nhfb, } @InProceedings{koltun01, year = "2001", title = "Hardware-Accelerated From-Region Visibility Using a Dual Ray Space", author = "Vladlen Koltun and Yiorgos Chrysanthou and Daniel Cohen-Or", booktitle = "Proceedings of the 12th EUROGRAPHICS Workshop on Rendering", }