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. Brown, L. G. 1992. A survey of image registration techniques. ACM Comput. Surv. 24, 4, 325--376.]]
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. Haeberli, P. 1990. Paint by numbers: abstract image representations. In Proceedings of SIGGRAPH 90, ACM Press, 207--214.]]
9. Hausner, A. 2001. Simulating decorative mosaics. In Proceedings of ACM SIGGRAPH, 573--580.]]
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.]]
12. Kaplan, C. S., and Salesin, D. H. 2000. Escherization. In Proceedings of ACM SIGGRAPH, 499--510.]]
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.]]
14. Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2003. Rotation invariant spherical harmonic representation of 3D shape descriptors. In Symposium on Geometry Processing 2003.]]
15. Kim, J., and Pellacini, F. 2002. Jigsaw image mosaics. In Proceedings of ACM SIGGRAPH, 657--664.]]
16. Klein, A. W., Grant, T., Finkelstein, A., and Cohen, M. F. 2002. Video mosaics. In Non-Photorealistic Animation and Rendering, 21--28.]]
17. Mason Woo, J. N., and Davis, T. 1997. OpenGL Programming Guide (2nd Edition). Addison-Wesley.]]
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.]]
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.]]
21. Silvers, R., and Hawley, M. 1997. Photomosaics. Henry Holt and Co., Inc.]]
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.]]
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

• Applied computing

  • Document management and text processing

    • Document capture

      • Graphics recognition and interpretation

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Image and video acquisition

        • 3D imaging

  • Computer graphics

    • Animation

    • Graphics systems and interfaces