Some news

Wow, it’s been more than a year since my last post here.

Arthur, my boy, is now 1 year and a half old, has a lot of teeth and a particular interest in music and dance.

I have not worked on Beworded for ages, mainly because I don’t plan to buy an Xbox anymore, and I don’t like the limitations of XNA.
I have shifted my spare time programming efforts towards Android. And when I say Android, I ain’t talking about the Java side of it, but the C side of things. On that platform, I can exercise in writing optimized code, even simd assembler (NEON) on my current phone. And OpenGL ES 2.0 of course :)

The (usual) problem now is that I’m rewriting everything, and struggling to have some kind of STL linked. I think it won’t be a problem anymore in a few versions of the NDK (native dev kit for Android). STL is somehow bad, but some libraries I’m using need some sort of STL, and I don’t want to rewrite container classes for the moment (especially maps).

I’m developing a game, or at least I have an idea of game so politically unacceptable that I won’t even tell you what it is about. I’ll keep it for me and my friend with whom I imagined the principles back in our High School days. It is an exercise, that game will never see the app stores, but more will follow. What I can say is that it’s a top-down view of a city (like GTA 1 or 2?) with pedestrians. You need to make some kind of triage within the crowd to extract and eliminate an « bad » subset without hitting the « good » subset. The extraction is done via baits, specific to who you need to get out of the crowd.

The most difficult part is actually working on it, finding some time. I need to finish it, I need to build a portfolio if ever want to get a chance to jump into the game industry.

Wish me luck.

Gamma Correction

As recently pointed out by John Hable of Naughty Dog here, gamma correction is an extremely important topic for graphics, but a topic that you never learn at school.

Basically, your monitor takes the framebuffer you send to it and applies a « gamma 2.2″ (e.g.: my_color^2.2), thus deforming, shifting your computed pixel values. When you try to output something linear, the screen shows something non-linear. You need to compensate for it !

« But what’s the problem ? When I paint my textures, I do it on a screen applying gamma, so they look exactly how I want them to look ».

Problem is that lighting calculations are linear by nature, and should be done in « linear space », not gamma space.

When your draw your texture, it looks good on screen (looks linear when you mean linear), so it is stored with gamma = 1/2.2 (sRGB) so that when the screen applies a gamma 2.2 it « cancels out » and looks linear.

When doing your lighting calculations, you want to bring your texture to linear space, applying pow(2.2), do your lighting, and apply a pow(1/2.2) before writing to the framebuffer in order to compensate for the monitor gamma.

Please refer to real articles on this topic, because my explanations are quick and not-clear. I just wanted to say that I applied that concept to our in-house product, and here are 2 screenshots demonstrating the huge effect it has on material rendering.

Gamma correction, color only

With bump and texture

As you can see, no hue shifting in the specular spots on the gamma corrected shots, and a really nice bump :)

Beworded, impossible sub-game

Wazaaaaaaaaaaa !

I thought about a second gameplay option for Beworded, kind of a « réussite ». Your grid is filled once, and you try to remove all the letters of the grid by swapping letters to find words. Columns collapse horizontally towards the center. You have to be smart when removing a word, or else you end up being stuck with low frequency letters.

                     1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
   1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8
 4|                                                            n
 5|                                    i                       n
 6|                                    t p             r       n
 7|                            n       s n             m       m             n
 8|              m         l   q       n s   n         t       m       q     r
 9|              d       q p l r       l n   n i     r q       q q     q   t x
10|n             t p     q n s r       r n m r r     v x d     q m     q   t t
11|r   q     n   f g     d l q v       m l n n n     n p q     r d l   c   l c
12|n   x x   q   q r     q n d n q     q n l l n q   l g q     n r n   d   q n
13|e x r r   q   r q     r t n d l s t z l r d n q   r l v   n g r r   y   q q
14|p n r q n p l d l     f r q q x v n p q l q r l   p v r   q q h g   d q q q
15|l q x q t x q r s   r q q q p l q v x g n g q r   r d r   n h x n f q v r c
16|t l m n s s r n j   h r d q q q p f q c r r v l l h r n   q x v l q r b n n
17|r g n q t r q d b x d l q v p q s q q v n q n x q q n r r n r c v r p p q l
18|l x n n q d q z r q d n t t q x n r q s r r t g l r n s l n l g n n l l n n
19|p q n r q d d n d x q v v t h d m x q l p d g b q n q l l y r q n r r m m q
20|t d q q r q q h q s r r l v j q d g p q l b r r h o e n q r h p q q y q t l

