Module: wine Branch: master Commit: 7da5dff88ce6d1cb77e855bf91697252f703c12f URL: https://gitlab.winehq.org/wine/wine/-/commit/7da5dff88ce6d1cb77e855bf9169725...
Author: Fabian Maurer dark.shadow4@web.de Date: Mon Jul 24 16:47:55 2023 +0200
gdiplus: Make flatten_bezier_add iterative.
---
dlls/gdiplus/graphicspath.c | 139 ++++++++++++++++++++++++++++++-------------- 1 file changed, 94 insertions(+), 45 deletions(-)
diff --git a/dlls/gdiplus/graphicspath.c b/dlls/gdiplus/graphicspath.c index 6cdc2a58059..06e17d4b98a 100644 --- a/dlls/gdiplus/graphicspath.c +++ b/dlls/gdiplus/graphicspath.c @@ -103,6 +103,28 @@ static INT path_list_count(path_list_node_t *node) return count; }
+struct flatten_bezier_job +{ + path_list_node_t *start; + REAL x2; + REAL y2; + REAL x3; + REAL y3; + path_list_node_t *end; + struct list entry; +}; + +static BOOL flatten_bezier_add(struct list *jobs, path_list_node_t *start, REAL x2, REAL y2, REAL x3, REAL y3, path_list_node_t *end) +{ + struct flatten_bezier_job *job = malloc(sizeof(struct flatten_bezier_job)); + struct flatten_bezier_job temp = { start, x2, y2, x3, y3, end }; + if (!job) + return FALSE; + *job = temp; + list_add_after(jobs, &job->entry); + return TRUE; +} + /* GdipFlattenPath helper */ /* * Used to recursively flatten single Bezier curve @@ -128,55 +150,82 @@ static BOOL flatten_bezier(path_list_node_t *start, REAL x2, REAL y2, REAL x3, R GpPointF pt, pt_st; path_list_node_t *node; REAL area_triangle, distance_start_end; + BOOL ret = TRUE; + struct list jobs; + struct flatten_bezier_job *current, *next; + + list_init( &jobs ); + flatten_bezier_add(&jobs, start, x2, y2, x3, y3, end); + LIST_FOR_EACH_ENTRY( current, &jobs, struct flatten_bezier_job, entry ) + { + start = current->start; + x2 = current->x2; + y2 = current->y2; + x3 = current->x3; + y3 = current->y3; + end = current->end; + + /* middle point between control points */ + pt.X = (x2 + x3) / 2.0; + pt.Y = (y2 + y3) / 2.0; + + /* calculate bezier curve middle points == new control points */ + mp[0].X = (start->pt.X + x2) / 2.0; + mp[0].Y = (start->pt.Y + y2) / 2.0; + mp[1].X = (mp[0].X + pt.X) / 2.0; + mp[1].Y = (mp[0].Y + pt.Y) / 2.0; + mp[4].X = (end->pt.X + x3) / 2.0; + mp[4].Y = (end->pt.Y + y3) / 2.0; + mp[3].X = (mp[4].X + pt.X) / 2.0; + mp[3].Y = (mp[4].Y + pt.Y) / 2.0; + + /* middle point between new control points */ + mp[2].X = (mp[1].X + mp[3].X) / 2.0; + mp[2].Y = (mp[1].Y + mp[3].Y) / 2.0; + + /* Is one pair of the new control points equal to the old control points? */ + if ((x2 == mp[0].X && y2 == mp[0].Y && x3 == mp[1].X && y3 == mp[1].Y) || + (x2 == mp[3].X && y2 == mp[3].Y && x3 == mp[4].X && y3 == mp[4].Y)) + continue; + + pt = end->pt; + pt_st = start->pt; + + /* check flatness as a half of distance between middle point and a linearized path + * formula for distance point from line for point (x0, y0) and line (x1, y1) (x2, y2) + * is defined as (area_triangle / distance_start_end): + * | (x2 - x1) * (y1 - y0) - (x1 - x0) * (y2 - y1) / sqrt( (x2 - x1)^2 + (y2 - y1)^2 ) | + * Here rearranged to avoid division and simplified: + * x0(y2 - y1) + y0(x1 - x2) + (x2*y1 - x1*y2) + */ + area_triangle = (pt.Y - pt_st.Y)*mp[2].X + (pt_st.X - pt.X)*mp[2].Y + (pt_st.Y*pt.X - pt_st.X*pt.Y); + distance_start_end = sqrtf(powf(pt.Y - pt_st.Y, 2.0) + powf(pt_st.X - pt.X, 2.0)); + if(fabs(area_triangle) <= (0.5 * flatness * distance_start_end)){ + continue; + } + else + /* add a middle point */ + if(!(node = add_path_list_node(start, mp[2].X, mp[2].Y, PathPointTypeLine))) + { + ret = FALSE; + break; + };
- /* middle point between control points */ - pt.X = (x2 + x3) / 2.0; - pt.Y = (y2 + y3) / 2.0; - - /* calculate bezier curve middle points == new control points */ - mp[0].X = (start->pt.X + x2) / 2.0; - mp[0].Y = (start->pt.Y + y2) / 2.0; - mp[1].X = (mp[0].X + pt.X) / 2.0; - mp[1].Y = (mp[0].Y + pt.Y) / 2.0; - mp[4].X = (end->pt.X + x3) / 2.0; - mp[4].Y = (end->pt.Y + y3) / 2.0; - mp[3].X = (mp[4].X + pt.X) / 2.0; - mp[3].Y = (mp[4].Y + pt.Y) / 2.0; - - /* middle point between new control points */ - mp[2].X = (mp[1].X + mp[3].X) / 2.0; - mp[2].Y = (mp[1].Y + mp[3].Y) / 2.0; - - /* Is one pair of the new control points equal to the old control points? */ - if ((x2 == mp[0].X && y2 == mp[0].Y && x3 == mp[1].X && y3 == mp[1].Y) || - (x2 == mp[3].X && y2 == mp[3].Y && x3 == mp[4].X && y3 == mp[4].Y)) - return TRUE; - - pt = end->pt; - pt_st = start->pt; - - /* check flatness as a half of distance between middle point and a linearized path - * formula for distance point from line for point (x0, y0) and line (x1, y1) (x2, y2) - * is defined as (area_triangle / distance_start_end): - * | (x2 - x1) * (y1 - y0) - (x1 - x0) * (y2 - y1) / sqrt( (x2 - x1)^2 + (y2 - y1)^2 ) | - * Here rearranged to avoid division and simplified: - * x0(y2 - y1) + y0(x1 - x2) + (x2*y1 - x1*y2) - */ - area_triangle = (pt.Y - pt_st.Y)*mp[2].X + (pt_st.X - pt.X)*mp[2].Y + (pt_st.Y*pt.X - pt_st.X*pt.Y); - distance_start_end = sqrtf(powf(pt.Y - pt_st.Y, 2.0) + powf(pt_st.X - pt.X, 2.0)); - if(fabs(area_triangle) <= (0.5 * flatness * distance_start_end)){ - return TRUE; + /* do the same with halves */ + if (!flatten_bezier_add(¤t->entry, node, mp[3].X, mp[3].Y, mp[4].X, mp[4].Y, end)) + break; + if (!flatten_bezier_add(¤t->entry, start, mp[0].X, mp[0].Y, mp[1].X, mp[1].Y, node)) + break; } - else - /* add a middle point */ - if(!(node = add_path_list_node(start, mp[2].X, mp[2].Y, PathPointTypeLine))) - return FALSE;
- /* do the same with halves */ - flatten_bezier(start, mp[0].X, mp[0].Y, mp[1].X, mp[1].Y, node, flatness); - flatten_bezier(node, mp[3].X, mp[3].Y, mp[4].X, mp[4].Y, end, flatness); + /* Cleanup */ + LIST_FOR_EACH_ENTRY_SAFE( current, next, &jobs, struct flatten_bezier_job, entry ) + { + list_remove(¤t->entry); + free(current); + }
- return TRUE; + return ret; }
/* GdipAddPath* helper