Jump to content
  • Advertisement
Sign in to follow this  
  • entries
  • comments
  • views

More Morphing, Shadows & Packing

Sign in to follow this  


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

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

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.

ambient occlusion

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.

ambient occlusion

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

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.

shadow atlas

Next time I'll talk about per-caster shadow maps.
Sign in to follow this  


Recommended Comments

Wow...amazing work, the ambient occlusion iamge looks fantastic.

You really know your stuff. I was fiddling around with lightmaps a month or so ago...my solution was a little less elegant than yours. I basicly purchased a program that generates lightmaps for an arbitrary mesh, and outputs them very nicely, so all I've got to do is setup my rendering pipline to use the new lightmaps :-p It did a good job of packing them in there, and it was very easy to add multiple lights, colored lights, etc. as well as adjust the values of each light, the program has a decent interface too plus it supports radiosity, and all kinds of other stuff, it's called "Light map Maker" it was only like 30 bucks.

Still that's not nearly as fun as it would have been to do what you're doing.

Also, those are pretty nice framerates you're pushing, what are the specs on the box you develop on?

My card doesn't even support hardware shadow mapping (Radeon 9200) I should upgrade soon ;-)

Anyways you're doing an great job, I look forward to your next entry.

- Dan

Share this comment

Link to comment
Thanks for the feedback.

Yeah, you were smart to purchase, rather than write your own. I did learn a lot in the process, though.

The framerates you see aren't necessarily indicative of the game. Some are in a simple level, others are in debug mode.

The actualy game gets ~150 fps with a two per-pixel shadowed lights and several creatures on screen, at 800x600 rez, in release mode, on a 2ghz amd, with 6800gt & 2gb ram.

The goal is ~30 fps on a ~1 ghz with gf3. We'll see....

I just checked out lightmap maker, and it's free. That's pretty cool.

Share this comment

Link to comment
Damn, light map maker wasn't free when I bought it a few months ago. Oh well it's a good piece of software and I'm sure I'll make lots of use of it, they deserve it.

How much RAM will your target system have?

How would your engine ideally distribute the CPU cycles between physics(if any?) AI, setting up rendering, etc? Or is there any point in even trying to acheive a optimal % between these things? I havn't ever really concerned myself with things like this, I'm curious to see if you plan that kind of thing.

Also, will a GF3 support all of the cool effects you're making? Or will you have somewhat simpler versions of the lighting, etc. for lower end cards? (I'm not sure about the capabilities of nvidia hardware, I've always had ATIs for years)

Sorry for all the quesions, your project/engine looks very interesting to me.

- Dan

Share this comment

Link to comment
No problem with the questions.

I haven't done a detailed analysis on the amount of ram required, but the only thing that may take a lot is the fact that I am using 64-byte vertices.

I can compact this to 40 bytes pretty easily, but I'm worried that most tools won't like working with .x files with a vertex decl, and not an FVF code. For instance, I have been meaning to compact my normal & tangent into a d3dcolor, and derive the binormal in the vertex shader. That would free up some memory for sure, at no cost in visual quality.

But, overall I don't think memory will be an issue, unless I decide to port it to xbox! ;)

CPU wise, I'm pretty good so far. I've been using AMD codeAnalyst ( free profiler ), and the most expensive method of mine, at 2% of the cpu or less, is my raycast through the AABB tree. I use this to do dynamic lighting of particles and objects.

Yes, all of my effects work on the GF3. There are definitely things that could be done on newer hw, but I don't require them for this game. Also, some effects require more cleverness on gf3, then a gf6 or r300+ card.

Share this comment

Link to comment
Wow, your conversation makes my head hurt[grin]. That looks really awesome though, I'm looking forward to your explanation on how the water looks so damn good.

Share this comment

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!