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. 1   2
 Dirty Rectangle System
Dustin Dettmer
Member #3,935
October 2003

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

Heres some relevant code:

 1 void 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 7 std::list dirty_zones; 8 std::list cleanup_zones; 9 std::list current_job; 10 bool buf_store_moded = false; 11 12 void stuoop_buf_blit() { 13 14 // ... 15 16 std::list::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::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::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 53 void _mark(list&,list&,dirty_zone*,int,int,int,int); 54 55 inline void mark(int x1, int y1, int x2, int y2, list &dest) { 56 dirty_zone *current_new = new dirty_zone(x1, y1, x2, y1); 57 58 list mark_list; 59 60 _mark(dest, mark_list, current_new, x1, y1, x2, y2); 61 62 list::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 71 inline 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 */ 110 inline 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 114 inline int _mark_logic(list &dirty_zones, list &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 153 void _mark(list &dirty_zones, list &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::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 .

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 Quote: Steve Terry's NAS GUI: Here I found a working DRS with overlapping . 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 I stole it and modified it from COUGH*Mirans*COUGH version 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.deBill 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 overlappingcase 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 overlappingPartial 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 visibleHorizontally:```-------------------- |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 hey i will!now whose the kind person who gave the long post about rectangles on thisthread ?good on ya
 axilmar Member #1,204 April 2001 Here is the 2nd part:AnalysisWhat 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.ImplementationThe 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 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()); } ``` ConclusionsThe 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 algorithmsAnother 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 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 -
 axilmar Member #1,204 April 2001 B-A != A-B.
 CGamesPlay Member #2,559 July 2002 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 -
 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 2Do 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 aximilar: Look A splits B into 3 parts: ------------- |B1/////////| |///////////|------------------|A |B2/|| |///|| |///|| |///|------------------ |B3/////////| |///////////| -------------BUT! What if we reversed it. B splits A! into 1 part! ------------- |B | | |-----| ||A1//| ||////| ||////| ||////| |-----| | | | | | -------------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 -
 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 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 -
 ReyBrujo Moderator January 2001 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 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 -
 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 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 -
 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 ```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 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 -
 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.
 Dustin Dettmer Member #3,935 October 2003 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: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads