Cohen M.F., Wallace J.R. - Radiosity and realistic image synthesis (1995)(en)

CHAPTER 6. RENDERING

6.2 MESH CHARACTERISTICS AND ACCURACY

Figure 6.4: Error image.

bands (letter C), inappropriate shading discontinuities (letter D), and unresolved discontinuities (letter E).

Figure 6.4 is a visualization of the RMS error (defined in the box on function norms on page 133) for each element. The error was computed by evaluating the radiosity at 16 interior points across each element and comparing this to the approximate value. The comparison shows absolute as opposed to relative error. As apparent in this image, the error in the approximation is very unevenly distributed over the mesh. Computational effort has been applied fairly equally over the domain of the approximation, with very unequal contributions to the resulting accuracy.

The example shown in these images will be referred to throughout this chapter, to illustrate the discussion of meshing strategies. That discussion will begin with the description of basic mesh characteristics in the following sections.

6.2.2 Mesh Density

Mesh density is determined by the size of the elements into which the domain is subdivided. The density of the element mesh determines the number of degrees of freedom available to the approximation. More elements provide more degrees of freedom, which allows the approximation to follow the actual function more closely and increases the degree to which small features like shadows can be resolved.

Radiosity and Realistic Image Synthesis	139
Edited by Michael F. Cohen and John R. Wallace

CHAPTER 6. RENDERING

6.2 MESH CHARACTERISTICS AND ACCURACY

Linear elements with uniform subdivision.

Linear elements with higher density subdivision.

Linear elements with non-uniform subdivision.

Figure 6.5: Comparison of element subdivision strategies.

Radiosity and Realistic Image Synthesis	140
Edited by Michael F. Cohen and John R. Wallace

CHAPTER 6. RENDERING

6.2 MESH CHARACTERISTICS AND ACCURACY

Figure 6.6: A radiosity solution with the mesh density increased four times over the mesh used in Figure 6.2.

To illustrate, a one-dimensional function is approximated in Figure 6.5 using a variety of subdivisions. In the coarsest subdivision (the topmost plot in Figure 6.5) the approximation follows the actual radiosity function closely where it is almost linear, but diverges where the function changes slope quickly. Smaller features of the function are missing entirely when they fall between nodes.

Evaluating the function at smaller intervals increases the accuracy of the approximation, as shown in the second plot of Figure 6.5. However, the errors remain unevenly distributed, meaning that the extra effort has been applied inefficiently. Ideally, the domain should be subdivided more finely only where it will improve the accuracy significantly, as in the third plot of Figure 6.5.

Similar observations apply to approximating the radiosity function. In the example image (see Figure 6.2), inadequate mesh density results in elements that are too large to capture shading detail accurately. This is particularly evident in the “staircase” shadows cast by the table (letter A in Figure 6.3(b)), where the size of the shading feature (the penumbra) is much smaller than the separation between nodes.

Just as in the one-dimensional case, uniformly increasing the mesh density improves the overall accuracy. The image in Figure 6.6 was produced using a uniform mesh with four times as many elements as used in Figure 6.2. The

Radiosity and Realistic Image Synthesis	141
Edited by Michael F. Cohen and John R. Wallace

CHAPTER 6. RENDERING

6.2 MESH CHARACTERISTICS AND ACCURACY

Figure 6.7: RMS error for the elements in figure 6.6.

quality is better and some of the artifacts are almost eliminated. However, the corresponding error image in Figure 6.7 shows that the extra effort has been applied inefficiently, with many elements subdivided where the error was already negligible. This effort would have been better expended in further reducing the error in the remaining problem areas, such as along the shadow boundaries.

6.2.3 Element Order and Continuity

