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.

Draw a picture

It's still somewhat of a sketch, but no idea if I'm ever going to develop it futher. Coloring was done really quick (probably about 5 minutes total) so the shading is off in a lot of places, I know.

A little teaser..

So here's a small screenshot of a filter. It's still lacking text labels and I'm not quite sure about the color scheme, but it's using the vector graphics library thingie.

The library itself needs a bit of tweaking before anything using it goes live. Maybe I'll release the library itself as well at some point, I don't know yet.



I was a bit worried about the performance, since it seemed to slow stuff down when redrawing a lot. That could happen for example when another window was moved on top of the thing. What was a bit strange though, was this would typically only happen after a while...

I was already going to write some bitmap caching logic to avoid doing the actual drawing unless something really changed in the window. Then my eyes caught something missing: I was leaking resources in my painting routine. Single line of code to fix that bug. Now it runs pretty nice just redrawing everything on the fly.

Subdivision made visible

I'm currently working on stroking, and trying to come up with a decent algorithm for that stuff. The big problem here isn't really how to code stuff, but rather what things should look like.

Anyway, in order to visualize some problems for myself, I draw a stroke around a stroke. Then I got the idea that if I modify it a little bit, line segments will become visible, and I kinda liked what the result looked like, as it nicely illustrates the bezier subdivision done.

So in the picture below, there is a cubic bezier, which is subdivided into line segments. Then each of these line segments is made 15 pixels wide, and filled with white. Finally those are stroked with a black outline, which makes each individual segment clearly visible.

Elliptic arcs and some more pron

So far the hardest problem to solve turned out to be how to parametrise arcs. There are three obvious parameters, namely a control triangle of the rational quadratic bezier that is the arc. But how to get a weight for the middle point?

After playing with different parametrisation, I currently have one which gives the middle point the weight of cos(angle/2) where angle is an extra parameter to the function. It happens that when the legs of the control triangle are of equal length, and the angle between them is supplied as angle, one gets an arc of a circle. When the legs aren't of equal length, or the parameter isn't the angle between the legs, one gets an ellipse instead. For zero angle one gets normal non-rational bezier, and for angle pi one gets a straight line. Larger angles give the other side of the ellipse or circle.

Bonus benefit is that when the curve is subdivided in the middle, one doesn't need to track weights for the control points. Just using half the angle will give the proper midpoint weight.

For the typical uses of arcs, there's an extra function which simply makes the guess that the angle between the legs will probably be fine. For stuff like corners of polyline strokes or rectangles this seems to be a reasonable value.

And naturally we have a sample picture:



In the picture you see 3 elliptic arcs, one line and one cubic bezier.

Beziergons

Did I miss the deadline?

Two dimensions for a change

Haven't got much of anything interesting added to the synthesizer thingie during the last few days. Instead, I've actually played around a bit in two dimensions. For a long time I've wanted a simple vector graphics library. A few days ago I started playing with the math. The result is rather boring system based on a couple of simple principles:

1. There is canvas, masks, and paint; paint is applied to canvas through a mask.
2. Geometric primitives (= line paths) work with masks.
3. Colors, gradients, bitmaps, whatever, work with paint.
4. To draw a white triangle, cut a triangle shaped hole in a mask, apply white paint.

The result looks like this (smaller one is screencap, bigger is the same thing magnified):


Now, at this point there isn't even a datatype for a path, so the individual lines in the mask must be drawn separately, but fixing that isn't a huge amount of work (actually probably less than writing this blog post). And I'd expect stuff like beziergons to work before christmas.

Now, what is nice about the design, is that as you see it antializes rather beautifully. It actually draws what you'd get by doing 16x16 naive supersampling and averaging down. Ofcourse all the supersampling is internal to the line drawing function. I'll probably make it 256x256 when I have the extra minute to tweak the algorithm a bit more.

The whole thing is a very basic scanline rasterizer, so the trick really is in the scanlines. Now a scanline rasterizer works by incrementing a counter every time it crosses a line going up, and decrements a counter every time it crosses a line going down. Then you typically fill when you've got either non-zero or odd number in your counter, depending a bit on what you want.

The antialising then is actually quite easy, just a question of putting fractional values in the scanline buffer, and drawing an anti-aliased line. The only important thing then is that the line drawing function makes sure that when one starts from left side of the line, and sums all the pixel values until one has crossed the whole line, the result is exactly one. In a sense, what is being drawn is the finite difference of the edge of an antialised half-plane. And I actually got the idea originally from anti-aliasing audio with BLEPs. Don't ask.

And the best thing? Since integration (and differentiation) are linear operations, one can draw each line independently, and just integrate the scanlines at the end. There aren't really any special cases whatsoever.

Ps. I'm not sure if the above makes any sense. I might consider a better explanation some other day, but I now have to add those beziergons. :)