|
|
|
This thread is locked; no one can reply to it.
|
1
2
|
| Dirty Rectangle System |
|
ImLeftFooted
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 So, this brings me to my main issue, getting this thing to work Heres some relevant code:
I've uploaded my project at its current status so its possible to see the issues in this system in real time. Is there anyone who understands this stuff? I sure dont edit: the controls for the linked project: |
|
Steve Terry
Member #1,989
March 2002
 |
Quote:
Steve Terry's NAS GUI: Here I found a working DRS with overlapping
Heh thanks ___________________________________ |
|
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 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 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. 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.
--- |
|
William Labbett
Member #4,486
March 2004
 |
hey i will! now whose the kind person who gave the long post about rectangles on this 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: 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: 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
 |
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. -- Ryan Patterson - <http://cgamesplay.com/> |
|
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. -- 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
|
aximilar: Look A splits B into 3 parts:</code> ------------- -- 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
|
How would it not be an optimization for other ones? You have fewer rectangles, meaning fewer blits... -- Ryan Patterson - <http://cgamesplay.com/> |
|
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. -- |
|
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. -- 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
|
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. -- 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
 |
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 -- 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
|
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
|
. 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.
.
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.
