Light Propagation Volumes

Posted on July 18, 2010 by BlackHC

I’ve finally finished my lab course last week – thanks to my supervisor Matthäus G. Chajdas – you can read his blog here -, it wasn’t your usual lab course with work sheets and boring homework, instead I’ve been allowed to implement a nice paper about a Global Illumination approximation algorithm called (Cascaded) Light Propagation Volumes. It’s been developed by Crytek and you can find more information (including some presentations and videos) on their server. (Note: this is an implementation of the I3D paper, not the earlier SIGGRAPH one.)

Sponza scene (direct + indirect lighting w/ occlusion)

Sponza scene (only indirect lighting w/ occlusion)

Sponza scene (ony direct lighting)

Sponza scene (boosted indirect lighting w/ occlusion)

Sponza scene (boosted indirect lighting w/o occlusion)

The algorithm approximates global illumination by rendering the light into a reflective shadow map, injecting it into a volume (using a spherical harmonics representation) and propagates the light flux in this volume (hence the name of the algorithm) and taking into account occlusion as possible extension.

The whole algorithm is physically motivated but corners everywhere, of course, to be more efficient. The paper also contains a few errors and doesn’t explain everything needed to implement it in great detail (like eg the solid angles of the side faces), so I’ve written two documents detailing the mistakes I’ve found and the additional calculations I’ve performed.

You can find the mistakes here (including suggested corrections) and the full annotations document here.

Finally I’ve also uploaded the whole prototype (including my code licensed under the FreeBSD license and the media files) here – it’s 68 MB big (and it’s been compressed with 7zip with a compression mode that might not be supported by WinZIP. The Sponza model is from Crytek, too. You can download the original model and textures here.
The project uses DirectX 10.1 and by default it won’t run in DirectX 10, because it uses a texture format that is deprecated in D3D10 but supported again 10.1 (BGRA). See the comment by FatGarfield for the location that needs to be changed for it work in DX10, too. (However red and blue will be swapped then.)

I haven’t implemented cascaded LPVs and I also use only one light/RSM and only inject its depth into the occlusion volume, but the results already look very nice in my opinion.

Stay tuned for more :-)
Cheers,
Andreas

Posted in Coding, Game Projects, Maths, University | Tagged , , , , , , , | 5 Comments

Panorama Stitching

Posted on July 17, 2010 by BlackHC

I’ve finally come around to “clean-up” some old project I’ve had lying around for a few months and upload it.
I’m talking about some Panorama Stitching code I wrote for our participation in Microsoft’s Imagine Cup.
I’m suppressing all memories of it since it was an epic fail, but at least I still have learnt quite a bit about computer vision and image processing – enough to know that it’s incredibly hard to come up with stable algorithms and kudos to anyone working in the field.

Here is the code dump: PanoramaStitching.zip

It contains many small projects which usually use multiple pictures as inputs or multiple webcams (depending on code or chosen preprocessor macros).

The most advanced prototype is the SnapshotHomographyConfigurator, which allows you to determine homographies between multiple cameras at once by marking shared points between the images.

Another one which works okay is the PanoramaStitching project. It creates panoramas using spherical or cylindircal projections of the input images. However, it is very sensitive to translations of the viewpoint. It works quite well with optimal/artificial images:

(Note: the small misalignment on the right stems from moving the player position slightly. Usually you use a deghosting algorithm to remove such misalignments.)

I’ve used OpenCV for image processing and yaml for loading and storing settings (and also rapidxml). OpenCV’s C++ wrapper is pretty awesome. It’s not perfect but it makes life a lot easier.

Stay tuned for more code/project uploads soon :-)

PS: Here are the links to some papers which proved useful to me (I didn’t implement most of them though, and some are implemented in OpenCV already):

Posted in Coding, Personal Rantings, University | Leave a comment

Rotation of Low Order Spherical Harmonics

Posted on June 20, 2010 by BlackHC

I’m currently working at university on implementing Light Propagation Volumes. The paper makes extensive use of spherical harmonics while the implementation uses the first two bands.

