Premultiplied in GIMP

This is really just a note to self (because I keep forgetting how to do it): when you want to do pre-multiplied stuff in GIMP, first take the image with regular alpha into a layer, then create layer mask (specify "copy of layer's alpha channel"). Then set background color to black and remove alpha channel from the layer (but keep the mask). This way the layer gets blended on a black background (effectively pre-multiplying it) and the layer mask keeps a copy of the alpha channel intact. This can then be saved as PNG or whatever and it'll look right when blended as pre-multiplied.

How to split quads of a height-map terrain?

Recently I needed to import some basic terrain height maps for a prototype project. It quickly became obvious that in order to get "smooth" geometry (whether you want it smooth for rendering, collision detection, or both) it's important to pay attention to how the terrain quads are triangulated. The problem is that even on a smooth heightmap most quads will not be planar, so two different ways to split the quad into two triangles will result in different geometry. Most of the time one of these is much worse than the other (sometimes neither is ideal, but at least you pick the "less bad" one). I'd also like to note that adding a vertex in the middle of the quad to get four triangles instead of two actually tends to make things worse on top of doubling the triangle count.

After searching the web for an algorithm and finding out that some big-name engines (eg UE3 docs about the issue just to name one example) just seem to let you set the orders manually, I ended up rolling my own algorithm. I'm not going to claim this is the best possible algorithm, nor am I going to claim it's novel or anything, but since it's very simple, works almost perfectly as long as the source data isn't awfully noisy (in which case any order tends to be bad), and I haven't found any other algorithms published I thought I'd share it here:

So, first do any non-uniform scaling of the heightmap terrain data such that we have a 2d array of 3d coordinates of the terrain vertices. Now for each vertex, calculate diagonal (one for each diagonal direction, on-axis doesn't work nearly as well because the problems occur in diagonal directions) two-sided finite-difference (eg [-1,0,1] kernel) "tangents" for each point (in 3d), then do a cross-product of the two "tangents" to get a "normal" and normalize the result. These "normals" are not that great for shading (you want to use something more sophisticated to calculate final normals), but take a dot-products between these "normals" at diagonally opposite corners of each quad, compare the results from the two diagonal pairs, and split the quad by adding an edge between the pair that gives the larger dot-product (ie have more "similar" normals) and you have an algorithm that will choose the better split order with "surprisingly large probability", even when neither of them is ideal.

That's not very complicated, nor did it take very long for me to come up with the algorithm. I'm sure more intelligent people could come up with much better algorithms, but if you just need "something" (so you don't need to rely on manual ordering) the above should provide you with a decent starting point.

Z-buffer precision, camera pivot and optimal zNear

Everyone who has done any non-trivial 3D programming knows that sooner or later you run into problems with z-buffer precision. Especially a first-person situation you can have objects very near to the camera, which should not clip against the near-plane. But you also want to draw objects far away (say hills to the horizon). So you need a small zNear and a large zFar which runs into problems with precision, because of the non-linear screen-space z.

There are well-known solutions from depth partitioning to distorting the z values, but sometimes you just need a "bit more precision" and the above solutions just cause more trouble than they solve. If only you could move the zNear a bit further away.

Let's look at a first-person situation. The necessary (and sufficient) condition for avoiding any near-plane clipping (with any colliding geometry at least) is to place the near-plane completely inside the collision sphere (for rotational symmetry) of the camera. This can be a collision sphere of a player, or it can be the largest sphere that will fit inside the AABB or whatever else we collide with.

The question is, what is the largest possible value of the zNear (for a given field-of-view) that will keep the near-plane completely inside the collision sphere? Well, it depends on where you put the "eye" point.

As should be obvious in the image, the near-plane (and hence the zNear distance) is larger in the right-image. The largest possible near-plane that will fit inside the sphere will always go through the sphere origin. It is important to realize that it doesn't matter (at all) whether the "eye" is inside the collision sphere: anything behind the near-plane will get clipped anyway and the eye is purely virtual. Both placements will avoid any near-plane clipping as long as no geometry gets inside the sphere.

In practice first-person cameras (and other cameras that you turn directly) usually use the example on the left (it's quite obvious when you zoom: if you don't see any "parallax" movement when turning, then it's using the "left" version). This is what any text-book view/projection matrices will give you (eg D3DX helpers and whatever) unless you explicitly move the camera somewhere else.

Now, I would like to argue that the placement on the right is better even if you don't have precision issues, because it ends up feeling much more natural (on top of giving you larger optimal zNear which is easier to calculate). To understand why, we need to think of the "near-plane" as a lens. Then for a narrow field-of-view (eg high zoom) the "virtual" eye should end up behind the "real eye." The pivot point then should be much closer to the lens than the virtual eye position.

When I actually tried this in practice, I immediately realized why zooming in most games has always felt "wrong" as far as turning goes. It's because the pivot is in totally wrong place with regards to the view. By placing the pivot at the near-plane I ended up reducing the feeling of "tunnel vision" significantly and high-zoom no longer felt "shaky" at all. Turning actually gives you a sense of depth too (because of the slight parallax movement). You also see slightly more to your sides, which reduces the pressure to use high field-of-view for observing your surroundings (and you no longer need high field-of-view to combat the weird pivot either). All that on top of getting 4-8 times (well, it's FoV dependent; with more "zoom" you get larger zNear and hence more precision out in the distance) as large zNear without any near-plane clipping. I can't name a single negative really (go ahead and post of comment if you disagree).

So given a collision sphere radius and field of view, how do we calculate the optimal zNear when the near-plane goes through the camera origin? It turns out to be quite simple. Something like the following:

// fovY is vertical field of view in radians
// aspect is screenWidth / screenHeight
// solve half near-plane diagonal for nominal zNear = 1
float diag = tan(fovY / 2.f) * sqrt(1.f + aspect*aspect);

// solve zNear for diagonal to equal collision radius
float zNear = collisionRadius / diag;

Now you can calculate view matrix as usual, except move the camera backwards by zNear, because "camera" is really the "virtual eye" and we want near-plane through origin of the "real" camera.

Why is math (written) so complex?

It's been ages since I wrote to this particular blog, but rather than make a new blog I'm going to use the existing one to mention some things that are in my mind these days.

We're going to start our series of rants with quaternion rotations. Now if you check the link, you'll find some annoyingly messy (long, error prone to type) formulas for converting a rotation quaternion into a 3x3 rotation matrix. As far as I'm concerned this is yet another perfect example of how people tend to make math unnecessarily cryptic.

Let's assume that we can multiply quaternions and use this to rotate vectors (see the link, it's simple enough). Now if we rotate axial unit vectors (1,0,0), (0,1,0) and (0,0,1) using the quaternion, we end up with a rotated basis that we can turn into a matrix simply by using those rotated vectors as the columns of the new matrix. It so happens that the resulting matrix is the rotation matrix that we want.

Now for efficiency purposes (in code) one might (if you don't trust your compiler's optimizer) want to write out the formulas, so all the products with zero can be dropped and all the products with one skipped and then simplify the remaining stuff a bit... but why do such premature optimizations when writing math for humans to read (as in Wikipedia) is just totally beyond me.

PS. I figured I could take the opportunity to also complain about the general hand-waving about adding scalars and vectors in the above mentioned Wikipedia article. The whole issue could be easily eliminated by defining vector i=(i,j,k) and taking a dot-product with the vector part of the quaternion. Then you'd end up with a+vi which becomes type-safe being all scalars now.

Watch out for the angry kernel

After approximately 12 hours of trying to compile the thing after tweaking the source very slightly in order to fix a minor inconvenience:

teemu@opensolaris:~$ uname -a
SunOS opensolaris 5.11 on111b-teemu i86pc i386 i86pc Solaris

And now I just hope it actually fixes the original problem and that I won't run into any driver problems...

plugin project has a site

Ok, nothing much yet, but at least I've got something, and now I've got a place to host my stuff that doesn't fit that well into a blog.

You can find it here: www.signaldust.com

What if...

What if there was no lambda in Lisp, but if defun returned the function defined? Wouldn't it be possible to define a macro such as:

(defmacro lambda (args . body)
  `(defun ,(gensym) ,args . ,body))

Please excuse the half-Scheme notation.