| ||
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.
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.
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 . A more formal statement is as follows.
Problem 6.16. Given a region R 2 in the plane, and a vector field : R 2 , find N sites P i ˆˆ R and N orientations o i ˆˆ 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 ( 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.
More formally , let V i be the Voronoi region of site P i . Then the centroid or center of mass is
(6.1) |
More generally , if we take a probability density function over R into account, then the centroid is
(6.2) |
Then the Voronoi diagram is a CVD if and only if
For a given Voronoi diagram { P i , V i } i =1 N , we define the energy (sometimes also called the cost) as
(6.3) |
[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).
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).
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
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 = , 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).
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, ( P i ). [6]
Here, we wont go into too much detail about how to obtain a suitable vector field . 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.
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.
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
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 ( 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
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)
or even the aspect ratio of the squares
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].
Figure 6.33 shows two examples generated with the method described above.
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 = { 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
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 , ˆˆ . Set ( P ) := . 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 , 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 , ( ). Voronoi regions that share a ( d ˆ 1)-dimensional face [7] are called neighbors .
Second, we construct the Voronoi diagram over := ˆ P , ( ). This is equivalent to inserting P into the Delaunay diagram over (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).
Let us denote the region of a site P i in ( ) by R i , the region of the same site in ( ) by , 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 ( ).
Next, we define the influence of a natural neighbor. This is done by further partitioning region R into subregions
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) |
(Note that ˆ