Home       About Me       Contact       Downloads       Part 54    GUI Design...   

Sleepless in Sacramento

April 19, 2012

In the last part, I described keeping the landscape as some kind of Octree, and was trying to figure out the shape of a leaf node. I needed something that would do heightmaps, but also let me break things into cubes, and dig holes in the landscape. I was imagining some kind of discrete shape, like a collection of tetrahedra.

Fig 1: Hermite data
Reader Scott Richmond linked three papers on variations of "Dual Contouring", which I think will be the right answer. The leaf cubes will contain up to 12 points, the intersection of the desired surface with the edges of the cube. Each point also has a normal associated with it, indicating the direction of the surface. In two dimensions, it looks like Figure 1.

In the papers, this is called "Hermite" data, and the algorithms use a "quadratic error function" which is minimized to place each polygon point during a modified "Marching Cubes" algorithm. I am still working through the papers to figure out what this all means!

The surface intersections and normals are easy to generate from the procedural heightmap-based landscape. I'm not sure exactly how I'll be manipulating those when the player digs holes. And I'm not sure when I recompute the polygonal form of the surface. I don't know how expensive that will get, and whether I can do it in sections (so they can be cached), or if I have to redo the entire landscape on each change. Since the input cubes change whenever you move (cubes get smaller as you move nearer) or when you dig, this needs to be fast.

Sleepless

I'm not sure when I'll get this working. My health has really been acting up for the last month or two. I haven't had a decent night's sleep in weeks. I've been staring at these papers for the last week, but I just don't have enough brain cells working at this point to figure out the algorithm.

While I wait for a doctor's appointment and the inevitable tests, I've decided to work on some odds and ends like my old GUI and adding features to Crafty. That can be done in small bursts and don't require any math, which my tired brain just isn't capable of right now. I'll post again when I get something working.

Home       About Me       Contact       Downloads       Part 54    GUI Design...   

blog comments powered by Disqus