On Sat Feb 10 14:09:38 2024 +0000, Esme Povirk wrote:
I think my reasoning for not precomputing bounding boxes was that in practice we'll likely be transforming the regions a lot, which will require recomputing them, so it's not clear to me whether precomputing would really be more efficient or not. The case where we fall down now in particular (as I mentioned in the MR description) is working with a very large path region that doesn't have perfectly vertical edges. This gets converted into many rectangles with small height that are unnecessary when point-testing or rendering to e.g. a window with finite size. We could do this more efficiently by only handling the points that will be in the final output. But I am reconsidering now whether it's worth doing a bounding box calculation separately from the conversion to a list of rectangles. Maybe the way to do this is to reimplement GdipGetRegionScans first, and do it in a way that tracks intersections as it goes. Then GdipIsVisibleRegionPoint can be implemented by intersecting a 1x1 rectangle with the region I want to point-test and converting that to scans. It would be simpler. The drawbacks of that approach are:
- It's sensitive to the order in which regions are combined. A large
region intersected with a small one will be slower than a small region intersected with a large one. We can try to set up our internal usage so that single points, Graphics bounding boxes, and Graphics clipping regions are first, but in some cases it won't be as efficient with large curvy regions as it could be.
- It'll use more memory. For paths I'll need 1 byte for each pixel in
the output to track where the polygon's edges are, and I'll need memory for every rectangle in the result. It won't be possible to "stream" the result to the function using it, which if it's a rendering function will be building one scanline at a time.
- Cases involving xor, exclude, or complement with multiple infinities
won't be handled as efficiently as they could be. It's unlikely that those will show up in practice though.
It occurred to me in discussing https://gitlab.winehq.org/wine/wine/-/merge_requests/5152 that we could take advantage of gdi32's clipping optimization by drawing to a DIB, and using the DIB as a representation of which pixels are in a region. But we'd have to specifically use `PolyPolygon` to do the drawing. (Or, maybe it'd be better to update other gdi32 drawing functions so they can use the optimization, and we can keep using `draw_poly`?)
Also, I tried doing the bounding box calculation at the same time as the region conversion, and having to worry about combining regions with different bounding boxes made things way more complicated. I believe working that out separately is worth it just to keep things simpler.
The plan I'm now favoring is: * Merge this basically as-is. * Reimplement `brush_fill_path` and `GDI32_GdipFillPath` based on `PolyPolygon`, so that gdi32 will use the clipping optimization (this also gets us code that converts to a point list for PolyPolygon which we can reuse later). * Write tests for exactly where the pixel boundaries are with rectangular regions so we can make sure get_region_bounding_box is precise in that situation. * Write a function that takes a boundary rectangle and a region, and returns a black & white DIB representing the region's intersection with the rectangle (can skip generating the DIB in some trivial cases). We'll replace `GdipGetRegionHRgn` with that. At that point, `GdipIsVisibleRegionPoint` can skip the boundary box calculation and just use that with a 1x1 rectangle.