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