Article

A spectral approach to NPR packing

Authors:

Allison W. Klein,

Kaleigh SmithAuthors Info & Claims

NPAR '06: Proceedings of the 4th international symposium on Non-photorealistic animation and rendering

Pages 71 - 78

https://doi.org/10.1145/1124728.1124741

Published: 05 June 2006 Publication History

Abstract

This paper presents improvements in mosaic packing by combining a new title evenness metric with an efficient, effective tile placement algorithm based on the Fast Fourier Transform. This new packing method applies to existing packing applications and makes possible novel mosaic applications, such as mosaic packings of 3D volumes using temporally repeating animated shapes. Applications of our approach include static 2D mosaic packing, mosaic animations, stippling, and texture generation.

References

[1]

Blasi, G. D., Gallo, G., and Maria, P. 2005. Fast techniques for mosaic rendering. In Eurographics Workshop on Computational Aesthetics 2005.]]

Digital Library

[2]

Brown, L. G. 1992. A survey of image registration techniques. ACM Comput. Surv. 24, 4, 325--376.]]

Digital Library

[3]

Cooley, J. W., and Tukey, J. W. 1965. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation 19, 297--301.]]

[4]

Ding, Z. 2002. Computer Generated Mosaic Animation. Master's thesis, University of Toronto.]]

[5]

Elber, G., and Wolberg, G. 2003. Rendering traditional mosaics. The Visual Computer 19, 1, 67--78.]]

[6]

Finkelstein, A., and Range, M. 1998. Image mosaics. Lecture Notes in Computer Science 1375.]]

Digital Library

[7]

Frigo, M., and Johnson, S. G. 2005. The design and implementation of FFTW3. Proceedings of the IEEE 93, 2, 216--231. special issue on "Program Generation, Optimization, and Platform Adaptation".]]

[8]

Haeberli, P. 1990. Paint by numbers: abstract image representations. In Proceedings of SIGGRAPH 90, ACM Press, 207--214.]]

Digital Library

[9]

Hausner, A. 2001. Simulating decorative mosaics. In Proceedings of ACM SIGGRAPH, 573--580.]]

Digital Library

[10]

Hiller, S., Hellwig, H., and Deussen, O. 2003. Beyond stippling - methods for distributing objects on the plane. Computer Graphics Forum 22, 3, 515--522.]]

[11]

Hoff III, K. E., Keyser, J., Lin, M., Manocha, D., and Culver, T. 1999. Fast computation of generalized Voronoi diagrams using graphics hardware. In Proceedings of ACM SIGGRAPH, 277--286.]]

Digital Library

[12]

Kaplan, C. S., and Salesin, D. H. 2000. Escherization. In Proceedings of ACM SIGGRAPH, 499--510.]]

Digital Library

[13]

Kaplan, C. S. 2005. Islamic star patterns from polygons in contact. In GI '05: Proceedings of the 2005 conference on Graphics interface, 177--185.]]

Digital Library

[14]

Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2003. Rotation invariant spherical harmonic representation of 3D shape descriptors. In Symposium on Geometry Processing 2003.]]

Digital Library

[15]

Kim, J., and Pellacini, F. 2002. Jigsaw image mosaics. In Proceedings of ACM SIGGRAPH, 657--664.]]

Digital Library

[16]

Klein, A. W., Grant, T., Finkelstein, A., and Cohen, M. F. 2002. Video mosaics. In Non-Photorealistic Animation and Rendering, 21--28.]]

Digital Library

[17]

Mason Woo, J. N., and Davis, T. 1997. OpenGL Programming Guide (2nd Edition). Addison-Wesley.]]

Digital Library

[18]

Moreland, K., and Angel, E. 2003. The FFT on a GPU. In HWWS'03: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, Eurographics Association, 112--119.]]

Digital Library

[19]

Rabiner, L., and Gold, B. 1975. Theory and Application of Digital Signal Processing. Prentice-Hall.]]

[20]

Secord, A. 2002. Weighted voronoi stippling. In Non-Photorealistic Animation and Rendering, 37--43.]]

Digital Library

[21]

Silvers, R., and Hawley, M. 1997. Photomosaics. Henry Holt and Co., Inc.]]

Digital Library

[22]

Smith, K., Liu, Y., and Klein, A. 2005. Animosaics. In SCA '05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, ACM Press, New York, NY, USA, 201--208.]]

Digital Library

[23]

Zahn, C. T., and Roskies, R. S. 1972. Fourier descriptors for plane closed curves. IEEE Transactions of computing 21 (March), 269--281.]]

Digital Library

Cited By

Freire MBhargava MSchreck CHugron PBickel BLefebvre S(2023)PCBend: Light Up Your 3D Shapes With Foldable Circuit BoardsACM Transactions on Graphics10.1145/359241142:4(1-16)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592411
Saputra RKaplan CAsente P(2021)Improved Deformation-Driven Element Packing with RepulsionPakIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2019.295023527:4(2396-2408)Online publication date: 1-Apr-2021
https://doi.org/10.1109/TVCG.2019.2950235
Hsu CWei LYou LZhang JBernhaupt RMueller FVerweij DAndres JMcGrenere JCockburn AAvellino IGoguey ABjørn PZhao SSamson BKocielnik R(2020)Autocomplete Element FieldsProceedings of the 2020 CHI Conference on Human Factors in Computing Systems10.1145/3313831.3376248(1-13)Online publication date: 21-Apr-2020
https://dl.acm.org/doi/10.1145/3313831.3376248
Show More Cited By

