Dimitri Plemenos
XLIM Laboratory, University of Limoges,
83, rue d’Isle,F-87000 Limoges, France.
http://msi.unilim.fr/~plemenos
- Abstract
- 1. Introduction
- 2. The hemisphere subdivision based monte carlo radiosity
- 2.1. General principle of the hemisphere subdivision techniques
- 2.2 Estimating local densities
- 2.3 Estimating a global density
- 2.4 Main drawbacks of the used criteria
- 3. A new heuristic sampling technique based on estimation of visible surfaces in a region
- 3.1 Subdivision depending on the neighbouring regions
- 3.1.1 Preprocessing
- 3.1.2 Radiosity computation
- 3.2 Independent processing of regions
- 3.2.1 Preprocessing
- 3.2.2 Radiosity computation
- 4. Discussion
- Conclusion and future work
- Acknowledgements
- References
In this paper, an overview of techniques to estimate the visual complexity of the different parts of a scene from a given point of view, in order to be used in radiosity computation, are presented. This information is then used to improve the Monte Carlo based radiosity calculation by distributing the rays leaving a patch according to the estimated visual complexity of each part of the scene. All the proposed techniques to estimate the visual complexity are based on artificial intelligence methods, especially heuristic search, and divide the scene in regions via a hemisphere associated to each patch and divided in spherical triangles. The visual complexity in a region is considered constant.
Key words:Monte Carlo radiosity, heuristic search, hemisphere subdivision, visual complexity.
The radiosity computation techniques based on Monte Carlo ray shooting [3, 4] are very interesting techniques because they do not need explicit calculation of form factors. However, these techniques have a well known drawback: as the Monte Carlo sampling of the scene is a quasi-regular sampling, all the regions of the scene receive approximately the same number of rays. Thus, very complex regions receive the same number of rays as very simple regions of the scene. If this number of rays is sufficient, and even useless, for simple regions, it can be insufficient for some complex regions of the scene. So, if Monte Carlo techniques give satisfactory results in many cases, they can introduce noise for scenes containing complex regions because of possible insufficient sampling.
The purpose of hemisphere subdivision techniques [2, 5, 6, 7, 8] is to improve traditional Monte Carlo techniques by taking into account the complexity of the different regions of the scene from a given point of view and by making a better distribution of the rays among these regions. Two main problems have to be resolved: estimate the complexity of a region of a scene and distribute the rays in the scene according to the complexity of each region.
Several papers have been published in the area of accurate estimation of the visual complexity of a scene or of a scene region. Some of the proposed techniques use scene geometry and topology-based criteria to estimate the visual complexity [1, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] while other techniques try to apply Information Theory-based measures [13, 17, 21, 22, 23, 24]. In this paper we present an overview of hemisphere subdivision techniques for improving Monte Carlo radiosity, based on scene visual complexity. Moreover, we propose a more accurate hemisphere subdivision technique, with better estimation of the visual complexity of a region.
The paper is organised as follows:
In section 2, the principle of the hemisphere subdivision technique is presented, together with the main used sampling criteria for dividing the scene into regions, according to the estimated visual complexity of a region. In section 3, the main drawbacks of the used sampling criteria are discussed and analysed. In section 4, a new sampling criterion is proposed for dividing the scene, together with a method to distribute the rays in the scene. A discussion on improvements obtained with various sampling criteria is presented in section 5, while in section 6 we conclude this paper and give some ideas for future work.
Techniques for improving the precision of Monte Carlo radiosity have been developed since 1996 [2, 5, 6, 7, 8]. These techniques are based upon hemisphere subdivision and their main purpose is to estimate the visual complexity of a scene from a patch and to use this complexity in order to :
• Get more precision in radiosity computation with Monte Carlo based algorithms, by shooting more rays in directions where the scene is more complex.
• Get a useful image more quickly, permitting to understand the scene and to modify it if visual impression is not satisfactory.
The techniques presented by the authors in previous papers are all based on subdivision of a virtual hemisphere, associated to each patch of the scene. The hemisphere subdivision can be regular or adaptive.
At the beginning, the hemisphere is divided into 4 equal-sized spherical triangles (figure 1). Each spherical triangle is then subdivided independently of the others, according to the retained criterion.
Fig. 1. Initial subdivision of a hemisphere
In regular subdivision, each spherical triangle of the hemisphere, at any subdivision level, is subdivided while a general subdivision criterion is verified (figure 2).
Fig. 2. Regular subdivision of a spherical triangle
In adaptive subdivision, only the spherical triangles verifying the subdivision criterion are subdivided (figure 3).
Fig. 3. Adaptive subdivision of a spherical triangle
The sampling techniques based on hemisphere subdivision are using criteria for estimating the visual complexity of a scene from a given point of view. A scene can be considered visually complex if many different elements of the scene are visible from a patch. All the problem is to estimate, as accurately and quickly as possible, the visual complexity of a scene from a patch. All the techniques presented in this section are based on the notion of density of a scene in a given direction or in a given region.
The first estimation of the visual complexity of a scene from a patch has used estimation of local densities and computation of an average complexity estimation from these local densities [5, 6].
According to this method, a ray is shot from the centre of the patch to each vertex of a spherical triangle (figure 4). The local density associated to a ray is the number of patches intersected by the ray. The density of the spherical triangle is the average value of the three local densities.
Fig. 4. Local densities
The density of a spherical triangle can be considered as an estimation of the visual complexity of a scene because the probability to have more surfaces in a spherical triangle increases with the number of patches intersected by the rays sent to the vertices of the triangle. So, it is reasonable to estimate that the number of visible surfaces increases with the total number of surfaces.
This estimated density of the spherical triangle is used in the following manner for computing radiosity, depending on the use of regular or adaptive subdivision.
Regular subdivision of the spherical triangles of the hemisphere is performed up to a subdivision level defined at the beginning of the process.
At the end of the subdivision phase, a number of rays, transporting the energy of the patch, are shot in the hemisphere. The number of rays shot in a spherical triangle is proportional to its density. The amount of energy transported by a ray is proportional to the area of the corresponding spherical triangle.
Adaptive subdivision of the spherical triangles of the hemisphere is performed up to a subdivision level defined at the beginning of the process, only for triangles with densities greater than a threshold value.
The energy diffusion phase for the current patch is performed at the end of the subdivision phase by shooting a number of rays in the hemisphere. The number of rays shot in a spherical triangle is the same for all spherical triangles. The amount of energy transported by a ray is proportional to the area of the corresponding spherical triangle.
The main drawback of this sampling technique is that estimation of visual complexity is very rough. So, in some cases (case of a wall which hides all the objects behind it), the expected improvement of Monte Carlo radiosity is avoided. In figure 5, the density of the direction defined by the ray shot from the current patch is 4 but the energy of the patch will never reach the objects behind the wall.
Fig. 5. The wall hides other objects of the scene
However, the implementation of this technique gives satisfactory results, improving the accuracy of radiosity computation by Monte Carlo techniques (Figure 6).
Fig. 6. The hemisphere subdivision technique using local density estimation (bottom image) improves Monte Carlo radiosity computation (top image).(Images by Vincent Jolivet)
2.3 Estimating a global density
We have seen that local density calculation is not accurate enough and can fail in some cases. The method of estimation of local densities is based on the hypothesis that the average density of a spherical triangle is the average value of the local densities associated with the vertices of the spherical triangle. However, this hypothesis is very rough and could fail in some cases.
In order to make the estimation of the complexity of a region of the scene more precise, a new definition of the density of a region has been introduced [7, 8]. The density of a region viewed from a patch is the number of objects (patches) contained in the region. As regions are delimited by spherical triangles in our case, the density of a region viewed from a patch is the number of objects (patches) contained in the triangular pyramid defined by the centre of the patch and the three vertices of the spherical triangle (figure 7).
This global density of a triangular pyramid is used in the following manner for computing radiosity, depending on the use of regular or adaptive subdivision.
Regular subdivision of the spherical triangles of the hemisphere corresponding to each patch is performed up to a subdivision level defined at the beginning of the process.
At the end of the subdivision phase, a number of rays, transporting the energy of the patch, are shot in the hemisphere. The number of rays shot in a region delimited by a spherical triangle is proportional to its global density. The amount of energy transported by a ray is proportional to the area of the corresponding spherical triangle.
Fig. 7. Global density of a pyramidal region
Adaptive subdivision of the spherical triangles of the hemisphere corresponding to each patch is performed up to a subdivision level defined at the beginning of the process, only for triangles corresponding to pyramids with global densities greater than a threshold value.
The energy diffusion phase for the current patch is performed at the end of the subdivision phase by shooting a number of rays in the hemisphere. The number of rays shot in a spherical triangle is the same for all spherical triangles. The amount of energy transported by a ray is proportional to the area of the corresponding spherical triangle.
Estimation of a global density for a region from a patch, based on the number of objects contained in the region, is more accurate than estimation of local densities and approximation of a global density by computing the average value of local densities. However, the main drawback of these techniques to estimate the visual complexity of a region is that the complexity estimated by both techniques is not a visual one. Indeed, computing the number of objects lying in a direction or in a region only permits to estimate the real complexity of a region and this real complexity is not the visual complexity of the region. In many cases, the real complexity of a region of the scene can be used to estimate its visual complexity but this estimation can fail, especially in cases where a big object hides several objects lying behind it. Thus, in the case where a wall hides several parts of the scene, both techniques used to estimate the visual complexity (density) of a region, fail.
In order to compute a more accurate visual complexity, an improvement was introduced in the technique based on the number of objects (patches) contained in a region. This improvement takes into account the number of patches contained in the pyramid and receiving energy from the current patch.
Let us consider figure 8, where 6 objects are contained in the pyramid associated with the current patch. Among all these objects, only one, the object no 1, receives energy from the rays shot from the current patch. This fact permits to conclude that it is useless to shoot a great number of rays in the pyramid since only a small percentage of the objects contained in the pyramid is concerned by these rays.
Fig. 8. The number of patches receiving energy from the emitting patch permits to dynamically improve the rays distribution.
So, at each step of energy distribution, the ratio: number of objects in the pyramid which received energy during the last step / number of rays sent in the pyramid is computed and serves to improve the rays distribution in the next step. The number of rays sent in the pyramid is dynamically updated at each energy distribution step, this number increasing or decreasing with the value of the above ratio.
Fig. 9. Detail of a reference scene obtained with classical Monte Carlo radiosity calculation (top image) and global density-based radiosity calculation (bottom image) at the end of the first step. (Images by Vincent Jolivet)
This improvement greatly increases the efficiency of the criterion estimating the visual complexity of the scene. Figure 9 shows results of radiosity calculation using this technique. However some drawbacks of the estimation technique remain:
1. Even if the visual complexity is progressively approximated, the hemisphere subdivision is based only on real complexity criteria because the above improvement is not applicable during the subdivision step.
2. The objects considered by the used criteria to estimate the visual complexity of a scene are patches. Unfortunately, the estimated number of visible patches cannot give a precise idea of the visual complexity of a region of the scene. A region containing a single flat surface divided into n visible patches, is generally much less complex than a region containing several small surfaces, even if the number of visible patches is less than n. In figure 10, two regions of a scene are considered from the current patch, that is, the patch which has to distribute its energy in the scene. In both regions, the number of visible patches is 5 but it is easy to see that the visual complexity of the second region is greater than the visual complexity of the first one. A small number of rays is sufficient to distribute the corresponding part of energy of the current patch in the first region while a more important number of rays is necessary to accurately distribute energy in the second region.
So, it becomes clear that the more accurate criterion of visible complexity of a region is the number of surfaces seen in the region. The question is: how to approximate the number of visible surfaces in a scene without increasing the complexity of radiosity computation ?
Fig. 10. the number of visible patches is not always a good visual complexity criterion
In the following section, a new technique to compute the visual complexity of a region of a scene is presented. This technique avoids the two main drawbacks of the criteria currently used by the hemisphere subdivision methods to compute radiosity.
We have seen that the criteria used for sampling the scene as viewed from a patch are not always very precise and can fail in some cases. Even with the improvement described in section 3, the solution is not fully satisfactory because the improvement occurs after the scene has been sampled and because the criterion used in this improvement - estimation of the number of visible patches - is not precise enough. In order to avoid these drawbacks, a new scene and rays sampling technique will be proposed in this section, based on adaptive refinement of a region.
Adaptive refinement technique can be used to improve the radiosity computation process for Monte Carlo based methods. The purpose of this technique is to introduce a new scene’s complexity criterion for the hemisphere subdivision method, the number of visible surfaces. The expected improvement is an enhanced processing of complex parts of the scene. Two variants of this technique can be imagined. In the first one, subdivision of a region depends on the state of neighbouring regions while in the second variant regions are processed independently of each othe
This technique uses a region subdivision criterion based on the state of neighbouring regions. The technique will be first explained in 2 dimensions, in order to be easier to understand. We will see that transposition to 3 dimensions is not always easy.
A hemisphere is associated to each patch of the scene. The technique works in two phases, preprocessing and radiosity computation.
1. The hemisphere is regularly subdivided into a fixed number of zones (figure 11).
Fig. 11. Selective scene refinement for a hemisphere
2. At each step, a ray is sent to the centre of each zone from the centre of each patch (or from a randomly chosen point of the patch).
If the visible surface (not the visible patch) for the current zone is different from the visible surface for a neighbour zone, the current zone is subdivided and the same process is applied to each resulting zone.
3. The whole process stops when a given subdivision level is reached.
At each step, the same number of additional rays is shot against each zone. The power transported by each ray is proportional to the area of each zone.
The radiosity computation process can be stopped at any step.
This variant is difficult to transpose in 3 dimensions, as the zones are now spherical triangles and it is difficult to find the neighbours of a spherical triangle (figure 12). Implementation of this variant supposes a heavy organisation of spherical triangles in order to find, as easily as possible, the neighbours of a given spherical triangle.
Fig. 12. Which are the neighbours of the triangle IGJ ?
3.2 Independent processing of regions
A hemisphere is associated to each patch of the scene. The variant works also in two phases, preprocessing and radiosity computation. Only the preprocessing phase is different from the one of the first variant.
1. The hemisphere is regularly subdivided into a fixed number of zones (figure 13).
2. At each step, a ray is sent to each extremity of each zone from the centre of each patch (or from a randomly chosen point of the patch).
If the visible surface (not the visible patch) for the current zone is not the same for all the extremities of the zone, the zone is subdivided and the same process is applied to each resulting zone.
Fig. 13. a new ray is to be traced
3. The whole process stops when a given subdivision level is reached.
This variant is easy to transpose in 3 dimensions. Now, a zone is a spherical triangle and a ray is shot against each vertex of the triangle. The spherical triangle is subdivided into 4 new spherical triangles (see figure 14).
At the end of the subdivision process, the same number of rays is shot to each spherical triangle. The energy transported by each ray is proportional to the area of the triangle.
The main advantage of the techniques proposed in this section is that subdivision is performed whenever changes, concerning the visible surface, are observed between two parts of a region. The number of visible surfaces in a region, that is the number of changes of visible surface, is a good criterion of the visual complexity of a scene from a patch, because a region with many changes of visible surface must be processed more accurately than a region with few changes. The only drawback of these techniques is that the visible surface must be computed for each ray shot during the hemisphere subdivision (sampling) phase.
The results obtained with the techniques described in this paper are always interesting and improve Monte Carlo based radiosity with all scenes we have tested. A new, more accurate, sampling technique has been proposed which should improve results of Monte Carlo-based radiosity computation.
From a theoretical point of view, it is possible that the sampling techniques described in the previous sections fail, because of an insufficient number of rays to be sent. For example, if the number of rays to shoot in a scene composed of two regions is 1000, if the visual complexity of the first region is 10000 times greater than the visual complexity of the second one, all 1000 rays will be sent in the first region and no energy will be diffused in the second region (figure 15).
Fig. 15. If a region is much more complex than the other one, all available rays could be shot in the first region.
Some heuristic techniques, using criteria to estimate the visual complexity of a region of a scene, have been presented in this paper. The purpose of these techniques is to divide the scene seen from a patch in a number of regions of constant visual complexity and then to distribute rays leaving the patch according to the complexity of each region. These techniques give very interesting results and permit to greatly improve Monte Carlo based radiosity calculation.
The technique presented in section 4 is not yet implemented but we do think that it is the best one because the used visual complexity criterion is the more accurate. This technique, which could be combined with the improvement permitting to dynamically estimate the visual complexity, presented in section 3, should give the more satisfactory results.
The author would like to thank Vincent Jolivet for providing discussion and images.
[1] Kamada T., Kawai S., “A simple Method for Computing General Position in Displaying Three-Dimensional Objects”. Computer Vision, Graphics and Image Processing, 41 (1988).
[2] Plemenos D., X. Pueyo, Heuristic Sampling Techniques for Shooting Rays in radiosity algorithms. In 3IA'96 Conference, Limoges (France), 3-4 April 1996.
[3] Shirley P., Radiosity via raytracing. In James Arvo, editor, Graphics Gem II, pages 306-310. Academic Press, San Diego, 1991.
[4] Feda M., W. Purgathofer, Progressive Ray Refinement for Monte Carlo Radiosity. In Fourth Eurographics Workshop on Rendering, pages 15-25, June 1993.
[5] Jolivet V., D. Plemenos, The Hemisphere Subdivision Method for Monte Carlo Radiosity. In Graphicon'97, Moscow, 21-24 May 1997.
[6] Jolivet V., D. Plemenos, A New Hemisphere Subdivision Method for Monte Carlo Radiosity. In Graphicon'98, Moscow, 5-12 September 1998.
[7] Jolivet V., D. Plemenos, M. Sbert, A Pyramidal Hemisphere Subdivision Method for Monte Carlo Radiosity. In Proc. Eurographics '99, Short papers, Milano, September 1999.
[8] Jolivet V., D. Plemenos, M. Sbert, Pyramidal Hemisphere Subdivision Radiosity. Definition and Improvements. In WSCG’2000, Plzen, February 2000.
[9] Colin C., Automatic computing of scene’s "good views". MICAD'90, Paris , February 1990 (in French).
[10] Plemenos D., A contribution to study and development of scene modeling, generation et display techniques - The “MultiFormes” project. Professorial dissertation, Nantes (France), November 1991 (in French).
[11] Plemenos D., Sokolov D., “Intelligent scene display and exploration”. STAR Report. International Conference GraphiCon'2006, Novosibirsk (Russia), June 30- July 5, 2006, pp. ?.
[12] Plemenos D., Grasset J., Jaubert B., Tamine K., “Intelligent visibility-based 3D scene processing techniques for computer games”. STAR Report. International Conference GraphiCon'2005, Novosibirsk (Russia), June 20-24, 2005, pp. 17-24.
[13] Plemenos D., Sbert M., Feixas M., “On viewpoint complexity of 3D scenes”. STAR Report. International Conference GraphiCon'2004, Moscow (Russia), September 6-10, 2004, pp. 24-31.
[14] Sokolov D., PlemenosD., Tamine K., “Methods and data structures for virtual world exploration”. " The Visual Computer ", Volume 22, no 7, pp. 506-516, 2006.
[15] Sokolov D., Plemenos D., Tamine K., “Viewpoint quality and global scene exploration strategies”. International Conference in Computer Graphics and Applications (GRAPP'2006), Setubal (Portugal), February 2006, pp.184-191.
[16] Sokolov D., Plemenos D., “Viewpoint quality and scene understanding”. The 6th International Eurographics Symposium on Virtual Reality, Archaeulogy and Cultural Heritage (VAST'2005), Pisa (Italy), November 8-11, 2005, pp. 67-73.
[17] Sbert M., Plemenos D, Feixas M., Gonzalez F., “Viewpoint Quality: Measures and Applications”. Computational Aesthetics in Graphics, Visualization and Imaging, Girona, May 2005, pp.1-8.
[18] Plemenos D., “Exploring virtual worlds. Current techniques and future issues”. International Conference GraphiCon’2003, Moscow (Russia), 2003.
[19] Plemenos D., Benayada M., “Intelligent Display in Scene Modelling. New Techniques to Automatically Compute Good Views”. International Conference GraphiCon’96, Saint Petersburg (Russia), 1996.
[20] Dorme G., “Study and Implementation of 3D Scene Understanding Techniques”. PhD Thesis, University of Limoges (France), 2001 (in French).
[21] M.Feixas, E.Acebo, Philippe Bekaert and M.Sbert, An information theory framework for the analysis of scene complexity, Eurographics'99.
[22] Vázquez P.P., Feixas M., Sbert M. and Heidrich W., Viewpoint Selection Using Viewpoint Entropy. Vision, Modeling, and Visualization 2001 (Stuttgart, Germany), pp. 273-280, 2001.
[23] Vázquez P.P. and Sbert M., Fast adaptive selection of best views. Lecture Notes in Computer Science, 2003 (Proc. of ICCSA'2003).
[24] Vázquez P.P., Feixas M., Sbert M., and Heidrich W., Automatic View Selection Using Viewpoint Entropy and its Application to Image-Based Modeling. Computer Graphics Forum, December-2003.