# 2D Real-Time shadows on level on a level made from a Dynamic Bitmap

The Bitmap has transparency, and only non-transparent pixels are solid and used for hit detection for the physics engine and gameplay.

I have seen some versions done with convex hulls, but for multiple reasons I am not using convex hulls to build the levels in my game.

How can I implement 2d shadows on a level made out of a Dynamic Bitmap?

The answer jpaver posted is good, but I am sure there are some other ways to do this. Does anyone else have any more information on this question?

This is only one way to approach the problem.

For each source pixel in your bitmap, ray march towards the pixel that currently represents the light source. If you hit a non-transparent pixel along the way, stop marching and assign a shadow value to your source pixel. If you reach the light pixel, the source pixel is lit.

As you can probably tell, marching and testing every pixel along the way for every source pixel can get expensive, especially when adding multiple lights. Fortunately, there are things that can be done:

• assign a bounding circle to your light. Before marching, test if the pixel is inside or outside of this circle radius. If it's outside, it's considered in shadow by default and there is no need to march. If it's inside, do the ray march. If the ray march yields that the pixel is lit, use a falloff function to determine how bright it is. (side note: interesting falloff functions can be derived to make your lights flicker and animate)

• To avoid marching and testing every pixel, pre-compute a distance field for your static bitmap. The distance field simply stores the distance to the closest opaque pixel for every pixel. Then when marching along a ray, you look at the distance field, and are guaranteed to hit no opaque pixels by stepping that amount. (side note: you can use these distance fields for your physics too).

If you have a dynamic bitmap field, updating the distance field is a bit of a pain. I'm sure there are clever techniques for doing this out there, I'm just not versed in them. Someone else is free to comment here if they are in the know! :)

An alternative technique to accelerate your ray marching is to use an tiled hierarchy that encodes your empty space in a much more efficient way. You can precompute the hierarchy from your original level bitmap, and only need to update parts of it when you add or remove opaque pixels.

So what does the hierarchy look like? If your original data of size MxN is mip0, then:

• mip1 is M/2 x N/2 (ie. half as big as mip0 in each dimension)
• mip2 is M/4 x N/4 (ie. half as big as mip1 in each dimension)
• mip3 is M/8 x N/8 (ie. half as big as mip2 in each dimension)
• etc.

The higher mips store whether there is any opaque geometry in the lower mip level pixels. If you wanted to update mip[k] at pixel(i,j), you'd probably do something like this:


mip[k].opaque[i][j] = mip[k-1].opaque[i*2][j*2] ||
mip[k-1].opaque[i*2+1][j*2] ||
mip[k-1].opaque[i*2][j*2+1] ||
mip[k-1].opaque[i*2+1][j*2+1];


Once you have the data structure computed, you can march your ray directly to the edge of a tile if that tile contains no opaque pixels. Your algorithm would look like this:

(extreme pseudo-code)



void StepOnce(int &x, int &y, int xDir, int yDir)
{
int k = COARSEST_MIP;
while (k > 0)
{
int x_in_mip = x >> k;
int y_in_mip = y >> k;
if (!mip[k].opaque[i_in_mip][j_in_mip])
{
// Here we can step (i,j) to the next tile for mip(k)
// (I'll leave the math as an exercise to the reader)
return; // exit since we've stepped once
}
else
{
// go to a finer level tile.
k--;
}
}
// do the math to step once.
return
}


Updating this structure is simply a matter of tracking a dirty region (ie. rectangle) for level 0 every frame. Once you've accumulated all changes, just update those pixels falling in the dirty region and update higher levels that touch that region too.

Note: if you're doing this on CPU, you may want to:

• rearrange the ordering of pixels in your bitmap data so that a tile of NxN all fall within the same cacheline. This will tend to improve your cache hit rate tremendously when ray tracing vertically.
• also, if you ray march your pixels in tile order rather than screen-width scanline order (one at a time, or 4 at a time using SSE), you will further improve your cache hit rate.
• This might be what I may do, although the bitmap is destroyable, and can have stuff added, I know how to update the distance variable on each pixel with destruction, but I don't know an efficient way to update the pixels for something being added to the environment. Oct 15 '10 at 18:47
• I've edited my response to handle the dynamic bitmap case (which was unfortunately not clear from the way you phrased your question originally). I'd suggest you change the wording to read: "How can I implement 2d shadows on a level made out of a dynamic Bitmap?" Oct 15 '10 at 23:09
• Updated question Oct 15 '10 at 23:10
• This is in AS3, so I really have to use the CPU. Oct 16 '10 at 0:37
• I think I may have found a way to recompute the distances really efficiently, but I do have to test it out. I think I will use a combination of the mip levels, and recalculation, as any speedup in something as intensive as this will increase the speed of the game and allow for a larger amount of lights per scene. Oct 16 '10 at 0:41

The answer to the following question has a link you might find very useful : How is 2D lighting implemented?

• I already saw that. It is not a useful resource for AS3, as some of the things he does are either impossible, or incredibly slow in AS3. That is why I asked this question. Oct 14 '10 at 15:46