This is an experiment in writing up a blog post for a development task while I actually perform the task! So right now, as I start writing this, I don’t know how it will end!
I was talking to David Hellman about the game the other day, and he was asking when the island was going to become less like a flat plane where you can just walk to any destination from anywhere else.
It’s been on my to-do list for a while to add more topology to the island. That week I had been working on an area full of puzzles, and I wanted the buildings that define this area to have more of a purpose than they currently do; a topological purpose seemed like the right thing.
So I figured I’d add a canyon, and the building containing these puzzles would also serve as a bridge across the canyon.
The natural way to build the canyon in this engine is to shape it out generally with terrain control points, and then make the walls steep by putting mesh objects in there (so that you can’t walk up them, and so that the walls of the canyon won’t look super-distorted the way heightfield terrains usually do when there are steep slopes.)
Here was the first cut at it:
As you can see, there are a lot of weird ripples and curves happening there. This is what signal processing people might call “ringing”. What’s happening is that the Kriging system that we are using for terrain modeling is always trying to reconstruct a smooth function, but what we are trying to build here is a discontinuous function (or else a function so steep that it has a lot of high frequencies in it).
There are a number of ways that one might fix this, but the cheap and hacky one, which would work not only for Kriging but for any other terrain modeling stuff we might stick in in the future, is to add the notion of separating planes that represent discontinuities in the terrain. When evaluating the height of the terrain at any point, we just ignore any control points that are on the other side of the separating plane.
Adding discontinuities has been on my to-do list since last year when Kriging was added to the engine. It was pretty obvious that it would be needed eventually, but in the spirit of getting things done and not rat-holing on technology, I chose to put it off for as long as possible. But it makes sense that if we are starting to add more topology to the island, we are going to want to have more steep places, and so it’s time to add this.
(We’ve already had this steepeness problem before, though: if you look at this plateau that is near the camera in our regular island snapshots, you’ll see that the whole thing is made out of mesh objects, rather than terrain; we did this in order to avoid this very same ringing problem:)
It didn’t take long to add discontinuity entities into the editor; here’s how they are represented:
To start with, I just used a really dumb heuristic to decide when control points should be excluded. When we use this, here’s the result:
There is still a bunch of heightfield terrain sticking out. What’s going on? If we look back at our red discontinuity planes, it is clear that there are some terrain sample points inside the canyon that are getting treated as if they were outside:
What’s going on is that my simple criterion said “if you are on the opposite side of a discontinuity plane from a control point, ignore that control point”. The problem is that I am treating them as infinite planes, so those points that you see, which are in front of one plane, are actually outside a neighboring plane, if you were to extend that plane infinitely. This is no surprise; I knew it would be a problem, but I am always about implementing the simple thing first and seeing what happens. But now I need a heuristic that will fix this problem.
One solution would be to combine the discontinuity objects into sequences of points, and then do some more-heuristicky things that may be easier because we have an ordering between the points. But I don’t want to resort to that if I don’t have to, because that may make the system less general, and may make it harder to edit. (Then again it may make it easier to edit, because we have editor support for paths! But if we want to, we can easily go the other way, from a path down to individual slabs, so it’s better to take the most-primitive thing as input if we are able to.)
I added a check that would make discontinuity planes irrelevant if the sample points are closer to the side planes of these very thin slabs than they are to the face planes. In theory that would at least help, but upon running this, the scene looked almost exactly the same.
Then upon further investigation I found that I was computing totally wrong planes in the Kriging code; I was transforming the coordinates incorrectly, and so the planes were not in fact where the red slabs in the picture would show them to be. I fixed this:
Ahhh, much better. This seems like it will be good enough for now. There’s still the question of how to seamlessly blend the heightfield terrain into the mesh objects, but that can wait until closer to ship. For now, it doesn’t need to be pretty; it just needs to let us build things of roughly the right shape.
The heuristic I use for discarding points is still pretty simplistic and may cause problems. My hope is that most of those problems can be worked around just by changing the planes a bit. If that turns out not to be true, a little more work will need to be done here!