Thread: Making Rectangle List Non-Overlapping

Hello,

This kinda leads on from an earlier post I made in the C Programming board, but as that one apparently fell on deaf ears I suppose graphics-related algorithms can be posted under Game Programming?

Anyways, I'm trying to implement what could be referred to as "dirty rectangle drawing". I've got all the basic rectangle functions sorted out (intersection, difference) and adapted them for use with linked lists of rectangles that can describe a complex region.

The thing is, applying intersection and difference to two rectangles in lists ignores the presence of any other rectangles and so I end up with a lot of overlapping rectangles, which is bad.

Is the pseudocode function below, which modifies a list given to it to contain non-overlapping rectangles only, sensible?

Code:

void deoverlap_region(t_region *region)
{
    t_region *rgn1, *rgn2, *rgnIntersect;

    rgn1 = region;
    While rgn1
    {
        rgn2 = region;
        While rgn2
        {
            If (rgn1 <> rgn2)
            {
                rgnIntersect = intersect(rgn1, rgn2);
                If (rgnIntersect)
                {
                    Detach rect rgn2 from the list
                    Append the difference of rgn2 and rgnIntersect (rgn2 - rgnIntersect) to region
                    rgn2 = the rect that was next in the list
                }
                Else
                    rgn2 = rgn2->next;

            }
            Else
                rgn2 = rgn2->next;
            
        }

        rgn1 = rgn1->next;
    }

}

If anyone knows anywhere that talks about this type of algorithm, I'd be grateful.

You can do that or you can create more rectangles to account for the overlap. When two rectangles overlap they create another rectangle. They also create an L-shaped area in both rectangles representing the portion that is non-overlapping. You can split these areas into two more rectangles using the appropriate corners of the overlapped area. This does not require any sorting in the list or removal but it does require a bit more memory since you are adding several more rectangles.

So when you overlap 2 rectangles you get this:

1 new rectangle representing the overlapped area.
Several new rectangles representing the non-overlapped area in both rectangles.

It may actually take more time to compute overlapped areas and eliminate them than it would just to update them as is. I wouldn't worry about it too much since a quad can be drawn extremely fast in hardware.

Quads be damned, I'm not just using this for a game. If it works out I'm gonna backport it to my assembly language OS. I will adjust behaviour based on hardware availability.

Anywho, for those of you who like to take a hands-on approach, here's a little example app that has been GDIerized and shows exactly my current problem. Change EXCLUDES to 5 and run, then change it back to 6 and see the problem.

Have a play and see if you can figure it out.

Req.: Windows (or WINE I suppose)