One of the things that Myriad has is a big (and deformable) landscape, this presents some challenges for rendering the landscape. Firstly the landscape is way too big to render all of it at the maximum level of detail, secondly when a deformation is in progress we want to see it animated, finally the landscape is actually spherical, which has a few of its own issues. I have come up with my own algorithm for detailing the landscape in real-time (none of this is tested yet, it's to be implemented after I have written this blog post).

My algorithm is split into two stages:
1) Subdivide/Merge
2) Triangulate

Subdivide/Merge
This section of the algorithm creates new vertices. Firstly it has all the traignles in a double ended priority queue ordered by screen space error. There is a target vertex count, and a current vertex count, if more vertices are needed then the triangle with the biggest screen space error is extracted and subdivided (creating a new vertex in the middle of each edge, and thus adding 4 new triangles to the queue). However, if the target has been exceeded then the triangle with the smallest screen space error is merged (add the parent triangle to the heap, and destroy all child triangles of the parent triangle). At the end of this we have a load of triangles, each triangle is in a tree and the leaf nodes of the tree are in a priority queue.

Triangulate
This section of the algorithm actually generates a mesh to send to the graphics card for rendering. This comes in a couple of sections:

1) Loop through and triangulate all triangles which have been affected by a merge (remember, if you merge a single triangle, you now have 4 triangles to triangulate, since triangle itself and its three neighbours get affected. Doing this will free up some free space in the vertex buffer
2) Loop through and triangulate all triangles which have been affect by a subdivide, if a triangle has been subdivided then the centre triangle is now 4 triangles, and the neighbours are triangulated as best possible (there are algorithms for triangulating convex shapes, and they quite good and there are algorithms for triangulating concave shapes, however my shapes are just on the limit and I suspect that means I can build something more efficient than the normal concave triangulation. This will be the topic of another, probably the next, blog post)

The screen space error is the difference between how much of the screen something would take up if it was perfectly represented, and the space something actually takes up on screen with your imperfect representation, I haven't yet decided on exactly how I will calculate this - in fact it'll probably be the topic of another entire blog post.