computer graphics, poisson disk, sampling
Poisson disk point sets are “ideally” generated through a process of dart throwing. The naive dart throwing algorithm is extremely expensive if a maximal set is desired, however. In this paper we present a hierarchical dart throwing procedure which produces point sets that are equivalent to naive dart throwing, but is very fast. The procedure works by intelligently excluding areas known to be fully covered by existing samples. By excluding covered regions, the probability of accepting a thrown dart is greatly increased. Our algorithm is conceptually simple, performs dart throwing in O(N) time and memory, and produces a maximal point set up to the precision of the numbers being used.
Original Publication Citation
David Cline, Kenric B. White, Parris Egbert, "Poisson Disk Point Sets by Hierarchical Dart Throwing", Symposium on Interactive Ray Tracing, pp. 129-132, Sept. 27.
BYU ScholarsArchive Citation
Cline, David; Egbert, Parris K.; and White, Kenric B., "Poisson Disk Point Sets by Hierarchical Dart Throwing" (2007). All Faculty Publications. 237.
Physical and Mathematical Sciences
© 2007 Institute of Electrical and Electronics Engineers
Copyright Use Information