Thursday, May 18, 2017

Domain Warping Noise

I recently watched this YouTube video and decided to make another pass at landscape height generation for tiled terrain mode in 3DWorld. The existing system allowed for several user-selectable noise variants, starting with my custom sine wave tables and including my recent implementation of GPU ridged simplex noise, which is a more efficient version of ridged Perlin noise. Two interesting variants of noise that I hadn't yet used for terrain height were noise derivatives and domain warping. Since domain warping seemed to be easier to implement in 3DWorld, I decided to start with that. The reference article (with source code) can be found on the Inigo Quilez website here.

Domain warping adds a swirly effect to regular noise that can be shown in the following overhead map view screenshot from 3DWorld.

Overhead map view of the central area of my island using domain warping noise is pseudocolor.

The features in this scene look very realistic, similar to eroded terrain with river valleys and steep peaks. Take a look at this image of North America for reference. It's much rougher than my smooth rolling hills seen in previous screenshots. If I use dirt and rock to replace grass and snow on steep slopes, the complexity of the terrain really stands out. Here is a slice of terrain from ground mode with grass, trees, flowers, and plants. Note that the grass blades are now curved, rather than being single triangles.

Ground mode closeup of terrain using domain warping, with grass, trees, flowers, and plants.

I can get some stunning views in tiled terrain mode, especially with the height scale turned up and lots of water in the scene. Here is a shot of steep cliffs near the edge of the ocean. The front side of the cliffs look like they have grass stairs cut into them. Notice the shadow of the mountain on the water to the right.

Steep cliffs above the ocean cast shadows to the right.

Keep in mind that 3DWorld creates an endless terrain that can be explored. There are no real limits to procedural generation (other than the wraparound every 2^32 = 4 billion tiles). The player can walk for hours in the same direction and never see the same landscape features. This is the main advantage of procedural generation compared to hand drawn maps. The downside, of course, is that generated terrain often lacks variety compared to what a human can create. This is the part I'm currently trying to improve.

Here is an image taken of the beaches and ocean near sunset, with fog in the background. It looks almost like a photograph. The black dots in the sky are birds.

Sun setting on the mountains near the ocean, with waves, distant pine trees, clouds, and fog.

I've applied a detail normal map to the textures of the sand, dirt, rock, and snow layers. This improves the look of the surface by adding high frequency detail. The distant peaks use per-tile normal maps to produce high frequency lighting details, even though the mesh vertices themselves are drawn at a lower level of detail to improve frame rate. Fog helps to reduce level of detail transitions in the distance.

Here is another view showing deep ravines and high peaks with water and grassy terraced fields below. I've disabled the trees so that the terrain stands out more.

View of an island with snowy peaks and sharp ridgelines. Trees have been disabled so that the underlying terrain can be seen more easily.

3DWorld does have some limited modeling of biomes. Some beaches are sandy and others are dirty/rocky. A low frequency procedural vegetation map is used to make some areas desert where no plants grow. This screenshot shows a strip of sandy desert between a snow peaked mountain range, with grassy areas behind it, and forest in the distance. No plants grow in the desert, and few plants are found on the rocks.

A strip of desert is caught between the lush green fields and the snow covered peaks.

This image shows a wall of mountains with a deep valley cut into the middle of it. I'll bet this area would be interesting to explore in a game. Domain warping can cause a large section of heightmap noise to be picked up and moved somewhere else in the scene. This effect can create high frequency content that isn't present in most other heightmap generation functions.

Grass fields leading toward a narrow mountain pass.

Finally, here is a screenshot showing a narrow land bridge connecting two islands. This feature was naturally created by my noise function. None of these scenes have been manually edited.

A natural land bridge connects these two islands.

I've also seen the inverse of this effect where rivers are cut into the land. It's not too common, and I forgot to take a screenshot. That's it for now. If I manage to get noise derivatives to work well, I'll post some screenshots for comparison.

Sunday, May 14, 2017

Instancing 3D Models in Tiled Terrain

My grand goal for 3DWorld is to allow an entire city of many square miles to be explored seamlessly. No loading screens, no delays, a huge view distance, shadows, indirect lighting, collision detection, etc. I started with the terrain in tiled terrain mode. Then I added water, trees, grass, flowers, plants, and rocks. That's good for natural scenery, but what about buildings? I haven't implemented procedural generation of building yet. In the meantime, I'll stick with importing 3D models in OBJ and 3DS formats.

Over the past few weeks, I've implemented a model instancing system that has allowed me to place a 2D array of - not just a few - but 10 thousand building models into a scene. I'm using the museum model from this post, which contains about 1.5M triangles across all materials. While only 100 or so museums are visible at any viewing location (limited by fog/distance), this is still a huge amount of data. 3DWorld's instancing system also includes sun/moon shadows, indirect sky lighting, and collision detection for the player. I'll discuss these features in more detail below.

