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. |
VRLab 51.182 polygons |
Aircraft: 184,456 polygons. |
Aircraft 184.456 polygons |
Trees: 15,188 polygons. |
Trees 15.188 polygons |
Office: 5,260 polygons. |
Office 5.260 polygons |
Hall: 273,473 polygons. |
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) |
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
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
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 |