Boost QVM provides a set of generic functions for working with quaternions, and vector and matrix types of static size. All operations use a type-traits system, which enables types from other vector/matrix libraries to be integrated in a common type-safe interface.

The current source code and documentation is available here. It contains minor bug fixes, and the following new features:

- view proxies that negate matrix rows and columns (negr/negc)

- view proxies that swap two rows or columns in a matrix (swapr/swapc)

- functions for indexing at run-time of any vector or matrix object of arbitrary size.

Background

In photography, depth of field is an artistic effect that makes objects in the picture appear sharper or blurrier depending on their depth (how far away they are from the camera.) Here are a couple of examples (images courtesy of Wikipedia):

The following diagram shows the depth of field graphically, however keep in mind that there isn't a sudden drop in sharpness: in any photograph, only a single plane is in perfect focus -- at all other depths, the sharpness varies smoothly.

The blurriness is an artifact of projecting the scene onto a 2D surface using a lens. In the case of a camera, the 2D surface the image is projected on is the CCD; in the case of the human eye, it is the retina.

In general, a point from the observed object isn't projected into a single point on the 2D surface. Depending on the geometry of the lens, the depth of the object in the scene, and the distance between the 2D surface and the lens, a beam of light from the object will hit an area on the 2D surface which looks something like a circle, technically called the circle of confusion:

An important physical property of the retina is that it is composed of many individual photo receptors. Depending on the circle of confusion, the projection of a point from the scene will hit a different number of these receptors, and so the bigger the circle of confusion, the blurrier the object appears and the less detail is available for the brain to see. To compensate, the eye continuously adjust the geometry of its lens, minimizing the circle of confusion for the object we're focusing on, and that makes it appear sharp.

A CCD is also composed of many individual photo receptors, and so the effect of the circle of confusion on the resulting image is very similar to the effect it has on the retina. This is what makes depth of field such an important artistic tool in photography: it removes detail from parts of the image depending on their depth, very similarly to the way refocusing the lens of your eye does it normally. So, the brain focuses on the sharp areas of the image by default.

Depth of field in movie production

A lot of the depth of field effects you see in movies are done in post production. This means that they aren't a result of the physical properties of the lens the shots were taken with. In other words, they're fake.

Since each frame is affected by the circle of confusion, even sharp objects are not uniformly sharp: with high enough resolution, a small amount of blurring can be seen throughout the image. So, some algorithms for faking depth of field effect in post production simply increase the blurriness present in the image, which already depends "correctly" on the depth.

Depth blur

In computer graphics, raytracing techniques can easily be adapted to simulate lens and the resulting circle of confusion. However, games and other real-time applications use simple polygon rasterization to display images. There is no lens, and there is no circle of confusion. So, not only depth of field has to be faked, but it can not be faked by increasing the blurriness that already exists in the image, since the image is perfectly sharp (more precisely, any blurriness in the image has nothing to do with depth.)

Realtime depth of field effects are done as a post-effect, meaning, they operate on the final 2D image after all 3D rendering and lighting has been completed. The technique is sometimes called a depth blur, because it applies varying amount of blur to all pixels based on their depth. Here is a capture of what this looks like:

Depth blur is typically implemented in 3 passes:

A final refinement

Simple depth blur doesn't produce satisfactory results in general. Consider a foreground object in focus that is in front of a background that is supposed to be blurred. The background pixels that are immediately next to pixels of the foreground object must be blurred, meaning, some of the color from the neighboring objects should bleed into them -- but not from the pixels that are part of the foreground (in-focus) object. To get a correct result, we need to blur with pixels that are behind (deeper than) that object, and the problem is that we don't have those pixels.

Therefore, if we simply blur based on depth, a foreground in-focus object will bleed onto the background. To our eyes, this looks very wrong.

One possible fix is, in the last step where we average the 7 or 8 samples interpolated by their corresponding depth, we could exclude in-focus pixels that are closer than the rest of the samples. The results produced by this simple hack turned out to be quite satisfactory for us.

Here is the final result -- note how the foreground in-focus object does not bleed into the blurred background.

But one of the most common problems programmers inflict on themselves is when they try to use the static type checking built in C and C++ compilers to detect bugs due to integer conversions that result in loss of precision.

Let's say in a class called point, we have reasons to store X and Y as shorts rather than ints:

Right, we might have a problem. On most platforms, the int and short types are 32- and 16-bits in size, respectively. This means that the call to the point constructor may result in loss of data.

It would be very nice if we could get the compiler to point out all instances where an int is implicitly converted to a short, so that we can verify that the loss of precision is desirable or at least that it isn't a problem.

So we enable the appropriate warning:

What makes this especially desirable is that function (and constructor) declarations are usually separated in a header file. The thinking is, if a careless programmer calls the constructor with int arguments, the compiler will point out the possible problem, the programmer will inspect the code carefully to confirm that the loss of precision is OK, and then... Well,

Then what?

What do you say? Casting? Yes, this situation is a textbook example for using casts:

The trouble is, in the original program, the compiler would have truncated x and y only if they needed to be truncated. The program that uses casts to avoid the warning will truncate x and y even if they don't need to be truncated.

We've changed the semantics of the program in a way that's not just dangerous, it's more dangerous than the potential bug the warning was intended to detect. If during later refactoring we realize that we do need the extra precision of int, the point class will have to change accordingly:

And now we don't have a warning but we have a nasty bug, all because we explicitly instructed the compiler to do something bad (cast), something that it's carefully designed not to do!

The source of the bug is the ill-advised attempt to use static type checking to detect what is inherently a run-time error. Converting an int to a short is dangerous only if the run-time value of x exceeds the valid range for short integers. A better approach is to ditch the warning and the cast it comes with, and use assert:

But now... even if we assume that programmers will always assert before calling foo (quite an assumption!) the resulting code is pretty ugly to look at.

To solve the problem, we need to take a step back and look at the original reasons why the point constructor takes shorts instead of ints. Clearly, this is because the values are copied to the members of class point, which are of type short to save memory. Note, however, that the savings come from the point members, not from the constructor itself taking shorts -- the latter was done for "consistency", which A) doesn't make it correct, and B) as we'll see later isn't even consistent.

First, we should make the constructor take int parameters regardless of the type of the (private) members:

This promotes consistency throughout the program, regardless of what type the members of class point are this week. The constructor is also the perfect place to put our asserts, thus completely relieving the caller from the burden of truncating ints to shorts.

Second,

C++ and C are obsessed with ints

Using short or char in any kind of integer expression ends up promoting them to int anyway. This can be illustrated by the following program:

The typical output of this program is:

Note that it prints 131070 for x+x, even though x is of type short and (for 16-bit shorts anyway) wouldn't be able to hold that value. That's because x+x is of type int.