These museum models are all placed on the mesh at the proper height/Z value using the terrain height values, in this case from a heightmap source texture. The mesh can be flattened under the buildings to make them level and remove any gaps. Buildings that are far away are obscured by fog and are not rendered.

Rendering / Level of Detail

Each museum model has nearly 1.5M triangles, so rendering all 10K of them would require 15 billion triangles. Clearly, that's no good for realtime. I needed to cut that down by three orders of magnitude (1000x) to something closer to 15M triangles. The obvious first step is to skip drawing of models that are far away. I already do distance culling for terrain, trees, etc. - that's what the distant fog is for. Also, View Frustum Culling (VFC) can be used to skip drawing models that aren't in the camera's view, for example buildings behind the camera. If I use the same visibility distance for buildings, and add VFC, this brings the number of models to draw down to only a hundred or so. Here is a screenshot of them, taken from a view direction near where the corner of the array starts. I believe there are about 120 buildings visible.

Large 2D arrays of museum models in various orientations, with shadows and indirect lighting. Around 120 model instances are visible in this view.

Okay, that's 120 * 1.5M = 180M triangles. If I use 3DWorld to brute force draw these, it runs at around 12 Frames Per Second (FPS). Interactive, but not realtime. Now, the buildings have a lot of small objects inside them, and these objects can hardly be seen when the player camera is outside the building such as in the screenshot above. Can you actually see any dinosaur bones in the nearby buildings? Disabling these small objects when the player is a few hundred meters away from a building helps somewhat, and the frame rate increases to 19 FPS. This is definitely helpful, but doesn't quite reach my goal.

Why doesn't this help more? Well, the problem is all that brick texture you see on the buildings. Over half the total triangles are brick material, and it's all one large object with randomly distributed triangle sizes. Most of what you see are the large outer wall polygons. What you don't see from outside are all the tiny triangles from the interior columns, stairs, railings, walkways, etc. Here is an interior screenshot showing indirect lighting and shadows (more on those topics later). The model looks much more complex on the inside than on the outside. Look at all those bricks!

Interior of museum showing indirect lighting. Adjacent museum models are visible though the windows.

I decided to bin the triangles by area in a power-of-two histogram, using up to 10 bins per material. Each bin contains triangles that are on average twice the surface area of the triangles in the previous bin. If only the first bin is drawn, this represents the largest 2% to 5% of triangles, which together account for 50% or so of the total surface area of that material. The min/max/average area values are stored for each material, along with the offsets for where each bin starts. The maximum visible bin can be determined based on projected pixel area, which varies as the square of the distance from the camera to the closest point on the model's bounding cube. The further the object is from the camera, the fewer bins need to be drawn.

If the player is inside a model, the distance is zero and all triangle bins are drawn. If the player is far from the model, only the first few bins are drawn, drastically reducing the number of triangles sent to the GPU. The largest count bins happen to be the ones with the smallest triangles, so even dropping the last bin or two can reduce triangle count by a factor of 2. This yields an overall 3-4x speedup, increasing frame rate from 19 FPS to 63 FPS for the view in the first image above. I think I was lucky with this model, because the outer walls don't have any small triangles in them that would produce holes when they're removed. The image with LOD turned on looks almost exactly like the image with LOD turned off. So much similar that I'm not even going to show both screenshots.

The final rendering performance improvement is dynamic occlusion culling. I manually added occlusion cubes to the museum model that include the large rectangular walls. Yes, these walls have some windows in them, so the occlusion isn't entirely correct. I was able to exclude the large windows in the roof though. This makes such a big difference in performance that I enabled occlusion culling anyway, even if it's not entirely correct. Each frame, 3DWorld collects a list of the 5 closest visible models to use as occluders. All of the models are checked to see if they're completely enclosed in the projected volume of any of the occluders from the point of view of the camera. If so, drawing of that model is skipped. This optimization has the most effect when the player is at ground level in the middle of the buildings, where the row of nearby museums forms a wall that obscures the other rows of museums behind it. In this case, only a handful of museums are drawn, and frame rate is increased from 60 FPS to 150-250 FPS.

Here is a video showing showing the array of museum models from various view points, both from the air and from the ground. There are almost no visible LOD artifacts while in the air. There are some artifacts due to occlusion culling when entering and exiting buildings, where the player crosses through a building's occlusion cube. Occluders are disabled when the player is inside them. I'll see if I can fix that somehow later.

This system works pretty well. I'm getting a good trade-off of performance and visual quality. But, I'm still lacking variety. I can't have a scene with the same one building placed over and over again. It's difficult to find high quality 3D building/architecture models for use in 3DWorld, and I don't have the time, tools, or experience to create them myself. Many of the free model files I can find online are poor quality, have missing meshes or textures, only represent one part/side of a building, are in a format that 3DWorld can't import (not OBJ or 3DS format), or have import errors/invalid data. I'll have to invest more time in searching for suitable model files in the future if I want to create a realistic city. However, the low-level rendering technology may be close to completion. That is, assuming there's enough memory for storing shadow maps and indirect lighting for each model. On to those topics next.


I enabled standard shadow maps with a 9x9 tap percentage closer filter for 3D models in tiled terrain mode. Shadow map size is defined in the config file and currently set to 1024x1024 pixels. Models cast shadows on the terrain, trees, plants, grass, and water. They're rendered into the individual shadow maps of each terrain tile and cached for reuse across multiple frames. This is no different from how mesh tile and tree shadows work.

Models also cast shadows on themselves. Shadows from directional light sources only depend on light direction, so the shadow maps can be reused in all translated instances of a model that have the same orientation. My arrays of museum models use three different orientations (0, 90, and 180 degree rotations), so three shadow maps are needed.

These shadow maps only need to be regenerated when the light source (sun or moon) moves. They're shared, so updating them only requires rendering one museum model in a depth only pass for each orientation, which is quite cheap. This means that the light sources can move in realtime with only a small reduction in frame rate - for self shadows, anyway. Updating all of the tile shadows can be more expensive, especially for low light positions during sunrise and sunset. This is because the shadow of a single model can stretch far across the landscape, which requires drawing many models into the shadow map of each tile. Note that models out of the player's field of view can still cast shadows that fall within the field of view. For this reason, nearby models have to be loaded and ready to draw, even if they're behind the player.

However, a model can't currently cast a shadow on another nearby model. This breaks the translational invariance, and seems to require many more than three shadow maps. If the models were all on the same plane I could reuse the same shadow map for all interior instances, which are known to have neighbors in all directions. Unfortunately, the models are all placed at different Z height values (based on terrain height), so this doesn't work. It can't generally be relied on. I'll try to find a workaround for this problem later. As long as the buildings aren't too close together, and the sun isn't too low in the sky, this shouldn't be much of a problem.

Indirect Lighting

I managed to apply my previous work on indirect lighting to tiled terrain models. In particular, I wanted to apply indirect sky lighting to instanced buildings. Indirect lighting is precomputed by casting rays from uniformly distributed points in the upper (+Z) hemisphere in random directions into the scene. A billion points are ray traced along their multiple-bounce reflection paths on all CPU cores using multiple threads. All ray paths are rasterized into a 3D grid that's then sampled on the GPU during lighting of each pixel fragment. The sampled texel contains the intensity and color of the indirect lighting. The resulting lighting information is also saved to disk and reused when the same building model is loaded later.

The nice property of sky light is that it comes from all directions, which means the lighting solution for an isolated model is independent of it's position or orientation within the scene. All I needed to do was generate the indirect lighting solution for an isolated museum, and the same solution could be used for all instances. This assumes nearby buildings have little impact on the indirect illumination. It all depends on how close the buildings are to each other. I'm not sure how much influence the other buildings would have on the lighting because I have no easy way to show it. The scene doesn't look obviously wrong, so it must be acceptable to drop this term. Buildings are pretty bright when viewed from the outside, even when in shadow and close to other buildings. The interior lighting mostly comes from the skylights in the roof, which aren't affected by adjacent models.

One additional benefit of my lighting system is that it stores normalized reflection values, rather than absolute color and intensity. Meaning that the cached lighting values are multiplied by the sky color and intensity during rendering, which allows these values to be changed dynamically. The lighting solution can be reused for all times of day, even at night! Just swap the daytime blue sky color with a much lower intensity night time color. This also works for changes in weather such as cloud cover, where bright blue is replaced with a dim white on cloudy days.

Collision Detection

3DWorld supports a simple, limited collision detection for tiled terrain mode that has been extended to models. It's a limited version of the ray/sphere collision detection system used in ground and gameplay modes. Here it's only used for player collisions, since I haven't implemented any gameplay yet.

Each unique model stores its own Bounding Volume Hierarchy (BVH), which is used across all model instances. This serves as an acceleration structure for fast ray queries. When the player is within the bounding cube of a model, two lines/rays are fired from the player's center point.

