Earlier this year, some friends and I, all successful independent game developers, put together the Indie Fund in order to help support newer folks with good ideas.  All the hoops involved in setting up such an organization have been passed through, and we are now open for general submissions.  If you are an independent developer who needs money for a project-in-progress, go check out the Apply page to see what kinds of games we are looking for.

Thanks, and good luck!

1. Use an external terrain editing tool and then write an importer for its file format
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)
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)

These seemed to be the main approaches on offer.  However, 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.

In concrete terms, this means that terrain was not going to be as malleable as the other objects in the world.  I 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.  The 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.

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.  If 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?  With the entities, it is no problem, we just do that in the editor.  But with the terrain it just becomes a mess to move the hills at all, regardless of which of the above approaches are used.  And if you want to move and rotate the hills in sync with the entities so that the whole scene is intact… good luck!

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.  Because 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).

As for control surfaces, the first ideas that come to mind are things like spline patches.  But 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?  What if I want to move one small, high-detail terrain area so that it overlaps somewhat with a big, low-detail area?  How 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.  If I am rough-drafting, I want to do the minimum possible work to lay out a given area.  If 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.

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.  When 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.

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.  The method is called Kriging, and it is well known in geostatistics.  If 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.

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.  The 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!  If anyone wants our version of the Kriging code, drop me a line).

Here’s how we have it integrated into our game engine.  There’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.  It looks like this:

The only meaningful data in this object, with respect to terrain shaping, are the positions of the control points (purple boxes).  The surface is just a visualization; it tells you what surface these points would define if they were the only control points in the universe.  (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).

Right now these control points haven’t actually been applied to the game’s terrain (green surface below); they are just hovering above it.  Here’s a shot from another angle:

I can press a key to add a new control point to this object:

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:

Or add many more control points:

Here’s that same visualization surface, with the control points and gridding turned off, so you can see it better:

Then, when I decide I like the shape, I can press another key to apply these control points to the game’s terrain:

(Now there’s a lot of z-fighting between the control surface and the terrain because they are in pretty much the same place.)

Here is the terrain with the control surface hidden.  Note that the terrain values have been smoothly interpolated, even in areas outside the control object:

(By the way, those seams you see in the previous two pictures are lighting seams.  These 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.  Any block-based terrain system has to solve a similar problem.  It’s easy to solve, but at a low priority on the to-do list, hence it hasn’t been done yet.  The distance between seams tells you how big the terrain blocks are, so the seams are sort of useful in this image!)

Suppose this control surface is part of a scene that I want to reorient.  I’ll rotate it about 70 degrees clockwise (now you’ll see the surface intercutting more-heavily with the existing terrain values):

And then once again, I apply Kriging to the terrain, generating the same hills in a rotated orientation:

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:

And here’s what the terrain looks like with them applied:

And here’s the final terrain along with the control objects (lots of z-fighting again):

Hopefully that’s enough screenshots to illustrate the point.  Compared to splines, Kriging has the following highly beneficial properties (aside from the huge benefits of not requiring a topology, discussed above):

• Always interpolates every control point exactly
• Adding a new control point does not change the existing surface at all.
• No funny spline-like behavior (curves appearing in strange places, huge overshoots, etc)

Hacking In Compact Support

When doing Kriging in a video game, you probably don’t want to compute the terrain for the entire world at once for every change, because that would be very expensive, and it also is a little bit unintuitive (since a change to a control point very far away could change some interpolated terrain nearby, even if only slightly).  However, the vanilla Kriging algorithm would require global computation and thus behave nonlocally.  For The Witness we clearly wanted our control points to affect only nearby areas, i.e. have compact support. My first attempt at this was:

• Pick a radius r0 at which any control point has maximum effect, and a larger radius r1 at which the point has no effect, with smooth interpolation in-between.
• Terrain consists of contiguous blocks 33×33 samples in size.
• For each block of terrain you want to Krige, find all control points whose distance in the XY plane from any sample in the block is less than r1 (these are all the control points that could possibly affect any sample in the block).
• Pass all these points to the Kriging routine, which computes every sample in the block.  It does this by building an inverse variogram matrix — square with dimension (n+1) — and performing one matrix-vector multiply for each terrain sample, which is pretty fast.
• For each sample, the Kriging routine gives us the set of weights we would use to blend each control point if the control points did not have compact support.  To provide compact support, just compute an additional factor that is (distance – r1) / (r0 – r1) clamped to [0, 1], multiply all the weights by these factors, and then re-normalize the weights (ensure they all add to 1).

This almost works, but not quite; we get discontinuities between terrain blocks (which should not happen if everything is correct, since two vertices at the same XY position should always get the same Z value). At first I thought this was a programming error, but after looking more closely at the situation I convinced myself that the reason is mathematical.  My assumption had been that a control point with a weight of 0 will have the same effect as a control point that never enters into the calculation, but this seems not to be true.

The step that I added, multiplying the compact-support factors against the weights provided by the matrix-vector multiply, is — by the distributive property — the same as multiplying each row of the matrix by the support factor before doing the matrix-vector multiply.  If a support factor is 0, then this makes the matrix rank-deficient, i.e. it could not have been the result of an inversion, which means that this step is not compatible with the mathematical technique being applied.  The idea of a 0 blend factor just isn’t valid.  (This also brings into question whether the idea of multiplying by the support factors is valid at all, but for now I will just observe that it produces very useful and convenient behavior.  However, there are some small stepping artifacts that I see in some locations.  I think these may be due to having too-low a density of control points in the world (some terrain samples having 0 control points inside r1) but there’s a possibility that they aren’t, and have something to do with the weighting procedure itself.  I haven’t investigated yet.)

