# Parallelizing Algorithms with Intel TBB and C++ Lambdas
Fri
27
Aug 2010
My demo for RiverWash is practically finished. I still could polish it or even make some big changes, because I know it's not great, but that's another story. What I want to write about today is how easily an algorithm can be changed to run in parallel on multicore processors when you use Intel Threading Building Blocks and C++ lambdas.
First, here is an algorithm. In one of my graphic effects I fill a 256x512 texture on CPU every frame. For each pixel I calculate a color based on some input data, which are constant during this operation. So the code looks like this:
void SaveToTexture(const D3DLOCKED_RECT &lockedRect)
{
uint x, y;
char *rowPtr = (char*)lockedRect.pBits;
for (y = 0; y < TEXTURE_SIZEY; ++y)
{
XMCOLOR *pixelPtr = (XMCOLOR*)rowPtr;
for (x = 0; x < TEXTURE_SIZEX; ++x)
{
*pixelPtr = CalcColorForPixel(x, y);
++pixelPtr;
}
rowPtr += lockedRect.Pitch;
}
}
How to parallelize such loop? First, some theoretical background. Intel TBB is a free C++ library for high-level parallel programming. It has nice interface that makes extensive use of C++ language features but is very clean and simple. It provides many useful classes, from different kinds of mutexes and atomic operations, through thread-safe, scalable containers and memory allocators, till sophisticated task scheduler. But for my problem it was sufficient to use simple parallel_for function that utilizes the task scheduler internally. To start using TBB, I've just had to download and unpack this library, add appropriate paths as Include and Library directories in my Visual C++ and add this code:
#include <tbb/tbb.h>
#ifdef _DEBUG
#pragma comment(lib, "tbb_debug.lib")
#else
#pragma comment(lib, "tbb.lib")
#endif
Second topic I want to cover here are lambdas - new, great language feature from C++0x standard, available since Visual C++ 2010. Lambdas are simply unnamed functions defined inline inside some code. What's so great about them is they can capture the context of the caller. Selected variables can be passed by value or by reference, as well as this pointer or even "everything". It makes them ideal replacement for ugly functors that had to be used in C++ before.
Summing it all together, parallelized version of my algorithm is not much more complicated than the serial version:
void SaveToTexture(const D3DLOCKED_RECT &lockedRect)
{
tbb::parallel_for(
tbb::blocked_range<uint>(0, TEXTURE_SIZEY),
[this, &lockedRect](const tbb::blocked_range<uint> &range)
{
uint x, y;
char *rowPtr = (char*)lockedRect.pBits + lockedRect.Pitch * range.begin();
for (y = range.begin(); y != range.end(); ++y)
{
XMCOLOR *pixelPtr = (XMCOLOR*)rowPtr;
for (x = 0; x < TEXTURE_SIZEX; ++x)
{
*pixelPtr = CalcColorForPixel(x, y);
++pixelPtr;
}
rowPtr += lockedRect.Pitch;
}
} );
}
This simple change made all my 4 CPU cores busy for 90+% and gave almost 4x speedup in terms of frame time, which is good result. So as you can see, coding parallel applications is not necessarily difficult :)
Comments | #libraries #rendering #c++ Share
# Another 3 Events
Sun
22
Aug 2010
I've recently wrote about this year's SIGGRAPH (scientific conference about computer graphics) and Assembly (demoscene party). Another 3 interesting events took place recently, so it's worth looking for information about what have been shown there.
1. QuakeCon (August 12-15, 2010, Dallas, USA). It's a huge LAN party dedicated to id Software games, but they also show some new stuff there. This year it looks like the highligh was Rage, including iPhone version presented by John Carmack himself.
2. GDC Europe (August 16-18, 2010, Cologne, Germany). It's European kind of Game Developers conference. List of all sessions can be found here. There were not many sessions about programming, comparing to other categories and I can't find any slides shared online. I wish Ke-Sen Huang gathered links to materials from GDC just like he does with purely scientific conferences...
3. GamesCom (August 18-22, Cologne, Germany). This one just about PC and console games. Many information and trailers of upcoming games have been shown. Good summary can be found at Polygamia [pl].
Comments | #events #games Share
# Demo for RiverWash 2010
Fri
20
Aug 2010
I code a demo for RiverWash 2010 demoscene party. I had a lot of doubt on this, but the more is done, the more I feel convinced I'm going to show it on the party, despite I know it's not of the highest quality, both because no super-advanced technology is involved and because I made all the graphics myself :) It will be my first demo made for such competition. All in all I'm more from Warsztat than demoscene community. Still I like the scenish atmosphere and after each big party, like Assembly or Breakpoint, I download and watch the productions. I've also been at the RiverWash last year and I had a lot of fun there.
I probably shouldn't show my demo before the party, so I'll do something inspired by what my former employers did on the website of their new game development studio - 11 bit studios - I'll show only small parts of some screenshots :)
Comments | #rendering #events #demoscene #productions Share
# Assembly 2010 Prods - My Impressions
Thu
12
Aug 2010
I've already mentioned that Assembly 2010 demoparty took place recenly. Now let me share with you my impressions about the productions from this party.
Gamedev category, with 19 productions this year, is bigger than demo, intro 4k or intro 64k, which was suprising for me. I've always thought demoscene is about making demos and that they don't like making games so much. But I'm not impressed by these games. Most of them have neither interesting gameplay like indie game developers do nor advanced graphics technology like demosceners put into their demos. Still games from higher places are much better than the other and the game from the first place - Tricky Truck by Archee (which is a driving simulation with physics where you have to park a truck) paid my attention for quite a long time.
About executable music, my favourites are actually the tunes from the bottom of the results - Pure Life 2.0 by Silent (place 7/9) and My Happy Place by Prophecy (place 8/9). But this surely is the matter of taste. I can see that voters prefered more retro-oldschool-style productions.
When it comes to "real wild" category, aggregating demos for exotic platforms, several web-based were presented. My favourite ones are Ballmer Peak by Department of Offense (place 4/7) and Spiral out by evoflash (place 1/7). I didn't know such amazing and even 3D graphics could be done in Flash.
About intros, for the first time I've seen a 4k intro where EXE unpacks itself to a temporary directory as HTML + SWF and then opens the actual Flash demo in the web browser. Atleeti by Archee is definitely a phenomenon. An intro with not good graphics or music, which scored 2nd place probably just because they've appreciate that it's very original piece of technology. Its idea is similar to Darwinism, which scored 1st at Breakpoint 2010. The 4k intro from the 1st place - Neanderstaller by Pittsburgh Stallers - looks great. It's definitely worth watching more than any other.
As for 64k intros, I liked them all. About demos, I recommend watching first 6 places. The demo from 2nd place - Ceasefire (all fall down..) by CNCD vs Fairlight - is the continuation of the famous Agenda Circling Forth (1st place at Breakpoint 2010). For me they are great examples showing that there is not good graphics VERSUS "real" artistic value, but the advanced technology and high computational power may well serve art by making it possible to do something stylish like this, where all the graphics is made of dots (particles). Details of this technology can be found on direct to video blog. The demo that scored 1st place - Happiness is around the bend by ASD - is especially worth seeing. It's long, beautiful, original, well designed - definitely something new or at least something of the highest quality that can be found on the demoscene nowadays.
Comments | #demoscene #events Share
# Assembly 2010
Sun
08
Aug 2010
Another interesting event took is taking place on August 5-8th, 2010. I'm talking about Assembly demoparty in Helsinki, Finland. It's one of the biggest demoscene parties and so we can expect new, highest quality productions to be presented on competitions there, like PC demos, 4k intros and 64k intros.
The list of productions can already be found on Assembly 2010 party page at Pouet.net, where you can download separate files. To download all the content, you can log on to anonymous FTP at ftp.scene.org/pub/parties/2010/assembly10.
After party page on Assembly website is not complete yet, but I'm already downloading the entries. Competition results are here. Watching demoscene production is always very inspiring for me, although I know that making something of such quality requires much higher skill than I have and collaboration of many programmers and artists.
Comments | #demoscene #events Share
# SIGGRAPH 2010
Mon
02
Aug 2010
On July 25-29th the 37th SIGGRAPH 2010 conference took place, subtitled "The People Behind the Pixels" this year. As always, many interesting papers were presented, varying from purely scientific, not-so-practical and working with SIGGRAPH-Interative-Frame-Rate (TM) :) through advances in movies and photography technology till what's most interesting for me - the real-time, hardware-accelerated graphics rendering related to game development. Now, after the event, many papers and slides are available for free to download. If you are interested, here are some links:
There is also a very active #siggraph hashtag on Twitter.
Comments | #rendering #events Share
# How to Equally Blend Multiple Images in GIMP
Sun
01
Aug 2010
During my today's walk on Warsaw I took many different photos. Some of them were series of photos of a road from exactly same place, with a purpose of merging them together into a single photo. My idea was to just average the color of each pixel, so it should be like:
out = 1/4 * (img[0] + img[1] + img[2] + img[3])
But how to do this in GIMP? There is no such filter AFAIK. An obvious solution is to use blending - Mode and Opacity settings for layers - but it turns out to be not so simple. Each layer blends with a merged image from beneath it, so instead of average formula above we have to refer to a formula for blending (linear interpolation), which is:
out[i] = t[i] * img[i] + (1-t[i]) * out[i+1]
Where:
i is a layer index 0..(n-1), indexed from the topmost layer,
t[i] is Opacity parameter for layer i.
After expanding it for 4 layers, the formula becomes:
out =
t[0] * img0 + (1-t[0]) * (
t[1] * img1 + (1-t[1]) * (
t[2] * img2 + (1-t[2]) * (
t[3] * img3 + (1-t[3]) * 0
)
)
)
Finally, after doing some math with pen and paper, I calculated that to equally blend (average) n images in GIMP, you should:
For example, I have 5 photos so I give them Opacity: 20, 25, 33, 50, 100. Here is the result: an image that could be called "Road of Ghosts" :)
By the way, I've found a website where panorama photos can be uploaded for free and interactively viewed using just Flash. Here is my profile: reg | Panogio.