Procedural World

One quick session in Voxel Studio

2012-02-27T20:12:00.002-05:00

As promised, here is a screen capture covering some other features in VoxelStudio. Here you will see terrain rendering happening on the Voxel Farm, also a glimpse of the tree and forest edition process.

I had only two nodes in the farm dedicated to rendering the terrain meshes shown here. A farm with four machines would have rendered twice as fast.

Real men don't draw buildings

2012-02-25T03:53:00.000-05:00

Real men -and women- don't draw buildings, they write them. Why limit yourself to one instance of a building when you could define an entire family?

It turns out writing building grammars is hard, it feels closer to programming. For procedural architecture to take off, creation tools must appeal to artists. All we have now are maddening languages and graph editors. Only a few artists have the skills to make any sense of them. I would like to find a solution for this, but I got nothing so far.

I have created a timelapse video where you can see me creating a grammar from scratch. It is for a family of simple, rustic houses like this one:

You can click on the image to see it in detail. This is a rendering of the triangles output by the grammar evaluation. This model has not been altered by hand.

Here is the video:

Grammar Editor in Voxel Studio

2012-02-20T13:14:00.000-05:00

To continue this series of posts about Voxel Studio, here is a sneak peek at the grammar editor:

As you can see I ended up devising a new language for expressing the architecture grammars. If you get the full image above you should be able to read the code. Two rules make this very simple test.

This is a dramatic reversal on an earlier post. If you don't remember about this, my initial approach was I would never need a custom language for architecture grammars, that being the only user of this system I could do fine with so-called fluent interfaces in C++. Many commented back then I would have to bite the bullet and write a custom parser. They were right. It has saved me time, also the new language is quite powerful. I will introduce it later in a future post.

Trees in terrain preview

2012-02-12T13:13:00.002-05:00

Here are some rendered trees. Keep in mind this is a preview to help the world designer choose the parameters for the procedural generation. The lighting is very poor. Also tree crowns appear as blobs in the preview, which is far from being realistic. These blob polygons are the base for instanced branches and leaves later in the client. This is similar to the grass I have posted in earlier screenshots.

Editing a Forest

2012-02-08T13:06:00.000-05:00

My approach to forests is that they are emergent patterns. They appear out of the properties of the different tree classes. A tree class may use a density mask to tell the system where this type of tree does well. Altitude is one clear example. These masks, however, are a very broad brush. Several species may share the same mask values for very large areas, still their distribution within that area has to be realistic.

To achieve this, I use a simulation of the forest evolution over several centuries. This is something I described in an earlier post. There are two key parameters: tree maturity, which is the average age at which the tree starts producing seed, and average lifespan, which is for how long a tree is expected to live.

The whole world (12km x 12km in my tests) is covered by a single forest, which takes less than a minute to simulate. Even if it is a single forest to the simulation, it looks like different forests and types of biomes. By using the masks you can make sure trees gradually disappear in deserts, or that some species never crossed certain range of mountains.

You can choose to simulate much smaller areas while you are still tweaking the tree classes, the results are consistent with a wider simulation. It creates a very quick workflow.

In the following screenshots you can see a quick test I did with seven different types of trees. This can be improved a lot with more tree classes and more detailed masks, hopefully you get the idea:

Tree editor in Voxel Studio

2012-02-03T18:14:00.000-05:00

Here is a screenshot of the tree editor in Voxel Studio:

You saw several trees taken from here a while ago. Now you can see some of the parameters that define a single Tree class. A lot of things to worry about, but most combinations result in believable trees.

Introducing Voxel Studio

2012-01-30T15:41:00.003-05:00

This introduction was also long overdue. For more than a year I had this program that allows me to work on a definition for the procedural world, then schedule it as a render job in the Voxel Farm and finally show the results on screen. Many of the screenshots you have seen in the past were taken from the viewer in this program, but the UI for it remained hidden. Until today.

I give you Voxel Studio:

This program has a series of editors for the different things that make the procedural world. In the previous screenshot you can see the Terrain Layers editor, which allows to define the multiple layers of the terrain. For instance, there is one layer for each type of rock. The placement of these layers is determined by masks, which are the output of an earlier process. It also covers Vegetation and Architecture, but I plan to show that later this year.

Something I like about this program is that it uses the Voxel Farm to create previews. Right now I have only three good machines in the farm, a single scene like the one in the screenshot still takes close to a minute to render. If I had six machines I would wait only half that time.

The Renders view will show you a list of the jobs currently in execution inside the farm:

One only render job at this moment, but there could be several at the same time. The green cube shows a world chunk that has just been received from the farm.

The material editor allows to define the multiple layers that make each material:

These layers follow the same model I had introduced in an earlier post. They are rendered in real-time, although there are no shadows nor global illumination unless you perform a deeper render.

If you are only working on the materials there is no need to recompute the geometry of the scene, this ends up being a pretty neat and fast workflow.

If you want to make sure you are working on the right layer of terrain or material, you can always ask the program to highlight it. The following screenshot shows the same scene as before, but the "Volcanic Talus" layer appears highlighted in red:

In the future I will post more about this program. If I get enough time I will capture a video so you can see a quick session.

In the poll at the top of this site there is an option that reads "Content creation application (like WorldMachine)". This option has received one third of the votes compared to the most popular option. This is a lot of votes once you consider it is a tool and not a game like other entries in the poll. Voxel Studio is that application.

