An intrinsic algorithm for parallel Poisson disk sampling on arbitrary surfaces
Poisson disk sampling has excellent spatial and spectral properties, and plays an important role in a variety of visual computing. Although many promising algorithms have been proposed for multidimensional sampling in euclidean space, very few studies have been reported with regard to the problem of...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/99298 http://hdl.handle.net/10220/17366 |
| _version_ | 1824456549484986368 |
|---|---|
| author | Ying, Xiang He, Ying Xin, Shi-Qing Sun, Qian |
| author2 | School of Computer Engineering |
| author_facet | School of Computer Engineering Ying, Xiang He, Ying Xin, Shi-Qing Sun, Qian |
| author_sort | Ying, Xiang |
| collection | NTU |
| description | Poisson disk sampling has excellent spatial and spectral properties, and plays an important role in a variety of visual computing. Although many promising algorithms have been proposed for multidimensional sampling in euclidean space, very few studies have been reported with regard to the problem of generating Poisson disks on surfaces due to the complicated nature of the surface. This paper presents an intrinsic algorithm for parallel Poisson disk sampling on arbitrary surfaces. In sharp contrast to the conventional parallel approaches, our method neither partitions the given surface into small patches nor uses any spatial data structure to maintain the voids in the sampling domain. Instead, 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. Our algorithm guarantees that the generated Poisson disks are uniformly and randomly distributed without bias. It is worth noting that our method is intrinsic and independent of the embedding space. This intrinsic feature allows us to generate Poisson disk patterns on arbitrary surfaces in IRn. To our knowledge, this is the first intrinsic, parallel, and accurate algorithm for surface Poisson disk sampling. Furthermore, by manipulating the spatially varying density function, we can obtain adaptive sampling easily. |
| first_indexed | 2025-02-19T03:55:52Z |
| format | Journal Article |
| id | ntu-10356/99298 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-02-19T03:55:52Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/992982020-05-28T07:18:01Z An intrinsic algorithm for parallel Poisson disk sampling on arbitrary surfaces Ying, Xiang He, Ying Xin, Shi-Qing Sun, Qian School of Computer Engineering DRNTU::Engineering::Computer science and engineering Poisson disk sampling has excellent spatial and spectral properties, and plays an important role in a variety of visual computing. Although many promising algorithms have been proposed for multidimensional sampling in euclidean space, very few studies have been reported with regard to the problem of generating Poisson disks on surfaces due to the complicated nature of the surface. This paper presents an intrinsic algorithm for parallel Poisson disk sampling on arbitrary surfaces. In sharp contrast to the conventional parallel approaches, our method neither partitions the given surface into small patches nor uses any spatial data structure to maintain the voids in the sampling domain. Instead, 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. Our algorithm guarantees that the generated Poisson disks are uniformly and randomly distributed without bias. It is worth noting that our method is intrinsic and independent of the embedding space. This intrinsic feature allows us to generate Poisson disk patterns on arbitrary surfaces in IRn. To our knowledge, this is the first intrinsic, parallel, and accurate algorithm for surface Poisson disk sampling. Furthermore, by manipulating the spatially varying density function, we can obtain adaptive sampling easily. 2013-11-07T06:16:26Z 2019-12-06T20:05:31Z 2013-11-07T06:16:26Z 2019-12-06T20:05:31Z 2013 2013 Journal Article Ying, X., Xin, S.-Q., Sun, Q., & He, Y. (2013). An Intrinsic Algorithm for Parallel Poisson Disk Sampling on Arbitrary Surfaces. IEEE Transactions on Visualization and Computer Graphics, 19(9), 1425-1437. 1077-2626 https://hdl.handle.net/10356/99298 http://hdl.handle.net/10220/17366 10.1109/TVCG.2013.63 en IEEE transactions on visualization and computer graphics |
| spellingShingle | DRNTU::Engineering::Computer science and engineering Ying, Xiang He, Ying Xin, Shi-Qing Sun, Qian An intrinsic algorithm for parallel Poisson disk sampling on arbitrary surfaces |
| title | An intrinsic algorithm for parallel Poisson disk sampling on arbitrary surfaces |
| title_full | An intrinsic algorithm for parallel Poisson disk sampling on arbitrary surfaces |
| title_fullStr | An intrinsic algorithm for parallel Poisson disk sampling on arbitrary surfaces |
| title_full_unstemmed | An intrinsic algorithm for parallel Poisson disk sampling on arbitrary surfaces |
| title_short | An intrinsic algorithm for parallel Poisson disk sampling on arbitrary surfaces |
| title_sort | intrinsic algorithm for parallel poisson disk sampling on arbitrary surfaces |
| topic | DRNTU::Engineering::Computer science and engineering |
| url | https://hdl.handle.net/10356/99298 http://hdl.handle.net/10220/17366 |
| work_keys_str_mv | AT yingxiang anintrinsicalgorithmforparallelpoissondisksamplingonarbitrarysurfaces AT heying anintrinsicalgorithmforparallelpoissondisksamplingonarbitrarysurfaces AT xinshiqing anintrinsicalgorithmforparallelpoissondisksamplingonarbitrarysurfaces AT sunqian anintrinsicalgorithmforparallelpoissondisksamplingonarbitrarysurfaces AT yingxiang intrinsicalgorithmforparallelpoissondisksamplingonarbitrarysurfaces AT heying intrinsicalgorithmforparallelpoissondisksamplingonarbitrarysurfaces AT xinshiqing intrinsicalgorithmforparallelpoissondisksamplingonarbitrarysurfaces AT sunqian intrinsicalgorithmforparallelpoissondisksamplingonarbitrarysurfaces |