Friday, March 24, 2017

Realtime Terrain Editing

I've changed topics once again and have gone back to working on realtime terrain editing. 3DWorld's heightmap based terrain has been editable using a brush system for a few years now. I'm currently working on additional editing functionality. Grass and trees can now be added and removed along with terrain height editing. This works for deciduous trees, pine trees, palm trees, grass, and flowers.

This is going to be a technical post. Sorry to those of you who were expecting another post with pretty pictures of fancy custom materials. I'll throw some samples of my wonderful terrain editing artwork in among the blocks of text to break things up a bit. Keep in mind that everything was created in realtime, and none of the scenes in the images took more than a minute or so to construct. I'm not an artist, but I'm sure an artist could make something really cool with these features.

Scene showing custom edited tree, grass, and flower coverage created in under a minute.

All editing modes use a brush system, with keyboard keys switching between modes and add vs. remove operations. The following modes are available:
  • Increase Terrain Height
  • Decrease Terrain Height
  • Smooth Terrain (constant height)
  • Add Trees (deciduous, pine, or palm depending on tree mode - another key)
  • Remove Trees
  • Add Grass (and flowers)
  • Remove Grass (and flowers)

Brushes have five parameters:
  • Brush Shape (square or round) 
  • Brush Size/Radius (in heightmap texel increments, from 0.5 to 128)
  • Brush Weight (applies to height increase/decrease and grass add/remove only)
  • Brush Falloff (for round brushes, controls falloff with radius: constant, linear, quadratic, sine)
  • Placement Delay (controls smooth brush application/painting vs. discrete stamp operations)

Terrain height editing operations only work for heightmap terrain read from a source image. The editing operates directly on heightmap image data stored in memory so that it can be saved back to an image on disk. Each user brush operation is stored in a list of edits that can be written to and loaded from disk, allowing the user to save their work. Brush operations that increase and decrease terrain height also support undo, which works by inverting the brush weight and reapplying it as a new brush at the same size and location. The updated height data is used everywhere, including in overhead map mode, which serves as a simple image viewer for the terrain in false colors.

3DWorld can load, display, and edit a terrain up to 2^15 by 2^15 (32K x32K) pixels in size, though the largest terrain image I have is the 16K x 16K Puget Sound dataset. This is an enormous 256M pixels! I can't even open the image in any standard image editing programs. Windows Explorer hangs when I try to click on the image because it can't even generate the thumbnail preview. Height data can be in either 8-bit or 16-bit resolution. Most of the larger datasets are 16-bit for higher precision.

Trees and grass can be added and removed without a heightmap because they operate directly on the procedurally generated data, overriding the procedural results. However, these brushes can't be saved (yet), and if the player moves far away from the edited region and comes back, the changes will be lost. I'll see if I can improve this in the future by saving and reapplying brushes when the terrain tiles they operate on are generated. Because of this, users will generally want to edit the height values before editing the vegetation.

Another example of my awesome artwork. This is a section of the Puget Sound heightmap, with custom hills and valleys and user placed trees and grass. The spikes in the back are one mesh quad wide and over 1 km tall.

All editing operations work on heightmap texels, or individual mesh elements when heightmaps aren't being used. Depending on the scene size/grid resolution, these units range from 1m to 10m. For example, the Puget Sound dataset is 10m resolution. This is around the spacing between trees, which means that individual trees can be added or removed. One mesh texel also contains a few hundred blades of grass, which isn't realistic but looks good enough. Addition and removal of grass is based on brush weight, meaning that the number of grass blades can be smoothly adjusted per grid cell. Flowers are generated or removed to match the grass density.

3DWorld also supports "zoomed out" heightmap editing on larger groups of power-of-two texels (2x2, 4x4, 8x8, etc.) This allows large heightmaps to be quickly modified without requiring a huge number of brush strokes to update millions of pixels. This increases CPU usage during editing, and is limited to a reasonable zoom factor of around 16x16. Zoomed editing is useful for creating larger features such as mountains and lakes that span many terrain tiles.

Who says you can't have a forest of 100K *unique* palms trees packed so close together you can't see the ground? I can create whatever I want in my map.

Heights (mesh z-values), trees, and grass and updated per-tile during editing. One tile consists of an NxN grid of height values, where N is typically equal to 128. Tiles that are modified have their data recomputed and sent to the GPU (height texture, material weight texture, ambient occlusion map, shadow map, etc.) The largest brush size available corresponds to one tile width (128), so in the worst case 4 tiles are updated per brush, if the brush happens to fall at the intersection of 4 tile corners. If brush delay is set to 0, this is 4 tiles per frame. The procedural generation and rendering system is capable of updating 4 tiles per frame at a realtime framerate of at least 30 Frames Per Second (FPS). Average editing framerate is often over 100 FPS. Most of the CPU time is spent recreating the various texture maps rather than on the editing operations themselves.

Smiley face "cookie" created with custom mesh brushes. This one is several hundred meters across, and has ponds for eyes and trees for hair.

The most important remaining task is adding a save + load system for trees and grass. That may also be the most difficult task. Considering the procedural nature of the vegetation system, it doesn't interact well with user edits. Edits are modifications on top of the procedural content; they can't be applied until the procedural content is first generated. This means that a saved edit file can only be replayed if the terrain tiles are loaded in the same order they were loaded during the initial editing. Unless the editable area is constrained to be within a few tiles of the starting location, this is difficult to guarantee. It requires some cooperation of the user - which means it only really works well when the user knows what they're doing.

I could, of course, save the entire state with every object placement. Then, when the save is loaded, skip all procedural generation and use the objects from the save file. It's unclear exactly how this would work if I continue editing the scene. If trees are removed and then re-added, are the new trees procedurally generated again, or do they need to match the trees from the save file that were removed? Also, there are performance/runtime issues to consider. I'll continue to think about this.

Finally, here is a video showing how I created a smiley face "cookie" within the Puget Sound scene. This one is similar to the steps I used to create the other smiley in the image above. Note that the water is at a constant height, so holes that are deep enough become filled with water.

If you're curious how I added the brush overlays as colors spread across the mesh, theses are done using the stencil buffer. A cylinder is drawn around the brush (cube for square brushes) in the proper editing color. Then the stencil buffer is used to mask off all but the pixels that are blocked by the mesh and trees, creating a decal effect. This way, the user can see exactly what area is being edited.

Here is another terrain editing video in the same scene. I loaded this heightmap with some existing edits, then added more.

I had only 1 of 4 CPU cores allocated to terrain generation/update, and the other 3 were allocated to video compression. This made update laggy since it's normally multi-threaded.That's why the video appears to play back so quickly in some places. It was recorded assuming a constant 60 FPS, but in reality I was getting 30-50 FPS during mesh height and tree editing. Grass editing takes almost no time. Also, the glitchy water tiles near the end of the video are only present during video recording, so I have no idea what's going on there. This is the first time I've seen that artifact.

Bonus: If you're curious how large the Puget Sound dataset is, take a look at this overhead map view. The area I was editing in in the center around that red circle. It's a tiny fraction of the entire heightmap. In reality, the heightmap is tiled/mirrored so that it actual goes on forever.

Puget Sound heightmap showing small user edited area in the center near the red circle.