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.
Six-sided height maps
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.
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.
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.
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.
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.
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.
blog comments powered by Disqus