Simulating decorative mosaics

ABSTRACT

This paper presents a method for simulating decorative tile mosaics. Such mosaics are challenging because the square tiles that comprise them must be packed tightly and yet must follow orientations chosen by the artist. Based on an existing image and user-selected edge features, the method can both reproduce the image's colours and emphasize the selected edges by placing tiles that follow the edges. The method uses centroidal voronoi diagrams which normally arrange points in regular hexagonal grids. By measuring distances with an manhattan metric whose main axis is adjusted locally to follow the chosen direction field, the centroidal diagram can be adapted to place tiles in curving square grids instead. Computing the centroidal voronoi diagram is made possible by leveraging the z-buffer algorithm available in many graphics cards.

REFERENCES

• 1: Deussen O., Hiller, S., va Overveld, C. and Strothotte T. Floating Points: A Method for Computing Stipple Drawings. Eurographics 00 19:3.
• 2: Qiang Du , Vance Faber , Max Gunzburger, Centroidal Voronoi Tessellations: Applications and Algorithms, SIAM Review, v.41 n.4, p.637-676, Dec. 1999 [doi>10.1137/S0036144599352836]
• 3: Adam Finkelstein , Marisa Range, Image Mosaics, Proceedings of the 7th International Conference on Electronic Publishing, Held Jointly with the 4th International Conference on Raster Imaging and Digital Typography: Electronic Publishing, Artistic Imaging, and Digital Typography, p.11-22, March 30-April 03, 1998
• 4: 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
• 5: Aaron Hertzmann, Painterly rendering with curved brush strokes of multiple sizes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.453-460, July 1998 [doi>10.1145/280814.280951]
• 6: 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]
• 7: 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]
• 8: Hetherington, P. Mosaics London: Paul Hamlyn, 1967.
• 9: Li, Z. and Milenkovic, V. Compaction and Separation Algorithms for Nonconvex Polygons and Their Applications. European Journal of Operations Research 84(1995): 539-561.
• 10: Lloyd, S. Least Square Quantization in PCM. IEEE Transactions on Information Theory 28(1982): 129-137.
• 11: Victor J. Milenkovic, Rotational polygon containment and minimum enclosure, Proceedings of the fourteenth annual symposium on Computational geometry, p.1-8, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276885]
• 12: Robert Silvers , Michael Hawley, Photomosaics, Henry Holt and Co., Inc., New York, NY, 1997
• 13: Richard Szeliski , David Tonnesen, Surface modeling with oriented particle systems, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.185-194, July 1992

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Design, Theory