Terrain, voxels, and meshes

Defining the terrain
Playform's terrain is defined using some cheap and easy noise functions. The basis is Perlin noise, which is a cheap and easy way of generating smooth, bubbly-looking output, like hilly terrain. A fractional Brownian model is applied to this noise, which is a term I learned just now, and a term I probably won't need to use again for at least another year. It basically just means that I take my Perlin noise, generate it at several amplitudes and frequencies in a fractal pattern (e.g. repeatedly multiplying both by 1/2), and then adding all the results together.

This lets you roughly describe lots of different terrain features pretty easily - mountains are high amplitude and low frequency, where bumps and ditches are low amplitude and high frequency. A nice thing about these fancy-sounding noise functions is that they're popular and well-understood, so finding libraries to generate them (and generate them quickly) isn't hard. Perlin noise can also be used to generate things like textures, which is a thing I've been meaning to work on for a while.

Storing the terrain
Playform's world is divided into a big 3D grid, and each cell can be called a "voxel" (which really just means a 3D pixel). Minecraft and many other games use this idea, so often each cell is considered filled or empty (or equivalently, filled with air). This world representation lets you add and remove pieces "anywhere" in the world without a whole lot of work.

Voxels don't just have to contain simple "full or empty" data; Playform's voxels contain more data so that we know whether each vertex in the grid is inside or outside the terrain. This means that any given grid edge can be entirely inside or outside the terrain (if both its vertices are), or it can be crossing the terrain. The crossing edges are the interesting ones.

This same idea applies to entire grid cells: if all the corners of a cell are on the same side of the terrain, we can just say that the whole voxel is inside/outside, but if it has some corners inside and some outside (or equivalently, if any of its edges cross the terrain), then the voxel intersects the surface of the terrain. Each intersecting voxel stores some extra data to help build the mesh: it stores a point inside that voxel that lies on the surface of the terrain (it doesn't have to be perfect, just approximate). It also stores a surface normal at that point, for lighting and whatnot.

Lastly, this grid isn't stored as a big 3D array; it's stored as an octree (a 3D binary tree). This lets you have bigger cells where less detail is needed (e.g. huge open areas, or huge chunks of space that are entirely inside the terrain), and it gives you the option of having "arbitrarily" smaller cells where more detail is needed.

From voxels to polys
The bulk of the credit for Playform's voxel-to-mesh algorithm goes to this Siggraph 2002 paper and to Miguel Cepero's blog post about exactly this problem.

Whenever we find an edge that intersects the terrain, we generate a little bit of mesh to represent the part of the terrain that is being crossed. We do this by looking at the four grid cells that the edge is a part of. Since the edge is crossing the terrain surface, all of those grid cells must be crossing it too, so they all store a point. We use those four points to construct a little patch of mesh.

This choice of what data to store in each voxel is nice for several reasons. It's pretty simple - a big portion of the work is deciding whether or not a given point is inside the terrain. Deciding where to place points inside the voxels isn't that important algorithmically, it just affects the visual quality of the resulting mesh - you can just put every point in the very center of its "parent" voxel. Curves won't look nice, but it's really easy to calculate. You can calculate surface normals using cross products, since once you have a few points, you also have vectors between those points that are roughly "lying on" the surface. You can make them a little smoother by averaging adjacent normals together.

The mesh points can be placed roughly anywhere inside the voxel, which means you can faithfully represent all kinds of different surfaces. Flat, curvy, pointy, the algorithm really doesn't care, as long as it has some points to work with. One thing I'd like to do is have a mesh import feature (again, credit to Miguel Cepero at Voxel Farm); as long as the grid is high-resolution enough that every mesh vertex is inside its own grid cell, the mesh could be imported without any loss of data, and then made a part of the world!