Below is a visualization of the first 4 bands of the SH basis functions (created using Mayavi):

sh0to3

The first 4 bands of the spherical harmonic basis functions

As you can see the first two bands are 4 functions, so 4 coefficients to store which conveniently fits into one RGBA texture.

One of the main transformations that is performed in the LPV paper is the rotation of the spherical harmonics representation of a clamped cosine lobe (that represents surface lighting) onto a normal vector direction.  It took me a while to figure out, but actually it’s quite easy, which is why I write about it :-)

The analytical presentation of the first four base functions is simple:

S_0 \left( x, y, z \right ) = \frac{1}{2 \sqrt{\pi}}
S_1 \left( x, y, z \right ) = - \frac{\sqrt{3}}{2 \sqrt{\pi}} y
S_2 \left( x, y, z \right ) = \frac{\sqrt{3}}{2 \sqrt{\pi}} z
S_3 \left( x, y, z \right ) = - \frac{\sqrt{3}}{2 \sqrt{\pi}} x

To evaluate lighting with SH for some direction v, you first determine the coefficients/weights of the SH basis functions and then sum them up.

L = \sum_i s_i \, S_i \left( v \right )

Let’s assume we know the coefficients s^z_0, s^z_1, ... of the clamped cosine lobe around the z axis, then we can determine the lighting in direction v for the cosine lobe around the normal n by transforming it into the space where the normal coincides with the z axis (ie rotate n onto the z axis):

L = \sum_i s^z_i \, S_i \left( R_{n \to z} \, v \right )

where R_{n \to z} is a rotation matrix that rotates n onto z.

The idea is to expand S_i \left( R_{n \to z} \, v \right ) and rewrite it in terms of S_i \left ( v \right ) .

Before doing this, let’s first take a look at the coefficients of the clamped cosine lobe:

\begin{align*}<br /> s^z_0 &=\frac{ \sqrt{ \pi } }{ 2 }<br /> s^z_1 &= 0<br /> s^z_2 &= \sqrt\frac{ \pi }{3}<br /> s^z_3 &= 0<br /> \end{align*}

The y and x direction are 0 because the cosine lobe is centered isotropic around the z axis:

So let’s look at the expanded version of this formula if r_1^T , r_2^T , r_3^T are the row vectors of the matrix,
v=\bigl(\begin{smallmatrix}<br /> x\\<br /> y\\<br /> z<br /> \end{smallmatrix}\bigr) and R_{n \to z}=\left(\begin{smallmatrix}<br /> r_1^T\\<br /> r_2^T\\<br /> r_3^T<br /> \end{smallmatrix}\right ) , then:

L = \sum_i s^z_i \, S_i \left( R_{n \to z} \, v \right ) = \sum_i s^z_i \, S_i \left( \left(\begin{smallmatrix}<br /> r_1^T \, v\\<br /> r_2^T \, v\\<br /> r_3^T \, v\end{smallmatrix}\right ) \right )
\begin{align*} L &= s^z_0 \, c_0\\<br /> &+ s^z_1 \, (-c_1) \, r_2^T \, v \\<br /> &+ s^z_2 \, c_1 \, r_3^T \, v\\<br /> &+ s^z_3 \, (-c_1) \, r_1^T \, v<br /> \end{align*}

Since s^z_1 = 0 and s^z_3 = 0 :

L = s^z_0 \, c_0 + s^z_2 \, c_1 \, r_3^T \, v = s^z_0 \, c_0 + s^z_2 \, c_1 \, r_{31} \, x + s^z_2 \, c_1 \, r_{32} \, y + s^z_2 \, c_1 \, r_{33} \, z

L = s^z_0 \, S_0 \left ( v \right ) - s^z_2 \, r_{32} \, S_1 \left ( v \right )+ s^z_2 \, r_{33} \, S_2 \left ( v \right ) - s^z_2 \, r_{31} \, S_3 \left ( v \right )