Like anything else in this project, I'm not sure if it will ever be released, but I'm closer to having this finished than a game or anything else. It could be a nice procedural creation suit, including both the studio and the farm. If you see yourself using an application like this, I would like to hear about what features you'd like on it. Please leave your suggestions as comments and we will sort out what is feasible and what is not.

A trip to the Voxel Farm

2012-01-19T17:12:00.006-05:00

This post is about something I have not discussed before, but somehow it has been present on every screenshot or video I have posted for a while now.

For more than a year I have been building a little farm of machines. They run a series of programs I wrote for the procedural generation. They work in parallel, sometimes doing the same task over different locations of the virtual world, sometimes running very different tasks one from another. Their efforts are highly coordinated. Thanks to this I can get large portions of terrain, forests and buildings generated in very little time. I can see the results of the changes I do to the world definition without having to wait too long.

What it is best, this setup allows me to throw more nodes in the network at any time. I only have three decent machines in the farm right now. They are old gaming rigs I found on Kijiji around Montreal. The minimum spec is 8 Gigs RAM, 3 or 4 cores and an ATI video card better o equal to a 4770. I need them to have GPUs because some algorithms use OpenCL. I cannot afford to get too many of them right now, but having software that scales over multiple systems is already saving me time.

What I like the most is that it really feels like a single very powerful machine. The existence of the farm is completely transparent to the application I use to design virtual worlds. I will cover this application in a future post, you have already seen many screenshots taken out of it without knowing.

I would like to introduce you to some different animals I keep in this farm and explain a little about what they do.

Dispatcher

The dispatcher controls everything that happens in the farm. There is a single instance of this process for the entire farm. At any time the dispatcher keeps tracks of the different jobs currently active. Each job may be at a different stage. The dispatcher knows to which farm worker should direct the next request. All the coordination happens over TCP/IP. The dispatcher listens on two different ports. One is for the farm workers to report their progress and get new work assignments. The other one is so clients of the farm can request new jobs and also query the status of ongoing jobs.

Contour
Several layers make the virtual world. Some are terrain layers, some vegetation, some are buildings and roads. All these layers have something in common, they represent a volume with an inside and an outside. Contouring is the process that allows to find the surface that divides the inside from the outside. The world is broken into many Octree cells. Each contour worker can process a cell individually. It knows which layers intersect the cell so it runs an algorithm known as Dual Contouring on the contents of the cell. The result is a very detail polygonal mesh.

Decimate
The meshes produced by the contour phase are very dense. If they were fed to the next processing stages it would slow them down. For this reason they go through a phase of decimation. This is a fast Multi-Choice mesh optimization that preserves topology, and only removes those triangles that bring very little difference to the mesh. The resulting mesh is very close to the original, but the number of triangles is drastically reduced..

Reduce
I use a LOD system to replace several distant small cells by a larger cell. Since they are Octree cells, this means combining eight children cells into one large parent cell. Even if it covers eight times the space, the parent cell must be similar in byte-size than the child cells. This means the eight children must be brought together and compressed. The compression at this phase does change the mesh topology, otherwise it would be impossible to achieve the target sizes. Then the resulting parent cells are again combined into a larger parent cell and so on, until the highest LOD cells are obtained.

Project
This process takes a high resolution mesh from the decimate or reduce phases and creates a very simplified mesh out of it. Then it projects the excess geometry on a normal map. The results are compressed as I described before and stored in a cell definition file. These are the files that are sent to the client for rendering. At this point the processing for a single cell is pretty much done.

I have not covered here the generation of cities, architecture, forests and other elements. They blend into this sequence and also live in the farm, but I think they deserve a dedicated post.

Probably the most interesting aspect of writing a collective of programs like this was how to make it reliable. Since I was targeting unreliable hardware to begin with, I realized failure had to be an integral part of the design. I devised a system where none of these processes expects you to do proper shutdown on them. They could just vaporize at any point. Actually I did not implement a way for them to exit gracefully. When one needs to close, the process is simply killed. The collective has to be resilient enough so no data corruption arises from such a failure.

GreenSpace

2012-01-05T11:32:00.002-05:00

This one is off-topic, I apologize for that.

A good friend and his indy studio just finished this game:

You start with a very dirty planet, there is funny-looking garbage everywhere. You have to clean the planet, develop it and make it green again.

It may not be your cup of tea, but odds are you know someone who will enjoy it a lot. Please pass it along.

You can play the game from here:

http://playgreenspace.com

Another two screenshots

2011-12-29T11:52:00.000-05:00

More Sputnik screenshots

2011-12-28T12:23:00.000-05:00

Here are some other screenshots so you can see the mesh compression results

Distant Mounts

2011-12-23T17:51:00.001-05:00

This is a screenshot taken from the Sputnik LOD viewer. I photoshoped the sky in the background, but the rest of the image is realtime. This shows some mountains on the distance which are all compressed using the method I described in my earlier post. Keep in mind I still need to work on the lighting and the actual textures. The textures will bring additional detail. This can get a lot better. This image is about the polygons in the distance.

Through the Eye of the Needle

2011-12-23T14:08:00.000-05:00

I remember this short science fiction story: A group of very wealthy men were attempting to make a camel go through the eye of a needle so they could get into heaven. They tried all sort of things short of melting the camel. The biggest challenge was to have the camel back in one piece and alive.

Sending complex meshes over a network will leave you the same feeling. For my world to be experienced over HTTP, I needed to compress terrain cells down to 10K average.