Element order (i.e., the order of the basis functions defined over the element) also has a direct effect on accuracy. Higher-order elements interpolate the function using higher-order polynomials and use more information about the behavior of the function, either by evaluating both values and derivatives at the nodes or by evaluating the function at Additional nodes. Thus, higher-order elements can follow the local variations in a function more closely than the same number of lower-order elements. However, higher-order elements are generally more expensive to evaluate. Thus, one approach is to use higher-order elements only where the error is high and the extra effort is justified.

The type of basis functions used also affects the degree of continuity in the approximation at element boundaries. Continuity of value and of lower-order derivatives (C0, C1, C2, ...) is important because the human visual system is

Radiosity and Realistic Image Synthesis	142
Edited by Michael F. Cohen and John R. Wallace

CHAPTER 6. RENDERING

6.2 MESH CHARACTERISTICS AND ACCURACY

Figure 6.8: Mach bands caused by first-derivative discontinuities at element boundaries.

highly sensitive to relative spatial variation in luminance and its derivatives.2 For example, the bright streaks along the wall in the example image (see

the closeup in Figure 6.8) correspond to discontinuities in the first derivative of the radiosity approximation, which occur at the boundaries of linear elements. The eye accentuates first derivative discontinuities, resulting in the perceptual phenomenon known as Mach bands [189]. Although Mach bands can occur naturally, they are distracting when they are incorrectly introduced by the approximation.

Since interpolation within elements is a linear sum of polynomials, the approximation is smooth (C∞) on element interiors. However, continuity at element boundaries is not guaranteed. For Lagrange elements interpolation inside or on the boundary of the element depends only on the function values at the nodes belonging to that element. Because interpolation along boundaries uses only nodes on the boundary, linear and higher order Lagrange elements guarantee C0 continuity at element boundaries. (Constant elements are discontinuous

2The notation Ck indicates that a function is continuous in all derivatives up to and including k. C0 thus indicates that a function is continuous in value (i.e., there are no sudden jumps in value), C1 that the function is continuous in slope (i.e., there are no kinks), and C∞ that the function is smooth (i.e., continuous in all derivatives).

Radiosity and Realistic Image Synthesis	143
Edited by Michael F. Cohen and John R. Wallace

CHAPTER 6. RENDERING

6.2 MESH CHARACTERISTICS AND ACCURACY

Figure 6.9: A combination of rectangular and triangular elements used to fill a complicated geometry.

in values at element boundaries). Hermite elements can provide a higher degree of continuity with fewer nodes by interpolating nodal derivatives as well as values. C1 continuity, for example, requires interpolating the gradient at boundary nodes.

For radiosity, providing continuity greater than C0 is motivated primarily by perceptual issues. Thus, elements with this property, such as the Clough-Tocher element used by Salesin et al. [203], have been applied mainly to the rendering stage. These will be discussed in detail in Chapter 9.

6.2.4 Element Shape

Elements should provide well-behaved, easily evaluated basis functions. For this reason, standard element shapes consist of simple geometries, typically triangles and rectangles. These standard shapes can be mixed to subdivide a complicated geometry more efficiently (see figure 6.9) or to provide a transition between regions of differing mesh density (see Figure 6.10).

Isoparametric elements allow the standard shapes to be mapped to more general geometries, using the basis functions to interpolate geometric location as well as radiosity values (see section 3.8). The bilinear quadrilateral element is a common example. Higher order isoparametric elements can be mapped to curved geometries. The parametric mapping must be invertible, which places some restrictions on the element shape. Concavities and extra vertices are normally to be avoided.

If Gouraud shading is to be used for rewndering, anumber of special problems relating to element shape must be avoided. For example, Gouraud interpolation

Radiosity and Realistic Image Synthesis	144
Edited by Michael F. Cohen and John R. Wallace

CHAPTER 6. RENDERING

6.2 MESH CHARACTERISTICS AND ACCURACY

Figure 6.10: Use of triangular elements to provide transition between regions of high and low mesh density.

over a concave element can generate discontinuities in value, as shown in Figure 6.11. The problems relating to element shape and Gouraud interpolation will be discussed in Chapter 9.

