Need algorithm to draw overlapping rectangles

Question

I need help with efficiently drawing/culling a series of opaque rectangles, in other words, this is a stack of index cards on a desk. The specifics are:

• no rotations, so everything is simple integer coordinates, axis-aligned
• cards are fully opaque
• cards can have any integer X,Y position
• all cards are the same size
• I have a list of the cards in z-order

I think I have (essentially) two choices:

1) brute force painter's approach, where all cards within the desktop viewport are fully drawn, in reverse z-order. Pros: simple. Cons: a) requires an off-screen buffer to avoid flicker, b) potentially lots of time wasted on drawing expensive areas of each card when that area might end up being obscured, worst-case being the entire card getting covered.

2) an algorithm that generates a list of visible (or obscured) rectangles for every card, such that only visible portions are ever drawn.

Choice 2 is where I need advice, especially in terms of algorithms, and pro's and con's of a "smarter" draw cycle.

Any language/platform agnostic advice is appreciated. If it matters, this will be implemented on MS Windows.

Am open to any suggestions, including hybrid approaches. I realize a precise answer is likely very dependent on the particulars of the code, but I'd be happy even with generalized concepts at this point!

Additional notes: It will be possible to have thousands of cards stacked on top of each other, so I'm highly motivated to avoid a purely brute force painter's approach - at least without some sort of pre-processing to cull out fully obscured cards. The same goes for lots of cards that were closely tiled, worse case being only their borders showing - I would like to skip painting the complex innards in those cases, if possible.

Answer 1

What about painting only the contour line of each card from the bottom most to the top most? Then you can do a flood fill to paint inside of the contours. This way you would repaint only a few pixels corresponding to the borders where there are intersections.

Edit: Uploaded images to help me explain the idea.

The first step is mark the borders of the cards assigning their Z-order (top left image). This way, there are overwrites, but only on borders which are a little amount of pixels.

After that, you can paint the texture of the cards (lowest Z-order first) following two rules:

• You start from the border and paint the blanks until reach a border;
• If the border's Z-order is the current one, you paint it;
• If the border's Z-order found is less than the current Z-order, you continue painting as it were a blank one;
• Otherwise, you found a border with greater Z-order, so you skip that block;
• Next card.

Hope it helps :)

Answer 2

OK, here's some loose pseudo code for how I think this problem can be solved.

Begin with a z-order sorted list of the cards. Each card has a list of visible rects (explained later), that needs to start out with just one rect, set to the card's full bounding box. The loop is begun with the lowest z-order card first.

Cards.SortZOrder();
foreach Card in Cards do
  Card.ResetVisibleRects; // VisibleRects.DeleteAll; VisibleRects.Add(BoundingBox);

CurrentCard = Cards.Last;
TestCard = CurrentCard;

The idea here is that we're going to work upwards from our "current" card, and see what effect each higher card has on it. There are 3 possibilities as we test each higher card. It either completely misses, completely obscures, or partially obscures. For a complete miss, we ignore the test card, since it doesn't affect our current card. For a complete obscure, our current card gets culled. A partial overlap is where the list of visible rectangles comes in, since partial overlap can (potentially) split the lower rectangle into two. (It's easy to see how this plays out if you just grab two playing cards, or index cards. The top one causes the bottom one to either adjust one of it's sides, if they share any edge, or it causes the bottom one to split into two rects if they share no edges.)

Caveat: This is VERY unoptimized, unrolled code ... just for talking about the principles. And yes, I'm about to use "goto" ... mock me if you must.

[GetNextCard]
TestCard = Cards.NextHighest(TestCard);

[OverlapTest]
// Test the overlap of TestCard against all our VisibleRects.
// The first time through this test, CurrentCard will have only one
// rect in the VisibleRect list, but that rect may get split up later.
// OverlapTests() checks each rect in the VisibleRects list, and
// creates an Overlap record for any of the rects that do overlap,
// like: Overlap.RectIndex, Overlap.Type. It also summarizes the
// results into the .Summary field. 

Result = CurrentCard.OverlapTests(TestCard);

case Result.Summary
  none: 
    goto [GetNextCard];

  complete:
    CurrentCard.Culled = true;

    // we're now done with this CurrentCard, so we move upwards
    CurrentCard = TestCard;
    goto [GetNextCard]

  partial:
    // since there was some overlap, we need to adjust,
    // split, or delete some or all of our visible rectangles.
    // (we won't delete them all, that would have been caught above)

    foreach Overlap in Result.Overlaps
      R = CurrentCard.VisibleRects[Overlap.RectIndex];
      case Overlap.Type
        partial: CurrentCard.SplitOrAdjust(R, TestCard);
        complete: CurrentCard.Delete(R);
      end case

    // so we've either added new rects, or deleted some, but either 
    // way, we're done with this test card. We leave CurrentCard
    // where it is and loop to look at the next higher card.
    goto [GetNextCard]

The testing is done when CurrentCard = Cards.First since the topmost card is always fully visible.

Just a couple more thoughts here ...

I think this would be fairly straightforward in real code. The most complicated thing about it would be splitting a rectangle into two, and given the fact that it's all integer math, even that is trivial.

Also, this doesn't have to be performed every paint cycle. It only needs to be done when there's any change in contents, position, or z-order.

After a pass up the list, you're left with a paint-ready list of cards, each non-culled card having at least one rectangle that can potentially fall within the display's clipping/dirty region. When you paint a card you can examine its list of visible rectangles, and potentially be able to skip drawing portions of the card that might be expensive to render.