Efficient Sorting and Searching in Rendering Algorithms

Information

• Publication Type: Invited Talk
• Workgroup(s)/Project(s):
  • GameTools
• Date: 2006
• Event: Eurographics 2006 Tutorial T4
• Keywords: Visibility, Sorting and Searching, Rendering

Abstract

In this 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.

Additional Files and Images

Weblinks

No further information available.

BibTeX

@talk{havran-2006-tut,
  title =      "Efficient Sorting and Searching in Rendering Algorithms",
  author =     "Vlastimil Havran and Jir\'{i} Bittner",
  year =       "2006",
  abstract =   "In this 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.",
  event =      "Eurographics 2006 Tutorial T4",
  keywords =   "Visibility, Sorting and Searching, Rendering",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2006/havran-2006-tut/",
}