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).
EDIT: to answer comment about dynamic updating problem:
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)
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] ||
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:
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;
// 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
// go to a finer level tile.
// do the math to step once.
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.