Now, as I type this, I am not 100% convinced that it is the right reasoning, and that something more like a typical programming error might be the problem.  My math is pretty rusty these days.  However, my updated version of the routine does not have discontinuities.  

Unfortunately, the fix for discontinuities has made the Kriging a bit slower.  What I do is, instead of building just one inverse variogram for the entire terrain block, I build a new variogram for every vertex, and include in that variogram only the control points that have nonzero support factors.  Thus the dimensions of the matrix will change from sample to sample, and I am inverting a new matrix for each output sample.

Unoptimized, this version of the algorithm takes between 5 and 25 seconds to recompute the terrain for the entire world, depending on how large r1 is.  This is fine for now, especially since editing operations only hit about 1/50 of the world or less at any given time.  However, it’ll get slower as more control points are added to the world.

Fortunately, this first version of the discontinuity-fixing was intended to be slow — I programmed it in the most straightforward way possible, to maximize the likelihood that it would work.  It is easy to think of ways to make it faster by caching the matrices, but it’s unclear which of these would be fastest.  For example, if you just cache one copy of the matrix and invalidate it any time a new control point comes into or out of range, then you might easily find yourself in a situation where you oscillate between recomputing two different matrices as you work your way along the sample grid.  This is a little reminiscent of the kinds of problems that 3D hardware has, which store images in a non-linear way so that they can be cache-efficient when sampled along lines in arbitrary directions… but it’s not clear to me how far to take that analogy or whether any applicable wisdom can be derived from it.

So I intend to optimize it, or come up with a faster solution to the discontinuity problem, but it’s not clear yet what form that will take.

Keep in mind that this is all a rough draft for gameplay purposes, and none of this is supposed to look remotely like final game visuals.

Despite not looking fancy yet, there’s already more than 5 hours of gameplay.  So that’s pretty good.

(Click image for full size.)

This time I’ll show how to reduce the memory usage by 25% on machines that support non-power-of-two textures; or, on machines that don’t, how to fit 5 shadow maps in the space previously used for 4.

Valient’s shadow system generates very stable shadow maps, but this costs a lot of texture memory.  Recall that so much memory is needed because you are inscribing your frustum slice inside a circle, and then inscribing that circle in the texture map:

When implementing cascading shadow maps, you will be using more than one frustum slice: say, four or five.  Valient’s ShaderX 6 paper suggests a way to sample from four different shadow slices quickly in the shader by packing them into an atlas, perhaps like this:

This was the way we implemented it at first, but very soon after that I was desiring a little more versatility.  If your graphics hardware will do non-power-of-two textures, then you may wish to have the number of shadow slices be an adjustable property; but if the texture maps are packed into a square like that, it’s hard to know where to put a fifth one.  So we changed the atlas layout to this:

This still works on power-of-two hardware (power-of-two textures don’t have to be square!), and on more-versatile hardware, we can now easily add new textures onto the end.

When your atlas is laid out in a line like this, and you add some runtime visualization to your game, it becomes very clear how much texture space is going unused.  Here’s a shot from The Witness’s shadow maps:

The frustum slices are shown in green.  Obviously there is a lot of empty space between them.  (For the purposes of visualization, we have left the pixels in the “empty space” filled with shadow map data, but anything that is not covered by green will never be visible in-game, so the game will run faster if we cull all that stuff!)

Because there’s so much empty space, we could move our shadow maps closer together, and use less memory.  But we need to be careful about it, because the whole point of the algorithm is that we need enough shadow map space to handle the worst case.  Indeed, if you turn the camera a bit, you get this:

Now there is very little space between the maps, so you can’t squeeze them together.  Instead, all the space is toward the bottom of the atlas, and it is unclear how to use it effectively.

But there’s a trick we can apply.  Even though these shadow maps are all packed into one atlas, they are still indexed as separate units in the shader, which means we can transform them as separate units.  So why don’t we just rotate each individual shadow map by 90 degrees?  Here’s what happens to the image above when you do that:

Now there is plenty of horizontal space and we can pack the maps all together!  (Of course we don’t need to render our shadow maps at the default orientation and then copy-and-rotate them in a post-pass; we can just rotate the up-vector of the camera used to render the shadow maps, so that we get the rotation for free.)

When we rotate the shadow maps like this, in order to render properly, our shader needs to realize that they are rotated; but Valient’s system already provided a way to transform the shadow map coordinates based on map index, so rotating the maps fits directly into that scheme.  Furthermore, if we are using any filter offsets to index into our shadow map, we need to ensure that those offsets get rotated (by either rotating the constants before uploading them to the shader, or by adding them before doing the map-to-atlas transform, depending on how your system is implemented).

So how do we figure out how to pack the frustum slices together?  Our implementation slides them to the left as far as we can make them go.  First, we compute bounding rectangles for the frustum slices (bounding rectangles shown in yellow):

These rectangles are all oriented in the same direction, so we can just slide them to the left until they nearly touch:

We figure out the rectangle orientation by performing a brute-force uv-bounding computation on one of the frustum slices, then using that same orientation for all slices.  By “brute-force uv-bounding computation” I mean that we just try a whole bunch of different angles and see which one fits the tightest.  In the current implementation we try 100 different orientations spread over 90 degrees, so we find the best angle to within less than 1 degree of accuracy.  (You only need to try 90 degrees, because at that point every angle has been covered by at least one of the sides of your rectangle).

