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

CHAPTER 8. MESHING

8.5 DISCONTINUITY MESHING

Figure 8.20: Determining penumbra and umbra volumes using Nishita and Nakamae’s algorithm. (After Nishista and Nakamae, 1985).

8.5.3 Shadow Volume Algorithms

Early algorithms deal only with the subset of events that define the boundaries of the umbra and penumbra. Nishita and Nakamae [175] determine these boundaries by computing shadow volumes formed by an object and each vertex of the light polygon (see Figure 8.20.) The umbra volume for a single occluder is defined by the intersection of the shadow volumes. The penumbra volume is defined by the three-dimensional convex hull containing the shadow volumes. The intersection of the umbra and penumbra volumes with surfaces defines the penumbra and umbra boundaries. This approach ignores discontinuities within the penumbra.

Campbell [42] also resolves only the outer penumbra and umbra boundaries. Like Nishita and Nakamae, Campbell constructs umbra and penumbra volumes for each source-occluder pair. However, he avoids computing a threedimensional convex hull by constructing the volumes directly from critical surfaces.

Campbell’s algorithm assumes convex source and occluder polygons. For each edge of the occluder, or blocker, there exists a critical surface formed with respect to each vertex of the source. The minimum blocker extremal plane is defined to be the critical surface that forms the minimum angle with respect to the plane of the blocker (see Figure 8.21). A minimum blocker extremal plane exists for each occluder edge. Likewise, there is a minimum source extremal plane for each edge of the source. The penumbra volume consists of the intersection

CHAPTER 8. MESHING

8.5 DISCONTINUITY MESHING

Figure 8.21: The minimum and maximum extremal planes and the penumbra volume created using the minimum blocker and source extremal planes. (After Campbell, 1991).

of the negative halfspaces of all of the minimum blocker and source extremal planes (see Figure 8.20). The umbra volume is constructed similarly, using the maximum blocker extremal planes.

The resulting umbra and penumbra volumes are stored as BSP-trees. These volumes are then merged with a BSP-tree representing the unified penumbra and umbra volumes for the entire scene to provide an efficient means of testing polygons against the volumes. Chin and Feiner [54] first describe the use of a BSP-tree to represent merged shadow volumes, but for point lights only. The merging of occlusion and umbra volumes for area lights requires more general methods, for which Campbell uses algorithms developed by Naylor [171]. Later work by Chin [55] describes a similar generalization of the BSP-tree shadow volume technique to area lights.

After constructing the shadow volumes, Campbell’s algorithm tests each polygon in the scene against the shadow BSP-tree. Polygons are split where they cross planes defining shadow volumes, thus effectively inserting the discontinuity edges. Campbell’s approach allows all regions to be classified as totally in shadow, totally in light, or partially occluded. Shadow testing can be eliminated for the subsequent computation of form factors for nodes within regions classified as totally in the light or totally in shadow. Figure 8.22 shows an example of a mesh produced by Campbell’s shadow algorithm.

CHAPTER 8. MESHING

8.5 DISCONTINUITY MESHING

Figure 8.22: A mesh produced by Campbell’s penumbra volume algorithm. Courtesy of A. T. Campbell III, University of Texas.

8.5.4 Critical Surface Algorithms

Heckbert [121] and Lischinski et al. [154] have independently developed similar algorithms that compute discontinuity boundaries due to VE (and EV) events involving the vertices or edges of source polygons. For a given source polygon, the wedge for each VE event is formed and intersected with the scene polygons. These intersections determine discontinuity edges, which are then inserted into the mesh data structure for the polygon.

For the intersection step, Heckbert tests the wedge against every polygon in the scene (see Figure 8.23). Each intersection forms a two-dimensional span on the wedge surface. A two-dimensional hidden span algorithm determines the visibility of the spans with respect to the wedge vertex. The visible portions of the spans correspond to discontinuity boundaries. These are accumulated for each polygon. Following the intersection step, a line-sweep algorithm is performed on each polygon to connect the discontinuity edges at coincident endpoints, split overlapping edges where necessary, and assemble the result into a connected winged-edge representation. The steps of this algorithm are diagramed in Figure 8.23. Heckbert performs discontinuity meshing for emitters only, on the assumption that discontinuities due to reflected light contribute very little to error in the approximation.

Lischinski, et al. store the scene polygons as a BSP-tree. The construction of the BSP-tree requires additional processing and storage, but has the advantage of allowing the polygons to be visited in front-to-back order when testing for intersections against the wedge. Each intersection of the wedge with a polygon generates a discontinuity edge and clips that portion of the wedge. When the wedge is entirely clipped away, no further polygons need be tested.

Each polygon’s mesh is stored as a two-dimensional BSP-tree. As discontinuity edges are generated, they are filtered down the BSP-tree until they reach leaf nodes, at which point the corresponding faces of the meshed polygon are split. Lischinski also maintains a winged-edge representation of the mesh

CHAPTER 8. MESHING

8.5 DISCONTINUITY MESHING

Figure 8.23: Steps in Heckbert’s computation of discontinuity edges.

Figure 8.24: Steps in the method of Lischinski et al. for the computation of discontinuity edges.

CHAPTER 8. MESHING

8.5 DISCONTINUITY MESHING

Figure 8.25: Artifacts resulting from conventional quadtree-based adaptive subdivision. Courtesy of Daniel Lischinski and Filippo Tampieri, Program of Computer Graphics, Cornell University.

Figure 8.26: Discontinuity Meshing. Courtesy of Daniel Lischinski and Filippo Tampieri, Program of Computer Graphics, Cornell University.

topology, with each node of the tree pointing to an edge in the winged-edge data structure. The steps of Lischinski’s algorithm are shown in Figure 8.24. Figures 8.25 and 8.26 compare results for conventional quadtree meshing and discontinuity meshing using this algorithm. Color plates 32 and 33 show images computed with and without Lischinski’s algorithm.

Heckbert and Lischinski ignore EEE events and VE events involving multiple occluders. Handling EEE events correctly is an involved problem. Algorithms applicable to finding discontinuity boundaries due to EEE events are

CHAPTER 8. MESHING

8.6 TOPOLOGICAL DATA STRUCTURES AND OPERATORS

Figure 8.27: Representation of mesh topology using an embedded graph.

described by Teller [233] for the case of a sequence of convex holes.

8.6 Topological Data Structures and Operators

The representation of a mesh naturally includes data describing node locations, surface normals, material attributes, and so on. In addition to geometric data, a complete representation also includes the mesh topology, which describes the adjacency between mesh elements, element edges, and nodes.

Many of the meshing algorithms described in this chapter depend on knowledge of adjacency. For example, splitting one element during adaptive subdivision often requires inserting a new node on an edge shared by adjacent elements. Computing a gradient at a node may require visiting adjacent nodes. A data structure that maintains the adjacency, or topology, of these entities explicitly can greatly improve the efficiency and simplicity of the algorithms described in this chapter.

The topology of a mesh can be represented by an embedded graph, that is, a graph that has been mapped to a surface. The faces of an embedded graph are the regions of the surface bounded by the graph edges. The graph vertices correspond to mesh nodes, edges correspond to element boundaries and faces correspond to elements (see Figure 8.27). When the meshed surface does not form the closed boundary of a solid, there are no elements adjacent to the outer edges of the mesh and a “pseudo-face” is often assumed in order to maintain topological consistency.

CHAPTER 8. MESHING

8.6 TOPOLOGICAL DATA STRUCTURES AND OPERATORS

8.6.1 Data Structure Criteria

A variety of data structures for representing the adjacency graph has been developed for solid modeling. Several are described and evaluated by Weiler in [261, 262] and by Mantyla in [158]. The data structures compared by Weiler are edge-based; all information required to find adjacent vertices, edges or faces is contained in the edge record. The winged-edge data structure, first developed by Baumgart for computer vision [22], may be the most familiar example, but many others have also been devised.

Topological data structures can be compared on the basis of storage and performance. Evaluation of the storage required to represent a given number of edges (or vertices) is straightforward. (A comparison of the storage requirements for several data structures, including the winged-edge, can be found in [6, 261].) However, compactness must be weighed against performance; an extremely succinct data structure may require extra pointer manipulations to extract certain information.

Performance is less straightforward to evaluate. The number of field accesses required for various operations is often used as a measure. Performance also depends on how often operations access different records, since these may reside on different pages in virtual memory. Papers by Ala and Woo contain experiments and discussions that help clarify these issues [6, 268]. However, actual performance will depend strongly on the mix of operations typical of the application. A careful evaluation of data structures would require statistical measurements of the operations performed by the particular application.

To date no such evaluation of topological data structures has been made for radiosity meshing. One reason is undoubtedly that the cost of numerical computation (integration, interpolation, etc.) tends to overwhelm other costs. Storage, on the other hand, is of immediate practical concern. Image synthesis is often a small component of a larger application, such as an architectural or industrial design package, and the additional memory requirements of radiosity are a serious consideration.

8.6.2 The Winged-Edge Data Structure

The winged-edge data structure (WED) will be used to illustrate how a topological data structure can be used to represent a mesh. The winged-edge data structure is fairly compact, provides reasonable performance, and has often been used for radiosity [61, 121, 154].

Figure 8.28 contains a diagram of the basic winged-edge data structure. As the name implies, the basic record is that of an edge. The record points explicitly to the pair of faces that are adjacent to the edge. It also points to the two vertices that are the endpoints of the edge (in order, thus orienting the edge). At each

CHAPTER 8. MESHING

8.6 TOPOLOGICAL DATA STRUCTURES AND OPERATORS

typedef struct {

stmct edge *vertex_edge ; } VERTEX ;

typedef struct {

struct edge *face_edge ; } FACE ;

typedef struct edge { VERTEX *head_vertex ; VERTEX *tail_vertex ; FACE *right_face ; FACE *left_face ; struct edge *cw_right_edge

struct edge *ccw_right_edge ; struct edge *cw_left_edge ; struct edge *ccw_left_edge ;

} EDGE ;

Figure 8.28: The winged-edge data structure.

endpoint, the next edge (or wing) around each of the adjacent faces is stored in both the clockwise and counterclockwise directions. The data structures for a face and a vertex need only keep a single pointer to any of the adjacent edges.

Operations on the topology represented by the winged-edge data structure consist of either modifications to the topology or queries about adjacency relationships. Modifications to the topology can be expressed in terms of Euler operators [22]. (Good introductions are provided by [117, 158, 159, 267].) Euler operators are so called because they maintain Euler’s formula, which expresses the relationship between the number of vertices, edges and faces in a topologically consistent adjacency graph. For a simple polyhedron with no holes this formula is

where V, E, and F are the number of vertices, edges, and faces,respectively.6 A complete set of Euler operators provides for all possible modifications

to the topology, and guarantees that the topology following any operation will be consistent. In addition, the use of operators simplifies the coding of higher

6The more general formula is given by V –E + F = 2 – 2g, where g is the genus of the polyhedron. Generalizations also exist for other dimensions.

CHAPTER 8. MESHING

8.6 TOPOLOGICAL DATA STRUCTURES AND OPERATORS

Figure 8.29: Operations on the winged-edge data structure.

level meshing operations by encapsulating the manipulation of the underlying data structures.

A complete set of Euler operators requires only five operators and their inverses [159]. Assuming no holes for the purpose of this discussion, these can be reduced to three. The three operators, plus one more included for convenience, are listed here:

1.Make-Vertex-Face (MVF) creates a new graph by creating a single vertex and face.

CHAPTER 8. MESHING

8.6TOPOLOGICAL DATA STRUCTURES AND OPERATORS

2.Make-Edge-Vertex (MEV) adds a vertex and connects it to an existing vertex using a new edge.

3.Make-Edge-Face (MEF) connects two existing vertices to create a new edge, which splits an existing face into two faces.

4.Split-Edge-Make-Vertex (SEMV) creates a new vertex and a new edge by splitting an existing edge into two edges.7

Figure 8.29 shows how a simple quadtree meshing scheme could be implemented using Euler operators. A graph representing the original geometry is first created using an initial MVF operation, followed by several calls to MEV, and finishing with MEF to close the polygon. (One of the two resulting faces is a “pseudo-face” that represents the exterior region of the graph). The polygon is then split along the vertical and horizontal directions using SEMV to split edges and MEF to split faces by linking vertices with new edges. Finally, one element of the initial mesh is split further, showing how the use of a topologically complete data structure correctly handles the insertion of the new vertex (labeled A in the diagram) along the shared edge.

Once the mesh has been created, higher level algorithms will need to query the topological data structure for adjacency information. For example, various ways of traversing the topology can be thought of as queries: get next face, get next vertex around face, get next edge around vertex, and so on. The implementations are straightforward in most cases, although edge orientation requires special handling. When traversing the boundary of a face in a wingededge data structure for example, edges may be oriented arbitrarily. Therefore, comparisons are required to determine which endpoint of the edge is the next vertex around the face.

The basic topological data structure can be augmented with extra information to speed up certain queries. Back-pointers might be added to allow direct access to the parent object record from the vertex record. An extra pointer can be added to the vertex record, allowing nodes to be linked into a list that can be traversed directly during the solution, when it is necessary to visit all the nodes of the scene in sequence to compute form factors or to update radiosities.

Finally, certain algorithms require the imposition of a mesh hierarchy. Hierarchical data structures, like quadtrees or BSP-trees, can be maintained in parallel with the topological data structure, with nodes of the tree pointing to faces of the topology.

7A helpful approach to implementing winged-edge operations is described in [98].