Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Dirty Rectangle System

Credits go to axilmar and CGamesPlay for helping out!
This thread is locked; no one can reply to it. rss feed Print
 1   2 
Dirty Rectangle System
ImLeftFooted
Member #3,935
October 2003
avatar

Edit: If you're searching for a good explination of a Dirty Rectangle System, read axilmar's posts below, they go through in detail and include many ASCII drawings as aids.

Aeiii! Headache city. I've dedicated about the last week or so to getting my DR system to work correctly, starting over about 5 times so far. The basic components I understand, draw to a buffer, store those corrodinates in a vector of some sort, check for overlapping rectangles, divide and conqueror. Keep a current list and and old list, combine the two into one list (check for overlapping again) and draw the final list buffer -> screen, background -> buffer.

All of it is simple enough except for one part.. Overlapping. I just can't seem to get it right.

I did some research, to try and see if there was an example I could understand, and these are what I found:

DRS: the 'Dirty Rectangle System' seemed like a nice enough system, except that it was missing the one part I wanted to mimic, overlapping. It simply just stored all the rectangles and never checked for overlapping.

Allegro Demo: Again same thing, the dirty rectangle system didnt check for overlapping

Steve Terry's NAS GUI: Here I found a working DRS with overlapping :o. Now my problem is I barely can understand the code, let alone copy it. The guts of the overlapping is in one function some 100 lines long with int flags and bit moves. Needless to say I got lost in seconds.

So, this brings me to my main issue, getting this thing to work :P.

Heres some relevant code:

1void tile_blit(BITMAP *src, BITMAP *des) {
2 for(int x = 0; x < des->w; x += src->w)
3 for(int y = 0; y < des->h; y += src->h)
4 blit(src, des, 0, 0, x, y, src->w, src->h);
5}
6 
7std::list<dirty_zone*> dirty_zones;
8std::list<dirty_zone*> cleanup_zones;
9std::list<dirty_zone*> current_job;
10bool buf_store_moded = false;
11 
12void stuoop_buf_blit() {
13 
14 // ...
15 
16 std::list<dirty_zone*>::iterator citr = cleanup_zones.begin();
17
18 for(int i = 0; citr != cleanup_zones.end(); citr++, i++) {
19 mark((*citr)->x1, (*citr)->y1, (*citr)->x2, (*citr)->y2, current_job);
20
21 delete *citr;
22 }
23
24 cleanup_zones.clear();
25 
26 std::list<dirty_zone*>::iterator itr = dirty_zones.begin();
27
28 for(; itr != dirty_zones.end(); itr++) {
29 mark((*itr)->x1, (*itr)->y1, (*itr)->x2, (*itr)->y2, current_job);
30
31 cleanup_zones.push_back(*itr);
32 }
33
34
35 dirty_zones.clear();
36
37 std::list<dirty_zone*>::iterator jitr = current_job.begin();
38
39 for(; jitr != current_job.end(); jitr++) {
40 blit( buf, screen_dest, (*jitr)->x1, (*jitr)->y1, (*jitr)->x1 + x, (*jitr)->y1, (*jitr)->x2 - (*jitr)->x1, (*jitr)->y2 - (*jitr)->y1);
41 // notice the + x used above is for hardware scrolling optimization
42 blit(background, buf, (*jitr)->x1, (*jitr)->y1, (*jitr)->x1, (*jitr)->y1, (*jitr)->x2 - (*jitr)->x1, (*jitr)->y2 - (*jitr)->y1);
43
44 delete *jitr;
45 }
46
47 current_job.clear();
48 
49 // ...
50 
51}
52 
53void _mark(list<dirty_zone*>&,list<dirty_zone*>&,dirty_zone*,int,int,int,int);
54 
55inline void mark(int x1, int y1, int x2, int y2, list<dirty_zone*> &dest) {
56 dirty_zone *current_new = new dirty_zone(x1, y1, x2, y1);
57
58 list<dirty_zone*> mark_list;
59
60 _mark(dest, mark_list, current_new, x1, y1, x2, y2);
61
62 list<dirty_zone*>::iterator itr = mark_list.begin();
63
64 for(; itr != mark_list.end(); itr++) {
65 dest.push_back(*itr);
66 }
67
68 delete current_new;
69}
70 
71inline int _get_quad(int x1, int y1, int x2, int y2, int x, int y) {
72 int ret = 0;
73
74 if(x < x1) {
75 if(y < y1)
76 ret = 1;
77 else if(y < y2)
78 ret = 4;
79 else
80 ret = 7;
81 } else if(x < x2) {
82 if(y < y1)
83 ret = 2;
84 else if(y < y2)
85 ret = 5;
86 else
87 ret = 8;
88 } else {
89 if(y < y1)
90 ret = 3;
91 else if(y < y2)
92 ret = 6;
93 else
94 ret = 9;
95 }
96
97 return ret;
98}
99 
100/* return values:
101 * 1 | 2 | 3
102 * -----------------
103 * 4 | 5 | 6
104 * -----------------
105 * 7 | 8 | 9
106 *
107 * 5 represents dirty_zone *o
108 * _get_quad returns which quad x,y are in in relation to box o
109 */
110inline int _get_quad(dirty_zone *o, int x, int y) {
111 return _get_quad(o->x1, o->y1, o->x2, o->y2, x, y);
112}
113 
114inline int _mark_logic(list<dirty_zone*> &dirty_zones, list<dirty_zone*> &mark_list, dirty_zone *current_new, dirty_zone *o, int x1, int y1, int x2, int y2) {
115 if(x1 > x2)
116 std::swap(x1, x2);
117 if(y1 > y2)
118 std::swap(y1, y2);
119
120 int o_upper_left = _get_quad(o, x1, y1);
121 int o_upper_right = _get_quad(o, x2, y1);
122 int o_lower_right = _get_quad(o, x2, y2);
123 int o_lower_left = _get_quad(o, x1, y2);
124
125 int cn_upper_left = _get_quad(current_new, x1, y1);
126 int cn_upper_right = _get_quad(current_new, x2, y1);
127 int cn_lower_right = _get_quad(current_new, x2, y2);
128 int cn_lower_left = _get_quad(current_new, x1, y2);
129 
130 // Must have all corners inside current_new to continue, if we dont return fail
131 if(cn_upper_left != 5 || cn_upper_right != 5 || cn_lower_right != 5 || cn_lower_left != 5)
132 return false;
133
134 // Cant have all corners inside original (o), if we do return fail
135 if(o_upper_left == 5 && o_lower_right == 5)
136 return false;
137
138 // Must have one corner inside original (o) to continue, if we dont, then this is a finished square, return success
139 if(o_upper_left != 5 && o_upper_right != 5 && o_lower_right != 5 && o_lower_left != 5)
140 return true;
141
142 // horizontal overlapping
143 _mark(dirty_zones, mark_list, current_new, x1, y1, o->x1, y2);
144 _mark(dirty_zones, mark_list, current_new, o->x2, y1, x2, y2);
145
146 // verticle overlapping (this crops corners)
147 _mark(dirty_zones, mark_list, current_new, MAX(x1, o->x2), y1, MIN(x2, o->x2), o->y1);
148 _mark(dirty_zones, mark_list, current_new, MAX(x1, o->x2), o->y2, MIN(x2, o->x2), y2);
149
150 return false;
151}
152 
153void _mark(list<dirty_zone*> &dirty_zones, list<dirty_zone*> &mark_list, dirty_zone *current_new, int x1, int y1, int x2, int y2) {
154 if(x1 > x2)
155 std::swap(x1, x2);
156 if(y1 > y2)
157 std::swap(y1, y2);
158
159 if(!(x2 - x1) || !(y2 - y1))
160 return;
161
162 bool mark_now = true;
163
164 std::list<dirty_zone*>::iterator itr = dirty_zones.begin();
165
166 for(int id = 0; itr != dirty_zones.end(); itr++, id++) {
167 mark_now = _mark_logic(dirty_zones, mark_list, current_new, *itr, x1, y1, x2, y2);
168 }
169
170 if(mark_now)
171 mark_list.push_back(new dirty_zone(x1, y1, x2, y2));
172}

I've uploaded my project at its current status so its possible to see the issues in this system in real time.
tar format
zip format
Both formats should work on any unix with gcc, windows with mingw32, or DOS with djgpp.

Is there anyone who understands this stuff? I sure dont :P.

edit: the controls for the linked project:
Left shift : call mark(0, 0, SCREEN_W, SCREEN_H) i.e. try to redraw the whole screen
Right shift : animate boxes on screen (theres 2 of them)
Enter : set second_countdown to 10 (fairly useless in this example)
Up Arrow : make the rectangles bounce faster (you'll only notice a differnce if you're also holding the right shift key)
Down Arrow : make the rectangles bounce slower (or backwards) (you'll only notice a differnce if you're also holding the right shift key)

Steve Terry
Member #1,989
March 2002
avatar

Quote:

Steve Terry's NAS GUI: Here I found a working DRS with overlapping :o. Now my problem is I barely can understand the code, let alone copy it. The guts of the overlapping is in one function some 100 lines long with int flags and bit moves. Needless to say I got lost in seconds.

Heh thanks ;D I stole it and modified it from COUGH*Mirans*COUGH version :P What's wrong with it, it's just a bit of recursion.... oooh and I found a way to optimize recursion too with some tricky assembly and stack winding I may have to use one day :) It's a pretty slick concept, you simply modify the stack so that when the end condition is met instead of unwinding the stack you simply pop right out of the sucker. I think we found though through bitter discussion is that overlapping can be a bottleneck and it's generally best to just not do it, there were a variet of other DRS methods discussed too, I still like optimized blits though, at least it makes you feel good knowing you did something cool.

___________________________________
[ Facebook ]
Microsoft is not the Borg collective. The Borg collective has got proper networking. - planetspace.de
Bill Gates is in fact Shawn Hargreaves' ßî+çh. - Gideon Weems

axilmar
Member #1,204
April 2001

Solving rectangle overlapping is a difficult thing to grasp at the beginning, but once you understand the basic concepts, it suddently becomes very easy.

The problem is about how to combine two collections of rectangles into a third one without having overlapping parts. A solution is to 'subtract' the overlapping parts from one of the lists, then combine the other list with the new list:

//first list
LIST A

//second list
LIST B

//list that contains all rectangles of B except the rectangles of A
TEMP LIST = LIST B - LIST A

//optimal list that contains all rectangles of A plus all rectangles of B not overlapping with A
OPTIMAL LIST = LIST A + TEMP LIST

In order to subtract one list from another, you have to understand all the possible ways two rectangles can overlap. Put one rectangle in the center, then move the other around it. You may use two pieces of paper to understand the concept better.

The obvious cases are that 1) a rectangle completely overlaps another rectangle, 2) the rectangles don't overlap at all, 3) rectangles overlap partially. Let's see all the possible cases:

total overlapping

--------------------
|A                 |
|                  |
|   ------------   |
|   |B         |   |
|   |          |   |
|   |          |   |
|   |-----------   |
|                  |
|                  |
--------------------

no overlapping

case a): rect A at left of B

--------------------
|A                 |
|                  |
|                  |      ------------
|                  |      |B         |
|                  |      |          |
|                  |      |          |
|                  |      ------------
|                  |
|                  |
--------------------

case b): rect A at right of B

                   --------------------
                   |A                 |
                   |                  |
------------       |                  |
|B         |       |                  |
|          |       |                  |
|          |       |                  |
------------       |                  |
                   |                  |
                   |                  |
                   --------------------

case c): rect A above B

#SelectExpand
1-------------------- 2|A | 3| | 4| | 5| | 6| | 7| | 8| | 9| | 10| | 11-------------------- 12 13 14 ------------ 15 |B | 16 | | 17 | | 18 ------------

case d): rect A below B

