标题: Parallel and Accurate Poisson Disk Sampling on Arbitrary Surfaces [打印本页] 作者: 彬彬 时间: 2012-1-4 17:10 标题: Parallel and Accurate Poisson Disk Sampling on Arbitrary Surfaces 1 Introduction
Sampling plays an important role in a variety of graphics applications.
Among existing sampling methods, Poisson disk sampling is
popular thanks to its useful statistical property in distribution and
the absence of aliasing artifacts. Although many promising algorithms
have been proposed for multi-dimensional sampling in Euclidean
space, very few research studies have been reported with regard
to the problem of generating Poisson disks on surfaces due to
the complicated nature of the surface. This still remains a challenge
due to the following reasons: first, a surface is a two-dimensional
manifold that has arbitrary topology and complicated geometry, and
is embedded in R3 or even higher dimensional space. Second, the
exact geodesic distance should be used to enforce the minimum distance
constraint between any pair of samples. Third, the algorithm
should be parallelized such that it can make full use of all available
threads. Last but not least, the generated samples should be randomly
and uniformly distributed on surfaces, and exhibit the blue
noise pattern without bias. Wei [2008] pioneered a parallel Poisson
disk sampling algorithm by subdividing the sample domain into
grid cells and drawing samples concurrently from multiple cells that
are sufficiently far apart to avoid conflicts. Bowers et al. [2010] extendedWei’s
algorithm to 3D surfaces. Their method is highly efficient,
allowing sampling on large-scale models at interactive speed.
However, the generated distribution is not fully random since the
sequence of processing the phase groups follows a predefined order.
Moreover, the approximate geodesic computation in their approach
results in large errors in models with rich features and thus
compromises the sampling quality.
This paper presents a parallel and unbiased algorithm for direct
Poisson disk sampling on arbitrary surfaces. Our contributions are
twofold. First, we propose a new technique for parallelizing the
Poisson disk sampling. Rather than the conventional approaches
that explicitly partition the spatial domain to generate the samples
in parallel, our approach assigns each sample candidate a random
and unique priority that is unbiased with regard to the distribution.
Hence, multiple threads can process the candidates simultaneously
and resolve conflicts by checking the given priority values. Second,
our algorithm is unbiased as it uniformly and randomly distributes
the Poisson disks on arbitrary surfaces. All the computations of
our algorithm are purely based on the intrinsic metric and are independent
of the embedding space. Therefore, it works for arbitrary
surfaces in Rn. To our knowledge, this is the first unbiased and parallel