It seems I've been neglecting this blog recently, almost a two month break since I last posted on here. Last time I said I was taking a break from Myriad, since Tom was updating the UI system, well I haven't actually resumed the main project yet! My SVN server went down and I've been working on getting another back up since then. So, what have I been working on?

Recently I've been putting some work into the terrain system. I have talked about this subject before, both the general concepts and more in depth about screen space error. This time I have been working on a robust triangulation system

First, what're my requirements, what do I want from this landscape?

• Render a planet


• High detail in front of the camera


• Landscape can be deformed at any time

Quite some requirements I have there! However, it turns out they can be simplified down a little. A planet can be rendered as 6 flat planes making up a cube, this isn't the best way of doing it but it's certainly the simplest! In the case of a cube I have 6 faces/12 edges to handle, in the case of an Icosahedron (which is a much better shape to use) I have 21 faces and a silly amount of edges. Yay! we've simplified our requirements to:

• High detail in front of the camera


• The landscape can deform

Now, I can simplify them once again. The works to maximise detail by subdividing vertices with the largest screen space error, this means that vertices in front of the camera have the highest detail, the clever thing here is that if the landscape deforms the system will suddenly think that all the vertices involved in the deformation have huge screen space error and will subdivide them, compensating for the change and nicely animating the deformation.

Brilliant, I've now reduced my requirements to a system for handling drawing high detail in front of the camera for a landscape, which turns out to be rather simple. First, my plane of landscape is a square floating in space. Now add all my nodes (at the moment only one) to a heap ordered by screen space error, subdivide the node on top of the heap into 4 smaller nodes (forming a quad-tree), add the new nodes to the heap and remove the original one. This operation can simply be repeated many times, which will continuously subdivide the node which needs subdividing the most, even better as the camera moves the screen space error will change to reflect the movement so no special handling is needed for that.

But, I can already hear your protests, won't the number of nodes keep growing? I'm glad you asked! Now we can simply pop the node off the bottom of the heap and Merge it (ie. destroy all children of this node). I can already hear your follow up protests to that statement, removing from the top of a heap is a wonderfully efficient O(logn) however removal from the bottom of a heap is a rather nasty O(nlogn). Not in my case! the heap I'm using is a Min-Max-Heap, which allows me to extract both the minimum and maximum in O(logn).

So we're ended up with a quadtree which can be subdivided and merged to have the most detail in front of the camera. All we need now is to get a mesh from this tree, which is an exercise I leave to the reader...

Not really, I'm going to cover triangulation in my next blog post, and then write a tutorial on Min-Max-Heaps in C# after that.