Home       About Me       Contact       Downloads       Part 72    Part 74   

Part 73: Topology

December 2, 2012

This week I was trying to make the project a bit more interesting by rendering the summary landscape on different surfaces. In the SeaOfMemes version, I'll have large spheres (the planet and moon), small spheres (the asteroids), large cylinders (the ringworld around the moon), and small cylinders (the hollow asteroid habitats.) Each of these turns out of have different issues.

First, the hollow asteroid habitat:

Fig 1: Life in a can

This has a surface area 4km along the axis of the cylinder, and 8km around the circumference. I think this is a reasonable size, but it is striking how curved the landscape is here. You are really going to notice it as you move. I think you'll also notice it as you build, since bricks will get narrower the higher you go. The radius is 1.3 km, and I've limited building height (and terrain height) to 1km.

I've played with a cylindrical rendering before, back when I was drawing everything a brick at a time. In that version, I just modified the shader to generate new coordinates at draw time. That's a waste of GPU cycles though, since I can generate cylindrical coordinates in the vertex list when I build it.

What I discovered however is that my new code, which combines faces into quads, can't be modified that way. Imagine a chunk that is all water. This generates a single quad over the entire chunk. If I map the corner vertexes into cylindrical coordinates, I get a flat quad between two points on the cylinder. Oops!

All my summary code stores the results as quads, so I had to invert that and break the quads back into individual cells and map their corners to the cylinder. Fortunately, the fall off in resolution keeps the number of cells reasonable, and this still has a decent draw speed.

To avoid this, I guess a geometry shader that computed individual cell bounds would cut the number of vertexes in the buffer. That would come at the cost of more GPU work on each draw though. And I don't have geometry shaders on the OpenGL 2.1 devices.

Fig 2: Subdividing chunks

The other complication here is my terrain management algorithm. Chunks near the eye are smaller, distant ones are larger. I had all this code working in three dimensions, but with a flat coordinate space. If I wrap the coordinates around a cylinder, the eye can be near the opposite side and cause increased resolution there as well as the floor underneath.

That required me to change the terrain code to work in world coordinates instead of grid coordinates. Figure 2 shows my test program on the ringworld surface. I'm using a bit of satellite imagery for the tile here, since it gives me some idea of what landscape will look like at a distance. That's a 256 by 256 tile, which is the upper limit of what I can use on each 32 by 32 grid.

The ringworld is 256 km across, and has a circumference of 16,384 km. Figures 3, 4, and 5 show views of the ring and terrain for context. The patch of Minecraft data in Figure 5 is about 4km by 8km.

Fig 3: Cells of the ring

Fig 4: With Minecraft summary data

Fig 5: The ring is huge

The Eight Corners of the World

I have been drawing my spheres by mapping six cube faces onto the surface. I just divide the cube vertex by its distance from the center and that gives me a decent grid (Figure 6.) The cells aren't square, but they don't bunch up anywhere and are easy to traverse. I had originally wanted to generate polygonal terrain, and if I do that at each vertex, everything will look fine. In fact, the moon in SeaOfMemes is generated this way.

Fig 6: Turning a cube into a sphere

Fig 7: One cube face covers a lot
For now, I've decided to just stick with cubes everywhere, and that creates a problem. If I use this structure, even if I subdivide it down to 1 meter resolution, there will be twelve noticeable seams and eight corners to the world! At these points, you just won't be able to build a normal structure.

I'm not sure what the right answer is here. There is no perfect tiling of squares onto a sphere. On the other hand, it occurs to me that you can never see more than half the sphere. I can extend a single cube face over that entire area (Figure 7).

At this point, I'm thinking that perhaps when a structure is created, I either start a new grid centered around that point, or use the grid of a nearby structure. Then they will grow as the community grows. On a planet, you aren't going to have a single structure that circles the world, and so you'll probably never see the edges of the grid.

If I keep each community on its own grid, it could all work. Only when two huge grids (hemisphere-sized) try to grow together would there be a problem. And in that case, I think I'd just have to kludge something up. You won't be able to join two huge grids, and so there will be places you can't build.

For any normal pattern of growth, this won't be a problem. Two less-than-huge grids could could be combined into one and the positions of buildings subtly adjusted. I think players would never notice it.

You might think that when the planet is viewed from orbit, this would never work. Don't I need a position for all the landscape blocks? But these are procedurally generated and can be created on any vertex positions. All grid spacing does for landscape is create very subtle distortions in sampling of the same landscape.

I think I could show the grids under cities and so on, filled with procedural landscape between them. I'm open to suggestions though, since I haven't implemented any of this.


This approach is not going to work for asteroids. They are so small that a grid could easily wrap the entire sphere. Also, they are small enough to tunnel through, so you might see parts of the inside or back side all in a single view.

I can think of only two alternatives that make sense for small spheres. I could just use a flat coordinate space and make a spherical shape out of blocks. That will mean that as you walk on the sphere, you go from flat tops to corners sticking out of the ground. I think that would be ugly and very hard to build on, but it would be consistent.

However, the problem here isn't really tilted blocks -- it's the combination of a flat coordinate space and gravity. If there were no gravity, you'd just be building a big structure in three dimensions, and would float around to whatever point you like, inside or outside. I'd have to try this to see how it feels, but implementation is no problem. My current terrain and summary algorithms are exactly what I'd need.

A second approach is to do all asteroids as cylinders. This is consistent with the habitat cylinders, although I have no idea what to do about gravity. With a cylinder coordinate space for asteroids, you can walk around them and blocks stay flat, and you can build easily. The problem is that the north and south poles will feel like cliffs, not flat terrain. This still might be playable though.

That's all for this week. I will probably get terrain generation on the fly to work and populate out all the surface of the ring. I don't know whether to try mapping the test landscape to a small sphere or not. Once I get chunks loading and unloading in the background (needed for decent performance), I can make some videos or demos of what I have.

Home       About Me       Contact       Downloads       Part 72    Part 74   

blog comments powered by Disqus