George Drettakis

Eugene Fiume

Structure-Directed Sampling, Reconstruction, and Data Representation for Global Illumination

The structure of the sampling and reconstruction process, as well as that of the scene and its data representation, can be utilised to effect significant benefits in global illumination algorithms. As an introduction, previous methods that have utilised this structure are reviewed and some possible improvements are suggested. A new framework is then introduced that utilises the concept of an oracle as an abstraction to provide information about the complex computational processes of global illumination. This framework is based on the recognition of the relevant aspects of scene structure, the description of the problems to be solved in terms of oracles, the use of structure to create approximations to the oracles, and finally techniques to monitor the cost, error and quality of the approximations. Each aspect of the framework is discussed in detail, presenting certain oracles that are useful for global illumination algorithms. Two examples of its application are presented. The first example is a simple local illumination problem, that allows us to consider several aspects of the oracle methodology. The second example uses the framework to enhance the progressive refinement radiosity based solution to global illumination. Both examples illustrate the benefits of the proposed framework. Finally, some suggestions are made for future research directions.

Introduction

The sampling theorem for the digital representation of continuous signals places exact constraints on the class of signals that are expressible when using a fixed set of regularly-spaced samples. For our purposes, the ''signal'' will be an illumination function defined throughout a scene. Many signals can interpolate any finite set of sample values, and the ''least complex'' of these signals, which is usually an alias for a more desirable signal, is unlikely to be visually satisfactory, unless we are careful to use prefiltering to reduce the class of signals that we intend to represent. The additional facts that, in computer graphics, reconstruction mechanisms in displays are often beyond our control, and that illumination signals inherently have significant high-frequency content, implies that the sampling rate should be even further increased; if this is not possible, then an even smaller class of signals can be faithfully represented. This gloomy news is of course simply a paraphrasing of well-known results from signal theory. However, for several reasons, the news is not nearly as bad as the theory suggests. First, results from texture mapping have shown that careful filtering can dramatically improve image quality using a fixed sampling rate. This suggests that current sampling rates are generally visually adequate. Second, the human visual system appears to be fairly adept at coping with some forms of noise. Third, our knowledge of scene structure and of the rendering process can be used to reduce the set of samples required to represent a given illumination signal. If we are careful, therefore, a much smaller set of illumination samples (associated to objects in space) than the set of image samples can be taken. The problem of creating a rectangular set of pixel samples then reduces to performing an appropriate resampling of the set of illumination samples.

Global illumination models and their corresponding algorithms typically require a large amount of storage and computation to simulate light-object interactions, and to finally generate a two-dimensional image. In this paper we introduce the idea of using structure-directed rendering to effect significant computational and storage savings. There are two relevant aspects of structure in the rendering process. The first is the structure of the actual scene, and that of its data representation. The second is the structure that exists in, or is imposed on, the sampling and reconstruction process during image generation.

We will propose a framework that utilises these forms of structure, with two main goals in mind. First, to achieve better understanding of global illumination and the rendering process, and second, to develop a set of suitable abstractions and conceptual mechanisms that will lead to better algorithms for rendering. The framework that we will introduce hinges on the following four components: (i) the identification of the aspects of the scene and sampling/reconstruction structure that are relevant for the specific problem being solved, (ii) the development of the oracle concept, which is a convenient abstraction allowing us to reason about illumination and rendering, (iii) the development of approximations to these oracles that will lead to algorithms and practical solutions, and (iv) error and quality metrics allowing us to evaluate the quality of the approximations developed.

Before entering a detailed discussion of this framework, we will try to give an intuitive feeling for how knowledge of structure can be used in rendering. The first example is the selection of samples to be used in illumination calculations. If we have a totally diffuse environment, we only require a small number of samples, placed at locations on the surfaces where there is a significant change in illumination. With appropriate reconstruction kernels to interpolate these sample values, accurate pictures can be produced from very little information. If we compare this to the amount of information required in a traditional radiosity-based solution, where the surfaces have to be blindly subdivided into patches, and possibly elements, we see that there are significant savings to be had (see Fig. 1). If a process existed that could choose the best sample locations and the best filters for reconstruction, it would in effect be an oracle for image synthesis. In its pure and perfect form, such a process is infeasible, since it would require previous knowledge of the distribution of illumination, a way to minimise the number of samples selected and also an inverse-reconstruction solution to choose the appropriate filters. Nevertheless, a number of meaningful approximations to an ideal oracle can be made, using known properties of a given scene, and structuring the sampling and reconstruction process.

Sparse Sampling

Patch-based subdivision Fig. 1

: Gains from Sparse Sampling

A second example illustrating a similar concept is that of importance sampling in Monte Carlo methods. In effect, an ideal importance sampling technique attempts to concentrate the samples taken to approximate an illumination integral, based on visibility and light power information, on those regions that contain the largest amount of information [START_REF] Hammersly | Monte Carlo Methods[END_REF]. Again, given an appropriate oracle, the computation of an integral over a hemisphere around a point collecting or shooting illumination, could be sped up considerably. The oracle would identify which parts of the hemisphere contribute the most to the integral, and the sampling operation of space would then be limited to these regions. Utilisation of knowledge about scene structure, sample placement information and corresponding reconstruction techniques, can allow an approximation of such an oracle.

The concept of structured rendering has appeared in various forms in previous work. In the following section we review such techniques, and discuss how further use of structure could enhance these methods. In the next section we introduce our proposed framework. This involves a discussion of scene properties used in the rendering process, identifying which of these are more important for global illumination. We then discuss the oracle concept in more detail and how such abstractions can be approximated. Some error and quality measures are then proposed. We continue with two examples. In the first, a fully detailed casestudy is presented, in which the framework is applied to solve a simple shading problem. To give an indication of how the framework applies to global illumination problems, the second example shows how a set of approximations can result in certain benefits to the progressive refinement, radiosity-based algorithm. We close with a discussion and suggestions for future research. Throughout the text we refer to the sampling operation performed by a grid superimposed on the image-plane as image-sampling; the term space-sampling refers to the operation of sampling the hemisphere above a point or area to determine illumination.

The Use of Structure in Previous Approaches

Structure, either in the form of the data-representation scheme, or in the sampling and reconstruction process, has been previously utilised to varying degrees. We will concentrate on a limited number of approaches, in which some effort has been made to combine more than one aspect of structure to attain a certain goal, thus allowing us to illustrate the importance of the concept of using an integrated approach. We examine cases from both the ray-tracing and the radiosity-based global illumination model. Ward et al. in (Ward et al. 1988) and (Ward and Rubinstein 1988) discuss a sparse sampling technique for the calculation of diffuse illumination in a ray-tracing environment. Four instances of structure are utilised in this method. Sparse Sample Selection. When a ray intersects a surface, diffuse illumination is calculated in one of two ways: the neighbourhood is searched to determine if there are enough diffuse samples nearby, in which case an interpolation is performed, otherwise a hemispherical integral is approximated using a Monte Carlo technique. An error metric based on distance between samples and a weighting function, derived from this distance, is used for sample selection and interpolation respectively. Stratified Sampling. The Monte Carlo integral is calculated by segmenting the hemisphere into equal regions to effect faster convergence than a simple ''crude'' [START_REF] Hammersly | Monte Carlo Methods[END_REF] or ''blind'' Monte Carlo solution. Data Structure Utilisation for Sample Location. The sparse samples described above are located using a data-structure that maintains a list of such samples allowing faster access, for interpolation and neighbourhood sample determination.

Ray-Tracing Approaches

Simple Reconstruction. For reconstruction, the weights used in the interpolation of the diffuse sample values are based on the distance of the point to be shaded to the various sample locations.

In this method, the scene structure, encoded in the octree, is used in the sample selection and interpolation calculations, resulting in significant computational savings. The sample selection process utilises structure in the following sense: (a) new samples are chosen based on an error approximation metric, and (b) when the new values require an integration to be performed, the nature of the hemisphere sampling operation is taken into account to allow the usage of stratified sampling. In addition, the sample selection metric is used in the specification of the weights for reconstruction, albeit in a somewhat arbitrary fashion.

Thomas et al. [START_REF] Thomas | Anti-aliased Ray-Tracing with Covers[END_REF]) introduce the cover data representation scheme to enchance the ray-tracing algorithm, that allows efficient determination of shadow boundaries and contours. This is a form of structured data representation for sparse image-sampling. Cover Data Structure. Each object is covered by an inside and an outside cover that are then intersected with the ray to determine proximity to silhouette contours and shadow boundaries. Sparse Pixel Sampling. Instead of sampling every pixel in a scan-line, pixels are sampled in a uniformly sparse fashion. When a region of interest is identified by the covers, denser sampling is employed.

The algorithm just described introduces a new data-representation scheme (the covers), specifically built to aid in the determination of the required image sampling rate. This is an example of a new structure being imposed on an existing rendering process (ray-tracing), as opposed to the recognition of underlying or previously existing structure.

Radiosity-Based Approaches

In the radiosity-based approaches, data-representation structure exists in all scenes, due to the subdivision of the surfaces into planar patches, that are essentially area samples in the rendering process [START_REF] Goral | Modelling The Interaction Of Light Between Diffuse Surfaces[END_REF]. Moreover, the hemi-cube [START_REF] Cohen | An Efficient Radiosity Approach for Realistic Image Synthesis[END_REF] defines the way in which the three-dimensional space is sampled. Both these aspects are simple forms of structure, but are not specific attempts to achieve benefit from either recognising, or imposing new, structure in the rendering process of the specified algorithm. Nevertheless, there have been cases that do introduce or utilise such information, and we discuss them in what follows. Substructuring. The substructuring technique [START_REF] Cohen | An Efficient Radiosity Approach for Realistic Image Synthesis[END_REF]) introduces an additional level of subdivision that is used to sample the patches in the hemi-cube computation. The additional subdivision, in essence a hierarchical sampling approach, occurs when deemed necessary by examining the variation of the radiosity values calculated on a surface. An iterative approach is used until desirable convergence is achieved. Space supersampling is thus achieved by the introduction of subsamples, called elements. One way of viewing the substructuring process, is that the knowledge of scene structure conveyed by the radiosity gradient is used to determine the sampling rate and to improve image quality. Ray-Tracing Sampling. In [START_REF] Wallace | A Ray-Tracing Algorithm for Progressive Radiosity[END_REF]) an alternative to the hemi-cube sampling approach is introduced, as applied to the progressive refinement solution [START_REF] Cohen | A Progressive Refinement Approach to Fast Radiosity Image Generation[END_REF][START_REF] Chen | A Progressive Radiosity Method and its Implementation in a Distributed Processing Environment[END_REF]. All elements in the scene receive power, but an adaptive sampling approach is used when such sampling of a source (an emitting patch), is required. This adaptive technique is based on the magnitude of the contribution of each region of the source to the form-factor, that depends on the geometrical configuration. The use of adaptive sampling imposes a different structure in the sampling process, utilising knowledge of scene geometry information.

In these methods, there has been some interaction of the structure of the underlying data representation (patches or elements) and the process of space sampling to determine formfactors. Here, as in the ray-tracing approaches, reconstruction has received little attention. This is due to the fact that simple interpolation schemes usually suffice for the purposes of the diffuse environments modelled, at least for the image-sampling case. Finally the viewindependence constraint has limited the introduction of new data representation schemes (such as space subdivision) that could be utilised in the space-sampling process.

Additional Structure Utilisation in Existing Techniques

We now discuss some possible enhancements to the methods described above, that will give a broader view of how the knowledge of structure can be beneficial. For illumination models based on ray-tracing or on radiosity, significant benefits can be achieved, either with the introduction of different data representation, or by taking advantage of existing aspects of the rendering process. We discuss a few such possible improvements to existing methods.

Ray Tracing

Sparse Sampling. In Ward et al.'s approach, space-sampling for diffuse illumination could be enhanced by taking geometry information into account. This information could come from the octree structure, or an enhanced hierarchical representation. The stratified sampling approach for the Monte-Carlo space sampling could be improved by utilising what would amount to importance sampling methods. Techniques similar to the shadow acceleration for octrees [START_REF] Woo | Voxel Occlusion Testing: A Shadow Determination Accelerator for Ray Tracing[END_REF]) could be used to determine which part of the hemisphere contributes the most significant part of illumination. This would be especially useful for the case of occluded complex environments, where the existing method is noted to have problems (Ward and Rubinstein 1988). Additional scene information, pertaining to geometry and shadows could be added to the criteria for placing samples, or calculating weights for interpolation. This would enhance the image quality. These operations would constitute a first order approximation to a sample selection oracle (see also Section 3.2). Covers. Another approach to selecting the sparse grid from which to start shooting rays could be based on a scan-conversion first pass (in the spirit of [START_REF] Weghorst | Improved Computational Methods for Ray-Tracing[END_REF])), augmented with a shadow volume calculation. The shadow boundaries and first-level contours could then be immediately located. This would allow the avoidance of all shadow casting operations for diffuse objects. In addition, the information recovered from the cover intersection operations could determine the choice of the different filters to achieve better effects, linking the cover structure to reconstruction (see also Section 3.2).

Radiosity-Based Approaches

Hemicube. The hemicube calculations can benefit significantly from a different approach to patch subdivision. A pyramid of varying resolution could be used instead of maintaining one or two levels (patches and elements), similar to the idea of MIP maps [START_REF] Williams | Pyramidal Parametrics[END_REF]. A related method has been proposed in [START_REF] Houle | Light Source Modelling[END_REF] to sample linear and area light sources in an adaptive fashion. If the view independence constraint is relaxed, then an octree-type structure can be utilised to sample adaptively, concentrating again on the regions of the hemisphere that contain the most powerful and large light sources. Ray-Tracing Solution. Similarly to the hemicube approach, hierarchical structures could be used to reduce computation and storage. The pyramid approach can drastically reduce the number of elements visited by each patch emission operation, since the elements will be in effect adaptively collapsed depending on projected size (onto the light-source).

In both cases, data representation would be enhanced and linked more closely to the sampling and reconstruction process. Additional information can be used in the image-sampling phase, by utilising the tagged sample concept introduced in Section 3.3.

Oracles and Structure: a New Framework for Global Illumination

The discussion on previous work gave some intuition on what is meant by identification of scene structure, and by the imposition of structure in the sample/reconstruction processes. In addition, indications were given on how the knowledge of such structure can be beneficial to global illumination and rendering algorithms.

In this section we attempt to establish a methodology that will allow the development of systematic structure-directed approaches. Initially, we examine some of the scene properties with respect to illumination and the rendering process. We attempt to isolate those aspects of scene structure that are important, and identify appropriate methods for their representation. We view this as an initial proposal that requires future research, that will enhance our understanding of global illumination and rendering by isolating the salient structural properties of scene representation as well as sampling and reconstruction. We proceed with a discussion of oracles, that are a convenient conceptual device allowing us to reason about global illumination and rendering. By discussing ways to approximate these oracles, we show how the framework can lead to practical implementations. Finally we present some initial thoughts on determining the quality and measuring the error of these approximations.

Aspects of Scene Structure

Many properties of scene structure influence the complexity of image synthesis. They can be grouped into four major categories: geometry, viewing parameters, light sources and local illumination. Geometry. A great deal of scene information resides in the geometric models of the individual objects in the scene, as well as in their subsequent interaction for the purposes of determining occlusion and visibility. Geometric primitives usually include objects such as polyhedra, polygons, free-form surfaces, algebraic surfaces, etc.; the ''normal form'' for many of these objects at rendering time is a polygonal decomposition. Object descriptions sometimes include an explicit, or have a natural, parameterisation, as is the case for bicubic surfaces or patches. Others can be assigned an implicit parameterisation, to aid in such applications as texture mapping. Surface information is usually encoded in the object structure, that may include textures or complex shading model parameters. One important aspect of geometrical representation is the storage of bounding volume information, and an optional hierarchical ''level of detail'' structure (for example that in [START_REF] Rubin | A 3-Dimensional Representation for Fast Rendering of Complex Scenes[END_REF]). Finally, the geometry of the scene can be enhanced by structuring information such as relative visibility or object proximity relationships, that are crucial, especially in light transfer calculations. Viewing Parameters. The set of viewing parameters that define the contents of the final image are of extreme importance in any rendering model. A fundamental structure representing this information is the viewing pyramid, based the definition of the viewpoint, the screen size and the near and far planes. This volume allows clipping to be performed when appropriate, provides projected screen size information for objects in the scene, and allows optimisations to be performed, such as backface removal. The use of these parameters has found less use in global illumination models, such as ray-tracing or radiosity-based methods, than it has in traditional scan-line visible surface determination algorithms [START_REF] Sutherland | A Characterization of Ten Hidden-Surface Algorithms[END_REF]). Light Sources. The description of light sources for a computer synthesized scene is extremely important. Primary illumination accounts for a very large number of the important visual effects that we perceive, and it has the benefit that it is somewhat simpler to calculate than secondary lighting. There are three main light source characteristics that need to be described: physical geometry, spatial and spectral light power distributions. There are a number of ways that have been proposed to represent these, concentrating mainly on the latter two. Storage of simple descriptions has been used in [START_REF] Verbeck | A Comprehensive Light-Source Description for Computer Graphics[END_REF] while recent work attempts more compact representations that capitalise on scene structure (including relative light-source size, surface properties, etc.) [START_REF] Houle | Light Source Modelling[END_REF]. Local Illumination. Despite the increasing focus on realistic global illumination models, it is the local illumination models that characterise much of the interaction of light with objects. A local illumination model is responsible for providing low-level, often high-complexity detail. Such models typically simulate several classes of surface microstructure, anisotropy, surface self-shadowing, as well as a wide variety of isotropic spectral and spatial reflectance functions, and many forms of texture detail (such as intensity-, bump-, displacement-, environment-, and reflectance-mapping). At first blush, the problem of exploiting the structure of local illumination models may seem impossibly difficult, but this is not so. Many aspects of local surface variation are represented in compact analytic, tabular, or probabilistic forms. This suggests that approaches based on multiresolution or levels-of-detail techniques, lowpass (or scale-space) filtering, or vector quantisation would be effective.

Recognising that the above scene properties are influential is only a small part of the battle. It is now critical to develop representations that facilitate efficient evaluation where possible, and that identify problem areas of the scene. In most of the above cases, we have pointed to possibilities for efficient representations, and one goal of our research is to demonstrate how these representations are useful to the implementation of oracles.

Oracles for Global Illumination

In theoretical computer science, oracles provide an elegant way of relating problems to one another. For our purposes, an oracle is a fictional black box that given a request, produces an exact answer for certain aspects of the sampling and reconstruction process. They are used as decision making processes that give answers to (usually complex and difficult) questions. Oracles allow us to encapsulate complex decision making into isolated objects or entities. These objects have the ability to access information on scene structure and all aspects of the rendering process, and can therefore reach approximate or sometimes exact decisions. This abstraction, as we shall see in Section 4.1, need not be limited solely to global illumination, but can also be used in other traditional problems in computer graphics.

We present three oracles directly related to the global illumination problem, thus giving an indication of how such a mechanism can encapsulate some of the difficult selection procedures. Optimal Sample Selection. The most obvious oracle that would be useful in a global illumination algorithm is one that selects the minimal set of samples located on the visible surfaces of scene S, from which all the pixel colours could then be satisfactorily reconstructed. Since we are determining a set of samples, a reconstruction method r is implied. As we shall see, the selection of r can be the result of a different oracle, but for the purposes of our definition, we assume that r is given. We informally define oracle O SaSel : O SaSel (S, r, q) = df a sample set {S i } s. t.

{S i } = minimum, w.r.t. image quality metric q. Optimal Space Sampling. A second important oracle would allow us to determine the minimal set of illumination samples in the 3D environment required to accurately compute the illumination at a given point, from the surrounding hemisphere of space. Given an area A for which illumination is being calculated, a hemi-sphere of integration above A, h, we define oracle O SpSa :

O SpSa (S, h, A, τ ) = def a sample {S i } s. t.
{S i } = minimum and calcluated illumination value is within tolerance τ Optimal Image Reconstruction. A third oracle permits efficient reconstruction, and chooses the correct reconstruction kernel for each specific pixel. In this fashion the final image, reconstructed from the minimal sample set (created for example by oracle O SaSel ), is equivalent to the image that would be generated by a given, much more dense, image sampling operation. We define oracle O IR , given sample set {S i } and pixel intensity set {P i } (to be calculated):

O IR (S, {S i }, {P i }, τ ) = def a filter set { f i } s. t.
the time to generate {P i } to tolerance τ is a minimum.

Simple brute-force implementations of these oracles either require the solution of the problem beforehand, or are simply impossible. However, even brute-force approaches may lead to the synthesis of effective approximate oracles based on observations of an ensemble of similar problems. One reason that the formulation in terms of these oracles is actually useful is that it allows us to reason about the complex processes of illumination and rendering in a meaningful way. As such it allows us to isolate the parts that require complicated calculation and knowledge, thus enhancing our understanding of the underlying process. In addition this formulation permits the development of approximations to these oracles in an elegant fashion, achieving modularity and encapsulation of certain complex aspects of the procedures modelled, since in this way only the oracle need have access and knowledge of structure.

Approximating Oracles Using Scene Structure

When defining a problem in terms of our framework, one would typically first define the set of oracles that suit the solution. The next step would be the identification of the scene and rendering process structure that is relevant, and the salient aspects of this structure. One would attempt to identify these aspects and quantify their effect on the selection or decision making process that the oracle is designed to perform. Based on these observations and this formulation an algorithm can be created that approximates the ideal oracle, which we call an oracle approximation. For the purposes of discussion, from now on we will use the terms oracle and oracle approximation interchangeably, since it will be clear from the context which is meant. To clarify the concept of oracle approximations we present a high-level formulation of approximations for the oracles discussed in the previous section.

To approximate optimal sample selection oracle O SaSel , information from all the scene properties should be used. Light source and geometry information can be used to efficiently predict where higher sampling rates are required due to primary illumination phenomena, such as shadow boundaries or variations due to geometry or local illumination characteristics. Sample selection for secondary illumination is a much more difficult problem and must necessarily be related to the techniques for optimal space-sampling, since the space-sampling approach will determine where in space illumination will be distributed to, or collected from. This can be achieved in part by the adaptive methods described in Section 3.4.

To approximate the space-sampling oracle O SpSa , geometry and viewing information must be utilised. View dependent rendering is critical in achieving low space-sampling rates, since numerous optimisations can be made due to specific geometrical configurations, relative visibility and projected size relationships between objects and the screen. ''Level of detail'' hierarchical structures as well as proximity information can result in large savings by avoiding significant computation (and storage) for parts of the scene that have little or no visible effect. It must be emphasized here that sacrificing pure view independence does not mean that the ability for motion or animation is forfeited. To the contrary, a necessary addition to the structured approach to global illumination would be that of temporal structure. Such a discussion will not be included in this paper however.

For a efficient reconstruction oracle O IR we introduce the notion of tagged samples. When the samples are chosen (by O SaSel ) during the sample selection stage, this choice is made due to a scene property, such as geometry, or a preprocessing step, such as shadow boundary determination. The reason causing this choice is stored with the samples, so that it can be accessed in the image reconstruction process. Efficient access mechanisms can be built to determine which samples need to be consulted, and by utilising the tags for each sample, appropriate filters can be chosen, that approximate the optimal. For example, for a set of samples resulting from slowly varying diffuse illumination, wide-support blurring filters can be used, while for boundaries, smaller-support, anisotropic, or even nonlinear filters can be used to maintain, or possibly enhance, the boundaries.

There is an important property of oracles that must be noted here: the computational cost of the oracle (i.e., the decision making process), itself. To make our proposed framework worthwhile, the computation time of the oracle itself must be very small compared to the computation time of the task we are attempting to improve. It may be possible to precompute the cost of the oracle, in which case it can be determined beforehand whether the method has any benefit. Alternatively, if the cost can not be precomputed, then it must be monitored during execution. In either case the implementation must always include a cost calculation mechanism that will allow the system to determine whether use of the oracle is beneficial.

Error and Quality Assessment for Oracles and their Approximations

A fourth important aspect of the proposed framework is the assessment of oracle quality. The quality of the approximation and of the benefits achieved by using the oracle must be continuously monitored. This checking procedure can then be utilised to tune the selection/decision criteria appropriately, achieving higher quality results. This is in effect a true adaptive technique, since the decision logic adapts, depending on performance. Error and quality measures can be derived from the selection criteria and the approximation techniques used. Typically a problem will have an exact solution, and the approximation can be defined in terms of the error resulting from the use of the approximation. The error can then be calculated during execution, and it can be determined whether or not certain selection criteria appear to be performing badly, contributing to higher error rates. If such a case is found, the criteria can be tuned to deliver better results. This error/quality assessment code is an integral part of any oracle's functionality.

Apart from the adaptive capabilities that the error/quality assessment provides for, it allows us to define oracles in terms of a tolerance. Such tolerance measures are usually defined in terms of the mean error μ and variance σ 2 (other statistics may be used too). This is very useful for many aspects of global illumination and rendering, since a requirement of exact equality (e.g., of pixel intensities) would be in many cases impossible to meet. In addition, a tolerance requirement can be relaxed, allowing us to define ''levels of quality'' of various oracles.

Two Examples: a Case Study and Global Illumination

This section attempts to solidify the proposed framework described in the previous section through the presentation of two examples. The first is a case-study that, though not a global illumination problem, is sufficiently simple to allow development of a number of details of the approach, and indicate how the framework leads to useful, practical solutions. In the second example, we discuss a more relevant global illumination problem, relating it to some of the oracles described in Section 3.2, albeit on a more general and abstract level than for the case study.

A Case Study: an Oracle for Scan Conversion

In a traditional scan-conversion system, one may use either Gouraud shading, in which a simple interpolation of colour computed at vertices is performed, or Phong shading, in which the normals are interpolated and the local illumination model is applied at every pixel. The difference in the renderings can be significant, mainly with respect to the highlights and the banding artifacts. Phong shading is obviously much more expensive computationally, so it is desirable to use it as rarely as possible. For the purpose of this discussion we will assume that the desired quality of rendering is the one generated purely by the application of Phong shading throughout (though it is questionable whether or not Phong shading always gives the best results). For a given scene, and within a certain tolerance (defined in terms of the mean μ and the variance σ 2 ), we can create the same image by selectively using Gouraud shading for certain cases. We represent this requirement in terms of the previously described framework as follows. Let O(Π, S, τ ) be an oracle with respect to a primitive Π (e.g., polygon, scan-line) a scene S and a tolerance τ , that answers the question: ''To generate an image of the desired quality, which shading rule should I use ?'' as follows:

O(Π, S, τ ) = ⎧ ⎪ ⎨ ⎪ ⎩ Phong Gouraud Neither
when quality of alternatives exceeds tolerance when satisfactory when only simple shading required (e.g., Π is in shadow)

The general benefits of the oracle framework has been discussed above. One of these is that of software engineering encapsulation that is provided for free. The oracle can be seen as an ''object'', that encapsulates the decision making logic for the shading rule selection. The specific oracle O would be used in the following way in a real rendering system: This oracle is now well defined, and we wish to see how to take advantage of scene structure to develop an approximation, as well as the oracle cost and error/quality evaluation metrics.

Relevant Aspects of Scene Structure

Due to the limited nature of the specific problem we are able to create an extensive list of structural aspects that affect the choice of shading rule. We will construct the list assuming a polygon primitive, since the scan-line case can be derived.

The purely geometric scene properties that are relevant are the following: polygon area, polygon shape, planarity, vertex normals and their variation, rate of change of the angle between the normal and the viewer, the distance of the polygon from the viewer, and the angle between the polygon normal and the viewing direction. Other aspects that are of importance are texture, surface properties and the local illumination model used, as well as light and shadow information. Each of these properties of the scene contributes to the decision of whether it is possible to use Gouraud shading, without significant degradation in image quality.

The properties above convey information that is relevant to the result of the applied shading rule. As an example, if the polygon is planar, and there is no variation in vertex normal, and in addition the angle between the viewer and the normal changes very little, Gouraud can be used without a problem. Obviously one can construct arbitrary combinations of cases that result in situations with varying degrees of certainty as to whether the shading rule can be substituted.

To allow a decision to be made, one can assign a weight to each of the properties, and construct a weighted sum that is then used as the decision variable (e.g., if the sum is larger than .5 one can use Gouraud). In addition one can rank each aspect so that the more important ones are those examined first (for example whether or not the polygon is in shadow), and apply increasingly complex heuristics to detect easy reject/accept cases.

The determination of the weights is initially a static, precomputation phase, followed by dynamic alteration discussed in Section 3.4. The static determination is based on a careful analysis of the effect each parameter or its variation has on the calculated (mean) intensity. Even for a simple case like this, one has to see how each of the properties listed above affects the final result, and express the effect each has by assigning appropriate weights.

Oracle Cost

The issue of oracle cost is of course of major importance. The case we have here is straightforward, since we have a yes/no decision to make. Suppose we have a sequence Opt 1 , Opt 2 , . . . of rendering options ordered by (increasing) costs. In our specific example, the rendering options are none, Gouraud, and Phong. We can also define a hierarchy of possible oracles as follows: We will also write Opt i j to denote that option j is being used at level i of this hierarchy. A number of cost constraints are evident:

Cost(Opt i j+1 ) > Cost(O i ) + Cost(Opt i j )
, where Cost(O i ) indicates the computational cost of the oracle O i itself, while Cost(Opt i j ) is the cost of using rendering option j at level i. For example, if i = 4 and j = 2, then the above constraint states that the use of Phong shading across a scan-line span must be more expensive than the cost of evaluating the oracle for this primitive together with the cost of employing Gouraud shading for the span. If it is more expensive to use the oracle to determine that one can shade scan-lines with Gouraud than it is to compute directly with Phong the advantage of the whole technique is lost.

In our case the cost of the computation for the oracle is fixed, and the cost of each option is also easily calculable since the cost of the application of illumination model and of the incremental operations is known, given a set number of pixels †.

Error/Quality Assessment and Adaptivity

As discussed in the previous section an important aspect of the oracle approximation process is determining the success of the selection strategy, which is the choice of shading rule in our case. A first order approach would be for the oracle to perform ''random tests'' in which when it selects Gouraud it also computes some pixels of Phong and computes the real mean error μ and variance σ 2 . A second order approach is to identify those parts of the shading rule equations that are most influential in the determination of the intensity, which can be determined by the weights used in the selection process, and compute an approximation of the error metrics, thus saving computation. When the oracle decides that it is performing poorly, it re-examines the weight assignments. By keeping track of selection history, it will be able to determine which weights are incorrect, and modify them so that they are closer to the correct decision.

An Example of Structural Diffuse Illumination

In this section we will present an augmented, progressive refinement radiosity-based solution to global illumination. Since this a much more involved and complicated problem than that of the shading rule, the discussion is necessarily less detailed and at a more abstract level. We formulate the problem in terms of two main oracles. The first is an approximation to the sample selection oracle O SaSel , treating patches as illumination samples. The approximation uses knowledge of the scene structure to determine patch size. The second is an approximation to oracle O IR , that, given a set of pixels associated to a patch or set of patches, selects a filter to be used.

Approximating the Sample Selection Oracle

The oracle implementation bases its choice of patches and patch size on a two-step selection process. The first step takes into account the effect of viewing parameters, and the second performs a preprocessing step to determine the influence of geometry and shadow boundary information.

As a first step we allow patch sizes to vary, depending on the size of the projection of each object onto the screen. In this fashion, objects that have a small screen projection are subdivided into a smaller number of patches. The area of each of these patches is calculated at subdivision time, since this is necessary in form-factor calculation. It must be noted that initial patch size, even for large objects, is taken to be significantly larger than in a normal radiosity-based approach.

In a second step, shadow boundary computation is performed in the spirit of [START_REF] Atherton | Polygon Shadow Generation[END_REF], from light cast from the initial emitters, onto the remaining objects in the scene. Object proximity is considered in these calculations, since diffuse emitters do not produce sharp shadows beyond a certain distance (or solid angle). These boundaries are then utilised to subdivide the patches that they intersect, so that a finer meshing exists along shadow boundaries. Other considerations, such as geometry information, and proximity, especially to light sources, can be used to further refine the meshing approach. All additional subdivision is subject to the projected screen size constraint: i.e., if the projected object is very small, subdivision will not be performed.

Approximating the Reconstruction Oracle

The reconstruction phase implements a simple form of the ''tagged sample'' concept. For patches that have not undergone additional subdivision, and thus do not have shadow boundaries crossing them, wide area filters are used to effect smooth blurring. An additional criterion in the kernel selection can depend on surface properties such as the existence of texture. Fast approximations based on table lookups or pyramidal techniques can be used [START_REF] Feibush | Synthetic Texturing Using Digital Filters[END_REF][START_REF] Williams | Pyramidal Parametrics[END_REF]. For more highly subdivided patches, blurring will not be attempted, allowing shadow boundaries, and intensity variations due to geometry to be more pronounced than in the standard solution.

Using the Oracles in the Enhanced Algorithm

The enhanced algorithm can now utilise these two oracles as black boxes. Instead of the initial static subdivision of the scene that typically occurs in traditional radiosity-based implementations, the first oracle is used, resulting in the generation of an ''intelligent'' selection of patches and patch sizes. This set of patches is subsequently used in the traditional progressive refinement solution. The number of patches will have been reduced compared to a straightforward patch subdivision (see Fig. 2). As a result the actual computation time for a converged solution will be significantly reduced, since the hemi-cube operation complexity is dependent on the number of patches in the environment.

Simple Patch-based subdivision

Adaptive subdivision light source

Fig. 2: Comparison of Adaptive and Simple Subdivision

At the final rendering stage, the filter selection oracle will be used instead of the usual bilinear interpolation [START_REF] Goral | Modelling The Interaction Of Light Between Diffuse Surfaces[END_REF]). This will lead to better defined boundaries for shadows and corners, at a fraction of the cost of higher subdivision that would be required to achieve the same result using the traditional approach.

Discussion and Future Directions

As we have seen, structure for the rendering process, both in the scene representation and in sampling/reconstruction, is an important factor that can significantly contribute to global illumination algorithms. The discussion of previous work indicated that, perhaps unknowingly, previous authors have capitalised on certain aspects of structure. In this paper we discussed how conscious and increased structure utilisation can benefit previous approaches.

We then proposed a new structure-directed framework based on the concept of oracles. We discussed initial approaches to approximating these ideal procedures. A discussion of their cost followed, together with simple suggestions on quality and error assessment, their adaptive nature and their definition in terms of tolerance factors.

We presented two examples: a detailed case study on how the framework can be of practical use, and an example for a radiosity-based progressive refinement approach that gives an indication of how this method relates to global illumination.

Further research is being pursued departing from existing global illumination techniques, that will take full advantage of the principles outlined in this paper. As such, algorithms developed will not be retrofitted to accommodate a structural approach but will be designed from the outset with it in mind.

To conclude, we are convinced that a structural approach to global illumination is a worthwhile area for future research. By carefully considering information given in scene descriptions, appropriately tuning data representation, and correctly structuring sampling and reconstruction methods in terms of abstractions such as oracles, it is quite possible that global illumination algorithms will see dramatic improvements both in terms of computational speed and storage requirement reduction.

O 1 (

 1 S, S, τ ) Choose shading rule for entire scene S O 2 (O, S, τ ) Choose shading rule for object O O 3 (P, S, τ ) Choose shading rule for polygon P O 4 (S p, S, τ ) Choose shading rule for span S p

† Depending on the algorithm used for visibility, the cost comparison between O 1 and O 2 may prove problematic, but we will assume for now that this is not the case.

Acknowledgements

The authors gratefully acknowledge the financial support of National Science and Engineering Research Council of Canada, the Information Technology Research Centre of Ontario, and the University of Toronto, for this research and for travel to the workshop. Thanks also to Pierre Poulin for reviewing an early version of this paper, Gavin Miller for fruitful discussions and also Greg Ward and the reviewers for their useful comments that significantly improved the presentation of this work.


George Drettakis

Eugene Fiume

Concrete Computation of Global Illumination Using Structured Sampling

A new methodology is presented for the computation of global illumination using structured sampling. Analytical/numerical solutions for illumination are developed for simple lighting configurations. These solutions are subsequently used to generate accurate reference images. The structured sampling solution for global illumination is then discussed, comprising sample placement for illumination calculation, reconstruction for light transfer and finally resampling and filtering of illumination samples for display. A first approximation to this technique is presented using a priori placement of samples, irregular polygon reflectors, grid resampling and a conical filter for display. The new algorithm is evaluated for image quality, and compared to the traditional radiosity-based approach. These first results show that the structured sampling solution yields significant computational savings while maintaining high image quality.

Goals of the Approach

The calculation of global illumination is inherently complex, even for environments that are simple in terms of geometry and reflectance properties. The physical laws governing illumination are described by integrals that can become extremely difficult to compute depending on geometrical configuration, light source type and surface properties. For reflection and refraction, the solution of a complex system of high-dimensional integral equations is required.