The initial instinct was to use Shadow Map 0 to compute the rectangle orientation, but this didn’t quite work out; because of the extreme pointiness of the first frustum slice, we sometimes end up with bounding rectangles that do not suit the other maps.  Using any of the other shadow maps solves this problem (because their near plane tends to create a coherent bounding edge).

We’re not done moving the shadow maps around.  Besides just shifting the later shadow maps leftward, as above, we save some more space by shifting the first shadow map leftward based on the leftmost vertex in its frustum slice.  (We don’t do it based on the yellow rectangle, because that rectangle will almost always be poking outside of the atlas already.  We don’t need to make sure the whole yellow rectangle is inside the atlas; just the green frustum slice!  Remember that the rectangles are just a tool to help us know how to pack.)  So then we get this:

And we can shave off even more space by shifting the rightmost map upward or downward, whichever direction will allow it to slide further to the left (in this case, it’s downward:)

Clearly we’ve saved a lot of space — about half for this viewing angle. But we have to allocate enough texture space for the worst case, and the question is, what is that worst case? Empirically, for our game’s FOV, we find that in this worst-case viewing angle we can chop off 25% of the texture map.

If you’re on non-power-of-two texture hardware, you can just cut your map down and you are happy.  If you are power-of-two-only, you can’t do that, but you could use five frustum slices in the space that previously held only four.

Dealing with Overlapping

You can pack these rectangular areas together however you want, as long as they don’t overlap — at scene rendering time, your shader doesn’t know or care how close these regions are to each other.  Actually building the shadow maps in the first place has become a bit trickier, though.  When each shadow map was in its own self-contained square region, we would just set up a viewport for that square, erase the contents, and render into it.  But now, suppose we are rendering the shadow maps from left to right: while we are rendering the second shadow map, its viewport is going to inevitably overlap the first shadow map.  We have to be careful not to write into the valid region of that first shadow map, or else we’ll mess up the scene.

In our current implementation, we use DirectX9’s API-provided clipping planes for this purpose.  (The long sides of the yellow rectangles tell us exactly where to put our clipping planes. )  Clipping planes are deprecated in future versions of the API, so we would either switch to stencil testing or else do the clipping ourselves in the shaders.

Here’s what the neighborhood of the worst case looks like:

It happens when you are looking sort-of in the direction of the light vector, but you are turned enough to the side that the view frustum has rotated to be diagonal relative to the axes of the texture map space.  (If you are pointing directly along the light vector, your view frustum extrema are likely to be parallel to the axes of the texture map space.)

Deeper Thinking We Have Not Yet Done

We’ve saved this texture memory by doing what are essentially image-space operations.  But it seems to me that one could somehow project these operations back to the 3D space that we use to compute the bounding spheres in the first place, and generate smaller spheres.  The operation of rotating our texture maps means that we are folding our output space over on itself, using only half the possible orientations.  The whole point of the bounding sphere is to permit the use of any orientation at all — which we clearly, in retrospect, do not need.  So it’s probably possible to reformulate this algorithm in terms of a bounding hemisphere of some kind (or some shape that is somewhat near a hemisphere but allows frustum corner protrusions to poke out of it).

Saving Tremendously More Memory, if you are willing to copy your maps or else render them in multiple pieces…

The reason our system works is that once the shadow maps are packed into an atlas, the shader doesn’t know or care where the boundaries of the shadow maps are.  We can address the atlas at will, because in reality it is just one continuous texture map.  This means that we can go even further, and place some of our shadow maps in the atlas in such a way that they cross the boundaries of the atlas and wrap to the other side.  It looks discontinuous, but the shader being run at scene-render time does not care, if the texture is addressed in a wrapping mode.  Here is a messy mock-up (not the output from an actual running version, because we haven’t implemented this):

Unwrapped, easy-to-see version of texture space:

Wrapped vertically:

Wrapped horizontally:

In my done-by-hand mockup, the result is 46% the size required by the default packing in Valient’s original algorithm.  That’s a lot of memory savings.

The catch is that, while it’s easy to employ this mapping without additional expense, it’s more expensive to generate.  You have to either render a non-wrapped version of each shadow map and then copy it into its multiple destination pieces, or else you have to render each map in multiple passes.  (It’s always possible to arrange your maps so that one of them is unsplit, so for 4 frustum slices, you probably need 3 additional passes.  Each pass has fewer objects, though, so maybe it’s not too bad.)

If you are using pre-filtered shadow maps, then the filtering step is just a kind of copy anyway, so you would be able to do this packing essentially for free.  We aren’t doing any pre-filtering on The Witness, but if we do, it is likely we will switch over to this packing scheme.  The memory savings are so huge, how could we not?

But I’d like to reiterate for clarity that at this time we have not implemented this wrapping-shadow-map scheme, so if there are any hidden gotchas, I don’t know.  We have only implemented the above 25% savings scheme (sliding the maps around, no wrapping).

We don’t yet smoothly interpolate between the maps in the shader; we just switch the maps outright.  Interpolation is coming soon.  But in screenshots you can’t see changing conditions anyway, so it’s time for some screenshots.

First is the house with the door closed, then with the door open.  After that comes the sculpture room, with two light sources toggled in various ways (see the captions on each picture). For now you’ll have to forgive the light leaking in the corners and the shadow speckles on the walls; they are due to issues with the dynamic shadow system (which is not really related to what is being shown here) and those issues have yet to be resolved!

I have developed some interesting technology to compute automatic paramaterizations, to formulate the lighting computations in a way that can be easily mapped to the GPU, and to speed them up performing them at a lower frequency by using irradiance caching. None of these things are very cutting edge, but I run into some interesting problems that are usually overlooked in the literature and came up with some creative solutions that I think would be interesting to share. However, in retrospect, I think I also made some mistakes, but I hope that being honest about them will help me avoid them in the future.

In this first post I will describe the lightmap parameterization algorithm that I have implemented and in the next few posts I’ll cover other details of our lighting system such as our approach to perform final gathering using hemicubes and our implementation of irradiance caching.

In order to use precomputed lighting we need a way of mapping these lighting computations to the surfaces. One possibility is to store them per vertex, but in many cases that does not provide enough resolution and the interpolation of the lighting makes the triangulation of the mesh fairly obvious. Many games get away with that by compensating the lack of detail in the lighting with high texture and normal map detail, but that does not go along well with the graphical style that Jon wants to achieve. So, instead of that we decided to create full parameterizations of our objects in order to store the precomputed lighting into lightmap textures.

Creating these parameterizations by hand is possible, but it is time consuming and I’d rather have our artists work on something more enjoyable. So, we decided to create the parameterizations automatically. However, the greatest mistake I’ve made so far is to not look more carefully at the available solutions to accomplish that. I had some pieces of the implementation already available, and I overestimated how much effort it would take to put them together and produce robust results. While talking about this to some friends at GDC one of them asked why I wasn’t using Microsoft’s UVAtlas tool, and to my dismay and embarrassment my only answer was that it had not occurred to me. I think that goes to prove how valuable it is to be open about our development in a small team like ours.

Now that I got that out of the way, let’s talk about the tech. We only use lightmaps to represent indirect illumination and the direct illumination of static area lights. So, our expectation was that lightmaps would be fairly smooth and that seams would not be a huge problem. For this reason we decided not to invest in a solution that guaranteed seamless parameterizations and instead used a fairly traditional approach: We first divide the input geometry into charts with disk topology, parameterize them individually, and finally pack them into a rectangular texture.

Segmentation

Dividing the mesh into charts is by far the most complex step of the process. In the past I had tried using hierarchical clustering without much success, so this time around I decided to use an iterative clustering algorithm similar to Lloyd’s algorithm, in the same vein as the algorithm used in the Multi-chart geometry images (MCGI) paper.

Like Lloyd’s clustering algorithm, the MCGI algorithm iterates between chart growing and reseeding stages. The growth of the charts is guided by a metric based on the normal deviation and the distance between the face centroids. After each chart growing iteration a new seed is selected taking the most central face of the chart, and the process is repeated until the seed location does not change anymore.

My implementation of the MCGI algorithm worked moderately well, but it didn’t always produce good results. It was possible to tweak the number and location of the seeds to obtain the desired output, but that required a certain amount of user intervention that was not desired.

Part of the problem is that the meaning of “good” in this setting is very subjective. It usually means nicely shaped charts, that fit well to the surface, produce parameterizations with little distortion, have fairly straight and convex boundaries and are more or less equaly sized.

In order to adapt the algorithm to our purposes I did two things, modified the bootstraping method so that the initial number of seeds is chosen automatically and used a combination of metrics to obtain better control over the results.

In order to select the initial number of seeds, I simply insert the seeds one by one, and grow the respective charts until a threshold is met. At that point I pick an arbitrary face that is not assigned to any chart yet and repeat the process. When no faces are left, the growing process is restarted from all seeds in parallel.

A common strategy to remove the sensitivity to the initial conditions is to use the farthest point heuristic. However, instead of doing that I found that an approach that works well is to pick the worst candidate face of the already chosen charts as the next seed.

The second important change to the algorithm was to use a different set of metrics. The MCGI paper proposes a metric that combines normal deviation with distance between face centroids. I found that using absolute distances made the algorithm very dependent on the tessellation of the mesh and that measuring the distances from the centroids favored triangles with low aspect ratios.

Instead of using distance between faces I considered only the normal deviation and combined it with other metrics similar to the ones proposed in D-Charts: Quasi-Developable Mesh Segmentation and that take roundness and straightness into account.

These metrics also had their own problems and I had to tweak them in various ways. The most significant issue is that they constrained the chart growth in undesired ways. For example, to encourage chart convexity you would associate a high factor to the corresponding metric, but that would result in a large number of almost convex charts, as soon as a convex configuration was found no additional faces could be added to the chart. So, instead of using these metrics to constrain the growth I only use them to favor convex charts or straight boundaries; that allowed the charts to grow freely, but still retain the most convex and most straight shape possible.

A trick that helped in many cases was to incorporate some input from the artist, but without imposing any additional burden to them. A simple way of doing that is taking into account the existing parameterization of the mesh. Our objects already have a parameterization that is used for texturing and the artists tend to place texture seams at locations that are not easily visible. Snapping the boundaries of our charts to the existing seams did not only reduce the overall number of seams, but also caused the charts to evolve in a way that matches better what the artist would have done manually.

I considered texture and normal seams independently. Since our parameterization is used for lighting I follow normal seams more strictly and proportionally to their angle, not doing so would cause the corners to appear less defined or more blurry. That also helps the process to converge much more quickly in architectural meshes that have many hard edges.

Finally, I don’t impose any chart topology constrains. I specially wanted charts go grow around holes in the mesh as long as the metric was below the desired threshold. I was tempted to use a better proxy fitting metric instead of the normal deviation metric, but that would have generated cylindrical or conical charts that would have to be cut, and I did not want to deal with that. Closing holes on the other side is fairly easy, it’s just matter of detecting the boundaries and closing all, but the longest one.

Parameterization

For the chart parameterization algorithm we simply use Least Squares Conformal Maps since I had an implementation already available. My implementation is based on the description of the algorithm in the notes of the SIGGRAPH 2007 Mesh Parameterization course, which I found much more accessible than the one in the original paper. Particularly useful is the chapter about numerical optimization, although if I had to write a sparse matrix solver again I would probably use OpenNL, since it has now been released under a liberal BSD license.

LSCM is not the best parameterization algorithm out there. It worked pretty well in most cases, although in some rare situations it resulted in small self-overlaps. That happened in two cases:

• Zero area triangles in the input sometimes flipped in the parameterization.
• Charts with complex boundaries that self-intersect when parameterized.

The first case turned out that was caused by T-junctions in the input mesh that were detected as holes and filled with a degenerate triangle. In practice the small overlaps in the parameterization were not really an issue so instead of fixing the input we simply plan to report these problems to the artist in the exporter and have him fix the them if it turns out it’s causing artifacts.

In the second case, increasing the weight of the convexity metric used during the clustering process allowed us to prevent these errors. So, I didn’t really do anything to handle this problem, but so far it has not been an issue.

Even after that we had some problematic cases remaining. I noticed that the implementation in Blender was not having this same issues and was handling these cases more gracefully. So, I asked Brecht Van Lommel, who suggested the use of alternate matrix weights based on the ABF formulation of LSCM, and that seemed to eliminate the remaining issues.

While LSCM is very easy to implement, it’s definitely not the best parameterization method out there. If I were to implement something better I would probably look at LinABF or Fitting to Guidance Gradient Fields. However, since parameterization of the individual charts is currently the fastest step it may make sense to also look at more expensive deformation analysis methods.

Packing

Our packing algorithm is fairly simple. Like many other implementations we first sort the charts by parametric area, rotate them to align the charts with their best fit rectangle and greedily introduce them in the atlas one by one. Ideally I should test all 4 possible orientations, but currently I simply pick one of the orientations randomly.

Instead of using a tetris-like scheme to find the best location for each chart, I use a more brute force approach in which all the possible locations are considered. I achieve that using a conservative rasterizer that tags all the texels touched by a chart, plus an extra texel for padding. I progressively increase the texture extents as new charts are inserted. If the a location within the current extents is found, the chart is automatically accepted, otherwise a metric is evaluated to determine the location that least increases the extents of the atlas. Since I use a greedy algorithm, minimizing area resulted in atlases with very high aspect ratios. So, instead I minimize a metric that combines extent and perimeter and results in mostly square atlases.

Here are some examples of the results:

Once we use lightmap compression it will probably make sense to align the charts to DXT block boundaries in order to prevent bleeding artifacts.

Future Improvements

This is one of the areas where I think there’s a lot of room for improvement, but at the same time, there’s not much !/$ in spending more time improving the results. Even though it has not been tested in production, I think that our current solution works fairly well. It would be nice to have larger charts with less distortion or a lower number of seams, and I would certainly have fun working on that. However, that’s not going to make the game run significantly faster or look dramatically better. We plan to release the source code of these algorithms at some point so my hope is that the implementation will progressively get better as other people adopt it and improve it to fit their needs.

That said, if there’s one area where I think it’s worth investing, that is in the use of signal specialized parameterizations. The research papers on the subject (Signal-specialized parametrization and Signal-specialized parameterization for piecewise linear reconstruction) are probably overkill in our setting, and I’m not sure they would work very well with our low resolution meshes.

Half-Life 2 achieved that that by using artist specified sampling rates for each surface, but I think it’s worth doing that automatically using an approach like the one proposed by Bungie, which seems fairly simple and provides most of the gains the more complex approaches would give us.

My expectation is that the current implementation won’t suffer significant changes, other than small tweaks and slight adjustments to deal with problematic cases that may show up in the future. If someone has any experience with these kind of algorithms, I would love to hear about it. In particular I’d like to know if there’s anything you would have done differently, or if there’s any optimization or improvement that I may have overlooked and you think is worth considering.

First, I’ve taken shots from 3 positions inside a house, with four different lighting settings.  For all four settings, we are computing only the first lighting bounce.  The parameters are:

1. 32×32 cube maps, adaptive sampling, quality = 0.5.  Time to compute: 197 seconds.
2. 32×32 cube maps, non-adaptive sampling.  Time to compute: 648 seconds.
3. 64×64 cube maps, non-adaptive sampling.  Time to compute: 738 seconds.
4. 128×128 cube maps, non-adaptive sampling.  Time to compute: 1570 seconds.

(Click for full size).

Front Door:

32×32 adaptive

32×32

64×64

128×128

Corner:

32×32 adaptive

32×32

64×64

128×128

Side Wall:

32×32 adaptive

32×32

64×64

128×128

The hardware used to compute these timings is an Intel Core i7-860 with an ATI Radeon 5870 (most of the process is GPU-bound).

The non-adaptive sampling renders one cube map for each shadow map texel, whereas the adaptive sampling uses heuristics to place samples and then smoothes the map between them.  At higher quality settings, adaptive sampling provides more-accurate results, but there always seem to be artifacts, so for the time being we are using it as a fast preview mode.  If at some point the quality becomes shippable, then we would switch to adaptive sampling for everything.

We also have a sub-texel sampling mode that improves quality, but I didn’t play with that during this run.

This second set of images shows progressive bounces of the lighting with 64×64 cube maps, non-adaptive sampling.  (The first one is the same 64×64 image as above).  The times are: 1 bounce, 738 seconds; 2 bounces, 1438 seconds; 3 bounces, 2481 seconds.  The precompute time is basically linear in the number of bounces, as one might expect (the algorithm is basically just doing the same thing n times.)

1 bounce

2 bounces

3 bounces

]]> http://the-witness.net/news/?feed=rss2&p=196 10 http://the-witness.net/news/?p=77 http://the-witness.net/news/?p=77#comments Wed, 03 Mar 2010 18:22:04 +0000 Jonathan Blow http://the-witness.net/news/?p=77 The Witness contains a mixture of indoor and outdoor scenes, but much of the game takes place outdoors with a very long view distance (you can see the entire island at once if you have a good vantage point).  So I wanted to implement a shadow system that would work robustly, provide high visual quality, and allow the player to see everything at once.  I have some experience with shadow systems of this type, but the last one I designed was for computers and graphics cards circa 2004, so I was interested to see how much more would be possible today.

We’ve implemented such a modern shadow map system for The Witness.  In the process, we’ve made some improvements to shadow mapping algorithms beyond anything we’ve seen published, so we are going to detail the improvements here.  Also, our shadow map system is still being improved, so I’ll talk about what we have yet to try and why we think it’s a good idea.

Before we get to those details, though, I’d like to establish some context so that the motivation for these design decisions is clearly explained.

The Literature

I have a somewhat cynical attitude toward graphics research literature: most of it describes techniques that don’t generally work, but the authors of the papers do the best they can to “sell” the technique to you anyway (using cherry-picked examples, glossing over or completely ignoring failure cases that would be obvious to anyone who understands the algorithm, etc).  As the reader, eventually you come to understand all the problems, but not after investing a lot of your time and energy (possibly months) implementing and understanding an algorithm that behaves so poorly that you never would have bothered if you had known the truth from the outset.

I’ve had this experience many times, with many different techniques.  Shadow maps, though, have been one of the big ones.  There are many published shadow map techniques that simply don’t work well enough to be taken seriously.  And often when I’ve heard someone say “so-and-so shadow technique is good,” it usually turns out they haven’t tried it themselves, so it’s just hearsay, or else that person has low quality standards.

So I’d like to put forth the statement that I have high quality standards and will only endorse things that have been found to robustly function; I will be open and honest about the degree to which things don’t work, and what the specific problems are.  In an ideal world this would not be necessary to say, but the situation in the literature today makes it otherwise.

Quality Goals; Previous System

Many shadow map schemes have been developed that try to maximize the effective resolution of shadows in the scene by performing transformations that are heavily view-dependent.  An extreme example of this is Perspective Shadow Maps.  I have learned through experience not to use these techniques.  They cause shadows to swim and flicker in annoying ways, and many of the algorithms break down severely as the player approaches certain viewing angles.

For the 2004 system, I took as a core design goal that shadows should appear rock-solid on nonmoving objects, regardless of any viewpoint motion.  The clearest way to achieve this was to center the shadow map on the viewpoint at all times, never letting the shadow map scale or rotate.  Because a single shadow map cannot cover the world at high resolution within memory and fill constraints, I used a scheme where 4 or more shadow maps of increasing worldspace size were centered on the viewpoint like square doughnuts.  In order to prevent crawling or shimmering, one just ensures that shadow map worldspace positions are snapped to integer multiples of their texel size.  (A family of related techniques, but which don’t necessarily center the maps on the viewpoint, soon came into more-common use and took on the moniker Cascaded Shadow Maps.)

On fixed-function pipeline hardware, this scheme was never quite satisfying (I had to use clip planes to render the scene in many slices, and there were small 1-pixel artifacts due to the resulting imprecision; rendering all the slices was a bit slow).  Modern hardware is able to do this kind of thing much  better.  Also, this scheme wastes a large amount of shadow map memory, because with all the shadow maps centered on the viewpoint, most of the map texels are going to be out of view at any given time.

Despite the drawbacks, the visual stability of this technique, and its ability to reach across the entire game world, were extremely appealing to me.  Having seen how nicely shadow mapping could behave in practice, this visual stability became a very-high-priority goal in my mind for any future shadow systems.

So, going into this new system, the goals were (listed in approximate order of importance):

1. High performance
2. Complete stability under camera motion
3. Long view distance
4. Visuals can be controlled to suit the style of the game
5. Efficient use of texture memory

The New System

I started working on the new system by looking at the 2004 system and trying to make it more memory-efficient.  Most likely this would involve moving the shadow maps around in world space, but it wasn’t initially clear to me how to do this without introducing problems.  Ignacio pointed me at Michal Valient’s article “Stable Rendering of Cascaded Shadow Maps” in ShaderX 6, which was exactly what I wanted.  Valient computes bounding spheres around the slices of the view frustum that tell him how much he can move the shadow maps in world space without introducing gaps.

To illustrate, here are a couple of figures reproduced from his article.  I don’t want to unduly step on anyone’s copyright, so if you are interested in cutting-edge shadow map techniques, buy ShaderX 6!  (Click for full size.)

So basically, you take the a frustum slice in worldspace, ensure that it is completely enclosed in a sphere, and then ensure that the sphere is completely enclosed in a square cylinder; the square is your shadow map.

You can render multiple frustum slices for multiple shadow maps, so long as the bounding spheres overlap enough to cover the whole frustum when put together (see 4.1.2 c and d).

The reason they are spheres is: because the shadow map is never allowed to change size (we voluntarily imposed that constraint in order to get solid shadows!), then we need to find a shape that conservatively encloses any possible orientation that a frustum slice could occupy as the camera rotates in space.  That’s a sphere.  Then we make sure that our shadow map covers that entire sphere, and we have then guaranteed that every point in the view frustum is covered by a valid shadow map  texel.

On top of this, Valient suggests the very helpful optimization of packing all your shadow maps into one atlas texture, so that when it’s time to render the scene, you can draw all your shadowed objects in one pass without having to sample multiple textures; you just figure out which frustum slice each pixel lands in, then use that information to determine the offset into the atlas, add that offset to your texture coordinates, and sample the texture.  This works great.  Valient suggests a 2×2 arrangement of textures, as this is convenient on a wide variety of hardware, for example, GPUs that only support power-of-two textures.  So if a single shadow map would be 1024×1024, then you can create a 2048×2048 texture map that contains 4 shadow maps packed in a 2×2 array:

So my first shot at a new system was basically a reimplementation of everything Valient describes.  It didn’t take too long, and when it was done, I was very happy with it — it was clearly much better than the 2004 system.

But…

Memory Usage

This technique is still a memory hog.  The image stability constraints, which result in us wrapping the frustum slice in a sphere and then the sphere in a box, add margins of unused and barely-used texture space at each step.  Looking at Figure 4.1.2, you can see that a frustum slice only occupies about 50% or 60% of the area of the square that represents your shadow texture.  This implies that half the square is wasted.  However, the actual situation is worse than this, because the diagram is misleading.

The problem is that the view frustum represented in the diagram is much narrower than the view frustum used in an actual game, and if you re-draw the diagram in realistic proportions, it looks very different.  For an accurate 2D diagram, you are finding a circle that encloses the widest part of your view frustum, which is the 2D trapezoid you get by cutting your frustum in half diagonally (Valient discusses this in his paper as well).  Suppose your game is rendering at a 16:9 aspect ratio, and your field of view is 90 degrees horizontally (this is what we use for The Witness currently.)  The vertical field of view is then going to be about 59 degrees, and the diagonal field of view will be about 98 degrees (click on image below for explanation).

The frustum slice in Valient’s diagram is only about 30 degrees, a huge difference!  So if we have a 98 degree frustum slice, and inscribe that in a circle, and inscribe that circle in a square, what does that look like?  Something like this:

Recall that the square is your shadow map texture and the innermost trapezoid is your frustum slice (the texels of your texture that may potentially be used).  It covers only a small  area of that square — and there’s no way to make it bigger!  The reason is that for wide frusta like this, the diagonal at the far plane is so long that it dominates the bounding sphere computation, and so the center of the circle has to land on that diagonal so that its diameter can be just barely large enough to enclose it.  (In The Witness, our frustum slices are not proportional, and the way we divided them up, this isn’t exactly true for the first 2 shadow maps — but it is very close to true).  The fact that the circle is centered on the far plane means that automatically half the map is wasted at this orientation — but the wide angle ensures that much of the other half is wasted too!

You can rotate the view frustum to other orientations and make it look like you are covering more of the shadow map… for example, if you orient the frustum so that the view vector is going straight down into the page, then the frustum’s projection onto the paper will be a rectangle, and it will appear to cover much more of the square.  But then you have to keep in mind that some of this coverage is worth a lot more than other coverage in terms of impact on the scene: think about how much space is covered by the texels toward the middle of the frustum projection, versus how much is covered toward the edges (almost none!)

If I add two more frustum slices, so that the total is 3 slices as in 4.1.2, it looks like this:

That innermost shadow map is just a tiny smudge (now you know why Valient chose a narrow field of view — for clarity of his figures!)  But notice what else is going on: each shadow map is fully contained within the next-larger shadow map, as with the concentric-square-doughnut system from 2004!  Valient’s scheme is better since it gives you more view distance (the squares are not concentric) — but it can’t give you nearly as much view distance as it would like, due to the wide angle of the frustum.

For Next Time

So, whereas on one level I was very happy with this shadow system’s performance and visual quality, it still seemed somewhat wasteful in terms of memory usage.   Next time I’ll talk about how we addressed that problem.  Subsequent postings after that will talk about issues like softening the shadow border, blending between slices, and various other implementation tricks.

To be continued.

Today we are announcing a fund that provides very good terms for talented indie developers working on high-quality games.  Our terms are much friendlier than what publishers offer.  Our goal is to help indies become stronger while retaining their independence.

The past couple of years have been good for independent game developers.  Through download services like Xbox Live Arcade, the PlayStation Network, WiiWare, and Steam, independent developers have found a very large audience.  Some of us have been lucky enough to develop hit indie games that were very financially successful.

Braid was one of those games.  The success of Braid has allowed me to undertake more-ambitious projects like The Witness.  At the same time, I felt that I wanted to do something with the profits that would help other indies with their own games.  More recently, while talking to publishers about The Witness, I felt that the business climate around publishing and funding these smaller games had not caught up with reality: it’s a model where the standard terms are tuned for budgets in the tens of millions of dollars.  Because publishers want to stick to this model even for low-budget games, it was very hard for indie developers to get a fair deal.

