Skip to main content

Posts

Assert no lock required

This is a technique I learnt about from Jason Gregory's excellent book, Game Engine Architecture (3rd Edition) . If you have a shared resource accessed by multiple threads, where you're fairly certain that it's only ever accessed by one thread at a time, you can use an assert() to check for this at debug time without having to pay the runtime cost of locking a mutex. The implementation is fairly straightforward: class UnnecessaryMutex { public: void lock() { assert(!_locked); _locked = true; } void unlock() { assert(_locked); _locked = false; } private: volatile bool _locked = false; }; #ifdef ENABLE_LOCK_ASSERTS #define BEGIN_ASSERT_LOCK_NOT_REQUIRED(mutex) (mutex).lock() #define END_ASSERT_LOCK_NOT_REQUIRED(mutex) (mutex).unlock() #else #define BEGIN_ASSERT_LOCK_NOT_REQUIRED(mutex) #define END_ASSERT_LOCK_NOT_REQUIRED(mutex) #endif Usage is equally straightforward: UnnecessaryMutex gMutex; void PossiblyOverlappingFunction...

Triangle bounding boxes in a single byte

Just thought of a way to store the bounding box for a single triangle in only one byte. It's not really practical or something you'd ever really want to use, but what the hell. Assume we have some kind of indexed mesh structure with a list of vertex positions and a list of triangle indices:   struct Mesh {     std::vector<vec3> verts;     std::vector<uvec3> triangles;   }; We can find the bounding box of a triangle by taking the min and max of all three vertices:   vec3 Mesh::lowerBound(uint32_t tri) const {     vec3 v0 = verts[triangles[tri].x];     vec3 v1 = verts[triangles[tri].y];     vec3 v2 = verts[triangles[tri].z];     return min(min(v0, v1), v2);   }   vec3 Mesh::upperBound(uint32_t tri) const {     vec3 v0 = verts[triangles[tri].x];     vec3 v1 = verts[triangles[tri].y];     vec3 v2 = verts[triangles[tri].z];     return ...

LD_DEBUG

Posting this mainly as a reminder to myself... If you ever find yourself needing to figure out a dynamic library loading problem on Linux, LD_DEBUG can be a massive help. This is an environment variable you can set to make the dynamic linker print out a ton of useful diagnostic info. There are a number of different values which control the amount and type of diagnostics printed. One of the values is help; if you set LD_DEBUG to this and run executable it will print out a list of all the available options along with brief descriptions. For example, on my Linux workstation at the office: > LD_DEBUG=help cat Valid options for the LD_DEBUG environment variable are: libs display library search paths reloc display relocation processing files display progress for input file symbols display symbol table processing bindings display information about symbol binding versions display version dependencies all all previous options combi...

Octree node identifiers

Let's say we have an octree and we want to come up with a unique integer that can identify any node in the tree - including interior nodes, not just leaf nodes. Let's also say that the octree has a maximum depth no greater than 9 levels, i.e. the level containing the leaf nodes divides space into 512 parts along each axis. The encoding The morton encoding of a node's i,j,k coordinates within the tree lets us identify a node uniquely if we already know it's depth. Without knowing the depth, there's no way to differentiate between cells at different depths in the tree. For example, the node at depth 1 with coords 0,0,0 has exactly the same morton encoding as the node at depth 2 with coords 0,0,0. We can fix this by appending the depth of the node to the morton encoding. If we have an octree of depth 9 then we need up to 27 bits for the morton encoding and 4 bits for the depth, which still fits nicely into a 32-bit integer. We'll shift the morton code up so t...

Common bit prefix length for two integers

Here's a neat trick I discovered a couple of months back: given two signed or unsigned integers of the same bit width, you can calculate the length of their common prefix very efficiently: int common_prefix_length(int a, int b) { return __builtin_clz(a ^ b); } What's this doing? Let's break it down: a ^ b is the bitwise-xor of a and b. The boolean xor operation is true when one of it's inputs is true and the other is false; or false if both have the same value. Another way to put this is that xor returns true when its inputs are different and false if they're the same. The bitwise-xor operation then, returns a value which has zeros for every bit that is the same in both a and b; and ones for every bit that's different. __builtin_clz is a GCC intrisinc function which counts the number of leading zero bits of its argument. It compiles down to a single machine code instruction on hardware that supports it (which includes every Intel chip made i...

Image based lighting notes

These are some of my notes from implementing image based lighting, a.k.a. IBL. I thought I understood it pretty well until I started implementing it. Now, after a lot of reading, discussing and trying things out, I'm finally getting back to the stage where I tentatively believe I understand it. Hopefully these notes will save future me, or anyone else reading them, from going through the same difficulty. I'll update them if I find out anything further. Some helpful references GPU-Based Importance Sampling , GPU Gems 3, Chapter 20 . Real-Time Computation of Dynamic Irradiance Maps , GPU Gems 2, Chaper 10. Physically Based Shading in Theory and Practice , SIGGRAPH 2013 Course. In particular, the course notes for "Real Shading in Unreal Engine 4" are very helpful. The radiance integral $$L_o(v) = L_e(v) + \int_\Omega L_i(l) f(l, v) (n \circ l) dl$$ The amount of light reflected at some point on a surface is the sum, over all incoming directions, o...

Faster morton codes with compiler intrinsics

Today I learned that newer Intel processors have an instruction which is tailor-made for generating morton codes: the PDEP instruction. There's an instruction for the inverse as well, PEXT . These exist in 32- and 64-bit versions and you can use them directly from C or C++ code via compiler intrinsics: _pdep_u32/u64 and _pext_u32/u64 . Miraculously, both the Visual C++ and GCC versions of the intrinsics have the same names. You'll need an Intel Haswell processor or newer to be able to take advantage of them though. Docs for the instructions: Intel's docs GCC docs Visual C++ docs This page has a great write up of older techniques for generating morton codes: Jeroen Baert's blog ...but the real gold is hidden at the bottom of that page in a comment from Julien Bilalte, which is what clued me in to the existence of these instructions. Update: there's some useful info on Wikipedia about these intructions too.

Awesome tools for Windows users

I moved back to Windows on my home computer a few months back. There are a few amazing free tools I've found since then that have been making my life better and I thought they deserved a shout-out. They are: SumatraPDF A fantastic PDF reader. Does everything I want and nothing I don't. RapidEE A sane way to edit environment variables. The simple joy of just being able to resize the window is... incredible. 7-Zip The best tool for dealing with compressed files on windows, bar none. GPU-Z A really handy way to see details about your GPU(s). XnView An amazingly good image viewer, which can also do bulk file format conversions. If you haven't already got these... go get them!

Whole program lexical analysis

I was thinking about parsing and lexical analysis of source code recently (after all who doesn't... right??). Everywhere I've looked - which admittedly isn't in very many places - parsers still seem to treat input as a stream of tokens. The stream abstraction made sense in an era where memory was more limited. Does it still make sense now, when 8 Gb of RAM is considered small? What if, instead, we cache the entire token array for each file? So we mmap the file, lex it in place and store the tokens in an in-memory array. Does this make parsing any easier? Does it lead to any speed savings? Or does it just use an infeasible amount of memory? Time for some back-of-the napkin analysis. Let's say we're using data structures kind of like this to represent tokens: enum TokenType { /* an entry for each distinct type of token */ }; struct Token { TokenType type; // The type of token int start; // Byte offset for the start of the token int end; ...

Project Tethys Post-mortem

Project Tethys was my entry for Ludum Dare 29 . Here's the elevator pitch: Project Tethys is a fast-paced underwater 2D shoot-em up inspired by the likes of Defender and Resogun . You control an advanced combat submarine tasked with defending an underwater research facility against an invading army. If you enjoy classic arcade-style action, this game is for you! So far the game has been getting pretty good feedback. It's the most polished entry I've ever submitted for a Ludum Dare and the one that I'm most proud of so far. Here's what it looks like in action: I've carried on working on it since the end of the competition, fixing some of the problems people have commented on and adding more of the features I'd originally planned. Expect another post about that when I'm ready to release it. Tools Unity 4.3 (free version) GarageBand for iPad bxfr Nuke 8.0 (specifically the ModelBuilder node) Paint.NET VLC What went right Makin...

Ludum Dare 29: Beneath the Surface

I'm halfway through making a game for Ludum Dare 29 . The theme this time around is "Beneath the Surface". For once I've had an idea right from the start that's practical, fun and in keeping with the theme. It's a lovely change from my usual pattern of starting with an idea that turns out to be impractical or boring & having to start over halfway through the competition. So on that basis alone I have high hopes for this one. Here it is: Project Tethys It's an underwater shoot-and-rescue-em-up inspired by the likes of Defender and Resogun . You control a state-of-the-art combat submarine tasked with defending an underwater research facility from an invading army. Or at least, that's what it should be if I can finish it in time... The controls are arrow keys or WASD to move, left mouse button to fire. There's still loads left to do: implementing the rescue mechanic; sound effects; enemy AI; a high score table; a menu system; better model...

OpenGL in OS X 10.9

Apple announced details of OS X 10.9 "Mavericks" today. For anyone who writes cross-platform graphics software, one of the biggest bits of news was that it will finally support OpenGL 4. Specifically: OS X 10.9 will support the OpenGL 4.1 Core Profile This info comes from their release notes . I haven't been able to find any info about supported extensions yet. While welcome, the news is still a bit disappointing. OpenGL 4.1 is now a 3 year old standard, so I'd hoped for something a bit more recent. I believe the Intel HD4000 and HD5000 chips used the MacBook Air & Pro only support up to OpenGL 4.1, so I guess that played a part in the decision.  OS X will be still be the lowest common denominator for OpenGL, relative to Windows and Linux; but at least the denominator is not quite as low any more!

Iterating faster

Today I spent a few minutes writing a Makefile. I think they may turn out to be some of the most effective minutes I've ever spent. At work we build using SCons . When I change a single source file, rebuilding takes between 50 and 65 seconds. That's more than long enough to lose my focus and get distracted, so to stay productive I have to work in larger batches. I code in longer bursts and recompile less often, so that the ratio of productive time to down time stays up; unfortunately that also means fewer opportunities to test my changes. That's not ideal, but it's manageable much of the time. Not at the moment though. Right now I'm developing an algorithm where I need to be able to quickly try out different approaches for each of the steps. In this situation I really want to see the effect of each change in isolation, so I can't batch up my coding. All of a sudden those 50 second build times are a real problem. I spent a little while looking into ways to...

OpenGL ES and occlusion queries

This is a follow-up to my earlier post "WebGL doesn't have query objects" . Since I wrote that post, the situation has changed a bit. It's still true to say that WebGL doesn't have query objects, but the underlying reason - that OpenGL ES doesn't - is no longer true. For OpenGL ES 2.0 , there's an extension which provides basic query functionality: EXT_occlusion_query_boolean  (which seems to have been based on ARB_occlusion_query2 from regular OpenGL). For OpenGL ES 3.0 , the functionality from that extension appears to have been adopted into the standard. The extension provides two query types, both of which set a boolean value to indicate whether any pixels passed the depth and stencil tests. While this is progress, unfortunately it's still not sufficient to implement the pixel accurate collision detection method I described in an earlier post. For that purpose it's not enough to know whether any  pixels passed the tests; you want to kno...

A handy little script for QtCreator users

If you use QtCreator for what it calls " generic projects " I've written a little script which might be useful for you: https://github.com/vilya/newfiles This script will rescan your project directories to see whether any files & include directories have been added or removed and update the QtCreator project files accordingly - something QtCreator isn't yet able to do for itself. It has a few extra features too, such as whitelisting or blacklisting paths using shell-style wildcards. See the README file at the link above for more details.

How to outperform std::vector in 1 easy step

Everyone who's familiar with C++ knows that you should avoid resizing a std::vector inside a loop wherever possible. The reasoning's pretty obvious: the memory allocated for the vector doubles in size each time it fills up and that doubling is a costly operation. Have you ever wondered why it's so costly though? It's tempting to assume that because implementations of the STL have been around for so long that they must be pretty efficient. It turns out that's a bad assumption because the problem, in this case, is the standard itself: specifically, the allocator interface. The allocator interface provides two methods that obtain and release memory: allocate allocates uninitialized storage (public member function) deallocate deallocates storage (public member function) (taken from this page ). What's missing is a   way of growing an existing memory allocation in place. In C this is provided by the realloc function, but there's no equiva...

Ludum Dare 24 Results

The voting has finally finished and the Ludum Dare 24 results are finally out. My game , frankly, did a lot better than I expected: Humour #36 Fun #239 Mood #296 Overall #417 Graphics #600 Innovation #603 Audio #615 Theme #672 There were 1006 entries in the 48 hour competition. I'd been hoping to finish in the top half of the rankings this time after a poor showing last time and that's what I managed: 417th overall. The big surprise was the humour score: wow! I was worried that the humour might be a bit too straight-faced for people, or that I'd be the only one who found it funny. Being wrong has rarely been a happier experience! I was also really pleased with the Fun score. To me that's the most important category after Overall. It means I made something that people enjoyed playing and that's a really rewarding feeling. It was nice to get a decent score for the mood category too, but I've never really understood what it means exactly. The ot...

Invaders: Evolution Post-mortem

Invaders: Evolution is the game I wrote for the 24th Ludum Dare competition. It's the 3rd time I've made a game for LD (as well as one for a MiniLD event) & although I think my games get a bit better each time, I still have so much to learn. This is a post-mortem not just for the game, but for my competition experience as well. The game is basically Space Invaders, but with a twist: it tells the back-story of the aliens through cut-scenes as you play. It also has two possible endings, one of which is rather unconventional by video game standards. You can try it out, or find out more, here: Post-competition version  (fixes some of the bugs in the competition version) Competition version  (this is what I submitted for the competition) Ludum Dare page (vote for it if you can!) Source code What went right I made a game! There was a low point where I thought I'd have to quit the competition (see the "what went wrong" section), but in the end I cam...

Ludum Dare 24: Evolution

The 24th Ludum Dare competition has just finished.  I got a game in for it, but only barely. In what seems to be becoming a pattern for me, I spent the first day working on an idea I ended up having to abandon. The game I ended up submitting was done in a mad 12 hour rush at the end. Here it is: Invaders: Evolution It's a fresh take (I hope) on the Space Invaders story. What, you didn't realise there was a story to that? Well if there wasn't, there is now... There were a few things about it I was really happy with and a few things that could have gone better. Expect a post-mortem soon.

Solar Sailor Post-mortem

Solar Sailor, for those of you who aren't yet aware, is a fairly simple racing game that I made for the Ludum Dare 48 hour challenge. Here's the competition entry page: http://www.ludumdare.com/compo/ludum-dare-23/?action=preview&uid=10456 Or you can get straight into it here: http://dl.dropbox.com/u/25468009/SolarSailor/index.html Making a playable game in just 48 hours is a pretty intense experience. This is my attempt to make sense of it all, with the benefit of a few days worth of hindsight. What went right I used Javascript and WebGL to write the game. Although I was fairly new to Javascript*, it turned out to be a great language for writing a game: Built-in support for object literals (a.k.a JSON) made it very easy to get content into the game. Being able to just hit reload in the browser to test out changes made for a very tight edit-run loop. You effectively get image and font loading for free, thanks to the web browser. Sound too, theoreti...