Kerbal Space Dev
On Quadtrees and why they are awesome

So, the new update is focusing mainly on implementing a new procedural terrain engine for the game. The current one is the random result of a heap of half-successful experiments and developing as fast as possible.

The new terrain is based on a Quadtree. Quadtrees are structures composed of nodes, each of which has the power to subdivide itself into 4 child nodes. 

This means that if a quadtree is used to create a terrain, you have very good control over how it subdivides, and the level of detail on any given point.

But for a planet, a single quadtree isn’t enough. Quadtrees are 2D spacial structures, so they don’t apply themselves too well for a spherical terrain (a.k.a., Planet).

So the solution is to use not one, but six quadtrees, arranged as a cube. 

What happens is that each vertex on a quadtree terrain tile is pushed outward from the center of the planet, creating a spherified cube, or hexsphere. This hexphere is really cool because it has no poles, which means no points where the quads would become terribly distorted by an attempt to map a flat thing onto a sphere.

And it’s fast. Really fast. Since you only need to create 4 new nodes at a time, and those are quite small to begin with, the game can do it without blinking. That means we no longer have to use yielding and coroutines to make the terrain system lighter. It can function in real time, meaning you will never be able to outrun the terrain.

A tile-based terrain also plays a lot more nicely with the physics. Each tile has it’s own collision mesh (well, the more detailed ones at least), so there are no issues with exploding when landing on the far side and things like that.

Also, the terrain shader used to texture the terrain can now work in tile-space, which means it’s a simpler shader, and a Mac version is now possible.

Yes, a Mac version has been proven to work with the new system, and will be released with the 0.10 update.

And that’s why quadtrees are so awesome!

Cheers

  1. kerbalspace posted this
Blog comments powered by Disqus