## Fachbereich Informatik

We introduce two novel techniques for speeding up the generation of digital \((t,s)\)-sequences. Based on these results a new algorithm for the construction of Owen's randomly permuted \((t,s)\)-sequences is developed and analyzed. An implementation of the new techniques is available at http://www.cs.caltech.edu/~ilja/libseq/index.html

Monte Carlo integration is often used for antialiasing in rendering processes.
Due to low sampling rates only expected error estimates can be stated, and the variance can be high. In this article quasi-Monte Carlo methods are presented, achieving a guaranteed upper error bound and a convergence rate essentially as fast as usual Monte Carlo.

The radiance equation, which describes the global illumination problem in computer graphics, is a high dimensional integral equation. Estimates of the solution are usually computed on the basis of Monte Carlo methods. In this paper we propose and investigate quasi-Monte Carlo methods, which means that we replace (pseudo-) random samples by low discrepancy sequences, yielding deterministic algorithms. We carry out a comparative numerical study between Monte Carlo and quasi-Monte Carlo methods. Our results show that quasi-Monte Carlo converges considerably faster.

The main problem in computer graphics is to solve the global illumination problem,
which is given by a Fredholm integral equation of the second kind, called the radiance equation (REQ). In order to achieve realistic images, a very complex kernel
of the integral equation, modelling all physical effects of light, must be considered. Due to this complexity Monte Carlo methods seem to be an appropriate approach to solve the REQ approximately. We show that replacing Monte Carlo by quasi-Monte Carlo in some steps of the algorithm results in a faster convergence.

A fundamental variance reduction technique for Monte Carlo integration in the framework of integro-approximation problems is
presented. Using the method of dependent tests a successive hierarchical function approximation algorithm is developed, which
captures discontinuities and exploits smoothness in the target function. The general mathematical scheme and its highly efficient
implementation are illustrated for image generation by ray tracing,
yielding new and much faster image synthesis algorithms.

Instant Radiosity
(1997)

We present a fundamental procedure for instant rendering from the radiance equation. Operating directly on the textured scene description, the very efficient and simple algorithm produces photorealistic images without any kernel or solution discretization of the underlying integral equation. Rendering rates of a few seconds are obtained by exploiting graphics hardware, the deterministic
technique of the quasi-random walk for the solution of the global illumination problem, and the new method of jittered low discrepancy sampling.

Monte Carlo & Beyond
(2002)

Quasi-Monte Carlo Radiosity
(1996)

The problem of global illumination in computer graphics is described by a second kind Fredholm integral equation. Due to the complexity of this equation, Monte Carlo methods provide an interesting tool for approximating
solutions to this transport equation. For the case of the radiosity equation, we present the deterministic method of quasi-rondom walks. This method very efficiently uses low discrepancy sequences for integrating the Neumann series and consistently outperforms stochastic techniques. The method of quasi-random walks also is applicable to transport problems in settings other
than computer graphics.

The simulation of random fields has many applications in computer graphics such as e.g. ocean wave or turbulent wind field modeling. We present a new and strikingly simple synthesis algorithm for random fields on rank-1 lattices that requires only one Fourier transform independent of the dimension of the support of the random field. The underlying mathematical principle of discrete Fourier transforms on rank-1 lattices breaks the curse of dimension of the standard tensor product Fourier transform, i.e. the number of function values does not exponentially depend on the dimension, but can be chosen linearly.

Many rendering problems can only be solved using Monte Carlo integration. The noise and variance inherent with the statistical method efficiently can be reduced by stratification. So far only uncorrelated stratification methods were used that in addition depend on the dimension of the integration domain. Based on rank-1-lattices we present a new stratification technique that removes this dependency on dimension, is much more efficient by correlation, is trivial to implement, and robust to use. The superiority of the new scheme is demonstrated for standard rendering algorithms.