#SelectExpand
1 ------------ 2 |B | 3 | | 4 | | 5 ------------ 6 7 8-------------------- 9|A | 10| | 11| | 12| | 13| | 14| | 15| | 16| | 17| | 18--------------------

There are also 4 more cases: A at left-above B, A at left-below B, A at right-above B, A at right-below B.

partial overlapping

Partial overlapping is the trickiest part to understand, as there are many cases. A rectangle A may overlap a rectangle B in such a way that:

1) only one part of B is visible.
2) only two parts of B are visible: a) one part from the left side and one part from the right side or b) one part from the top side and one part of the bottom side.
3) rectangle A overlaps a corner of B.
4) rectangle A overlaps a middle portion of one side of B.
5) rectangle A is in the middle of B.

Let's see some examples.

case (1): only one part of B is visible

Horizontally:

--------------------
|A                 |
|                  |
|                  |------
|                  |B    |
|                  |     |
|                  |     |
|                  |------
|                  |
|                  |
--------------------

or

     --------------------
     |A                 |
     |                  |
-----|                  |
|B   |                  |
|    |                  |
|    |                  |
-----|                  |
     |                  |
     |                  |
     --------------------

Vertically:

    ------------
    |B         |  
    |          |  
--------------------
|A                 |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
--------------------

Or

--------------------
|A                 |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
--------------------
    |B         |  
    |          |  
    ------------

case (2): only two parts of B are visible

    -----------------
    |B              |
    |               |
-------------------------
|A                      |
|                       |
|                       |
-------------------------
    |               |
    |               |
    -----------------

or

     |-------------|
     |A            |
-----|             |-----
|B   |             |    |
|    |             |    |
|    |             |    |
|    |             |    |
-----|             |-----
     |             |
     ---------------

case (3): rectangle A overlaps a corner of B

--------------------
|A                 |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |-------
|                  |      | 
|                  |      |
--------------------      |
              |B          |
              |           |
              -------------

or

              -------------
              |B          |
              |           |
--------------------      |
|A                 |      |
|                  |      |
|                  |-------
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
--------------------

or

-------------
|B          |
|           |
|       --------------------
|       |A                 |
|       |                  |
--------|                  |
        |                  |
        |                  |
        |                  |
        |                  |
        |                  |
        |                  |
        --------------------

or

        --------------------
        |A                 | 
        |                  |
        |                  |
        |                  |
        |                  |
        |                  |
--------|                  |
|B      |                  |
|       |                  |
|       --------------------
|           |
|           |
-------------

case (4) rectangle A overlaps a middle portion of one side of B.

     -------------
     |B          |
     |           |
--------------   |
|A           |   |
|            |   |
|            |   |
|            |   |
--------------   |
     |           |
     |           |
     -------------

Or

     -------------
     |B          |
     |           |
     |    --------------
     |    |A           |
     |    |            |
     |    |            |
     |    |            |
     |    --------------
     |           |
     |           |
     -------------

Or

     -----------
     |A        |
-----|         |-----
|B   |         |    |
|    |         |    |
|    -----------    |
|                   |
|                   |
---------------------

Or

---------------------
|B                  |
|                   |
|    -----------    |
|    |A        |    |
|    |         |    |
-----|         |-----
     |         |
     -----------

case (5) rectangle A is in the middle of B.

--------------------
|B                 |
|                  |
|   ------------   |
|   |A         |   |
|   |          |   |
|   |          |   |
|   |-----------   |
|                  |
|                  |
--------------------

The above is the first part. Somebody please post a little message so I can post the 2nd part.

Kauhiz
Member #4,798
July 2004

Quote:

Somebody please post a little message so I can post the 2nd part.

---
It's Ridge Racer! RIIIIIDGE RAAAAACER!

William Labbett
Member #4,486
March 2004
avatar

hey i will!

now whose the kind person who gave the long post about rectangles on this
thread ?

good on ya

axilmar
Member #1,204
April 2001

Here is the 2nd part:

Analysis

What we see from the above is that rectangle A splits rectangle B into one or more rectangles. Let's see how rectangle B is splitted.