Index Terms

A spectral approach to NPR packing
1. Applied computing
  1. Document management and text processing
    1. Document capture
      1. Graphics recognition and interpretation
2. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Image and video acquisition
        3D imaging
  2. Computer graphics
    1. Animation
    2. Graphics systems and interfaces

Recommendations

Calligraphic packing
GI '07: Proceedings of Graphics Interface 2007

There are many algorithms in non-photorealistic rendering for representing an image as a composition of small objects. In this paper, we focus on the specific case where the objects to be assembled into a composition are letters rather than images or ...
Packing polyominoes clumsily

For a set D of polyominoes, a packing of the plane with D is a maximal set of copies of polyominoes from D that are not overlapping. A packing with smallest density is called a clumsy packing. We give an example of a set D such that any clumsy packing ...
Packing resizable items with application to video delivery over wireless networks

Motivated by fundamental optimization problems in video delivery over wireless networks, we consider the following problem of packing resizable items (PRI). Given is a bin of capacity B > 0 , and a set I of items. Each item j I has a size s j > 0 . A ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

NPAR '06: Proceedings of the 4th international symposium on Non-photorealistic animation and rendering

June 2006

160 pages

ISBN:1595933573

DOI:10.1145/1124728

Conference Chairs:
Doug DeCarlo
Rutgers University
,
Lee Markosian
University of Michigan

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Annecy Animation Festival

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

NPAR06

Sponsor:

NPAR06: The 4th International Symposium on Non-Photorealistic Animation

June 5 - 7, 2006

Annecy, France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
908
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)2

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Freire MBhargava MSchreck CHugron PBickel BLefebvre S(2023)PCBend: Light Up Your 3D Shapes With Foldable Circuit BoardsACM Transactions on Graphics10.1145/359241142:4(1-16)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592411
Saputra RKaplan CAsente P(2021)Improved Deformation-Driven Element Packing with RepulsionPakIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2019.295023527:4(2396-2408)Online publication date: 1-Apr-2021
https://doi.org/10.1109/TVCG.2019.2950235
Hsu CWei LYou LZhang JBernhaupt RMueller FVerweij DAndres JMcGrenere JCockburn AAvellino IGoguey ABjørn PZhao SSamson BKocielnik R(2020)Autocomplete Element FieldsProceedings of the 2020 CHI Conference on Human Factors in Computing Systems10.1145/3313831.3376248(1-13)Online publication date: 21-Apr-2020
https://dl.acm.org/doi/10.1145/3313831.3376248
Javid ADoyle LMould DJorge JBartram LCatalano CKaplan CForbes ADiVerdi S(2019)Irregular pebble mosaics with sub-pebble detailProceedings of the 8th ACM/Eurographics Expressive Symposium on Computational Aesthetics and Sketch Based Interfaces and Modeling and Non-Photorealistic Animation and Rendering10.2312/exp.20191084(133-141)Online publication date: 5-May-2019
https://dl.acm.org/doi/10.2312/exp.20191084
Gortler JSpicker MSchulz CWeiskopf DDeussen O(2019)Stippling of 2D Scalar FieldsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2019.290394525:6(2193-2204)Online publication date: 1-Jun-2019
https://doi.org/10.1109/TVCG.2019.2903945
Martín DArroyo Gdel Sol VRomo CIsenberg T(2019)Analysis of drawing characteristics for reproducing traditional hand-made stipplingComputers and Graphics10.1016/j.cag.2019.02.00180:C(1-16)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1016/j.cag.2019.02.001
Saputra RKaplan CAsente PBatty CReilly D(2018)RepulsionPak: Deformation-Driven Element Packing with Repulsion ForcesProceedings of the 44th Graphics Interface Conference10.20380/GI2018.03(10-17)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.20380/GI2018.03
Saputra RKaplan CAsente PMěch REisemann EBateman S(2017)FLOWPAK: Flow-based Ornamental Element PackingProceedings of the 43rd Graphics Interface Conference10.5555/3141475.3141479(8-15)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.5555/3141475.3141479
Gómez EMéndez EArroyo GMartín yGutiérrez DMelero JPelechano N(2017)Fast stippling based on weighted centroidal voronoi diagramsProceedings of the XXVII Spanish Computer Graphics Conference10.2312/ceig.20171214(87-96)Online publication date: 28-Jun-2017
https://dl.acm.org/doi/10.2312/ceig.20171214
Martn DArroyo GRodrguez AIsenberg T(2017)A survey of digital stipplingComputers and Graphics10.1016/j.cag.2017.05.00167:C(24-44)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1016/j.cag.2017.05.001
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents