of 12

Radiosity for dynamic scenes in flatland with the visibility complex

Radiosity for dynamic scenes in flatland with the visibility complex Rachel ORTI, Stéphane RIVIERE, Frédo DURAND and Claude PUECH imagis / GRAVIR - IMAG, BP 53, F Grenoble Cedex 09, France (
0 views12 pages
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Radiosity for dynamic scenes in flatland with the visibility complex Rachel ORTI, Stéphane RIVIERE, Frédo DURAND and Claude PUECH imagis / GRAVIR - IMAG, BP 53, F Grenoble Cedex 09, France ( Abstract The radiosity method is particularly suitable for global illumination calculations in static environments. Nonetheless, recent applications of image synthesis such as architectural simulation or lighting design require the ability to modify environments. Previous methods have attempted to deal with dynamic environments (environments where the geometry, the material properties, etc., can change) but still suffer some limitations in the case of moving objects. One of the main problems remaining is the efficient and accurate detection of which form factors must really be recomputed, since their calculation is the most time-consuming part of the radiosity method. To correctly understand and solve this problem, we start with a method in D for polygonal scenes using the visibility complex. It is a powerful data structure representing the visibility relationships between objects in the plane. We have developed and implemented an algorithm which uses this structure to efficiently compute the discontinuity mesh and the form factors for static scenes. We also propose an extension to our algorithm to efficiently update only the modified form factors when an object is moving. This approach enhances our understanding and will hopefully lead to efficient solutions in 3D. Keywords: global illumination, radiosity, discontinuity mesh, form factor, visibility, dynamic environments 1. Introduction The radiosity method is particularly suitable for visualization of interiors and can thus be used in many applications such as architectural simulation or lighting design. Applications of this type require the capability to modify the scene (move objects, change the material properties, etc.) and also to deal with complex geometry. To be usable, they must use algorithms fast enough to provide a new global solution whenever changes are made to the scene, at interactive if not real-time update rates. The requirement to rapidly render complex environments has motivated research efforts in visibility processing, since visibility calculations are very important in the rendering process. Specifically in the radiosity method most of the time is spent in the calculation of the form factors (more than 50% of the time in the case of efficient algorithms as shown in 1 for example). Therefore the idea is to build a special data structure that allows for easy determination of the set of potentially visible objects. Most notably, Teller, 3 has proposed global visibility algorithms that preprocess polygon databases in order to accelerate visibility determination during illumination calculations. Although the radiosity method was initially applied to static environments 4, 5, recently researchers have attempted to deal with dynamic environments 6, 7, 8, 9. These approaches typically begin with a current radiosity solution and then try, for a given modification of the environment, to incrementally compute a new solution from the current one. The difficulty remains in the efficient and accurate identification of the form factors that really need to be recomputed, without considering the others. In order to limit re-computations, several different approaches have been proposed. Chen 7 has limited the computation of the form factors by considering only the imagis is a joint project of CNRS, INRIA, Institut National Polytechnique de Grenoble and Université Joseph Fourier. fraction of the hemi-cube that bounds the extent of the projection of the new object. George et al. 8 have used a shadow volume to cull away patches that cannot possibly require a new form factor. These two methods that use progressive refinement radiosity, still perform unnecessary computations and are not interactive in the case of moving objects. Shaw 9 has applied hierarchical radiosity to dynamic environments. She has used a motion volume that encloses the range of motion for an object (in the same spirit as 6 ) and has considered as affected only those links that intersect this volume. But still too much re-computation is performed. No method has yet been proposed which exactly identifies the form factors that really need to be recomputed. In 10 we discussed some computational geometry aspects related to the method we present here, but for curved objects. In this paper, we propose a method permitting the efficient computation of the discontinuity mesh and the form factors for D polygonal scenes. This method uses the visibility complex (a data structure that represents visibility relationships between objects in the plane). The complex allows us to consider only the mutually visible parts of a pair of objects and thus permits the computation of only the strictly necessary form factors. We have a running implementation which computes the discontinuity mesh and radiosity using the visibility complex for static scenes. We also detail an algorithm for the form factors in dynamic environments and show that the visibility complex, by permitting the efficient identification of the visibility relationships that change, allows us to restrict the re-computation of the form factors to exactly those that change. The geometric complexity of the visibility relations led us to begin this research with a thorough solution in D. In two dimensions analytic solutions permit the validation of the models, and in addition, the scenes are much simpler to understand and allow for better overall comprehension of the phenomena. The structures used (the augmented visibility complex in particular) permit a comprehensive description of all visibility relations required for form-factor calculations. These structures, manageable in D, give a better comprehension of the intricate visibility interactions for dynamic scenes, a step necessary for the development of truly efficient algorithms for radiosity in dynamic 3D environments. This approach, i.e. the study of the simpler two-dimensional case to facilitate understanding, leading to a 3D solution, is common in illumination research (e.g., for discontinuity meshing and radiosity calculations 11, 1 or wavelet radiosity approaches 13, 14 ).. The visibility complex.1. Visibility computation The most time consuming part of a radiosity algorithm is the visibility calculation when computing form factors. For each pair of patches, one must find the part of one patch which is visible from the other. The complexity can be greatly improved if we can consider only pairs of patches that are mutually visible, and if, for those pairs, we can have direct access to their mutually visible parts. To solve visibility problems in the plane, computational geometry has given particular attention to global data structures that encode visibility information. They are used to efficiently solve global visibility problems or to answer multiple queries concerning local visibility problems. A well known data structure is the visibility graph. Its vertices are, for a polygonal scene, the polygon vertices, and its edges link two mutually visible vertices. But because of its discrete structure, it does not carry enough information for our visibility computation. To cope with this problem, Pocchiola and Vegter 15 introduced a new data structure, the visibility complex, which represents sets of rays going from one object to another... The visibility complex We consider here polygonal scenes in the plane. The elementary objects considered are not the polygons themselves, but the segment lines forming their sides. When dealing with visibility, one deals with oriented maximal free line segments, that is line segments in free space of maximal length. Such segments will be called rays. The extremities of a ray lie on the border of the two objects that stop the ray. These two objects O l and O r (stopping the ray on its left and on its right) constitute the label (O l,o r ) of the ray. The visibility complex is the set of equivalence classes of rays according to the following equivalence relation: two rays are equivalent if one can pass continuously from one to another while keeping its label constant. These equivalence classes are of three types: faces, edges and vertices. The faces are D components representing rays going from O l to O r without touching any other object (see Figure 1). The edges are 1D components representing rays with label (O l,o r ) passing through the same polygon vertex. Finally the vertices are 0D components representing rays passing through two polygon vertices, that is edges of the visibility graph. An edge is therefore delimited by two vertices. Edges represent limits of zones of constant visibility. They bound the faces of the complex. A study of the complex also shows that an edge is incident to at most three faces and that a vertex is incident to four edges and to six faces. The visibility complex was introduced in 15 face (,) edges vertices Figure 1. Elements of the visibility complex. for scenes of curved convex objects in the plane, where an optimal incremental algorithm for computing the complex is given. An optimal sweep algorithm is described in 16. The complex is studied for general polygonal scenes in 17, where an optimal sweep algorithm is given..3. Duality Sets of lines (or rays) are difficult to handle directly, and visualizing the elements of the visibility complex and their incidence relation is not evident. Dealing with lines (or rays) becomes easier when considering them in a dual space. The duality principle allows the representation of a line in the scene as a point in a dual space. In this paper we consider the duality relation which associates with the line l : y = ax b the dual point l :(a, b). Notice that rays contained in the same line are mapped to the same dual point. Visibility along a line changes when the line crosses a polygon vertex of the scene. In the dual space, the set of lines passing through a polygon vertex p :(a, b) is the dual line p : y = ax b. The vertices of the polygonal scene induce an arrangement of lines in the dual space, supporting the edges of the visibility complex. Figure illustrates the correspondence of the elements of the complex between the scene and the dual space and also illustrates more clearly the structure of its faces. A face has two extremal vertices (the left one and the right one) separating the edges bounding the faces into two sets: the upper and lower chains of edges. Sets of rays are now turned into sets of points in the dual space and are easier to handle. Figure 3 shows a view lu 1 ru vertex 1* * face lu* face (,) ru* 3 ld rd edge rd* ld* 3* Scene Dual space Figure. Correspondence between the scene and the dual space. of the complex around one of its vertices. This figure also shows more clearly the incidence relations between elements of the complex. 3. Radiosity in flatland 3.1. The form factor The form factor F ij between two surface elements A i and A j is the fraction of energy leaving A i reaching A j 5 : F ij = Radiative energy reaching A j from A i Total radiative energy leaving A i in all directions. (1) Oqp q Op Op- Oqq Op Op- Oq q* p* (Oq,) (,Oq-) (,) (,Op) (Op-,) (Op-,Oq-) Oq Figure 3. Visibility complex around a vertex. This quantity is expressed in 3D as a double integral over areas, which takes into account the visibility between surfaces. In the D case, line segments are the equivalent of surfaces and thus the form factor becomes a double integral over segments. Figure 4 shows its expression for two elements L i and L j. N i L i dl i φ i r φ j L j dl j N j F ij = 1 L i L i L j cos φ i cos φ j H ij dl j dl i, r { 1 if dli and dl where H ij = j are mutually visible 0 otherwise. Figure 4. Formulation of the D form factor. The form factor is a strictly geometric quantity: it depends only on the shape and relative location of elements in the scene. This property appears in the string rule established by Hottel 18 in thermal engineering that we will use to compute the form factors: String rule: The D form factor between two segments C i and C j is obtained by computing the length of strings drawn between the endpoints of C i and C j (see Figure 5). The strings stretched from the endpoints of C i to the corresponding endpoints of C j (i.e., a to c and b to d) are called un-crossed strings, and those drawn to the opposite endpoints on C j (i.e., a to d and b to c) are called crossed strings. The form factor between the two segments C i and C j (with lengths L i and L j respectively) can be expressed as: length crossed strings length un-crossed strings F ij =. () L i When some parts of C i and C j are not mutually visible, the strings are simply stretched around the obstruction (see the string between a and c in Figure 5) and formula is still valid. a Ci b e un-crossed strings crossed strings c Cj d Figure 5. Strings for two portions of curves C i and C j. When considering the visibility complex, the form factor defined by a weighted sum of curve lengths can be re-expressed as a weighted sum depending on vertices bounding a face of the complex: Expression in a dual space: The line segments that compose the strings corresponding to a pair (C i,c j ) of objects are edges of the visibility graph. These edges correspond to vertices in the visibility complex which bound the corresponding face with label (C i,c j ). More precisely, the two extremal vertices correspond to the crossed strings and the other vertices of the two chains of edges of the face correspond to the two un-crossed strings (see Figure 6a). If we compute the length d(v) of the corresponding line segment in the scene for each vertex v of the complex, then the string rule () becomes: { vboundingface F ij = d (v), where d d(v) if v is an extremal vertex (v) = (3) L i d(v) otherwise If the opposite extremities of C i and C j are hidden by an obstacle, some segments of the strings do not Ci i (a) i1 p j1 Cj i1* - p* - j1* p* j* i* - j - i j S=(i1,j) (i,j1) -(i1,p) -(p,j1) -(i,j) (b) S = (i1,p)(p,j)(i,p)(p,j1)-(i1,p)-(p,j1)-(i,j) = (i,p)(p,j)-(i,j) Figure 6. String rule in the visibility complex. Ci i1 p j1 Cj j* i* correspond to vertices bounding the face. But these segments are part of the crossed and the un-crossed strings, so they disappear from the computation and the rule is still valid (see Figure 6b). 3.. Discontinuity meshing and radiosity sampling In order to apply the radiosity method to a polygonal scene, each edge of a polygon must be divided into small elements (or samples) for which the form factors must be computed. The accuracy of the radiosity solution depends on the discretization of the environment. Changes in visibility in the scenes produce discontinuities of illumination and indirect illumination. Such discontinuities are important to consider when computing the samples since an element typically has constant radiosity. An appropriate method is to position the elements according to a discontinuity mesh whose boundaries are placed on the radiosity discontinuities caused by occlusions 11. However, this meshing strategy traditionally requires many geometric calculations which make it expensive to use. The visibility complex is very useful in this case since it allows to compute the discontinuity mesh very easily. In what follows we describe an augmented structure to directly provide the form factors for the samples obtained. Let us consider a face (O l,o r ) in the complex. If we consider O l as being lit by O r, then the objects associated with the edges that bound the face introduce discontinuities in the illumination of O l. More precisely, the points of discontinuities (l i ) are the intersections between O l and the (extended) edges of the visibility graph that bound the face. In the complex, the face is subdivided by dual lines that pass through the dual point of O l and the vertices bounding the face. Figure 7(a) shows an example where a sub-face and the corresponding set of rays in the scene are highlighted. They correspond to rays that can see the lower extremity of O r but that are blocked by the vertex when looking at the upper extremity of O r. The same reasoning applies when considering O r as being lit by O l. Obstacles induce illumination discontinuities (r i ) on O r, and a corresponding subdivision appears in the corresponding face in the complex. Figure 7(b) illustrates the set of rays leaving O r that can see both extremities of O l. If we divide both objects O l and O r into elements according to their illumination discontinuities (l i ) and (r i ), we notice that the form factors between these elements can be expressed by considering the sub-faces of the complex induced by both subdivisions. Figure 7(c) shows the set of rays going from patch [l 1,l ] to patch [r 1,r 3 ] in the scene and the corresponding sub-face in the dual space. l1 l l3 1 1* * 3 l1* l* 3* l3* 1 3 r r1 r3 1* 3* * r* r1* r3* * (a) (b) * l1 1 r l l3 r1 r3 3 Scene (c) Dual space Figure 7. Discontinuity mesh for a face 4. Implementation - Results A program has been implemented which first computes the visibility complex for a D polygonal scene. It then uses this structure to compute the discontinuity mesh and the radiosity solution of this scene. It also provides different types of visualization: the scene with the radiosity value for each element, the radiosity matrix and a 3D visualization of the visibility complex. In this section we give some details about the different algorithms we have implemented Computing the discontinuity mesh Heckbert studied radiosity in flatland for polygonal scenes 11, 1.In 1, he computed D 1 discontinuities (discontinuities occurring at critical points where there is a change in visibility) with a straightforward ray tracing algorithm running in O(n 3 ) time (where n is the number of edges of polygons). As he states, the running time can be improved to O(n log n) by using a radial sweep-line perspective visibility algorithm. In our program, the visibility complex is constructed using the code of the output-sensitive algorithm of 17. This algorithm runs in optimal O(mn log n) time (where m is the number of vertices of the visibility complex, that is the size of the visibility graph, which is Ω(n) and O(n )), and is efficient in practice too (see 17 ). Once the visibility complex is built, the discontinuity mesh can be computed by considering the vertices of the complex, in O(m) time. Figure 8 shows the algorithm we use to compute the discontinuities. Care has been taken to implement all parts of the algorithm using the appropriate data structures, permitting truly optimal running time. The different types of discontinuities named (1), (), (3), and (4) in the algorithm are illustrated in Figure 9. The discontinuity of type (5) is not illustrated since it is a symmetrical case of type (4). In Figure 9, the objects O l and O r associated with the face correspond to the edges of polygons with endpoints (A 1,A ) and (B 1,B ) respectively. 4.. Computing the form factors between elements The form factor between two elements is null if these elements are not mutually visible. In practice, such situations are frequent and should be taken into account in order to avoid unnecessary computations. Heckbert 1 has noticed in his tests that matrix density α (α is the fraction of nonzero elements in the radiosity matrix) typically ranged between 10% and 40%. The visibility complex is very useful in this case, since it allows one to consider only pairs of mutually visible objects and then to accurately examine only the mutually visible parts of these objects. To compute the necessary form factors between two objects O l and O r, we just have to consider all the faces of the complex labelled (O l,o r ). We define a zone of interference associated with a given edge of a face of the complex, as the zone in the scene which is between
View more
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!