“Curl Noise Jittering” by Bærentzen, Lyngby and Martínez
Conference:
Type(s):
Title:
- Curl Noise Jittering
Session/Category Title: Technical Papers Fast-Forward
Presenter(s)/Author(s):
Abstract:
We propose a method for implicitly generating blue noise point sets. Our method is based on the observations that curl noise vector fields are volume-preserving and that jittering can be construed as moving points along the streamlines of a vector field. We demonstrate that the volume preservation keeps the points well separated when jittered using a curl noise vector field. At the same time, the anisotropy that stems from regular lattices is significantly reduced by such jittering. In combination, these properties entail that jittering by curl noise effectively transforms a regular lattice into a point set with blue noise properties. Our implicit method does not require computing the point collection in advance. This makes our technique valuable when an arbitrarily large set of points with blue noise properties is needed. We compare our method to several other methods based on jittering as well as other methods for blue noise point set generation. Finally, we show several applications of curl noise jittering in two and three dimensions.
References:
[1]
Abdalla G. M. Ahmed, Markus Hadwiger, Mikhail Skopenkov, and Peter Wonka. 2023. Analysis and synthesis of digital dyadic sequences. https://doi.org/10.48550/arXiv.2306.06925 arxiv:2306.06925 [cs.GR]
[2]
Abdalla G. M. Ahmed, Hui Huang, and Oliver Deussen. 2015. AA patterns for point sets with controlled spectral properties. ACM transactions on graphics 34, 6 (2015), 212:1–212:8. https://doi.org/10.1145/2816795.2818139
[3]
Abdalla G. M. Ahmed, Till Niese, Hui Huang, and Oliver Deussen. 2017. An adaptive point sampler on a regular lattice. ACM Transactions on Graphics 36, 4 (2017), 138:1–138:13. https://doi.org/10.1145/3072959.3073588
[4]
Abdalla G. M. Ahmed, Jing Ren, and Peter Wonka. 2022. Gaussian blue noise. ACM Transactions on Graphics 41, 6 (2022), 260:1–260:15. https://doi.org/10.1145/3550454.3555519
[5]
Abdalla G. M. Ahmed and Peter Wonka. 2020. Screen-space blue-noise diffusion of Monte Carlo sampling error via hierarchical ordering of pixels. ACM Transactions on Graphics 39, 6 (2020), 244:1–244:15. https://doi.org/10.1145/3414685.3417881
[6]
Abdalla G. M. Ahmed and Peter Wonka. 2021. Optimizing dyadic nets. ACM Transactions on Graphics 40, 4 (2021), 141:1–141:17. https://doi.org/10.1145/3450626.3459880
[7]
Michael Balzer, Thomas Schlömer, and Oliver Deussen. 2009. Capacity-constrained point distributions: A variant of Lloyd’s method. ACM Transactions on Graphics 28, 3 (2009), 86:1–86:8. https://doi.org/10.1145/1531326.1531392
[8]
Lukas Bogunia, Stefan Buchen, and Kerstin Weinberg. 2022. Microstructure characterization and stochastic modeling of open-cell foam based on μ CT-image analysis. GAMM-Mitteilungen 45, 3-4 (2022), e202200018. https://doi.org/10.1002/gamm.202200018
[9]
Robert Bridson. 2007. Fast Poisson disk sampling in arbitrary dimensions. In SIGGRAPH 2007 Sketches. 22. https://doi.org/10.1145/1278780.1278807
[10]
Robert Bridson, Jim Houriham, and Marcus Nordenstam. 2007. Curl-noise for procedural fluid flow. ACM Transactions on Graphics 26, 3 (2007), 46:1–46:3. https://doi.org/10.1145/1276377.1276435
[11]
Kenneth Chiu, Changyaw Wang, and Peter Shirley. 1994. Multi-jittered sampling. In Graphics Gems. Elsevier, 370–374.
[12]
Per Christensen, Andrew Kensler, and Charlie Kilpatrick. 2018. Progressive multi-jittered sample sequences. Computer Graphics Forum 37, 4 (2018), 21–33. https://doi.org/10.1111/cgf.13472
[13]
Robert L Cook. 1986. Stochastic sampling in computer graphics. ACM Transactions on Graphics 5, 1 (1986), 51–72. https://doi.org/10.1145/7529.8927
[14]
Massimiliano Corsini, Paolo Cignoni, and Roberto Scopigno. 2012. Efficient and flexible sampling with blue noise properties of triangular meshes. IEEE Transactions on Visualization and Computer Graphics 18, 6 (2012), 914–924. https://doi.org/10.1109/TVCG.2012.34
[15]
Sabrina Dammertz. 2009. Rank-1 Lattices in Computer Graphics. Ph. D. Dissertation. Universität Ulm. https://doi.org/10.18725/OPARU-1068
[16]
Fernando De Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. 2012. Blue noise through optimal transport. ACM Transactions on Graphics 31, 6 (2012), 171:1–171:11. https://doi.org/10.1145/2366145.2366190
[17]
Daniel Dunbar and Greg Humphreys. 2006. A spatial data structure for fast Poisson-disk sample generation. ACM Transactions on Graphics 25, 3 (2006), 503–508. https://doi.org/10.1145/1141911.1141915
[18]
Mohamed S. Ebeida, Andrew A. Davidson, Anjul Patney, Patrick M. Knupp, Scott A. Mitchell, and John D. Owens. 2011. Efficient maximal Poisson-disk sampling. ACM Transactions on Graphics 30, 4 (2011), 49:1–49:12. https://doi.org/10.1145/2010324.1964944
[19]
Raanan Fattal. 2011. Blue-noise point sampling using kernel density model. ACM Transactions on Graphics 30, 4 (2011), 48:1–48:12. https://doi.org/10.1145/2010324.1964943
[20]
Jens Feder. 1980. Random sequential adsorption. Journal of Theoretical Biology 87, 2 (1980), 237–254. https://doi.org/10.1016/0022-5193(80)90358-6
[21]
L. Fejes. 1942. Über die dichteste Kugellagerung. Mathematische Zeitschrift 48, 1 (1942), 676–684. https://doi.org/10.1007/BF01180035
[22]
Robert W. Floyd and Louis Steinberg. 1976. An adaptive algorithm for spatial gray-scale. Proceedings of the Society of Information Display 17, 2 (1976), 75–77.
[23]
Jeppe Revall Frisvad and Geoff Wyvill. 2007. Fast high-quality noise. In GRAPHITE 2007. 243–248. https://doi.org/10.1145/1321261.1321305
[24]
Andrew S. Glassner. 1995. Principles of Digital Image Synthesis. Morgan Kaufmann. Two volumes.
[25]
John H. Halton. 1964. Algorithm 247: Radical-inverse quasi-random point sequence. Commun. ACM 7, 12 (1964), 701–702. https://doi.org/10.1145/355588.365104
[26]
J. M. Hammersley and D. C. Handscomb. 1964. Monte Carlo Methods. Chapman and Hall.
[27]
John C. Hart. 1996. Sphere tracing: A geometric method for the antialiased ray tracing of implicit surfaces. The Visual Computer 12, 10 (1996), 527–545. https://doi.org/10.1007/s003710050084
[28]
Daniel Heck, Thomas Schlömer, and Oliver Deussen. 2013. Blue noise sampling with controlled aliasing. ACM Transactions on Graphics 32, 3 (2013), 25:1–25:12. https://doi.org/10.1145/2487228.2487233
[29]
Stefan Hiller, Oliver Deussen, and Alexander Keller. 2001. Tiled blue noise samples. In Vision, Modeling, and Visualization (VMV).
[30]
Min Jiang, Yahan Zhou, Rui Wang, Richard Southern, and Jian Jun Zhang. 2015. Blue noise sampling using an SPH-based method. ACM Transactions on Graphics 34, 6 (2015), 211:1–211:11. https://doi.org/10.1145/2816795.2818102
[31]
Andrew Kensler. 2013. Correlated Multi-Jittered Sampling. Technical Memo 13-01. Pixar. https://graphics.pixar.com/library/MultiJitteredSampling/paper.pdf
[32]
R Victor Klassen. 2000. Filtered jitter. Computer Graphics Forum 19, 4 (2000), 223–230. https://doi.org/10.1111/1467-8659.00459
[33]
Johannes Kopf, Daniel Cohen-Or, Oliver Deussen, and Dani Lischinski. 2006. Recursive Wang tiles for real-time blue noise. ACM Transactions on Graphics 25, 3 (2006), 509–518. https://doi.org/10.1145/1179352.1141916
[34]
Ares Lagae and Philip Dutré. 2005. A procedural object distribution function. ACM Transactions on Graphics 24, 4 (2005), 1442–1461. https://doi.org/10.1145/1095878.1095888
[35]
Ares Lagae and Philip Dutré. 2008. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum 27, 1 (2008), 114–129. https://doi.org/10.1111/j.1467-8659.2007.01100.x
[36]
Ares Lagae, Sylvain Lefebvre, Rob Cook, Tony DeRose, George Drettakis, David S Ebert, John P Lewis, Ken Perlin, and Matthias Zwicker. 2010. A survey of procedural noise functions. Computer Graphics Forum 29, 8 (2010), 2579–2600. https://doi.org/10.1111/j.1467-8659.2010.01827.x
[37]
Daniel L. Lau, Robert Ulichney, and Gonzalo R. Arce. 2003. Blue and green noise halftoning models. IEEE Signal Processing Magazine 20, 4 (2003), 28–38. https://doi.org/10.1109/MSP.2003.1215229
[38]
John-Peter Lewis. 1984. Texture synthesis for digital painting. Computer Graphics (SIGGRAPh ’84) 18, 3 (1984), 245–252. https://doi.org/10.1145/800031.808605
[39]
John-Peter Lewis. 1989. Algorithms for solid noise synthesis. Computer Graphics (SIGGRAPH ’89) 23, 3 (1989), 263–270. https://doi.org/10.1145/74333.74360
[40]
Stuart Lloyd. 1982. Least squares quantization in PCM. IEEE Transactions on Information Theory 28, 2 (1982), 129–137. https://doi.org/10.1109/TIT.1982.1056489
[41]
Andrea Luongo, Viggo Falster, Mads Brix Doest, Macarena Mendez Ribo, Eyþór Rúnar Eiríksson, David B Pedersen, and Jeppe Revall Frisvad. 2020. Microstructure control in 3D printing with digital light processing. Computer Graphics Forum 39, 1 (2020), 347–359. https://doi.org/10.1111/cgf.13807
[42]
Jonàs Martínez, Jérémie Dumas, and Sylvain Lefebvre. 2016. Procedural Voronoi foams for additive manufacturing. ACM Transactions on Graphics 35, 4 (2016), 44:1–44:12. https://doi.org/10.1145/2897824.2925922
[43]
Nelson L Max. 1981. Vectorized procedural models for natural terrain: Waves and islands in the sunset. Computer Graphics (SIGGRAPH ’81) 15, 3 (1981), 317–324. https://doi.org/10.1145/965161.806820
[44]
Johannes Meng, Marios Papas, Ralf Habel, Carsten Dachsbacher, Steve Marschner, Markus Gross, and Wojciech Jarosz. 2015. Multi-scale modeling and rendering of granular materials. ACM Transactions on Graphics 34, 4 (2015), 49:1–49:13. https://doi.org/10.1145/2766949
[45]
Victor Ostromoukhov. 2001. A simple and efficient error-diffusion algorithm. In SIGGRAPH 2001. 567–572. https://doi.org/10.1145/383259.383326
[46]
Victor Ostromoukhov. 2007. Sampling with polyominoes. ACM Transactions on Graphics 26, 3 (2007), 78:1–78:6. https://doi.org/10.1145/1276377.1276475
[47]
Victor Ostromoukhov, Charles Donohue, and Pierre-Marc Jodoin. 2004. Fast hierarchical importance sampling with blue noise properties. ACM Transactions on Graphics 23, 3 (2004), 488–495. https://doi.org/10.1145/1015706.1015750
[48]
Steven G. Parker, James Bigler, Andreas Dietrich, Heiko Friedrich, Jared Hoberock, David Luebke, David McAllister, Morgan McGuire, Keith Morley, Austin Robison, and Martin Stich. 2010. OptiX: a general purpose ray tracing engine. ACM Transactions on Graphics 29, 4 (2010), 66:1–66:13. https://doi.org/10.1145/1778765.1778803
[49]
Loïs Paulin, David Coeurjolly, Jean-Claude Iehl, Nicolas Bonneel, Alexander Keller, and Victor Ostromoukhov. 2021. Cascaded Sobol’ sampling. ACM Transactions on Graphics 40, 6 (2021), 275:1–275:13. https://doi.org/10.1145/3478513.3480482
[50]
Ken Perlin. 1985. An image synthesizer. Computer Graphics (SIGGRAPH ’85) 19, 3 (1985), 287–296. https://doi.org/10.1145/325165.325247
[51]
Ken Perlin. 2002. Improving noise. In SIGGRAPH 2002. 681–682. https://doi.org/10.1145/566570.566636
[52]
Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2023. Physically Based Rendering: From Theory to Implementation (fourth ed.). MIT Press.
[53]
Adrien Pilleboue, Gurprit Singh, David Coeurjolly, Michael Kazhdan, and Victor Ostromoukhov. 2015. Variance analysis for Monte Carlo integration. ACM Transactions on Graphics 34, 4 (2015), 1–14. https://doi.org/10.1145/2766930
[54]
Hongxing Qin, Yi Chen, Jinlong He, and Baoquan Chen. 2017. Wasserstein blue noise sampling. ACM Transactions on Graphics 36, 5 (2017), 168:1–168:13. https://doi.org/10.1145/3119910
[55]
Marvin R. Querry. 1985. Optical Constants. Technical Report CRDC-CR-85034. University of Missouri.
[56]
Carl Runge. 1895. Über die numerische Auflösung von Differentialgleichungen. Math. Ann. 46, 2 (1895), 167–178. https://doi.org/10.1007/BF01446807
[57]
Bruce Schachter. 1981. Long crested wave models. In Image Modeling. Elsevier, 327–341. https://doi.org/10.1016/B978-0-12-597320-5.50024-3
[58]
Thomas Schlömer and Oliver Deussen. 2011. Accurate spectral analysis of two-dimensional point sets. Journal of Graphics, GPU, and Game Tools 15, 3 (2011), 152–160. https://doi.org/10.1080/2151237X.2011.609773
[59]
Il’ya Meerovich Sobol’. 1967. On the distribution of points in a cube and the approximate evaluation of integrals. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki 7, 4 (1967), 784–802. https://doi.org/10.1016/0041-5553(67)90144-9
[60]
Thomas Theußl, Torsten Möller, and Meister Eduard Gröller. 2001. Optimal regular volume sampling. In Proceedings of Visualization 2001 (VIS’01). IEEE, 91–98 + 546. https://doi.org/10.1109/VISUAL.2001.964498
[61]
Salvatore Torquato and Frank H. Stillinger. 2010. Jammed hard-particle packings: From Kepler to Bernal and beyond. Reviews of Modern Physics 82, 3 (2010), 2633–2672. https://doi.org/10.1103/RevModPhys.82.2633
[62]
Robert A Ulichney. 1988. Dithering with blue noise. Proc. IEEE 76, 1 (1988), 56–79. https://doi.org/10.1109/5.3288
[63]
Florent Wachtel, Adrien Pilleboue, David Coeurjolly, Katherine Breeden, Gurprit Singh, Gaël Cathelin, Fernando De Goes, Mathieu Desbrun, and Victor Ostromoukhov. 2014. Fast tile-based adaptive sampling with user-specified Fourier spectra. ACM Transactions on Graphics 33, 4 (2014), 56:1–56:11. https://doi.org/10.1145/2601097.2601107
[64]
Xiaoqun Wang and Ian H. Sloan. 2008. Low discrepancy sequences in high dimensions: How well are their projections distributed?J. Comput. Appl. Math. 213, 2 (2008), 366–386. https://doi.org/10.1016/j.cam.2007.01.005
[65]
Li-Yi Wei. 2008. Parallel Poisson disk sampling. ACM Transactions on Graphics 27, 3 (2008), 20:1–20:9. https://doi.org/10.1145/1360612.1360619
[66]
Steven Worley. 1996. A cellular texture basis function. In SIGGRAPH ’96. 291–294. https://doi.org/10.1145/237170.237267
[67]
Dong-Ming Yan, Jian-Wei Guo, Bin Wang, Xiao-Peng Zhang, and Peter Wonka. 2015. A survey of blue-noise sampling and its applications. Journal of Computer Science and Technology 30, 3 (2015), 439–452. https://doi.org/10.1007/s11390-015-1535-0
[68]
Cem Yuksel. 2015. Sample elimination for generating Poisson disk sample sets. Computer Graphics Forum 34, 2 (2015), 25–32. https://doi.org/10.1111/cgf.12538
