Next time you want to buy a toy for your cat, consider buying an iPad instead!

Finished writing my own acceleration structure for my Ray Tracer. Currently it's something between a KD-Tree and an Octree. I expected performance to be slightly better than my original code, but to my suprise it's already superfast (< 1 second for a Stanford Dragon) and I didn't even optimize it yet.

Last week I had a working implementation of the n-dimensional Hilbert algorithm. Next step was using a 3D Hilbert curve on my depth maps. Goal: further increase the compression ratio of my depth maps. I had already done some tests with this kind of curve two weeks ago and back then the results were interesting enough to do some further experimenting.

Due to implementation issues back then, I was however limited to a curve of (2⁷)³ elements. For 1024 depth maps with a resolution of 128x128 pixels this came down to 8 cubes of (2⁷)³ elements (1024x128x128 = 2²⁴ = (2⁷)³ x 2³). With my new implementation this restriction is gone and I can generate Hilbert curves up to (2¹⁰)³ (going any higher would require the use of 64 bits integers, which would only slow down my computations, something that is to be avoided as much as possible).

These are the currently best results:


As can be seen from this graph, the 3D Hilbert compression outperforms the per-pixel compression for anything below 9216 (96²) depth maps. Beyond that per-pixel compression is still the way to go. Two weeks ago I thought that this could possibly be solved by increasing the resolution of my Hilbert curve (and thus reducing the amount of cubes necessary to browse through all my data). Last week I got more insight in the recursive nature of the Hilbert curve and had a suspicision that the size of my cubes (and the resolution of the Hilbert curve) wouldn't matter that much. The thing is, a Hilbert curve of a higher resolution is basically a concatenation of rotated versions of a lower resolution Hilbert curve. So the difference between one cube of a high resolution and two cubes of lower resolution is merely a rotation. And due to it's nature, the effect of these rotations are minimal.


This theory is also confirmed in practice. The results for higher resolution Hilbert curves are nearly identical to those given above (up to some KB).

After spending the last week on spherical stuff, I'm currently implementing an algorithm to build Hilbert curves. My idea of increasing the compression rate for the Coherent Shadow Maps is to use a 3D (possibly 4D) Hilbert curve that will traverse through all my data. Due to its nature, the Hilbert curve is very good at preserving data locality. This in turn affects my compression ratio in a positive way.


Writing a program that can generate multi-dimensional Hilbert curves for a variety of resolutions is however, far from trivial. Fortunately, a few years ago C. Hamilton wrote a couple of articles on the subject together with a high-level version of the algorithm^{1, 2}. Currently I have a CPU version of the basic algorithm working.

In his work, Hamilton also wrote about Compact Hilbert Indices. This allows for Hilbert curves to be applied to non-hypercubic data (a rectangle instead of a square for example). Though a Hilbert curve is still generated for the smallest hypercube fitting around all data, the compact indices don't require as much memory (bits) as their conventional indices. This is the next thing I will implement and once the job is done, I can begin working on the GPU version of the algorithm. I wonder if anyone ever tried that before :).

[1] C. H. Hamilton. Compact Hilbert Indices. Dalhousie University Technical Report CS-2006-07, July 2006.
[2] C. H. Hamilton, A. Rau-Chaplin. Compact Hilbert Indices: Space-filling curves for domains with unequal side lengths. Information Processing Letters, 105(5), 155--163, Feburary 2008.

Time to give a recap on what I've been doing the last week:

1. Bounding Sphere Algorithm
I've implemented some more advanced algorithms for finding the (minimum) bounding sphere of an object. I first tried the Ritter algorithm (Graphics Gems, 1990). Ritter stated that his algorithm should give an approximation within 5% of the true minimum sphere. A simple test on a cube proved otherwise though.
Then I tried the Gärtner algorithm. Writing my own implementation would be to much work, so I used an existing implementation from here. After doing some tests with the algorithm, it seems the implementation must be broken because I never even ended up with a sphere containing all the necessary vertices ...

In short: attempts to use another bounding sphere algorithm failed.

2. Uniform Sampling
Taking uniform samples on my bounding sphere gave some interesting results. Depending on the orientation of my bounding sphere and the space-filling curve used to traverse through my samples on this sphere, it's possible to decrease the size of the compressed depth maps with one third (compared to my original results). There's also a huge variation in the size of the CSM's for various settings of orientation and space-filling curve.

To give you an example, an Armadillo with 1024 depth maps:
Uniform, Vertical Zig-Zag curve and a ZYX (left) rotation of the bounding sphere: 6.6 Mb.
Not uniform, Horizontal Zig-Zag curve, YXZ: 17.3 Mb!


In order to find the best match of orientation, sampling and path-curve I wrote a script that builds CSM's for all of the possible combinations for a specific number of depth maps. This was repeated for the Stanford Dragon, Bunny, Teapot, Armadillo and Venus. (I currently have around 9Gb of CSM's, without going any higher than 4096 depth maps). As an overal result of all the data I gathered, the (ZXY, Uniform, Vertical Zig-Zag) combination gave the smallest (and best) CSM's. I have yet to test if this is also the case for the overall quality of my shadows.

3. Hilbert Curve
Started reading some papers on how to generate the curve and algorithms for switching between the 1-dimensional and n-dimensional indices of the curve. Goals for this week are getting these implemented and start building results.

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:

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:

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:


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]² 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