Introduction to Probabilistic Visibility

I finished reading through Björn Engelen's thesis on Probabilistic Visibility and I would like to spend this post to summarize some of his results, explain the idea behind probabilistic visibility and prove that probabilistic visibility works. I will conclude with an implementation of a naïve probabilistic visibility algorithm in my own ray tracer to demonstrate the algoritm.

Since HTML has little support for mathematical formules, the main content will be available in this pdf file: Probabilistic Visibility Post.

The main conclusion will be restated here. It can be proved that the probabilistic visibility estimation will converge to the correct solution. However, since the evaluation is a Monte-Carlo process, it will introduce more variance in the estimation of the radiance. The upside is, that the number of intersections  needed to perform the probabilistic evaluation is a lot less than the number of intersections for deterministic evaluation.

The experiments by Björn and the implementation in my own ray tracer confirm these results. Below are some images with an increasing number of shadow rays.

Deterministic visibility (16 shadow rays)

Probabilistic visibility (16 shadow rays)

Deterministic visibility (64 shadow rays)

Probabilistic Visibility (64 shadow rays)

Deterministic Visibility (256 shadow rays)

Probabilistic Visibility (256 shadow rays)

The number of intersections evolves as shown in the next graph:

And when we divide the number of intersections for deterministic visibility, by the number of probabilistic visibility, it shows that deterministic visibility requires 50% more intersections.

For a more detailed report, consult the pdf.

Mastering C++ - Global Illumination

While I was programming on my ray tracer, I got a little stuck in a bush of errors and a bad class design (that's what you get when you start programming without thinking about a proper design :P). Therefore I restarted with the help of the book Physically Based Rendering - From Theory to Implementation.

This is an excellent book on graphics theory with lots of code snippets. After rewriting my previous raytracer, I also added global illumination and a specular surface. The result is shown below.

Cornell box with 100 samples per pixel for the direct illumination and 1000 samples per pixel for the indirect illumination

The program is also multithreaded by using the pthreads library. I feel now that I've got C++ pretty good in the fingers.

The next step as a preperation for my thesis, is reading the previous work by Björn Engelen. In his master's thesis, he explains the probabilistic visibility approach to rendering and proves that the images will ultimately converge to the correct solution. Furthermore, I will continue to read in the PBR book to familiarize myself with the PBRT raytracer that comes with the book.

Mastering C++ - Raytracer

After my little chess game, I felt a bit more ambitious and I started on implementing a simple ray tracer. I partially borrowed the basic structure for the program from the appendix of the book Advanced Global Illumination.

The implementation proved to be quite a struggle, since the books don't prepare you from the errors. The errors from the compiler aren't a great help either and having a null pointer just stops the program leaving you no clue about where it all went wrong.

However, after a little less than 25 hours of programming, I finally managed to calculate the direct lighting in a simple cornell box with two spheres.

Cornell box with two spheres. Rendered with path tracing and 1000 rays per pixel.

The code, however, is a little bit messy and could be a bit more efficient. The next step is code cleanup, a little documentation and calculating the global illumination in the scene.

Mastering C++ - A chess game

Knowledge of C++ is a prerequisite for my thesis. Since the only languages I'm profound in are Java, GML and Matlab, I'll spend quite some time mastering C++ during the summer vacation.

Last week I started reading the book Accelerated C++, which was a great introduction (better than C++ for Dummies which I tried last year). The great thing about this book is that it is example driven, motivating you to actually crawl behind your PC and program (which is the only way you can truly master a programming language).

After making my way through the first nine chapters, I started on a small project outside of the book to test my programming skills: a chess game. This would provide ample of exercise, since it involves input/output, inheritance, data management etc...

A quick preview of the output is shown below:

The code got a bit messy though, so I'll wait with posting a link to the source code ;)

Next up is implementing a simple ray tracer.

Thesis Probabilistic Visibility - Introduction

I am Niels Billen, a graduate student in Computer Sciences, at the KULeuven University in Belgium. In the coming year I'll start working on my thesis under the watchfull eye of prof. dr. ir. Philip Dutré. The subject of my thesis is Probabilistic Visibility in Computer Graphics.

In this thesis I'll try develop a novel algorithm to accelerate the calculation of the visibility function in a scene. This will be done by reducing the number of object-ray intersection not (only) by using a spatial acceleration structure, but intersecting only a subset of the objects in a stochastic manner.

The implementation of the algorithm will be in C++, probably by expanding on code of the PBRT engine. I have never programmed in C++ however, so mastering C++ will be a fine starting point for my thesis.

I'll blog regularly about my progress, so stay tuned for more updates.