If you remember from earlier posts, I had broken the terrain into chunks. A LOD system builds cells around the camera position. In the first LOD cells are 12x12x12 meters, the next is 24x24x24m, then 48x48x48m and so on. The highest LOD in my scenes is 7, where each cell covers 1.5 kilometers approximately. No matter which LOD, all cells should be around 10K.

This is a challenge. 10K is not much. In vanilla form you need to store three coordinates for each vertex in a mesh, one for each axis (x, y, z). Then you have to store the actual triangles that make up the mesh. Each triangle requires three indices. If you used floats for the coordinates and 16 bit integers for the indices, it would require 12 bytes per vertex, 6 bytes per triangle. Odds are you also need texture coordinates, which are 2D points in texture space. Each triangle takes 3 of these pairs, one for each corner. If you store them as floats, it adds 24 bytes per triangle. A typical mesh has twice the number of triangles compared to faces. Each vertex is approximately costing 72 bytes. 10K would store only 142 vertices.

It helps to cut on the number of bits used to represent each component. You could use 10 bits for each vertex coordinate, 12 bits for face indices and 8 bits for texture coordinates. Each vertex would be 30 bits, each triangle 78 bits. A mesh taking 10K this way would contain 440 vertices. It is an improvement but still very far from my target.

The naive approach is not enough. Something different must be done.

One very interesting approach to mesh compression is Geometry Images. This was developed by our granddaddy Hoppes. The idea is to store the mesh as two images: one for the vertex positions and one for the normal map. The main advantage is you can compress these images using traditional compression techniques, even use lossy compression like JPEG.

The problem with it is you will need to flatten your mesh. Depending on mesh topology, you will need to cut it and create charts. This is not for the faint of hart. Also you need to make sure the image compression produces consistent results for the boundaries of these charts. If you use lossy compression you could get cracks in the reconstructed mesh. Like any 3D to 2D mapping, there can be stretch issues, and since you are storing geometry in a map, aliasing may be very noticeable in some places.

For these reasons I decided to wait a little bit on the geometry images. I chose a more traditional approach to compression, here is what I did.

The first step is to simplify the original mesh. This can be considered as some form of lossy compression. I described the method I used in an earlier post. At the end of this stage I have a simplified mesh for the cell which ranges from 200 to 2000 triangles.

The next step is to recover most of the original detail in a normal map. Using a normal map allows you to crank up the mesh compression. Many of the smaller features of the mesh will be gone in the compressed mesh but will appear in the normal map.

At this point I had a mesh with 2000 triangles and a normal map of 256x256 pixels. Both had to fit in 10K. To make things worse, there was some additional information I needed to store for each face corner. I needed to somehow describe which materials were present. The least I could pack was two materials and a blending factor between them.

I decided I would worry first about the mesh, then deal with the normal map.

As we saw before, just cutting the number of bits used to express components helped, but was far from enough. I needed some sort of compression scheme. Compression is about finding redundant data and taking it out. Redundancy is not always evident, for this reason you need to reshuffle your data, transform it in a way that redundancy will show. Here is a very simple way to illustrate this.

Let's say you need to describe the sizes of these dolls:

You could just list each doll and specify how big it is. What if you reorder the series?

Then you could just say how big the first one is and the rate at which their sizes will decrease. That is a lot less data to convey the same amount of information.

I did the same for the vertex positions in my meshes. I sorted vertices so the next vertex in the list would be the closet to the preceding one. The following image shows this list as a series of arrows:

The advantage of sorting is that you could use less bits to express the difference between one position and the next.

This approach does not guarantee you end up with minimal distances between vertices. The blue arrow shows one clear case. Often the best fitting configuration is not a list, but rather a tree. Using a list all the time has one advantage, you don't need to waste bits coding whether the next element is in the current branch of if it goes back to a previous point in the tree. Results may depend on the nature of your meshes, I advise you test with a lot of data to see what will do best.

So using a list you will get you a few bad cases. These bad apples really hurt. To avoid this, I created two buckets. Most increments will be small and can be coded with just a few bits. Those go into the first bucket. Then the bad cases go into the second bucket. For each mesh you can find out at runtime how many bits you need for each bucket. Then you need only one bit to express which bucket it is.

The bit map for a single channel of coordinates ends up looking like:

For the first item:

Store origin coordinate: 12 bits
Store length of bucket A: 4 bits
Store length of bucket B: 4 bits

For each next value:

Store bucket selector: 1 bit
Store difference from previous: variable bits as determined by bucket
If difference is different than zero, write sign: 1 bit

In most of my meshes the first bucket can be represented with 4 to 5 bits. The second bucket is usually around 10 bits. 90% of the items fall in the first bucket. 1000 vertices stored at 10 bits each component would take 3,750 bytes. With sorting and buckets it would take around 2,436. This does not only save space, in most cases you get better precision.

To compress triangle indices, it is probably best to use triangle strips. For each strip run you only need to add one additional index to get a new triangle. This does require you to re-sort your triangle data. I did not want to sort triangles just for this, cause I feared I needed to sort them to compress a different type of information in the future. For the triangles, I had to compress their vertex indices some other way.

Each triangle has three different indices to vertices in the mesh. I found that in most cases these indices were very close. It does make sense since the closer two vertices were in space, the closer their position in the sorted vertex list. I could then store the first index of the three and save bits in the next two by only storing their difference with the first.

