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 SE corner of the screen and I’m moving the mouse cursor in the NW corner?
What would be the screen area to be considered “dirty” and thus redrawn?
Yu guessed it – basically, the whole screen.
Baaaaad.
This was in fact the way dirty recting was originally implemented in the WME engine for ScummVM:
void BaseRenderOSystem::addDirtyRect(const Common::Rect &rect) {
if (!_dirtyRect) {
_dirtyRect = new Common::Rect(rect);
} else {
_dirtyRect->extend(rect);
}
_dirtyRect->clip(_renderRect);
}
That’s it, one rect, extend it as needed.
We needed multiple dirty rects.
Whenever we “dirty” a screen area, we need to mark that separately.
But a simple array is probably not enough.
For example, what happens if multiple partially overlapping sprites are to be redrawn and we naively traverse the array?
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
with a single rect.
Also bad, very, very bad.
Even if unnecessary redrawing is avoided, needlessly big rect lists can be a problem.
I chose to address the issue with a special class that:
a) Takes requests for adding rects…
a’) …while doing some on-the-fly-optimizations (e.g. discarding duplicates)
b) Can spit out, upon request, an optimized version with only the necessary rectangles.
It is still in the works so this is not final code, but the basic idea is definitely there.
Have a look – code is partial and amended as usual, but you don’t want to know about all the boring housekeeping and utility methods, do you?
namespace Wintermute {
DirtyRectContainer::DirtyRectContainer() {
_disableDirtyRects = false;
_clipRect = nullptr;
}
DirtyRectContainer::~DirtyRectContainer() {
delete _clipRect;
}
void DirtyRectContainer::addDirtyRect(const Common::Rect &rect, const Common::Rect *clipRect) {
if (_clipRect == nullptr) {
_clipRect = new Common::Rect(*clipRect);
} else {
assert(clipRect->equals(*_clipRect));
}
if (target > kMaxInputRects) {
_disableDirtyRects = true;
} else if (isHuge(&rect)) { // More than 90% of the viewport
_disableDirtyRects = true;
} else if (rect.width() == 0 || rect.height() == 0) {
} else {
_rectArray.insert_at(target, tmp);
_rectArray[target]->clip(*clipRect);
}
}
Common::Array DirtyRectContainer::getOptimized() {
if (_disableDirtyRects) {
return getFallback();
}
Common::Array ret;
Common::Array queue;
for (int i = 0; i < _rectArray.size(); i++) {
queue.insert_at(queue.size(), _rectArray[i]);
}
int j = 0;
while (j < queue.size()) { Common::Rect *candidate = queue[j]; if (candidate->width() == 0 || candidate->height() == 0) {
// We have no use for this
queue.remove_at(j);
continue;
}
if (ret.size() > kMaxOutputRects) {
_disableDirtyRects = true;
return getFallback();
}
bool discard = false;
// See if it's contained or containes
for (uint i = 0; i < ret.size() && !discard; i++) { Common::Rect *existing = ret[i]; if (existing->contains(*candidate) || existing->equals(*candidate)) {
// It is already contained by an existing rect - useless!
discard = true;
continue;
}
if (candidate->contains(*(existing))) {
// Contains an existing one.
// Extend the pre-existing one and discard this.
existing->extend(*candidate);
discard = true;
continue;
}
// Okay, we now see if we have an overlapping corner and slice accordingly.
Common::Rect intersecting = existing->findIntersectingRect(*candidate);
// We have to remove intersecting and enqueue the rest
// We know that it's not a simple contained rect, we know that
// it's not a cross-shaped thing like above, we know that it's not
// a Commodore-logo type of deal (where the C is the bigger rect)
// So intersecting is either the NE, SE, SW or NW corner of candidate
if (intersecting.width() >= kMaxSplicingX &&
intersecting.height() >= kMaxSplicingY
) {
if (intersecting.top >= candidate->top &&
intersecting.left >= candidate->left &&
intersecting.bottom == candidate->bottom &&
intersecting.right == candidate->right
) { // SE case
Common::Rect *neslice = new Common::Rect(*candidate);
neslice->bottom = intersecting.top;
neslice->left = intersecting.left;
if (neslice->width() != 0 && neslice->height() != 0) {
queue.insert_at(queue.size(), neslice);
}
candidate->right = intersecting.left;
if (candidate->width() == 0) {
discard = true;
}
} else if () //SAME FOR NE
{ // ...
} else if () //SAME FOR NW
{ // ...
} else if () //SAME FOR SW
{ // ...
} else if (existing->left <= candidate->left &&
existing->right >= candidate->right &&
existing->top >= candidate->top &&
existing->bottom <= candidate->bottom) { // Cross shaped intersections
Common::Rect *top_slice = new Common::Rect(*candidate);
Common::Rect *bottom_slice = new Common::Rect(*candidate);
top_slice->bottom = existing->top;
bottom_slice->top = existing->bottom;
if (top_slice->height() > 0 && top_slice->width() > 0) {
queue.insert_at(queue.size(), top_slice);
}
if (bottom_slice->height() > 0 && bottom_slice->width() > 0) {
queue.insert_at(queue.size(), bottom_slice);
}
discard = true;
continue;
} else if () // Same for vertical vs horizontal cross intersection
{
}
} // End of intersecting test
} // End loop
if (discard) {
queue.remove_at(j);
} else {
if (isHuge(candidate)) {
_disableDirtyRects = true;
return getFallback();
}
ret.insert_at(ret.size(), candidate);
j++;
}
} // End loop
return ret;
}
}