One Knight Studio © 2019

  • Yukkafuzz

Cube Morphology and Terrain

It was an early design decision to avoid photorealism in EXO. The feel should not be cartoonish exactly, but simple. Not only does this align with the experience I hope the player to receive, but it's also a practical choice; one person cannot create AAA game graphics and make the rest of a game in a reasonable time frame. With that, I wanted to make sure to avoid imitating other games around with non-photorealistic styles - Minecraft and Astroneer come to mind - when it comes to planetary terrain in EXO. So I arrived at the idea of a block-based system, like Minecraft, except where every "block" can take a number of shapes, allowing for corner pieces, slants, and many others. To accomplish this, I needed a system to determine which shape a given block should take.


Consider a cube. It has eight vertices. But what if I remove one vertex, and make a shape with the remaining seven? You get a cube with a corner chopped off, like below:

Cube with a cutout corner. A technique for smooth lighting is used (averaged normals on vertices), so the faces of the shape are not too sharp.

What if I take off two vertices? Now what shape does it make? .... It depends on which two. Can you determine how many fundamentally different shapes can be formed with 6 vertices of a cube? (As in, different shapes that cannot form each other by rotating and flipping.)


Well, if you remove two vertices that form an edge, you'll get a shape I call a slant. There are twelve orientations of the slant shape (one for each edge). It's fundamentally different to remove two vertices across a face diagonal, as you'll get a shape that's a cube with two corners chopped off, with a diagonal edge between those corners. (There are also twelve orientations of these, one for each face diagonal.) Finally, as you might guess, the last different shape is formed by taking away two vertices across the long diagonal of the cube. That shape is also a cube with two chopped-off corners, but this time they are opposite each other. (4 orientations of these). See below for pictures - in order mentioned.



All right, so what's the point here? For every unique set of vertices you choose, there is a unique orientation of one of these "morphologies" of a cube's eight vertices. (More math for those inclined: how many total shapes/orientations are there? Answer at the bottom.) So interesting terrain can be produced by generating a value "used" or "not used" for each vertex in a large grid. This works for continuous terrain because neighboring cubes share vertices. The edge of one cube's morphology will always align with the neighbor's on that side, since they determined their shape using the same used/not used values for the vertices on their shared face.


Now, complications do arise when fully implementing this for terrain in game. First of all, any 2D shapes look very jarring in a 3D world. So most three- and four-vertex morphologies should actually be ignored. (Imagine the triangle made up by three vertices. You would just see a floating triangle with no depth). For efficiency, the program also should not consider any cube faces that will be hidden by other blocks. So, a block with all 8 vertices used should actually render (show on screen) nothing: if it's fully "used", it is fully solid, which means it should be totally covered. As it turns out, for any morphology, anything on a cube face need not be rendered, since its neighbor will share that face, except when the face makes up the only used vertices.


Imagine a solid, flat ground surface made up of many layers of cubes. Now imagine a ghost layer of cubes on top of that surface. Each of those ghost cubes has its bottom four vertices on the surface. It's actually those ghost blocks that the terrain algorithm uses to render the ground. This is more convenient than checking if a given shape is neighboring "air" on a certain side to determine to show a face.


However, that causes one small complication: what if (for example) three coplanar vertices get generated at the top of a spire? As was mentioned before: floating triangles! So in the end, the terrain generation algorithm does have to check the neighbors of blocks with only three or four coplanar vertices to decide whether to actually render them.



The spire on the left has an awkward-looking 2D top.


To put this into context, the whole terrain creation "pipeline" goes like this:

1. Create a large grid of points.

2. Use Perlin noise to generate a value between 0 and 1 for those points.

3. Threshold that value: air if below a certain value, and solid if above.

4. Go through each "block" and look up the correct block morphology. (Represented as a set of triangles to render. So I had to manually program in more than a hundred sets of triangles, for all the different morphologies.)

5. Translate the resulting triangles into that block's position.

6. Put the resulting triangles in the "mesh" (the object that gets sent to the graphics card)


As you can see, it can be quite a process! I've gone in depth on only one of these steps here (although a couple of them are trivial). Still, I hope it provides some insight on the work and the kind of fun (read: math) that goes into EXO: Perl.


-Yukkafuzz


Answer: 256. (or 255, if you don't count no vertices, or 247, if you don't count single vertices either.) Each vertex can either be used or not be used, so it has 2 states. There are 8 vertices. So the possible combinations can be calculated as 2^8 = 256. Subtract if you don't count low vertex counts as morphologies, and there you go.


Sample terrain in context, on a planet.