Source code: Implementing Direct3D for fun and profit

Almost a year and a half ago I blogged about several useful things that you can do with custom IDirect3DDevice9 implementations. I don’t know why I did not post the code back then, but anyway – here it is:

dummydevice.h – this is just an example of a dummy device implementation; it implements all device methods with stubs that can’t be called without a debugging break. This is useful for other partial implementations.

deferreddevice.h – this is the implementation of the device that buffers various rendering calls and then allows to execute them on some other device. Note that it lives in a fixed size memory buffer, which can be easily changed, and that it implements only a subset of rendering-related functions (i.e. no FFP).

texturedevice.h – this is the implementation of the device that works with D3DXCreateTextureFromFile for 2D textures and cubemaps (3D texture support is missing but can be added in the same way).

DL_BREAK is the replacement for __debugbreak, DL_ASSERT is a custom assertion macro (with neat (void)sizeof(!(expr)) trick that I hope everybody knows about by now), everything else should be obvious.

Posted in Direct3D | 3 Comments

Quicksort killer sequence

Today I’m going to describe a not very practical but neat experiment, the result of which is a sequence that’s awfully slow to sort using Microsoft STL implementation; additionally, the method of generating such sequence naturally extends to any other quicksort-like approach.

First, a quick refresher on how std::sort [in Microsoft STL] works. It is a variant of introsort with insertion sort for small chunks. It proceeds as follows: Continue reading

Posted in Algorithms, C++, Sorting | 2 Comments

AABB from OBB with component-wise abs

This post is about a neat trick that is certainly not of my invention, but that should really be more well-known; at least, I haven’t heard of it till I stumbled across it while reading Box2D sources.

There are a lot of bounding volumes out there; the most widespread are certainly spheres and boxes, which come in two flavors – axis-aligned bounding boxes (AABB) with faces parallel to the coordinate planes, and oriented bounding boxes (OBB), which is essentially a AABB and an orientation matrix.

It’s common to use AABB in spatial subdivision structures, like octrees, kD-trees, ABT and so on – the intersection test between two AABB is pretty straightforward. However, when dealing with dynamic meshes, it is needed to recalculate the AABB of the mesh when the mesh transformation changes. Continue reading

Posted in Mathematics, Optimization | 2 Comments

Death by static initialization

The language war in game development is long over – and the winner is C++. The utmost majority of code that’s going to run on the users side (engine code and game code) is written in C++. This is mostly not because the language is good, but because there is no better alternative.

Many features of C++ carry some penalty in different areas – performance, memory overhead, compilation time, code flow clearness, etc. The great thing about the language is that you usually can avoid using the feature where you don’t need it or would rather do without.

One powerful feature in C++ (which is, by the way, present in most high-level languages, like Java, C#, Python, etc.) is static initialization. In the days of C the only code that ran before the main() was the CRT startup code – basically, nothing interesting ever happened outside of main(). Continue reading

Posted in C++, Memory | 6 Comments

Taking testing seriously

As I’ve written in the previous post, there is a long way to go from first tests to the complete testing suite. Without further ado, here is the list of things I consider important for a test suite of a middleware product. Some of the items here are only relevant for the case where you want an automatic continuous integration-style testing – they’re marked with asterisk (*).

  • Get a good testing framework. With a good framework you have to be able to add a new test in a couple of lines of code, and add a new check in a single line of code. Continue reading

Posted in Testing, XML | 2 Comments

Testing libraries is important – who knew?!

Four years and a half ago, I was working on a pet game project which used XML format as intermediate storage format. Initially we used TinyXML, but I got tired of its interface and horrible parsing performance, and found pugxml. It was somewhat faster, with the interface which was somewhat better, but still – it was very rough. I decided to slightly change the library, improving performance and design along the way. Thus pugixml was born.

Little did I know at the time, that in five years I’d still be working on the same code. The amount of code and documentation is nearing a megabyte (the library itself is 280 kb, the rest is samples, tests and documentation), the revision number is 750+, hardly any original code is left untouched – it’s not a weekend affair anymore, that’s for sure.

In 2006 I took a very different approach to programming; initially the library had no tests at all. When I started developing an XPath implementation, Continue reading

Posted in Testing, XML | 1 Comment

There’s more than one way to map a cat

There are lots of data structures out there, ranging from primitive to so sophisticated that only a single person in the world understands them (these are, of course, mostly useless). The choice of the data structure is mostly specific to the problem; however, obviously some data structures are generally more popular/useful than others.

I’d say that the most generally useful data structure in the imperative world is an array. Arrays are as good as you can get if you do not need fast searching over large datasets – they have a simple efficient memory pattern (unless you need a multi-gigabyte array), leading to fast iteration, they have minimal meta data (per instance cost is zero), they can be indexed in guaranteed constant time, array transformations are trivially parallelizable, they generalize to multiple dimensions easily, etc.

However, in functional world, from my limited experience it looks like the favorite data structure is a consed list, which is better known as a singly-linked list. Continue reading

Posted in F#, Functional | 2 Comments