Now the question is: what is the third row of R_{n \to z} ? If we look at the inverse matrix instead: R_{z \to n} , we can immediately see that its third column has to be n, because R_{n \to z} \, \bigl(\begin{smallmatrix}<br /> 0\\<br /> 0\\<br /> 1<br /> \end{smallmatrix}\bigr) = n by construction. Since rotations are orthogonal matrices, the inverse is the same as the transposed, so we can deduce that the third row of R_{n \to z} is the same as the third column of R_{z \to n} ,  that is: n. Thus with n = \bigl(\begin{smallmatrix}<br /> n_x\\<br /> n_y\\<br /> n_z<br /> \end{smallmatrix}\bigr) we get:

L = s^z_0 \, S_0 \left ( v \right ) - s^z_2 \, n_y \, S_1 \left ( v \right )+ s^z_2 \, n_z \, S_2 \left ( v \right ) - s^z_2 \, n_x \, S_3 \left ( v \right )

So the SH coefficients of the clamped cosine lobe along n are:

<br /> s^n_0 = s^z_0 = \frac{ \sqrt{ \pi } }{ 2 } \\<br /> s^n_1 = - s^z_2 \, n_y =  -\sqrt{ \frac{ \pi }{3} } \, n_y \\<br /> s^n_2 = s^z_2 \, n_z = \sqrt{\frac{ \pi }{3} } \, n_z \\<br /> s^n_1 = - s^z_2 \, n_x = - \sqrt{\frac{ \pi }{3}} \, n_x<br />

This is it :-)

Cheers,
Andreas

PS: a few screenshots from the LPV project:

GPUPropCopy 0616
noLPVLPV32P128C

noLPV_2LPV32P128C_2

Posted in Coding, Games, Maths | Tagged , , , | Leave a comment

Rigid Body Motion

Posted on May 30, 2010 by BlackHC

Last week I had to give a presentation about Rigid Body Motion (ie the basics of rigid body physics and some general mechanics).

Here are two versions of my presentatio (one with less text and one with more):

Rigid Body Motion Presentation as PPTX; Rigid Body Motion Presentation as PDF
Rigid Body Motion Full Version as PPTM; Rigid Body Motion Full Version as PDF

If you are truly interested in learning about rigid body physics, here are some books/links:

Cheers,
Andreas

Posted in Maths, Uncategorized, University | Tagged , , , , , | 2 Comments

PowerPoint LaTeX

Posted on May 30, 2010 by BlackHC

Hey everybody :-)
I only wanted to point out that I’ve uploaded a new and improved version of PowerPoint LaTeX at http://code.google.com/p/powerpointtools/ – it now supports MiKTeX \o/

I’ve also finally added a project page for it to this blog.
More updates might follow soon if I find enough spare time :-)
Cheers,
Andreas

Posted in Uncategorized | Tagged , , , , , | Leave a comment

A quick note on quantifiers: For almost all and there exist infinitely many

Posted on March 27, 2010 by BlackHC

It’s been a while since my last post and now it’s time for a mathematical post:

I’m currently preparing for a math exam (calculus) and I’m thinking it would be nice if there was a way to avoid much of the “for every \epsilon > 0 there is an N \in \mathbb{N}, so that for all n \ge N some property … holds” stuff you find in textbooks. Some textbooks actually shorten it to “for every \epsilon > 0 some property … holds for almost all n“.
However, I haven’t found a quantifier to express this anywhere yet, so I’m proposing to introduce a new one:

\tilde{\forall} x \in M: P(x) should mean “for almost all x \in M P(x) holds”, which suggests that there are only finitely many elements for which it does not hold.
One can formalize this as:
\tilde{\forall} x \in M: P(x) \equiv \exists n \in \mathbb{N}: \left | \left \{ x \in M \mid \neg P(x) \right \} \right | \le n

Of course, a new existential quantifier is required then, too (for negation):
\tilde{\exists} x \in M: P(x) stands for “there exist infinitely many x \in M, for which P(x) holds”.
And this can be formalized as:
\tilde{\exists} x \in M: P(x) \equiv \forall n \in \mathbb{N}: \left | \left \{ x \in M \mid P(x) \right \} \right | > n

