|
Frustrating algorithm for calculating redraw in DRS |
Edgar Reynaldo
Major Reynaldo
May 2007
|
Hi, I've got a dirty rectangle system in my WidgetHandler class that takes care of reducing the amount of screen to redraw. I'm trying to calculate which widgets need to be redrawn based on 1) the areas that have been marked dirty and 2) the widgets that have marked themself for redraw. For a long time I had a working implementation but for some reason or another now its broken (possibly due to my most recent refactor of the entire widget hierarchy) and it breaks the stack after going into an endless recursive loop. Here are the old routines : 1#warning TODO : CRASH IN CheckRedraw, endless loop
2void WidgetHandler::CheckRedraw(UINT widget_index) {
3 if (widget_index >= drawlist.size()) {return;}
4 WidgetBase* widget = drawlist[widget_index];
5 UINT widgetflags = widget->Flags();
6 Rectangle widgetarea = widget->OuterArea();
7
8 /// For widgets that need their background redrawn, this means all widgets behind them need to be redrawn as well
9 if ((widgetflags & NEEDS_BG_REDRAW) ||
10 ((widgetflags & NEEDS_REDRAW) && !(widgetflags & VISIBLE))) {
11 /// Check whether each widget behind it overlaps
12 for (UINT i = 0 ; i < widget_index ; ++i) {
13 WidgetBase* w = drawlist[i];
14 Rectangle area = w->OuterArea();
15 if (widgetarea.Overlaps(area)) {
16 if (w->Flags().FlagOff(NEEDS_REDRAW)) {// w doesn't have the redraw flag set
17 w->SetRedrawFlag();
18 CheckRedraw(i);
19 }
20 }
21 }
22 }
23 /// For widgets that need to be redrawn, this means all widgets in front of them need to be redrawn as well
24 if ((widgetflags & NEEDS_REDRAW) && (widgetflags & VISIBLE)) {
25 /// Check whether each widget in front of it overlaps
26 for (UINT i = widget_index + 1 ; i < drawlist.size() ; ++i) {
27 WidgetBase* w = drawlist[i];
28 Rectangle area = w->OuterArea();
29 if (widgetarea.Overlaps(area)) {
30 if (w->Flags().FlagOff(NEEDS_REDRAW)) {
31 w->SetRedrawFlag();
32 CheckRedraw(i);
33 }
34 }
35 }
36 }
37}
38
39
40
41void WidgetHandler::CheckRedraw() {
42 /// Each widget that needs its background redrawn needs all overlapping widgets before it to be redrawn as well
43 /// Each widget that needs to be redrawn needs all overlapping widgets after it to be redrawn as well.
44 /// Each time a widget is set to be redrawn by this algorithm it needs to have the same two checks performed on it as well.
45 /// Each widget that overlaps a dirty background area needs to be redrawn
46 for (list<Rectangle>::iterator it = dbg_list.begin() ; it != dbg_list.end() ; ++it) {
47 Rectangle r = *it;
48 for (UINT i = 0 ; i < drawlist.size() ; ++i) {
49 WidgetBase* w = drawlist[i];
50 Rectangle area = w->OuterArea();
51 if (r.Overlaps(area)) {
52 if (w->Flags().FlagOff(NEEDS_REDRAW)) {
53 w->SetRedrawFlag();/// TODO : This might invalidate dbg_list
54 }
55 }
56 }
57 }
58 /// TODO : From back to front? Or front to back?
59
60 /// drawlist is sorted from the back to the front
61 for (UINT i = 0 ; i < drawlist.size() ; ++i) {
62 CheckRedraw(i);
63 }
64}
Like I said, they crash now, so I need to rework them to fix things. Here are the rules ; So, what is a good way to go about this? In the old version (which worked for a long time, or else I just never ran into corner cases), I used recursion. I iterated over the whole list from back to front depth wise (in z order) and if any widget was in front of a widget that needed to be redrawn, then I marked it for redraw. Likewise if it needed its bg redrawn, I marked all widgets behind it as needing to be redrawn. Well the old version is a giant cloister freak and I'm suprised it works at all. What is a good data structure and algorithm to tackle this problem? Help me solve it and I'll give you credit in my contributors list and in the source code. Is there something I can fix in the original algorithm? Or should I write it from scratch? E. My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
Peter Hull
Member #1,136
March 2001
|
Would it help the infinite recursion to return early from WidgetHandler::CheckRedraw(UINT widget_index) if the widget has already been marked as needing redraw? Does it always get stuck or just for certain combinations of widgets?
|
Edgar Reynaldo
Major Reynaldo
May 2007
|
In the current scenario, it crashes in an endless loop between CheckRedraw(0) and CheckRedraw(1). Each one is calling the other forever. Peter Hull said: Would it help the infinite recursion to return early from WidgetHandler::CheckRedraw(UINT widget_index) if the widget has already been marked as needing redraw? The name is misleading, as it is checking if the widget that needs redraw is causing other widgets to need redraw. It might help if it has already been checked though, and I don't currently test for that. :O My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
Elias
Member #358
May 2000
|
Well, one very simple way to avoid infinite recursion, remove the two recursive CheckRedraw(i) calls in your first CheckRedraw method and then instead of the loop in your second CheckRedraw method do something like: while (true) { changed = false; for (UINT i = 0 ; i < drawlist.size() ; ++i) { CheckRedraw(i); } if (!changed) break; } And every time you call SetRedrawFlag also set changed to true. -- |
Chris Katko
Member #1,881
January 2002
|
I don't get the problem. I mean, I get it. But what have you done to replicate it? Get a simple test case. Measure the stack depth, once it hits 10 or 15, dump the entire stack trace / supporting variables / etc. Or, fire off a breakpoint at that point, and step through each one manually and watch the control flow. (Visual Studio is wicked easy at that. As much as I hate the bloated mess.) Something like infinite recursion is NOT a subtle failure mode! It's not like, setting one bit wrong compared to your expectations. It's completely going off the rails! So find where the place where it starts to jump the rails. There's only a few places / functions that are "allowed" to modify the stack, right? -----sig: |
Edgar Reynaldo
Major Reynaldo
May 2007
|
Well, after everyone's advice, here's what I came up with : 1
2std::set<unsigned int> WidgetHandler::CheckRedraw(UINT widget_index) {
3 std::set<unsigned int> eset;
4 if (widget_index >= drawlist.size()) {return eset;}
5 WidgetBase* cwidget = drawlist[widget_index];
6 UINT cflags = cwidget->Flags();
7 Rectangle carea = cwidget->OuterArea();
8
9 if (!(cflags & NEEDS_REDRAW)) {
10 return eset;
11 }
12
13 /// If we need to be redrawn, so does every widget in front of us
14
15 /// Check every widget in front of us for overlap with our area
16
17 std::set<unsigned int> checkset;
18 for (unsigned int i = widget_index + 1 ; i < drawlist.size() ; ++i) {
19 WidgetBase* w = drawlist[i];
20 if (carea.Overlaps(w->OuterArea())) {
21 if (w->Flags().FlagOff(NEEDS_REDRAW)) {
22 w->SetRedrawFlag();
23 checkset.insert(i);
24 }
25 }
26 }
27 return checkset;
28}
29
30
31
32void WidgetHandler::CheckRedraw() {
33 /// Check from back to front
34 typedef std::set<unsigned int> WSET;
35 typedef list<Rectangle> RLIST;
36
37 /// Prime the list of widgets to check
38 WSET recheck;
39 for (unsigned int i = 0 ; i < drawlist.size() ; ++i) {
40 if (drawlist[i]->Flags().FlagOn(NEEDS_REDRAW)) {
41 recheck.insert(i);
42 }
43 }
44
45 /// Prime the dirty background list - it may be altered by CheckRedraw or if a widget sets the BG_REDRAW flag
46 RLIST dirty = dbg_list;
47 dbg_list.clear();
48
49 /// For storing new areas that get marked as dirty by widget checks
50 RLIST new_dbg_list;
51
52 /// Run each list at least once
53 do {
54 WSET check = recheck;
55 recheck.clear();
56
57 /// Each widget that overlaps a dirty background area needs to be redrawn
58 for (RLIST::iterator it = dirty.begin() ; it != dirty.end() ; ++it) {
59 Rectangle r = *it;
60 for (UINT i = 0 ; i < drawlist.size() ; ++i) {
61 WidgetBase* w = drawlist[i];
62 Rectangle area = w->OuterArea();
63 if (r.Overlaps(area)) {
64 if (w->Flags().FlagOff(NEEDS_REDRAW)) {
65 w->SetRedrawFlag();/// This may alter dbg_list
66 recheck.insert(i);
67 }
68 }
69 }
70 }
71
72 /// Each widget that needs redraw needs to check for causing other widgets to redraw
73 for (WSET::iterator it = check.begin() ; it != check.end() ; ++it) {
74 WSET newcheck = CheckRedraw(*it);/// This may alter dbg_list
75 recheck.insert(newcheck.begin() , newcheck.end());
76 }
77
78 /// Prepare the next set of dirty backgrounds
79 new_dbg_list.insert(new_dbg_list.end() , dirty.begin() , dirty.end());
80 dirty = dbg_list;
81 dbg_list.clear();
82
83 } while (recheck.size() || dirty.size());
84
85 dbg_list = new_dbg_list;
86}
It uses iteration instead of recursion. The new algorithm is as follows : l) For every widget that overlaps a dirty background area, it's redraw flag is set. 3) Repeat steps 1 and 2 until there are no new dirty background rectangles or widgets that need to be checked. Seems to be working so far, but I need to do some testing before I can say it's good. EDIT Anyway, Thanks! I'll be sure to include a mention of your help in my source code before my next commit. My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
|