[9/9] gdiplus: initial GdipFlattenPath implementation
Nikolay Sivov
bunglehead at gmail.com
Tue Sep 2 16:08:43 CDT 2008
Changelog (try2):
- remove some trailing spaces
Changelog:
- added implimentation of GdipFlattenPath based on recursive dividing of Bezier curve
- added simple test which pass with criterion used. Some existing tests pass too.
>From fe99561c40ac4f5fb4fdd6fba238f53c75ee6556 Mon Sep 17 00:00:00 2001
From: Nikolay Sivov <bunglehead at gmail.com>
Date: Wed, 3 Sep 2008 00:54:19 +0400
Subject: initial implementation of GdipFlattenPath with test
---
dlls/gdiplus/graphicspath.c | 227 ++++++++++++++++++++++++++++++++++++-
dlls/gdiplus/tests/graphicspath.c | 45 ++++++--
2 files changed, 258 insertions(+), 14 deletions(-)
diff --git a/dlls/gdiplus/graphicspath.c b/dlls/gdiplus/graphicspath.c
index d0f5dc0..ae9dc3a 100644
--- a/dlls/gdiplus/graphicspath.c
+++ b/dlls/gdiplus/graphicspath.c
@@ -33,6 +33,134 @@
WINE_DEFAULT_DEBUG_CHANNEL(gdiplus);
+typedef struct path_list_node_t path_list_node_t;
+struct path_list_node_t {
+ GpPointF pt;
+ BYTE type; /* PathPointTypeStart or PathPointTypeLine */
+ path_list_node_t *next;
+};
+
+/* init list */
+BOOL init_path_list(path_list_node_t **node, REAL x, REAL y)
+{
+ *node = GdipAlloc(sizeof(path_list_node_t));
+ if(!*node)
+ return FALSE;
+
+ (*node)->pt.X = x;
+ (*node)->pt.Y = y;
+ (*node)->type = PathPointTypeStart;
+ (*node)->next = NULL;
+
+ return TRUE;
+}
+
+/* free all nodes including argument */
+void free_path_list(path_list_node_t *node)
+{
+ path_list_node_t *n = node;
+
+ while(!n){
+ GdipFree(node);
+ node = n = n->next;
+ }
+}
+
+/* Add a node after 'node' */
+/*
+ * Returns
+ * pointer on success
+ * NULL on allocation problems
+ */
+path_list_node_t* add_path_list_node(path_list_node_t *node, REAL x, REAL y, BOOL type)
+{
+ path_list_node_t *new;
+
+ new = GdipAlloc(sizeof(path_list_node_t));
+ if(!new)
+ return NULL;
+
+ new->pt.X = x;
+ new->pt.Y = y;
+ new->type = type;
+ new->next = node->next;
+ node->next = new;
+
+ return new;
+}
+
+/* returns element count */
+INT path_list_count(path_list_node_t *node)
+{
+ INT count = 1;
+
+ while((node = node->next))
+ ++count;
+
+ return count;
+}
+
+/* GdipFlattenPath helper */
+/*
+ * Used to recursively flatten single Bezier curve
+ * Parameters:
+ * - start : pointer to start point node;
+ * - (x2, y2): first control point;
+ * - (x3, y3): second control point;
+ * - end : pointer to end point node
+ * - flatness: admissible error of linear approximation.
+ *
+ * Return value:
+ * TRUE : success
+ * FALSE: out of memory
+ *
+ * TODO: used quality criteria should be revised to match native as
+ * closer as possible.
+ */
+BOOL flatten_bezier(path_list_node_t *start, REAL x2, REAL y2, REAL x3, REAL y3,
+ path_list_node_t *end, REAL flatness)
+{
+ /* this 5 middle points with start/end define to half-curves */
+ GpPointF mp[5];
+ GpPointF pt, pt_st;
+ path_list_node_t *node;
+
+ /* 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;
+ /* middle point between control points */
+ pt.X = (x2 + x3) / 2.0;
+ pt.Y = (y2 + y3) / 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;
+
+ mp[2].X = (mp[1].X + mp[3].X) / 2.0;
+ mp[2].Y = (mp[1].Y + mp[3].Y) / 2.0;
+
+ pt = end->pt;
+ pt_st = start->pt;
+ /* check flatness as a half of distance between middle point and a linearized path */
+ if(fabs(((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))) <=
+ (0.5 * flatness*sqrtf((powf(pt.Y - pt_st.Y, 2.0) + powf(pt_st.X - pt.X, 2.0))))){
+ 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 halfs */
+ 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);
+
+ return TRUE;
+}
+
GpStatus WINGDIPAPI GdipAddPathArc(GpPath *path, REAL x1, REAL y1, REAL x2,
REAL y2, REAL startAngle, REAL sweepAngle)
{
@@ -818,15 +946,106 @@ GpStatus WINGDIPAPI GdipDeletePath(GpPath *path)
GpStatus WINGDIPAPI GdipFlattenPath(GpPath *path, GpMatrix* matrix, REAL flatness)
{
- static int calls;
+ path_list_node_t *list, *node;
+ GpPointF pt;
+ INT i = 1;
+ INT startidx = 0;
+
+ TRACE("(%p, %p, %.2f)\n", path, matrix, flatness);
if(!path)
return InvalidParameter;
- if(!(calls++))
- FIXME("not implemented\n");
+ if(matrix){
+ WARN("transformation not supported yet!\n");
+ return NotImplemented;
+ }
- return NotImplemented;
+ if(path->pathdata.Count == 0)
+ return Ok;
+
+ pt = path->pathdata.Points[0];
+ if(!init_path_list(&list, pt.X, pt.Y))
+ return OutOfMemory;
+
+ node = list;
+
+ while(i < path->pathdata.Count){
+
+ BYTE type = path->pathdata.Types[i] & PathPointTypePathTypeMask;
+ path_list_node_t *start;
+
+ pt = path->pathdata.Points[i];
+
+ /* save last start point index */
+ if(type == PathPointTypeStart)
+ startidx = i;
+
+ /* always add line points and start points */
+ if((type == PathPointTypeStart) || (type == PathPointTypeLine)){
+ type = (path->pathdata.Types[i] & ~PathPointTypeBezier) | PathPointTypeLine;
+ if(!add_path_list_node(node, pt.X, pt.Y, type))
+ goto memout;
+
+ node = node->next;
+ continue;
+ }
+
+ /* Bezier curve always stored as 4 points */
+ if((path->pathdata.Types[i-1] & PathPointTypePathTypeMask) != PathPointTypeStart){
+ type = (path->pathdata.Types[i] & ~PathPointTypeBezier) | PathPointTypeLine;
+ if(!add_path_list_node(node, pt.X, pt.Y, type))
+ goto memout;
+
+ node = node->next;
+ }
+
+ /* test for closed figure */
+ if(path->pathdata.Types[i+1] & PathPointTypeCloseSubpath){
+ pt = path->pathdata.Points[startidx];
+ ++i;
+ }
+ else
+ {
+ i += 2;
+ pt = path->pathdata.Points[i];
+ };
+
+ start = node;
+ /* add Bezier end point */
+ type = (path->pathdata.Types[i] & ~PathPointTypeBezier) | PathPointTypeLine;
+ if(!add_path_list_node(node, pt.X, pt.Y, type))
+ goto memout;
+ node = node->next;
+
+ /* flatten curve */
+ if(!flatten_bezier(start, path->pathdata.Points[i-2].X, path->pathdata.Points[i-2].Y,
+ path->pathdata.Points[i-1].X, path->pathdata.Points[i-1].Y,
+ node, flatness))
+ goto memout;
+
+ ++i;
+ }/* while */
+
+ /* store path data back */
+ i = path_list_count(list);
+ if(!lengthen_path(path, i))
+ goto memout;
+ path->pathdata.Count = i;
+
+ node = list;
+ for(i = 0; i < path->pathdata.Count; i++){
+ path->pathdata.Points[i] = node->pt;
+ path->pathdata.Types[i] = node->type;
+ node = node->next;
+ }
+
+ free_path_list(list);
+ return Ok;
+
+memout:
+ free_path_list(list);
+ return OutOfMemory;
}
GpStatus WINGDIPAPI GdipGetPathData(GpPath *path, GpPathData* pathData)
diff --git a/dlls/gdiplus/tests/graphicspath.c b/dlls/gdiplus/tests/graphicspath.c
index 47d8205..7a5fbc2 100644
--- a/dlls/gdiplus/tests/graphicspath.c
+++ b/dlls/gdiplus/tests/graphicspath.c
@@ -888,10 +888,10 @@ static void test_addpie(void)
static path_test_t flattenellipse_path[] = {
{100.0, 25.0,PathPointTypeStart, 0, 0}, /*0*/
- {99.0, 30.0, PathPointTypeLine, 0, 1}, /*1*/
- {96.0, 34.8, PathPointTypeLine, 0, 1}, /*2*/
- {91.5, 39.0, PathPointTypeLine, 0, 1}, /*3*/
- {85.5, 42.8, PathPointTypeLine, 0, 1}, /*4*/
+ {99.0, 30.0, PathPointTypeLine, 0, 0}, /*1*/
+ {96.0, 34.8, PathPointTypeLine, 0, 0}, /*2*/
+ {91.5, 39.0, PathPointTypeLine, 0, 0}, /*3*/
+ {85.5, 42.8, PathPointTypeLine, 0, 0}, /*4*/
{69.5, 48.0, PathPointTypeLine, 0, 1}, /*5*/
{50.0, 50.0, PathPointTypeLine, 0, 1}, /*6*/
{30.5, 48.0, PathPointTypeLine, 0, 1}, /*7*/
@@ -916,14 +916,26 @@ static path_test_t flattenellipse_path[] = {
static path_test_t flattenarc_path[] = {
{100.0, 25.0,PathPointTypeStart, 0, 0}, /*0*/
- {99.0, 30.0, PathPointTypeLine, 0, 1}, /*1*/
- {96.0, 34.8, PathPointTypeLine, 0, 1}, /*2*/
- {91.5, 39.0, PathPointTypeLine, 0, 1}, /*3*/
- {85.5, 42.8, PathPointTypeLine, 0, 1}, /*4*/
+ {99.0, 30.0, PathPointTypeLine, 0, 0}, /*1*/
+ {96.0, 34.8, PathPointTypeLine, 0, 0}, /*2*/
+ {91.5, 39.0, PathPointTypeLine, 0, 0}, /*3*/
+ {85.5, 42.8, PathPointTypeLine, 0, 0}, /*4*/
{69.5, 48.0, PathPointTypeLine, 0, 1}, /*5*/
{50.0, 50.0, PathPointTypeLine, 0, 1} /*6*/
};
+static path_test_t flattenquater_path[] = {
+ {100.0, 50.0,PathPointTypeStart, 0, 0}, /*0*/
+ {99.0, 60.0, PathPointTypeLine, 0, 0}, /*1*/
+ {96.0, 69.5, PathPointTypeLine, 0, 0}, /*2*/
+ {91.5, 78.0, PathPointTypeLine, 0, 0}, /*3*/
+ {85.5, 85.5, PathPointTypeLine, 0, 0}, /*4*/
+ {78.0, 91.5, PathPointTypeLine, 0, 0}, /*5*/
+ {69.5, 96.0, PathPointTypeLine, 0, 0}, /*6*/
+ {60.0, 99.0, PathPointTypeLine, 0, 0}, /*7*/
+ {50.0, 100.0,PathPointTypeLine, 0, 0} /*8*/
+ };
+
static void test_flatten(void)
{
GpStatus status;
@@ -941,11 +953,15 @@ static void test_flatten(void)
status = GdipFlattenPath(NULL, m, 0.0);
expect(InvalidParameter, status);
+ /* flatten empty path */
+ status = GdipFlattenPath(path, NULL, 1.0);
+ expect(Ok, status);
+
status = GdipAddPathEllipse(path, 0.0, 0.0, 100.0, 50.0);
expect(Ok, status);
status = GdipFlattenPath(path, NULL, 1.0);
- todo_wine expect(Ok, status);
+ expect(Ok, status);
ok_path(path, flattenellipse_path, sizeof(flattenellipse_path)/sizeof(path_test_t), TRUE);
status = GdipResetPath(path);
@@ -953,9 +969,18 @@ static void test_flatten(void)
status = GdipAddPathArc(path, 0.0, 0.0, 100.0, 50.0, 0.0, 90.0);
expect(Ok, status);
status = GdipFlattenPath(path, NULL, 1.0);
- todo_wine expect(Ok, status);
+ expect(Ok, status);
ok_path(path, flattenarc_path, sizeof(flattenarc_path)/sizeof(path_test_t), TRUE);
+ /* easy case - quater of a full circle */
+ status = GdipResetPath(path);
+ expect(Ok, status);
+ status = GdipAddPathArc(path, 0.0, 0.0, 100.0, 100.0, 0.0, 90.0);
+ expect(Ok, status);
+ status = GdipFlattenPath(path, NULL, 1.0);
+ expect(Ok, status);
+ ok_path(path, flattenquater_path, sizeof(flattenquater_path)/sizeof(path_test_t), FALSE);
+
GdipDeleteMatrix(m);
GdipDeletePath(path);
}
--
1.4.4.4
More information about the wine-patches
mailing list