In computer graphics global illumination algorithms, a simulation of lighting phenomena is required so that visually satisfying realistic images can be synthesized. To achieve this goal, several simplifying assumptions have been made in previous work. The most common (e.g. [Zatz93,ChFe90]) is the subdivision of the environment into small diffuse-reflector pieces, in which constant luminosity (or radiosity) is assumed. This subdivision is done ''blindly'', or with adaptive methods that refine the level of subdivision based on the output of the already discretised environment [NiNa85]. The actual behaviour of the light-transfer functions, even for the simple special cases considered, is not studied, and not incorporated into the subdivision criteria. In addition the structure of the scene geometry, the viewing parameters, light source properties etc. are also ignored.

In most previous approaches, light is deposited onto samples of equal luminosity, in the form of luminosity values. To simulate the light transfer process, a subsequent reconstruction step is required to retrieve the light function from the segments of equal luminosity (elements). The most commonly used reconstruction is to shoot from an emitter (patch) using a straight average ([ChFe92,GrCT86]) of the samples on which illumination is placed (elements). Even though some work has been done to achieve intelligent reconstruction (e.g. [(null)]) again the adaptivity criteria are based on the discrete samples and not on light function behaviour or scene properties. In addition, most calculations are performed in object space without consideration of the viewing and imaging parameters.

In general, computing an exact solution for any environment of moderate complexity is not feasible. To be able to assess image quality of global illumination approximations, ''converged'' images are usually taken as the ''correct'' solution, and used as a quality measure. These images can sometimes contain significant errors, and therefore are not always reliable as a quality measure. To allow for more concrete measures of comparison, simpler environments are considered in which a combination of analytical solution and numerical quadrature can be used, to compute exactly correct luminance values, within reasonable time constraints. By carefully examining these simple cases, more concrete understanding of luminance function behaviours can be achieved. This understanding will be used in global illumination approximations as shall be shown later.

The ideas behind structured, or structure-directed, sampling were presented by the authors in [DrFi91]. An implementation of parts of the process will be presented here. In essence, the solution utilises the properties of illumination functions to guide sampling for display and light transfer. The experiments show that the new solution results in high-quality images at a lower cost than the corresponding radiosity-based approaches. The simple environments used allow careful comparisons with the exact solution, giving significant insight into the sampling rates used in the admittedly complex calculations of the radiosity-based approaches. A test containing a moderately complex environment is presented, indicating that the algorithm presented can be applied to real environments with significant benefit.

Analysis of Simple Diffuse Environments

To allow the computation of exact images for simple configurations it is necessary to formulate the equations for direct illumination and ''one-bounce'' reflection.

Direct Illumination

Direct or primary illumination is simpler to study since it involves only the calculation of the luminance due to light originating from the light source, reflecting off a visible surface and finally reaching to the eye. The luminance l′(r 1 ) in general direction r 1 is the power leaving a surface per area, per solid angle. All subsequent equations are given in terms of luminance.

Figure 1

For the configuration shown in Figure 1, where light source LS has luminance l LS (r 0 ), and the surface S has reflectivity ρ S ′′(r 0 ,r 1 ), the luminance in direction r eye , from the surface differential area dA, due to the light source LS, is given:

l A ′(r eye ) = LS ∫ l LS ′(r 0 )ρ A ′′(r 0 ,r 1 ) cosθ A in dω (1)
where dω is as shown in Figure 1. This is a general equation that makes no limiting assumptions about the nature of the reflectance (encapsulated in ρ A ′′(r 0, r 1 )) or the light source behaviour (described by l LS ′(r 0 )). For a perfectly diffuse light source LS and a perfectly diffuse reflector S, source luminance and surface reflectivity become simple constants l LS and ρ S , and if R 0 is the distance between dA and dσ, Eq. (1) simplifies to:

l A ′(r eye ) = l LS π ρ A LS ∫ cosθ A in dω = l LS ρ A LS ∫ π R 0 2 cosθ A in cosθ A out dσ = l LS ρ A F dA -LS (2)
The quantity F dA -LS is termed the form-factor between the differential surface element dA and the source LS.

Solving for Simple Light Source Geometries

In the general case, Eq. ( 2) is a complicated function that does not usually have an closed form solution. This complexity is due to the inherent difficulty of finding the domain of integration, and applying a suitable transformation to allow computation of the cosines. For certain specific geometries and types of light sources, analytical solutions to F dA -LS exist (see [Moon36,SiHo72,Dret91]).

Figure 2

One such example is an arbitrary planar polygonal light source with n sides. For the polygon shown in Figure 2, the analytical solution for F dA -LS is:

F dA-LS = 2 1 i =0 Σ n γ i cosδ i (3)
The angle γ i is defined by the lines connecting the point P and the vertices v i , v i +1 of the polygon, and δ i is the angle between the normal n to the plane defined by these lines and the normal at P, at the centre of dA. Because the derivation is based on Stokes theorem, the only limitation is that the polygonal light sources have no holes.

Mathematical Formulation of One-Bounce Reflection

The configuration now considered is that of a single, constant luminosity, diffuse light source LS, placed on a plane parallel and directly opposing receiver A, and a parallel receiver B that receives no light directly from LS (see again Figure 1). From the previous section, and ignoring the interaction from B to A, the luminance on visible points on B will be determined.

One way of viewing this calculation for each visible point on B is as if the receiver A is a light source. In this case the value of the luminance function l A (r 1 ) varies over the surface A, in the manner described by Eq. ( 2). The luminance l B (r ′ eye ) at point M on surface B is given by the following expression (note that R 1 , the distance between dA and M, is a function of the position of dA):

l B (r ′ eye ) = ρ B A ∫ l A (r 1 ) π R 1 2 cosθ B in cosθ A out dA (4)
Using Eq. ( 2), Eq. ( 4) becomes:

l B (r ′ eye ) = l S ρ B ρ A π 2 1 A ∫ F dA-LS R 1 2 cosθ B in cosθ A out dA
The above equation entails a single integration over the surface of receiver A, assuming that there is an analytical expression for the term F dA -LS . To give an indication of the complexity involved for such a computation, Eq. ( 5) is the final expression for a rectangular light source. Briefly, n A ,b B ,n s are the normals at A, B and the light source, r A -B ,r B -A are unit vectors between the visible point on B and the point (x,y) on A, and s i is a vector from vertex i of the source to (x,y). For details and the derivation, see [Dret91]. The luminance at a visible point on B is given as follows:

l B (r ′ eye ) = l S π 2 ρ B ρ A y =0 ∫ b x =0 ∫ a (x B -x) 2 + (y B -y) 2 + (z B ) 2 (r B -A . n B ) (r A -B . n A ) i =0 Σ 3 cos -1 ( s i . s i +1 ) (s i × s i +1 )
. n S dxdy (5)

Accurate Numerical Solution

To allow the use of a numerical solution for the computation, the integral in Eq. ( 5) is given to an adaptive quadrature routine, written in FORTRAN, taken from the netlib library. Even though it is a complicated function, it is tractable for medium resolution images †.

Test scenes have the configuration of Figure 1. The renderer applies the direct illumination equations (Eq. ( 2) and ( 3)) for the visible pixels of A, resulting in exact analytical values. For the tertiary reflector B the scan-converter first finds the appropriate light-source and the appropriate secondary reflector. All values are transformed into the suitable space so that Eq. ( 5) can be applied, and the numerical integrator (a Gaussian quadrature) is invoked to any desired accuracy. This calculation is performed for each visible pixel on B.

An example of an image computed with this method is shown in Image 1, which corresponds to the environment presented in Figure 1. From now on this will be referred to the ''simple'' environment.

Structured Sampling: a First Approach

As discussed in detail in [DrFi91] the basis of structured sampling is the recognition of the properties (structure) of light in a scene and their subsequent utilisation in computing illumination.

Fundamental Concepts

The basic tenet of the approach is that in diffuse environments, luminance functions across surfaces are very smooth (with the exception of shadow boundaries), and therefore the number of samples required to reconstruct the luminance is small. Taking this assumption as a starting point, there are three main actions that need to be performed to calculate illumination in a scene and generate a realistic synthesized image.

Selection and tagging of illumination samples. Illumination samples are associated with the original given geometry. Three things are worth noting here. First, scene structure, such as geometry variation, shadow boundaries and viewing parameters can be used to determine the density and positioning of these samples. Second, this sampling can change adaptively as the requirements of illumination become more apparent. Third, the samples are directly related to the resampling for display described below. This ties in with the concept of ''tagged samples'' introduced in the earlier paper [DrFi91]. A tagged sample contains information indicating whether it is in shadow, or it is in an area with smoothly varying illumination, or it was placed due to viewing parameter constraints etc.

Reconstruction for light-transfer. Some of the samples that have been previously selected are used to propagate light. A shooting paradigm is used, similar to that of the progressive refinement radiosity-based technique [ChSD93]. Depending on the requirements and variation of the illumination functions, varying degrees and quality of interpolation can be used to achieve the desired result. If for example a collection of samples have extremely smooth variation, and the geometry is suitable, simple averaging may be sufficient. For more complex variation, linear or higher order approximations may be required.

Resampling and filtering for display. The samples that have been selected contain values, exact or approximate, of the luminance at a certain point in space. The original geometric primitives must then be rendered using this information. In the radiosity-based algorithms the radiosity is computed at vertices [GrCT86] or at centres [Zatz93] of polygons and therefore there is a direct relationship between illumination samples and geometry. For structured sampling, the samples are chosen to match the variation of illumination, they are irregular and sparse and do not correspond directly to geometry. To render the primitives, a resampling is required, mapping the illumination back to the original geometric primitives. This method is especially beneficial when graphics hardware is used and therefore displaying numerous primitives is cheap compared to the illumination calculations.

The essence of the approach is to direct sampling and reconstruction based on the study and analysis of illumination function behaviour. Using isolux contours to guide sample placement and light transfer reconstruction, sampling rates are significantly reduced. In addition, using resampling and filtering for display enhances image quality without adding light-transfer calculations. Further work on selecting appropriate filters will also be guided by the study of light function variation.

A First Approach to Structured Sampling

In what follows a first structured sampling solution is presented. This is not yet a complete new algorithm: the main purpose of this presentation is to discuss the encouraging first results of experiments. The use of controlled and simple environments facilitates careful evaluation of the proposed solutions.

Sample selection. In this paper samples are placed in a preprocessing step by the user, using an interactive sample editor built into a global illumination testbed. Even though automatic placement has not yet been achieved, the guidelines used to interactively place samples will be presented, since they will become the basis for such an algorithm.

The illumination samples associated with a surface can be of two kinds. Display samples are used only for display, and are collectors of illumination. Light transfer samples also serve as collectors, but are grouped with several other samples to form secondary emitters. The purpose of the grouping is to form surfaces that correspond to areas of equal or almost equal luminosity. The placement of these samples is based on the properties of the light sources and shadow regions.

To assist in this selection lower resolution colour images can be used to identify the areas with almost equal illumination. Consider the environment shown in Image 1, that corresponds to Figure 1. This image has been computed using the analytical/numerical technique previously described. Figures 3(a Samples are now placed to correspond with the curvature of these contours. Depending on the requirements for further propagation, some of these samples are connected together to form (usually coarse) approximations of the ''isolux'' areas. Display samples can be selected in a ''view-dependent'' manner, so that the regions that are larger in the final image have higher sample density. The samples selected and the secondary emitter polygons created for the scene Shadow boundaries are treated in a similar manner. Samples are placed across the umbra and penumbra regions with varying density. The emitters need not contain many samples, especially in the case of the shadowed regions, since these do not contribute much to scene illumination. Figure 5 shows structured samples corresponding to Image 4.

Even though this selection process assumes knowledge that does not exist prior to a global illumination solution, it offers significant insight into how automatic sample placement algorithms will be created. By carefully studying common light-source types and configuration, isolux contours can be computed exactly or approximately. Shadow boundary calculations, at varying levels of granularity, can also be used. As mentioned previously, samples will maintain information about the reason for their selection, becoming intelligent or ''tagged'' samples. This information can be used both for light-transfer as well as resampling and filtering.

Light-transfer reconstruction. As mentioned before, some samples have been collected into secondary emitter polygons representing ''isolux'' regions (these are the polygons shown in Figure 4(a) and Figure 5). For direct illumination, light is shot from the light sources to the samples, and exact luminance values are stored using the analytic formulas (Eq. ( 2) and ( 3 samples of the luminance function defined over a surface are stored at points carefully selected to correspond well to the illumination variation. For secondary light, the values at the vertices of each polygon are averaged, and the light is shot from the polygon corresponding to the region to the display samples, again using Eqs. ( 2) and (3). The shape of these polygons is based on the isolux contours. As a result this approximation is much more accurate than the regular patch subdivision, since the constant luminosity polygons correspond closely to regions that have almost constant luminosity as a result of the light function properties.

For more complex environments, shooting will continue until unshot light power has dropped below a preset threshold. At each step, the polygon with the highest power is selected. In future work, occlusion will be computed during sample placement (since shadowed regioned will have been identified), and samples will carry a tag indicating their occluded or visible status. For now, a simple ray-casting scheme is used, for demonstration purposes. When a secondary emitter polygon with vertices v 0, . . . ,v n shoots light, a ray is cast from each v i to every display sample in the environment, and the result at each display sample is weighted based on the ray intersection count.

Resampling and filtering for display. To incorporate the information contained in the display and light transfer samples for the final image generation, a grid resampling technique is used. A grid is placed over the surface to be rendered that contains the samples, the sparse irregular samples are then filtered to the grid vertices, and the polygons subsequently rendered. An example grid is shown in Figure 4(b), used for the samples of Figure 4(a).

To assign a luminance value to each vertex on the grid, the sparse irregular samples within a certain radius r of each grid point are filtered using a simple conical filter. Assume that the grid point is at (u,v), and there are n samples S i ,i=1, . . . n at corresponding positions (u i ,v i ), and

d i = √ (u -u i) 2 +(v-v i ) 2 <
r is the distance from the grid point to each sample S i . If the luminance at each sample S i is L i then the luminance value, L uv , at grid point (u,v) is given as follows:

L uv = i =0 Σ n d i i =0 Σ n (1- r d i )L i
It is evident that when ''tagged samples'' are used, different weights or kernels can be used, depending on whether the samples represent discontinuities such as shadows, or areas in which smoothing is appropriate. For example if a set of samples are tagged as shadow boundaries, nonlinear or adaptive filters can be used to produce the desired effect. The current conical filter is a starting point, simply showing the feasibility of the resampling approach. Better filters, with radial characteristics are being designed that are better adapted to the properties of isolux contours. In particular, the shadow boundaries resulting from the conical filter are not of very high quality, since the filtering results in excessive blurring.

The algorithm just described is not a full solution. However, the implementation and experiments presented in the following section show very encouraging first results that confirm the choices made.

Experiments and Comparative Analysis

The goal of the experiments is to determine the quality of the new algorithm and show that the sampling rates required are significantly reduced. In addition a comparison with traditional radiosity-based solutions is performed. The first experiments are of the environment previously described in Section 2.3. The parameters of the scene are listed in Table 1. In Image 1, the exact solution was shown, calculated with the analytical/numerical solution. The structured solution was computed using the structured samples shown in Figure 4(a), based on the isolux contouring in Figure 3(a) and (b). The structured solution image is shown in Image 2. Image 3 shows the image computed using the ray-traced formfactor solution (Scene 1 in Table 2). Results from four runs of the ray-traced form-factor solution (Scenes 1-4) are presented in which different parameters are varied.

Image quality can be measured in a number of ways, and the error metric can be weighted to be sensitive to different types of errors. The metric used here is an pixel-by-pixel absolute difference of the the approximate image from the reference image. Only pixels corresponding to visible points are taken into consideration. The percentage of pixels with an absolute difference greater than a certain tolerance τ is taken as the error of the approximation image. In Table 2, the results of the experiments in quality and speed are listed, in terms of the relative sampling rates. These results are indicators of general behaviour of diffuse functions and lighting situations. The controlled environment, and the benefit of an analytical solution allows trustworthy and concrete conclusions to be reached. The structured solution results in three main benefits:

Reduction in the number of display samples. To achieve less than 2% error on surface A, (τ = 10%), 48 structured samples are required for the structured solution, while a total of 100 element vertices are needed for the radiosity-based approach (Scene 1). If the ray-traced solution uses only 64 elements, the error is somewhat larger (2.54% in Scene 2), than the corresponding structured approach result. This reduction in required number of samples is due to the fact that display samples are placed based on variation of illumination, following the isolux contours.

Significant speedup. As a result of the reduction in the required number of samples, the structured solution outperforms the radiosity-based approach in terms of speed. The secondary reflection is 5-6 faster than the corresponding radiosity-based solutions, while the total varies Table 3 shows that the ray-traced form-factor solution requiring the same computation time results in approximately double error rate. The illumination levels in Image 5 for the structured solution are much closer to those in the converged solution (Image 4), than the radiosity-based solution (Image 6). This is particularly evident on the ceiling. The ray-traced form factor solution that achieves the same quality requires almost quadruple computation time, and significantly more sample points on walls and floor. In addition, despite the lower number of samples, element gridding can be seen in the radiosity-based solution, while the filtering in the structured solution results in a much smoother overall image.

These results must be taken only as a first indication, since a full structured solution will not require ray-casting for occlusion, and will incorporate different filters for display. When completed, much improved results are expected from the structured approach.

Summary, Conclusions and Future Prospects.

In this paper a first concrete approach to structured sampling is presented. The use of simple environments in which exact solutions can be used for evaluation purposes is advocated. Such cases are presented and exact solutions derived, using analytical solutions for light sources and numerical quadrature for reflection. The structured sampling concepts are presented and a first partial implementation of the methods proposed is described. Experiments involving simple environments that allow careful evaluation, and moderately complex scenes that indicate feasibility are presented, with images and quality/computation time statistics.

The first results presented here are very encouraging. Computation time and sample requirements are significantly reduced. Careful evaluation of simple environments show the importance of the following new techniques: separation of samples into those used for display and those used for light-transfer, use of better reconstruction for light transfer, in this case by using isolux region and shadow boundary information and resampling and filtering for display that allows some of the cost of generating high-quality images to be performed by imageprocessing techniques. In addition, the moderate complexity environments, even without a full occlusion solution, show encouraging sampling, quality and speed benefits.

The possibilities for future work are numerous. For sample placement, shadow boundary techniques and corresponding sample ''tagging'' as well as automatic calculation of ''isolux'' contours are currently being investigated. The use of view-specific information (for display samples), and adaptive techniques for secondary lighting will also be investigated. For light-transfer reconstruction, further research will include evaluation of the quality required for reconstruction. For resampling and filtering for display the emphasis will be on design and evaluation of appropriate filters and sampling rates, as well as use of other filter types when displaying tagged samples. Occlusion is an important issue and involves all three stages. Adaptive techniques must be used, and the use of different reconstruction in light-transfer may alleviate part of the problem. Finally the use of special filters for display to enhance desired effects can be used to in the place of accurate occlusion calculation.

  ) and 3(b) show the variation of illumination with 8-bit colour resolution instead of 24-bit, across surfaces A and B. In each of these Figures the viewpoint is exactly above the centre of each surface. The regions of almost equal illumination (''isolux'' from now on) can easily be seen.

  shown in Image 1, are shown in Fig 4(a). These are coarse approximations of the contours in Figures 3(a) and 3(b).

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	.	.	.	.	. dω . . . . .	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	r ′ eye
																									a

  )). Thus exact

	Light Source	Surface B	Light Source	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Surface B
			Surface A	.	.	.	.	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	.	.
	Surface A		. . . . . . . . . . . .	Resampling grid lines
									Kernel width over grid point

Image 1: Simple Environment Computed with Analytical/Numerical Image 2: Structured Solution Image 3: Radiosity-based Solution

		Simple Case Scene Parameters
	Resolution	200x200 Light Source Area	9
	Aspect Ratio	2.2	Light Source Power (r=g=b) 12
	Offset of LS	1.2	Area of A, B	25

Table 1 : Simple Case Scene Parameters 4.1. Simple Case Experiments

 1

Table 2 : Results for Rectangular Light Source

 2

	Structured Sampling	Ray-Traced Form-Factor Solution
				Scene 1 Scene 2 Scene 3 Scene 4
	Polys (A)	4	# of Patches (A)	4	4	4	4
	Samples on A	48	Total Samps. (A)	100	64	64	64
	Samples (B)	10	# Elem. Vert. (B)	36	36	16	9
			Samps. on Source	400	400	400	400
			Samps./Patch (A)	16	16	16	16
	% > 10% err (B)	0.02		0.00	0.02	0.92	2.92
	% > 10% err (A)	1.52		0.53	2.54	2.54	2.54
	Time (LS → A) Time (A → B)	0.02 0.01		0.97 0.06	0.69 0.05	0.69 0.04	0.69 0.03
	Time Total (sec)	0.03		1.03	0.74	0.88	0.68

† An average 200x200 resolution image takes 10 minutes to compute. All computation times reported are on an SGI Iris 4D/35 workstation.

Acknowledgements

The authors gratefully acknowledge the financial support of National Science and Engineering Research Council of Canada, the Information Technology Research Centre of Ontario, and the University of Toronto, for this research and for travel to the workshop. Thanks also to Pierre Poulin for fruitful discussions, Tom Milligan for shooting the final pictures and Rob Lansdale for providing the software base, on which most of the global illumination testbed was built.

from 24-34 times, although this is dependent on the sampling rate of the light source †.

Reduction in samples required for light transfer. The use of isolux region approximations as constant luminosity polygons, allows equivalent quality light-transfer to be performed at a lower cost. The total required number of samples on surface B for less than 1% error, is 10 for the structured solution. Keeping all other parameters constant, in Scene 3, the radiosity-based solution requires 16 element vertices (samples) on B to achieve the same quality. If this is reduced to 9 element vertices the error reaches 2.2% (Scene 4).

Moderate-Complexity Scenes

As discussed above, simple scenes give valuable insight due to their simplicity and the existence of exact solutions. However, it is also beneficial to examine moderate complexity scenes to evaluate possible performance gains from new solutions. The advantage of having the exact solution is lost yielding results that are less concrete, since numerous other parameters have been introduced. They do however give a sense of feasibility of the structured method. 3 as ''Converged'', with the ray-traced form-factor solution), is shown in Image 4. This image is used for evaluation purposes. A relatively good quality structured solution is shown in Image 5, while the structured samples are shown in Figure 5. A image that has similar computational requirements using the ray-traced form-factors is shown in Image 6. The results for this run are listed in Table 3 in the ''Same speed'' column. A second ray-traced form-factor solution is run that results in equivalent image quality, listed in the ''Same quality'' column. The error tolerance τ for all tests was set to 15%.

Structured