Efficient Sorting and Searching

in Rendering Algorithms

 

Eurographics 2006 Tutorial T4

 

 

Date: Monday, 4th September 2006

Time: 14:00 - 17:30

Location: Tutorial Room 8 (HS 8)

 

Organizer

Vlastimil Havran, Czech Technical University

 

Speakers

Vlastimil Havran, Czech Technical University

Jiri Bittner, Vienna University of Technology

 

Abstract

In the proposed tutorial we would like to highlight the connection between rendering algorithms and sorting and searching as classical problems studied in computer science. We will provide both theoretical and empirical evidence that for many rendering techniques most time is spent by sorting and searching. In particular we will discuss problems and solutions for visibility computation, density estimation, and importance sampling. For each problem we mention its specific issues such as dimensionality of the search domain or online versus offline searching. We will present the underlying data structures and their enhancements in the context of specific rendering algorithms such as ray shooting, photon mapping, and hidden surface removal.

 

Speakers' Background

 

Vlastimil Havran

is an assistant professor at the Czech Technical University in Prague since February 2006. He defended his Ph.D. dissertation on ray shooting algorithms in 2001 at the Czech Technical University in Prague. Later he joined the computer graphics group at Max-Planck-Institute for Informatics in Saarbruecken. He became a research associate at the same institute in 2003. He has contributed to the topic of sorting and searching by his dissertation on ray shooting algorithms which started the area of interactive ray tracing. In addition to sorting and searching he worked on various other topics in rendering.

 

Jiri Bittner

holds a Ph.D. in Computer Science from the Czech Technical University in Prague. His main research interests include visibility preprocessing, occlusion culling, real-time rendering, and computational geometry. He has also been active in development of two commercial products dealing with real-time rendering of large scenes. He is currently affiliated with the Vienna University of Technology and the Czech Technical University in Prague.

 

 

 

 

Tutorial Contents

 

Slides . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . .. . . . . . . . . . 5

Overview . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . . . ... . . . . . . . . 5

Introduction to Rendering . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 6

Introduction to Sorting and Searching . . . . .. . . . . . .. . . . . . . . . . . . . . . . 8

Hierarchical data structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

Ray shooting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 15

Hidden surface removal . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . .. . . . . . . 22

Visibility culling . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 25

Photon Maps and Irradiance Caching . . . . . . . . . . . . . . .. . . . . . . . . . . . 34

Ray Maps . . . . . . . . . . . . . . . . . . . . . . . . . .. .. . . . . . . . . . . . . . . . . . . . . . . .40

Other methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . 43

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .  . . . . . . 45

Sorting and Searching, Hierarchical Data Structures . . . . . . . . . . . . . .46

Ray Shooting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 48

Hidden Surface Removal . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

Visibility Culling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . . .  . . . . . . . . .64

Photon Mapping, Irradiance Caching, and Ray Maps . . . . . .. . . . . . . . 71

Other Publications on Rendering with Sorting and/or Searching . . . . 74

 

Tutorial Slides

 

The updated version of this tutorial presented at Eurographics 2006 can be found under the following URL: http://www.cgg.cvut.cz/~havran/eg2006tut/tut4eg06.pdf.

 

Acknowledgements

 

We would like to thank Robert Herzog, Jaroslav Krivanek, Michael Wimmer, Peter Wonka, Tommer Leyvand, David Luebke, and Hansong Zhang for providing us various materials used in the tutorial. This work has been partially supported by the EU under the project no. IST-2-004363 (GameTools) and by the Ministry of Education, Youth and Sports of the Czech Republic under the research program LC-06008 (Center for Computer Graphics).