Meshless Finite Elements for Hierarchical Global Illumination

Jaakko Lehtinen, Matthias Zwicker, Janne Kontkanen, Emmanuel Turquin, François X. Sillion, Timo Aila2007

TL;DR

This paper introduces a novel "meshless" finite element framework for simulating global illumination in computer graphics. By decoupling lighting calculations from scene geometry and using hierarchical scattered data approximation, it overcomes limitations of traditional methods, leading to more accurate, artifact-free renderings and easier implementation.

What Problem Does This Paper Address?

Traditional finite element methods for global illumination, like radiosity, have been hampered by several issues. They typically rely on meshing and parameterizing scene geometry, which is a complex, error-prone, and sensitive pre-processing step. The resulting lighting solutions often exhibit visible discontinuities, requiring heuristic post-processing. Furthermore, these methods tightly couple lighting computations with geometric representations, unlike more modern techniques like irradiance caching or photon mapping. This paper aims to provide a more robust, flexible, and production-friendly finite element approach by addressing these limitations.

Methods

The core innovation is a meshless finite element framework that leverages hierarchical scattered data approximation techniques. Instead of relying on a mesh, the lighting functions are represented using basis functions derived from a set of scattered points. This approach decouples the function spaces used for solving the rendering equation from the scene's geometric representation.

Key methodological components include:

  • Meshless Multilevel Approximation: This technique, inspired by Floater and Iske, uses a cascade of function spaces with increasing density of scattered points. It builds approximations progressively, similar to wavelets, leading to efficient representations.
  • Shepard Approximation with Modified Weights: The paper uses Shepard approximation for scattered data, but crucially modifies the weighting functions. These weights combine a spatial fall-off kernel with a factor that considers the alignment of surface normals, allowing for more accurate representation of lighting on surfaces with varying orientations.
  • Operator Discretization: The rendering equation is discretized using these meshless basis functions. This results in a transport matrix where coefficients represent the interaction between basis functions, independent of explicit geometric meshing.
  • Extension to Glossy Surfaces: The framework is extended to handle glossy reflections by incorporating directional bases (like spherical harmonics) alongside the spatial meshless basis functions, creating a tensor product space.

Datasets

Not discussed in the paper. The paper uses example scenes (Sibenik cathedral, Michelangelo's David, Cornell box) for demonstration and evaluation, but these are not presented as formal datasets.

Key Insights and Ideas

  • Decoupling Lighting from Geometry is Key: The paper strongly advocates for separating the representation of lighting from the underlying scene geometry. This is a major departure from traditional finite element methods and allows for greater flexibility and robustness.
  • Meshless Approach Solves Pre-processing Woes: By avoiding explicit meshing and parameterization, the method significantly simplifies the workflow and reduces the sensitivity to input geometry quality.
  • Artifact-Free Solutions: The meshless nature and the way basis functions are constructed lead to solutions that are accurate and free from the spurious discontinuities often seen in traditional finite element methods.
  • Hierarchical Representation for Efficiency: The multilevel approximation scheme allows for efficient representation of lighting, similar to wavelets, enabling sparse operator representations and faster computations.
  • Flexibility for Various Illumination Models: The framework is shown to be applicable to hierarchical radiosity, glossy precomputed radiance transfer (PRT) from distant and local light sources, demonstrating its versatility.

Key Results

The paper demonstrates the effectiveness of its meshless finite element framework through several applications:

  • Hierarchical Radiosity: Produces high-quality, artifact-free renderings of complex scenes (e.g., Michelangelo's David) without pre- or post-processing. The method shows visual convergence towards path-traced results.
  • Glossy PRT: Achieves interactive rendering (7.2 FPS at 960x720) for scenes with complex lighting and materials. Precomputation for a glossy Buddha model took 8 minutes and 18 seconds, with adaptive computation of transfer matrices saving time and memory.
  • Indirect Diffuse PRT: Enables real-time rendering of indirect illumination from local light sources. For the Sibenik scene (1.2M triangles), precomputation was significantly faster (31 minutes) compared to previous methods, with runtime memory consumption of 103 MB and 7.2 FPS.

Limitations and Future Work

  • Basis Function Leakage: Coarse basis functions can sometimes "leak" into adjacent areas (e.g., through walls), requiring finer levels to correct.
  • Normal Orientation Sensitivity: The weighting functions rely on consistently oriented surface normals.
  • Sharp Discontinuities: The smooth basis functions cannot perfectly represent sharp discontinuities like shadow boundaries, potentially leading to minor ringing artifacts.
  • Future Work:
    • Generalization to participating media.
  • Improved weighting functions, potentially anisotropic ones that better follow surface geometry.
  • More sophisticated point placement strategies, possibly adaptive or offset from surfaces for better detail handling.
  • Combining their approach with better discontinuity-handling techniques (e.g., bilateral filtering).
  • Exploring alternative representations for direct lighting to complement their indirect illumination approach.
  • Investigating smarter ways to manage the hierarchy and potentially flatten it for runtime performance.

Summary updated

Abstract

HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci-entific research documents, whether they are pub-lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et a ̀ la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.
BibTeX
@misc{lehtinen2007meshless,
  author = {Jaakko Lehtinen and Matthias Zwicker and Janne Kontkanen and Emmanuel Turquin and François X. Sillion and Timo Aila},
  title = {{Meshless Finite Elements for Hierarchical Global Illumination}},
  year = {2007},
}
Figure