Fast Maximal Poisson-Disk Samplin g by Randomized Tiling TONG WANG, REIJI SUDA, IST, University of Tokyo Maximal Poisson Disk Samplin g Poisson-disk sampling Definition: Poisson-disk sampling pattern is a group of samples with no two of th em within a specified distance r. Considered a good property in many applications. r Random d Sample Poisson-disk Essentials in many computer graphics applications. Texture generation, Object placement, Rendering and anti-aliasing, Image stipp ling, etc. Blue noise property One reason that Poisson-disk sampling is good for many applications is becaus e of its blue noise spectral properties [1].

Power Frequency Samples Power Spectrum Radial Mean [1] Gamito M N, Maddock S C. Accurate multidimensional Poisson-disk sampling[J]. ACM Transactions on Graphics (TOG), 2009, 29(1): 8. Maximal Poisson-disk samples (MPS) A Poisson-disk sample set is maximal co verage iff. For sample set as X in domain D. r Guaranteed the quality of samples. No big gaps and clusters. Evenly distributed sampling density. Generate Poisson-disk samples Dart throw Relaxation

r Often need many iterations to reach maximal coverage. Tile based method Sample Plane 1 Tile Set 0.8 0.7 0.7 0.6 0.6 0.6 0.5 0.5 0.5 0.4

0.4 0.4 0.3 0.3 0.3 0.2 0.2 0.2 0.1 0.1 0.3 0.3 0.4 0.5 0.6 0.7 0.8

0.9 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.2 0.3 0.4 0.4 0.5 0.5

0.6 1 0 0.1 0.4 0.8 0.7 0.2 0.2 0.5 0.1 0.6 0.8 0 0.7 0.9 0 0.8

1 0.6 0.8 0.9 1 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.7 0 0.2 0.3

0.4 0.5 0.6 0.7 0.8 1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.9 0.8 0.8 0.8

0.7 0.7 0.7 0.6 0.6 0.6 0.5 0.5 0.5 0.4 0.4 0.4 0.3 0.3 0.3 0.2 0.2

0.2 0.1 0.1 0 0.9 0.1 1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.9

0.1 1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.9 0.1 1 0.2 0.3

0.4 0.5 0.6 0.7 0.8 0.9 1 1 Preprocessing. Generate tile set, etc. Tile on the plane. 1 0 0 Choose a tile from tile set. 0.1 1 0

0.1 0.9 1 0 0 0.9 0.9 0 0.1 0.8 0.1 1 0 0 0.7 0.2 0.1 1

0 0.3 1 0.9 0.1 1 0.9 1 0.9 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0 0 0.9

0.1 1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.9 0.9 0.8 0.8 0.8 0.7 0.7

0.7 0.6 0.6 0.6 0.5 0.5 0.5 0.4 0.4 0.4 0.3 0.3 0.3 0.2 0.2 0.2 0.1 0.1

0 0.1 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0 0 0.9 0.1 1 0.2 0.3

0.4 0.5 0.6 0.7 0.8 Tile based method Extremely fast to fill the sample plane. But Preprocessing takes a long time. Regular artifacts are not desirable in many applications. 1 0.6 0.9 0.55 0.8 0.7

0.5 0.6 0.45 0.5 0.4 0.4 0.3 0.35 0.2 0.1 0.3 0 0 0 0.1 0.2 0.3 0.4 0.5 0.6

0.7 0.8 0.9 1 20 40 60 80 100 Add more randomness in tiling Design the tile sets and tiling techniques: [1][2]. Affect preprocessing and tiling performance. Transform and rotate tiles to make tiles non-periodic: [3]. But [3] didnt deal with sample conflicts, which is not acceptable in many applic ations.

Randomly subdivide the space and fetch tiles on-the-fly. Our method. [1]. Kopf J, Cohen-Or D, Deussen O, et al. Recursive Wang tiles for real-time blue noise[M]. ACM, 2006. [2]. Wachtel F, Pilleboue A, Coeurjolly D, et al. Fast tile-based adaptive sampling with user-specified Fourier spectra[J]. ACM Transactions on Graphics (TOG), 2014, 33(4): 56. [3]. Kalantari N K, Sen P. Fast generation of approximate blue noise point sets[C]//Computer Graphics Forum. Blackwell Publishing Ltd, 2012, 31(4): 1529-1535.Transactions on Graphics (TOG), 2012, 31(6): 171. Performance and Regularity For Poisson-disk sample generation: Regular Sampling Performance Regular Tiling Approximate Tiling [3] Ours PixelPie[2] Flat Quadtree Dart Throw[5] Dart Throw Wang Tiles[1]