One ray points down, in the -Z direction. This is the gravity ray. Gravity is enabled in "walking" mode but not in "flight" mode. The first polygon that this ray hits is the polygon the player is walking on, and is used to set the height (Z) value of the player. This test is what allows for walking up stairs and falling over ledges. I haven't implemented real falling, so walking over a ledge will just teleport the player to the bottom. There are some holes in the stairs of the museum model which can cause the player to fall though the floor. Oops! I'm not sure what I can do to fix this, other than inserting some other tiny model to fill in the gaps like I did in another scene. It's not like I can easily find and fix these polygons in a 56MB file filled with numbers.

The second line extends from the player position in the previous frame to the position in the current frame. This represents the distance the player has walked over the past frame, and is typically very short. If the movement is legal, the line won't intersect any polygons. But if the line does intersect, this means the player has run into a wall. The normal to the polygon is used to produce an updated player position that allows for sliding against a wall but not traveling through it. I haven't implemented anything more complex such as bumping your head on a low ceiling.

This simple collision system is enough to allow for exploring the buildings and terrain by walking. I'll have to find a way to extend this system to volume (cube/sphere) intersections if I want gameplay to work in the future.

Sunday, April 30, 2017

1000 Dynamic Lights

It's been over a month since my last post. For the past month, I've been working on a number of smaller unrelated topics, so I'll probably add a few shorter length posts in quick succession. Recent work has been on the subjects of large numbers of dynamic lights, the game mode freeze gun, instanced placement of complex 3D models in tiled terrain mode, and tiled terrain animated clouds.

The first topic is dynamic light sources. I've discussed my dynamic light implementation in 3DWorld before. Lights are managed on the CPU, then the visible lights are sent to the GPU each frame as a group of 1D and 2D textures. These textures encode the world space position of each light source grouped spatially, so that the GPU fragment shader can efficiently determine which lights affect which pixels. Every fragment (similar to a pixel) looks up its position in the lights list texture using the {x,y} position of the fragment. Then, the contribution of each light in the list corresponding to that grid entry is added to the fragment. Typical texture/grid size is 128x128.

This has been working well for a long time. I've been experimenting with 100 dynamic light sources in scenes and have posted screenshots of these in my planar reflection posts such as here and here. I recently experimented to see how many lights I could add to a scene while achieving realtime (60+ FPS) rendering. After various low-level optimizations on the CPU side, I managed to get up to 1000 lights for many scenes. Here are some screenshots of the office building scene with dynamic light sources at night.

Office building scene viewed from outside, at night, with 1000 dynamic, floating, colored light sources.

Back of the office building where the only lighting comes from 1000 dynamic light sources, at 67 FPS.

Keep in mind that all of these glowing spheres are moving, colliding with the scene, and casting light. In addition, they cast shadows from the sun and moon. However, I've created these images on a moonless night, so that there are no other light sources. All lighting comes from dynamic lights. I normally get around 60 FPS (frames per second) with reflections enabled and 90 FPS without.

Here is a view from inside the building lobby. There are a few dozen lights visible in this room alone. I've enabled reflections for the floor so that the glowing sphere reflections are visible.

A room densely filled with light sources, which also reflect off the floor.

Here is a screenshot from a larger room that contains around 100 light sources. The building is huge! This is just one of 4 floors (+ basement), all full of lights.

Another room containing over 100 light sources, with floor reflections.

The max number of lights is actually 1024, because I encode light indices as 10-bit values within the lookup textures. I used to run into problems with this limit when there were a large number of reflected laser beams in the scene during gameplay. I previously had implemented laser beam light using a series of small point light sources along the beam path. This quickly adds up when there are multiple beams crossing an entire floor of the building. Each beam segment could have over a hundred point lights. Now I'm using analytical line light sources for laser beams, which are directly rasterized into the lighting lookup texture. One beam segment is only one light source.

I also increased the number of lights in the Sponza atrium scene from 100 to 200. This scene is much smaller (~8x), so the lights are packed together more closely. They have the same light radius in a smaller space. Each pixel has contributions from 10-20 light sources. 1000 lights is possible, but overkill. The frame rate drops and the walls appear a very bright white.

Sponza atrium scene with 200 dynamic colored light sources and floor reflections.

These images are also taken at night, where the glowing spheres and fires are the only light sources. Here is the same scene from a different view on the lower level, with smooth reflective floors enabled. There are no shadows for these light sources, so they shine through walls.

Sponza scene lower level, with floating lights and reflective floor. The fire and burning embers also cast light.

Note that the fire on the right of the image also emits dynamic light, with approximate shadows. In addition, it throws out glowing embers, which also emit light. You can see three of these on the floor, reflecting their red glow on the smooth marble.

Here are two older screenshots of the Sponza scene with fewer lights.

Sponza scene at night, lit by only dynamic lights.

Sponza scene at night, with reflections on the floor.