It turns out that other successful indies felt the same way, so we have pooled our resources and launched this fund.  We will be announcing further details soon.  At the GDC, Ron Carmel will be giving a talk about the problems that exist in the current publishing model for indie-budget games.

We’ve had the timing of this announcement planned for a while, but it seems like some kind of strange synchronicity that we’re revealing our existence just as all this trouble is happening at Infinity Ward.  When you’re a mainstream developer, and you’ve made one of the most successful and profitable games of all time, and then just a few months later your publisher and parent company is willing to so bald-facedly mutilate your company, well, what conclusions can be drawn from that?  If publishers of that size are so megalomaniacal as to be incapable of seeing the importance of a developer’s talent — instead believing that the game’s success is somehow due primarily to their brilliant marketing strategy or their CEO’s charming personality — then how will this ever change?

If Infinity Ward can’t be treated with respect, then who can?

Independent developers can.  That’s one answer, at least.  Indie Fund is here to help make that independent existence a reality for as many talented developers as we can.

Here’s a link to the main Indie Fund site, with an email you can use to contact us.

At the moment of writing this post, The Witness has no Twitter followers and no Facebook fans, so you could be the first!

For The Witness, I wanted to develop a graphical style that values simplicity.   It would be suited to mellower environments, with both indoor and outdoor settings.  Some kind of global illumination solution seemed like the right idea here.  (Global illumination is when you simulate light bouncing around in a scene; the resulting look is usually much richer and subtler than the direct lighting that games usually do.)

Clearly, full real-time global illumination would be the most versatile solution.  I investigated some licensable packages that provide this, such as Geomerics’ SDK.  However, these solutions will invariably use a lot of texture space, and consume a bunch of processing time, and they seem like overkill for this game (The Witness does not have many moving light sources, relative to other types of games).

So, some form of precomputed global illumination seemed like the right thing.  3D modeling packages have plugins to compute global illumination, but they are very difficult to interface with, and they could not even come close to handling a full game scene.   The only thing that knows where all the objects in the world are at once is the game itself (and the in-game editor), so it seemed appropriate to develop our own in-game system for global illumination.  It could have been radiosity, could have been something like Monte Carlo Path Tracing, but Charles Bloom suggested the very simple solution of just rendering the scene for every pixel in a lightmap, and that seemed like a good idea.  With an approach like that, you don’t have to do a bunch of monkeying around to make radiosity or ray tracing match the completely different algorithm that is used to render your realtime game scene; light transport is computed by that same algorithm, so it will automatically match unless you mess things up.

For several months, Ignacio Castaño has been working on this system.  He is writing up a highly technical explanation of how the system works, which I think he’ll be done with in a few days, but in the meantime, here is a lighter-weight overview.

At preprocess time, we just walk a camera over every surface, pointing the camera away from the surface and rendering the game scene into a hemicube in video memory.  The render target textures of a hemicube are packed together into an atlas, and when the atlas fills up, we download it into system memory, integrate the values in each hemicube to find an average light value, and then store that value in the lightmap.  Most of the shots below were generated using 128×128 cube maps and multiple samples per texel.

Because we are just using our regular rendering code, this precomputation process is hardware-accelerated by default.

Note: In the images below, all geometry and textures are placeholders. As with Braid, we are using rough-draft versions of all these things while the core gameplay is built.  Bloggers, these are not to be considered screenshots of the game.  They aren’t supposed to look good yet — they are just supposed to show the precomputed lighting.

First, some shots of the house.  The precomputed lighting is responsible for most of the light in the room.  The places where you see sunlight hitting surfaces directly are dynamic; everything else is a static precompute.  (Without the precomputed lighting, the entire room would be black except for the patches of sunlight).

Note the ambient occlusion, soft shadows, and other nice effects that all come naturally from this system. (In the third image, the picture on the wall hasn’t been lightmapped yet, which is why it sticks out so brightly.)

Here’s a simple bunker interior consisting mostly of a single material and color.

Lastly, the tower:

There are lots of caveats on these images.  The game renders in HDR, but we haven’t balanced our lighting constants or done tone mapping yet, so I have gamma-corrected the output images by various amounts.  For now, we are computing only the first lighting bounce.  We’ll probably do at least 2 or 3 bounces for the final game, and when we have that running I’ll post some comparison images.  I believe our model of sky illumination is still overly simple and wrong (though I’d need to check with Ignacio on that, maybe he has fixed it up).  I haven’t played around with the results of the current system in outdoor areas (e.g. lots of small branches and leaves), though if we find that we have too many aliasing problems, we can always make the lightmaps higher-resolution in those areas.

In areas that have doors or windows that open and close, we are planning on layering a supplemental lightmap that gets scaled by the openness of that light aperture, then added to the base lightmap.  This will provide a pretty good approximation for the way the indirect light in the room changes as the aperture opens and closes.  Direct light will be completely correct since it uses the fully dynamic shadow system.  I’ll do a post about that shadow system sometime in the future.

Click for full-sized versions.  The gallery seems to hang some versions of Google Chrome.  Sorry about that.  It works fine in Firefox and Internet Explorer.

These concepts (and many more) were all done by Eric Urquhart, who has been working on the game for some months now.

Many people have been asking for more details about the game, so I thought it might be nice to kick things off with some concept art… in the next post.

Welcome, and thanks for your time and attention!

-Jonathan.