Total overlap:

In total overlap, there is no left overs from rectangle B.

No overlap:

When two rectangles don't overlap, B remains as is.

Partial overlap:

(Area covered with '////' is the remaining rectangle)

Rectangle A splits rectangle B in one rectangle:

--------------------
|A                 |
|                  |
|                  |------
|                  |B1///|
|                  |/////|
|                  |/////|
|                  |------
|                  |
|                  |
--------------------

     --------------------
     |A                 |
     |                  |
-----|                  |
|B1//|                  |
|////|                  |
|////|                  |
-----|                  |
     |                  |
     |                  |
     --------------------

    ------------
    |B1////////|  
    |//////////|  
--------------------
|A                 |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
--------------------

--------------------
|A                 |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
--------------------
    |B1////////|  
    |//////////|  
    ------------

Rectangle A splits rectangle B in two rectangles:

    -----------------
    |B1/////////////|
    |///////////////|
-------------------------
|A                      |
|                       |
|                       |
-------------------------
    |B2/////////////|
    |///////////////|
    -----------------

     |-------------|
     |A            |
-----|             |-----
|B1//|             |B2//|
|////|             |////|
|////|             |////|
|////|             |////|
-----|             |-----
     |             |
     ---------------

--------------------
|A                 |
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |-------
|                  |B2////| 
|                  |//////|
-------------------|------|
              |B1/////////|
              |///////////|
              -------------

              -------------
              |B1/////////|
              |///////////|
-------------------|------|
|A                 |B2////|
|                  |//////|
|                  |-------
|                  |
|                  |
|                  |
|                  |
|                  |
|                  |
--------------------

-------------
|B1/////////|
|///////////|
|-------|-------------------
|B2/////|A                 |
|///////|                  |
--------|                  |
        |                  |
        |                  |
        |                  |
        |                  |
        |                  |
        |                  |
        --------------------

        --------------------
        |A                 | 
        |                  |
        |                  |
        |                  |
        |                  |
        |                  |
--------|                  |
|B1/////|                  |
|///////|                  |
|-------|-------------------
|B2/////////|
|///////////|
-------------

Rectangle A splits rectangle B in three rectangles:

     -------------
     |B1/////////|
     |///////////|
------------------
|A           |B2/|
|            |///|
|            |///|
|            |///|
------------------
     |B3/////////|
     |///////////|
     -------------

Or

     -------------
     |B1/////////|
     |///////////|
     -------------------
     |B2//|A           |
     |////|            |
     |////|            |
     |////|            |
     -------------------
     |B3/////////|
     |///////////|
     -------------

Or

     -----------
     |A        |
-----|         |-----
|B1//|         |B3//|
|////|         |////|
|////-----------////|
|////|B2///////|////|
|////|/////////|////|
---------------------

Or

---------------------
|B1//|B2///////|B3//|
|////|/////////|////|
|////-----------////|
|////|A        |////|
|////|         |////|
-----|         |-----
     |         |
     -----------

case (5) Rectangle A splits rectangle B in four rectangles:

--------------------
|B1////////////////|
|//////////////////|
|------------------|
|B2/|A         |B3/|
|///|          |///|
|///|          |///|
|------------------|
|B4////////////////|
|//////////////////|
--------------------

As we can see, the splitting of rectangle B from rectangle A results to 0, 1, 2, 3 or 4 new rectangles. We see that splitting is done per side, i.e. the left side of rect A splits the left side of rect B, the top side of rect A splits the top side of rect B etc. Let's see how we can implement it.

Implementation

The following is only an example, of course. You may optimize it the way it suits you. I am going to use C++, as STL gives me a ground to talk on.

We need a routine that takes two rectangles as an input, and produces a list of rectangles that is the remains of the splitting, as it was described above. The routine supposes that the two rectangles overlap. Let's see the routine:

