Spherical Coordinates

Monday 8 March, 2010

In orde to reduce the oversampling at the poles of my bounding sphere, I tried out this distribution. The visual result of this is given below:

Non-uniform

Uniform

Coherence Maps

Monday 22 February, 2010

Last week I’ve created a small program which allows me to render all of my compressed depth maps separately. This way I can manually look at each depth map and get an idea of how correct they are. I also implemented a way to render what I call Coherence Maps. These maps give an idea on how coherent each pixel is over all depth maps. When a pixel is white, it means that the depth value for this pixel is the same for all depth maps, and thus we have perfect coherence. A black pixel means the opposite, namely a lot of variation in the depth values for that pixel. This means a low coherence and low compression rate.

Some examples of these coherence maps are shown below:

Stanford Dragon (left) and Sphere (right)

Utah Teapot (left) and Stanford Bunny (right)

More Results

Sunday 7 February, 2010

In my attempt to find out why the Hilbert curve doesn’t give better results than the Zig-Zag one, I experimented a bit with rotated versions of my path-filling curves. Instead of going from left to right, I tried going up and down (= 90° rotation). A 2D representation of this:

Original Zig-Zag (left) and the 90° CCW rotation (right)

The result of this simple rotation however is quite shocking. With the original curve my compressed map was 136Mb, with the rotated version it was 244Mb! Yes, that’s almost twice as big!

Of course, the real question is: why is there such a big difference between both maps? The answer: because my sampled points aren’t equidistant in (theta, phi)-space. To sample the entire surface of the bounding sphere surrounding my object, I first build a regular sampled grid in the [0, 1]2 square and then scale this up to [0, PI] x [0, 2PI]. Et voila, instead of equidistant points in my square, we get a rectangular surface with non-equidistant points (green and blue arrow):

As the distance between vertically-aligned points (blue) is larger than for horizontally-aligned points (green), this means there are also more differences between the vertically-aligned points and thus less coherence and worse compression. This explains why the rotated version of the Zig-Zag curve performs worse than the original version. Because we’re moving in the vertical direction the majority of the time, the compression rate decreases dramatically. One might think that increasing the number of samples minimizes this problem, but the previously mentioned results already used 65.536 depth maps, hardly a small sample size.

I also tried rotated versions of the linear curve and the Hilbert curve. Results are given below, but they are hardly worth mentioning:

Stanford Dragon, 65.536 depth maps:

Zig-Zag: 136Mb
Zig-Zag 90° CCW: 244Mb

Hilbert: 147Mb
Hilbert 90° CCW: 147Mb
Hilbert 180° CCW: 147Mb
Hilbert 270° CCW: 147Mb

Linear: 145 Mb
Linear 90°CCW: 248Mb

Hilbert / Spiral Results

Saturday 6 February, 2010

As promised, some results of using different space-filling curves:

Sphere – 16.384 depth maps:
Zig-Zag: 6 Mb
Hilbert: 7 Mb
Spiral: 8 Mb

Sphere – 65.536 depth maps:
Zig-Zag: 15 Mb
Hilbert: 17 Mb
Spiral: 19 Mb

Sphere – 262.144 depth maps:
Zig-Zag: 42 Mb
Hilbert: 43 Mb
Spiral: 51 Mb

Dragon – 16.384 depth maps:
Zig-Zag: 61 Mb
Hilbert: 69 Mb
Spiral: 83 Mb

Dragon – 65.536 depth maps:
Zig-Zag: 136 Mb
Hilbert: 147 Mb
Spiral: 188 Mb

Dragon – 262.144 depth maps:
Zig-Zag: 302 Mb
Hilbert: 308 Mb
Spiral: 420 Mb

Zig-zag still seems the best choice. I also double-checked my Hilbert implementation but unfortunately I didn’t find any bugs in it.

Space-Filling Curves

Saturday 30 January, 2010

The past two days I’ve been reading a bit about space-filling curves. These are basically curves that allow you to traverse through a 2D (or any N-Dimensional) space without visiting a single point more than once.

You might wonder why these are important. Well, in order to achieve a high compression ratio for my depth maps, I need to find a highly coherent permutation of these. This permutation basicly corresponds to the order in which my depth maps are generated and compressed. (For a visual representation of this, check out the movies later on in this post.)

Currently I’ve been using a Zig-Zag curve. Other examples of space-filling curves are a Spiral or Hilbert curve. Especially the Hilbert curve is quite known and can be used for a variety of things. Some of the more art-like applications I found on the internet are color sorting or traversing the 3-dimensional RGB cube:

Below is a 2D representation of the Zig-Zag, Spiral and Hilbert space-filling curve:

Zig-zag (left) and spiral (right).

Hilbert curve of third order.

To give you an idea on how these curves are mapped on my 3D sphere:

Of course, what’s really important are the results of using these new space curves. And unfortunately both the Spiral and Hilbert curve perform worse than my original Zig-Zag curve . Especially the result for the Hilbert curve suprises me, I really expected an improvement …

(Detailed results will follow later.)

Thesis Update

Friday 29 January, 2010

It’s been a while since I made a post about my thesis so time to give you guys an update. Since many people probably forgot what my thesis is about, here’s a quick recap:

Last semester I’ve been working on a technique to render realistic looking shadows for non-deformable objects in 3D scenes and this in real-time. The technique I use is called Coherent Shadow Maps and was discovered by Tobias Ritschel in 2007 [1]. In december I had a working implementation of this technique, resulting in pictures like this:

Stanford Dragon using Coherent Shadow Maps

A high-level description of how the algorithm works is the following:

The goal for this semester is to find improvements for this technique. The main focus will be on increasing my compression ratio. Storing the information of 262.000 shadow maps of the Stanford Dragon still requires 300Mb. Even though the uncompressed size is 32Gb (that’s around 8 DVD’s), it’s still way to big for most applications.

The following two weeks I will mainly focus on the sampling part (ie. building shadow maps on the bounding sphere of an object) and less on the compression part of the algorithm. Here’s my short term list of things to do:

1. Check out other space curves for sampling the bounding sphere (spiral, Hilbert, …). More information about this tomorrow.
2. Find a way to integrate something like k-means clustering or an adaptive sampling procedure.
3. Find or build a highly non-coherent object (like a fractal) for testing purposes.

[1] RITSCHEL, T., GROSCH, T., KAUTZ, J., AND MUELLER, S.
2007. Interactive illumination with coherent shadow maps. In
Proceedings of the Eurographics Symposium on Rendering.