Making Rectangle List Non-Overlapping

This is a discussion on Making Rectangle List Non-Overlapping within the Game Programming forums, part of the General Programming Boards category; Hello, This kinda leads on from an earlier post I made in the C Programming board, but as that one ...

  1. #1
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,262

    Question 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.

  2. #2
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    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.

  3. #3
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,262
    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)
    Attached Files Attached Files

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 03:09 AM
  2. Duplicating value of pointer to linked list
    By zephyrcat in forum C Programming
    Replies: 14
    Last Post: 01-22-2008, 02:19 PM
  3. urgent help please...
    By peter_hii in forum C++ Programming
    Replies: 11
    Last Post: 10-30-2006, 05:37 AM
  4. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 08:01 AM
  5. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21