## Shutting down

### Featured

Dear readers, as you will certainly have noticed I haven’t been able to dedicate much time to this blog in the past years: Too many things going on at work, a family to support, two wonderful kids growing up,… just to name a few. And it doesn’t look like things are going to change. So I have decided to shut this site down: Mid September 2022 the site will be take off DNS and end of September 2022 the server will shut down for good.

I hope you have enjoyed the content as much as I have enjoyed making it and I wish you the best.

Theodor

# Depth Precision

In a previous post I discussed the use of reciprocal depth $1/z$ in depth buffer generation. I gave some figures showing the problematic hyperbolical depth value distribution in the depth buffer and the dependence on the near plane.

Let’s expand a bit on that and investigate strategies to better distribute depth values. In the following I will be using a right handed coordinate system, i.e. $-z$ points forward and (as usual) vectors are multiplied from the right. View space depth is denoted $z$ and the near/far planes are $z_n$ and $z_f$.

## Standard Depth

The standard DirectX projection matrix $\mathbf{P}$ as produced by D3DXMatrixPerspectiveFovRH, transforms view space positions $\mathbf{v} = (x, y, z)$ into clip space positions $\mathbf{v'}$

$\mathbf{v'} = \mathbf{P} \mathbf{v} = \begin{pmatrix}s_x & 0 & 0 & 0 \\ 0 & s_y & 0 & 0 \\ 0 & 0 & \frac{z_f}{z_n-z_f} & \frac{z_n z_f}{z_n-z_f} \\ 0 & 0 & -1 & 0\end{pmatrix} \mathbf{v}$

and results in depth buffer values

$z'=\frac{\frac{z_f}{z_n-z_f} z + \frac{z_n z_f}{z_n-z_f}}{-z}$

As shown before, this can cause a significant warp of the resulting depth values due to the division by $z$.

## Reverse Depth

Reverse depth aims to better distribute depth values by reversing clip space: Instead of mapping the interval $[z_n,z_f] \mapsto [0,1]$, the projection matrix is adjusted to produce $[z_n,z_f] \mapsto [1,0]$. This can be achieved by multiplying the projection matrix with a simple ‘z reversal’ matrix, yielding

$\mathbf{v'} = \begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -1 & 1 \\ 0 & 0 & 0 & 1\end{pmatrix} \mathbf{P} \mathbf{v} = \begin{pmatrix}s_x & 0 & 0 & 0 \\ 0 & s_y & 0 & 0 \\ 0 & 0 & -\frac{z_f}{z_n-z_f}-1& -\frac{z_n z_f}{z_n-z_f} \\ 0 & 0 & -1 & 0\end{pmatrix} \mathbf{v}$

The advantage of this mapping is that it’s much better suited to storing depth values in floating point format: Close to the near plane, where similar view depth values are pushed far apart by the hyperbolic depth distribution, not much floating point precision is required. It is thus safe to map these values to the vicinity of 1.0 where the floating point exponent is ‘locked’. Similar values near the far plane on the other hand are compressed to even closer clip space values and thus benefit from the extremely precise range around 0.0. Interestingly this results in the least precision in the middle area of the view space depth range.

## Linear depth (i.e W-Buffer)

As the name already suggests, the idea here is to write out the depth value itself, normalized to $[0, 1]$ range:

$z' = z_n + \frac{-z}{z_f-z_n}$

Unfortunately, without explicit hardware support, this method causes significant performance overhead as it requires depth export from pixel shaders.

## Asymptotic behaviour

For situations where extremely large view distances are required, one can let $z_f$ approach infinity. For standard depth we get

$\lim \limits_{z_f \to \infty} \begin{pmatrix}s_x & 0 & 0 & 0 \\ 0 & s_y & 0 & 0 \\ 0 & 0 & \frac{z_f}{z_n-z_f} & \frac{z_n z_f}{z_n-z_f} \\ 0 & 0 & -1 & 0\end{pmatrix} = \begin{pmatrix}s_x & 0 & 0 & 0 \\ 0 & s_y & 0 & 0 \\ 0 & 0 & -1 & -z_n \\ 0 & 0 & -1 & 0\end{pmatrix}$

and for reverse depth

$\lim \limits_{z_f \to \infty} \begin{pmatrix}s_x & 0 & 0 & 0 \\ 0 & s_y & 0 & 0 \\ 0 & 0 & -\frac{z_f}{z_n-z_f}-1& -\frac{z_n z_f}{z_n-z_f} \\ 0 & 0 & -1 & 0\end{pmatrix} = \begin{pmatrix}s_x & 0 & 0 & 0 \\ 0 & s_y & 0 & 0 \\ 0 & 0 & 0 & z_n \\ 0 & 0 & -1 & 0\end{pmatrix}$

Note how the matrices are suddenly free of approximate numerical computations, resulting in less rounding and truncation errors.

## Precision Analysis

With all these possibilities, which one will be the fit best for a given scenario? I try to answer this question by comparing depth resolution for each projection type. The idea is simple: View space depth is sampled in regular intervals between $z_n$ and $z_f$. Each sampled depth value is transformed into clip space and then into the selected buffer format. The next adjacent buffer value is then projected back into view space. This gives the minimum view space distance two objects need to be apart so they don’t map to the same buffer value – hence the minimum separation required to avoid z-fighting.

The following graph overlays depth resolution for the different projection methods. Click the legend on top of the graph to toggle individual curves. The slider on the bottom lets you restrict the displayed depth range. The zoom button resamples the graph for the current depth range. Use the reset button to reset the depth range.

 Near Plane Far Plane Buffer Type FloatInt24Int16

## Discussion

Results depend a lot on the buffer type. For floating point buffers, reverse depth clearly beats the other candidates: It has the lowest error rates and is impressively stable w.r.t. extremely close near planes. As the distance between the near and far plane increases $z_n-z_f$ starts to drop more and more mantissa bits of $z_n$, effectively making the projection converge gracefully to the reverse infinite far plane projection. On top of that, on the AMD GCN architecture floating point comes at the same cost as 24-bit integer depth.

With integer buffers, linear Z would be the method of choice if it wouldn’t entail the massive performance overhead. Reverse depth seems to perform slightly better than standard depth, especially towards the far plane. But both methods share the sensitivity to small near plane values.

## Reverse depth on OpenGL

In order to get proper reverse depth working on OpenGL one needs to work around OpenGL’s definition of $[-1,1]$ clip space. Ways to do so would either be via the extension arb_clip_control or a combination of gl_DepthRangedNV and a custom far clipping plane. The result should then be the same as reverse depth on DirectX. I included the Reversed OpenGL curve to visualise the depth resolution if clip space is kept at $[-1,1]$ and the regular window transform glDepthRange(0,1) is used to transform clip space values into buffer values.

# Raspberry Pi

So, I got myself a new gadget for christmas: A Raspberry Pi model B. For those of you who are not familiar: It’s basically a credit card sized computer with the computing power of a cell phone. Well, a somewhat slow cellphone to tell the truth. Not really the right device to do any fancy computing. One really cool thing though: the integrated BCM2835 chip has a built-in GPU with support for full HD video encoding/decoding and OpenGL 2.0 ES. And all at the power consumption of about 3.5 Watts. Perfect for a little, always on, media center to stream youtube videos and music or watch movies!

First thing, I loaded XBian, a Raspberry Pi optimized Linux distribution with XBMC preinstalled onto a memory card and booted up. Worked like a charm, out of the box you get a full media center solution with support for video playback and audio streaming and plugins that let you browse youtube and dailymotion. Sweet!

# IR control

Up to that point I had used my mouse as input and this was getting a bit tedious: A mouse to control the Raspberry, one remote to control the TV and another one to control the sound bar. Way too many devices with a two year old kid running around ;). So I decided to simplify the system. The Raspberry has eight general purpose input/output (GPIO) ports. They can quite easily be programmed and thus used to control all sorts of electronic circuits. At first I hooked up an IR receiver like shown in this Adafruit tutorial. Once I had configured LIRC this allowed me to control XBMC with any remote control. Next I built an IR sender circuit like described here. This allowed me to send IR signals as well. As a final step I configured my programmable remote to mimic some device unknown to TV and sound bar and used lircrc in combination with irsend to control both. Let me illustrate with an example: The volume up button on my remote sends a volume up command which only the Raspberry can understand. Based on the contents of lircrc, the Raspberry then sends the appropriate volume up command for the sound bar. Likewise, a channel up command will be translated to a command for the TV. This allowed me to get rid of two of the three input devices as everything can now be controlled with one remote only.

I should probably add that I struggled for quite a while to get this to work reliably. Sometimes the TV would not react, sometimes multiple button presses were sent etc. Finally it turned out that the issue was related to the low processing power of the CPU: Under heavy load, lircd would be interrupted by the OS quite often in order to run other tasks and thus mistimed the IR impulses. The issue went away once I increased the priority of the lircd daemon.

# More fun stuff

This project was so much fun that I started to to look into something else: What about supervising system and network stats? So I wrote a little python script that would grab internet transfer stats from my router, and temperature and free memory from the on-chip sensors in the Raspberry. The script would run every 5 minutes and log the results to a mysql database. I then installed the apache web server and made a little website that shows the data in some neat charts. Some weeks later I also hooked up a temperature and humidity sensor to one of the free GPIOs.

And as the last project (for now 🙂 ) I built a custom tracker for my cellphone: I configured my phone to send a HTTP POST request with the current location to my public IP address (which I set up via dyndns). A php script then extracts the location and stores it to a database. Another small webpage then displays the data via the google maps API.

And thatâ€™s it for now. Definitely a lot of fun and a nice departure from graphics programming. Note that Iâ€™ve left out a lot of the gory details, like the components in electronic circuits, or patching the lirc GPIO driver to fix some problems with IR inference from energy saving lamps. Donâ€™t hesitate to contact me in case youâ€™re interested and I can send you some more details.

# Gaussian Kernel Calculator

Did you ever wonder how some algorithm would perform with a slightly different Gaussian blur kernel? Well than this page might come in handy: just enter the desired standard deviation $\sigma$ and the kernel size $n$ (all units in pixels) and press the “Calculate Kernel” button. You’ll get the corresponding kernel weights for use in a one or two pass blur algorithm in two neat tables below.

Sigma   Kernel Size

## One dimensional Kernel

This kernel is useful for a two pass algorithm: First perform a horizontal blur with the weights below and then perform a vertical blur on the resulting image (or vice versa).

 0.06136 0.24477 0.38774 0.24477 0.06136

## Two dimensional Kernel

These weights below be used directly in a single pass blur algorithm: $n^2$ samples per pixel.

 0.003765 0.015019 0.023792 0.015019 0.003765 0.015019 0.059912 0.094907 0.059912 0.015019 0.023792 0.094907 0.150342 0.094907 0.023792 0.015019 0.059912 0.094907 0.059912 0.015019 0.003765 0.015019 0.023792 0.015019 0.003765

## Analysis & Implementation Details

Below you can find a plot of the continuous distribution function and the discrete kernel approximation. One thing to look out for are the tails of the distribution vs. kernel support: For the current configuration we have 1.24% of the curve’s area outside the discrete kernel. Note that the weights are renormalized such that the sum of all weights is one. Or in other words: the probability mass outside the discrete kernel is redistributed evenly to all pixels within the kernel.

The weights are calculated by numerical integration of the continuous gaussian distribution over each discrete kernel tap. Take a look at the java script source in case you are interested.