Home       About Me       Contact       Downloads       Part 53    Sleepless   

Part 54: Stuck

April 12, 2012

Fig 1: Heightmap-based landscape

Since the beginning of the project, I've been talking about putting Minecraft-style structures made of cubes on a polygonal landscape. I just can't render a large world with distant views if it's all made of cubes. They take too long to render, and are too hard to summarize in the distance. Also, I just like the look of a polygonal landscape. Figure 1 looks much better to me than anything done with cubes.

I've been doing polygonal landscapes with heightmaps. You have a grid in x and z, and each point has a height in y. Each square cell of the grid is drawn with two triangles. In Part 28 I showed how you could vary the resolution of a quad-tree, where each node contained a 32 by 32 heightmap. By using coarser grids in the distance, the demo can draw a view right out to the horizon without using too many triangles.

The problem with heightmaps is they are only vertical. If you play with Minecraft, you can see that caves are really important to the look. On the TwentyMine server, there are all kinds of interesting underground structures. So although my fallback was to just use heightmaps and let you dig vertically before building, I've wanted a better data structure.

In particular, for my asteroids, I want you to be able to carve them up and make any structure you like out of them, from a hollow habitat (Figure 2), to some bizarre nesting of levels and structures at all angles.

Fig 2: A hollow asteroid
I've been toying with different kinds of data structure for months now, trying to find one that would do what I want:
  • It has to handle arbitrary 3D shapes with mountains, caves, holes, etc.

  • When the player digs through a mountain or shell of an asteroid, I need to easily know when he's broken through to the other side.

  • I need to be able to summarize landscape at lower resolution in the distance. For example, if you dig out a mountain, ideally I'd like to see some sign of the holes when you move far away.

  • The rendering code can quickly extract a list of triangles to draw, and they should not include too many extra, obscured triangles.

  • I should be able to do at least what a heightmap would do.

  • It can't take a ridiculous amount of memory for the kind of landscapes I'm using.

Six-sided height maps

Fig 3: Height maps in all directions
In the asteroid case, the ground might be oriented in any direction, so I decided the simplest approach was a cube with a height map on each face. When I needed to switch directions for a cave, I would just build another level of the tree and have a heightmap in the correct direction. In two-dimensions, Figure 3 shows a bunch of heightmaps in all directions.

You can start to see the problems even in this illustration. The data structure does not enforce anything about the height map values, so they might not meet up at corners, or the bottom heights might extend until they hit the opposite face, or even the sides. As you dig, I would continually have to check the intersections with the nearby faces, both horizontal and vertical.

I was also originally thinking each node in the tree is a 32 by 32 by 32 cube with a heightmap, but this won't work. It would only allow you to dig 32 by 32 meter holes in the landscape! To have arbitrary shapes, I would have to take the scale down to a single cube. If each cube had a 32 by 32 heightmap on each face, that's too much memory.

After more thought, I decided that this all really reduces to an Octree, and the only question here is what shape is in the leaf cube.

Leaf Shapes

Fig 4: Larger cubes in the distance

If you kept only a single bit per leaf cube, you'd have a Minecraft-like world, except with larger cubes in the distance. This works and satisfies all my criteria except that it looks terrible. It won't do the nice landscape in the distance that a heightmap will do.

Fig 5: 8-point
To implement a heightmap, the leaf cube has to handle a height at all four corners. To handle my asteroid case, it has to do this in any of the six face directions. Last week, I was thinking that I would just implement the leaf cube with 8 points that can have arbitrary positions within the cube (Figure 5.) The leaf shape is drawn just as I currently draw cubes -- with two triangles per face.

If I set the bottom corners to be at the cube points, and the top corners to follow the heightmap, I could do everything I currently do with heightmaps. When digging, I would need to push the corner points into the cube until they intersected the opposite face. At that point, the cube is empty.

Fig 6: Clipped
Unfortunately, since I'm so poor at visualizing things in three dimensions, the obvious problem had never occurred to me. The adjacent points of a heightmap landscape are not necessarily within a cube. In fact, clipped to a cube, you can get some nasty shapes (Figure 6.) To avoid this, I would have to constrain the 8 points to be within the cube, which restricts the shapes the player can build.

You might think this doesn't matter, and close up, it probably wouldn't matter much. It would just mean that as you dig, whole cubes disappear when you think there should still be a sliver. In the distance though, constraining the surface points to fit in a cube means you can't have more than a 50% slope, and the mountains of Figure 1 are impossible. It would also be impossible to draw a deep cut into a more gently sloping mountain.


Fig 7: Subdividing tetrahedra
If the surface of the heightmap is drawn as two triangles per cell, then my leaf shape is the union of two tetrahedrons. I briefly considered redoing the whole thing with a tree of tetrahedrons, since the landscape shape can definitely be broken up that way.

Unfortunately, the tree wouldn't have a nice structure like the Octree. The tetrahedron would not be split at regular intervals -- that would just build the landscape out of fixed-sized pyramids instead of cubes. Instead, we need to split at arbitrary points along the edges.

If you imagine a large "universe"-sized tetrahedron, the landscape would be a bit of noise at the bottom. As you subdivided the top level tetrahedron, you would get all kinds of thin slices, leading to round off errors and probably some "flimmering" when you drew parts of the shape.

I also rejected this because I simply can't visualize what is going on. In the simple case of Figure 7, where you cut each edge at one point, how many child tetrahedra are there? I can't visualize what is happening in the center. I could probably look it up somewhere, but the fact that it's not obvious to my defective 3-d reasoning makes me nervous. This is not a data structure I want to work with.

Oriented cubes?

Fig 8: Oriented cubes
I have two problems with the leaf shape. One is that I'm insisting on doing everything from all six sides of the cube. That makes even a simple shape much more complex. I could solve this by orienting the cubes, so that the shape, whatever it is, always faces "up".

Figure 8 shows the 2D version. Independent of rotations, there are two cases. The box is either on the axis or on the diagonal. Picture a little heightmap or whatever inside each box, where "up" is in the direction of the arrow.

In 3D, there would be three cases -- the cube imbedded in a surface, with one face exposed, the corner with two faces exposed, and the corner with three faces exposed. I could define "up" in the corner cases as pointing along a diagonal of the cube.

Doing the cubes this way means checking that when the player deletes a cube, I also delete neighbors to make sure no cube has opposite sides exposed. That's manageable.

The other problem is the shape itself. I could just go ahead and use four heights making two triangles, and clip them to the cube. A stack of these with a steep slope is going to draw all the clipped shapes, and there is some round-off error to worry about, but it would work.

When you are digging, you might touch the middle of a sequence of these cubes, all with identical slopes. I'm not sure what happens to the middle cube in that situation, or how I adapt the neighbors.

I'd like to find some more natural shape to put in the leaf cubes, so that the landscape is built out of these shapes, and digging just removes some of the shapes. Perhaps there's a better way to do the whole thing! I'm open to suggestions.

Home       About Me       Contact       Downloads       Part 53    Sleepless   

blog comments powered by Disqus