Regularity Artifact Capacity Constrained Relaxation[4] Lloyds Relaxation [1]. [Kopf J, Cohen-Or D, Deussen O, et al. Recursive Wang tiles for real-time blue noise[M]. ACM, 2006. [2]. Ip C Y, Yalin M A, Luebke D, et al. Pixelpie: Maximal poisson-disk sampling with rasterization[C]//Proceedings of the 5th High-Performance Graphics Conference. ACM, 2013: 17-26. [3]. Kalantari N K, Sen P. Fast generation of approximate blue noise point sets[C]//Computer Graphics Forum. Blackwell Publishing Ltd, 2012, 31(4): 15291535.Transactions on Graphics (TOG), 2012, 31(6): 171. [4]. Balzer M, Schlmer T, Deussen O. Capacity-constrained point distributions: a variant of Lloyd's method[M]. ACM, 2009. [5]. Ebeida M S, Mitchell S A, Patney A, et al. A Simple Algorithm for Maximal PoissonDisk Sampling in High Dimensions[C]//Computer Graphics Forum. Blackwell Publishing Ltd, 2012, 31(2pt4): 785-794. Our algorithm Algorithm Outline Prepare a pre-generated MPS pattern.

KD-tree based randomized tiling (KDRT) is divide-and-conquer based. Divide: Subdivide the sampling plane using KD-tree. Each leaf node square (2d case) is called a building block of the entire sampling plane. Tile: Fill each building block with points clipped from a pre-generated MPS patt ern. Conquer: Eliminate conflicts on the edge, and insert new samples in the gap to ensure maximal coverage property. Divide and clipping from MPS pattern are randomized, no regular artifacts. Conquering process is determined and easy to convergence. Prepare pre-generated pattern Use any unbiased Poisson-disk sampling method to generate a pattern. Here we use algorithm described in [1] to generate a pattern. Define a scale factor ratio as how many times samples that the final sampling pl ane contains compared with the pattern. The final sample set size is controlled by manipulate this parameter. Pattern Result Ratio=2

Result Ratio=4 [1]. Ebeida M S, Mitchell S A, Patney A, et al. A Simple Algorithm for Maximal PoissonDisk Sampling in High Dimensions[C]//Computer Graphics Forum. Blackwell Publishing Ltd, 2012, 31(2pt4): 785-794. Divide: Subdivide the sampling plane Building blocks of the samplin g plane. Conflict area that will be processed in conquering. Tiling: Filling building block with samples Tiling: Filling building block with samples 1.2 MPS Pattern Tilled Sampling Domain 1 Tile Tile Clipping Tile Tile Cl i

Tile 0.6 pp in g Tile pp Cl i Clipping 0.8 0.4 in g 0.2 Tile Tile 0 0 (a) 0.1 0.2

0.3 0.4 0.5 (b) 0.6 0.7 0.8 0.9 1 Tiling: Filling building block with samples (a) (b) Conquering: Outline Conquer Tile A : Eliminated Conflict Area Tile B Tile A

Tile B : Inserted Conquering Conquered Result Conquering: Necessary Redundant height height+2r width+2r width (a) (b) Conquering: Gap detection Gap detection[1]: A gap exist among three disks centered at i,j,k ( i,j,k C ), if the C ), if the circumcenter c of the triangle i,j,k is not covered by any disks. i i j k

k j [1]. Yan D M, Wonka P. Gap processing for adaptive maximal Poisson-disk sampling[J]. ACM Transactions on Graphics (TOG), 2013, 32(5): 148. Conquering: Elimination Processing yellow point. Eliminate red point to avoid conflicts. Insert blue point to ensure maximal cov erage. Conquering: Insertion Notice that there are circumstances that if GapDetectionAndInsertion being appl ied on all sample points p C ), if the C , it is not guaranteed that all gaps could be cover ed. (1). Processing yellow disk (2). Red disk eliminated gap generated (3). Green disk inserted in gap

(a) Gaps that cannot be covered by single insertion Conquering: Insertion Notice that there are circumstances that if GapDetectionAndInsertion being appl ied on all sample points p C ), if the C , it is not guaranteed that all gaps could be cover ed. (1). Processing yellow disk (2). Red disk eliminated gap generated (b) Gaps that cannot be detected by current processing sample (3). No gaps detected, No insertion Conquering: Insertion All samples are marked as gap detector New gaps detected by the green disk k i j All samples are marked as gap detector

Gap detected by triangle i,j,k while dealing one of the vertex Conquering: Insertion All gaps can be detected this way. Type N Gap Type N-1 Gap Type 1 Gap No Gap Results Results Results Results Time taken by each procedure to generate 1 million samples. Combining MPS sample sets 9 MPS set each 1017625 samples Vertical Zipping Horizontal Zipping Result with 8795941 samples

Vertical Zipping Result 3 MPS set each 2991817 samples Combining Size CPU Time (ms) 3751372 85 4689216 102 5861520 144 7326900 158 9158625 202 Conclusion KDST is a tile based method that can generate maximal Poisson-disk samples. KDST is a divide and conquer method, including:

Divide: Randomly divide the sample plane into building blocks. Tiling: Fill the building blocks with samples clipped from a pre-generated patter n. Conquer: Eliminate conflict points and insert new points in the gap. Conquering step can be used to combine MPS sample sets together to form a la rger one. KDST performs fast on CPU and GPU, and is very easy to implement. Thank you! Thanks for all reviewers for your constructive comments. Special thanks to Anjul Patney for his efforts to help the author to get the U. S. visa.