I don't think this should be committed so late in the release cycle, but the work others have been doing with point checking functions inspired me to move on this, and I wanted to let folks know what I'm thinking about and get some feedback. Consider it a proof of concept for now.
The problem: GdipGetRegionHRgn is expensive. Regardless of how much of the region we actually care about, we must rasterize the entire plane of that region. Currently, we rely on gdi32 to do this, which doesn't provide us with any way to ask for a smaller area. This has been a real problem for applications that work with very large, non-rectangular regions or paths.
So it seems to me, the solution will involve writing two functions, one of which is in this MR: a bounding-box calculation for regions, and rasterization. Since the result of rasterization will be short-lived, I think it should always be an array of bytes (which are effectively a bitmap but don't require bitwise operations to work with). The rasterization should be limited to a specific integer rectangle, which in the case of GdipIsVisibleRegionPoint can be 1x1 pixel. We should then be able to eliminate all internal uses of GdipGetRegionHRgn, except when we have to return an HRGN to the application.
This would also be useful for implementing anti-aliasing, as we could keep the memory usage down by only rasterizing the part we need for each scanline at a time.
My current concerns about what I've written so far: * Although it shouldn't change the behavior, I doubt it's adequately tested, even including the Mono tests. I'd like to ideally test every combine mode in a variety of cases. * This is too clever for its own good. Unfortunately, with the complexity of handling so many combine modes as well as infinities for each region being combined, I think the only available choices are "too clever for its own good" and "20 different special cases that need to be considered manually". Still, I want to make this as simple and easy to follow as possible, within its requirements.
-- v3: gdiplus: Check bounding box in GdipIsVisibleRegionPoint.
From: Esme Povirk esme@codeweavers.com
--- dlls/gdiplus/region.c | 218 +++++++++++++++++++++++++++++++++++++++++- 1 file changed, 217 insertions(+), 1 deletion(-)
diff --git a/dlls/gdiplus/region.c b/dlls/gdiplus/region.c index 9617f492a51..3034dedae76 100644 --- a/dlls/gdiplus/region.c +++ b/dlls/gdiplus/region.c @@ -17,6 +17,7 @@ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA */
+#include <assert.h> #include <stdarg.h>
#include "windef.h" @@ -1313,6 +1314,208 @@ GpStatus WINGDIPAPI GdipIsVisibleRegionRectI(GpRegion* region, INT x, INT y, INT return GdipIsVisibleRegionRect(region, (REAL)x, (REAL)y, (REAL)w, (REAL)h, graphics, res); }
+/* get_region_bounding_box + * + * Returns a box guaranteed to enclose the entire region, but not guaranteed to be minimal. + * Sets "empty" if bounding box is empty. + * Sets "infinite" if everything outside bounding box is inside the region. + * In the infinite case, the bounding box encloses all points not in the region. */ +static void get_region_bounding_box(struct region_element *element, + REAL *min_x, REAL *min_y, REAL *max_x, REAL *max_y, BOOL *empty, BOOL *infinite) +{ + REAL left_min_x, left_min_y, left_max_x, left_max_y; + BOOL left_empty, left_infinite; + REAL right_min_x, right_min_y, right_max_x, right_max_y; + BOOL right_empty, right_infinite; + /* For combine modes, we convert the mode to flags as follows to simplify the logic: + * 0x8 = point in combined region if it's in both + * 0x4 = point in combined region if it's in left and not right + * 0x2 = point in combined region if it's not in left and is in right + * 0x1 = point in combined region if it's in neither region */ + int flags; + const int combine_mode_flags[] = { + 0xa, /* CombineModeReplace - shouldn't be used */ + 0x8, /* CombineModeIntersect */ + 0xe, /* CombineModeUnion */ + 0x6, /* CombineModeXor */ + 0x4, /* CombineModeExclude */ + 0x2, /* CombineModeComplement */ + }; + + /* handle unit elements first */ + switch (element->type) + { + case RegionDataInfiniteRect: + *min_x = *min_y = *max_x = *max_y = 0.0; + *empty = TRUE; + *infinite = TRUE; + return; + case RegionDataEmptyRect: + *min_x = *min_y = *max_x = *max_y = 0.0; + *empty = TRUE; + *infinite = FALSE; + return; + case RegionDataPath: + { + GpPath *path = element->elementdata.path; + int i; + + if (path->pathdata.Count <= 1) { + *min_x = *min_y = *max_x = *max_y = 0.0; + *empty = TRUE; + *infinite = FALSE; + return; + } + + *min_x = *max_x = path->pathdata.Points[0].X; + *min_y = *max_y = path->pathdata.Points[0].Y; + *empty = FALSE; + *infinite = FALSE; + + for (i=1; i < path->pathdata.Count; i++) + { + if (path->pathdata.Points[i].X < *min_x) + *min_x = path->pathdata.Points[i].X; + else if (path->pathdata.Points[i].X > *max_x) + *max_x = path->pathdata.Points[i].X; + if (path->pathdata.Points[i].Y < *min_y) + *min_y = path->pathdata.Points[i].Y; + else if (path->pathdata.Points[i].Y > *max_y) + *max_y = path->pathdata.Points[i].Y; + } + + return; + } + case RegionDataRect: + *min_x = element->elementdata.rect.X; + *min_y = element->elementdata.rect.Y; + *max_x = element->elementdata.rect.X + element->elementdata.rect.Width; + *max_y = element->elementdata.rect.Y + element->elementdata.rect.Height; + *empty = FALSE; + *infinite = FALSE; + return; + } + + /* Should be only combine modes left */ + assert(element->type < ARRAY_SIZE(combine_mode_flags)); + + flags = combine_mode_flags[element->type]; + + get_region_bounding_box(element->elementdata.combine.left, + &left_min_x, &left_min_y, &left_max_x, &left_max_y, &left_empty, &left_infinite); + + if (left_infinite) + { + /* change our function so we can ignore the infinity */ + flags = ((flags & 0x3) << 2) | ((flags & 0xc) >> 2); + } + + if (left_empty && (flags & 0x3) == 0) { + /* no points in region regardless of right region, return empty */ + *empty = TRUE; + *infinite = FALSE; + return; + } + + if (left_empty && (flags & 0x3) == 0x3) { + /* all points in region regardless of right region, return infinite */ + *empty = TRUE; + *infinite = TRUE; + return; + } + + get_region_bounding_box(element->elementdata.combine.right, + &right_min_x, &right_min_y, &right_max_x, &right_max_y, &right_empty, &right_infinite); + + if (right_infinite) + { + /* change our function so we can ignore the infinity */ + flags = ((flags & 0x5) << 1) | ((flags & 0xa) >> 1); + } + + /* result is infinite if points in neither region are in the result */ + *infinite = (flags & 0x1); + + if (*infinite) + { + /* Again, we modify our function to ignore the infinity. + * The points we care about are the ones that are different from the outside of our box, + * not the points inside the region, so we invert the whole thing. + * From here we can assume 0x1 is not set. */ + flags ^= 0xf; + } + + if (left_empty) + { + /* We already took care of the cases where the right region doesn't matter, + * so we can just use the right bounding box. */ + *min_x = right_min_x; + *min_y = right_min_y; + *max_x = right_max_x; + *max_y = right_max_y; + *empty = right_empty; + return; + } + + if (right_empty) + { + /* With no points in right region, and infinities eliminated, we only care + * about flag 0x4, the case where a point is in left region and not right. */ + if (flags & 0x4) + { + /* We have a copy of the left region. */ + *min_x = left_min_x; + *min_y = left_min_y; + *max_x = left_max_x; + *max_y = left_max_y; + *empty = left_empty; + return; + } + /* otherwise, it's an empty (or infinite) region */ + *empty = TRUE; + return; + } + + /* From here we know 0x1 isn't set, and we know at least one flag is set. + * We can ignore flag 0x8 because we must assume that any point within the + * intersection of the bounding boxes might be within the region. */ + switch (flags & 0x6) + { + case 0x0: + /* intersection */ + *min_x = fmaxf(left_min_x, right_min_x); + *min_y = fmaxf(left_min_y, right_min_y); + *max_x = fminf(left_max_x, right_max_x); + *max_y = fminf(left_max_y, right_max_y); + *empty = *min_x > *max_x || *min_y > *max_y; + return; + case 0x2: + /* right (or complement) */ + *min_x = right_min_x; + *min_y = right_min_y; + *max_x = right_max_x; + *max_y = right_max_y; + *empty = right_empty; + return; + case 0x4: + /* left (or exclude) */ + *min_x = left_min_x; + *min_y = left_min_y; + *max_x = left_max_x; + *max_y = left_max_y; + *empty = left_empty; + return; + case 0x6: + /* union (or xor) */ + *min_x = fminf(left_min_x, right_min_x); + *min_y = fminf(left_min_y, right_min_y); + *max_x = fmaxf(left_max_x, right_max_x); + *max_y = fmaxf(left_max_y, right_max_y); + *empty = FALSE; + return; + } +} + /***************************************************************************** * GdipIsVisibleRegionPoint [GDIPLUS.@] */ @@ -1320,12 +1523,25 @@ GpStatus WINGDIPAPI GdipIsVisibleRegionPoint(GpRegion* region, REAL x, REAL y, G { HRGN hrgn; GpStatus stat; + REAL min_x, min_y, max_x, max_y; + BOOL empty, infinite;
TRACE("(%p, %.2f, %.2f, %p, %p)\n", region, x, y, graphics, res);
if(!region || !res) return InvalidParameter;
+ x = gdip_round(x); + y = gdip_round(y); + + /* Check for cases where we can skip quantization. */ + get_region_bounding_box(®ion->node, &min_x, &min_y, &max_x, &max_y, &empty, &infinite); + if (empty || x < min_x || y < min_y || x > max_x || y > max_y) + { + *res = infinite; + return Ok; + } + if((stat = GdipGetRegionHRgn(region, NULL, &hrgn)) != Ok) return stat;
@@ -1335,7 +1551,7 @@ GpStatus WINGDIPAPI GdipIsVisibleRegionPoint(GpRegion* region, REAL x, REAL y, G return Ok; }
- *res = PtInRegion(hrgn, gdip_round(x), gdip_round(y)); + *res = PtInRegion(hrgn, x, y);
DeleteObject(hrgn);
My 2 cents from a very quick look: what about a traversal function similar to `get_region_hrgn` but that only checks whether a point is inside a region, without constructing regions in most cases?
You could then have a `is_visible_path_point` function to implement the path case, similar to `get_path_hrgn`, using a bounding box as a quick way to discard points outside of it, and keep the rasterization for now for anything within it.
Then checking whether a point is within a polygon should also not be too difficult to implement in an efficient way (ie: without rasterizing at all), tho I don't know what GDI+ expects as a behavior here.
On Fri Feb 9 21:51:46 2024 +0000, Rémi Bernon wrote:
My 2 cents from a very quick look: what about a traversal function similar to `get_region_hrgn` but that only checks whether a point is inside a region, without constructing regions in most cases? You could then have a `is_visible_path_point` function to implement the path case, similar to `get_path_hrgn`, using a bounding box as a quick way to discard points outside of it, and keep the rasterization for now for anything within it. Then checking whether a point is within a polygon should also not be too difficult to implement in an efficient way (ie: without rasterizing at all), tho I don't know what GDI+ expects as a behavior here.
Doable, but it wouldn't be very efficient for cases where we need more than a 1x1 rasterization, and once we have that we may as well use it for the hit-testing (effectively a 1x1 rasterization) as well. A bounding box calculation is theoretically useful for path/region fills because it allows us to reduce the number of pixels we need to consider.
On Fri Feb 9 21:51:46 2024 +0000, Esme Povirk wrote:
Doable, but it wouldn't be very efficient for cases where we need more than a 1x1 rasterization, and once we have that we may as well use it for the hit-testing (effectively a 1x1 rasterization) as well. A bounding box calculation is theoretically useful for path/region fills because it allows us to reduce the number of pixels we need to consider.
I don't understand what you mean by 1x1 rasterization. The only case where I see rasterization being somehow complicated is for a path region, where the path is traced to convert it to a region, to decide whether a point is within it.
Every other region type, or combined region type, can decide whether a point is within it with a simple recursive traversal, the same way `get_region_hrgn` traverses the tree but without even having to compute and combine GDI regions.
Even without bounding boxes I don't think this would be very costly, and only the path tracing probably is?
Anyway, I don't know what GDI+ expects in term of logic, in the case of a path region, like does it actually expect the path to be rasterized and any point inside a pixel from the region edges to be considered inside the region even though it's mathematically outside the path? If not, and if the mathematical result is actually expected there's a very simple way to do it with standard "point in polygon" algorithm (basically only a matter of computing and counting segment intersections with every segment in the path).
The algorithm is actually defined in the FillMode documentation, as it depends on the kind of filling used: https://learn.microsoft.com/en-us/windows/win32/api/gdiplusenums/ne-gdipluse...
Bounding boxes may be useful, as an optimization, to quickly exclude points that are outside region components, and avoid useless recursive calls, but somehow I don't feel like this is the most common case. Though, doing it may be useful but I think it would be much easier to precompute and keep the bounding boxes on every node as they are created, which should be pretty easy as well and much more efficient than recomputing them.
checking whether a point is within a polygon should also not be too difficult to implement in an efficient way
A path region is not always a polygon.[^p] For example, it may have a bézier curve along the path.
a point is within a polygon should also not be too difficult to implement in an efficient way
Right, this is useful for implementing GdipIsVisibleRegionPoint *specifically*, but that's not the point of this MR.[^1] This patchset intends to introduce a generic bounding box calculation mechanism so that plenty of other HRgn-computing functions can benefit in the future. GdipIsVisibleRegionPoint is merely an example.[^e]
[^p]: Yes, technically everything is a polygon after rasterization, but this is not very useful here. [^1]: From paragraph 3-4 of the MR description: "The rasterization should be limited to a specific integer rectangle, which in the case of GdipIsVisibleRegionPoint can be 1x1 pixel. We should then be able to eliminate all internal uses of GdipGetRegionHRgn, except when we have to return an HRGN to the application. This would also be useful for implementing anti-aliasing, as we could keep the memory usage down by only rasterizing the part we need for each scanline at a time." [^e]: For 1x1 case only.
On Sat Feb 10 13:59:41 2024 +0000, Jinoh Kang wrote:
checking whether a point is within a polygon should also not be too
difficult to implement in an efficient way A path region is not always a polygon.[^p] For example, it may have a bézier curve along the path.
a point is within a polygon should also not be too difficult to
implement in an efficient way Right, this is useful for implementing GdipIsVisibleRegionPoint *specifically*, but that's not the point of this MR.[^1] This patchset intends to introduce a generic bounding box calculation mechanism so that plenty of other HRgn-computing functions can benefit in the future. GdipIsVisibleRegionPoint is merely an example.[^e] [^p]: Yes, technically everything is a polygon after rasterization, but this is not very useful here. [^1]: From paragraph 3-4 of the MR description: "The rasterization should be limited to a specific integer rectangle, which in the case of GdipIsVisibleRegionPoint can be 1x1 pixel. We should then be able to eliminate all internal uses of GdipGetRegionHRgn, except when we have to return an HRGN to the application. This would also be useful for implementing anti-aliasing, as we could keep the memory usage down by only rasterizing the part we need for each scanline at a time." [^e]: For 1x1 case only.
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.
Hi all.
I don't understand what is happening here. I suppose you merge this code if it works @madewokherd
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.
On Mon Feb 26 20:46:41 2024 +0000, Esme Povirk wrote:
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.
If we're sailing on the same boat then said gdi32 clipping optimization was not primarily an optimization.
This was primarily a bug fix and will remain as one such unless it is proven to be reasonably broken.
Which it is, but no-one noticed.
-
David Kahurani (＠kahurani) -
David Kahurani (＠ReDress)
-
Esme Povirk
-
Esme Povirk (＠madewokherd)
-
Jinoh Kang (＠iamahuman)
-
Rémi Bernon (＠rbernon)