J. A. Quinn, F. C. Langbein, R. R. Martin, G. Elber
In: M.-S. Kim, K. Shimada (eds), Proc. Geometric Modeling and Processing,
Springer LNCS, 4077:465-484, 2006.
ISBN 354036711X.
[DOI: 10.1007/11802914_33] [Preprint] [CiteSeer]
Low-discrepancy point distributions exhibit excellent uniformity properties while avoiding regular patterns. For applications like sampling and rendering, such distributions minimise the number of artefacts introduced by regular sampling. However, known low-discrepancy distributions are aimed at particular shapes like squares and spheres, and little work has been done for general surfaces in 3D. To address this issue we propose an algorithm which generates low-discrepancy point distributions on arbitrary surfaces by converting the 2D surface sampling problem into a 1D line sampling problem using a space-filling curve mapped onto the surface. To ensure that the 1D distribution gives a 2D low-discrepancy distribution on the surface, we employ a corrective approach similar to histogram equalisation. Our experiments suggest that this approach efficiently generates low-discrepancy distributions of good quality on arbitrary parametric surfaces. Comparisons with well-known low-discrepancy sequences aimed at sampling particular surfaces show that our algorithm produces nearly as good results, while being more general. Furthermore, our approach allows us to control the local density of the distribution, for example placing more points where the surface curvature is greater, which would be of use in applications such as surface mesh generation. We also discuss potential applications, which not only build upon the quality and flexibility of the distribution itself, but also on the ordering and locality properties provided by the space-filling curve.
@INPROCEEDINGS{Quinn2006,
author = {Jonathan A. Quinn and Frank C. Langbein and Ralph R.
Martin and Gershon Elber},
title = {Density-Controlled Sampling of Parametric Surfaces
Using Adaptive Space-Filling Curves},
booktitle = {Proc. Geometric Modeling and Processing},
year = 2006,
editor = {M.-S. Kim and K. Shimada},
volume = 4077,
series = {LNCS},
pages = {465-484},
address = {Berlin, Heidelberg},
publisher = {Springer},
isbn = 3540367116,
doi = {10.1007/11802914_33},
url = {http://www.langbein.org/research/points/sampling/quinn2006/},
abstract = {Low-discrepancy point distributions exhibit
excellent uniformity properties for sampling in
applications such as rendering and measurement. We
present an algorithm for generating low-discrepancy
point distributions on arbitrary parametric surfaces
using the idea of converting the 2D sampling problem
into a 1D problem by adaptively mapping a
space-filling curve onto the surface. The 1D
distribution takes into account the parametric
mapping by employing a corrective approach similar
to histogram equalisation to ensure that it gives a
2D low-discrepancy point distribution on the
surface. This also allows for control over the local
density of the distribution, e.g. to place points
more densely in regions of higher curvature. To
allow for parametric distortion, the space-filling
curve is generated adaptively to cover the surface
evenly. Experiments show that this approach
efficiently generates low-discrepancy distributions
on arbitrary parametric surfaces and creates nearly
as good results as well-known low-discrepancy
sampling methods designed for particular surfaces
like planes and spheres. However, we also show that
machine-precision limitations may require surface
reparameterisation in addition to adaptive
sampling.},
}
Density-Controlled Sampling of Parametric Surfaces Using Adaptive Space-Filling Curves,http://www.langbein.org/research/points/sampling/quinn2006 by Frank C Langbein [ 6/December/2008, 19:19].
Copyright © 1995-2012, Frank C Langbein.
Except where otherwise stated, this web site, Ex Tenebris Scientia, by Frank C Langbein is licensed under a Creative Commons Attribution-Non-Commercial-Share Alike 2.0 UK: England & Wales License.
