{"id":345,"date":"2010-05-24T06:46:10","date_gmt":"2010-05-24T06:46:10","guid":{"rendered":"http:\/\/the-witness.net\/news\/?p=345"},"modified":"2010-05-24T06:46:10","modified_gmt":"2010-05-24T06:46:10","slug":"kriging-is-cool","status":"publish","type":"post","link":"http:\/\/the-witness.net\/news\/2010\/05\/kriging-is-cool\/","title":{"rendered":"Kriging is cool."},"content":{"rendered":"

In The Witness<\/em> we decided that it's a good idea to have a heightfield terrain making up the bulk of the island surface. \u00a0The advantages of this are in rendering performance and in ease of texturing (it is relatively easy, with one continuously-parameterized terrain block, to get rid of seams; if your terrain is a bunch of otherwise-unrelated meshes, then what do you do?) When we made this decision it seemed clear to me that the biggest disadvantage, for this game at least, was authoring the terrain. \u00a0There are typically a few different ways that large heightfields are built:<\/p>\n

    \n
  1. Use an external terrain editing tool and then write an importer for its file format<\/li>\n
  2. Build a terrain editing tool into the game's editor (this will require a bunch of work to do a good job, and will have fewer features than an external tool but they may be more appropriate for your game; also, you can make reasonable things happen to entities placed in the world when you interactively move the terrain around)<\/li>\n
  3. Paint heightmaps in an image editor like Photoshop and hotload those from the game engine (requires much less programming; doesn't provide many features, but you have very fine control over the results; unfortunately, the editing process becomes pretty cumbersome)<\/li>\n<\/ol>\n

    These seemed to be the main approaches on offer. \u00a0However, I wasn't enthusiastic about doing any of the traditional things; I have written a number of terrain systems for games, and what bugged me, with respect to this game, was the way in which terrain handling tends to be very different from laying out objects in the world, and how this creates an extremely disjoint work process.<\/p>\n

    In concrete terms, this means that terrain was not going to be as malleable as the other objects in the world. \u00a0I am taking a very rough-drafty approach to the game; we are building areas, then moving them across the world if we feel they will work better somewhere else, rotating them as a group, etc. \u00a0The goal is to build a very-cohesive game world in which carefully-tuned gameplay is the most important thing -- where we more-or-less have a rough draft of the whole world set up before we go in and try to get serious about how everything looks.<\/p>\n

    This kind of approach just dies when you have elements that behave very differently, and are difficult to manipulate together, such as terrain and objects. \u00a0If I have two hills with a path winding between them, a bench by the path with a book upon the bench, and a signpost nearby, what happens when I want to move that scene across the map and then rotate it by 30 degrees? \u00a0With the entities, it is no problem, we just do that in the editor. \u00a0But with the terrain it just becomes a mess to move the hills at all, regardless of which of the above approaches are used. \u00a0And if you want to move and rotate the hills in sync with the entities so that the whole scene is intact... good luck!<\/strong><\/p>\n

    To solve this problem, terrain needed to be built in the in-game editor, in a way that would be maximally malleable -- so that I can pick up a hill and rotate and drag it. \u00a0Because of the requirement for rotation, you can't really be manipulating samples directly; it has to be control surfaces of some kind (because if you are just blitting samples around, a few rotation operations are going to mangle whatever original shapes you made).<\/p>\n

    As for control surfaces, the first ideas that come to mind are things like spline patches. \u00a0But the problem with spline patches is that you have to be very careful managing the control points in a patch, and they ultimately aren't that malleable -- what if I want to split a patch in half without changing the shapes of areas near the edges? \u00a0What if I want to move one small, high-detail terrain area so that it overlaps somewhat with a big, low-detail area? \u00a0How is that going to work? And if I have spline patches, then any time I instantiate a new grid of patches, I have to manage a bunch of individual control points, which is labor-intensive. \u00a0If I am rough-drafting, I want to do the minimum possible work to lay out a given area. \u00a0If I just generally want to build a hill but don't care much about its shape, I ought to be able to do that with just 2 or 3 control points, arbitrarily-placed.<\/p>\n

    Clearly what I wanted was a system that would just look at a set of unstructured control points -- no topology or anything -- and generate a terrain from those points in the local area. \u00a0When there is no topology or parameterization, you can merge and split groups of control points at will; you can have them overlap; you can do whatever you want.<\/p>\n

    I started putting together an ad hoc scheme for doing this, but did not take it very far before discovering that the mathematics for doing a good job at exactly this problem had already been invented decades ago. \u00a0The method is called Kriging<\/a>, and it is well known in geostatistics. \u00a0If you've got a survey of height field data (or any other field data -- the density of a mineral at certain points, for instance), and that data is missing values for some locations, Kriging will give you a reasonable guess at the values of the field at the unknown points.<\/p>\n

    For rough-draft terrain modeling, we can turn the idea around; if we give a Kriging function only a small set of known data points, it will do a quite fantastic job of filling in the values at all the other points. \u00a0The basic math involves the inverse of an n by n matrix, where n is the number of known data points. In theory that could become a huge computation, but for the number of points we may typically have in one local area of the map, the computation is easy for modern CPUs. Kriging is not hard to implement; I started with some public domain code written at a university and modified it for our needs (though this basically involved rewriting it, as it was messy and had some serious bugs! \u00a0If anyone wants our version of the Kriging code, drop me a line).<\/p>\n

    Here's how we have it integrated into our game engine. \u00a0There's a type of object that exists as a set of terrain control points, which can be moved around the world arbitrarily, just like anything else. \u00a0It looks like this:<\/p>\n

    \n\t\t

    \n\t\t\t \t\n \"untitled-1\"\n\n \t<\/a>\n\t\t <\/div>\n <\/span> <\/p>\n

    The only meaningful data in this object, with respect to terrain shaping, are the positions of the control points (purple boxes). \u00a0The surface is just a visualization; it tells you what surface these points would define if they were the only control points in the universe. \u00a0(Though actually, the surface defined by those points would extend infinitely in all directions; this visualization stays within the convex hull of the control points, which helps you see what you are doing when editing).<\/p>\n

    Right now these control points haven't actually been applied to the game's terrain (green surface below); they are just hovering above it. \u00a0Here's a shot from another angle:<\/p>\n

    \n\t\t

    \n\t\t\t \t\n \"untitled-2\"\n\n \t<\/a>\n\t\t <\/div>\n <\/span> <\/p>\n

    I can press a key to add a new control point to this object:<\/p>\n

    \n\t\t

    \n\t\t\t \t\n \"untitled-3\"\n\n \t<\/a>\n\t\t <\/div>\n <\/span> <\/p>\n

    The new control point doesn't affect the shape of the old surface in any way, which is very convenient. I can drag the new control point at will:<\/p>\n

    \n\t\t

    \n\t\t\t \t\n \"untitled-4\"\n\n \t<\/a>\n\t\t <\/div>\n <\/span> <\/p>\n

    Or add many more control points:<\/p>\n

    \n\t\t

    \n\t\t\t \t\n \"untitled-5\"\n\n \t<\/a>\n\t\t <\/div>\n <\/span> <\/p>\n

    Here's that same visualization surface, with the control points and gridding turned off, so you can see it better:<\/p>\n

    \n\t\t

    \n\t\t\t \t\n \"untitled-6\"\n\n \t<\/a>\n\t\t <\/div>\n <\/span> <\/p>\n

    Then, when I decide I like the shape, I can press another key to apply these control points to the game's terrain:<\/p>\n

    \n\t\t

    \n\t\t\t \t\n \"untitled-7\"\n\n \t<\/a>\n\t\t <\/div>\n <\/span> <\/p>\n

    (Now there's a lot of z-fighting between the control surface and the terrain because they are in pretty much the same place.)<\/p>\n

    Here is the terrain with the control surface hidden. \u00a0Note that the terrain values have been smoothly interpolated, even in areas outside the control object:<\/p>\n

    \n\t\t

    \n\t\t\t \t\n \"untitled-8\"\n\n \t<\/a>\n\t\t <\/div>\n <\/span> <\/p>\n

    (By the way, those seams you see in the previous two pictures are lighting seams. \u00a0These don't have anything to do with Kriging, it's just that the terrain blocks don't know how to look up their neighbors' height values when generating their surface normals. \u00a0Any block-based terrain system has to solve a similar problem. \u00a0It's easy to solve, but at a low priority on the to-do list, hence it hasn't been done yet. \u00a0The distance between seams tells you how big the terrain blocks are, so the seams are sort of useful in this image!)<\/em><\/p>\n

    Suppose this control surface is part of a scene that I want to reorient. \u00a0I'll rotate it about 70 degrees clockwise (now you'll see the surface intercutting more-heavily with the existing terrain values):<\/span><\/em><\/p>\n

    \n\t\t

    \n\t\t\t \t\n \"untitled-9\"\n\n \t<\/a>\n\t\t <\/div>\n <\/span> <\/p>\n

    And then once again, I apply Kriging to the terrain, generating the same hills in a rotated orientation:<\/p>\n

    \n\t\t

    \n\t\t\t \t\n \"untitled-10\"\n\n \t<\/a>\n\t\t <\/div>\n <\/span> <\/p>\n

    To illustrate the way that interpolation is not confined to a single control object, and that in fact this is a control point soup, here I've created three control objects:<\/p>\n

    \n\t\t

    \n\t\t\t \t\n \"untitled-11\"\n\n \t<\/a>\n\t\t <\/div>\n <\/span> <\/p>\n

    And here's what the terrain looks like with them applied:<\/p>\n

    \n\t\t

    \n\t\t\t \t\n \"untitled-12\"\n\n \t<\/a>\n\t\t <\/div>\n <\/span> <\/p>\n

    And here's the final terrain along with the control objects (lots of z-fighting again):<\/p>\n

    \n\t\t

    \n\t\t\t \t\n \"untitled-13\"\n\n \t<\/a>\n\t\t <\/div>\n <\/span> <\/p>\n

    Hopefully that's enough screenshots to illustrate the point. \u00a0Compared to splines, Kriging has the following highly beneficial properties (aside from the huge benefits of not requiring a topology, discussed above):<\/p>\n