Accelerating GI computations.

So I have been developing a new game where a rocket engine Globally Illuminates its environment. It started out as an AVX2 implementation, but since then I have been pursuing other acceleration techniques. For instance, can I run the photon mapping algorithm on the GPU instead? Here are some initial results of the different approaches.

Technology: AVX2, single threaded.
OS: Linux
Device: i5-4570 CPU @ 3.20GHz.
Cores: 1
Frames per second: 51

Technology: GLSL- OpenGL3.2
OS: Linux
Device: Intel® HD Graphics 4600 GPU
Cores: ?
Frames per second: 37

Technology: GLSL- OpenGL3.2
OS: Linux
Device: ATI HD 5670 Graphics, Open Source Gallium driver.
Cores: ?
Frames per second: 60

Technology: OpenCL 1.2
OS: Linux
Device: i5-4570 CPU @ 3.20GHz.
Cores: 4
Frames per second: 38

Technology: GLSL - OpenGLES 3.0
OS: Android
Device: Adreno(TM) 420
Cores: ?
Frames per second: 10-14.
Remarks: Oscillates with a 3.5s period. Thermal throttle?

Technology: OpenCL 1.2
OS: Mac OSX
Device: i5-4278U CPU @ 2.60GHz.
Cores: 4
Frames per second: 11
Remarks: Could not handle work group sizes larger than 1.

Technology: OpenCL 1.2
OS: Mac OSX
Device: Intel Iris GPU
Cores: 40
Frames per second:-
Remarks: Apple's OpenCL compiler failed to build the OpenCL kernel source. Gave 'Parse Error' on a perfectly fine source fragment for no traceable reason.

Some conclusions I got from this: OpenCL has not been worth the effort. It takes 4 CPU cores to get to a speed that still lies significantly below the speed of my hand optimized AVX2 implementation that runs on a single core.

Apple's OpenCL seems to be in a bad shape. I could not get it to run on GPU, and running on CPU yielded a 3.5 times slower result compared to Linux.

The GLSL implementation seems promising. A dependency on ES3.1 or OpenGL 3.2 is less of a barrier than the AVX2 dependency. With some temporal caching, and reducing photon counts, it should be able to reach solid 60fps on integrated GPUs, and maybe even 60fps on future mobile CPUs.

Programming

Programming is my passion. It is the best life-time hobby I can imagine. It all got sparked in 1982 when I played Munchkin on a friend's Videopac G7000. This pacman clone blew me away, and I desperately wanted a 'game computer'. My father replied to my plea: `No we are not going to buy a game computer. We'll buy a real computer.' To which I replied: `What is a real computer?' The answer hit like a bomb: `With a real computer you can make your own games.' The rest, as the saying goes, is history. Here's an overview of the programming languages in my life in rough chronological order.

• It all started with ZX Spectrum Basic.
• Then Z80 machine language (Assembler came later!)
• Forth, using White Lightning from Oasis Software required a mental shift due to the RPN.
• Intel 8086 assembly.

Most of the programming languages I picked up were studied as part of my Computer Science degree at the University of Amsterdam:

• Pascal
• Motorola 68K assembly
• Microcode
• Scheme
• Sasl
• Fortran
• Prolog
• C
• Occam

And then in mostly in industry, I picked up:

• Postscript (stack based like Forth)
• C++
• Python
• Objective C

Currently, my favourites are C (I use a C++ compiler but try to use as little C++ features as possible) and Python.

Extraterrestrial spelæology

So my Global Illumination experiment made some more progress. The technology demo is slowly evolving into an actual game. And the hero of this game might very well be a spelunking rocket. Maybe I should call the game Spelunking Rocket? It currently has a single Google hit, so it should be easy to find online.

So what you see in the video is a rocket flying through a voxel world that is defined by a 3-octave simplex noise function. I sample one noise field to determine block/empty space, and sample another noise field to determine the hue. Notice how the rocket exhaust illuminates the scenery, both directly and indirectly via light bouncing off a wall. Also, the exhaust particles collide with the world, and act as light sources for my photon mapper.

In the left corner an instrument that combines attitude-indication (where is the rocket's nose pointing?) with a compass. Flying towards the little circle on the perimeter will make you go in the +X direction, where the first coordinate increases. The attitude indicator helps you to right the rocket, although there is also an autopilot function mapped on the gamepad that does this automatically using PID controllers.

Still to do are game play objectives. I was considering putting fuel drops in the world, and make them more rare as you move further away from launch position. Farthest voyage wins the leader board?

For technical challenges, there is still the issue of moving away from AVX2 which is not widely supported on current hardware. A possibility would be doing GPGPU. Possible APIs are OpenCL, OpenGL4.3 Compute Shaders, CUDA, Apple Metal. CUDA is too proprietary, as is Metal. OpenGL4.3 support is horrible: I don't think a single Macintosh can do this?

Rocket Engine Illumination

So I have been playing with my real time Global Illumination renderer some more. I added a particle system to model a rocket engine. The particle system is comprised of 1024 particles. And the kicker is: each and every particle is a light source that casts both direct and indirect light. For each particle, 24 photons are fired in random directions. When a photon hits a surface, a secondary photon is emitted in a diffusely reflected direction. This bounced photon creates the indirect illumination. See for instance the red and green glows that are created if the engine is close to a coloured wall.

In the video, the best demonstration of indirect light happens as very short flashes of green and red on the sides of the center block. If the engine flame is directly above the center block, its light cannot directly reach the sides. So mainly the light bouncing off the coloured walls reaches the sides, causing them to briefly flash in green or red before going bright white as the engine light shines directly upon it.

It currently runs 60fps on a single Haswell core. But I plan on multi threading the code so that I can increase the photon count. This should reduce the light flicker. The code is in AVX2 intrinsics, so it's rather incompatible with most PCs. I may have to port it to AVX or SSE at some point in time.

Next up in my GI research is integration into an actual game, preferably with rockets of course. I feel like making a GI homage to the ZX Spectrum classic JetPac.

Moving lights

So my Global Illumination Voxel Engine Research is making progress. I've added colour, indirect lighting, and also SIMD intersection tests. The SIMD is AVX 8-wide. And the speed up compared to scalar code is 4.5x which leads me to believe there is some room left in optimizing it. It now runs 38fps on a single 3.2GHz Haswell core.

Notice the low-frequency noise. Photon Mappers typically have high frequency noise, and path tracers that update only some of the screen's pixels have even higher frequency noise. The noise in my renderer is much more pleasant, and reminds me more of oscillating electrical lighting, or maybe the flickering of a fireplace flame.

2014 totals

So, The Little Crane That Could is still chugging along, but undeniably it has peaked. I hope there is life left in the brave little crane, but it may be running out of steam. Here are the 2014 results (Number of free Downloads.)

	2014	2013	2012	2011
iOS	1300K	3199K	3454K	1550K
Android	825K	1579K	1656K	-
Mac	30K	53K	81K	-
OUYA	4K	15K	-	-
Kindle	46K	95K	-	-
Rasp Pi	?	6K	-	-

I have been unable to check the Raspberry Pi downloads. The statistics report on the raspberry store is broken. It looks like the pi store was part of indiecity, which is part of Blitz Games, which seems to have gone under. I'm not sure if the download is still available on the store.

This brings the grand total of Little Crane downloads to 13.9 Million. Hooray for Little Crane! One last note: Little Crane is also available for GNU/Linux and Windows, but those releases saw downloads in homeopatic doses.

More Photon Mapping

In yesterday's post, I introduced my new hobby project Photon Mapping Voxels. Today, I made some more progress, and managed to properly interpolate the shading. The voxel faces in a plane now share vertices. But there is still a matter of ambiguity when shading a quad, which causes the triangle seam to show in the middle of the quad. To alleviate this issue, I added a center vertex in the middle of the quad, and render it as 4 triangles, instead of just 2. The results are below. The animated gif cycles through four renderings: quads, triangles, triangles in wireframe, quads in wireframe. As you can see, there are less discontinuities in the triangle version, at the cost of more vertices, and double the triangles.

Again, this is direct light only. I am getting excited about seeing it with indirect light (bounces) and also colour. Currently, all photons and all voxels are white. Also on the todo list: make it really fast by doing SIMD intersection tests: a ray versus 8 voxels in a single go. This requires AVX though, probably AVX2 even.