Spheres

Sunday 14 March, 2010

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.