[PATCH v2 0/2] MR7654: gdiplus: Implement path to region conversion without gdi32.

[Esme Povirk (＠madewokherd)]

This will later allow for optimization by limiting the area we
consider to the region's bounding rectangle.

--
  v2: gdiplus/tests: Test rounding of region rectangles.
      gdiplus: Implement path to region conversion without gdi32.

https://gitlab.winehq.org/wine/wine/-/merge_requests/7654

[PATCH v2 1/2] gdiplus: Implement path to region conversion without gdi32.

[Esme Povirk]

From: Esme Povirk

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;
 }

[PATCH v2 2/2] gdiplus/tests: Test rounding of region rectangles.

[Esme Povirk]

From: Esme Povirk

---
 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..d6550b7d035 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;
+    static 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(&region);
+    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);
 }

[Esme Povirk (＠madewokherd)]

On Tue Apr  8 16:49:44 2025 +0000, Nikolay Sivov wrote:
> Making test data array 'td' static "fixes" it for me.

Thanks, it does here too. Marking it static makes sense to me (even if it's not clear to me why it would cause this), so I rebased with that change.

[PATCH v2 0/2] MR7654: gdiplus: Implement path to region conversion without gdi32. - approved

[Nikolay Sivov (＠nsivov)]

This merge request was approved by Nikolay Sivov.