Hierarchical Data Structures for Lighting Simulation
Deliverable 2.1-1

Comparative Experiments [added 10/13/1998]

Experimental Setup

The ARCADE partners have contributed a number of scenes which they have previously used, but not necessarily for radiosity rendering. We have taken these scenes as representative scenes for the clustering problem, allowing us to identify the different problems of the algorithms which we will test. The scenes tested are described in the following table:

VRlab: 51,182 polygons.
A model of the virtual reality lab at IGD, Darmstadt. The room has two floors and mostly overhead lighting.

VRLab 51.182 polygons

Aircraft: 184,456 polygons.
Model of an aircraft cabin. All objects have been tesselated into (rather small) triangles to account for the rounded shapes. Therefore the model contains a large number of small surfaces.

Aircraft 184.456 polygons

Trees: 15,188 polygons.
A model of several trees. This model is representative of some applications where an average representation of light transfers may be sufficient. In addition, it is a good test case for the volumetric visibility algorithm.

Trees 15.188 polygons

Office: 5,260 polygons.
A model of a simple office scene.

Office 5.260 polygons

Hall: 273,473 polygons.
A model of a large hall with some furniture. In this model there is a large range of object sizes.

Hall 273.473 polygons

We have decided to conduct tests with the following set of clustering methods.

Since the OBT algorithm and OBT-derived DHBV both accept an "overlap" parameter, we have used instances of these algorithms corresponding to the values [0.0 (regular KDT), 0.2, 0.5 and 0.85] for OBT, and [0.2, 0.85] for DHBV. The complete set of clusterizers used in our study is therefore:

HBV KDT = OBT(0.0) OBT(0.2) OBT(0.5) OBT(0.85) DHBV(0.2) DHBV(0.85)

Cluster statics

Let us first examine the spatial data structures created by our seven instances of the clusterizing mechanisms. The total number of clusters created in the scene is given in the following graph. From these figures we can already make the following obervations:

Total number of cluster

Another interesting global figure is the average number of children for each cluster node, as presented in the graph below:

We observe that the "branching factor" of all trees is similar in general, with the exception of DHBV, especially for a low value of lambda.This is due to a special feature of our DHBV algorithm, whereby a cluster containing a single surface (as created by the first OBT phase) will not be kept as a bounding volume, but instead merged up the hierarchy until a "sufficiently dense" cluster is found. Therefore DHBV creates no clusters with a single surface.

Average number of children elements

Construction efficiency

Looking at the construction time for all clusterizers, it is obvious that HBV behaves very differently than all others. This is clearly due to the inherent complexity of the algorithm, which is essentially an optimization procedure and has to work from the bottom up.

OBT and DHBV clusterizers require more time as the parameter lambda is increased. This is a natural consequence of the behavior described above, with objects being pushed further down the hierarchy thanks to a more relaxed tolerance on overlap.

DHBV clusterizers naturally exhibit some overhead cost compared to their corresponding OBT, since they first construct the OBT structure, then extract a HBV hierarchy from its analysis. Note however that this second phase typically accounts for only about 5-10% of the OBT building time.

Cluster time

Quality of volumetric visibility

In order to "visually" compare the influence of the hierarchy structure on the quality of volumetric visibility, we show the result of the first iteration of the radiosity algorithm (direct lighting) for the test scene involving trees (the set of leaves being a good approximation of a turbid media).

Compared to the reference image shown at the top (obtained with classical ray casting on the surfaces), we see that as we go from KDT to OBT to DHBV to HBV, the quality of the " volumetric " shadows increases, as well as the computation time. In terms of quality, this means that the clusters are more tightly fit around the enclosed objects, which is logical in this sequence. As far as computation time goes, it is interesting to note that the ordering is not the same as that obtained when measuring " random " ray tracing acceleration. This can probably be explained by the fact that we do not simply test for a single hit as in classical ray casting, but instead build a list of all segments traversed by a given ray, in order to combine all the corresponding attenuation contributions.

Reference image

KDT: 1.676 seconds

OBT(0.5): 3.027 seconds

DHBV: 11.982 seconds

HBV: 20.371 seconds