[PATCH 0/2] MR3394: gdiplus: Make flatten_bezier iterative
Recursive code is pretty hard to debug, so I do think this makes sense. -- https://gitlab.winehq.org/wine/wine/-/merge_requests/3394
From: Fabian Maurer <dark.shadow4(a)web.de> --- dlls/gdiplus/graphicspath.c | 84 ++++++++++++++++++------------------- 1 file changed, 42 insertions(+), 42 deletions(-) diff --git a/dlls/gdiplus/graphicspath.c b/dlls/gdiplus/graphicspath.c index 6cdc2a58059..6258c372d99 100644 --- a/dlls/gdiplus/graphicspath.c +++ b/dlls/gdiplus/graphicspath.c @@ -129,48 +129,48 @@ static BOOL flatten_bezier(path_list_node_t *start, REAL x2, REAL y2, REAL x3, R path_list_node_t *node; REAL area_triangle, distance_start_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)) - 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; - } - else - /* add a middle point */ - if(!(node = add_path_list_node(start, mp[2].X, mp[2].Y, PathPointTypeLine))) - return FALSE; + /* 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; + } + 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); -- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/3394
From: Fabian Maurer <dark.shadow4(a)web.de> --- dlls/gdiplus/graphicspath.c | 63 ++++++++++++++++++++++++++++++++----- 1 file changed, 56 insertions(+), 7 deletions(-) diff --git a/dlls/gdiplus/graphicspath.c b/dlls/gdiplus/graphicspath.c index 6258c372d99..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,6 +150,20 @@ 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; @@ -150,7 +186,7 @@ static BOOL flatten_bezier(path_list_node_t *start, REAL x2, REAL y2, REAL x3, R /* 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; + continue; pt = end->pt; pt_st = start->pt; @@ -165,18 +201,31 @@ static BOOL flatten_bezier(path_list_node_t *start, REAL x2, REAL y2, REAL x3, R 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; + continue; } else /* add a middle point */ if(!(node = add_path_list_node(start, mp[2].X, mp[2].Y, PathPointTypeLine))) - return FALSE; + { + ret = FALSE; + break; + }; + + /* 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; + } - /* 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 -- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/3394
Hi, It looks like your patch introduced the new failures shown below. Please investigate and fix them before resubmitting your patch. If they are not new, fixing them anyway would help a lot. Otherwise please ask for the known failures list to be updated. The tests also ran into some preexisting test failures. If you know how to fix them that would be helpful. See the TestBot job for the details: The full results can be found at: https://testbot.winehq.org/JobDetails.pl?Key=135162 Your paranoid android. === debian11b (64 bit WoW report) === Report validation errors: 0be4windows.devices.bluetooth:bluetooth has no done line (or it is garbled)
I'm not sure about the whitespace patch (personally, I tend to review with whitespace ignored for exactly that reason anyway), but I'll approve in case that's acceptable. -- https://gitlab.winehq.org/wine/wine/-/merge_requests/3394#note_40025
This merge request was approved by Esme Povirk. -- https://gitlab.winehq.org/wine/wine/-/merge_requests/3394
participants (4)
-
Esme Povirk (＠madewokherd) -
Fabian Maurer
-
Fabian Maurer (＠DarkShadow44)
-
Marvin