Friday, October 7, 2011

Clipmaps

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.




9 comments:

  1. Maybe not directly related to your project but you might find this one interesting:
    http://www.youtube.com/watch?v=KfGX73NOA6I&t=9m50s

    ReplyDelete
  2. @Obi: Thanks, I saw it a few days ago from the Tuan Kuranes Twitter feed: @tuan_kuranes.

    Here they show neighbor patches at different resolution still sharing the same vertices on their edges. Their method does not need dependencies between one patch and another, so it lends well to parallelism.

    ReplyDelete
  3. Have you seen the implementation in GPU Gems for avoiding popping? As you get get farther out on the clipmap, you linearly interpolate the heightmap you're using to the next LOD in the vertex shader. And then you have a ring that seals any TVerts that may have been formed to make everything watertight. That way, everything slightly changes when you move, but the movement covers it up.

    ReplyDelete
  4. @Reavenk: Yes I saw that one. The method is for heightmaps, it does not apply to my case. In a heightmap topology never changes, no matter the resolution of the cell.

    ReplyDelete
  5. But maybe you could do something similar? At the far outer edge of each ring, send info for those cells which has the same number of vertices as the normal mesh for that cell, but positioned to represent the topology of the next lower level of detail, in addition to the normal cells being sent. Then for each vertex in the cells in the outer edge of the ring, interpolate position between those two meshes based on distance from the outer edge of the ring.

    Doesn't seem that difficult on the client side. Am I missing something that makes this harder? Maybe it's difficult to generate the lower-detail topology with a higher-detail mesh on the server side?

    ReplyDelete
  6. @elias: Yes it is possible. I actually found a nice way to do it using space warps on both ends of the seams. I'm not so sure I need that, however. So far the overbite between adjacent cells is working pretty well. We'll see.

    ReplyDelete
  7. One thing I don't undertand though, is how you are mapping your 3D terrain data, complete with overhangs and voxel islands disconnected from the main terrain, into clipmaps which are inherently a 2D construct designed to drape grids of vertices over a heighfield.

    How did you rework clipmaps to support overhangs?

    Are you adapting the classical 2D clipmap system so instead of having each clipmap as a single continuous mesh of vertices, it is instead a 3D block of octree data which is then later converted back into polys as per your OpenCL work?

    ReplyDelete
  8. @RobH: Well clipmaps is the technique of having concentric rings of decreasing resolution around the viewer. It can be applied to textures and geometry of different topology. Heightmaps is just one case.

    As you say, in my case each ring is composed of an array of 3D blocks having the same dimensions. For each following ring, the size of the block is eight times larger.

    ReplyDelete