Drawing lots of overlapping 2D shadows

Question

I'm working on a program that involves drawing lots of very simple overlapping shadows. There's nothing fancy about the shadows: they have hard edges and there is a single light source at infinity (i.e. all shadows are parallel). The unique aspect is that the shadows represent areas of partially absorbed light, and so many many shadows can overlap to make progressively darker regions.

Here is an image to illustrate the idea:

My question is this: What would be a good way to take the shadows in my program (stored as convex quadrilaterals) and efficiently draw them to the screen?

I can simply draw them all with the appropriate alpha values and the result looks fine, but doing so can get awfully slow. I think this is because pixels that are in many shadows are drawn over many times. I suspect an approach that only draws to each pixel once could be much faster.

My program is in C++ and I'm using Qt to do the UI and drawing. I'd be happy to make use of a library to do polygon clipping or something (e.g. Clipper or boost), but I'd be reluctant to dive into the world of OpenGL/GPUs (unless there is a particularly painless way of doing so).

Any ideas? Thanks!

Answer 1

Well I think an efficcient way to draw your shadow will be to do something like ray-tracing. It means basically that you iter through every pixel in your image and draw in the right color by checking how many "wall" the reversed ray traverses. something like :

For every pixel in the image
    compute the reversed lightray (from the pixel to your light direction)
    compute the number of walls traversed by your lightray
    (= nb of intersections with all the segments/walls)
    draw the pixel according to the number of intersections 
    (the more intersections, the darker)

It should be easy and O(n) in complexity with the number of pixels ^^

By the way I think boost::geometry can manage intersections.