Premium
Global Illumination Using Well‐Separated Pair Decomposition
Author(s) -
Bus N.,
Mustafa N. H.,
Biri V.
Publication year - 2015
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/cgf.12610
Subject(s) - cluster analysis , computer science , rendering (computer graphics) , global illumination , point (geometry) , radiosity (computer graphics) , artificial intelligence , decomposition , set (abstract data type) , computer vision , algorithm , computer graphics (images) , mathematics , geometry , ecology , biology , programming language
Abstract Instant radiosity methods rely on using a large number of virtual point lights (VPLs) to approximate global illumination. Efficiency considerations require grouping the VPLs into a small number of clusters that are treated as individual lights with respect to each point to be shaded. Two examples of clustering algorithms are Lightcuts [WFA*05] and LightSlice [OP11]. In this work, we use the notion of geometric separatedness of point sets as a basis for a data structure for pre‐computing and compactly storing a set of candidate VPL clusterings. Our data structure is created prior to rendering, is view‐independent and relies only on geometric and radiometric information. For any point to be shaded, we show that a suitable clustering of the VPLs can be efficiently extracted from this data structure. We develop the above framework into an accurate and efficient clustering algorithm based on well‐separated pair decompositions which outperforms earlier work in speed and/or quality for diffuse scenes.