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

algorithm for distributing Poisson disks on arbitrary surfaces.

tc

非常感谢，管理员设置了需要对新回复进行审核，您的帖子通过审核后将被显示出来，现在将转入主题

菜刀吻电线

呵呵，很好，方便罗。

tc

响应天帅号召，顶

晃晃

佩服，好多阿 ，哈哈

奇

真不错,全存下来了.