A spectral approach to NPR packing

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.
• 2: Lisa Gottesfeld Brown, A survey of image registration techniques, ACM Computing Surveys (CSUR), v.24 n.4, p.325-376, Dec. 1992 [doi>10.1145/146370.146374]
• 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.
• 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: Paul Haeberli, Paint by numbers: abstract image representations, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.207-214, September 1990, Dallas, TX, USA
• 9: Alejo Hausner, Simulating decorative mosaics, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.573-580, August 2001 [doi>10.1145/383259.383327]
• 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: Kenneth E. Hoff, III , John Keyser , Ming Lin , Dinesh Manocha , Tim Culver, Fast computation of generalized Voronoi diagrams using graphics hardware, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.277-286, July 1999 [doi>10.1145/311535.311567]
• 12: Craig S. Kaplan , David H. Salesin, Escherization, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.499-510, July 2000 [doi>10.1145/344779.345022]
• 13: Craig S. Kaplan, Islamic star patterns from polygons in contact, Proceedings of the 2005 conference on Graphics interface, May 09-11, 2005, Victoria, British Columbia
• 14: Michael Kazhdan , Thomas Funkhouser , Szymon Rusinkiewicz, Rotation invariant spherical harmonic representation of 3D shape descriptors, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 15: Junhwan Kim , Fabio Pellacini, Jigsaw image mosaics, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 16: Allison W. Klein , Tyler Grant , Adam Finkelstein , Michael F. Cohen, Video mosaics, Proceedings of the 2nd international symposium on Non-photorealistic animation and rendering, June 03-05, 2002, Annecy, France [doi>10.1145/508530.508534]
• 17: Mason Woo , Jackie Neider , Tom Davis, OpenGL programming guide (2nd ed.): the official guide to learning OpenGL version 1.1., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 18: Kenneth Moreland , Edward Angel, The FFT on a GPU, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 19: Rabiner, L., and Gold, B. 1975. Theory and Application of Digital Signal Processing. Prentice-Hall.
• 20: Adrian Secord, Weighted Voronoi stippling, Proceedings of the 2nd international symposium on Non-photorealistic animation and rendering, June 03-05, 2002, Annecy, France [doi>10.1145/508530.508537]
• 21: Robert Silvers , Michael Hawley, Photomosaics, Henry Holt and Co., Inc., New York, NY, 1997
• 22: Kaleigh Smith , Yunjun Liu , Allison Klein, Animosaics, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073397]
• 23: Zahn, C. T., and Roskies, R. S. 1972. Fourier descriptors for plane closed curves. IEEE Transactions of computing 21 (March), 269--281.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.4 Graphics Utilities
          Subjects: Application packages
      I.3.8 Applications

General Terms:
Algorithms, Design

Keywords:
Fourier analysis, animation, area voronoi diagram, centroidal voronoi diagram, mosaics, packing