Entry Taubin:1994:DAR from tog.bib

Last update: Sat Sep 5 02:07:01 MDT 2009                Valid HTML 3.2!

Index sections

Top | Symbols | Numbers | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Taubin:1994:DAR,
  author =       "Gabriel Taubin",
  title =        "Discrete Approximations for Rasterizing Implicit
                 Curves",
  journal =      j-TOG,
  volume =       "13",
  number =       "1",
  pages =        "3--42",
  month =        jan,
  year =         "1994",
  CODEN =        "ATGRDF",
  ISSN =         "0730-0301",
  bibdate =      "Sat Jan 06 15:42:26 1996",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/0730-0301/174531.html",
  abstract =     "In this article we present new algorithms for
                 rasterizing implicit curves, i.e., curves represented
                 as level sets of functions of two variables.
                 Considering the pixels as square regions of the plane,
                 a ``correct'' algorithm should paint those pixels whose
                 centers lie at less than half the desired line width
                 from the curve. A straightforward implementation,
                 scanning the display array evaluating the Euclidean
                 distance from the center of each pixel to the curve, is
                 impractical, and a standard quad-tree-like recursive
                 subdivision scheme is used instead. Then we attack the
                 problem of testing whether or not the Euclidean
                 distance from a point to an implicit curve is less than
                 a given threshold. For the most general case, when the
                 implicit function is only required to have continuous
                 first-order derivatives, we show how to reformulate the
                 test as an unconstrained global root-finding problem in
                 a circular domain. For implicit functions with
                 continuous derivatives up to order $k$ we introduce an
                 approximate distance of order $k$. The approximate
                 distance of order $k$ from a point to an implicit curve
                 is asymptotically equivalent to the Euclidean distance
                 and provides a sufficient test for a polynomial of
                 degree $k$ not to have roots inside a circle. This is
                 the main contribution of the article. By replacing the
                 Euclidean distance test with one of these approximate
                 distance tests, we obtain a practical rendering
                 algorithm, proven to be correct for algebraic curves.
                 To speed up the computation we also introduce
                 heuristics, which used in conjunction with low-order
                 approximate distances almost always produce equivalent
                 results. The behavior of the algorithms is analyzed,
                 both near regular and singular points, and several
                 possible extensions and applications are discussed.",
  acknowledgement = ack-nhfb,
  keywords =     "algorithms; design; theory",
  subject =      "{\bf I.3.3}: Computing Methodologies, COMPUTER
                 GRAPHICS, Picture/Image Generation, Display algorithms.
                 {\bf I.3.5}: Computing Methodologies, COMPUTER
                 GRAPHICS, Computational Geometry and Object Modeling,
                 Curve, surface, solid, and object representations. {\bf
                 J.6}: Computer Applications, COMPUTER-AIDED
                 ENGINEERING, Computer-aided design (CAD).",
}

Related entries