It’s easy to see that \neg \left ( \tilde{\forall} x \in M: P(x) \right ) \equiv \tilde{\exists} x \in M: \neg P(x)

Thus one can use the two quantifiers just as one would use \forall and \exists usually. Note however than \forall and \tilde{\forall} don’t interchange and neither do \exists and \tilde{\exists}.

One last note: it might be worth using a different notation, for example: \exists ^ \infty might be easier to understand than \tilde{\exists} , and \forall ^ \approx might be better than \tilde{\forall}.

I’ll try to formalize these quantifiers some more when I find some spare time.

Stay tuned for coding related updates soon :-)
Cheers,
Andreas

Posted in Maths, University | Tagged , , , , | Leave a comment

Random Things

Posted on November 27, 2009 by BlackHC

It’s been a while since the last update. Here’s a small update on what I’m thinking about various stuff.

Prototype

Gameplay is okay I guess. Nothing I would spent too much time on though. It looks a lot worse than GTA 4 though (same as Crackdown).

Resident Evil

Seems to be lots of fun and some nice graphics, too.

Red Faction: Guerrilla

Some weird texture filtering issues and the presentation doesn’t knock off my chair (terrain popping and other ugliness), but multiplayer is loads of fun with friends. Physics isn’t completely stable though. I played the game for one hour in MP with friends and there were quite a few cases where geometry dropped through the floor with enough pressure from above (after destroying a building).

Brüno

A bad and quite stupid movie (Ali G in Da House is probably the only movie I kinda like that stars Cohen). If you haven’t watched it already, don’t >_<

Shadow Complex

I bought shadow complex a few weeks ago and I have to say that it is an awesome game. I read somewhere that the developer used the Metroid series as inspiration and it shows. It’s really fun to play and quite addictive. The graphics are pretty awesome (it is using the Unreal 3 engine) and the whole presentation is pretty polished. It certainly is worth its 1200 gamerpoints

Summing Formulas

A month ago I was doing some exercises in an analysis book (Königsberger) and found a nice/interesting problem:

Prove that if we denote of the sum of the numbers 1 to n to the p-th power by S_n^p = 1^p + 2^p + ... + n^p , then the following equation by Pascal holds: (p+1) S_n^p + \binom{ p + 1 }{ 2 } S_n^{p-1} + \binom{ p + 1 }{ 3 } S_n^{p-2} + ... + S_n^0 = (n+1)^{p+1} - 1

It can be used to get recursively/iteratively get formulas for sums of higher powers of numbers.

This is interesting because the proof doesn’t need any advanced maths (like eg the Euler-MacLaurin formula, which can be used to show this, too).

You can download the proof and a few examples here.

Cheers

Posted in Maths, Personal Rantings | Leave a comment

Extracting Information from StudiVZ

Posted on October 19, 2009 by BlackHC

Some time ago somebody stole 1 million data records from StudiVZ, the German Facebook clone. I’m not exactly sure why people call the person a hacker who stole data, because it appears he simply wrote a tool that harvested the publicly available data from StudiVZ (which everyone with an account can view).

People on StudiVZ share all their data by default—contrary to Facebook which values a person’s private data a lot more. Thus by simply opening each profile from a dummy user and processing the HTML data from StudiVZ one can extract a lot and some more information from random people who probably don’t even know about it or don’t care.. so I’m not sure about the stealing part.

Apparently there are some captcha’s when you start browsing searches beyond a few pages. I guess that is where the hacking part comes in, because getting around a captcha probably constitutes hacking—maybe?

Anyway I think part of the media coverage is a bit ridiculous because anyone can write a simple harvester in an hour or two. It took me one and half hours, so I think I’m on the safe side with this estimate and I didn’t really have a clue about this stuff before either.

Since I don’t want to “hack”, I’ve only written a very tame harvester. It connects to your personal StudiVZ account, and retrieves the name and profile ID (and thus profile URL) of all your friends in the “Meine Freunde” pages.

It could do a lot more with that like retrieving everybody’s birthday or random pictures, but I’m too lazy to code that because you use the same pattern for extracting data over and over again and it stops being interesting quite fast.

You can download the project here. It is a one file C# project. I’m releasing it under GPL (whatever).

It’s really easy to explain how it works:

  • It uses System.Net‘s HttpWebRequest and HttpWebResponse to get (and post) web pages.
  • StudiVZ (like every other portal) uses cookies, so I create a CookieContainer and use it in every http request.
  • There are a few hidden values that StudiVZ expects during login. I’m retrieving them from the main page using custom built regular expressions. I’ve found a handy AJAX tester for .NET regular expressions. It was really useful for building the expressions and debugging them. (BTW you can find all URLs I used in the comments.)
  • After login I use the same pattern: get page & parse using regex for everything.
  • Visual Studio has an awesome “HTML Visualizer” for strings. It displays the content of a string as HTML page, which is really nifty if you’re doing anything related to HTML processing.

The code is quite ugly. Well, it’s not production code and this is only meant as a proof of concept.

Also note that I have at most violated the AGB of StudiVZ and not committed any criminal acts and I’m not planning to sell my friend’s profile IDs or data either :-)

Maybe someone can extend the code and make it more useful. I guess it would be fun to automatically download all your pictures (including tags) and feed them into flickr or picasa… but someone else can do that.

Cheers,
Andreas

Posted in Coding, Personal Rantings, University, Web | Tagged , , | 1 Comment

My Bachelor Thesis

Posted on October 17, 2009 by BlackHC
Screenshot of Utah

Screenshot of Utah

For the last two months I have been working on my bachelor thesis at the Chair of Computer Graphics and Visualization. It is about “Multi-Tile Terrain Rendering with OGL/Equalizer”´.
The chair has a very nice Direct3D 10 terrain rendering engine and they want to run it at the newly founded KAUST (King Abdullah University of Science and Technology´) in a massive CAVE environment. A CAVE is a room whose walls are actually screens.
The CAVE at KAUST even supports stereoscopic rendering. Thus in total 12 views can be rendered to.

My job was to port said terrain engine from Direct3D to OpenGL and afterwards to the Equalizer framework, which is an open-source framework for parallelizing OpenGL applications.

You can find/download an online version of my bachelor thesis here. I’ll upload the LaTeX at a later date and update this post.

I’ve spent the last months writing about all this, so I don’t feel like talking about the thesis itself anymore. Instead the remainder of this post will contain a post-mortem of it.
Continue reading →

Posted in Personal Rantings, University | Tagged , , , , , , | Leave a comment

Sploidz Revisited (Unofficially)

Posted on August 23, 2009 by BlackHC

I’ve already written about the semi-conductor project and how I’ve written some Flash animations/applications for it. Of course, I’m more interested in making fun stuff´, so I decided to put my knowledge to good use and write a small game to see how difficult/awkward Flash actually is.

To sum it up, it is somewhat awkward, at least if you use the IDE itself. FlashDevelop still is as nice as ever, but you can quickly develop games nonetheless. I prefer Torque Game Builder though in retrospect.

Before I continue talking about the development itself, let’s take a look at the actual game. Sploidz was the first game I wrote using Torque Game Builder for Joshua Dallman, and since I still had all the assets in my subversion repository, it was an easy decision to try and port this game. If you want to play it, you can download it for free here.
I haven’t ported everything: I’ve just rewritten the main characteristic features that make up Sploidz’s code in ActionScript.

Without further ado´ here is the game:

Click to open Sploidz in its own window

Because the art is still copyrighted and I haven’t heard back from Joshua yet ´, I decided to create a free version that only uses “coder art” – in this hand-drawn coder art :-)

Some´ have said that this version looks cuter, decide for yourself:

Click to open SploidzCC in its own window

Below you’ll find a description of the development and at least one helpful trick and most importantly a link to the source code of the “copyright-free” version.

Because the orginal version is way too difficult to be really fun, I actually sat down one more time and added code to make the platform slower if you’re in danger of losing (up to 3 times slower):

Click to open SploidzMoreFun in its own window

Continue reading →

Posted in Coding, Game Projects, Games, Red Thumb Games | Tagged , , , , , | 1 Comment