Computing the Discrepancy with Applications to Supersampling Patterns

David P. Dobkin, David Eppstein, Don P. Mitchell

Research output: Contribution to journalArticle

46 Scopus citations

Abstract

Patterns used for supersampling in graphics have been analyzed from statistical and signal-processing viewpoints. We present an analysis based on a type of isotropic discrepancy - how good patterns are at estimating the area in a region of defined type. We present algorithms for computing discrepancy relative to regions that are defined by rectangles, halfplanes, and higher-dimensional figures. Experimental evidence shows that popular supersampling patterns have discrepancies with better asymptotic behavior than random sampling, which is not inconsistent with theoretical bounds on discrepancy.

Original languageEnglish (US)
Pages (from-to)354-376
Number of pages23
JournalACM Transactions on Graphics
Volume15
Issue number4
DOIs
StatePublished - Oct 1996

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design

Keywords

  • Algorithms
  • Discrepancy
  • Experimentation
  • F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems-geometrical problems and computations
  • I.3.3 [Computer Graphics]. Picture/Image Generation-antialiasing
  • Ray-tracing

Fingerprint Dive into the research topics of 'Computing the Discrepancy with Applications to Supersampling Patterns'. Together they form a unique fingerprint.

Cite this