As another example, if we pass something like x+1 (which would be pretty common) to a function that takes short, the program will first produce an int which is then truncated to a short as part of the function call (and I'm not aware of a way to make compilers issue a warning in this case, not that it would be desirable anyway.)

The best way to be consistent is to use the consistency of C and C++ to always promote small integer types to int. This means to forget about char and short as function arguments; they are (almost) never justified. The net effect of using them is that the program will contain a lot more places where data gets truncated, which makes it more prone to bugs.

Avoiding char and short function arguments is not ideal, but it is better than using dangerous casts to suppress a retarded warning that should never have been enabled to begin with.

void foo( short x );

void bar( int x )
{
  foo(safe_cast<short>(x));
}

One of the projects that I've started years ago and never finished is a version control system. The main problem I have with Subversion, Perforce, Git and the like is that they're way too slow for us game developers. In games, besides code, we need to store very many and very large binary blobs. So many that even over a gigabit local network syncing the entire project tree to the latest revision is a major pain.

The net effect is that developers become hesitant to syncing: your local revision of the project is in good working order, why would you bring in changes that might break it? The answer, of course, is that frequent syncing makes merging easier and more reliable. Yes, you might sync to something broken, but why is this a problem? You have a version control system right? You should be able to undo a situation like that in no time!

But you can't. It takes forever to sync! So you keep working, until you're ready to commit. At this point you *should* first sync, but you don't. It takes forever to sync and forever more to undo a bad sync!

Is it possible for syncing to work faster? After all, the version control system already uses binary deltas and you can't easily improve the speed of your network. So it boils down to how many and how big your files are, nothing can be done about that right? Not quite.

Regardless of how large the files are, they are all being created and modified by people; and regardless of how productive people are, in practice all changes they make are highly localized. People work on individual files, and compared to the size of the entire project tree even Photoshop files are tiny on their own.

So, there is no reason whatsoever for the version control system to wait for me to request a sync before it begins to transfer the data. In fact, there is no reason whatsoever to wait for someone to commit a change. As soon as a file is modified locally, that change can be mirrored to all other users who are likely to need it in the future. That way whenever they're ready to sync, the operation would involve moving a bunch of local files. And that *is* fast.

Does such a version control system exist? Is it possible to emulate this behavior with existing software? Is there any reason why such a design is undesirable?

Type safety as seen by fans of value-typed languages

Languages as seen by fans of other languages

Microsoft languages as seen by fans of other Microsoft languages

Why Otter and not Scaleform? Perhaps the most important design decision for any middleware is where it draws the line in the sand: how much it does, and how much it relies on the game to provide. You don't want it to leave a critical and difficult problem for the game to deal with, but you also don't want it doing trivial things, which often makes the middleware unnecessarily rigid and inflexible.

In a nutshell:

• Otter does not use Flash, so it comes with its own animation editor.
• Otter doesn't have a script of its own, which means that the UI logic can be implemented in C++ or in Lua. This removes the need for a separate Flash interpreter in your game.
• Otter's runtime (the "player", in Flash terms) does not do any rendering. Instead, it just tells your game what textures to load and what polygons to draw -- which makes it very portable. Besides, it integrates seamlessly in your engine's shading framework.

Lastly but perhaps most importantly, the Aonyx team has been a pleasure to work with.

He showed me a union similar to this:

The idea here is to use the union, bar, to convert foo to network byte order when sending, and (if necessary) back to host byte order when receiving.

Even if we set aside the obvious issues of size (we don't really know that an int is 32 bits) and aliasing rules (if you write x in the union, reading y is undefined behavior), such code is buggy also because when bitfields are used, it is unspecified whether the bits are allocated from the least significant to most significant bytes, or the other way around. The code worked on Windows only because both peers are compiled with the same compiler.

But what caught my eye was the int bitfield of size 1. Clearly, you can store two values in it, and it is safe to assume that one of them is 0. But what is the other value? I wasn't sure.

My thinking was, if the 1-bit two's complement format is used, then the possible values would be -1 and 0. But then again, we're talking about a bitfield, and in fact a 1-bit bitfield, so 0 and 1 also seem logical values.

It turns out, the C standard states that the behavior in this case is implementation-defined.

What's more, if a bitfield is of type unsigned int, then it is unsigned, but unless you explicitly say signed int, it is implementation-defined whether you're going to get a signed or unsigned int!

So, going back to the original 1-bit bitfield value of type int, it is implementation-defined whether its range is [-1,0] or [0,1].

In reality this subtlety is difficult to notice for 1-bit bitfields, because in boolean contexts 0 is false, and both -1 and 1 are true. However, to avoid portability problems, when larger bitfields are used, signed should be specified explicitly if negative values are needed.

The colorful balls bounce away from the cursor and that's lots of fun I suppose, unless you're a geek and you notice that OMG this stupid little animation is taking 100% of my CPU time running at no more than 10 frames per second! And that comes from the same company whose product happily announces that it has found more than a billion results in 0.25 seconds. I know, not a fair comparison, but still -- I wonder how many millennia would the search engine need to find a billion matches had it been running on Javascript or whatever advanced, Just-In-Time compiled, Virtual Machine powered, Garbage Collected, uber-secure engine powers the colorful balls.

What's the big deal, you say? It's just a bunch of colorful balls, they'll be gone in a day or two!

I wish the same could be said about Java in general. Whenever I run any Java-powered program on my computer, even when the program is idle, the OS often needs to power up the fan. To collect a dead object perhaps, who knows. The point is, ever since Java's arrival, we've heard the same mantra over and over: "Oh, it's slow now but don't you worry it'll get faster. Soon. Like, tomorrow. JIT FTW!"

I've lost count on how many years I've been hearing that.

But aren't these colorful dots fun anyway? Not if you realize how wasteful and inefficient the whole thing is. It really is a Googleplex slower than it should be. :)

LA stands for Linear Algebra, but the initial feedback I got made it clear that the name is incorrect. To make the library domain clearer, I've decided to rename it to QVM, which stands for Quaternions, Vectors and Matrices.

Click boost-qvm.zip to download the source code and tests. This is a very preliminary announcement but of course I welcome all feedback here or privately at emildotchevski@gmail.com. Unfortunately I have not yet updated the documentation; for now, please refer to the original (Boost) LA documentation which is correct semantically, but keep in mind the differences I've outlined below.

Operator| "pipe" overload gone

Based on feedback, I've removed the operator| "pipe" overload which was used to chain up view proxies. View proxies can be used to access (with zero abstraction penalty) an object "as if" it is of a different type. For example in (Boost) LA you could say:

to multiply column 1 of the matrix m, as if it is a vector, by the scalar s. In (Boost) QVM the following expression achieves the same result:

Simplified header files

Also based on feedback, I have consolidated the very many and small (Boost) LA header files into much fewer files. This makes using the library simpler.

A new naming convention helps make header file names shorter:

• "q" stands for quaternion, "v" stands for vector, and "m" stands for matrix.
• numbers indicate dimensionality, so 2 means 2D, 3 means 3D, etc.

For example, to get function overloads that can be used with any vector type, you'd #include "boost/qvm/v.hpp", while if you only wanted to work with 2D vector types, you'd #include "boost/qvm/v2.hpp". To get operations between matrices and vectors, you'd #include "boost/qvm/vm.hpp" or "boost/qvm/vm3.hpp" if you needed only the 3D overloads.

Header files defining view proxies are named depending on the type of the input and the output type; for example view proxies that map matrix types to vector types are defined in "boost/qvm/map_mv.hpp".

New namespace sfinae

The main namespace boost::qvm contains all (Boost) QVM types and functions. All function and operator overloads found in boost::qvm which use SFINAE are also available in the new namespace boost::qvm::sfinae. Therefore, while

may introduce ambiguities, it should now be always safe to say

The above directive does not bring any types in scope. The introduced overloads are extremely generic (meaning, any overload that takes a specific type will take precedence) yet are only available for types for which the appropriate boost::qvm::q_traits/v_traits/m_traits is defined.

Element access

The main innovation in this library is that it uses SFINAE to define operations which kick-in for any appropriate types, including user-defined types. This is what enables the view proxy functionality, which would have been impractical if each of the matrix or vector types it produces had to define its own operations.

This design needs a way to access quaternion, vector and matrix elements generically. Traditionally, vector and matrix types overload operator[] or operator() to provide element access, which is impossible to do generically since the C++ standard requires them to be member functions.

Using a function such as get<Y> or something similar to access elements is not very practical, so (Boost) LA used operator| overload for that purpose. (Boost) QVM uses operator% instead, because it has higher precedence (refer to this link). For example, in (Boost) QVM, to access the Y of a vector you'd use the following notation:

The same syntax is used for swizzling view proxies, for example:

Yes, a telephone was much easier to use in the 70s, but then again it didn't do that much, did it? Could you imagine having to memorize the phone numbers of everyone you need to text or call? Right, that would have sucked. How about having to fast forward in order to get to the next song on a compact cassette? Ouch.

Yet, some things from the past are worth admiring. To me, a steam engine is prettier than the most advanced internal combustion engines of today. Not really practical, yet pretty.

But I'm a programmer, and a lot of the old stuff I admire is software. And while I have (if only once) programmed a computer with punchcards, those were already antiques when I was in school; the computer I grew up programming was the Apple ][.

So here we go: at the risk of wasting my time raving about something most programmers today can't appreciate, I'll try to explain but just a tiny bit of Wozniak's brilliancy:

The Apple ][ floppy disk controller bootstrapping routine

Some background: on physical magnetic media, you can't "just record data". Instead, 1 is encoded as a magnetic polarity transition (also known as flux reversal), and 0 is encoded as, well, lack of transition. Basically, for each bit there is a limited time window in which flux reversal is expected to occur. If it occurs, the bit is 1, otherwise it's 0. The problem is that the time window is so small that there is a limit on the accuracy with which the data window length can be measured. So, while detecting a series of ones is not a problem, it's difficult to know how many zeroes are encoded in a measured period of lack of flux reversal.

Wozniak's original hardware design imposed two constraints on the raw data:

• between any two 1-bits, there can be no more than one 0-bit, and
• each 8-bit byte must start with a 1-bit

However, using simple FM encoding "wastes" 4 bits per raw byte, which would allow only 10 256-byte sectors per track to be recorded. Instead, he devised a more complex encoding scheme that was based on the fact that there are 34 8-bit numbers which have the top bit set and no two 0-bits in a row. That way, 13 sectors per track could be recorded. Later on the hardware design of the floppy disk controller was modified to allow no more than one occurrence of two consecutive 0-bits in a byte, which lead to different encoding called 6&2; it allowed 16 sectors per track.

A conventional floppy disk controller design would put all this bit twiddling in silicone which just DMAs the decoded bytes in memory -- but it would cost more in hardware. So what is a Wozniak to do? Obviously: screw hardware, do everything in software.

That would have been impressive enough on a 6502 CPU, but even more impressive is what is required of the bootstrapping routine. It must:

• generate the 6&2 decoding table in RAM
• seek the disk drive to track zero
• look for the beginning marker of sector zero and read the raw data in RAM
• decode the data and jump into it

...all in no more than 256 bytes of code, which is the addressing limit for the ROM on Apple ][ expansion cards.

By the way, there are no timers on the Apple ][, all timing is based on the CPU clock, e.g. you'd know that an INX instruction takes 2 microseconds to execute. The 6502 has three 8-bit registers: an accumulator A which can add, subtract, shift, rotate, and, or, xor, etc., and two 8-bit index registers X and Y which can do none of those operations. :)

Here are some pictures I found of Bulgarian-made Apple ][ clones: the first two are of Pravetz-82 from the late 70s/early 80s, the third picture is of Pravetz-8C from the late 80s/early 90s. These Bulgarian computers were compatible with Apple ][, but their evolution didn't entirely follow the evolution of Apple ][, e.g. some models didn't have an exact original.