J. A. Quinn, F. C. Langbein, R. R. Martin, G. Elber. Density-Controlled Sampling of Parametric Surfaces Using Adaptive Space-Filling Curves. In: M.-S. Kim, K. Shimada (eds), Proc. Geometric Modeling and Processing, Springer LNCS, 4077:465-484, 2006. [DOI:10.1007/11802914_33]
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.
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.