This will later allow for optimization by limiting the area we consider to the region's bounding rectangle.
From: Esme Povirk esme@codeweavers.com
This will later allow for optimization by limiting the area we consider to the region's bounding rectangle. --- dlls/gdiplus/region.c | 253 +++++++++++++++++++++++++++++++++++------- 1 file changed, 210 insertions(+), 43 deletions(-)
diff --git a/dlls/gdiplus/region.c b/dlls/gdiplus/region.c index ebab5c0a8a8..01f85605a0b 100644 --- a/dlls/gdiplus/region.c +++ b/dlls/gdiplus/region.c @@ -104,6 +104,21 @@ typedef struct packed_point short Y; } packed_point;
+struct edge +{ + /* Represents an intersection of a path segment with a scanline */ + int x; + int y; + BOOL rising; +}; + +struct edge_list +{ + struct edge *edges; + size_t capacity; + size_t length; +}; + 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);
@@ -988,73 +1003,225 @@ GpStatus WINGDIPAPI GdipGetRegionDataSize(GpRegion *region, UINT *needed) return Ok; }
-static GpStatus get_path_hrgn(GpPath *path, GpGraphics *graphics, HRGN *hrgn) +static GpStatus edge_list_reserve(struct edge_list *edges, size_t count) { - HDC new_hdc=NULL, hdc; - GpGraphics *new_graphics=NULL; - GpStatus stat; - INT save_state; + size_t new_capacity, max_capacity; + struct edge *new_edges; + + if (count <= edges->capacity) + return Ok; + + max_capacity = ~(SIZE_T)0 / sizeof(edges->edges[0]); + if (count > max_capacity) + return OutOfMemory; + + new_capacity = max(4, edges->capacity); + while (new_capacity < count && new_capacity <= max_capacity / 2) + new_capacity *= 2; + if (new_capacity < count) + new_capacity = max_capacity; + + new_edges = realloc(edges->edges, new_capacity * sizeof(edges->edges[0])); + if (!new_edges) + return OutOfMemory; + + edges->edges = new_edges; + edges->capacity = new_capacity; + + return Ok; +} + +static const REAL RGN_ROUND_OFS = 0.03; /* arbitrary constant found by experiment to be close to native */ + +static inline INT rgn_round(REAL x) +{ + return (INT) ceilf(x - RGN_ROUND_OFS); +} + +static GpStatus line_to_edge_list(GpPointF p1, GpPointF p2, struct edge_list *edges) +{ + GpStatus stat = Ok; + int y, top_y, bottom_y; + BOOL rising = (p2.Y < p1.Y); + GpPointF top_pt, bottom_pt; + REAL dx, dy;
- if (!path->pathdata.Count) /* PathToRegion doesn't support empty paths */ + top_pt = rising ? p2 : p1; + bottom_pt = rising ? p1 : p2; + + top_y = rgn_round(top_pt.Y); + bottom_y = rgn_round(bottom_pt.Y); + + if (bottom_y == top_y) + /* No scanlines intersect this segment */ + return Ok; + + dx = bottom_pt.X - top_pt.X; + dy = bottom_pt.Y - top_pt.Y; + + stat = edge_list_reserve(edges, edges->length + (bottom_y - top_y)); + if (stat != Ok) + return stat; + + for (y = top_y; y < bottom_y && stat == Ok; y++) { - *hrgn = CreateRectRgn( 0, 0, 0, 0 ); - return *hrgn ? Ok : OutOfMemory; + REAL x = top_pt.X + (y + RGN_ROUND_OFS - top_pt.Y) * dx / dy; + + int rounded_x = rgn_round(x); + + edges->edges[edges->length].x = rounded_x; + edges->edges[edges->length].y = y; + edges->edges[edges->length].rising = rising; + edges->length++; }
- if (!graphics) + return stat; +} + +static GpStatus flat_path_to_edge_list(GpPath *path, struct edge_list *edges) +{ + GpStatus stat=Ok; + int i, subpath_start=0; + + for (i=1; i < path->pathdata.Count && stat == Ok; i++) { - hdc = new_hdc = CreateCompatibleDC(0); - if (!new_hdc) - return OutOfMemory; + BYTE type = path->pathdata.Types[i]; + + if ((type&PathPointTypePathTypeMask) == PathPointTypeStart) + subpath_start = i;
- stat = GdipCreateFromHDC(new_hdc, &new_graphics); - graphics = new_graphics; - if (stat != Ok) + if ((type&PathPointTypePathTypeMask) == PathPointTypeLine) { - DeleteDC(new_hdc); - return stat; + stat = line_to_edge_list(path->pathdata.Points[i-1], path->pathdata.Points[i], edges); + + if (stat == Ok && ((type & PathPointTypeCloseSubpath) || i == path->pathdata.Count - 1)) + stat = line_to_edge_list(path->pathdata.Points[i], path->pathdata.Points[subpath_start], edges); } } - else if (has_gdi_dc(graphics)) + + return stat; +} + +static int cmp_edges(const void *a, const void *b) +{ + const struct edge *edge1 = (struct edge*)a; + const struct edge *edge2 = (struct edge*)b; + + if (edge1->y != edge2->y) { - stat = gdi_dc_acquire(graphics, &hdc); - if (stat != Ok) - return stat; + return (edge1->y > edge2->y) - (edge1->y < edge2->y); } - else + + return (edge1->x > edge2->x) - (edge1->x < edge2->x); +} + +static GpStatus edge_list_to_rgndata(struct edge_list *edges, FillMode fill_mode, RGNDATA **rgndata) +{ + int i, start_x = 0, winding_count = 0; + BOOL in_shape = FALSE; + INT scan_count = 0; + RECT *scans, bound = {0}; + + /* sort edges */ + qsort(edges->edges, edges->length, sizeof(edges->edges[0]), cmp_edges); + + /* allocate rgndata */ + *rgndata = malloc(sizeof(RGNDATAHEADER) + sizeof(RECT) * edges->length / 2); + if (!*rgndata) + return OutOfMemory; + + scans = (RECT*)&(*rgndata)->Buffer; + + /* translate edges into scans based on winding mode */ + for (i=0; i < edges->length; i++) { - graphics->hdc = hdc = new_hdc = CreateCompatibleDC(0); - if (!new_hdc) - return OutOfMemory; + BOOL new_in_shape; + + winding_count += edges->edges[i].rising ? 1 : -1; + + /* check all edges at this point before starting/ending a scan */ + if (i + 1 < edges->length && + edges->edges[i+1].x == edges->edges[i].x && edges->edges[i+1].y == edges->edges[i].y) + continue; + + new_in_shape = (fill_mode == FillModeWinding) ? (winding_count != 0) : ((winding_count & 1) == 1); + + if (new_in_shape == in_shape) + continue; + + in_shape = new_in_shape; + + if (in_shape) + { + start_x = edges->edges[i].x; + } + else + { + scans[scan_count].left = start_x; + scans[scan_count].right = edges->edges[i].x; + scans[scan_count].top = edges->edges[i].y; + scans[scan_count].bottom = edges->edges[i].y+1; + UnionRect(&bound, &bound, &scans[scan_count]); + scan_count++; + } }
- save_state = SaveDC(hdc); - EndPath(hdc); + (*rgndata)->rdh.dwSize = sizeof(RGNDATAHEADER); + (*rgndata)->rdh.iType = RDH_RECTANGLES; + (*rgndata)->rdh.nCount = scan_count; + (*rgndata)->rdh.nRgnSize = scan_count * sizeof(RECT); + (*rgndata)->rdh.rcBound = bound;
- SetPolyFillMode(hdc, (path->fill == FillModeAlternate ? ALTERNATE : WINDING)); + return Ok; +}
- gdi_transform_acquire(graphics); +static GpStatus get_path_hrgn(GpPath *path, GpGraphics *graphics, HRGN *hrgn) +{ + GpStatus stat = Ok; + GpMatrix *graphics_transform = NULL, matrix; + GpPath *transformed_path = NULL; + struct edge_list edge_list = { 0 }; + RGNDATA *rgndata = NULL;
- stat = trace_path(graphics, path); - if (stat == Ok) + if (!path->pathdata.Count) { - *hrgn = PathToRegion(hdc); - stat = *hrgn ? Ok : OutOfMemory; + *hrgn = CreateRectRgn( 0, 0, 0, 0 ); + return *hrgn ? Ok : OutOfMemory; + } + + /* transform path by graphics transform if necessary */ + if (graphics) + { + stat = get_graphics_transform(graphics, WineCoordinateSpaceGdiDevice, CoordinateSpaceWorld, &matrix); + graphics_transform = &matrix; }
- gdi_transform_release(graphics); + if (stat == Ok) + stat = GdipClonePath(path, &transformed_path); + + if (stat == Ok) + stat = GdipFlattenPath(transformed_path, graphics_transform, FlatnessDefault); + + /* build edge list */ + if (stat == Ok) + stat = flat_path_to_edge_list(transformed_path, &edge_list); + + /* transform edge list into scans list */ + if (stat == Ok) + stat = edge_list_to_rgndata(&edge_list, path->fill, &rgndata);
- RestoreDC(hdc, save_state); - if (new_hdc) + /* transform scans list into hrgn */ + if (stat == Ok) { - DeleteDC(new_hdc); - if (new_graphics) - GdipDeleteGraphics(new_graphics); - else - graphics->hdc = NULL; + *hrgn = ExtCreateRegion(NULL, rgndata->rdh.dwSize + rgndata->rdh.nRgnSize, rgndata); + stat = *hrgn ? Ok : OutOfMemory; } - else - gdi_dc_release(graphics, hdc); + + free(edge_list.edges); + free(rgndata); + + if (transformed_path != NULL) + GdipDeletePath(transformed_path);
return stat; }
From: Esme Povirk esme@codeweavers.com
--- dlls/gdiplus/tests/region.c | 126 ++++++++++++++++++++++++++++++++++++ 1 file changed, 126 insertions(+)
diff --git a/dlls/gdiplus/tests/region.c b/dlls/gdiplus/tests/region.c index 93c6c53ebc1..ed4ecbc2e7e 100644 --- a/dlls/gdiplus/tests/region.c +++ b/dlls/gdiplus/tests/region.c @@ -2570,6 +2570,131 @@ static void test_incombinedregion(void) } }
+static void test_rounding(void) +{ + GpRegion *region; + GpMatrix *matrix; + GpBitmap *bitmap; + GpGraphics *graphics; + GpBrush *brush; + GpStatus status; + UINT count=80085; + INT icount; + GpRectF scans[2]; + HRGN hrgn; + int i, x, y, min_x, min_y, max_x, max_y; + ARGB color; + const struct { + GpRectF region_rect; + GpRectF scan_rect; + RECT hrgn_rect; + GpRect fill_rect; + } td[] = { + { + { 1.1, 2.1, 3.85, 4.85 }, + { 2, 3, 3, 4 }, + { 2, 3, 5, 7 }, + { 2, 3, 3, 4 } + }, + { + { 1, 1, 1.5, 1.5 }, + { 1, 1, 2, 2 }, + { 1, 1, 3, 3 }, + { 1, 1, 2, 2 } + }, + { + { 1.01, 1.01, 1.5, 1.5 }, + { 1, 1, 2, 2 }, + { 1, 1, 3, 3 }, + { 1, 1, 2, 2 } + }, + { + { 1.5, 1.5, 1.5, 1.5 }, + { 2, 2, 1, 1 }, + { 2, 2, 3, 3 }, + { 2, 2, 1, 1 } + } + }; + + status = GdipCreateRegion(®ion); + expect(Ok, status); + + status = GdipCreateMatrix(&matrix); + expect(Ok, status); + + status = GdipCreateBitmapFromScan0(10, 10, 0, PixelFormat32bppARGB, NULL, &bitmap); + expect(Ok, status); + + status = GdipGetImageGraphicsContext((GpImage*)bitmap, &graphics); + expect(Ok, status); + + status = GdipCreateSolidFill(0xffffffff, (GpSolidFill**)&brush); + expect(Ok, status); + + for (i = 0; i < ARRAY_SIZE(td); i++) + { + winetest_push_context("%i", i); + + status = GdipCombineRegionRect(region, &td[i].region_rect, CombineModeReplace); + expect(Ok, status); + + status = GdipGetRegionScansCount(region, &count, matrix); + expect(Ok, status); + expect(1, count); + + status = GdipGetRegionScans(region, scans, &icount, matrix); + expect(Ok, status); + expect(1, icount); + expectf(td[i].scan_rect.X, scans[0].X); + expectf(td[i].scan_rect.Y, scans[0].Y); + expectf(td[i].scan_rect.Width, scans[0].Width); + expectf(td[i].scan_rect.Height, scans[0].Height); + + status = GdipGetRegionHRgn(region, NULL, &hrgn); + expect(Ok, status); + + verify_region(hrgn, &td[i].hrgn_rect); + + DeleteObject(hrgn); + + status = GdipGraphicsClear(graphics, 0); + expect(Ok, status); + + status = GdipFillRegion(graphics, brush, region); + expect(Ok, status); + + min_x = min_y = 10; + max_x = max_y = -1; + + for (x = 0; x < 10; x++) + for (y = 0; y < 10; y++) + { + status = GdipBitmapGetPixel(bitmap, x, y, &color); + expect(Ok, status); + + if (color) { + min_x = min(min_x, x); + min_y = min(min_y, y); + max_x = max(min_x, x); + max_y = max(min_y, y); + } + } + + expect(td[i].fill_rect.X, min_x); + expect(td[i].fill_rect.Y, min_y); + expect(td[i].fill_rect.Width, max_x - min_x + 1); + expect(td[i].fill_rect.Height, max_y - min_y + 1); + + winetest_pop_context(); + } + + GdipDeleteBrush(brush); + GdipDeleteGraphics(graphics); + GdipDisposeImage((GpImage*)bitmap); + GdipDeleteRegion(region); + GdipDeleteMatrix(matrix); +} + START_TEST(region) { struct GdiplusStartupInput gdiplusStartupInput; @@ -2605,6 +2730,7 @@ START_TEST(region) test_excludeinfinite(); test_GdipCreateRegionRgnData(); test_incombinedregion(); + test_rounding();
GdiplusShutdown(gdiplusToken); }
Would also request review from @gang65 if I could.
Bartosz Kosiorek (@gang65) commented about dlls/gdiplus/region.c:
- scans = (RECT*)&(*rgndata)->Buffer;
- /* translate edges into scans based on winding mode */
- for (i=0; i < edges->length; i++) {
graphics->hdc = hdc = new_hdc = CreateCompatibleDC(0);
if (!new_hdc)
return OutOfMemory;
BOOL new_in_shape;
winding_count += edges->edges[i].rising ? 1 : -1;
/* check all edges at this point before starting/ending a scan */
if (i + 1 < edges->length &&
edges->edges[i+1].x == edges->edges[i].x && edges->edges[i+1].y == edges->edges[i].y)
It would be great to use the same formatting in whole PR ```suggestion:-0+0 edges->edges[i + 1].x == edges->edges[i].x && edges->edges[i + 1].y == edges->edges[i].y) ``` There are more places with inconsistent formatting.
Bartosz Kosiorek (@gang65) commented about dlls/gdiplus/region.c:
short Y;
} packed_point;
+struct edge +{
- /* Represents an intersection of a path segment with a scanline */
- int x;
- int y;
Should we use INT? ```suggestion:-0+0 INT y; ```
Bartosz Kosiorek (@gang65) commented about dlls/gdiplus/region.c:
int rounded_x = rgn_round(x);
edges->edges[edges->length].x = rounded_x;
edges->edges[edges->length].y = y;
edges->edges[edges->length].rising = rising;
}edges->length++;
- if (!graphics)
- return stat;
+}
+static GpStatus flat_path_to_edge_list(GpPath *path, struct edge_list *edges) +{
- GpStatus stat=Ok;
- int i, subpath_start=0;
```suggestion:-0+0 INT i, subpath_start = 0; ```
Bartosz Kosiorek (@gang65) commented about dlls/gdiplus/region.c:
- int i, subpath_start=0;
- for (i=1; i < path->pathdata.Count && stat == Ok; i++) {
hdc = new_hdc = CreateCompatibleDC(0);
if (!new_hdc)
return OutOfMemory;
BYTE type = path->pathdata.Types[i];
if ((type&PathPointTypePathTypeMask) == PathPointTypeStart)
subpath_start = i;
stat = GdipCreateFromHDC(new_hdc, &new_graphics);
graphics = new_graphics;
if (stat != Ok)
if ((type&PathPointTypePathTypeMask) == PathPointTypeLine)
```suggestion:-0+0 if ((type & PathPointTypePathTypeMask) == PathPointTypeLine) ``` as it is in line: 1097
Bartosz Kosiorek (@gang65) commented about dlls/gdiplus/region.c:
- if (edge1->y != edge2->y) {
stat = gdi_dc_acquire(graphics, &hdc);
if (stat != Ok)
return stat;
}return (edge1->y > edge2->y) - (edge1->y < edge2->y);
- else
- return (edge1->x > edge2->x) - (edge1->x < edge2->x);
+}
+static GpStatus edge_list_to_rgndata(struct edge_list *edges, FillMode fill_mode, RGNDATA **rgndata) +{
- int i, start_x = 0, winding_count = 0;
```suggestion:-0+0 INT i, start_x = 0, winding_count = 0; ```
Bartosz Kosiorek (@gang65) commented about dlls/gdiplus/tests/region.c:
}
}
+static void test_rounding(void) +{
- GpRegion *region;
- GpMatrix *matrix;
- GpBitmap *bitmap;
- GpGraphics *graphics;
- GpBrush *brush;
- GpStatus status;
- UINT count=80085;
- INT icount;
- GpRectF scans[2];
- HRGN hrgn;
- int i, x, y, min_x, min_y, max_x, max_y;
```suggestion:-0+0 INT i, x, y, min_x, min_y, max_x, max_y; ```
Bartosz Kosiorek (@gang65) commented about dlls/gdiplus/tests/region.c:
expect(Ok, status);
min_x = min_y = 10;
max_x = max_y = -1;
for (x = 0; x < 10; x++)
for (y = 0; y < 10; y++)
{
status = GdipBitmapGetPixel(bitmap, x, y, &color);
expect(Ok, status);
if (color) {
min_x = min(min_x, x);
min_y = min(min_y, y);
max_x = max(min_x, x);
max_y = max(min_y, y);
Why we are not checking colours? I guess that `min_x` colour will be 0, and max_x will be 9.
Bartosz Kosiorek (@gang65) commented about dlls/gdiplus/tests/region.c:
}
}
+static void test_rounding(void) +{
- GpRegion *region;
- GpMatrix *matrix;
- GpBitmap *bitmap;
- GpGraphics *graphics;
- GpBrush *brush;
- GpStatus status;
- UINT count=80085;
```suggestion:-0+0 UINT count = 80085; ```
Bartosz Kosiorek (@gang65) commented about dlls/gdiplus/region.c:
{ case CombineModeIntersect: return get_region_hrgn(element->elementdata.combine.right, graphics, hrgn); case CombineModeXor: case CombineModeExclude:
I know that you have not touched this code, but the `case` formatting is really weird compared to the rest of the code. ```suggestion:-0+0 case CombineModeXor: case CombineModeExclude: ```
Was this taken from win32u mostly? I wouldn't bother with mentioned cosmetic changes, for example I see no reason to prefer INT over int.
On Tue Mar 25 20:19:46 2025 +0000, Bartosz Kosiorek wrote:
Should we use INT?
INT y;
It's not the equivalent of any INT passed in to an API, so I don't see a reason to use INT.
On Tue Mar 25 20:44:30 2025 +0000, Bartosz Kosiorek wrote:
Why we are not checking colours? I guess that `min_x` colour will be 0, and max_x will be 9.
We are checking if color is zero (fully transparent, the value we cleared the image to) or non-zero, to figure out where the shape was drawn. I'm assuming (not checking) that it's a rectangle and the min/max x and y drawn correspond to the corners.
On Mon Mar 31 18:52:09 2025 +0000, Nikolay Sivov wrote:
Was this taken from win32u mostly? I wouldn't bother with mentioned cosmetic changes, for example I see no reason to prefer INT over int.
It was written mostly from scratch. From what I remember from when the polygon fill code was in gdi32, that version sorts all the line segments by where they intersect the current scanline as it goes. I guess it uses less memory, but I didn't really see the point of that.
On Mon Mar 31 18:52:09 2025 +0000, Esme Povirk wrote:
It was written mostly from scratch. From what I remember from when the polygon fill code was in gdi32, that version sorts all the line segments by where they intersect the current scanline as it goes. I guess it uses less memory, but I didn't really see the point of that.
That's the reason I want careful review - it's basically a rewrite from scratch of a core part of gdiplus's rendering.
On Mon Mar 31 18:55:18 2025 +0000, Esme Povirk wrote:
That's the reason I want careful review - it's basically a rewrite from scratch of a core part of gdiplus's rendering.
Ok, in this case I need to look closely to understand it. Do you think we have sufficient amount of tests for this?
On Mon Mar 31 19:46:14 2025 +0000, Nikolay Sivov wrote:
Ok, in this case I need to look closely to understand it. Do you think we have sufficient amount of tests for this?
Between the Wine test suite and a manual rendering test program I used (which did identify an issue), yes.
I guess I should also run the System.Drawing tests with this, though I'm not sure if it has much that'd be applicable.
On Tue Apr 1 17:49:16 2025 +0000, Esme Povirk wrote:
Between the Wine test suite and a manual rendering test program I used (which did identify an issue), yes. I guess I should also run the System.Drawing tests with this, though I'm not sure if it has much that'd be applicable.
OK, no new failures in System.Drawing.
This merge request was approved by Nikolay Sivov.
I do see the same image.c failures on Windows that CI reported. Only happens with 32bit build, and I don't see how it could be related.
On Tue Apr 8 16:08:10 2025 +0000, Nikolay Sivov wrote:
I do see the same image.c failures on Windows that CI reported. Only happens with 32bit build, and I don't see how it could be related.
I think it may have been fixed separately? I can try a rebase and see if that helps.
On Tue Apr 8 16:08:10 2025 +0000, Esme Povirk wrote:
I think it may have been fixed separately? I can try a rebase and see if that helps.
Fixed with what? I tried locally with and without this mr.
On Tue Apr 8 16:09:38 2025 +0000, Nikolay Sivov wrote:
Fixed with what? I tried locally with and without this mr.
Never mind, I thought maybe it was working on the master branch.
I'll look into it, it's my area regardless.
On Tue Apr 8 16:15:13 2025 +0000, Esme Povirk wrote:
Never mind, I thought maybe it was working on the master branch. I'll look into it, it's my area regardless.
I don't see those failures on test.winehq.org or CI on the master branch.
I'll try to reproduce it locally with this patchset rebased, I guess.
On Tue Apr 8 16:37:21 2025 +0000, Esme Povirk wrote:
I don't see those failures on test.winehq.org or CI on the master branch. I'll try to reproduce it locally with this patchset rebased, I guess.
Making test data array 'td' static "fixes" it for me.