aboutsummaryrefslogtreecommitdiff
path: root/render/vulkan
diff options
context:
space:
mode:
authorManuel Stoeckl <code@mstoeckl.com>2023-10-01 16:25:39 -0400
committerSimon Ser <contact@emersion.fr>2023-10-05 11:45:32 +0000
commitd180f4d9b3fab72ff1bad881c91b004c905299c3 (patch)
tree0db65ca8def31d644852826ea4b9000eb6697264 /render/vulkan
parentd817ebb80f8b0f1a27152104525d4b5a8c38e56d (diff)
util: add struct to track union of rectangles
The new struct rect_union is designed to make it easier to efficiently accumulate a list of rectangles, and then operate on an exact cover of their union. Using rect_union, the times needed to added t rectangles, and then compute their exact cover will be O(t), and something between Ω(t) and O(t^2), depending on the rectangle arrangement. If one tries to do the same by storing a pixman_region32_t and updating it with pixman_region32_union_rect(), then total time needed would be between Ω(t^2) and O(t^3), depending on the input. Without changing the public API (data structure + rectangle ordering rules) for pixman_region32_t, it is impossible to improve its worst case time.
Diffstat (limited to 'render/vulkan')
0 files changed, 0 insertions, 0 deletions