Collapse Game: LOST after 121 iterations.

Well, I made the game play itself, and it always ends up being stuck with half the grid still filled… I ordered the game to give me the first valid word it found on the grid, remove it, collapse vertical and horizontal, and test for grid emptiness. Maybe always taking the first « next move » isn’t a smart choice, well, sure it isn’t.

I wonder what I could add to that mode to be able to finish it. Random high frequency letters dropping from the sky? Lots of « joker » letters acting as any letter? Bonuses that give you temporary special powers like « swap entire columns ». I don’t know. If any reader of this blog have an idea, please share :)

As a side note: English grids are waaaaaays longer to generate than French grids, maybe English has a lot more 3-letters words…


Beworded, some statistics and sample Grids !!!

My Grid algorithms are pretty much finished. I’ll share some word count statistics that I found while running my test functions.

I’m generating the initial Grid iteratively, as I described in the previous post. For a typical game grid(7×6):

  • I needed to iterate 10-48 times !!! (one English grid took 1873 iterations)
  • The algorithm removed 90-300 words during the process !!! (the English grid removed 32183 words)
  • That process is taking roughly 20ms.

Not really efficient, but its a one time computation at the initialization of the grid, who cares. After the init, we have a nice grid without any word directly formed (see at the end of the post).

Then, I coded a function to gather all the valid words found for every possible letter swap !

  • Approximately 2500 potential words for a (7×6) grid
  • Valid words out of these 2500 words: 8-60 !!!
  • Timing: 5 ms

A French Grid containing 36 words:

e q p e y i u
a n t o e m q
l t c i q g e
d t i q l q d
t d x q t d r
g j n a s i n

An English Grid containing 48 words:

h d t k h s e
x g h h m j l
i d n r i i g
y r y i q h w
l d y t y h u
n r t i h d c

I don’t have the solution, I didn’t output it to my console, but I could generate it on your request :)

Xna Game « Beworded » Started !

Hi there,

I’ve begun to code an XNA game, finally !! It is called, for the moment, « Beworded ». It’s like bejeweled, but with words.

You have a grid of letters, and you need to swap 2 letters in order to form words between 3 and 5 letters long. When a word (or several) is found, it disappears in a beautiful particle explosion, the grid collapses on its empty spaces and is refilled from the top with new letters.

The words are found in a dictionary. I’ve struggled to find a text list for French and English words. For those who want to create a game based on a dictionary, here is the procedure I followed:

  1. install aspell, and the dictionary in the language you want to export.
  2. in a shell, type "aspell dump master --lang=fr --master=fr --strip-accents > FR-full.txt", with the good locale. The --strip-accents replaces accentuated words with their non-accentuated counterparts (épéé -> epee). I didn’t want to struggle with accents, the game is already gonna be difficult. The problem is that you get multiple instances of the same word.
  3. If you want to select some words, do it with a grep and a regular expression: "grep -i "^[a-z]\{3\}$" FR-full.txt > FR-3.txt". It extracted the 3-letters words from the list.
  4. If you want to sort your words: "sort FR-3.txt /O FR-3-sort.txt" in a DOS shell, for example.
  5. If you want to paste multiple files together, do this in DOS: "copy FR-3-sort.txt + FR-4-sort.txt + FR-5-sort.txt FR-final.txt".
  6. Finally, I used some C# code to remove doubles, and « to-lower » everything. I didn’t know any other way to do it. I’m not a shell guru, at all.

Well, the only interesting line is the second one, how to extract words from aspell, the rest is up to you.

Now that I have my dictionary, I need a file describing the occurrence of every letter in the French and English language. There are multiple sources for this, with different results. They are calculated from text corpus, I found the English one on wikipedia.

With the Dictionary and the Letters Frequency, I can build a random letter generator (using the frequency) to fill a grid with letters, and check in the dictionary if any word in the grid is a real word !

It works, and it works really fast without optimization. I thought it would take ages, but no :)

What I did, naively, for the moment, in order to speed-up the words lookup in the dictionary was to build a small (26×26) lookup table indexed with the first 2 characters of the word, like table["aa"], table["zs"]. This table helps me find a range of indexes inside the full word table. With this I only have to compare my word with like 10-20 words. If anyone has a better idea, I’m all ears.

Then I started coding utility functions in the Grid class, like « give me the potential words to check when I swap these 2 letters », or remove that list of words in the Grid. Now I’m generating the first Grid iteratively, removing all natively formed words, collapsing the Grid and refilling it with new letters.