#SelectExpand
1//rectangle 2struct Rect { 3 int left; 4 int top; 5 int right; 6 int bottom; 7}; 8 9//type of rectangle list 10typedef std::list<Rect> RectList; 11 12//splits a rectangle by another rectangle 13RectList splitRect(const Rect &b, const Rect &a) 14{ 15 RectList result; 16 Rect t; 17 18 //split the left side 19 if (b.left < a.left) { 20 t.left = b.left; 21 t.right = a.left - 1; 22 t.top = MAX(a.top, b.top); 23 t.bottom = MIN(a.bottom, b.bottom); 24 result.push_back(t); 25 } 26 27 //split the right side 28 if (b.right > a.right) { 29 t.left = a.right + 1; 30 t.right = b.right; 31 t.top = MAX(a.top, b.top); 32 t.bottom = MIN(a.bottom, b.bottom); 33 result.push_back(t); 34 } 35 36 //split the top side 37 if (b.top < a.top) { 38 t.top = b.top; 39 t.bottom = a.top - 1; 40 t.left = MAX(a.left, b.left); 41 t.right = MIN(a.right, b.right); 42 } 43 44 //split the bottom side 45 if (b.bottom > a.bottom) { 46 t.top = a.bottom + 1; 47 t.bottom = b.bottom; 48 t.left = MAX(a.left, b.left); 49 t.right = MIN(a.right, b.right); 50 } 51 52 return result; 53}

The above routine splits rectangle B into one or more rectangles by subtracting rectangle A from B. After the splitting, the rectangle B is no longer useful. The routine should be used in another routine that subtracts a rectangle from a rectangle list:

#SelectExpand
1//rectangle iterator 2typedef RectList::iterator RectIterator; 3 4//subtracts rect 'r' from list 'l' 5void subtractRect(RectList &l, const Rect &r) 6{ 7 //iterate list 'l' 8 RectIterator it = l.begin(); 9 while (it != l.end()) { 10 //get next rectangle before the main action because 'it' may be erased from the list 11 RectIterator itNext = it; 12 ++itNext; 13 14 //get rectangle of list 'l' 15 const Rect &t = *it; 16 17 //if rectagle of list 't' and given rectangle 'r' overlap, then split 't' by 'r' 18 if (rectsOverlap(t, r)) { 19 RectList temp = splitRect(t, r); 20 l.insert(it, temp.begin(), temp.end()); 21 22 //the rectangle 't' was splitted, so we no longer need it 23 l.erase(it); 24 } 25 26 //next rectangle 27 it = itNext; 28 } 29}

The above routine is useful in subtracting one list from the other:

//subtracts rectangle list 'a' from rectangle list 'b'
void subtractList(RectList &b, const RectList &a)
{
    for(RectIterator it = a.begin(); it != a.end(); ++it) {
        subtractRect(b, *it);
    }
}

So the algorithm of optimally combine two rectangle lists becomes:

void combineLists(RectList &result, const RectList &a, const RectList &b)
{
    //subtract list A from list B
    result = b;      
    subtractList(result, a);
    
    //unite B-A with list A
    result.insert(result.end(), a.begin(), a.end());
}

Conclusions

The above algorithms may be optimized in numerous ways: rectangles can be kept in pre-allocated lists ordered by scanlines; arrays can be used instead double-linked lists; horizontal strips may be combined; rectangles can be ordered vertically from top to bottom in order to be nice to the screen refresh etc.

Other DRS algorithms

Another DRS algorithm, which is much simpler, is to divide the playing area into blocks, and mark each block that is dirty. When it is time to update the screen, blit all dirty blocks. By carefully chosing the size of blocks, an optimal speed may be achieved.

Dirty blocks can be placed in a list if their dirty flag is not set. Then the list of dirty blocks is traversed, each block's dirty flag is reset and the relevant area of the game buffer is blitted to the screen.

