Monday, January 25, 2010

Initial lander terrain triangulation

I'm back in the saddle again (barely) on my lunar-lander-on-a-disc program. (The latest released version is here, but does not include today's changes.) I am working on triangulating the terrain so I can draw it as a solid mass rather than an outline.

My first pass does the job and fits into the recursive framework for how I'm creating the BSP and outline, but it isn't ultimately what I'd like because it wastes a ton of triangles in the interior:

I could just triangulate the outline, and I may end up just doing that. It will result in long sliver-like triangles, which aren't necessarily a problem. If I decide I'd like to render the terrain in several discrete chunks that can be culled independently, though, I'd want something different. I don't yet have a solid vision for how the terrain ought to look, so I'm experimenting.

I think I'd like something that is similar to this but replaces clusters of solid triangles with larger ones, so I'm working out how to do that.

I also want to filter out those inaccessible pockets inside the terrain (and maybe the floating islands), so I'm trying to figure out the best way to do that. I have several representations of the terrain and it's a trick to figure out how to process them all. The outlines would be an easy thing to cull: just remove all the ones that wind in the interior direction. Fixing up the BSP to remove the pockets would be more of a challenge, though. I sort of want to flood-fill BSP leaf nodes. BSPs don't have readily accessible connectivity information between adjacent cells, though.

Scott said...

How are you generating the outline to begin with exactly? Do you have an image map of your noise function it was generated from? For a terrain engine prototype I made, I used a modified marching squares to convert the anti-aliased mask of the terrain into an outline. I drew the same mask to the screen using alpha testing to see how well it would match up with the generated outlines. It worked fantastically even when magnified up by 16x.

Personally I'd leave the islands in. I think they are cool. If you want to get rid of the caverns, you can check which of the loops have a reversed winding if you track such things.

James McNeill said...

The outline, triangulation, and BSP are currently all generated in a single recursion. It starts with a triangle encompassing the planet, subdivides it to a depth of nine steps (splitting each triangle into four at each step), and then evaluates a density function at the resulting points. If a leaf triangle has one or two corners outside and the other(s) inside it generates a line segment. There's a binary-tree data structure for keeping track of the endpoint indices for sharing with the neighbors. The BSP generation is pretty simple; the line segments make splits, and empty children are coalesced as the recursion unwinds to reduce the number of nodes.

Typical stats for a current planet: 7000 line segments in the outline; 22500 splits in the BSP; 110000 triangles and 110000 vertices in the triangulation. Obviously the triangulation is ridiculous for the complexity of the boundary.

Marching squares is definitely a possibility for the boundary, although I suppose I'd need to do the BSP some other way.

Yeah, I like the islands too. What I'd really like is to find a way to create background layers of terrain that "support" the islands. One way would be to make the density function 3D (not hard) and then take N slices at various depths behind and union them together. It would not guarantee support for everything though.