“Simulating decorative mosaics” by Hausner

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.

1. Deussen O., Hiller, S., va Overveld, C. and Strothotte T. Floating Points: A Method for Computing Stipple Drawings. Eurographics 00 19:3.
2. Du, Q., Faber, V. and Gunzburger, M. Centroidal Voronoi Tessellations: Applications and Algorithms. SIAM Review 41 (1999): 637-676.
3. Finkelstein, A. and Range, M., Image Mosaics, in Roger D. Hersch, Jacques Andre, and Heather Brown (eds.), Electronic Publishing, Artistic Imaging and Digital Typography, Proceedings of the EP98 and RIDT’98 Conferences, St Malo: March 30 – April 3, 1998, Lecture Notes in Computer Science Series, number 1375, Heidelberg: Springer-Verlag 1998.
4. Haeberli, P. Paint by Numbers. SIGGRAPH ’90 207-214.
5. Hertzmann, A. Painterly Rendering with Curved Brush Strokes of Multiple Sizes. SIGGRAPH 98: 453-460.
6. Hoff, K., Keyser, J., Lin, M., Manocha, D. and Culver, T. Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware. SIGGRAPH 99: 277-286.
7. Kaplan, C. and Salesin, D. Escherization. SIGGRAPH 00: 499-510.
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. Milenkovic, V. Rotational Polygon Containment and Minimum Enclosure. Proceedings of the 14th Annual Symposium on Computational Geometry, (June 1998): 1-8.
12. Silvers, R. and Hawley, M. Photomosaics, New York: Henry Holt, 1997.
13. Szeliski, R. and Tonnesen, D. Surface modeling with oriented particle systems. SIGGRAPH 92: 185-194.