Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Frustrating algorithm for calculating redraw in DRS

Credits go to Chris Katko, Elias, and Peter Hull for helping out!
This thread is locked; no one can reply to it. rss feed Print
Frustrating algorithm for calculating redraw in DRS
Edgar Reynaldo
Major Reynaldo
May 2007
avatar

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 :

#SelectExpand
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 ;
1) Any widget that overlaps a dirty area needs to be redrawn.
2) Any widget that needs to be redrawn needs all widgets in front of it to be redrawn as well.
3) Any widget that needs its background redrawn needs all widgets behind it to be redrawn as well.
4) When a widget marks itself with the flag NEEDS_BG_REDRAW it calls its parent widget handler and marks its area as dirty on the widget handler buffer, which starts the process over again.

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.

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
avatar

In the current scenario, it crashes in an endless loop between CheckRedraw(0) and CheckRedraw(1). Each one is calling the other forever.

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

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.

--
"Either help out or stop whining" - Evert

Chris Katko
Member #1,881
January 2002
avatar

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:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Well, after everyone's advice, here's what I came up with :

#SelectExpand
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.
2) For every widget that has it's redraw flag set, all widgets in front of it have their redraw flag set. This may create new dirty background rectangles.

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
Haven't had a chance to test it, but it seems valid. The base case (no new regions to redraw) should terminate the iteration.

Anyway,
Creditz!

Thanks!

I'll be sure to include a mention of your help in my source code before my next commit. ;)

Go to: