$ Spatial indexes
Rectangle list
O(n³)fn compute_extra_draws() {
for full_redraw_rect in rects_to_fully_redraw.iter() {
for elem in compositor_state.elements.iter() {
for visible_region in elem.drawable_rects().iter() {
if visible_region.intersects_with(full_redraw_rect) {
let intersection = visible_region
.area_overlapping_with(full_redraw_rect)
.unwrap();
compositor_state.queue_extra_draw(elem, intersection);
}
}
}
}
}R-tree
O(n log n)fn compute_extra_draws() {
for full_redraw_rect in rects_to_fully_redraw.iter() {
let nearby_regions = spatial_index.query(full_redraw_rect);
for (elem, visible_region) in nearby_regions.iter() {
let intersection = visible_region
.area_overlapping_with(full_redraw_rect)
.unwrap();
compositor_state.queue_extra_draw(elem, intersection);
}
}
}- 5 elements 9x speedup
- 10 elements 18x speedup
- 20 elements (typical) 37x speedup