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_zone*> dirty_zones; |
| 8 | std::list<dirty_zone*> cleanup_zones; |
| 9 | std::list<dirty_zone*> current_job; |
| 10 | bool buf_store_moded = false; |
| 11 | |
| 12 | void 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 | |
| 53 | void _mark(list<dirty_zone*>&,list<dirty_zone*>&,dirty_zone*,int,int,int,int); |
| 54 | |
| 55 | inline 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 | |
| 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_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 | |
| 153 | void _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 .
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)
I stole it and modified it from COUGH*Mirans*COUGH version 
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.