Then I had the texture mapping coordinates. This is was entirely redundant. For my meshes, texture coordinates are created by an algorithm, they are not tweaked by hand. This meant the same algorithm could run on the receiving end and come up with the same data, without having to send anything. The tricky part was to make sure the results were consistent. If you think having running the same algorithms on two very different machines, at different moments in time and produce exactly the same results is easy, you may be surprised. There are many things that can go wrong. Comparisons you may do with floats or doubles could go any way. Numeric error may build up in different ways. But it is possible if you know what to look for. The savings in mesh size are great.

The material information that augmented each triangle was easier to compress. There was a lot of regularity there. I saw the blending channel could do very well with just four bits. Also the materials present on each cell could go into a palette. For most cells it would be below 3 bits.

While doing all this I made sure each channel of information was stored continuously. For instance, the material blending information for all triangles was written sequentially. This was to help the last phase, which was to feed the entire bit soup to traditional ZIP compression. For most meshes ZIP was not able to compress the resulting data anymore, but some times I could see a gain of up to 5%.

At this point the meshes alone were taking around 4 to 5K. I still needed to fit the 256x256 normal map into a budget of 5K. I tried loss-less compression similar to PNG, but only storing two components for the normal. Since the normal vector is expected to have length equal to 1.0, you can skip one of the coordinates and reconstruct it later. Loss-less would not do it. It could not compress the map enough. So I decided to test how bad it would look if I used lossy compression. To my surprise it was not bad at all. The reason is that my meshes were very organic and noisy, so the errors in the compression were hard to spot.

I looked at different codecs but ended up picking the new WebP by Google. It had the best compression I found. But I did not try JPEG2000.

So I had done it. My rich, bloated original meshes were down to 10K average. A lot of detail was lost in the process, but there was no choice. I think that somehow relates to the ending of that sci-fi story. The wealthy mean got into heaven after all. Their failed camel compression and teleportation schemes were so expensive they became poor in the process.

A Procedural Universe

2011-12-08T09:11:00.001-05:00

You may think building one procedural world is a daunting task. How about a procedural universe? This is what John Whigham is trying to do. Take a look at his blog:

http://johnwhigham.blogspot.com/

I like his rendition of stars and gas giant planets. Here is one screenshot:

I'm determined to steal some of his ideas for the night sky of my little world.

The fine art of motion sickness

2011-12-02T21:20:00.001-05:00

I have a new video of the streaming and LOD system in action. This one is guaranteed to make you sick, so watch at your own risk.

I managed to push LOD switches a lot further, now it does not change under your feet unless the streaming lags behind for too long. The amount of detail on screen increased a lot too. Still, the required download rate remains pretty much the same. It is interesting how I did it, this will be the topic of a future post.

Your suggestions and comments for the earlier iteration of the LOD/Streaming were on the money. Please keep them coming.

Here is the video:

Streaming LOD

2011-11-28T21:28:00.001-05:00

If you remember an earlier post, I had built a little program called Sputnik to test mesh streaming over HTTP. Over the weekend I had some time and made it stream multiple levels. Here you can see some results. Please be forgiving, I did not spend any time on the texturing, lighting or anything but streaming.

LOD transitions are smoothed now whenever possible. I do it by gradually blending the changes into the scene. There are a couple of bugs in the normals which make popping more noticeable than what it should.

I capped download speed at 200 KBytes per second. Often the downloading lags behind the camera position. The scene shows with less resolution until the download catches up. I think 200 KBytes per second may not do it once I add large trees and buildings. I will also reduce the amount of mesh simplification, the rock profiles are too straight on this one.

Material World

2011-11-25T12:52:00.000-05:00

I often get questions about the texturing in the screenshots and videos I have posted so far. There is nothing really new in what I do, still it may help to discuss it.

The material system I devised shares the same core philosophy as the voxel system. It is all based on my hope that if you put enough layers into something it will eventually look good. I know this is an awfully technocratic approach to art and design, it is just the way I found to compensate my lacking skills. I also hope this system is flexible enough for true artists when the time comes.

The volumetric world definition is a set of layers. Each new layer adds or subtracts to the layers before. If you look at a cliff formation, there is one base layer for the main volume of the cliff, then other layers on top of it, each one adding a different type of rock.

Each volumetric layer has a different material assigned to it. The material system defines the look of each layer, and very important, how transitions between different materials are rendered.

Let's look first at how material boundaries work.

Once voxels are converted into a triangle mesh, each triangle ends up having a material assigned to it. A change of material happens because the predominant voxel layer changes too. Very often the material boundaries align perfectly with sharp features in the geometry.

This is what you want in some cases. Imagine where the foundation of a building goes under the rock. You don't want the rock and the wall materials to blend, it would look weird. In other cases you do want different materials to blend. For instance where snow ends and bare rock starts. A clean line would not be right.

This behavior had to be controlled by a material setting. The engine then looks at all the triangles contributing to each vertex and compiles a list of materials for the vertex. Material boundaries form based on these blend settings.

At some point I was alpha-blending materials at the boundaries and baking the resulting image into a texture. I would later use this texture for rendering. This alpha-blending turned to be a problem when I moved all material rendering to realtime shaders. As you will see next, each material is a also collection of layers. Rendering a single material means all these layers must be evaluated and blended together. Now, imagine a point where three different materials overlap: I would need to evaluate all the layers for all materials there. It was often worse than that, in some spots I could find up to seven or eight different materials.

I knew rendering a single set of layers was fast enough, so what I did was pick one of the materials and render just that one. Materials already have an alpha value. Picking the one with the highest alpha does the trick. This still creates sharp transition lines, but they can be fixed by offsetting the alpha by a noise function. The transitions become more natural that way.

The following screenshot shows several transition areas as produced by the shader:

Then there is the other half of the material system: how each material is defined. As I mentioned before, it is just a set of layers. Each layer has defines several properties that control how it looks and how and where it is applied. Here are some of them:

Diffuse map: A texture with the color information for the layer
Normal map: A texture that describes additional orientation changes in the surface of the layer
Start and Bottom angles: These angles determine where the texture appears based on the orientation of the geometry. They are based on the world's up vector. This is what you would use to put moss on the top of rocks for instance
Mask noise: A noise definition that determines the intensity of the layer at any point in world space.

I have some other properties, but the ones listed above do most of the work.

I leave you with a screenshot of Buddha, where you can see the angle properties used to place some grass in the horizontal areas. It does not make sense in this case, this is just so you can see it in action:

Streaming Meshes

2011-11-17T03:29:00.000-05:00

Here is a quick video I did over the weekend. It shows a new program which connects to a web server and downloads chunks of terrain as you move.

I had posted similar videos in the past, but there is a radical difference. In earlier videos the meshes were loaded from the hard-drive. This baby you could run from your home. I actually plan to put it out for everyone to try it early next year. Since it will be the fist foray of this technology out there, I called it Sputnik.

It is only the first level of the clipmap, but I have expanded it so the load it generates is similar to a full scene spanning several kilometers. I capped the download speed to one megabyte per second to see if the downloading can cope with the camera movement.

The meshes are not textured in this video, but the all the information required for the final rendering is being downloaded. So this is really it. The chunks average 20K. They contain the mesh, normal maps and material information. I tried hard to make them smaller than that, but the loss in quality was not acceptable.

Using HTTP for transfer is a gamble, I'm still not sure about it. So far the results are encouraging, but I'm still weary of the worst case scenario happening too often. With HTTP it is not really about the transfer speed, it is the overhead of starting requests what worries me.

If you have any experience on this field, I would really appreciate your insight.

Playing Dice with Mesh Simplification

2011-10-27T10:09:00.003-04:00

Mesh simplification is as old as polygon meshes. Even then, it is still a hot topic. There are plenty of methods out there, picking the right one is the tricky part. It is not only about the quality of the resulting mesh, but also how fast can you do it.

I had decided not to use progressive meshes at all and chose clipmaps instead. That meant I had to deliver each cell of the clipmap in a single shot. My plan was to use a very simplified mesh and keep most of the detail in a series of maps: normal map, material map, etc. In this post I will describe the method I used for mesh simplification.

Here you can see some results:

The voxel countouring phase was churning out huge meshes. A single cubic cell of 6 meters side would easily take a few hundred thousand polygons. I needed to fit that into a budget of one or two thousand polygons.

Hitting this budget was the first problem. Removing so many faces from the mesh could severely alter its appearance. It was necessary that the simplification introduced the least amount of error possible.

There are two main classic approaches to mesh simplification: Vertex Clustering and Greedy Serial simplification. I had used some vertex clustering methods before, but disliked their boxy artifacts.

One of the best methods for minimizing error is one described by Hoppes in 1993, which is a greedy serial approach. It uses Quadratic Error metrics to minimize errors. The algorithm can be described like this: For all edges in the mesh, find the one edge that when collapsed introduces the least error. Then repeat until the desired polygon count is reached.

This method produces beautiful results, but it is very slow. It sequentially visits each edge in the mesh to discover which one to collapse. If your mesh has to be compressed from 100,000 triangles to 1,000 that's a lot of iterations for every collapse. It can be optimized so errors are pre-computed in one initial phase and kept in a sorted list, having the smallest error edge on top. As long as the list is properly sorted, you can get the edge at the top and collapse it. Still, every time an edge collapses, several other edges need their collapse error to be recomputed and their place updated in the sorted list. This comes at some cost.

Then I found this paper which opened my eyes to a technique called Multiple Choice Algorithms. These guys apply it to mesh simplification, but it is a very general and powerful way to solve a big family of problems. Load balancing and network routing are some typical applications.

This is how the method is usually explained: Imagine you have 100 large odd-shaped containers and a tube that continuously ejects a ping-pong ball. Your task is to fill the containers evenly with balls. The catch is that someone else will remove balls behind your back, so the only way to know how many balls you have in any given container is to count them. You cannot just keep track of how many balls you have put since some may have been removed already.

The naive approach would be to count the number of balls in each container and then place the ball in the one having the least amount. That would work, but it is an awful lot of work and it would take a lot of time.

Now, instead of that, imagine you just pick 5 random containers, count the number of balls in them and place the new ball in the one having the least amount of balls. Would it work in the long run? If it did, it would be great, you have reduced the number of containers to count from 100 to just 5.

The question of whether this really works depends on the total number of balls. For small numbers it won't be good, but when the balls start to pile up the randomness evens out and so do the containers.

Applied to mesh simplification, the method means you pick only a few edges randomly, let's say 10, and you collapse the one introducing the smallest error.

Does this create noticeable differences with the sequential greedy method? Again it is a matter of how many times you perform this operation. These are huge meshes and most edges in the original mesh will be gone. This is the equivalent of having a large number of balls.

You can actually estimate the chances of it making an error. A compression from 100,000 triangles to 1,000 means only 1% of the edges will remain. An error happens when the best edge collapse in the set of 10 random edges belongs to the 1% that should never collapse. This means that the other nine candidates are also in the 1%, otherwise one of them would have been picked for the collapse. So the probability of picking the wrong edge is 0.01 at the tenth power: 0.00000000000000000001. This is what in engineering we like to call never.

I implemented this method and the speedup was considerable. It also made the whole algorithm a lot simpler. In the serial greedy method you need to do a lot of housekeeping to avoid recomputing edge collapse errors. Also when a collapse actually happens, you need to recompute the error metric for the adjacent edges. In the multiple choice method it is OK to recompute the error metrics for the small set of edges every time, the optimization structures of the serial greedy approach are not needed anymore.

What is truly remarkable about the multiple choice optimization is that it lends very well to parallelization. You can have thousands of simultaneous threads, each one looking at one different bucket of random candidates. Each thread would output the result of the collapse operation for its bucket and the resulting mesh would be the input for the next iteration. A single iteration could collapse thousands of edges in one shot.

Remember, this can be used in many other things than just meshes. Like the scan algorithm, this is one tool you may want to keep in your set for the future. As for myself I'll keep walking with this hammer in my hand, I'll let you know if I find another nail.

Popping Detail

2011-10-07T18:39:00.000-04:00

I have added two new videos where you can see the popping of new detail.

It is very noticeable when the camera is close to a boundary and the new mesh comes right in front of it.

In these videos the clipmap loader is always trying to catch up with the moving view. In most cases it drags behind, as it really needs to load and process nearly 50 Megs worth of new meshes for each new scene. These meshes won't be used by the clients. Clients will receive very simplified meshes with all the detail projected. They will load a lot faster, but some of them will have to come from the network, so it is essentially the same problem.

Adding some degree of prediction should help. A prediction logic would load the clipmap scene for where the camera will be, at least a second ahead.

These videos are from some kind of weird terrain I was testing. I still need to go back and improve the terrain definition and materials. Right now it is a bit crazy.

If you look carefully you will notice both videos end in the same spot of terrain, but they start in very different places. Enjoy!

Clipmaps

2011-10-07T01:05:00.000-04:00

After playing with some ideas on how to send the world to viewers, I ended up choosing Clipmaps.

Clipmaps have been around for a while, so I won't spend much time explaining what they are, how they work. It is about breaking the world around the viewer into concentric rings. Each ring has roughly the same amount of information, but the further they are from the viewer, the larger they become. The perspective projection makes distant objects appear smaller on screen, so you end up having a fairly constant distribution of information for the entire view.

In most implementations clipmap rings are square. This is mostly because Euclidean spaces have affinity with square things, but rings could be spherical, pyramidal, etc. Spherical rings provide the best ratio between information and the size at which it appers on screen. With square clipmaps three will be some areas where you have more information than what you actually need. This error is the difference between the Manhattan and the Euclidian distance, but it is not very noticeable. It is very hard for the viewer to perceive the axes of the clipmap system.

Clipmaps were quite easy to implement in my case. I already had the world information stored in an octree. The leaf cells were 6m by 6m by 6m. It is not hard to see that octree cells can be arranged around any point in space so cells are increasingly subdivided as they get closer to this point. The following image shows this in a quadtree:

Something nice about this approach is that a given cell is always the same regardless of the point from where its is being observed. Once a cell is downloaded from the server it can be cached and reused any time later, no matter if the viewer has now moved to a different position.

Clipmaps are very simple to manage. The cells can be stored as files and served over HTTP. No server-side programming is necessary. Cloud services like Amazon's S3 make it dirt cheap to store and serve arrays of files like these clipmap cells. They also provide caching at multiple points if your files don't change often. As a solution it is fast, reliable and scales very well.

In principle clipmaps are a way to manage information for a scene from a point of view. Some of the shortcomings we usually attribute to clipmaps do not really come from the method, rather from the way it is used.

A landmark limitation of clipmaps is the noticeable popping of higher detail cells into the view. This is not the clipmap's fault. It is caused by the way information is stored. For instance, if the higher detail cells contained progressive mesh operations to be performed over the lower resolution, it would be possible to smoothly transition into the higher detail geometry and topology.

One real hairy issue with clipmaps is managing the seams between rings at different resolution. Some engines do a lot of stitching. Some other engines create "skirts" on the seams so any holes would be covered by the skirts.

How am I dealing with popping and seams? For now I'm just waiting to see how bad of a problem this is in my case. Right now seams are hidden by some overlap between cells. Since the texturing matches, they are hard to see. I like this solution since it is very parallel, one cell does not depend on its neighbors. The popping will depend on the mesh simplification and projection for the final meshes. In the high resolution mesh explorer program I did the popping is very noticeable, but this may be misleading at this point.

Here are a couple of videos. Again, they are taken from the mesh explorer, so please disregard texturing, illumination. The clipmap shows nicely in the wireframe at some point in the first video. The second video shows high frequency meshes, where the popping is most noticeable.

Streaming Meshes

2011-09-28T11:37:00.003-04:00

At this point I was considering different methods to stream this huge world to users. I was looking for an approach that featured great compression, but also could be selective about what information to send. There is no point in sending very compressed information if it's not needed anyway.

Polygons, actually triangles, are a very efficient way to compress 3D models. You can think of it as some form of lossy compression. A very irregular surface can be approximated by a series of triangles. Depending on how many triangles you use, the resulting surface becomes closer to the original.

The beauty of this is you can do it progressively: you start with a coarse approximation and then, if needed, you can increase the amount of triangles until the approximation is satisfactory.

Progressive meshes are quite old. The classic approach is to simplify a mesh and record all the compression operations. If you reverse this process, that is, start from the simplified mesh and play back the recording, it is like you were adding detail.

This principle has been extended so playback only happens for the polygons that are visible, making it view-depending. Detail outside the view is not refined. This property suits very well for streaming from a server. You can be very selective about what details are sent to clients. For instance, if the user cannot see the back of a mountain or a house, there is no need to stream any detail there.

Now, if you use a simplification method that is able to change mesh topology, it means the playback can increase the "genus" of your mesh. For instance a house in the distance would not have a hole in the chimney, but if you get close enough, this hole would appear. This is a game changer.

An octree-based mesh simplification method can do this for you:

This method works very well over a network. TCP/IP is a streaming protocol. Not only it makes sure all bits of info arrive, it makes them arrive in the same order as they were sent. This is actually an overkill. For traditional progressive meshes it was required that playback occurred in the exact same order as simplification ocurred. You needed something like TCP/IP for them. With an octree-based progressive mesh this is not necessary all the time. For instance, cells at the same level can be refined in any order. In this case it makes sense to use UDP, since in many cases you won't matter if packets arrive out of order.

A big problem with traditional polygonal approaches is texturing. Each vertex requires some UV parametrization that links the 3D model with the 2D texture space. It is a problem because a progressive mesh evolves in a way that may break its texture mapping. Often the solution was to create charts that were shared both by the model and the 2D space, and then constrain simplification to within the charts. This was too limiting, and it did not do well with massive topology changes.

What if I dumped 2D parametrization altogether? I could use the actual vertices to store all the information I needed, like material, illumination, etc. The mesh itself acted as a compression structure. If I had enough vertices, the results could be very detailed, same as if I was using conventional 2D mapping to store materials and lightmaps. Then the concept of material kicks in. A material is more than a texture, it can include displacement maps for tessellation, wang-tiles of very detailed geometry for instancing, instructions for procedural generators, etc.

I did some quick tests and saw this method was within what the current hardware generation can do. I did not like a couple of things about it. First, it required to render a lot of polygons. Newer systems could take it, but older ones did not do so well. And second, I would need to run some streaming logic on the server-side, making sure only those packets needed by the client were sent. I don't have the budget for running UDP-streaming servers right now.

So I did not choose this direction, but I think it has a lot of potential. I may come back to it later. As I see it, this method is an alternative to sparse voxel octrees. Voxels make most sense when polygons are too small. They don't require a 2D parametrization of your world anymore. And they can deal with topology simplification in a beautiful way. Progressive octree meshes does pretty much the same, as long as you don't allow your polygons to become very small on screen. The advantage is you may still use all the polygon hardware.

How much data?

2011-09-23T11:36:00.001-04:00

While we are in the subject of big data, I wanted to show how much detail these algorithms are able to generate. It may give you an idea of the amount of information that needs to be delivered to clients, one way or another.

Before anything else a disclaimer: the following images (and video) are taken from a mesh preview explorer program I have built. The quality of the texturing is very poor, this is actually textured in realtime using shaders. There are a lot of shorcuts, especially in the noise functions I use. Also the lighting is flat, no shadows, no radiosity. But it is good enough to illustrate my point about these datasets.

Take a look at the following screenshot:

Nothing fancy here, it is just some rock outcrops. In the next two screenshots you can see how many polygons are generated for this scene:

This is how meshes are output from the dual-contouring stage. If you look carefully you will see there is some mesh optimization. The dual contouring is adaptive, which means it can produce larger polygons if the detail is not there. Problem is, with this type of procedural functions there is always detail. This is actually good, you want to keep all the little cracks and waves in the surface. It adds character to the models.

Here is another example of the same:

These scenes are about 60x60x60 meters. Now extrapolate this amount of detail to a 12km by 12km island. Are you sweating yet?

I leave you with a screen capture of the mesh preview program flying over a small portion of this island. It is the same 60m x 60m x 60m view moving around, detail outside this view is clipped. The meshes loading here are a bit more optimized, but they still retain a lot of detail. I apologize for the motion sickness this may cause. I did not spend any time smoothing camera movement over the terrain.

Big Data

2011-09-12T11:07:00.000-04:00

The terms "Big Data" are frequently thrown around these days. I don't know about you, but this is what comes to mind:

Big Data is when you have so much information that traditional storage and management techniques begin to lose their edge.

One of the promises of Procedural Generation is to cut the amount of data required to render virtual worlds. In theory it sounds perfect. Just describe the world by a few classes, pick a few seeds and let everything grow from there. It is storing metadata instead of data. The actual generation is done by the player's system, data is created on-demand.

The problem is how to generate compelling content. The player's machine may not be powerful enough for this. Odds are you will end up targeting the lowest common denominator and your options will become seriously limited. For instance, Minecraft generates the entire world locally. This limits its complexity. Blocks are huge and there is little diversity. For Minecraft it works, but not many games could get away with it. If you want some kind of realistic graphics it is probably out of the question.

As it seems, data must be generated away from the user`s system. One possible approach is to use procedural techniques to create a static world. Whatever data constraints we may have can be built in as parameters to the procedural generation. For instance we could make it sure the entire world definition fits on a DVD.

On the other hand, procedural techniques can produce huge datasets of very unique features. If you don`t really need to fit on a DVD, Bluray or any type of media you can keep around your house, you could create very large worlds. This is not new, Google Earth already does that. You don't need to download the entire dataset to start browsing, it all comes on-demand. A game world would not be as large as our real planet, but it would be a lot more complex and detailed. The world's topology for sure will be more than just a sphere.

Then it becomes about Big Data. While generation and storage may be simple and affordable, moving that much data becomes a real challenge. What is the point of becoming so big when you cannot fit through the door anymore?

One option is not to move any data and render the user's point of view on the server. You would stream these views down to the player's machine pretty much like you would stream a movie. This is what the OnLive service does for conventional games. It is appealing because you can deal with bandwidth using generic techniques that are not really related to the type of content you produce, like the magic codecs from OnLive and their competition. But there are a few issues with this. Every user will create some significant load on the servers. Bandwidth costs may also be high, every frame experienced by the users must go down your wires.

The other option is to do it like Google Earth: send just enough data to the client so the virtual world can be rendered there. This approach requires you to walk a thin line. You must decide which portions of data to send over the wire and which ones can be still be created on the client at runtime. Then, whatever you choose to send, you must devise ways to compress it the most.

It is not only about network bandwidth. In some cases data will be so big, traditional polygon rendering may not make sense anymore. When you start having large amounts of triangles becoming smaller than actual pixels after they are projected into screen, it is best to consider other forms of rendering like ray-tracing. For instance this is what these guys found:

This is taken from their realtime terrain engine. This dataset covers a 56 km × 85 km area of the Alps at a resolution of 1 m and 12.5 cm for the DEM and the photo texture, respectively. It amounts to over 860 GB of data

I am a hobbyist, having dedicated servers to render the world for users is not even an option. I rather pay my mortgage. If I want anyone to experience the virtual world I'm creating, I will need to stream data to end-users and render there. I have not figured out a definitive solution, but I have something I think will work. My next post will be about how I'm dealing with my big data.

The case for procedural generation

2011-08-18T17:40:00.002-04:00

John Carmack recently said procedural techniques are nothing more than a crappy form of compression. This is while he was asked about the Unlimited Detail tech. To be fair, this should be taken only in the context of that question and runtime-engines, which is anyway a bit strange since Unlimited Detail is not really using anything procedural, it is mostly tiling instances of unique detail. Still, is he right about that? Is procedural generation just crappy compression?

Others have said that procedural generation in games inevitably leads to large, bland scenarios. Or maddening repetitive dungeons and corridors. As they put it, humans can only be engaged by content that was created by other humans.

I actually agree with them. And yes, you are still reading Procedural World.

Despite of what we naysayers may believe, procedural techniques have seen a lot of success already. It is not really in your face, not a household name, but it has been instrumental producing content that otherwise would simply not exist.

Take a look at this image:

Well thanks, it does looks like the shinny things I'm trying to do, but this is Pandora from the Avatar movie. Now, do you think this was entirely handcrafted?

Pandora is mostly procedural. They have synthetic noises everywhere, L-systems for plants and ground cover, it is actually a textbook example for procedural techniques. A lot of people went to visit it, and it made heaps of money. If you define success on those terms, this baby takes the cake. And it is thanks to procedural generation. Without it Pandora would have looked like this:

So clearly proceduralism can help creating appealing content. As Carmack says, it is some form of compression. What got compressed in this case was not information over the wire, or over the bus to the graphics card, it is the amount of work artists needed to do. Instead of worrying about every little fern, they could spend their effort somewhere else.

What is wrong with this? Now imagine it was a game and you were marooned in this huge Pandora place. You would probably get bored after a while, besides staying alive there is not much to do. If there is a thing we humans can do is we can get bored anywhere, all the time.

We need this sort of battle-is-brewing, storm-is-coming thing lurking in the horizon. We need a sense of purpose and destiny, or a mystery for the lack of it. Is this something that only other humans can create for us?

At this point it becomes about Artificial Intelligence. Think of a variation of the Turin Test, where a human player would not be able to tell whether a game was designed by another human or by a computer. This is the real frontier for pure Procedural Content generation.

In the field of physics there are two theories that are very successful in explaining the two halves of the real world: Quantum Physics and General Relativity. They don't get along at all. There is a discontinuity where one theory ends and the other starts.

A similar scenario can be found in Procedural generation. On one side you have the Roguelike-Dwarf Fortress type of games which can generate compelling experiences, but lack any visual appeal. These games use text or ASCII screens. It is like never jacking into the Matrix and keep staring at the floating text. Can you see the woman in the red dress?

Then any attempt to visualize the worlds they describe, the magic dies. You realize it was better when it was all ASCII, which is sad cause only weirdos play ASCII games.

The other side is rich visual worlds like Pandora. With the advent of computing as a commodity -the cloud- bigger and richer worlds will become available, even for devices with limited power like mobiles and tablets. But they lack the drama. Even a Pocahontas remix is beyond what they can do.

Triple A studios have realized this. It is better to use procedural techniques at what they do best: terrain filler, trees, texturing, and leave the creative work for the humans. They do not have a reason to invest in this type of AI, they won't push this front if it was up to them.

I do believe it is possible to marry these two opposed ends. Someone with an unique vision into both fields will be able to come up with a unified theory of procedural generation. And I think it will be the Unlimited Detail guys.

(EDIT: OK, OK. I'm kidding about Unlimited Detail. Their next bogus claim could be they made procedural content generation 100,000 times better. It is surprising to me they still can be taken seriously.)