Computing the Discrepancy with Applications to Supersampling Patterns

David P. Dobkin; David Eppstein; Don P. Mitchell

doi:10.1145/234535.234536

Computing the Discrepancy with Applications to Supersampling Patterns

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

Research output: Contribution to journal › Article › peer-review

62 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 language	English (US)
Pages (from-to)	354-376
Number of pages	23
Journal	ACM Transactions on Graphics
Volume	15
Issue number	4
DOIs	https://doi.org/10.1145/234535.234536
State	Published - 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

Access to Document

10.1145/234535.234536

Cite this

@article{0eea6fc3048f4b6a8e36e6aaea2db2cd,

title = "Computing the Discrepancy with Applications to Supersampling Patterns",

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.",

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",

author = "Dobkin, {David P.} and David Eppstein and Mitchell, {Don P.}",

year = "1996",

month = oct,

doi = "10.1145/234535.234536",

language = "English (US)",

volume = "15",

pages = "354--376",

journal = "ACM Transactions on Graphics",

issn = "0730-0301",

publisher = "Association for Computing Machinery (ACM)",

number = "4",

}

TY - JOUR

T1 - Computing the Discrepancy with Applications to Supersampling Patterns

AU - Dobkin, David P.

AU - Eppstein, David

AU - Mitchell, Don P.

PY - 1996/10

Y1 - 1996/10

N2 - 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.

AB - 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.

KW - Algorithms

KW - Discrepancy

KW - Experimentation

KW - F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems-geometrical problems and computations

KW - I.3.3 [Computer Graphics]. Picture/Image Generation-antialiasing

KW - Ray-tracing

UR - http://www.scopus.com/inward/record.url?scp=0030264248&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030264248&partnerID=8YFLogxK

U2 - 10.1145/234535.234536

DO - 10.1145/234535.234536

M3 - Article

AN - SCOPUS:0030264248

SN - 0730-0301

VL - 15

SP - 354

EP - 376

JO - ACM Transactions on Graphics

JF - ACM Transactions on Graphics

IS - 4

ER -

Computing the Discrepancy with Applications to Supersampling Patterns

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this