Three Point Clustering for Radiance Computations

Marc Stamminger, Philipp Slusallek, Hans-Peter SeidelRendering Techniques 1998 · DOI

TL;DR

This paper introduces "Three Point Clustering," a novel hierarchical approach to accelerate non-diffuse global illumination computations. By representing light transport within a line space hierarchy and projecting radiance directly, it overcomes limitations of previous finite-element methods, enabling more efficient and accurate rendering of complex lighting scenarios.

What Problem Does This Paper Address?

Rendering realistic global illumination in computer graphics is computationally intensive, especially for scenes with non-diffuse (e.g., glossy, specular) surfaces. While diffuse scenes can be handled efficiently with methods like radiosity, non-diffuse surfaces require considering the direction of light, significantly increasing complexity. Existing finite-element approaches for non-diffuse scenes often suffer from extremely long computation times, limiting their applicability to simple scenes. Monte-Carlo methods, while more general, can be slow to converge and produce noisy results. The paper aims to bridge this gap by developing a finite-element method that is both efficient and capable of handling complex non-diffuse lighting.

Methods

The core of the paper is the "Three Point Clustering" algorithm, which builds upon the concept of a line space hierarchy. This hierarchy represents all mutually visible connections between scene objects. The algorithm iteratively refines the radiance solution by:

  • Line Space Hierarchy: A hierarchical representation of directional light transport is constructed. Unlike traditional hierarchical radiosity, illumination is stored within this line space hierarchy, not directly on scene objects.
  • Radiance Projection: Instead of projecting the rendering equation's kernel (as in some prior methods), this algorithm directly projects the radiance onto the hierarchical basis. This is a key difference that helps avoid the "sum of projection" problem and allows for better control over representation error.
  • Bounded Computations: To avoid sampling issues, especially with specular surfaces, the algorithm computes bounds on radiance and BRDF values. This ensures that details are not missed, even with complex shaders.
  • Diffuse Object Optimization: A specific optimization is included for diffuse objects, allowing them to be handled much like traditional radiosity, significantly speeding up computations for scenes with mixed diffuse and non-diffuse elements.

Datasets

Not discussed in the paper. The paper uses synthetic test scenes for evaluation, including a caustic from a cylinder, a "disco" ball scene, and a dining room scene.

Key Insights and Ideas

  • Projecting Radiance vs. Kernel: Directly projecting the radiance onto the hierarchical representation, rather than the rendering equation's kernel, is crucial for avoiding artifacts and achieving better refinement control in non-diffuse scenarios.
  • Line Space Hierarchy for Illumination: Storing illumination information within the line space hierarchy, rather than on scene objects, simplifies the reflection computation and allows for efficient traversal.
  • Bounded Computations are Essential: For non-diffuse surfaces, especially specular ones, using bounded computations for radiance and BRDFs is critical to avoid sampling problems and capture fine details accurately.
  • Diffuse Optimization is Key: Differentiating between diffuse and non-diffuse surfaces and applying specific optimizations for diffuse objects can drastically improve performance, making the algorithm behave similarly to radiosity for purely diffuse scenes.

Key Results

The paper demonstrates the effectiveness of Three Point Clustering through several test scenes:

  • Caustic Scene: A caustic from a cylinder was computed in 206 seconds on a 196 MHz R10k, producing a result that would typically suffer from sampling problems in other methods.
  • Disco Ball Scene: A complex scene with glossy patches took 800 seconds on an SGI Onyx (R10k CPU at 195 MHz). The authors note that a significant portion of this time was spent on computing the line space measure (propagation) and, particularly, on bounded BRDF evaluations for clusters.
  • Room Scene: A scene with specular table and chairs, featuring a strong highlight, was rendered in 500 seconds. Again, reflection computations, especially BRDF queries to clusters, were identified as bottlenecks.
  • Diffuse Room Scene: When compared to a standard clustering algorithm for a diffuse scene, the three-point clustering approach was less than twice as slow. With diffuse optimizations enabled, it performed comparably to radiosity.

Limitations and Future Work

  • BRDF Evaluation Cost: The authors acknowledge that the high cost of evaluating BRDFs, especially for clusters, is a significant bottleneck. They are actively working on an optimized hierarchical version of reflection computations for clusters to address this.
  • Refiner Selection: While the paper uses a simple "Darea" refiner for the line space hierarchy, they suggest that finding better refiners that account for scene properties (like constant radiance over a receiver) is an interesting area for future research.
  • Generalization: The paper focuses on a specific parameterization and hierarchy. Further research could explore alternative representations and refinements for even greater efficiency and accuracy.

Summary updated

BibTeX
@inproceedings{stamminger1998three,
  author = {Marc Stamminger and Philipp Slusallek and Hans-Peter Seidel},
  title = {{Three Point Clustering for Radiance Computations}},
  booktitle = {Rendering Techniques},
  year = {1998},
  doi = {10.1007/978-3-7091-6453-2\_20},
}
Figure