CS798 Project: Simulating Decorative Mosaics

Jie Xu

CGL, University of Waterloo



Decorative mosaic is an interesting art. It is also a research topic in NPR. Unlike stroke based rendering methods, mosaic uses tiny tiles as "stroke". It gives us a different feeling. Because we have done something about stroke, silhouette in assignments, I want to simulate the basic features of mosaic as a new work. Hausner's paper is a good start.

Algorithm:

The basic algorithm includes such steps:
  1. Generate a set of points randomly. For each point, place a square pyramid and align it with direction field. To identify the pyramid, I use a method that is similar with the ID image used in assignment2. Each seed point has a ID number. Then the pyramid color is Colour((ID>>16)&0xff, (ID>>8)&0xff, (ID)&0xff). So by reading the color, we can infer which pyramid it belongs to and get other information.
  2. Render the pyramids with an orthogonal projection to produce a Voronoi diagram.
  3. Use Lloyd's algorithm to compute the centroid of each Voronoi region and update the diagram.
  4. Render the tiles based on the computed information.
Approach:
          To decide the orientation of tiles, a direction field is used. The direction field is also computed from Voronoi diagram. I implemented it in three steps:
          1. Compute generalized Voronoi diagrams along edges using forward discussed method. The edges are defined by the user.
          2. Get depth data from z-buffer, and take z-buffer data as source image. Using central differencing to compute the gradient in this image.
          3. Rotate the rendering units(pyramids) along the gradient direction.

 edge edge2 edge3
Figure1: User defined edge, edge's Voronoi diagram, direction field.
           To prevent the tiles straddling the edge, a simple method is used. First, the user draw the thick edge lines with a unique color. I set the width of these lines 5 pixels, and use white color to express edge line. If edge overwrites some part of a tile, from centroid algorithm, we can conclude that the tiles will be moved away from edge. Because there are fewer pixel contribute to the centroid computing. So the centroid will be moved to the position away from the edge. Obviously, it will generate gaps where edge was. The following figures show the procedure.

edge1 edge2 edge3 edge4 edge5 edge6
           Figure2: Edge avoidance. From left to right: initial stage, user defined edge, result after 5 iterations, after 10 iterations, final result after 20 iterations, final tiling.

         Using the algorithm, we can get the basic information such as position, orientation for each tile. We also can setother attributes. For example, we can get the color of tile by sampling at a point or compute the average region color in this tile. In my program, I use average color. The tile size also can be changed. The normal size is defined by this formula equ1. I set the constant delta to 0.8. The h and w are the size of source image and n is the number of seed points. We modify the equation of Manhattan distance so that the tile size will be changed. equ2. Alpha is a parameter to control the tile size. In my implementation, the user provide a mask image. It defines the alpha value for each pixel. By sampling the mask image, we can create different tiles. The mask image is set with different colors, and each color mapping to a alpha value. In order to avoid conflicting with the color of Voronoi diagram, I set the color of mask image such that they only have blue component. And I defined such mapping:
               blue color component: 0xff -- alpha: 1.0
               blue color component: 0xc8 -- alpha: 0.8
               blue color component: 0x96 -- alpha: 0.6
               blue color component: 0x64 -- alpha: 0.4
               blue color component: 0x32 -- alpha: 0.2

Example:
The following example shows the full procedure. The input image is a pattern of Yinyang. There are 300 seed points.
Then the user defines the edges and computes according Voronoi diagram. Computing the centroid using Lloyd's method. The final tiling is the result after 20 iterations.
              
taiji0 taiji1 taiji2 taiji3 taiji5 taiji6 taiji 7
Figure3: Procedure of generating a mosaic. From left to right: source image, initial stage, user defined edge, edge's Voronoi diagram, result after 5 iterations, after 20 iterations and final tiling.

Another more complex example is from Hausner's paper. I set 2000 seed points. Then input the edges and mask image. Compute the direction field. Finally generate the tiling after iterating 20 times. Figure4 displays this example.

ex2 ex2_mask ex2_edge ex2_edge ex2_result
Figure4: Another example. Source image, initial stage, mask image, user defined edge, edge's Voronoi diagram, final tiling.

Extensions:

  1. I also did some simple extensions. People usually use dark color tile to enforce the edge of shape in moscaics. I simulate it by displaying the edge lines. I also test the result render litter tiles instead of lines. Figure5 shows my result.       

castle_line castle_tile
Figure5: Display edge lines.
                                                                                                                           
  1. I find that there are some similar arts, for example, pebble mosaic. Pebble mosaic is using small pebbles to tile patterns on the road or wall. Pebble mosaic is an interesting artistic style. In order to simulate this style, I first generate the normal tiling with the basic algorithm, then tranform the tile from flat square to ellipsoid and using tiny random number to perturb the size. I output the result into python script file and render it using my ray tracer which is created in CS688. To enhance the result, I also use bump mapping in rendering. The bump textures are distilled from real pebble pictures and attribute to pebble tile randomly. I also render the mosaic using cube tile. Figure6 shows my result.

castle_sphere castle_cube
Figure6:  Simulated pebble mosaic and cube tile mosaic.
 
  1. Another extension is to simulate different mosaic styles. For example, the opus classicum and opus vermiculatum styles. To simulate the opus vermiculatum style, I just draw some parallel edges. Figure7 shows this example.
       
style1_1 style1_2 style1_3 style1_4
Figure7: Simulated opus vermiculatum style

To simulate the opus classicum style, I constructed it with two layers. In the first layer, I used regular pattern to tile the background. In the second layer, I created the mosaic. Finally, I combined the two layers to get the desired style. Figure8 shows this style.

style2_1 style2_2 style2_3 
Figure8:  Simulated opus classicum style. from left to right: first layer, second layer, combined result.


Bibliography:
    
Hoff, K., Keyser, J., Lin, M., Manocha, D. and Culver, T. Fast Computation of Generalized Voronoi Diagrams               Using Graphics Hardware. SIGGRAPH 99: 277-286.
Hausner, A. Simulating Decorative Mosaics. SIGGRAPH 2001: 573-580.
Kim, J. and Pellacini, F. Jigsaw Image Mosaics. SIGGRAPH 2002: 657-664.

                                                                       
More results:

bird duck_mask duck_voronoi duck_edge duck_mosaic duck_cube duck_sphere


flower flower_mask flower_voronoi flower_edge flower_mosaic flower_cube flower_sphere


horse horse_mask horse_voronoi horse_edge horse_mosaic horse_cube horse_sphere


mountain mountain_mask mountain_voronoi mountain_edge mountain_mosaic mountain_cube mountain_sphere

statue statue_mask statue_voronoi statue_edge statue_mosaic statue_cube statue_sphere

stone stone_mask stone_voronoi stone_edge stone_mosaic stone_cube stone_sphere

tree2 tree2_mask tree2_voronoi tree2_edge tree2_mosaic tree2_cube tree2_sphere

tree tree_voronoi tree_edge tree_mosaic tree_cube tree_sphere