RTree coalesces rectangles too eagerly #116070
Description
RTree::searchNonOverlappingDrawnRects will union any rectangles that so much as touch each other:
rtree1.mov
This has some negative implications: We think that the platform view is covered, even though there's no actual content above it. That means overlay surface is used even in case where it doesn't need to be.
I tried the following implementation that uses SkRegion instead :
std::list<SkRect> RTree::searchNonOverlappingDrawnRects(
const SkRect& query) const {
std::list<SkRect> res;
SkRegion region;
for (const auto& p : draw_op_) {
region.op(p.second.roundOut(), SkRegion::kUnion_Op);
}
SkRegion::Cliperator iterator(region, query.roundOut());
// Vertically deband cliperator rectangles.
while (!iterator.done()) {
auto rect = SkRect::Make(iterator.rect());
auto iter = res.end();
// If there is recangle previously in rect on which this one is a vertical
// continuation, remove the previous rectangle and expand this one
// vertically to cover the area.
while (iter != res.begin()) {
--iter;
if (iter->bottom() < rect.top()) {
// Went too far.
break;
} else if (iter->bottom() == rect.top() && iter->left() == rect.left() &&
iter->right() == rect.right()) {
rect.fTop = iter->fTop;
res.erase(iter);
break;
}
}
res.push_back(rect);
iterator.next();
}
return res;
}rtree2.mov
Engine branch: https://github.com/knopp/engine/tree/macos_platform_views
Test project: https://github.com/knopp/layer_playground
I'm wondering if we could use something like this instead.