You can find an example of the above [url http://www.allegro.cc/forums/view_thread.php?_id=395646]here[/url].

CGamesPlay
Member #2,559
July 2002
avatar

The most glaring optimization to me would be that if subtracting A from B yields 3 or 4 rectangles, instead subtract B from A, which will result in 1 or 0 rectangles, respectively.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

axilmar
Member #1,204
April 2001

CGamesPlay
Member #2,559
July 2002
avatar

The goal of overlap handling is to effectively OR the two buffers together (were they stored as a mask). In order to do this, you remove the intersection of A from B, then merge the two lists together. This is functionally the same as removing B from A and merging the two lists together. By doing this, you have fewer rectangles in the end product.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

axilmar
Member #1,204
April 2001

Quote:

This is functionally the same as removing B from A

Nothing guarrantees that A-B is more optimizable than B-A and vice versa.

Quote:

and merging the two lists together.

You have to unite the result with the other list though.

kentl
Member #2,905
November 2002

In a situation similar to the one below in figure 1, wouldn´t it be more effective to just blit the combined borders as in figure 2? (in that specific case) So that you get only one blit, and the rectangles are within a quite close range and aligned horizontally.

----------           -------
|        | --------  |     |
|   a    | |   b  |  |  c  |
---------- |      |  |-----|
           --------

Above -- Figure 1

----------------------------
| a:s left upper corner &  |
| a.left,b.bottom low left |
| corner and c upper right |
----------------------------

Above -- Figure 2

Do anyone know of any good books/articles about different DRS algorithms? I would like to get a feeling for which solutions are commonly used.

CGamesPlay
Member #2,559
July 2002
avatar

aximilar: Look A splits B into 3 parts:</code> -------------
|B1/////////|
|///////////|
------------------
|A |B2/|
| |///|
| |///|
| |///|
------------------
|B3/////////|
|///////////|
-------------</code>BUT! What if we reversed it. B splits A! into 1 part! -------------
|B |
| |
-----| |
|A1//| |
|////| |
|////| |
|////| |
-----| |
| |
| |
-------------</code>The net result of this is that when you merge A and B you have fewer rectangles and thus fewer blits. I don't know how much of an actual speed optimization this is, but it's there, nonetheless.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

axilmar
Member #1,204
April 2001

Quote:

In a situation similar to the one below in figure 1, wouldn´t it be more effective to just blit the combined borders as in figure 2? (in that specific case) So that you get only one blit, and the rectangles are within a quite close range and aligned horizontally.

It certainly would be more effective, but in order to do so you have to calculate distances between each pair of rectangles, either horizontally or vertically, which means that each rectangle should be compared with every other rectangle at least twice.

And then, how do you combine more than two rectangles in one blit?

There have to be some compromizes for such an optimization to work.

Quote:

aximilar: Look A splits B into 3 parts:

BUT! What if we reversed it. B splits A! into 1 part!

The net result of this is that when you merge A and B you have fewer rectangles and thus fewer blits. I don't know how much of an actual speed optimization this is, but it's there, nonetheless.

I understood what you say in the first post. But you have to be aware that if you reverse the subtraction (do A-B instead of B-A), you have to subtract the result from the other list. In other words, you either do:

//list that contains all rectangles of B except the rectangles of A
TEMP LIST = LIST B - LIST A

//optimal list that contains all rectangles of A plus all rectangles of B not overlapping with A
OPTIMAL LIST = LIST A + TEMP LIST

or you do:

//list that contains all rectangles of B except the rectangles of A
TEMP LIST = LIST A - LIST B <---- your optimization here

//optimal list that contains all rectangles of B plus all rectangles of A not overlapping with B
OPTIMAL LIST = LIST B + TEMP LIST <---- needed change

There is no guarrantee that by doing the latter the subtraction will be more optimized. It may be so for one rectangle, but it may not be so for the other ones.

CGamesPlay
Member #2,559
July 2002
avatar

How would it not be an optimization for other ones? You have fewer rectangles, meaning fewer blits...

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

ReyBrujo
Moderator
January 2001
avatar

I just melt both rectangles in one, using the bounds to create it. Some parts that don't need to be blitted will be blitted, but still it is much faster than blitting a lot of small pieces in a near place.

--
RB
光子「あたしただ…奪う側に回ろうと思っただけよ」
Mitsuko's last words, Battle Royale

axilmar
Member #1,204
April 2001

Quote:

How would it not be an optimization for other ones? You have fewer rectangles, meaning fewer blits...

Because it is not guarranteed that the rest of the rectangles will have a configuration similar to the one you showed.

CGamesPlay
Member #2,559
July 2002
avatar

But I covered all possible configurations. If A-B would result in 3 or 4 resultant rectangles (which we can check for), than instead do B-A, which results in 1 or 2 resultants, respectively. If A-B results in 0, 1, or 2 resulatants, than stick with A-B.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

axilmar
Member #1,204
April 2001

Quote:

But I covered all possible configurations. If A-B would result in 3 or 4 resultant rectangles (which we can check for), than instead do B-A, which results in 1 or 2 resultants, respectively. If A-B results in 0, 1, or 2 resulatants, than stick with A-B.

The way the formula I posted works, if A and B are swapped in the rectangle subtraction, they have to be swapped in all the formulas.

And I am not sure if checking of how many rectangles the subtraction will result in is any different from the actual subtraction.

CGamesPlay
Member #2,559
July 2002
avatar

Consider the case with the largest difference. Case 5 in your above example. The way it is now, B-A, there are five rectangles in the end. Subtract A from B instead to see the new net: 1 rectangle.

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

axilmar
Member #1,204
April 2001

Quote:

Consider the case with the largest difference. Case 5 in your above example. The way it is now, B-A, there are five rectangles in the end. Subtract A from B instead to see the new net: 1 rectangle.

I understood what you said. Really. And you are correct, in the context of the rectangle subtraction. But unfortunately, it is not what we want.

If I do this:

     -------------
     |B          |
     |           |
-----|           |
|A1//|           |
|////|           |
|////|           |
|////|           |
-----|           |
     |           |
     |           |
     -------------

instead of this

     -------------
     |B1/////////|
     |///////////|
------------------
|A           |B2/|
|            |///|
|            |///|
|            |///|
------------------
     |B3/////////|
     |///////////|
     -------------

then the area A1 will exist twice in the final rectangle list: it will exist once in the intermediate temporary list that is the result of A-B and once in the list A.

Let's do the same example with sets. This is my way:

A = {1, 2, 3}
B = {2, 4, 5}
T = B - A = {2, 4, 5} - {1, 2, 3} = {4, 5}
R = A + T = {1, 2, 3} + {4, 5} = {1, 2, 3, 4, 5}

In the above example, we end up with a set that all elements are unique. Now let's try your method:

A = {1, 2, 3}
B = {2, 4, 5}
T = A - B = {1, 2, 3} - {2, 4, 5} = {1, 3}
R = A + T = {1, 2, 3} + {1, 3} = {1, 1, 2, 3, 3, 4, 5}

With your way, we end up with a set with duplicate elements. If an element was a rectangle, we would have duplicate rectangles.

Surt
Member #273
April 2000
avatar

A = {1, 2, 3}
B = {2, 4, 5}
T = A - B = {1, 2, 3} - {2, 4, 5} = {1, 3}
R = B + T = {2, 4, 5} + {1, 3} = {1, 2, 3, 4, 5}

EDIT: Where is the union symbol in WinXP charmap? I could find intersection, but union was no where near it.

---
--
-

CGamesPlay
Member #2,559
July 2002
avatar

I'm not sure of your notation, but how difficult is it to remove A from the original list?

(Sorry for the long delay, I had a hurricane take me offline for a few days :))

--
Tomasu: Every time you read this: hugging!

Ryan Patterson - <http://cgamesplay.com/>

axilmar
Member #1,204
April 2001

CGamesPlay, nothing guarrantees that by subtracting list A, the algorithm would be more optimizable than it is right now.

ImLeftFooted
Member #3,935
October 2003
avatar

Axilmar, you should submit this to pixelate, its an awesome walk through, thanks!

axilmar
Member #1,204
April 2001

I don't know how Pixelate works. Can anyone submit articles to it?

 1   2 


Go to: