6.5. Voronoi Diagrams in Computer Graphics

6.5. Voronoi Diagrams in Computer Graphics

In the following, we will present some applications in computer graphics that use Voronoi diagrams (or Delaunay graphs) to achieve an elegant or simple solution.

6.5.1. Mosaics

One of the major subjects in computer graphics is the photorealistic rendering of scenes or environments modeled in the computer. However, a fairly recent topic in computer graphics is the so-called non-photorealistic rendering (NPR). For example, NPR might be used to produce mosaics.

Mosaics are made up of small pieces, such as stones, pebbles, or shells , that are closely set on a surface. The pieces are usually variously colored, so that the overall ensemble creates a picture when viewed from a distance. The individual pieces are small compared to the size of the mosaic and more or less congruent to each other. Examples are the wonderful Greek, Roman (see Figure 6.26), or Byzantine mosaics found in baths, houses , and temples.

image from book
Figure 6.26: Roman mosaics from baths [Mosaic a, Mosaic b]. (See Color Plate X.) ((left) Courtsey of D. Mesher at the SJSU Jewish Studies program. (right) Courtesy of the Hellenic Ministry of Culture.

In addition, a mosaic consisting of N pieces can potentially carry more information than an image made up of N pixels, because the pieces can carry extra information, such as shape and orientation. For instance, in the examples in Figure 6.26, one can see that the orientation of the pieces follows the edges, contours , or other features (e.g., medial axis) of the image. Because this is a very characteristic feature of mosaics, we want to achieve this effect in our computer-generated ones, too. However, we are now given two conflicting tasks : using only congruent pieces, we are to place them such that the area between them (the grout) is minimized, and such that the orientation of all of them (we assume the pieces have a unique up direction) is as close as possible to a prescribed one.

In the following, let us assume that the pieces are squares of equal size (later, we will see how to lift this restriction easily). At each point in the mosaic, we will prescribe the orientation of the pieces by a vector field image from book . A more formal statement is as follows.

Problem 6.16. Given a region R image from book 2 in the plane, and a vector field image from book : R image from book 2 , find N sites P i ˆˆ R and N orientations o i ˆˆ image from book 2 , such that the following conditions hold: if N squares of side length s are placed on the sites, one at each P i and with orientation o i , then

  • they are disjoint ;

  • the area they cover is maximized;

  • the sum of the angles between the o i and image from book ( P i ) is minimized.

The idea is that the region R covers an image and the direction field is designed such that it aligns the squares with the edges in the image. When the P i have been found, we will color each square uniformly by the color found at position P i in the image.

Choosing exactly equal squares for the pieces of the mosaic is a simplification, but we can make the mosaic look more handcrafted after the sites have been found by distorting each square randomly by a small amount.

Actually, the problem of placing the sites P i , as stated above, is the general problem of generating low-discrepancy sampling patterns , or low-energy particle configurations . [2]

Placing the sites. First, we will consider only the problem of placing the sites for equally aligned squares (i. e., we omit the orientation for the moment).

Imagine N particles in region R , each one repelling its neighbors. When the particles come to a rest, we can compute the Voronoi diagram of the particle set, and this Voronoi will be a special variant, called the centroidal Voronoi diagram (CVD). In a CVD, we have the additional property that each site is located at the mass center (centroid) of its Voronoi region. Figure 6.27 shows an example; another example is a honeycomb.

image from book
Figure 6.27: Example centroidal Voronoi diagram (CVD).

More formally , let V i be the Voronoi region of site P i . Then the centroid or center of mass is

(6.1)  image from book

More generally , if we take a probability density function over R into account, then the centroid is

(6.2)  image from book

Then the Voronoi diagram is a CVD if and only if

image from book

For a given Voronoi diagram { P i , V i } i =1 N , we define the energy (sometimes also called the cost) as

(6.3)  image from book

[Du et al. 99] proved that a necessary condition for E to be minimal is that { P i , V i } i =1 N is a CVD of R .

Observe that the CVDs produced so far look locally like hexagonal tilings. This is because in Equation (6.3), the Euclidean metric is used to measure distances and, thus, the range of influence of a Voronoi region. However, we would like more square-like tilings. Consequently, we need to choose a different metric, namely the L 1 metric, or Manhattan distance metric, x 1 ˆ x 2 + y 1 ˆ y 2 . Then the CVD becomes much more like a tiling with squares (see Figure 6.28).

image from book
Figure 6.28: Example CVD with the Manhattan metric instead of the Euclidean metric.

In order to compute a CVD for a given region R , there are two well-known algorithms; Lloyds method and MacQueens method [Ju et al. 02]. While the latter is simpler to perform on a CPU, we will present the former, for reasons you will see shortly. In addition, Deussen et al. [Deussen et al. 00] report that it seems to be more stable than other particle spreading techniques (although, theoretically, its convergence in two or more dimensions has not been proven).

Algorithm 6.9: Lloyds algorithm to compute a centroidal Voronoi diagram for a region R.
image from book
 select an initial set of  N  random points  P    i      R   repeat  construct the Voronoi regions  V    i   determine the centroids  C    i   of all  V    i   set  P    i   :=  C    i    until   E  ({  P    i    , V    i   } is small enough 
image from book
 

Lloyds method is basically an iteration between computing Voronoi diagrams and mass centers. [3] Algorithm 6.9 outlines the procedure. There are two open issues: how to compute the Voronoi regions and how to determine the centroid.

Since an approximate CVD will serve our purpose perfectly , we can compute the Voronoi regions by the same method as in Section 5.1.2 [Hausner 01]: we place a right cone with its apex on each of the P i , with its axis along the z -axis. Then we project all of them orthogonally on the xy -plane. This is exactly what happens when rendering all the cones into the frame buffer. For each pixel, the Z-buffer performs the nearest neighbor search, because the pixel will get filled by that cone whose apex is nearest . For each cone, we choose a unique color, so that in the end, all pixels in the same Voronoi region will have the same ID (i. e., color). [4]

With this approach, we can even accommodate different metrics, because the shape of the cones embodies the metric. The function of a circular cone is z = image from book , which is exactly the distance of a point x 1 from the apex x 2 . If we want to embody the Manhattan metric, we just render square cones whose function is z = x 1 ˆ x 2 + y 1 ˆ y 2 (see Figure 6.29).

image from book
Figure 6.29: Different shapes of cones embody different metrics.

What remains is to compute the centroids of the Voronoi regions (see Equation (6.1)). In a conventional CPU implementation, this would be done by a Monte Carlobased integration technique [Ju et al. 02]. Here, we can simply scan the frame buffer and compute, for each color ID, the average of all x - and y -values, respectively, of pixels that have been colored with that ID. Again, this gives just an approximate centroid, but this is fine for our application. [5]

Orienting the pieces. So far, we have ignored the orientation of the pieces that are to be placed at the P i . With circular cones, there is no distinguished orientation; and with square cones we have, so far, oriented them all in the same way.

The modification we have to make is quite simple [Hausner 01]: instead of rendering square cones with the same orientation, we just rotate the cones according to the vector field at the apex, image from book ( P i ). [6]

Here, we wont go into too much detail about how to obtain a suitable vector field image from book . One simple way is similar to the method in Section 5.1.2 of computing the Voronoi regions [Hausner 01]. We start with a set of curves in the region R , along which the mosaic pieces should be aligned. For each of the curves, we render (with orthogonal projection) a (tessellated) curved mountain. Then, we read back the Z-buffer, which contains kind of a height field, and compute the discrete gradient at each pixel (see Figure 6.30). These gradients will be perpendicular to the curves at pixels close to the curve.

image from book
Figure 6.30: The vector field for orienting the mosaic pieces can be computed by discrete gradients from a set of curves [Hausner 01]. (Courtesy of Alejo Hausner and ACM.)

Edge avoidance . One prominent feature of mosaics is that the pieces usually do not straddle edges or contours of the image, to make them more pronounced in the mosaic. This is something we want to simulate in our computer-generated mosaics, too. This can be achieved by modifying the density function appropriately. Here, we should set to zero in a band around the edges, with the width of the band about the same as the size of the pieces.

Since we compute the new Voronoi region centroids by scanning the frame buffer for pixels with the regions color ID, all we need to do is to insert an additional step just before the scanning, in which we set all pixels inside the edge bands to a neutral color (e. g., white), so that they wont be counted for any Voronoi region. Thus, the Voronoi sites (i. e., centroids) will be pushed away from the edges. This process is illustrated in Figure 6.31.

image from book
Figure 6.31: Process to preserve edges of the original image in the final mosaic. [Hausner 01]. (See Color Plate XI.) (Courtesy of Alejo Hausner and ACM.)

Overall, the algorithm for computing a mosaic is shown in Algorithm 6.10. Compared to Algorithm 6.9, we might want to change the convergence criterion, e. g., we could stop if the energy does not decrease significantly anymore. The size s of the final mosaic pieces can be estimated as

Algorithm 6.10: Algorithm to generate a mosaic.
image from book
 1: select an initial set of  N  random points  P    i      R  2:  repeat  3:            place a square pyramid at each site  P    i   , with apex at  P    i   and axis along z-axis, and                      rotate it about z-axis to align it with the direction field  image from book  (  P    i   ) 4:            render all pyramids using orthogonal projection into the frame buffer, each with                      a unique color 5:            draw edge bands over the discrete Voronoi diagram in frame buffer, using neutral                      color (white) 6:            read color buffer back 7:            scan buffer and compute average  x  and  y  values (centroids  C    i   ) for each color                      ID  i  8:            set  P    i   :=  C    i   9:  until  convergence criterion is met 10:draw a square of size  s  at each  P    i   with uniform color found at position  P    i   in the original            image 
image from book
 
image from book

where S is the number of pixels in the region R , and is a factor to account for the dead space between the squares (grout) due to different orientations.

Varying the piece size. Just as with the orientation, we can adapt the algorithm to vary the size of the mosaic pieces (squares) simply by changing the slope of the square cones (pyramids)

image from book

or even the aspect ratio of the squares

image from book

This can be useful in areas of the image with fine detail.

Basically, this amounts to changing the probability density function in Equations (6.2) and (6.3). Accordingly, Lloyds algorithm will pack the squares more densely in areas with high probability density.

Examples. Figure 6.32 shows an example of a Voronoi diagram, where a number of sites have been placed randomly on an image, and each Voronoi cell is colored uniformly according to the color in the image at the Voronoi site. This is basically the technique presented in [Haeberli 90]. The example was generated using the software of [Hoff III et al. 99].

image from book
Figure 6.32: Mosaics generated by randomly placing 6000 Voronoi sites on an image and coloring each Voronoi region uniformly by the color in the image. (See Color Plate XII.)

Figure 6.33 shows two examples generated with the method described above.

image from book
Figure 6.33: Two examples of mosaics [Hausner 01], generated with the CVD method. (See Color Plate XIII.) (Courtesy of Alejo Hausner and ACM.)

6.5.2. Natural Neighbor Interpolation

Interpolation is a very important technique that arises in many situations in computer graphics and other fields of engineering.

The problem statement can be formulated quite simply.

Let image from book = { P 1 , , P n } R d be a set of fixed points in d -dimensional space. Sometimes, we call these points data sites . At each of these, we are given a real value z i (here, we will generalize this a bit). Now, the interpolation problem is to find a good (in some sense) function such that

image from book

An example is the interpolation of vectors in space, e. g., normals, which are given only at a discrete set of points, e. g., the vertices of a model or a point cloud obtained from a scanner (see Figure 7.19).

There are almost infinite ways to solve this problem. Here, we will describe one method that utilizes Voronoi diagrams in a neat way.

An extremely simple method is the following. Given a point P , determine the nearest neighbor of P , image from book ˆˆ image from book . Set ( P ) := image from book . Finding the nearest neighbor amounts to identifying the Voronoi region in which P is located. However, an explicit construction of the Voronoi diagram is not needed (although it could be used to accelerate the search). Obviously, this interpolant is a piecewise constant function and, thus, not continuous.

The remedy is, more or less, clear: we need to involve the neighbors of P or image from book , respectively. This was proposed by [Sibson 80, Sibson 81]. The idea is to utilize the Voronoi diagram for determining the neighbors of P and for determining their influence on P .

More precisely, we first construct the Voronoi diagram over image from book , image from book ( image from book ). Voronoi regions that share a ( d ˆ 1)-dimensional face [7] are called neighbors .

Second, we construct the Voronoi diagram over image from book := image from book ˆ P , image from book ( image from book ). This is equivalent to inserting P into the Delaunay diagram over image from book (see Section 6.2), and then carrying the changes over to the Voronoi diagram. Note that the changes will usually be only local (see Figure 6.34).

image from book
Figure 6.34: Inserting P changes the Voronoi diagram. The thick and dashed lines together constitute the Voronoi diagram over image from book , while the thick and the thin lines show the Voronoi diagram over image from book . The thin lines alone represent the Voronoi region for P, the point at which the interpolation is to be computed.

Let us denote the region of a site P i in image from book ( image from book ) by R i , the region of the same site in image from book ( image from book ) by image from book , and the region of site P by R . The natural neighbors of P are defined as the points P i that are neighbors of P in image from book ( image from book ).

Next, we define the influence of a natural neighbor. This is done by further partitioning region R into subregions

image from book

From Figure 6.34, it should be obvious that P i is a natural neighbor of P if and only if S i ‰  ˜. Let Vol( S i ) denote the volume of these subregions (or, more precisely, the Lebesgue measure in d dimensions). Now, the natural coordinate of P associated to P i is defined by

(6.4)  image from book

(Note that ˆ



Geometric Data Structures for Computer Graphics2006
Geometric Data Structures for Computer Graphics2006
ISBN: N/A
EAN: N/A
Year: 2005
Pages: 69

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net