[gtk/path-ops: 4/8] path: Implement boolean ops
- From: Matthias Clasen <matthiasc src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/path-ops: 4/8] path: Implement boolean ops
- Date: Fri, 25 Mar 2022 16:57:19 +0000 (UTC)
commit eccdf2146a8c3e3adb3ebe89acd19ee07b5689fc
Author: Matthias Clasen <mclasen redhat com>
Date: Thu Mar 24 01:41:02 2022 -0400
path: Implement boolean ops
This adds apis for union, intersection, difference
and symmetric difference of two paths.
The implementation is not super-robust yet.
gsk/gskpath.h | 16 ++
gsk/gskpathsimplify.c | 765 ++++++++++++++++++++++++++++++++++++++------------
2 files changed, 605 insertions(+), 176 deletions(-)
---
diff --git a/gsk/gskpath.h b/gsk/gskpath.h
index 60188009aa..feb7a3e9a5 100644
--- a/gsk/gskpath.h
+++ b/gsk/gskpath.h
@@ -124,6 +124,22 @@ GskPath * gsk_path_offset (GskPath
GskLineJoin line_join,
float miter_limit);
+GDK_AVAILABLE_IN_ALL
+GskPath * gsk_path_union (GskPath *first,
+ GskPath *second);
+
+GDK_AVAILABLE_IN_ALL
+GskPath * gsk_path_intersection (GskPath *first,
+ GskPath *second);
+
+GDK_AVAILABLE_IN_ALL
+GskPath * gsk_path_difference (GskPath *first,
+ GskPath *second);
+
+GDK_AVAILABLE_IN_ALL
+GskPath * gsk_path_symmetric_difference (GskPath *first,
+ GskPath *second);
+
GDK_AVAILABLE_IN_ALL
GskPath * gsk_path_simplify (GskPath *self);
diff --git a/gsk/gskpathsimplify.c b/gsk/gskpathsimplify.c
index 835eca5220..b79af4cca7 100644
--- a/gsk/gskpathsimplify.c
+++ b/gsk/gskpathsimplify.c
@@ -48,8 +48,13 @@ typedef struct
GskCurve curve;
Connection *start;
Connection *end;
- gboolean internal;
+ gboolean interior;
+ gboolean area_to_the_left;
+ gboolean area_to_the_right;
+ gboolean classified;
gboolean collected;
+ float start_angle;
+ float end_angle;
char *name;
} Curve;
@@ -60,15 +65,6 @@ curve_free (Curve *c)
g_free (c);
}
-typedef struct
-{
- GList *curves;
- GList *connections;
- Curve *start;
-} SimplifyData;
-
-static int collect_num = 0;
-
static gboolean
is_stationary_close (GskCurve *curve)
{
@@ -76,12 +72,23 @@ is_stationary_close (GskCurve *curve)
graphene_point_near (&curve->line.points[0], &curve->line.points[1], 0.01);
}
+static gboolean
+is_tiny (GskCurve *curve)
+{
+ GskBoundingBox bounds;
+
+ gsk_curve_get_bounds (curve, &bounds);
+
+ return bounds.max.x - bounds.min.x < 0.01 &&
+ bounds.max.y - bounds.min.y < 0.01;
+}
+
static void
merge_connections (GList **connections,
Connection *c1,
Connection *c2)
{
- g_assert (graphene_point_near (&c1->p, &c2->p, 0.1));
+ //g_assert (graphene_point_near (&c1->p, &c2->p, 0.1));
if (c1 == c2)
return;
@@ -101,17 +108,24 @@ merge_connections (GList **connections,
connection_free (c2);
}
+typedef struct
+{
+ GList *curves;
+ GList *connections;
+ Curve *start;
+ int num;
+} CollectData;
+
static gboolean
-simplify_collect_cb (GskPathOperation op,
- const graphene_point_t *pts,
- gsize n_pts,
- float weight,
- gpointer user_data)
+collect_cb (GskPathOperation op,
+ const graphene_point_t *pts,
+ gsize n_pts,
+ float weight,
+ gpointer user_data)
{
- SimplifyData *data = user_data;
+ CollectData *data = user_data;
Curve *curve;
Connection *connection;
- const char *opname[] = { "Move", "Close", "Line", "Curve", "Conic" };
g_assert (op != GSK_PATH_CONIC);
@@ -139,6 +153,7 @@ simplify_collect_cb (GskPathOperation op,
curve->curve.op = GSK_PATH_MOVE;
curve->curve.line.points[0] = pts[0];
curve->end = connection;
+ g_ptr_array_add (curve->end->edges, curve);
data->curves = g_list_prepend (data->curves, curve);
data->start = curve;
@@ -182,7 +197,10 @@ simplify_collect_cb (GskPathOperation op,
}
#ifdef G_ENABLE_DEBUG
- curve->name = g_strdup_printf ("%s %d", opname[op], collect_num++);
+ {
+ const char *opname[] = { "Move", "Close", "Line", "Curve", "Conic" };
+ curve->name = g_strdup_printf ("%s %d", opname[op], data->num++);
+ }
#endif
return TRUE;
@@ -192,61 +210,82 @@ static void
gsk_path_builder_append_curve (GskPathBuilder *builder,
GskCurve *curve)
{
- switch (curve->op)
- {
- case GSK_PATH_CLOSE:
- gsk_path_builder_close (builder);
- break;
-
- case GSK_PATH_MOVE:
- gsk_path_builder_move_to (builder, curve->line.points[0].x, curve->line.points[0].y);
- break;
-
- case GSK_PATH_LINE:
- gsk_path_builder_line_to (builder, curve->line.points[1].x, curve->line.points[1].y);
- break;
-
- case GSK_PATH_CURVE:
- gsk_path_builder_curve_to (builder,
- curve->curve.points[1].x, curve->curve.points[1].y,
- curve->curve.points[2].x, curve->curve.points[2].y,
- curve->curve.points[3].x, curve->curve.points[3].y);
- break;
-
- case GSK_PATH_CONIC:
- gsk_path_builder_conic_to (builder,
- curve->conic.points[1].x, curve->conic.points[1].y,
- curve->conic.points[2].x, curve->conic.points[2].y,
- curve->conic.points[3].x);
- break;
-
- default:
- g_assert_not_reached ();
- }
+ if (curve->op == GSK_PATH_MOVE)
+ gsk_path_builder_move_to (builder, curve->line.points[0].x, curve->line.points[0].y);
+ else
+ gsk_curve_builder_to (curve, builder);
}
-#define NEAR(f1, f2) (fabs ((f2) - (f1)) < 1e-3)
+typedef enum
+{
+ PATH_OP_SIMPLIFY,
+ PATH_OP_UNION,
+ PATH_OP_INTERSECTION,
+ PATH_OP_DIFFERENCE,
+ PATH_OP_XOR
+} PathOp;
+
+typedef struct
+{
+ PathOp operation;
+ GskPathMeasure *first;
+ GskPathMeasure *second;
+} PathOpData;
static gboolean
-curve_is_external (GskCurve *curve,
- GskPathMeasure *measure)
+point_is_inside (graphene_point_t *p,
+ PathOpData *opdata)
+{
+ gboolean in1, in2;
+
+ in1 = gsk_path_measure_in_fill (opdata->first, p, GSK_FILL_RULE_WINDING);
+ if (opdata->second)
+ in2 = gsk_path_measure_in_fill (opdata->second, p, GSK_FILL_RULE_WINDING);
+ else
+ in2 = FALSE;
+ switch (opdata->operation)
+ {
+ case PATH_OP_SIMPLIFY: return in1;
+ case PATH_OP_UNION: return in1 || in2;
+ case PATH_OP_INTERSECTION: return in1 && in2;
+ case PATH_OP_DIFFERENCE: return in1 && !in2;
+ case PATH_OP_XOR: return in1 != in2;
+ default: g_assert_not_reached ();
+ }
+}
+
+static void
+classify_boundary (Curve *curve,
+ PathOpData *opdata)
{
graphene_point_t pos, pos1, pos2;
graphene_vec2_t normal;
- if (curve->op == GSK_PATH_MOVE || is_stationary_close (curve))
- return TRUE;
+ gsk_curve_get_point (&curve->curve, 0.5, &pos);
+ gsk_curve_get_normal (&curve->curve, 0.5, &normal);
- gsk_curve_get_point (curve, 0.5, &pos);
- gsk_curve_get_normal (curve, 0.5, &normal);
+ pos1.x = pos.x + 0.5 * graphene_vec2_get_x (&normal);
+ pos1.y = pos.y + 0.5 * graphene_vec2_get_y (&normal);
+ pos2.x = pos.x - 0.5 * graphene_vec2_get_x (&normal);
+ pos2.y = pos.y - 0.5 * graphene_vec2_get_y (&normal);
- pos1.x = pos.x + 5 * graphene_vec2_get_x (&normal);
- pos1.y = pos.y + 5 * graphene_vec2_get_y (&normal);
- pos2.x = pos.x - 5 * graphene_vec2_get_x (&normal);
- pos2.y = pos.y - 5 * graphene_vec2_get_y (&normal);
+ curve->area_to_the_left = point_is_inside (&pos1, opdata);
+ curve->area_to_the_right = point_is_inside (&pos2, opdata);
+ curve->interior = curve->area_to_the_left == curve->area_to_the_right;
+ curve->classified = TRUE;
+}
- return gsk_path_measure_in_fill (measure, &pos1, GSK_FILL_RULE_WINDING) !=
- gsk_path_measure_in_fill (measure, &pos2, GSK_FILL_RULE_WINDING);
+static void
+compute_angles (Curve *curve)
+{
+ graphene_vec2_t tangent;
+
+ gsk_curve_get_start_tangent (&curve->curve, &tangent);
+ curve->start_angle = atan2 (- graphene_vec2_get_y (&tangent),
+ - graphene_vec2_get_x (&tangent));
+ gsk_curve_get_end_tangent (&curve->curve, &tangent);
+ curve->end_angle = atan2 (graphene_vec2_get_y (&tangent),
+ graphene_vec2_get_x (&tangent));
}
static Curve *
@@ -254,33 +293,118 @@ find_next (Curve *curve)
{
Connection *c = curve->end;
Curve *next = NULL;
+ guint idx;
+ int dir;
- g_print ("at %s:\n", curve->name);
- for (int i = 0; i < c->edges->len; i++)
+ g_assert (c != NULL);
+ g_assert (c->edges != NULL);
+
+ GSK_NOTE (PATHS,
+ g_print ("at %s:\n", curve->name);
+ for (int i = 0; i < c->edges->len; i++)
+ {
+ Curve *n = g_ptr_array_index (c->edges, i);
+ const char *ind = " ";
+ float angle;
+
+ if (n->collected) ind = "()";
+ else if (n->interior) ind = "[]";
+
+ angle = n->start == c ? n->start_angle : n->end_angle;
+
+ g_print ("\t%c%s%c %g\n", ind[0], n->name, ind[1], angle);
+ }
+ );
+
+ if (curve->curve.op == GSK_PATH_MOVE)
{
- Curve *n = g_ptr_array_index (c->edges, i);
- g_print ("\t%s\n", n->name);
- }
+ /* If we start a new contour, we just need to pick an
+ * eligible outgoing curve.
+ */
+ for (int d = 0; d < c->edges->len; d++)
+ {
+ Curve *n = g_ptr_array_index (c->edges, d);
+
+ if (n->collected || n->interior)
+ continue;
+
+ if (n->curve.op == GSK_PATH_MOVE)
+ continue;
- for (int i = 0; i < c->edges->len; i++)
+ if (n->end == c)
+ continue;
+
+ next = n;
+ break;
+ }
+ }
+ else
{
- Curve *n = g_ptr_array_index (c->edges, i);
+ /* Edges are sorted counterclockwise by their tangent.
+ * We pick the next eligible edge to the left
+ * or to the right of curve, depending on whether
+ * the left or right is inside.
+ */
+ g_ptr_array_find (c->edges, curve, &idx);
+ dir = curve->area_to_the_left ? -1 : 1;
+ for (int d = 0; d < c->edges->len; d++)
+ {
+ guint pos = (idx + dir * (d + 1)) % c->edges->len;
+ Curve *n = g_ptr_array_index (c->edges, pos);
+ float angle;
- if (n->collected || n->internal)
- continue;
+ if (n->collected || n->interior)
+ continue;
- if (next != NULL && n->curve.op == GSK_PATH_CLOSE)
- continue;
+ if (n->curve.op == GSK_PATH_MOVE)
+ continue;
- if (next != NULL && next->start == c)
- continue;
+ angle = n->end == c ? n->end_angle : n->start_angle;
+ if (fabs (angle - curve->end_angle) < 0.0001)
+ continue;
- if (next != NULL)
- g_print ("Two candidates. Do the sorting dance!\n");
+ next = n;
+ break;
+ }
+ }
- next = n;
+ if (next && next->end == c)
+ {
+ GskCurve r;
+ Connection *s;
+ gboolean a;
+
+ GSK_NOTE (PATHS, g_print ("reversing %s\n", next->name));
+ gsk_curve_reverse (&next->curve, &r);
+ next->curve = r;
+ s = next->start;
+ next->start = next->end;
+ next->end = s;
+ a = next->area_to_the_left;
+ next->area_to_the_left = next->area_to_the_right;
+ next->area_to_the_right = a;
}
+ GSK_NOTE (PATHS,
+ if (next == NULL)
+ {
+ g_print ("at %s: next is NULL\n", curve->name);
+ for (int i = 0; i < c->edges->len; i++)
+ {
+ Curve *n = g_ptr_array_index (c->edges, i);
+ const char *ind = " ";
+ float angle;
+
+ if (n->collected) ind = "()";
+ else if (n->interior) ind = "[]";
+
+ angle = n->start == c ? n->start_angle : n->end_angle;
+
+ g_print ("\t%c%s%c %g\n", ind[0], n->name, ind[1], angle);
+ }
+ }
+ );
+
return next;
}
@@ -289,21 +413,22 @@ validate_curves (GList *curves,
gboolean split)
{
#ifdef G_ENABLE_DEBUG
- Curve *start;
for (GList *l = curves; l; l = l->next)
{
Curve *c = l->data;
GSK_NOTE (PATHS,
- g_print ("%s%s: ", c->internal ? "(" : "", c->name);
+ g_print ("%s%s: ", c->interior ? "(" : "", c->name);
if (c->curve.op != GSK_PATH_MOVE)
gsk_curve_print (&c->curve);
else
g_print ("%g %g", c->curve.line.points[0].x, c->curve.line.points[0].y);
- g_print ("%s\n", c->internal ? ")" : "");
+ g_print ("%s\n", c->interior ? ")" : "");
);
+#if 0
+ Curve *start;
if (c->curve.op == GSK_PATH_MOVE)
{
start = NULL;
@@ -317,9 +442,11 @@ validate_curves (GList *curves,
g_assert (c->start != NULL);
g_assert (c->end != NULL);
- g_assert (graphene_point_near (&c->start->p, gsk_curve_get_start_point (&c->curve), 0.001));
- g_assert (graphene_point_near (&c->end->p, gsk_curve_get_end_point (&c->curve), 0.001));
+ g_assert (graphene_point_near (&c->start->p, gsk_curve_get_start_point (&c->curve), 0.1));
+ g_assert (graphene_point_near (&c->end->p, gsk_curve_get_end_point (&c->curve), 0.1));
+#if 0
+ /* This isn't true with MOVE */
if (split)
{
g_assert (c->start->edges->len % 2 == 0);
@@ -332,6 +459,7 @@ validate_curves (GList *curves,
g_assert (c->start->edges->len == 2);
g_assert (c->end->edges->len == 2);
}
+#endif
g_assert (g_ptr_array_find (c->start->edges, c, &pos));
g_assert (g_ptr_array_find (c->end->edges, c, &pos));
@@ -342,6 +470,7 @@ validate_curves (GList *curves,
g_assert (g_ptr_array_find (start->start->edges, c, &pos));
}
}
+#endif
}
#endif
}
@@ -351,57 +480,122 @@ g_list_insert_after (GList *l,
gpointer data)
{
GList *res G_GNUC_UNUSED;
-
+ /* Silence warn-if-unused */
res = g_list_insert_before (l, l->next, data);
}
-/**
- * gsk_path_simplify:
- * @self: a `GskPath`
- *
- * Create a new path that describes the area as @self,
- * without overlapping contours.
- *
- * Returns: a new `GskPath`
- */
-GskPath *
-gsk_path_simplify (GskPath *self)
+static GskPath *
+gsk_path_remove_unclosed (GskPath *path)
{
- SimplifyData data;
+ GSList *contours;
+ GskPath *path2;
+
+ contours = NULL;
+ for (int i = 0; i < gsk_path_get_n_contours (path); i++)
+ {
+ const GskContour *contour = gsk_path_get_contour (path, i);
+ if (gsk_contour_get_flags (contour) & GSK_PATH_CLOSED)
+ contours = g_slist_prepend (contours, (gpointer)contour);
+ }
+
+ GSK_NOTE (PATHS, g_print ("%ld contours, %d closed\n", gsk_path_get_n_contours (path), g_slist_length
(contours)));
+
+ contours = g_slist_reverse (contours);
+ path2 = gsk_path_new_from_contours (contours);
+ g_slist_free (contours);
+
+ gsk_path_unref (path);
+
+ return path2;
+}
+
+#define NEAR(f1, f2) (fabs ((f2) - (f1)) < 0.0001)
+
+typedef struct
+{
+ float t1;
+ float t2;
+ graphene_point_t p;
+ Connection *connection;
+} SplitPoint;
+
+static int
+compare_t1 (const void *p1,
+ const void *p2)
+{
+ const SplitPoint *sp1 = p1;
+ const SplitPoint *sp2 = p2;
+ return sp1->t1 < sp2->t1 ? -1 : (sp1->t1 > sp2->t1 ? 1 : 0);
+}
+
+static int
+compare_t2 (const void *p1,
+ const void *p2)
+{
+ const SplitPoint *sp1 = p1;
+ const SplitPoint *sp2 = p2;
+ return sp1->t2 < sp2->t2 ? -1 : (sp1->t2 > sp2->t2 ? 1 : 0);
+}
+
+static int
+compare_angle (gconstpointer p1,
+ gconstpointer p2,
+ gpointer user_data)
+{
+ Connection *c = user_data;
+ Curve *c1 = *(Curve **)p1;
+ Curve *c2 = *(Curve **)p2;
+ float f1 = c1->start == c ? c1->start_angle : c1->end_angle;
+ float f2 = c2->start == c ? c2->start_angle : c2->end_angle;
+
+ return f1 < f2 ? -1 : (f1 > f2 ? 1 : 0);
+}
+
+static GskPath *
+gsk_path_op (PathOp operation,
+ GskPath *self,
+ GskPath *other)
+{
+ GList *curves;
+ GList *connections;
+ CollectData data;
GskPathBuilder *builder;
GList *l, *ll;
- GskPathMeasure *measure;
- gboolean closed;
+ PathOpData opdata;
/* Special-case convex paths */
- if (gsk_path_compute_convexity (self) == GSK_CONVEXITY_CONVEX)
+ if (operation == PATH_OP_SIMPLIFY &&
+ gsk_path_compute_convexity (self) == GSK_CONVEXITY_CONVEX)
return gsk_path_ref (self);
GSK_NOTE (PATHS, g_print ("collecting\n"));
data.curves = NULL;
data.connections = NULL;
+ data.num = 0;
- collect_num = 0;
- gsk_path_foreach (self, GSK_PATH_FOREACH_ALLOW_CURVE, simplify_collect_cb, &data);
+ gsk_path_foreach (self, GSK_PATH_FOREACH_ALLOW_CURVE, collect_cb, &data);
+ if (other)
+ gsk_path_foreach (other, GSK_PATH_FOREACH_ALLOW_CURVE, collect_cb, &data);
- data.curves = g_list_reverse (data.curves);
- data.connections = g_list_reverse (data.connections);
+ curves = g_list_reverse (data.curves);
+ connections = g_list_reverse (data.connections);
- validate_curves (data.curves, FALSE);
+ validate_curves (curves, FALSE);
- GSK_NOTE (PATHS, g_print ("intersecting\n"));
- l = data.curves;
+ GSK_NOTE (PATHS, g_print ("splitting\n"));
+ l = curves;
while (l)
{
Curve *cd1 = l->data;
while (l && (cd1->curve.op == GSK_PATH_MOVE ||
- is_stationary_close (&cd1->curve)))
+ is_tiny (&cd1->curve)))
{
l = l->next;
- if (l)
- cd1 = l->data;
+ if (!l)
+ break;
+ cd1 = l->data;
}
if (!l)
@@ -410,44 +604,61 @@ gsk_path_simplify (GskPath *self)
ll = l;
while (ll)
{
- Curve *cd2 = ll->data;
+ Curve *cd2;
float t1[9], t2[9];
- graphene_point_t p [9];
+ graphene_point_t p[9];
+ SplitPoint sp[9];
int n;
- GList *next;
- Connection *connection;
GskCurve cs, ce;
Curve *cd;
+ GList *before;
+ char *name;
+
+ cd1 = l->data;
+ cd2 = ll->data;
while (ll && (cd2->curve.op == GSK_PATH_MOVE ||
- is_stationary_close (&cd2->curve)))
+ is_tiny (&cd2->curve)))
{
ll = ll->next;
- if (ll)
- cd2 = ll->data;
+ if (!ll)
+ break;
+ cd2 = ll->data;
}
if (!ll)
break;
- next = ll->next;
-
n = gsk_curve_intersect (&cd1->curve, &cd2->curve, t1, t2, p, sizeof (p));
+
+ GSK_NOTE (PATHS,
+ if (n > 1 || (n == 1 && (!NEAR (t1[0], 0) && !NEAR (t1[0], 1))))
+ g_print ("%d intersections between %s and %s\n",
+ n, cd1->name, cd2->name);
+ );
+
+ for (int i = 0; i < n; i++)
+ sp[i] = (SplitPoint) { t1[i], t2[i], p[i], NULL};
+
+ qsort (sp, n, sizeof (SplitPoint), compare_t1);
+
+ name = g_strdup (cd1->name);
+ before = l;
for (int i = 0; i < n; i++)
{
- if (NEAR (t1[i], 0))
- connection = cd1->start;
- else if (NEAR (t1[i], 1))
- connection = cd1->end;
+ if (NEAR (sp[i].t1, 0))
+ sp[i].connection = cd1->start;
+ else if (NEAR (sp[i].t1, 1))
+ sp[i].connection = cd1->end;
else
{
- connection = g_new0 (Connection, 1);
- connection->p = p[i];
- connection->edges = g_ptr_array_new ();
+ sp[i].connection = g_new0 (Connection, 1);
+ sp[i].connection->p = sp[i].p;
+ sp[i].connection->edges = g_ptr_array_new ();
- data.connections = g_list_prepend (data.connections, connection);
+ connections = g_list_prepend (connections, sp[i].connection);
- gsk_curve_split (&cd1->curve, t1[i], &cs, &ce);
+ gsk_curve_split (&cd1->curve, sp[i].t1, &cs, &ce);
cd1->curve = cs;
cd = g_new0 (Curve, 1);
@@ -455,26 +666,61 @@ gsk_path_simplify (GskPath *self)
cd->end = cd1->end;
g_ptr_array_remove (cd->end->edges, cd1);
g_ptr_array_add (cd->end->edges, cd);
+
#ifdef G_ENABLE_DEBUG
- cd->name = g_strdup_printf ("%s.%d", cd1->name, i);
+ if (i == 0)
+ {
+ char *nn = g_strdup_printf ("%s.0", name);
+ g_free (cd1->name);
+ cd1->name = nn;
+ }
+ cd->name = g_strdup_printf ("%s.%d", name, i + 1);
#endif
- cd1->end = connection;
- cd->start = connection;
-
- g_list_insert_after (l, cd);
-
- g_ptr_array_add (connection->edges, cd1);
- g_ptr_array_add (connection->edges, cd);
+ GSK_NOTE (PATHS,
+ if (i == 0)
+ {
+ g_print ("split %s from %s at %g\n", cd1->name, name, sp[i].t1);
+ g_print ("%s%s: ", cd1->interior ? "(" : "", cd1->name);
+ gsk_curve_print (&cd1->curve);
+ g_print ("%s\n", cd1->interior ? ")" : "");
+ }
+ );
+ GSK_NOTE (PATHS,
+ g_print ("split %s from %s at %g\n", cd->name, name, sp[i].t1);
+ g_print ("%s%s: ", cd->interior ? "(" : "", cd->name);
+ gsk_curve_print (&cd->curve);
+ g_print ("%s\n", cd->interior ? ")" : "");
+ );
+
+ cd1->end = sp[i].connection;
+ cd->start = sp[i].connection;
+
+ g_list_insert_after (before, cd);
+ before = before->next;
+
+ g_ptr_array_add (sp[i].connection->edges, cd1);
+ g_ptr_array_add (sp[i].connection->edges, cd);
+
+ cd1 = cd;
+ for (int j = i + 1; j < n; j++)
+ sp[j].t1 = (sp[j].t1 - sp[i].t1) / (1 - sp[i].t1);
}
+ }
+ g_free (name);
+
+ qsort (sp, n, sizeof (SplitPoint), compare_t2);
- if (NEAR (t2[i], 0))
- merge_connections (&data.connections, connection, cd2->start);
- else if (NEAR (t2[i], 1))
- merge_connections (&data.connections, connection, cd2->end);
+ name = g_strdup (cd2->name);
+ for (int i = 0; i < n; i++)
+ {
+ if (NEAR (sp[i].t2, 0))
+ merge_connections (&connections, sp[i].connection, cd2->start);
+ else if (NEAR (sp[i].t2, 1))
+ merge_connections (&connections, sp[i].connection, cd2->end);
else
{
- gsk_curve_split (&cd2->curve, t2[i], &cs, &ce);
+ gsk_curve_split (&cd2->curve, sp[i].t2, &cs, &ce);
cd2->curve = cs;
cd = g_new0 (Curve, 1);
@@ -482,21 +728,50 @@ gsk_path_simplify (GskPath *self)
cd->end = cd2->end;
g_ptr_array_remove (cd->end->edges, cd2);
g_ptr_array_add (cd->end->edges, cd);
+
#ifdef G_ENABLE_DEBUG
- cd->name = g_strdup_printf ("%s.%d", cd2->name, i);
+ if (i == 0)
+ {
+ char *nn = g_strdup_printf ("%s.0", name);
+ g_free (cd2->name);
+ cd2->name = nn;
+ }
+ cd->name = g_strdup_printf ("%s.%d", name, i + 1);
#endif
- cd2->end = connection;
- cd->start = connection;
+ GSK_NOTE (PATHS,
+ if (i == 0)
+ {
+ g_print ("split %s from %s at %g\n", cd2->name, name, sp[i].t2);
+ g_print ("%s%s: ", cd2->interior ? "(" : "", cd2->name);
+ gsk_curve_print (&cd2->curve);
+ g_print ("%s\n", cd2->interior ? ")" : "");
+ }
+ );
+ GSK_NOTE (PATHS,
+ g_print ("split %s from %s at %g\n", cd->name, name, sp[i].t2);
+ g_print ("%s%s: ", cd->interior ? "(" : "", cd->name);
+ gsk_curve_print (&cd->curve);
+ g_print ("%s\n", cd->interior ? ")" : "");
+ );
+
+ cd2->end = sp[i].connection;
+ cd->start = sp[i].connection;
g_list_insert_after (ll, cd);
+ ll = ll->next;
+
+ g_ptr_array_add (sp[i].connection->edges, cd2);
+ g_ptr_array_add (sp[i].connection->edges, cd);
- g_ptr_array_add (connection->edges, cd2);
- g_ptr_array_add (connection->edges, cd);
+ cd2 = cd;
+ for (int j = i + 1; j < n; j++)
+ sp[j].t2 = (sp[j].t2 - sp[i].t2) / (1 - sp[i].t2);
}
}
+ g_free (name);
- ll = next;
+ ll = ll->next;
}
l = l->next;
@@ -504,78 +779,216 @@ gsk_path_simplify (GskPath *self)
GSK_NOTE (PATHS, g_print ("classifying\n"));
- measure = gsk_path_measure_new (self);
+ opdata.operation = operation;
+ opdata.first = gsk_path_measure_new (self);
+ opdata.second = other ? gsk_path_measure_new (other) : NULL;
- for (l = data.curves; l; l = l->next)
+ for (l = curves; l; l = l->next)
{
Curve *curve = l->data;
- curve->internal = !curve_is_external (&curve->curve, measure);
+ if (curve->curve.op == GSK_PATH_MOVE || is_stationary_close (&curve->curve))
+ continue;
+
+ compute_angles (curve);
+
+#if 0
+ if (curve->start->edges->len == 2)
+ {
+ Curve *other_curve;
+
+ if (curve == g_ptr_array_index (curve->start->edges, 0))
+ other_curve = g_ptr_array_index (curve->start->edges, 1);
+ else
+ other_curve = g_ptr_array_index (curve->start->edges, 0);
+ if (other_curve->classified)
+ {
+ /* propagate classification */
+ curve->area_to_the_left = other_curve->area_to_the_left;
+ curve->area_to_the_right = other_curve->area_to_the_right;
+ curve->interior = other_curve->interior;
+ curve->classified = TRUE;
+ continue;
+ }
+ }
+#endif
+
+ classify_boundary (curve, &opdata);
}
- gsk_path_measure_unref (measure);
+ gsk_path_measure_unref (opdata.first);
+ if (opdata.second)
+ gsk_path_measure_unref (opdata.second);
+
+ validate_curves (curves, TRUE);
- validate_curves (data.curves, TRUE);
+ GSK_NOTE (PATHS, g_print ("sorting\n"));
+
+ for (l = connections; l; l = l->next)
+ {
+ Connection *c = l->data;
+
+ g_ptr_array_sort_with_data (c->edges, compare_angle, c);
+ }
GSK_NOTE (PATHS, g_print ("reassembling\n"));
builder = gsk_path_builder_new ();
- closed = TRUE;
- for (l = data.curves; l; l = l->next)
+ for (l = curves; l; l = l->next)
{
Curve *curve = l->data;
- const graphene_point_t *p;
+ Connection *start;
- if (curve->collected || curve->internal)
+ if (curve->collected || curve->interior)
continue;
- /* start a new contour */
- if (!closed)
- {
- gsk_path_builder_close (builder);
- closed = TRUE;
- }
-
g_assert (curve->curve.op != GSK_PATH_CLOSE);
- g_assert (!curve->internal);
GSK_NOTE (PATHS, g_print ("start new contour %s\n", curve->name));
if (curve->curve.op == GSK_PATH_MOVE)
- p = &curve->curve.line.points[0];
+ start = curve->end;
else
- p = gsk_curve_get_start_point (&curve->curve);
- gsk_path_builder_move_to (builder, p->x, p->y);
+ start = curve->start;
+
+ gsk_path_builder_move_to (builder, start->p.x, start->p.y);
if (curve->curve.op != GSK_PATH_MOVE)
gsk_path_builder_append_curve (builder, &curve->curve);
curve->collected = TRUE;
- closed = FALSE;
/* collect segments, following through connections */
for (curve = find_next (curve); curve; curve = find_next (curve))
{
- g_assert (!curve->internal);
+ g_assert (!curve->interior);
if (curve->collected)
- break;
+ {
+ g_warning ("find_next returned collected %s, falling off\n", curve->name);
+ break;
+ }
GSK_NOTE (PATHS, g_print ("append %s\n", curve->name));
gsk_path_builder_append_curve (builder, &curve->curve);
curve->collected = TRUE;
- if (curve->curve.op == GSK_PATH_CLOSE ||
- curve->curve.op == GSK_PATH_MOVE)
+ if (curve->curve.op == GSK_PATH_CLOSE)
+ {
+ GSK_NOTE (PATHS, g_print ("explicitly closed\n"));
+ break;
+ }
+
+ if (curve->end == start)
{
- closed = TRUE;
+ GSK_NOTE (PATHS, g_print ("implicitly closed\n"));
+ gsk_path_builder_close (builder);
break;
}
}
+
+ gsk_path_builder_close (builder);
+ }
+
+#ifdef G_ENABLE_DEBUG
+ /* Check that we've collected all */
+ for (l = curves; l; l = l->next)
+ {
+ Curve *curve = l->data;
+ g_assert (curve->interior == !curve->collected);
}
+#endif
+
+ g_list_free_full (curves, (GDestroyNotify) curve_free);
+ g_list_free_full (connections, (GDestroyNotify) connection_free);
+
+ return gsk_path_remove_unclosed (gsk_path_builder_free_to_path (builder));
+}
+
+/**
+ * gsk_path_simplify:
+ * @self: a `GskPath`
+ *
+ * Create a new path that describes the same area as @self,
+ * without overlapping contours.
+ *
+ * Returns: a new `GskPath`
+ */
+GskPath *
+gsk_path_simplify (GskPath *self)
+{
+ GSK_NOTE (PATHS, g_print ("\n***simplify***\n"));
+ return gsk_path_op (PATH_OP_SIMPLIFY, self, NULL);
+}
+
+/**
+ * gsk_path_union:
+ * @first: a `GskPath`
+ * @second: a `GskPath`
+ *
+ * Create a new path that describes the union of the areas
+ * of the given paths.
+ *
+ * Returns: a new `GskPath`
+ */
+GskPath *
+gsk_path_union (GskPath *first,
+ GskPath *second)
+{
+ GSK_NOTE (PATHS, g_print ("\n***union***\n"));
+ return gsk_path_op (PATH_OP_UNION, first, second);
+}
- g_list_free_full (data.curves, (GDestroyNotify) curve_free);
- g_list_free_full (data.connections, (GDestroyNotify) connection_free);
+/**
+ * gsk_path_intersection:
+ * @first: a `GskPath`
+ * @second: a `GskPath`
+ *
+ * Create a new path that describes the intersection of the areas
+ * of the given paths.
+ *
+ * Returns: a new `GskPath`
+ */
+GskPath *
+gsk_path_intersection (GskPath *first,
+ GskPath *second)
+{
+ GSK_NOTE (PATHS, g_print ("\n***intersection***\n"));
+ return gsk_path_op (PATH_OP_INTERSECTION, first, second);
+}
- return gsk_path_builder_free_to_path (builder);
+/**
+ * gsk_path_difference:
+ * @first: a `GskPath`
+ * @second: a `GskPath`
+ *
+ * Create a new path that describes the difference of the areas
+ * of the given paths.
+ *
+ * Returns: a new `GskPath`
+ */
+GskPath *
+gsk_path_difference (GskPath *first,
+ GskPath *second)
+{
+ GSK_NOTE (PATHS, g_print ("\n***difference***\n"));
+ return gsk_path_op (PATH_OP_DIFFERENCE, first, second);
+}
+
+/**
+ * gsk_path_symmetric_difference:
+ * @first: a `GskPath`
+ * @second: a `GskPath`
+ *
+ * Create a new path that describes the symmetric difference
+ * of the areas of the given paths.
+ *
+ * Returns: a new `GskPath`
+ */
+GskPath *
+gsk_path_symmetric_difference (GskPath *first,
+ GskPath *second)
+{
+ GSK_NOTE (PATHS, g_print ("\n***symmetric difference***\n"));
+ return gsk_path_op (PATH_OP_XOR, first, second);
}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
