![\"\"](\"https:\/\/blogs.scummvm.org\/t0by\/wp-content\/uploads\/sites\/43\/2013\/08\/untitled-1.png\")
<\/a>What would be the screen area to be considered \u201cdirty\u201d and thus redrawn?<\/p>\nYu guessed it \u2013 basically, the whole screen.<\/p>\n
Baaaaad.<\/p>\n
This was in fact the way dirty recting was originally implemented in the WME engine for ScummVM:<\/p>\n
void BaseRenderOSystem::addDirtyRect(const Common::Rect &rect) {\r\n if (!_dirtyRect) {\r\n _dirtyRect = new Common::Rect(rect);\r\n } else {\r\n _dirtyRect->extend(rect);\r\n }\r\n _dirtyRect->clip(_renderRect); \r\n}\r\n<\/pre>\nThat\u2019s it, one rect, extend it as needed.<\/p>\n
We needed multiple dirty rects.<\/p>\n
Whenever we \u201cdirty\u201d a screen area, we need to mark that separately.
\nBut a simple array is probably not enough.<\/p>\n
For example, what happens if multiple partially overlapping sprites are to be redrawn and we naively traverse the array?<\/p>\n
We redraw the same area over and over again; if the rects are big enough, we may end up doing *more* blitting than without dirty rects, *more* blitting than<\/p>\n
with a single rect.<\/p>\n
Also bad, very, very bad.<\/p>\n
Even if unnecessary redrawing is avoided, needlessly big rect lists can be a problem.<\/p>\n
I chose to address the issue with a special class that:<\/p>\n
a) Takes requests for adding rects\u2026
\na\u2019) \u2026while doing some on-the-fly-optimizations (e.g. discarding duplicates)
\nb) Can spit out, upon request, an optimized version with only the necessary rectangles.<\/p>\n
It is still in the works so this is not final code, but the basic idea is definitely there.
\nHave a look \u2013 code is partial and amended as usual, but you don\u2019t want to know about all the boring housekeeping and utility methods, do you?<\/p>\n
namespace Wintermute {\r\n \r\n \r\nDirtyRectContainer::DirtyRectContainer() {\r\n _disableDirtyRects = false;\r\n _clipRect = nullptr;\r\n}\r\n \r\nDirtyRectContainer::~DirtyRectContainer() {\r\n delete _clipRect;\r\n}\r\n \r\nvoid DirtyRectContainer::addDirtyRect(const Common::Rect &rect, const Common::Rect *clipRect) {\r\n \r\n if (_clipRect == nullptr) {\r\n _clipRect = new Common::Rect(*clipRect);\r\n } else {\r\n assert(clipRect->equals(*_clipRect));\r\n }\r\n \r\n if (target > kMaxInputRects) {\r\n _disableDirtyRects = true;\r\n } else if (isHuge(&rect)) { \/\/ More than 90% of the viewport\r\n _disableDirtyRects = true;\r\n } else if (rect.width() == 0 || rect.height() == 0) {\r\n } else {\r\n _rectArray.insert_at(target, tmp);\r\n _rectArray[target]->clip(*clipRect);\r\n }\r\n}\r\n \r\n \r\nCommon::Array DirtyRectContainer::getOptimized() {\r\n \r\n if (_disableDirtyRects) {\r\n return getFallback();\r\n }\r\n \r\n Common::Array ret;\r\n Common::Array queue;\r\n \r\n for (int i = 0; i < _rectArray.size(); i++) {\r\n queue.insert_at(queue.size(), _rectArray[i]);\r\n }\r\n \r\n int j = 0;\r\n while (j < queue.size()) { Common::Rect *candidate = queue[j]; if (candidate->width() == 0 || candidate->height() == 0) {\r\n \/\/ We have no use for this\r\n queue.remove_at(j);\r\n continue;\r\n }\r\n \r\n if (ret.size() > kMaxOutputRects) {\r\n _disableDirtyRects = true;\r\n return getFallback();\r\n }\r\n \r\n bool discard = false;\r\n \r\n \/\/ See if it's contained or containes\r\n for (uint i = 0; i < ret.size() && !discard; i++) { Common::Rect *existing = ret[i]; if (existing->contains(*candidate) || existing->equals(*candidate)) {\r\n \/\/ It is already contained by an existing rect - useless!\r\n discard = true;\r\n continue;\r\n }\r\n \r\n if (candidate->contains(*(existing))) {\r\n \/\/ Contains an existing one.\r\n \/\/ Extend the pre-existing one and discard this.\r\n existing->extend(*candidate);\r\n discard = true;\r\n continue;\r\n }\r\n \r\n \/\/ Okay, we now see if we have an overlapping corner and slice accordingly.\r\n Common::Rect intersecting = existing->findIntersectingRect(*candidate);\r\n \/\/ We have to remove intersecting and enqueue the rest\r\n \/\/ We know that it's not a simple contained rect, we know that\r\n \/\/ it's not a cross-shaped thing like above, we know that it's not\r\n \/\/ a Commodore-logo type of deal (where the C is the bigger rect)\r\n \/\/ So intersecting is either the NE, SE, SW or NW corner of candidate\r\n if (intersecting.width() >= kMaxSplicingX &&\r\n intersecting.height() >= kMaxSplicingY\r\n ) {\r\n if (intersecting.top >= candidate->top &&\r\n intersecting.left >= candidate->left &&\r\n intersecting.bottom == candidate->bottom &&\r\n intersecting.right == candidate->right\r\n ) { \/\/ SE case\r\n Common::Rect *neslice = new Common::Rect(*candidate);\r\n neslice->bottom = intersecting.top;\r\n neslice->left = intersecting.left;\r\n if (neslice->width() != 0 && neslice->height() != 0) {\r\n queue.insert_at(queue.size(), neslice);\r\n }\r\n candidate->right = intersecting.left;\r\n if (candidate->width() == 0) {\r\n discard = true;\r\n }\r\n \r\n } else if () \/\/SAME FOR NE \r\n { \/\/ ...\r\n } else if () \/\/SAME FOR NW\r\n { \/\/ ...\r\n } else if () \/\/SAME FOR SW \r\n { \/\/ ...\r\n } else if (existing->left <= candidate->left &&\r\n existing->right >= candidate->right &&\r\n existing->top >= candidate->top &&\r\n existing->bottom <= candidate->bottom) { \/\/ Cross shaped intersections\r\n Common::Rect *top_slice = new Common::Rect(*candidate);\r\n Common::Rect *bottom_slice = new Common::Rect(*candidate);\r\n top_slice->bottom = existing->top;\r\n bottom_slice->top = existing->bottom;\r\n \r\n if (top_slice->height() > 0 && top_slice->width() > 0) {\r\n queue.insert_at(queue.size(), top_slice);\r\n }\r\n \r\n if (bottom_slice->height() > 0 && bottom_slice->width() > 0) {\r\n queue.insert_at(queue.size(), bottom_slice);\r\n }\r\n \r\n discard = true;\r\n continue;\r\n } else if () \/\/ Same for vertical vs horizontal cross intersection\r\n {\r\n }\r\n } \/\/ End of intersecting test\r\n \r\n } \/\/ End loop\r\n if (discard) {\r\n queue.remove_at(j);\r\n } else {\r\n if (isHuge(candidate)) {\r\n _disableDirtyRects = true;\r\n return getFallback();\r\n }\r\n ret.insert_at(ret.size(), candidate);\r\n j++;\r\n }\r\n } \/\/ End loop\r\n \r\n return ret;\r\n}\r\n \r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"In our last post we were talking about the dirty rect system. The simplest implementation uses a single rectangle; it can save us quite some unnecessary blitting already, but there is some dangers to be taken into account that could spoil our grand plan. For example, what happens if a character is moving in the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-75","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/posts\/75","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/comments?post=75"}],"version-history":[{"count":2,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/posts\/75\/revisions"}],"predecessor-version":[{"id":78,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/posts\/75\/revisions\/78"}],"wp:attachment":[{"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/media?parent=75"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/categories?post=75"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/tags?post=75"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}