Here is an intermediate screenshot (with awesome particle effects and bump maps !!!):

That’s all for the moment !

See you.

Too many books for a life time.

Hi there,

First, I’d like to apologize for my previous statement about Game Engine Architecture. There are a few UML diagrams after all. I have that bad habit of judging anything I read too soon. Sorry Jason, I love your book.

Talking about books, I’ve been reading Programming Massively Parallel Processors: A Hands-on Approach for about a month now, at work during lunch time. As I said on SebH’s blog, it’s a little bit short for such a price, but contains good material on CUDA. I like when teachers write books. I’m not done with it yet, I’ll post my review when I’ll be sure about what I want to say :)

I just received Video Game Optimization, and Game Programming Gems 8. That’s too much to read before the two next one coming early on May: Game Engine Gems, Volume One and GPU Pro: Advanced Rendering Techniques.

Video Game Optimization is a relatively short book (~300 pages), but it gathers a whole lot of optimization theory and practice, packed into a single book. I read a lot of books that used to give code snippets to optimize one thing or another, but this time it’s an all-in-one book. I like « gems » collections books, but now I’m starting to really look for specialized books, and this one is promising. We’ll see. Btw, it’s written by Ben Garney and Eric Preisz, who among other things have developed the Torque Game Engine.

Game Programming Gems 8, well, it’s a Game Programming Gems book, always a pleasure to read, I love that series. I noticed a gem on application design when using « tablets », and that’s precisely what I’m working on. There’s even an article by a Blizzard guy, on SSAO in Starcraft 2. One friend of mine, an « Art Director » at Supamonks, told me that Blizzard artists never post on public forums to share ideas and their work, and that the community would be pleased to here from them. I’m wondering if there’s a black-hole on all Blizzard’s technology, because I haven’t read a lot of graphics articles from them.

One day maybe, I’ll start coding all those techniques I read… I should do that if I want to put interesting things into my CV :)


A few words about myself

Now I’ll talk a bit about myself, so that whoever is reading this blog knows whose thoughts he’s reading.

My name is Nicolas Fauvet, 28, living in France. I got married almost a year ago, and a baby is soon coming out oh his mother’s… hum… belly. The name is secret ! No hints ! EDIT: I’m now almost 30, and the baby’s name is Arthur :)

I’ve lived in Africa when I was young, for 8 years. It’s a part of me I can never forget, and I think it made me the open-minded person I am.

I’ve got a MSc in computer science from the Orsay faculty (Paris 11). I chose all the computer graphics, interaction and virtual reality options I could (not many, though).

After that, I’ve been a PhD student for 4 years at the CNRS-Limsi, in Orsay. During that PhD, I researched in the fields of Virtual Reality, massive fluid dynamics data visualization and haptic exploration. I’ve also been teaching Computer Graphics the whole time at the undergraduate level (BSc). It was a fantastic experience.

After those 4 years of vacatio… hum… hard work, I started the « real-life » work (’cause you know, research isn’t work…) with some IT consulting. Consulting firms are evil, everyone knows it, but I was unaware of that fact… at the beginning. Pressure, low salary (a thesis doesn’t count as experience), lies, manipulation, etc. The day I woke up I immediately started looking for something else, I had to get out or I would be stuck for years of depression. My consulting missions were boring as hell, simple, non-challenging, and on top of everything, too away from anything I liked (computer graphics).

Hopefully, I found a computer software company, working on computer assisted design (CAD) for shoes. Yes, shoes, and leather handbags, and real estate maps/furniture. But let’s only talk about shoes. I’m working on a an application that enables a designer to draw directly on a 3D model of a shoe, using a Wacom Cintiq screen/tablet. It means that with a plastic pen, you are drawing directly on the screen, on a 3d model, with numerous drawing tools (ala Photoshop). I’m working on these tools, and 3d in general. There’s a lot of work to do, a lot of potential enhancements to the application. It’s written in ADA, a bit weird at first, but I got used to it. ADA is so strongly typed that we almost never have to debug anything !!!!

I’m interested in computer games and 3d graphics since the age of 15, if I remember correctly (when I got my Ti-92). I used to program games with a friend during school time, it was really interesting. I found it to be logical and easy. For my 16th birthday I had my mom buy me a big C++ book. In college, I learned a lot of things from the demoscene, and coded my first dynamic 3d scenes, in software. I bought that awesome book from Mickael Abrash, « Zen of graphics programming ». Man, it was full of assembly rendering code he used in quake, such a good time. After that I learned how much DirectX and Win32 code could be ugly, and I ran the opposite way towards OpenGL and NeHe’s tutorials. After having studied computer graphics (along with general computer science), I got my master’s degree, and started my PhD thesis on virtual reality and massive scenes handling. At that time, I was the professor, and I could give back what I learned during the last 5 years. My best human experience ever.

I haven’t stopped coding in OpenGL since the days of the NeHe tutorials, and now it’s my real work. I have tried DirectX a number of times. I bought several books on the subject, and the only one that could have me pass to the dark side was the Wolfgang Engel one (really liked the style). But no, I couldn’t, just too ugly for me. My « closest to DirectX » experience was with XNA (within Teapot Studio, because you don’t actually code with DirectX but you know it’s underneath (what a relief). DirectX has changed, I could give it a last try, but OpenGL has changed too, and I’ve got to catch up with it’s latest advances.

I’m a computer graphics books devourer, I love them, and it’s actually the only thing I’m collecting. I’m reading too much and not coding enough, my head is full of game and rendering algorithms. I hope I can put out some of that living knowledge base into my daily work, cause at home I’m busy exploring and studying games. Yeah, ok, playing games, and WoW, but only to keep myself informed!

Why « droune » ? The history of nicknames are sometimes strange. I used to nickname me « doctor oon », because I wanted to be a doctor (in computer science), and « oon » meant « out of nowhere »… I wrote it « dr_oon », which a friend of mine pronounced « droune ». So it became droune.
Why « Matumbo » ? It’s my main World of Warcraft character’s name, I like it. It’s taken from the name of a bad guy in « The Pretender ».

Ok, now you know a lot of uninteresting things on me, and I could spend a few hours at work not working :)


Too much love for books…

I was a little too much enthusiastic about Game Engine Architecture. I really enjoyed reading it cover to cover, but I’m a bit disappointed. It is a good book, but with the wrong title. It discusses about game engine components for current games, but only from a far view. It actually never talks about the architecture itself (not any single UML diagram), more about what are all the components you must find in a serious game engine.

Moreover, it barely describes numerous rendering effects, but thoroughly talks about character animation (the guy has actually worked on animation). It has an uneven coverage of topics.

I learned things about character animation, really, and I was pleased to read through that broad overview of game engine components, but the book didn’t give me what I bought it for.

The other book, on the contrary, gave me exactly what I wanted from him: the engineering process(es).

That blog is gonna be filled with comments on books, I’ll be soon talking about the zillion books I have pre-ordered on amazon :)


A few good books that need some love

Today, I want to start talking about good books I’ve read, and mostly about the two I’m currently reading.

I’m a wannabe game programmer, and I’ve read a lot of books about game programming and 3d graphics, including the Game Programming Gems (7) series, the GPU Gems (3) series and the ShaderX (7) series (Wolfgang E., one of my heroes). These are just awesome, full of incredibly usefull techniques, and beautiful books to have in your personal library.
After having read all these, I knew (theoretically) a lot of game and graphics « gems », but I was still missing important knowledge bits to start engineering games. Architecture and Engineering processes for games !!!! I thought « there must be a book dealing with the subject !!! »
That’s when I found :

Man, these two books contain exactly what’s mentioned in their title, and moreover exactly what I was looking for for so many years.

The first one deals with the entire engineering process to build a game, from design, requirement specification document, use cases, activity diagrams, uml… the good ol’ IEEE engineer process, but this time applied to a game. Along with the book is an entire game with full source code for every step of the development, including all engineering documents. This book is extremely useful. I wanted to apply some engineer love to my game developments, but had never written any « real » software engineering document. That’s the definite best example.

The second book is another dream fulfilled. It describes all the common building blocks and patterns of good games for PC and consoles. « Architecture », THE word I was desperatly looking for in amazon. I’m reading it when I have time, I’ll talk a bit more about it when I’m finished. It’s written by a cool guy who worked on Uncharted 1 & 2 on PS3. Btw, thanks to that guy, I bought a PS3 ! I don’t regret it.

All these books where bought on, in the « english book » section. Great idea, thanks Amazon.

Blog creation

Hi everyone,
This is my first blog. I’ll be talking about 3d graphics and game programming. I’m not an expert, I don’t have that much practical experience in both domains, but a lot of theoretical knowledge. I read tons of books on 3d, gpu, graphics, game programming, and it is time to jump into dirt. So I’ll be sharing my thoughts about algorithms I’m trying to implement, or games I’m writing within Teapot-Studio, or even useless comments on how life sucks sometimes.