Aspect Ratio

Element shape affects the efficiency with which the mesh samples the radiosity function [18]. To make the most efficient use of a given number of nodes, the nodes should be evenly distributed over the domain of the function (assuming that the behavior of the function is unknown). A distribution of nodes that is denser in one direction than in another is inefficient, since if elements are subdivided far enough to make sampling adequate in the sparse direction, sampling in the denser direction will be greater than necessary. Poor element shape can also affect the accuracy or efficiency of numerical integration of the form factors.

A reasonably uniform distribution of nodes can be obtained by requiring elements to have as high an aspect ratio as possible. The aspect ratio is defined as the ratio of the radius of the largest circle that will fit completely inside the element to the radius of the smallest circle that will fit completely outside the element (see Figure 6.12) [18]. This ratio should be as close to 1 as possible.

However, if the behavior of the function is known, anisotropic sampling

Radiosity and Realistic Image Synthesis	145
Edited by Michael F. Cohen and John R. Wallace

CHAPTER 6. RENDERING

6.2 MESH CHARACTERISTICS AND ACCURACY

Figure 6.11: A concave element, with a discontinuity introduced by Gouraud shading (closeup of letter D in Figure 6.3 (b)).

may be more efficient than a uniform distribution, since the function changes more slowly in the direction orthogonal to the gradient and thus fewer samples are required along that direction. Elements with a lower aspect ratio may be more efficient in this case, if oriented correctly.

In a review of surface triangulation techniques, Schumaker [207] provides an excellent example of the effect of element orientation. A function surface is first approximated by triangulating regularly spaced nodes. However, the approximation is more accurate when the nodes are connected to form triangles with “poor” aspect ratios (see Figure 6.13). Schumaker discusses how approximation accuracy can be incorporated into the quality metric used by the triangulation algorithm. The approximation of a surface in 3-space is analogous to the approximation of the radiosity function and the surface approximation literature is thus a fruitful source for meshing algorithms.

Form factor algorithms may make assumptions that are violated by elements with poor aspect ratios. For example, in the adaptive ray casting algorithm described by Wallace et al. [247], (see Chapter 4), elements or pieces of elements (delta-areas) are approximated as disks. The accuracy of the disk approximation decreases with decreasing element aspect ratio.

Radiosity and Realistic Image Synthesis	146
Edited by Michael F. Cohen and John R. Wallace

CHAPTER 6. RENDERING

6.2 MESH CHARACTERISTICS AND ACCURACY

Figure 6.12: The effect of aspect ratio on sampling density. A low aspect ratio tends to produce an anisotropic sampling density.

Mesh Grading

A nonuniform, or graded, mesh may be required to distribute the error evenly in the approximation. In a well-graded mesh, element size and shape vary smoothly in the transition between regions of higher and lower density (see Figure 6.14). Abrupt changes in size or shape will often cause visible irregularities in shading, since neighboring elements will approximate the function with slightly different results. Because of the eye’s sensitivity to contrast, such differences may be visible even when the error for both elements is within tolerance.

Mesh Conformance

It is important that adjacent elements conform across shared boundaries, as shown in Figure 6.15. Discontinuities in value created by nonconforming elements can cause distinctive image artifacts. Conforming elements share nodes

Radiosity and Realistic Image Synthesis	147
Edited by Michael F. Cohen and John R. Wallace

CHAPTER 6. RENDERING

6.2 MESH CHARACTERISTICS AND ACCURACY

Figure 6.13: (a) A surface approximation based on a regular subdivision. (b) The same surface approximated using elements with poor aspect ratios but oriented so as to provide a better approximation, (after Schumaker, 1993).

Figure 6.14: The top mesh shows a poorly graded transition between regions of high and low mesh density. The bottom well-graded mesh provides a smoother transition.

Radiosity and Realistic Image Synthesis	148
Edited by Michael F. Cohen and John R. Wallace