Parameterization and Surface Texture
Instant Stippling on 3D Scenes
Lei Ma,
Jianwei Guo,
Dong-Ming Yan,
Hanqiu Sun, Yanyun Chen,
Lei Ma
State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences
University of Chinese Academy of Sciences
Search for more papers by this authorJianwei Guo
NLPR, Institute of Automation, Chinese Academy of Sciences
University of Chinese Academy of Sciences
Search for more papers by this authorDong-Ming Yan
NLPR, Institute of Automation, Chinese Academy of Sciences
University of Chinese Academy of Sciences
Search for more papers by this authorYanyun Chen
State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences
University of Chinese Academy of Sciences
Search for more papers by this authorLei Ma,
Jianwei Guo,
Dong-Ming Yan,
Hanqiu Sun, Yanyun Chen,
Lei Ma
State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences
University of Chinese Academy of Sciences
Search for more papers by this authorJianwei Guo
NLPR, Institute of Automation, Chinese Academy of Sciences
University of Chinese Academy of Sciences
Search for more papers by this authorDong-Ming Yan
NLPR, Institute of Automation, Chinese Academy of Sciences
University of Chinese Academy of Sciences
Search for more papers by this authorYanyun Chen
State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences
University of Chinese Academy of Sciences
Search for more papers by this authorcorresponding author
Abstract
In this paper, we present a novel real-time approach to generate high-quality stippling on 3D scenes. The proposed method is built on a precomputed 2D sample sequence called incremental Voronoi set with blue-noise properties. A rejection sampling scheme is then applied to achieve tone reproduction, by thresholding the sample indices proportional to the inverse target tonal value to produce a suitable stipple density. Our approach is suitable for stippling large-scale or even dynamic scenes because the thresholding of individual stipples is trivially parallelizable. In addition, the static nature of the underlying sequence benefits the frame-to-frame coherence of the stippling. Finally, we propose an extension that supports stipples of varying sizes and tonal values, leading to smoother spatial and temporal transitions. Experimental results reveal that the temporal coherence and real-time performance of our approach are superior to those of previous approaches.
Supporting Information
| Filename | Description |
|---|---|
| cgf13565-sup-0001-S1.zip4.2 MB | Supplement Material |
Please note: The publisher is not responsible for the content or functionality of any supporting information supplied by the authors. Any queries (other than missing content) should be directed to the corresponding author for the article.
References
- Ahmed A., Guo J., Yan D.-M., Franceschi J.-Y., Zhang X., Deussen O.: A simple push-pull algorithm for blue-noise sampling. IEEE Trans. on Vis. and Comp. Graphics 23, 12 (2017), 2496–2508. 2
- Ahmed A. G. M., Huang H., Deussen O.: AA patterns for point sets with controlled spectral properties. ACM Trans. on Graphics (Proc. SIGGRAPH Asia) 34, 6 (2015), 212: 1–212:8. 2
- Ahmed A. G. M., Niese T., Huang H., Deussen O.: An adaptive point sampler on a regular lattice. ACM Trans. on Graphics (Proc. SIGGRAPH) 36, 4 (2017), 138: 1–138:13. 2, 9, 10
- Ahmed A., Perrier H., Coeurjolly D., Ostromoukhov V., Guo J., Yan D., Huang H., Deussen O.: Low-discrepancy blue noise sampling. ACM Trans. on Graphics (Proc. SIGGRAPH Asia) 35, 6 (nov 2016), 247: 1–247:13. 2
- Bayer B. E.: An optimum method for two-level rendition of continuous-tone pictures. IEEE Int. Conf. on Communications 26 (1973), 11–15. 2
- Bridson R.: Fast poisson disk sampling in arbitrary dimensions. In SIGGRAPH Sketches (2007), p. 22. 2
- Balzer M., Schl T., Deussen O.: Capacity-constrained point distributions : A variant of ***lloyd's method. ACM Trans. on Graphics (Proc. SIGGRAPH) (2009). 2
- Baer A., Tietjen C., Bade R., Preim B.: Hardware-accelerated Stippling of Surfaces derived from Medical Volume Data. In EurographicsIEEE-VGTC Symposium on Visualization (2007), Museth K., Moeller T., Ynnerman A., (Eds.), The Eurographics Association. 2
- Bowers J., Wang R., Wei L.-Y., Maletz D.: Parallel Poisson disk sampling with spectrum analysis on surfaces. ACM Trans. on Graphics (Proc. SIGGRAPH Asia) 29, 6 (2010), 166: 1–166:10. 2
- Corsini M., Cignoni P., Scopigno R.: Efficient and flexible sampling with blue noise properties of triangular meshes. IEEE Trans. on Vis. and Comp. Graphics 18, 6 (2012), 914–924. 2, 6
- Cline D., Jeschke S., White K., Razdan A., Wonka P.: Dart throwing on surfaces. Computer Graphics Forum (Proc. EGSR) 28, 4 (2009), 1217–1226. 2
- Cook R. L.: Stochastic sampling in computer graphics. ACM Trans. on Graphics 5, 1 (1986), 69–78. 2
- Chen Z., Yuan Z., Choi Y. K., Liu L., Wang W.: Variational blue noise sampling. IEEE Trans. on Vis. and Comp. Graphics 18, 10 (2012), 1784. 2
- Du Q., Faber V., Gunzburger M.: Centroidal Voronoi tessellations: applications and algorithms. SIAM Review 41 (1999), 637–676. 2
- de Goes F., Breeden K., Ostromoukhov V., Desbrun M.: Blue noise through optimal transport. ACM Trans. on Graphics (Proc. SIGGRAPH Asia) 31, 6 (2012), 171. 2
- Deussen O., Hiller S., van Overveld C. W. A. M., Strothotte T.: Floating points: A method for computing stipple drawings. Computer Graphics Forum 19, 3 (2000), 41–50. 2
- Deussen O., Isenberg T.: Halftoning and stippling. In Image and Video-Based Artistic Stylisation. Springer London, 2013, pp. 45–61. 2
10.1007/978-1-4471-4519-6_3 Google Scholar
- Deussen O., Spicker M., Zheng Q.: Weighted linde-buzogray stippling. ACM Trans. on Graphics (Proc. SIGGRAPH Asia) 36, 6 (2017), 233: 1–233:12. 2
- Dippé M. A. Z., Wold E. H.: Antialiasing through stochastic sampling. ACM Trans. on Graphics (Proc. SIGGRAPH) 19, 3 (July 1985), 69–78. 2
10.1145/325165.325182 Google Scholar
- Ebeida M. S., Mitchell S. A., Patney A., Davidson A. A., Owens J. D.: A simple algorithm for maximal poisson-disk sampling in high dimensions. Computer Graphics Forum (Proc. EUROGRAPHICS) 31, 2 (2012), 785–794. 2
- Ebeida M. S., Patney A., Mitchell S. A., Davidson A., Knupp P. M., Owens J. D.: Efficient maximal Poisson-disk sampling. ACM Trans. on Graphics (Proc. SIGGRAPH) 30, 4 (2011), 49: 1–49:12. 2
- Fattal R.: Blue-noise point sampling using kernel density model. ACM Trans. on Graphics (Proc. SIGGRAPH) 30, 4 (2011), 48: 1–48:12. 2
- Gamito M. N., Maddock S. C.: Accurate multidimensional Poisson-disk sampling. ACM Trans. on Graphics 29, 1 (2009), 8: 1–8:19. 2
- Guo J., Yan D.-M., Jia X., Zhang X.: Efficient maximal Poisson-disk sampling and remeshing on surfaces. Computers & Graphics 46, 6–8 (2015), 72–79. 2
- Halton J. H.: On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numerische Mathematik 2, 1 (1960), 84–90. 9
10.1007/BF01386213 Google Scholar
- Jones T. R.: Efficient generation of Poisson-disk sampling patterns. Journal of Graphics Tools 11, 2 (2006), 27–36. 2
10.1080/2151237X.2006.10129217 Google Scholar
- Kopf J., Cohen-Or D., Deussen O., Lischinski D.: Recursive wang tiles for real-time blue noise. ACM Trans. on Graphics (Proc. SIGGRAPH) 25, 3 (2006), 509–518. 2, 9
- KrÃijger J., Westermann R.: Efficient stipple rendering. In IADIS Computer Graphics and Visualization (Lisbon, 2007), pp. 19–26. 3
- Lagae A., Dutre P.: A comparison of methods for generating poisson disk distributions. Computer Graphics Forum 27, 1 (2008), 114–129. 2
- Li H., Mould D.: Contrast-aware halftoning. Computer Graphics Forum 29, 2 (may 2010), 273–280. 7
- Li H., Mould D.: Structure-preserving stippling by priority-based error diffusion. In Proceedings of Graphics Interface 2011 (School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, 2011), GI ‘11, Canadian Human-Computer Communications Society, pp. 127–134. 7
- Lu A., Morris C. J., Taylor J., Ebert D. S., Hansen C., Rheingans P., Hartner M.: Illustrative interactive stipple rendering. IEEE Trans. on Vis. and Comp. Graphics 9, 2 (2003), 127–138. 1
- Lévy B., Petitjean S., Ray N., Maillot J.: Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 3 (July 2002), 362–371. 1, 9
- Lawonn K., Viola I., Preim B., Isenberg T.: A survey of surface-based illustrative rendering for visualization. Computer Graphics Forum 37 (2018). 3
- Martín D., Arroyo G., Rodríguez A., Isenberg T.: A survey of digital stippling. Computers & Graphics 67 (2017), 24–44. 1, 2
- Ma L., Chen Y., Qian Y., Sun H.: Incremental voronoi sets for instant stippling. The Visual Computer 34, 6 (Jun 2018), 863–873. 2, 3, 9
- Mitchell S. A., Ebeida M. S., Awad M. A., Park C., Patney A., Rushdi A. A., Swiler L. P., Manocha D., Wei L.-Y.: Spoke-darts for high-dimensional blue-noise sampling. ACM Trans. on Graphics 37, 2 (2018), 22: 1–22:20. 2
- Medeiros E., Ingrid L., Pesco S., Silva C.: Fast adaptive blue noise on polygonal surfaces. Graphical Models 76, 1 (2014), 17–29. 2, 6
- Mitsa T., Parker K. J.: Digital halftoning technique using a blue-noise mask. J. Opt. Soc. Am. A 9, 11 (Nov. 1992), 1920–1929. 2
10.1364/JOSAA.9.001920 Google Scholar
- Ostromoukhov V., Donohue C., Jodoin P.-M.: Fast hierarchical importance sampling with blue noise properties. ACM Trans. on Graphics (Proc. SIGGRAPH) 23, 3 (2004), 488–495. 2, 3
- Ostromoukhov V.: Sampling with polyominoes. ACM Trans. Graph. 26, 3 (July 2007), 78. 2
- Pastor O. M., Freudenberg B., Strothotte T.: Real-time animated stippling. IEEE Computer Graphics & Applications 23, 4 (2003), 62–68. 1, 3
- Praun E., Hoppe H., Webb M., Finkelstein A.: Real-time hatching. Proceedings of Siggraph (2001), 581. 3
- Pastor O. M., Strotthote T.: Graph-based point relaxation for 3d stippling. In Mexican International Conference in Computer Science (2004), pp. 141–150. 3
- Palacios J., Zhang E.: Rotational symmetry field design on surfaces. ACM Trans. on Graphics (Proc. SIGGRAPH) 26, 3 (2007), 55: 1–55:10. 3
- Quan W., Guo J., Yan D.-M., Meng W., Zhang X.: Analyzing surface sampling patterns using the localized pair correlation function. Computational Visual Media 2, 3 (2016), 219–230. 2
10.1007/s41095-016-0050-8 Google Scholar
- Suarez J., Belhadj F., Boyer V.: Real-time 3d rendering with hatching. The Visual Computer (2016), 1–16. 3
- Sawhney R., Crane K.: Boundary first flattening. ACM Trans. Graph. 37, 1 (Dec. 2017), 5: 1–5:14. 1, 9
- Secord A.: Weighted Voronoi stippling. Proceedings of the second international symposium on Non-photorealistic animation and rendering - NPAR ‘02 1 (2002), 37. 2
10.1145/508530.508537 Google Scholar
- Sousa M. C., Foster K., Wyvill B., Samavati F.: Precise Ink Drawing of 3D Models . Computer Graphics Forum 22, 3 (2003), 369–379. 3
- Sobol’ I. M.: 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. 9
- Sumner R. W., Popović J.: Deformation transfer for triangle meshes. ACM Trans. on Graphics (Proc. SIGGRAPH) 23, 3 (2004), 399–405. 10
- Ulichney R.: Dithering with Blue Noise. MIT Press, 1987. 2
- Ulichney R. A.: Void-and-cluster method for dither array generation. In Human Vision, Visual Processing, and Digital Display IV (sep 1993), Allebach J. P., Rogowitz B. E., (Eds.), Vol. 1913, SPIE. 2, 9
10.1117/12.152707 Google Scholar
- Vanderhaeghe D., Barla P., Thollot J., Sillion F. X.: Dynamic Point Distribution for Stroke-based Rendering. In Rendering Techniques (2007), Kautz J., Pattanaik S., (Eds.), The Eurographics Association. 1, 2
- Wang Z., Bovik A. C., Sheikh H. R., Simoncelli E. P.: Image quality assessment: from error visibility to structural similarity. IEEE Transactions on Image Processing 13, 4 (April 2004), 600–612. 7
- White K. B., Cline D., Egbert P. K.: Poisson disk point sets by hierarchical dart throwing. In Proceedings of the IEEE Symposium on Interactive Ray Tracing (2007), pp. 129–132. 2
- Wei L.-Y.: Parallel poisson disk sampling. ACM Trans. on Graphics (Proc. SIGGRAPH) 27, 3 (2008), 20: 1–20:9. 2
- Wei L.-Y.: Multi-class blue noise sampling. ACM Trans. on Graphics (Proc. SIGGRAPH) 29, 4 (2010), 79: 1–79:8. 2
- Wang X., Le T. H., Ying X., Sun Q., He Y.: User controllable anisotropic shape distribution on 3d meshes. Computational Visual Media 2, 4 (2016), 305–319. 3
10.1007/s41095-016-0057-1 Google Scholar
- Wachtel F., Pilleboue A., Coeurjolly D., Breeden K., Singh G., Cathelin G., de Goes F., Desbrun M., Ostromoukhov V.: Fast tile-based adaptive sampling with user-specified fourier spectra. ACM Trans. on Graphics (Proc. SIGGRAPH) 33, 4 (2014), 56: 1–56:11. 2
- Wei L.-Y., Wang R.: Differential domain analysis for ***non-uniform sampling. ACM Transactions on Graphics (TOG) 30, 4 (2011), 50. 6, 7
- Xu Y., Liu L., Gotsman C., Gortler S. J.: Computers & Graphics Capacity-Constrained Delaunay Triangulation for point distributions. Computers and Graphics 35, 3 (2011), 510–516. 2
- Yan D.-M., Guo J., Wang B., Zhang X., Wonka P.: A survey of blue-noise sampling and its applications. J. Comput. Sci. Technol 30, 3 (2015), 439–452. 2
- Yuan X., Nguyen M. X., Zhang N., Chen B.: Stippling and Silhouettes Rendering in Geometry-Image Space. In Eurographics Symposium on Rendering (2005) (2005), Bala K., Dutre P., (Eds.), The Eurographics Association. 1, 3
- Yuksel C.: Sample elimination for generating poisson disk sample sets. Computer Graphics Forum (Proc. EUROGRAPHICS) 34, 2 (2015), 25–32. 2
- Yan D.-M., Wonka P.: Gap processing for adaptive maximal Poisson-disk sampling. ACM Trans. on Graphics 32, 5 (2013), 148: 1–148:15. 2, 6
- Zhou K., Synder J., Guo B., Shum H.-Y.: Iso-charts: stretch-driven mesh parameterization using spectral analysis. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing (2004), ACM, pp. 45–54. 1, 9
