Enlightenment: A Monte-Carlo Ray Prediction Model

Team: 69

School: Los Alamos High

Area of Science: Physics/Graphics

Interim: Problem Definition:

Creating realistic digital images is a task that is important to a number of real world applications, including computer aided drafting, physics simulations, and modern medicine. However, the equations and algorithms involved are often imperfect, which can lead to faulty conclusions and results. This imperfection can usually be traced back to the difficulty that software developers encounter with the rendering equation.
The rendering equation, to this day, has never been fully solved. This is due to the mathematical complexity of the problem, the lack of a perfect physical light model, and the vast amount of computation required for even a partial solution. However, much like Simpson's rule can be used to estimate an integral, several mechanisms have been developed to aid in finding a prediction to the rendering equation.
Our purpose is to design and implement an effective solution to the rendering equation. A fully functional solution to the rendering equation would require absolute knowledge about the workings of light, which simply is not within the scope of current physics. Just like an integral can be evaluated a summation of smaller and smaller sections, we believe an highly accurate, or photorealistic, prediction of the rendering equation is possible given enough computational power. Currently, several predictions to the rendering equation have been proposed, including ray tracing, ray casting, and photon tracing. However no current single solution provides a satisfactory solution to the rendering equation.

Problem Solution:

Because we are interested in creating an highly accurate solution to the rendering equation, we will utilize a combination of bi-directional path tracing (ray tracing combined with photon tracing) and a Monte Carlo method known as the Metropolis-Hastings algorithm. We believe that the combined use of these two algorithms, in addition to advanced shading algorithms, will be able to create a unique and accurate solution to the rendering equation.

Progress to Date:

Currently, we have successfully implemented an advanced ray tracing algorithm for spheres and rectangles, with a similar algorithm for cylinders currently under developement. The vast amount of math involved with 3D space has proved to be difficult to work with, but not impossible. Our algorithm is capable of anti-aliasing and rendering reflection, refraction, and “soft shadows” (non-point light sources). Current running time for the project depends on the size of the requested image, ranging from 20 seconds for a 800 by 400 pixel image to several hours for a 1600 by 800 image.
Experimentation with homogenous and heterogenous networks for task distribution has yielded nearly perfect scaling factors. A version of the model utilizing stream processing has been started, and will be compared to the reference model in terms of scaling upon its completion.

Expected Results:

Despite many unpredicted road blocks, the progression of our project seems to consistent with our projected timeline. We hope to be able to expand our advanced ray tracing model to encompass a random-walk Monte Carlo method, allowing for one of the most, if not the most, accurate predictions of the rendering equations currently available.

References:

Kajiya, James T. (1986), "The rendering equation", Siggraph 1986: 143

Eric P. Lafortune and Yves D. Willems (December 1993). "Bi-Directional Path Tracing"

Roth, Scott D. (February 1982), "Ray Casting for Modeling Solids", Computer Graphics and Image Processing 18: 109–144

Team Members:

  Jake Poston
  Ryan Marcus
  Dov Shlachter
  Kathy Lin

Sponsoring Teacher: Lee Goodwin

Mail the entire Team