Holey Sampling: Topological Analysis of Sampling Patterns for Assessing Error in High-dimensional Quadrature

Estimating integrals of functions forms the cornerstone of many general classes of problems such as optimisation, sampling and normalisation; these problems, in turn, are central tools for a plethora of applications across various fields such as computer graphics, computer vision and machine learning. The integrand, or function to be integrated, is complicated and rarely available in closed form. Its domain spans spaces of arbitrarily high dimensionality. Exact integration is hopeless and approximation is unavoidable in practice. An estimate of the integral is typically constructed using evaluations of the integrand at a number of sampled locations in the domain. The set of points where the function is sampled is often referred to collectively as a sampling pattern. For computer graphics applications, a modern animation feature film of length 1.5h typically involves the generation of a total of a few hundreds of trillions of high-dimensional samples that are mapped into light paths.

Although a number of strategies have been proposed towards generating samples, measuring the quality of high-dimensional sampling patterns is an open problem. Sampling strategies are currently compared on a case-by-case basis by explicitly computing errors in the context of each application independently. The computation associated with measures such as discrepancy and Fourier analysis scale exponentially with dimensionality and are therefore not practicable for samples in high-dimensional domains.

The proposed work seeks to quantify equidistribution of high-dimensional point sets using an alternative measure to discrepancy that is tractable. This project will establish mathematical connections between computational topology, stochastic geometry and error analysis for Monte Carlo integration. The goal is to develop a measure for assessing the quality of sampling-based estimators purely based on the samples used. The derived theory will be evaluated and applied on Monte Carlo rendering for Computer Graphics applications.

The proposed research will improve the state of the art in assessing sampling strategies used for rendering computer graphics imagery. Identifying efficient sampling strategies is key for fast rendering. An animated feature film of 1.5h typically requires about 100 million CPU hours of computation for its final render. The number of Monte Carlo samples drawn is typically in the order of hundreds of trillions. Even identifying that a particular sampling strategy is a mere 1% improvement in error over others leads to a saving of the order of millions of CPU hours.

The proposed project will impact companies that develop or rely on rendering software to generate realistic computer graphics imagery. Companies in the business of visual effects for motion pictures, such as Framestore, Double Negative, Moving Picture Company, Industrial Light Magic, etc., develop their own rendering software. In addition, major users of rendering software are spread widely across other fields such as video games, architecture and advertising. The Department for Culture Media and Support estimates (2016) that the Gross Value Added due to the Creative Industries was £84.1bn in 2014 of which IT and computer services constitute about 62%.

Companies with large budgets, such as Framestore and Double Negative, are able to adapt and tinker with sampling strategies developed by academic researchers for their own benefit. However, even this requires employees with specialist know-how and exemplary mathematical and computer programming abilities (letters attached). Recruitment of such trained people is a looming issue.

Techniques developed by large companies are often protected IP and thereby affect the balance of the wider ecosystem of the creative industries. As EPSRC acknowledges on their webpage for Graphics and Visualisation, a large portion of the creative industries is formed by a vibrant community of small and medium-sized enterprises (SMEs) which rely heavily on academic research for improvements to fundamental problems such as sampling.

The proposed research will generate impact through both fundamental improvements to sampling for rendering as well as improved skills (via improved curricula) and dissemination (course at ACM SIGGRAPH).