Dart Throwing on Surfaces

David Cline, Stefan Jeschke, Anshuman Razdan, Kenric White, Peter Wonka
Dart Throwing on Surfaces
Computer Graphics Forum, 28(4):1217-1226, June 2009. [paper] [video]

Information

Abstract

In this paper we present dart throwing algorithms to generate maximal Poisson disk point sets directly on 3D surfaces. We optimize dart throwing by efficiently excluding areas of the domain that are already covered by existing darts. In the case of triangle meshes, our algorithm shows dramatic speed improvement over comparable sampling methods. The simplicity of our basic algorithm naturally extends to the sampling of other surface types, including spheres, NURBS, subdivision surfaces, and implicits. We further extend the method to handle variable density points, and the placement of arbitrary ellipsoids without overlap. Finally, we demonstrate how to adapt our algorithm to work with geodesic instead of Euclidean distance. Applications for our method include fur modeling, the placement of mosaic tiles and polygon remeshing.

Additional Files and Images

Additional images and videos

image: Example of tiles placed with our algorithm.

Additional files

Weblinks

No further information available.

BibTeX

@article{cline-09-poisson,
  title =      "Dart Throwing on Surfaces",
  author =     "David Cline and Stefan Jeschke and Anshuman Razdan and
               Kenric White and Peter Wonka",
  year =       "2009",
  abstract =   "In this paper we present dart throwing algorithms to
               generate maximal Poisson disk point sets directly on 3D
               surfaces. We optimize dart throwing by efficiently excluding
               areas of the domain that are already covered by existing
               darts. In the case of triangle meshes, our algorithm shows
               dramatic speed improvement over comparable sampling methods.
               The simplicity of our basic algorithm naturally extends to
               the sampling of other surface types, including spheres,
               NURBS, subdivision surfaces, and implicits. We further
               extend the method to handle variable density points, and the
               placement of arbitrary ellipsoids without overlap. Finally,
               we demonstrate how to adapt our algorithm to work with
               geodesic instead of Euclidean distance. Applications for our
               method include fur modeling, the placement of mosaic tiles
               and polygon remeshing.",
  month =      jun,
  journal =    "Computer Graphics Forum",
  number =     "4",
  volume =     "28",
  pages =      "1217--1226",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2009/cline-09-poisson/",
}