Erik McClure

Today, xkcd featured a comic with a comically large image that is navigated by clicking and dragging. In the interests of SCIENCE (and possibly accidentally DDoSing Randall’s image server - sorry!), I created a static HTML file of the entire composite image.¹

The collage is made up of 225 images² that stretch out over a total image area 79872 pixels high and 165888 pixels wide. The images take up 5.52 MB of space and are named with a simple naming scheme "ydxd.png" where d represents a cardinal direction appropriate for the axis (n for north, s for south on the y axis and e for east, w for west on the x axis) along with the tile coordinate number; for example, "1n1e.png". Tiles are 2048x2048 png images with an average size of 24.53 KB. If you were to try and represent this as a single, uncompressed 32-bit 79872x165888 image file, it would take up 52.99 GB of space.

Assuming a human’s average height is 1.8 meters, that would give this image a scale of about 1 meter per 22 pixels. That means the total composite image is approximately 3.63 kilometers high and 7.54 kilometers wide. It would take an average human 1.67 hours to walk from one end of the image to the other. Note that the characters at the far left say they’ve been walking for 2 miles - they are 67584 pixels from the starting point, which translates to 3.072 km or ~1.9 miles, so this seems to indicate my rough estimates here are reasonably accurate.

If Randall spent, on average, one hour drawing each frame, it would take him 9.375 days of constant, nonstop work to finish this. If he instead spent an average of 10 minutes per frame, it would take ~37.5 hours, or almost an entire 40-hour work week.

Basically I’m saying Randall Munroe is fucking insane.

Today I learned that there are way too many coordinate systems, and that I’m an idiot (but that was already well-established). I have also learned to not trust graphics tutorials, but the reasons for that won’t become apparent until the end of this article.

There are two types of coordinate systems: left-handed and right-handed coordinate systems. By convention, most everyone in math and science uses right-handed coordinate systems with positive x going to the right, positive y going up, and positive z coming out of the screen. A left-handed coordinate system is the same, but positive z instead points into the screen. Of course, there are many other possible coordinate system configurations, each either being right or left-handed; some modern CAD packages have y pointing into the screen and z pointing up, and screen-space in graphics traditionally has y pointing down and z pointing into the screen.

If you start digging through DirectX and OpenGL, the handedness of the coordinate systems being used are ill-defined due to its reliance on various perspective transforms. Consequently, while DirectX traditionally uses a left-handed coordinate system and OpenGL uses a right-handed coordinate system, you can simply use D3DPerspectiveMatrixRH to give DirectX a right-handed coordinate system, and openGL actually uses a left-handed coordinate system by default on its shader pipeline - but all of these are entirely dependent on the handedness of the projection matrices involved. So, technically the coordinate system is whichever one you choose, but unlike the rest of the world, computer graphics has no real standard on which coordinate system to use, and so its just a giant mess of various coordinate systems all over the place, which means you don’t know what handedness a given function is for until things start getting funky.

I discovered all this, because today I found out that, for the past 6 or so years (the entire time my graphics engine has ever existed in any shape or form), it has been rotating everything backwards. I didn’t notice.

This happened due to a number of unfortunate coincidences. For many years, I simply didn’t notice because I didn’t know what direction the sign of a given rotation was supposed to rotate in, and even if I did I would have assumed this to be the default for graphics for some strange reason (there are a lot of weird things in graphics). The first hint was when I was integrating with Box2D and I had to reverse the rotation of its bodies to match up with my images. This did trigger an investigation, but I mistakenly concluded that it was Box2D that had it wrong, not me, because I was using atan2 to check coordinates, and I was passing them in as atan2(v.x,v.y). The problem is that atan2 is defined as float atan2(float y, float x), which means my coordinates were reversed and I was getting nonsense angles.

Now, here you have to understand that I was currently using a standard left-handed coordinate system, with y pointing up, x pointing right and z into the screen. The thing is, I wanted a coordinate system where y pointed down, and so I did as a tutorial instructed me to and reversed all of my y coordinates on the low-level drawing functions.

So, when atan2(x,y) gave me bad results, I mistakenly thought “Oh, i forgot to reverse the y coordinate!” Suddenly atan2(x,-y) was giving me angles that matched what my images were doing. The thing is, if you switch x and y and negate y, atan2(x,-y)==-atan2(y,x). One mistake had been incorrectly validated by yet another mistake, caused by yet another mistake!

You see, by inverting those y coordinates, I was accidentally reversing the result of my rotation matrices, which caused them to rotate everything backwards. This was further complicated by how the camera rotates things - if your camera is fixed, how do you make it appear that it is rotating? You rotate everything else in the opposite direction! Hence even though my camera was rotating backwards despite looking like it was rotating forwards, it was actually being rotated the right way for the wrong reason.

While I initially thought the fix for this would require some crazy coordinate system juggling, the actual solution was fairly simple. The fact was, a coordinate system with z pointing into the screen and y pointing down is still right-handed, which means it should play nicely with rotations from a traditional right-handed system. Since the handedness of a coordinate system is largely determined by the perspective matrix, reversing y-coordinates in the drawing functions was actually reversing them too late in the pipeline. Hence, because I used D3DXMatrixPerspectiveLH, I had a left-handed coordinate system, and my rotations ended up being reversed. D3DXMatrixPerspectiveRH negates the z-coordinate to switch the handedness of the coordinate system, but I like positive z pointing into the screen, so I instead hacked the left-handed perspective matrix itself and negated the y-scaling parameter in cell [2,2], then undid all the y-coordinate inversion insanity that had been inside my drawing functions (you could also negate the y coordinate in any world transform matrix sufficiently early in the pipeline by specifying a negative y scaling in [2,2]). Suddenly everything was consistent, and rotations were happening in the right direction again. Now the Camera rotation actually required the negative rotation, as one would expect, and I still got to use a coordinate system with y pointing down. Unfortunately it also reversed several rotation operations throughout the engine, some of which were functions that had been returning the wrong value this whole time so as to match up with the incorrect rotation of the engine - something that will give me nightmares for weeks, probably involving a crazed rabbit hitting me over the head with a carrot screaming “STUPID STUPID STUPID STUPID!”

What’s truly terrifying that all of this was indirectly caused by reversing the y coordinates in the first place. Had I instead flipped them in the perspective matrix itself (or otherwise properly transformed the coordinate system), I never would have had to deal with negating y coordinates, I never would have mistaken atan2(x,-y) as being valid, and I never would have had rotational issues in the first place.

All because of that one stupid tutorial.

_{P.S. the moral of the story isn’t that tutorials are bad, it’s that you shouldn’t be a stupid dumbass and not write unit tests or look at function definitions.}

It’s almost a tradition.

Every time my graphics engine has been stuck in maintenence mode for 6 months, I’ll suddenly realize I need to push out an update or implement some new feature. I then realize that I haven’t actually paid attention to any of my testing programs, or their speed, in months. This is followed by panic, as I discover my engine running at half speed, or worse. Having made an infinite number of tiny tweaks that all could have caused the problem, I am often thrown into temporary despair only to almost immediately find some incredibly stupid mistake that was causing it. One time it was because I left the profiler on. Another time it was caused by calling the Render function twice. I’m gearing up to release the first public beta of my graphics engine, and this time is no different.

I find an old backup distribution of my graphics engine and run the tests, and my engine is running at 1100 FPS instead of 3000 or 4000 like it should be. Even the stress test is going at only ~110 FPS instead of 130 FPS. The strange part was that for the lightweight tests, it seemed to be hitting a wall at about 1100 FPS, whereas normally it hits a wall around 4000-5000 due to CPU⇒GPU bottlenecks. This is usually caused by some kind of debugging, so I thought I’d left the profiler on again, but no, it was off. After stepping through the rendering pipeline and finding nothing, I knew I had no chance of just guessing what the problem was, so I turned on the profiler and checked the results. Everything seemed relatively normal except-

PlaneShader::cEngine::_callpresent       1.0    144.905 us   19%        145 us   19%
PlaneShader::cEngine::Update             1.0     12.334 us    2%        561 us   72%
PlaneShader::cEngine::FlushMessages    1.0    546.079 us   70%        549 us   71%

bool cEngine::FlushMessages()
{
PROFILE_FUNC();
_exactmousecalc();
//windows stuff
MSG msg;

while(PeekMessageW(&msg, NULL, 0, 0, PM_REMOVE))
{
TranslateMessage(&msg);
DispatchMessageW(&msg);

    if(msg.message == WM_QUIT)
    {
      _quit = true;
      return false;
    }

}

_joyupdateall();
return !_quit; //function returns opposite of quit
}

void cInputManager::_joyupdateall()
{
JOYINFOEX info;
info.dwSize=sizeof(JOYINFOEX);
info.dwFlags= \[ Clipped... \];

for(unsigned short i = 0; i < _maxjoy; ++i)
{
if(joyGetPosEx(i,&info)==JOYERR_NOERROR)
{
if(_allbuttons\[i\]!=info.dwButtons)
{

Of course, if you aren’t developing a graphics engine, consider that 1/60 of a second is 16666 µs - 550 µs leaves a lot of breathing room for a game to work with, but a graphics engine must not force any unnecessary cost on to a program that is using it unless that program explicitly allows it, hence the problem.

Then again, calculating invsqrt(x)*x is faster than sqrt(x), so I guess anything is possible.

A couple years ago, when I first started designing a game engine to unify Box2D and my graphics engine, I thought this was a superb opportunity to join all the cool kids and multithread it. I mean all the other game developers were talking about having a thread for graphics, a thread for physics, a thread for audio, etc. etc. etc. So I spent a lot of time teaching myself various lockless threading techniques and building quite a few iterations of various multithreading structures. Almost all of them failed spectacularly for various reasons, but in the end they were all too complicated.

I eventually settled on a single worker thread that was sent off to start working on the physics at the beginning of a frame render. Then at the beginning of each subsequent frame I would check to see if the physics were done, and if so sync the physics and graphics and start up another physics render iteration. It was a very clean solution, but fundamentally flawed. For one, it introduces an inescapable frame of input lag.

Single Thread Low Load
  FRAME 1   +----+
            |    |
. Input1 -> |    |
            |[__]| Physics   
            |[__]| Render    
. FRAME 2   +----+ INPUT 1 ON BACKBUFFER
. Input2 -> |    |
. Process ->|    |
            |[__]| Physics
. Input3 -> |[__]| Render
. FRAME 3   +----+ INPUT 2 ON BACKBUFFER, INPUT 1 VISIBLE
.           |    |
.           |    |
. Process ->|[__]| Physics
            |[__]| Render
  FRAME 4   +----+ INPUT 3 ON BACKBUFFER, INPUT 2 VISIBLE

Multi Thread Low Load
  FRAME 1   +----+
            |    | 
            |    |
. Input1 -> |    | 
.           |[__]| Render/Physics START  
. FRAME 2   +----+        
. Input2 -> |____| Physics END
.           |    |
.           |    | 
. Input3 -> |[__]| Render/Physics START
. FRAME 3   +----+ INPUT 1 ON BACKBUFFER
.           |____|
.           |    | PHYSICS END
.           |    | 
            |____| Render/Physics START
  FRAME 4   +----+ INPUT 2 ON BACKBUFFER, INPUT 1 VISIBLE

The multithreading, by definition, results in any given physics update only being reflected in the next rendered frame, because the entire point of multithreading is to immediately start rendering the current frame as soon as you start calculating physics. This causes a number of latency issues, but in addition it requires that one introduce a separated “physics update” function to be executed only during the physics/graphics sync. As I soon found out, this is a massive architectural complication, especially when you try to put in scripting or let other languages use your engine.

There is another, more subtle problem with dedicated threads for graphics/physics/audio/AI/anything. It doesn’t scale. Let’s say you have a platformer - AI will be contained inside the game logic, and the absolute vast majority of your CPU time will either be spent in graphics or physics, or possibly both. That means your game effectively only has two threads that are doing any meaningful amount of work. Modern processors have 8 logical cores¹, and the best one currently available has 12. You’re using two of them. You introduced all this complexity and input lag just so you could use 16.6% of the processor instead of 8.3%.

Instead of trying to create a thread for each individual component, you need to go deeper. You have to parallelize each individual component separately, then tie them together in a single-threaded design. This has the added bonus of being vastly more friendly to single-threaded CPUs that can’t thread things (like certain phones), because the parallization goes on at a lower level and is invisible to the overall architecture of the library. So instead of having a graphics thread and a physics thread, you simply call the physics update, then call the graphics update, and inside each physics and graphics update you spawn enough worker threads to match the number of cores you have to work with and concurrently process as much stuff as possible. This eliminates latency problems, complicated library designs, and it scales forever. Even if your initial implementation of concurrency won’t handle 32 cores, because the concurrency is encapsulated inside the engine, you can just go back and change it later without ever having to modify any programs that use the graphics engine.

Consequently, don’t try to multithread your games. It isn’t worth it. Separately parallelize each individual component instead and write your game engine single-threaded; only use additional threads for asynchronous activities like resource loading.

¹ The processors actually only have 4 or 6 physical cores, but use hyperthreading techniques so that 8 or 12 logical cores are presented to the operating system. From a software point of view, however, this is immaterial.

The fact that math, for most people, is about a set of rules, exemplifies how terrible our attempts at teaching it are. A disturbing amount of programming education is also spent hammering proper coding guidelines into students’ heads. Describing someone as a cowboy programmer is often derisive, and wars between standards, rules and languages rage like everlasting fires. It is into these fires we throw the burnt-out husks that were once our imaginations. We have taken our holy texts and turned them into weapons to crush any remnants of creativity that might have survived our childhood’s educational incarceration.

Math and programming are not sets of rules to be followed. Math is a language - an incredibly dense, powerful way of conveying ideas about abstraction and generalization taken to truly astonishing levels. Each theorem is another note added to a chord, and as the chords play one after another, they build on each other, across instruments, to form a grand symphony. Math, in the right hands, is the language of problem solving. Most people know enough math to get by. It’s like knowing enough French to say hello, order food, and call a taxi. You don’t really know the language, you’re just repeating phrases to accomplish basic tasks. Only when you have mastered a certain amount of fluency can you construct your own epigraphs, and taste the feeling of putting thoughts into words.

With the proper background, Math becomes a box of legos. Sometimes you use the legos to solve problems. Other times you just start playing around and see what you can come up with. Like any language, Math can do simple things, like talk about the weather. Or, you can write a beautiful novel with words that soar through the reader’s imagination. There are many ways to say things in Math. Perhaps you want to derive the formula for the volume of a sphere? You can use geometry, or perhaps calculus, or maybe it would be easier with spherical coordinates. Math even has dialects, there being many ways of writing a derivative, or even a partial derivative (one of my professors once managed to use three in a single lecture). As our mathematical vocabulary grows, we can construct more and more elegant sentences and paragraphs, refining the overall structure of our abstract essay.

Programming too, is just a language, one of concurrency, functions and flow-control. Programming could be considered a lingual descendant of Math. Just as English is Latin-based, so is programming a Math-based language. We can use it to express many arcane designs in an efficient manner. Each problem has many different solutions in many different dialects. There’s functional programming and procedural programming and object-oriented programming. But the programming community is obsessed with solving boring problems and writing proper code. Too overly concerned about maintainability, naming conventions and source control. What constitutes “common sense” varies wildly depending on your chosen venue, and then everyone starts arguing about semicolons.

Creativity finds little support in modern programming. Anything not adhering to strict protocols is considered useless at best, and potentially damaging at worst. Programming education is infused with corporate policy, designed to teach students how to behave and not get into trouble. Even then, its terribly inconsistent, with multiple factions warring with each other over whose corporate policies are superior. Programming languages are treated more like religions than tools.

The issue is that solving new problems, by definition, requires creative thinking. Corporate policy designed to stamp out anything not adhering to “best practices” is shooting itself in the foot, because it is incapable of solving new classes of problems that didn’t exist 5 years ago. Companies that finally succeed in beating the last drop of creativity out of their employees suddenly need to hire college graduates to solve new problems they don’t know how to deal with, and the cycle starts again. We become so obsessed with enforcing proper code etiquette that we forget how to play with the language. We think we’re doing ourselves a favor by ruthlessly enforcing strict coding guidelines, only to realize our code has already become irrelevant.

We need to separate our mathematical language from the proof. Just as there is more to English than writing technical specifications, there is more to Math than formal research papers, and more to programming than writing mission-critical production code. Rules and standards are part of a healthy programming diet, but we must remember to take everything in moderation. We can’t be so obsessed with writing standardized code that we forget to teach students all the wonderful obscurities of the language. We can’t be telling people to never use a feature of a programming language because they’ll never use it properly. Of course they won’t use it properly if they can’t even try! We should not only be teaching programmers the importance of formality, but where it’s important, and where it’s not. We should encourage less stringent rules on non-critical code and small side projects.

In mathematics, one never writes a proof from beginning to finish. Often you will work backwards, or take shortcuts, until you finally refine it to a point where you can write out the formal specification. When messy code is put into production, it’s not the programmer’s fault for being creative, it’s the idiot who didn’t refactor it first. Solving this by removing all creativity from the entire pipeline is like banning cars to lower the accident rate.

Corporate policy is for corporate code, not experimental features. Don’t let your creativity die. Stop following the rules.