Last time I talked about my new landscape level of detail algorithm which I'm building for Myriad, I promised that I would talk about triangulation next - so here I am!

The triangulation algorithm comes in two distinct parts, both rather simple. The part is called GetInnerTriangles, this gets all the triangles which are inside a node on the Level of Detail quadtree, to get the triangulation of the entire algorithm you can simply run this method on the root node. If a node has no children, it simply returns two triangles making up a square. The exciting bit comes when a node does have children, firstly the algorithm gets the inner triangles of all four children, which will fill most of the space but might leave cracks in the landscape between child nodes with differing levels of detail; to fix this the second phase is to "weld" together edges of children which are at different levels of detail. Welding works by getting two lists of all the vertices down the two adjacent sides of the given nodes, and then putting in triangles to join together the edges.

So what's the end result of all this is our grand scheme of planet rendering? Now we have a way to render a flat surface at automatically varying levels of detail, without any cracks showing between different levels of detail. Using this we can render 6 flat surfaces (one for each face of a cube) and weld them together using the weld algorithm I already described.

The only thing we have left to do is to actually build our quadtree with the correct level of detail applied to each node, this is done with a Min-Max-Heap, which is something I'll be talking about next time.

The other thing I wanted to mention was that I'm currently working on a new layout for my blog, built on top of a new (far more efficient and responsive) blogging engine. You can find the preview here. Currently it's just the layout and background code which is mostly final, obviously colours are likely to change ;)