Inventory & Item Grabbing

This morning I implemented entity -> item collision, so that if your character runs over an equipable item,
it removes the item from the world, puts it in the character's inventory, and notifies the item of its new
parent object. It also plays a little sound to let you know.

When I get the GUI sorted out a bit more, I will have it display the name, description, and relevant stats
for each item as it's picked up.

Yesterday I added a 'Flatten' Morph shape to the level editor, so you can bring a set of vertices down towards
their minimum, or their average, depending on the sharpness setting.

I also added ramps, but those didn't turn out very well. To do them properly would require a triangle tool, rather than a vertex tool.

Chart Packing

One of the challenges of implementing lightmaps is to efficiently pack the lightmap charts into an atlas,
so that all triangles on the same atlas can be potentially be efficiently rendered together.

If your chart packer is inefficient, then you will at times create bigger lightmaps than are truly needed for
the number of texels that you have.

There are numerous papers on extremely efficient, but reasonably complex algorithms for fitting charts in atlases,
I wanted an algorithm that was reasonable efficient, simple to code & debug, one that would never stretch or distort
a chart, and one that could be modified to run in real time as well.

The algorithm I came up with was fairly simple. Each chart's size in UV space is determined, and is used to create
a rectangle that represents each chart. Better packers actually pack texel-by-texel, but that's harder.

Now you have a bunch of rectangles that you want to attempt to pack into the bigger rectangle of the atlas. There
are no real size restrictions on the rectangles, and they could be of any aspect ratio.

I made a 2d array that corresponded to the atlas, and simply filled in a 1 where there was a rectangle placed
already, and a 0 otherwise. To place a rectangle, you pick a spot for it and check its area in the atlas to
make sure there wasn't already something there. The interesting part is wisely choosing a spot for placing the
rectangle.

In general, it's best to sort the rectangles before you pack, in size order. You can define size as perimeter,
longest side, area, or some combinations of these. In my experiments, longest side worked best, perimeter next, and
lastly area.

The first method I came up with was a best fit algoritm, which would simply go from left to right, top to bottom,
and attempt to place the rectangle in every valid slot, and would count the # of empty texels around the perimeter
for each placement. The placement with the lowest # of unoccupied perimeter texels was chosen, as that would be the
placement with the tightest packing.

Of course, this is an extremely inefficent algorithm, on the order of W * H * R * N operations, where W and H are the width
and height of the atlas, and R is the perimeter of the test rectangle, and N is the number of rectangles. This was
unusably slow.

I did a few simple optimizations, like not testing the rectangle texels in the obvious order, but doing the right & bottom
corners first in order to skip ahead, but it was still too slow to use. I suppose another optimization would be a heuristic
to abort early if I found a 'good enough' fit. In general, you can't typically do better than 1/2 of your perimeter cells
occupied.

So, I did a first fit algorithm instead. I sort the rectangles in the same way as before, and go from upper left to
lower right just like before, but I take the first valid placement, without trying them all. This was certainly fast enough
to use, and did a good job packing as well. They key is really sorting the rectangles first. That way your larger, more
awkward rects go in early, and if they leave small holes, they will fill up later with smaller rects.

To test out these algorithms, I wrote a little SDL app that drew the rects as I was testing & placing them. This was
a really fun side project, and I really dug writing in SDL - very quick to get up & running.

Next I put the first fit method in the engine when creating lightmaps, and it worked very well. I had to change a bit of
code, but not too much. It definitely packed my lightmaps better than the older method I was using that I found on
flipcode, and was plenty fast.

Here is a shot of each lightmap chart as its own color.



So, that was the last major change to my lightmap code. I didn't talk about ambient occlusion, but it's a simple thing to
add once you have a light mapper, and can add a nice bit of depth to your scenes. I look at it as sort of half of radiosity,
you get occluded areas being darker, but you don't get the color bleeding part.

Here is a shot of ambient occlusion only. It looks a bit noisy due to the small # of samples I took.



Packing Shadows

When I first got around character & object shadowing, I tried a couple of different methods. One was to find the triangles
under the character, keep the ones facing up, and drawing a blob as a projected texture. This worked OK for some things, but
clearly wouldn't work for trees or complex objects, and also was not accurate on a per-light basis.

At some point I decided I needed real per-light shadows, so I did the lightmaps, for static objects, but needed some other
method for dynamic shadows. I decided to try a simple approach and only complicated as needed.

The idea was :

for each light, render its occlusion term from the lightmap to dest alpha

for each shadow caster, render it in black to a white texture from the light's POV.

for each shadow caster, build a frustum from the caster's bounding sphere, pointing away from the light

for each chunk of world geometry that intersects the shadow frustum, render it with the shadow texture

multiply this shadow texture shadow term by the contents of dest alpha, and store in dest alpha

for each chunk of world geometry in the light, perform lighting, and blend in with dest alpha

This looked great, but was way too slow. Just a few characters killed my framerate, so I did some experiments to
determine why. It turned out that having a separate 64x64 render target for each shadow caster was killing my
framerate.

So, I needed to eliminate or reduce this issue. The solution was the shadow atlas!

The idea is that, for each light, each shadow caster is rendered into a section of a shadow atlas, and when
performing shadowing onto the terrain, you access just this sub-rect of the shadow map rather than the whole thing.
This way, you could fit 16 shadow maps in one 256x256 atlas, and avoid the expensive render target changes.

The only trick to it is using a separate masking texture to achieve sub-rect clamping, which avoids grabbing
neighboring shadows during shadow rendering.

Of course, using a 64x64 shadow map was at times overkill, and at other times not enough. This was not a huge
deal at first, b/c I was using blurred black & white shadows, so was hard to see. When I later changed to 8-bit
depth shadow maps, the lack of resolution was very obvious.

That's when I was forced to change my shadow atlas allocation strategy. I decided to choose the shadow map
resolution for each caster based on its bounding sphere size in screen space. That way each caster would
no longer be a uniform 64x64 size, and would require use of the rectangle packer.

When I added it, I discovered that it was fast for pre-processing, but way too slow for use in the game itself.
When several charcters were within range of a light, things slowed to a crawl while my algorithm searched for
the first fit on a texel-by-texel basis.

I realized that it didn't need to be an optimal fit - I'm re-rendering these things every frame anyway - I just
needed a decent fit so I could quickly either pack it, or realize I was out of space and render the shadows I had
so far the dest alpha, then clear the shadow map and start packing over again.

The solution was easy - I just told the rectangle packer to work with an atlas of size 16x16 texels, and I told it
my rectangles aligned on these boundaries ( making sure to round properly so things didn't come out zero size ).

This modification was plenty fast and plenty efficient for real-time.

Here is a shot of the shadow map atlas, using NVPerfHUD.



Next time I'll talk about per-caster shadow maps.