I've also implemented dynamic cube map shadows for moving light sources. It's limited to a small number of lights, currently only 9 (64 textures, 6 textures per cube face/light). This is determined by shader size and uniform variable count. I could increase the texture array size for my new system/GPU, but I also want this to work properly on older systems. For now, I have added a reasonable cap on shadowed lights.

Here is a screenshot showing two shadow casting lights near the stairs in the office building. If you look closely, you can see some shadows cast by the red light on the stairs and support columns.

Two shadow casting, moving lights. Shadows can be seen on the stairs for the red light on the right.

The approach I'm using for local lighting is similar to a standard tiled forward approach, also known as Forward+. Some reference articles and examples can be found here, here, and here. This is an alternative approach to deferred shading. 3DWorld was originally written using a forward rendering pipeline because I wanted to have a lot of transparency effects. Also, deferred shading wasn't very common back when I started writing 3DWorld in 2001, and I've never gotten around to implementing it. The tiled forward approach works well in my engine so I've continued to use it.

However, I'm doing it a nonstandard way. I came up with my system years ago, before deferred shading and tiled forward rendering were well known. This is one of the early application of GPU shaders to replace the fixed function pipeline in 3DWorld. Instead of using screen space tiles, I use world space tiles in the XY plane. This is the floorplan or map view of the building; I use up=Z in 3DWorld. In the past few weeks, I attempted to implement screen space lighting tiles in the standard way. I thought it might yield better performance, but my experiments showed that this was not the case. Why is that? Part of the problem is that it takes more work to transform world space light positions into screen space, but that's a minor issue. Maybe I haven't optimized it properly. But there's more.

3DWorld's "ground mode" is intended to be a first person shooter environment. The player is usually standing on the ground/floor, unless they have the flight powerup or are in spectate mode. This means that the view direction is often in the XY plane. A common case is to be looking down a hallway that has lights on the sides. Using my world space light tiles, these lights will be in their own texture tiles. The subdivision system effectively splits them up so that pixels along the view direction (along the hallway) will see different tiles at different distance/depth. On the other hand, if screen space tiles are used, the rows of lights will all stack up behind each other at different depths, which means that many of them will contribute to the same pixel. Screen space tiles appear to be slower in this situation.

Maybe I'm doing something wrong here? Or maybe my system just works better for my type of scenes? I suspect that if the lights are small and dense enough, the screen space system works better. For example, if there are 100 lights that all fit within a small area of a single XY tile in 3DWorld, they would all contribute to each pixel. The tile subdivision system is ineffective. But if these were screen space tiles, there would still be subdivision. I guess this case doesn't come up much in 3DWorld because there are no sources of small, dense lights. Explosion particles and shrapnel, the smallest light casting objects, use a system of grouping of multiple smaller lights into a single larger virtual light to work around this problem. World space tiles sized on the order of a typical light source's radius work well in most cases.

Some tiled forward systems use 3D tiles (screen X, screen Y, and depth/Z). [I've read about this before, but I can't seem to find the original article.] That would give better resolution along the hallway, fixing this issue. It would seem to guarantee that no matter what the view vector and light placement is, the tiles always split up light sources that are far apart from each other in world space. The only pathologically bad case is where many light sources are close enough to each other that their spheres of influence overlap. Of course, I could add a 3D texture/array of world space tiles to my system as well. I have experimented with that before, but it turns out the performance is worse. 3D texture lookups are slower than 2D texture lookups, the math is more complex (and slower), and I need to use more total tiles. This increases memory usage and CPU => GPU transfer costs as well.

As far as I can tell, the dynamic lighting system I've implemented in 3DWorld works well. It scales to 1000 lights for a large scene, with no problems. If I ever need more than 1024 lights, the system needs to change. For now, this seems to be sufficient for even my most demanding scenes.

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.

Saturday, February 25, 2017

Yes, More Custom Materials!

It's time for more fun with custom materials in the form of reflective and refractive cubes and spheres. Every time I get distracted by some other new feature, I keep coming back to these materials. Part of the reason is that I've never seen a system that can do something like this before. I'm not saying no other game engines or material editors like this exist, just that I've never seen one.

In theory, 3DWorld should be rendering these materials using close to physically correct lighting models. Of course, there could be bugs. I have no idea how to check for correctness. Some of the materials I can create may not exist in the real world, such as a half metal half glass. Or a material that absorbs/scatters blue light and reflects red light. Maybe they exist, but I don't have any around for reference, and good luck finding a reference image for something like that online.

What's changed since I last blogged about this stuff? I think I finally have refraction working correctly with per-object cube maps, at least for cubes and spheres. These two shapes are simple enough that I can ray trace them inside the shader to compute correct ray intersection points and reflection/refraction angles. The shader code is pretty complex as it handles up to two reflections and two refractions corresponding to both the front and back faces of transparent materials. In addition, it handles volumetric light scattering and light absorption/attenuation. This is what we see in volumetric/solid, partially transparent materials such as ice, glass blocks, colored plastic, liquids such as milk, etc.

There are an incredibly large combination of material parameters that I can create in 3DWorld, so I can't possibly show them all in this post. At best I can show a dozen or so examples. Here is the set of parameters that can be edited in realtime that affect lighting (excluding parameters used for physics):
Texture, Emission, Reflectivity, Metalness, Alpha, Specular Magnitude, Shininess, Refraction Index, Light Attenuation, Diffuse Red, Diffuse Green, Diffuse Blue, Specular Red, Specular Green, and Specular Blue. These user parameters are explained more in my previous blog post on this topic.

Parameters are changed through my simple onscreen editing system where the arrow keys select the variables and move the sliders. It's similar to a monitor's onscreen menu system. Maybe it's not the best or nicest looking UI, but it's simple to use, easy to work with in the code, and has almost no impact on framerate. Plus, it avoids having to pull in a 3rd party UI library and figure out how to make it work in fullscreen mode when 3DWorld only supports a single window + render target. I did, however, add a texture preview image and some small color indicator circles. Everything but the texture image is ASCII art. If I ever release 3DWorld to the public, I'll have to add a better UI.

Here is an example of a refractive glass cube and sphere together. Refraction currently only works correctly with sphere and cube shapes; other shapes are approximated without knowing the exit point of the view ray from the object. You can see the reflection of the sphere in two of the back faces of the cube. The fragment shader traces each view ray through the object. The ray is both reflected and refracted at the front surface of the shape (the current pixel's 3D position in the fragment shader). The refracted ray is then intersected with the back face of the shape using a ray-sphere or ray-cube intersection. The hit position is reflected back into the shape, and also refracted out of the shape into air. The reflection and refraction angles depend on the indexes of refraction at the material/air interface. Each of the rays that exits the shape is looked up in the correct face of the reflection cube map to determine the color to use for blending. This produces first-order physically correct reflections and refractions, as seen in the image below.

Glass cube and sphere drawn using a cube map with two reflections and two refractions, in shadow.

Does that look like a real glass cube? Maybe. I do have a clear plastic cube that I used as a reference last year. Unfortunately, I seem to have misplaced it after moving to the new house. The sphere certainly looks like images of glass spheres I found on Google (example). It has the typical inverted, zoomed out refraction image of glass spheres. However, I don't have the physical parameters (such as index of refraction) for the glass used in those images, so I can't do an accurate comparison. A small change in index of refraction makes a large change in the reflections and refractions, especially the second order ones. The difference is amplified with each reflection/refraction.

I've also experimented with more than two reflections/refractions, but this didn't seem to improve the results, so I left it out. It definitely changed the results, but it wasn't clear that they were more correct. I don't think the average human can detect correct third order reflection/refraction effects. Also, multiple bounces in spheres tends to magnify part of the image, which makes the pixel borders of the cube map texture more obvious. I would rather have a smooth and clean image than one that is every so slightly more physically correct. Besides, this adds extra complexity and reduces framerate.

Here are some screenshots where I was experimenting with different diffuse and specular colors. The blueish diffuse and reddish specular makes these glass objects look like anti-reflective coated lenses as used in cameras and some sunglasses.

Textured glass "marble" with reflection, refraction, and scattering using custom material texture and colors. The smiley face is my placeholder player model!

The glass eyeball.

Normal maps can be applied to object as well to perturb the reflection/refraction normal vector and get some interesting effects.

Glass ... pumpkin? Well, this is a wooden fence normal map applied to a sphere.

I made some attempts at creating ice. I don't have any ice normal maps, so I had to make do with the normal maps I happen to have. The stucco normal map shown in the first video at the bottom looks like a natural chunk of ice. These two cubes look more like ice sculptures or something else man made.

Ice cube? More like ice bricks.

Another ice cube, using a different normal map texture. Since it's supposedly transparent, it doesn't cast a shadow.

Light absorption and scattering within the material volume is also supported. This is sometimes referred to as participating media. The way this works is by calculating the length of the view ray clipped to the bounds of the sphere or cube for each fragment in the shader. This is the distance light must travel to cross the 3D volume of the object. The amount of light absorption/scattering varies exponentially as exp(distance) and is used to blend between the cube map ray hit color and the material's bulk color.

I can add hundreds of cubes and spheres and they're all drawn in depth sorted order for correct alpha blending. You can see the reflections and refractions between all of the objects. Is this physically correct? I have no idea, it's not obviously wrong as far as I can tell. I've seen similar effects in image searches such as this one. The exact value for index of refraction makes a huge difference.

Refractive glass cubes and spheres that absorb and scatter light. They also reflect and refract each other.

Here is a screenshot of the San Miguel scene from the previous blog posts, this time with some interesting glass and metal objects on the ground. The gold sphere can be seen twice in the glass sphere. On the left is a refraction, and on the right is a reflection off the inside surface of the sphere. It looks like it could be physically correct. If I only had a glass sphere and gold sphere I could probably figure it out. Is anyone interested in donating these to me in the name of science?

Material spheres placed in the San Miguel scene. The reflective gold sphere is reflected and refracted in the glass sphere.

I created two videos showing material editing. Both videos were recorded in realtime. As long as a single sphere or cube is placed or moved at one time, the framerate remains high. There is a list of predefined materials read from a text file. The UI allows for editing of existing materials to create new named materials. These can be saved in the scene for later use. Dynamic objects can have their parameters modified after placement if their named material is the one being edited. This is because they store a reference back to their material. However, the cube map is rendered every frame, so this only works well for a single dynamic object. Multiple objects reduce framerate due to all the required scene rendering passes. Static objects, on the other hand, can be placed all over the scene until graphics memory is exhausted (a few hundred objects on my system). The downside is that their material parameters can't be modified once they're placed. Both types of objects can be moved by the player and also destroyed.

Here is a similar video, this time in the San Miguel scene shown in the previous two blog posts. The only collision object is the ground. The tables and chairs weren't added as collision objects because they're not really grouped in a convenient way in the model file, and I haven't computed their bounding volumes. 3DWorld really prefers volumetric collision objects rather than polygon-based ones. I could add all ~7M polygons as individual collision objects, and it would probably work, but the performance would be terrible. I'm not sure if 3DWorld could actually fit the data + acceleration structure in 32-bit address space. So you can ignore the fact that I'm pushing cubes through tables and chairs, because I haven't bothered to fix it. Also note that the final cube's refraction image looks a bit odd because it's partially sticking though the wall.

That's all I have for now. I have a lot more images and videos of more materials with strange parameters, but I feel I've shown enough of the interesting ones.

The question is, what can I do with these? Is it possible to build an entire building or game level with them? I guess I need to add support for shapes other than cubes and spheres. Technically, I do have other shapes, but I hard-coded the parameters into the source code rather than adding a proper UI for controlling them. I've already created a scene with over 10K cubes so I know it scales, as long as they're not all reflective and refractive. 10K opaque/diffuse objects and 100 reflective/refractive objects should be fine for a realtime scene. Of course, it would be an incredible amount of work to build something useful from them if every object needs to be individually placed. I suppose I can continue to use these objects as decorations. And yes, they can be saved and reloaded, keeping most of the parameters. I can no longer edit object materials properties after reloading.

Wednesday, February 1, 2017

San Miguel Rain and Snow

This post continues my San Miguel scene experiments using techniques from previous posts on rain and snow. I decided I wanted to see how this scene looked with wet and snowy surfaces and how well the environment coverage mask worked on a highly detailed, complex model.

Here are two screenshots showing a rainy San Miguel. The wet look on the stone ground, tables, and chairs is achieved by decreasing the material diffuse lighting and increasing both specular intensity and specular exponent. This is a pretty simple effect, but works well in practice, especially on the ground. Wetness is higher for horizontal surfaces, and surfaces that have an unoccluded view of the sky above. These are the surfaces that naturally receive and accumulate the most water.

The raindrops themselves are drawn as vertical lines that quickly fall in a mostly vertical direction depending on the wind. They look much better in a dynamic scene than they do in the static screenshots shown here. Each drop is visible for only a few frames.

Rain and wet ground. Raindrops are drawn as lines and look much better when moving.

Rain and wet ground + objects from another angle.

I also enabled snow coverage and let the simulation run for a few minutes. Snow is accumulated over time and is drawn as a white layer on top of the normal textured scene geometry as a postprocessing step in the fragment shader. Snow thickness/density is a function of polygon normal and is highest for horizontal surfaces that face the sky above. Since the camera is above the scene in this screenshot, most of the visible surfaces such as the tree leaves are pointed up and have a high snow density.

Snowy scene from above, after several minutes game time of accumulated snowfall.

I enabled the snow coverage mask for the next two screenshots. This works by precomputing a depth-based coverage mask for the scene that stores the vertical distance from the sky plane for each pixel. The fragment shader accesses this texture to determine whether the current fragment is at or below the recorded occluder height. If the fragment is below this height, it is occluded by other scene geometry from above and receives no snow. The texture is blurred using multiple projection angles to simulate a randomization from the typical vertical snowfall. This smooths the edges of the snow coverage mask in areas of high frequency geometry, such as under the trees. However, if snow is left to fall over an extended period of time, this saturates the coverage layer and produces sharper boundaries (as seen below).

The first image was created using a low resolution 512x512 coverage mask, and the second image was created using a much higher resolution 2048x2048 coverage mask. The second image contains higher frequency content for a more accurate representation of snow coverage, though it takes much longer to compute. Preprocessing time is still under a minute on 4 cores. I don't think it looks all that much better though.

Snowy scene using a low resolution 512x512 snow coverage mask.

Snowy scene with a high resolution 2048x2048 snow coverage mask. The snow "shadow" from the trees can be seen.

I'll continue to experiment with snow effects. It would be interesting to see how well true volumetric snow accumulation works on this scene. This will likely take several hours of CPU time, and generate a large amount of voxel coverage data.

[Update: It in fact only takes 7 minutes to create the snow volume for 1 billion simulated snowflakes. I underestimated how well the bounding volume hierarchy scales to scenes with many polygons. However, the snow coverage is very noisy due to the large number of small leaves and other objects. I think the white color non-volumetric snow actually looks better. If you're interested, here is a screenshot.]

Volumetric snow simulated using 1 billion snowflakes.

Monday, January 9, 2017

San Miguel Scene

This post doesn't contain much technical content, because I was busy with moving to a new house and then the holidays, so I didn't have much time to write code. Instead, I'll post some images of the San Miguel scene modeled by Guillermo M. Leal Llaguno of EvoluciƩn Visual. I downloaded the Lightwave object file model and textures from the McGuire Computer Graphics Archive.

It took me a few days at an hour or so per day to get the scene to render correctly in 3DWorld. I had to add several minor new features, including a user-specified environment map cube, per-model normal map options, texture invert, custom sunlight intensity, custom mipmap creation for the leaves, and a per-material metalness parameter. Some of the features worked well, but others need more work. In addition, there are some errors in this version of the model, including missing triangles, missing textures, and incorrect texture coordinates. However, these problems don't affect the overall scene quality too much, as long as you're not looking at the details.

I computed indirect lighting for both the sky and sun for this scene using a preprocessing ray tracing operation that took around 10 minutes on 4 CPU cores. Once the preprocessing is finished, the lighting can be used for all view points and various weather conditions. There is no fake ambient term here, all indirect lighting is computed over a 3D grid. This isn't a closed model - meaning, many of the polygons are two sided and don't form a watertight volume. This leads to light leaking through the walls in some places. I don't have a good solution for this problem yet.

I used a single 8192x8192 shadow map and a 6 face 1024x1024 cube map centered in the courtyard for environment reflections. 3DWorld computes the shadow map and cube map when the scene is loaded, and updates them dynamically when objects move or any lighting/environment parameters change. This update requires the scene to be drawn multiple times, but there aren't any dynamic objects enabled by default so this isn't a problem.

Here are some screenshots showing the San Miguel scene from various locations and directions. These are some of the most photorealistic images I've gotten from 3DWorld so far. It can render this scene at an average of almost 200 frames per second at 1920x1080 on my Geforce GTX 1070.

View of the San Miguel scene from the corner showing shadows and indirect lighting.

View from the trees looking down. The indirect lighting appears to soften the shadows.

San Miguel scene viewed from near the fountain with a low value of sun and sky indirect lighting but strong direct sunlight.

View from the upper balcony showing closeup of plants. The sky is cloudy, which makes indirect lighting stand out more.

Here are some screenshots showing cube map environment reflections on glass and metallic objects. The reflection and transmission model is physically based and uses true Fresnel equations. Reflections don't use per-object cube map centers yet, so they're not very accurate, but they still look pretty good. There are some alpha blending artifacts due to not sorting the faces for individual objects from back to front. The materials are themselves sorted correctly as the viewpoint changes. Some of the objects are misaligned with each other, such as the salt shaker. This appears to be a problem in the model file and not a 3DWorld bug.

Reflections in glasses and silverware. For some reason, the salt shaker's salt, glass case, and metal lid are misaligned from each other.

More environment reflections of objects on the table.

Cube map reflection in the window. The reflection is a bit undersampled and distorted because it's far from the single cube map center point.

Cube map reflections in the silverware on a table. Can you spot the sun?

Here is a short video where I fly through the scene and examine some objects. At some point I'll have to add a system to improve the smoothness of camera movements when recording videos.

Here is another video with a slower camera speed and my attempt at smoother movement.

This work has been pretty fun and interesting. It's quite different from writing graphics and physics algorithms. I can't wait to find more large and interesting models like this one, and the museum scene from a previous post, to show in 3DWorld. If I find enough of them, I can combine them into some sort of town and maybe build a game into exploring the environments.