[gtk/path-tests] Handle degenerate curves
- From: Matthias Clasen <matthiasc src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/path-tests] Handle degenerate curves
- Date: Sat, 19 Dec 2020 05:22:07 +0000 (UTC)
commit ba43db7b09c57ff21925b305fd8a97b3b43e90f5
Author: Matthias Clasen <mclasen redhat com>
Date: Fri Dec 18 16:51:15 2020 -0500
Handle degenerate curves
Handle cases of cubics and conics where
control points are nearly collinear.
gsk/gskpathstroke.c | 465 ++++++++++++++++++++++++++++++++++++++--------------
1 file changed, 338 insertions(+), 127 deletions(-)
---
diff --git a/gsk/gskpathstroke.c b/gsk/gskpathstroke.c
index 244e040258..f091e44d9b 100644
--- a/gsk/gskpathstroke.c
+++ b/gsk/gskpathstroke.c
@@ -196,12 +196,203 @@ path_builder_add_reverse_path (GskPathBuilder *builder,
g_list_free_full (ops, g_free);
}
+/* }}} */
+/* {{{ GskCurve utilities */
+
+static gboolean
+cubic_is_simple (const GskCurve *curve)
+{
+ const graphene_point_t *pts = curve->curve.points;
+ float a1, a2, s;
+ graphene_vec2_t t1, t2, t3;
+ graphene_vec2_t n1, n2;
+
+ get_tangent (&pts[0], &pts[1], &t1);
+ get_tangent (&pts[1], &pts[2], &t2);
+ get_tangent (&pts[2], &pts[3], &t3);
+ a1 = angle_between (&t1, &t2);
+ a2 = angle_between (&t2, &t3);
+
+ if ((a1 < 0 && a2 > 0) || (a1 > 0 && a2 < 0))
+ return FALSE;
+
+ get_normal (&pts[0], &pts[1], &n1);
+ get_normal (&pts[2], &pts[3], &n2);
+
+ s = graphene_vec2_dot (&n1, &n2);
+
+ if (fabs (acos (s)) >= M_PI / 3.f)
+ return FALSE;
+
+ return TRUE;
+}
+
+static gboolean
+curve_is_degenerate (const GskCurve *curve)
+{
+ if (curve->op == GSK_PATH_CURVE)
+ {
+ const graphene_point_t *pts = curve->curve.points;
+ float a1, a2;
+ graphene_vec2_t t1, t2, t3;
+
+ get_tangent (&pts[0], &pts[1], &t1);
+ get_tangent (&pts[1], &pts[2], &t2);
+ get_tangent (&pts[2], &pts[3], &t3);
+ a1 = angle_between (&t1, &t2);
+ a2 = angle_between (&t2, &t3);
+
+ if (a1 < 0)
+ a1 += M_PI;
+ if (a2 < 0)
+ a2 += M_PI;
+
+ if (MIN (fabs (M_PI - a1), fabs (a1)) < DEG_TO_RAD (3) &&
+ MIN (fabs (M_PI - a2), fabs (a2)) < DEG_TO_RAD (3))
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
+static void
+align_points (const graphene_point_t *p,
+ const graphene_point_t *a,
+ const graphene_point_t *b,
+ graphene_point_t *q,
+ int n)
+{
+ graphene_vec2_t n1;
+ float angle;
+ float s, c;
+
+ get_tangent (a, b, &n1);
+ angle = - atan2 (graphene_vec2_get_y (&n1), graphene_vec2_get_x (&n1));
+ sincosf (angle, &s, &c);
+
+ for (int i = 0; i < n; i++)
+ {
+ q[i].x = (p[i].x - a->x) * c - (p[i].y - a->y) * s;
+ q[i].y = (p[i].x - a->x) * s + (p[i].y - a->y) * c;
+ }
+}
+
+static int
+get_cubic_extrema (float pa, float pb, float pc, float pd, float t[2])
+{
+ float a, b, c;
+ float d, tt;
+ int n = 0;
+
+ a = 3 * (pd - 3*pc + 3*pb - pa);
+ b = 6 * (pc - 2*pb + pa);
+ c = 3 * (pb - pa);
+
+ if (fabs (a) > 0.0001)
+ {
+ if (b*b > 4*a*c)
+ {
+ d = sqrt (b*b - 4*a*c);
+ tt = (-b + d)/(2*a);
+ if (0 < tt && tt < 1)
+ t[n++] = tt;
+ tt = (-b - d)/(2*a);
+ if (0 < tt && tt < 1)
+ t[n++] = tt;
+ }
+ else
+ {
+ tt = -b / (2*a);
+ if (0 < tt && tt < 1)
+ t[n++] = tt;
+ }
+ }
+ else if (fabs (b) > 0.0001)
+ {
+ tt = -c / b;
+ if (0 < tt && tt < 1)
+ t[n++] = tt;
+ }
+
+ return n;
+}
+
+/* For degenerate curves, find interior points
+ * where the function has a cusp. We do that by
+ * aligning the control points to be all on the
+ * x axis, and then looking for the t where x
+ * has the min/max value.
+ */
+static int
+find_turning_points (const GskCurve *curve,
+ float t[2])
+{
+ const graphene_point_t *pts = curve->curve.points;
+ graphene_point_t p[4];
+
+ align_points (pts, &pts[0], &pts[1], p, 4);
+
+ return get_cubic_extrema (p[0].x, p[1].x, p[2].x, p[3].x, t);
+}
+
+/* Get the points where the curvature of curve is
+ * zero, or a maximum or minimum, inside the open
+ * interval from 0 to 1.
+ */
+static int
+cubic_curvature_points (const GskCurve *curve,
+ float t[3])
+{
+ const graphene_point_t *pts = curve->curve.points;
+ graphene_point_t p[4];
+ float a, b, c, d;
+ float x, y, z;
+ float u2, u, tt;
+ int n_roots = 0;
+
+ align_points (pts, &pts[0], &pts[3], p, 4);
+
+ a = p[2].x * p[1].y;
+ b = p[3].x * p[1].y;
+ c = p[1].x * p[2].y;
+ d = p[3].x * p[2].y;
+
+ x = - 3*a + 2*b + 3*c - d;
+ y = 3*a - b - 3*c;
+ z = c - a;
+
+ if (fabs (x) >= 0.001)
+ {
+ tt = -y / (2*x);
+ if (0 < tt && tt < 1)
+ t[n_roots++] = tt;
+
+ u2 = y*y - 4*x*z;
+ if (u2 > 0.001)
+ {
+ u = sqrt (u2);
+
+ tt = (-y + u) / (2*x);
+ if (0 < tt && tt < 1)
+ t[n_roots++] = tt;
+
+ tt = (-y - u) / (2*x);
+ if (0 < tt && tt < 1)
+ t[n_roots++] = tt;
+ }
+ }
+
+ return n_roots;
+}
+
/* }}} */
/* {{{ Stroke helpers */
static void
add_line_join (GskPathBuilder *builder,
- GskStroke *stroke,
+ GskLineJoin line_join,
+ float line_width,
+ float miter_limit,
const graphene_point_t *c,
const graphene_point_t *a,
const graphene_vec2_t *ta,
@@ -209,7 +400,7 @@ add_line_join (GskPathBuilder *builder,
const graphene_vec2_t *tb,
float angle)
{
- switch (stroke->line_join)
+ switch (line_join)
{
case GSK_LINE_JOIN_MITER:
case GSK_LINE_JOIN_MITER_CLIP:
@@ -220,12 +411,12 @@ add_line_join (GskPathBuilder *builder,
{
float s = fabs (sin ((M_PI - angle) / 2));
- if (1.0 / s <= stroke->miter_limit)
+ if (1.0 / s <= miter_limit)
{
path_builder_line_to_point (builder, &p);
path_builder_line_to_point (builder, b);
}
- else if (stroke->line_join == GSK_LINE_JOIN_MITER_CLIP)
+ else if (line_join == GSK_LINE_JOIN_MITER_CLIP)
{
graphene_point_t q, a1, b1;
graphene_vec2_t n;
@@ -251,7 +442,7 @@ add_line_join (GskPathBuilder *builder,
case GSK_LINE_JOIN_ROUND:
gsk_path_builder_svg_arc_to (builder,
- stroke->line_width / 2, stroke->line_width / 2,
+ line_width / 2, line_width / 2,
0, 0, angle > 0 ? 1 : 0,
b->x, b->y);
break;
@@ -267,11 +458,12 @@ add_line_join (GskPathBuilder *builder,
static void
add_line_cap (GskPathBuilder *builder,
- GskStroke *stroke,
+ GskLineCap line_cap,
+ float line_width,
const graphene_point_t *s,
const graphene_point_t *e)
{
- switch (stroke->line_cap)
+ switch (line_cap)
{
case GSK_LINE_CAP_BUTT:
path_builder_line_to_point (builder, e);
@@ -279,7 +471,7 @@ add_line_cap (GskPathBuilder *builder,
case GSK_LINE_CAP_ROUND:
gsk_path_builder_svg_arc_to (builder,
- stroke->line_width / 2, stroke->line_width / 2,
+ line_width / 2, line_width / 2,
0, 1, 0,
e->x, e->y);
break;
@@ -404,13 +596,31 @@ static void
add_segments (StrokeData *stroke_data,
const GskCurve *curve,
GskCurve *r,
- GskCurve *l)
+ GskCurve *l,
+ gboolean force_round_join)
{
float angle;
float t1, t2;
graphene_vec2_t tangent1, tangent2;
graphene_point_t p;
+ if (!stroke_data->has_current_curve)
+ {
+ stroke_data->c0 = *curve;
+ stroke_data->r0 = *r;
+ stroke_data->l0 = *l;
+ path_builder_move_to_point (stroke_data->right, gsk_curve_get_start_point (r));
+ path_builder_move_to_point (stroke_data->left, gsk_curve_get_start_point (l));
+
+ stroke_data->c = *curve;
+ stroke_data->r = *r;
+ stroke_data->l = *l;
+
+ stroke_data->has_current_curve = TRUE;
+ stroke_data->is_first_curve = TRUE;
+ return;
+ }
+
gsk_curve_get_end_tangent (&stroke_data->c, &tangent1);
gsk_curve_get_start_tangent (curve, &tangent2);
angle = angle_between (&tangent1, &tangent2);
@@ -447,7 +657,10 @@ add_segments (StrokeData *stroke_data,
append_left (stroke_data, &stroke_data->l);
add_line_join (stroke_data->left,
- stroke_data->stroke,
+ force_round_join ? GSK_LINE_JOIN_ROUND
+ : stroke_data->stroke->line_join,
+ stroke_data->stroke->line_width,
+ stroke_data->stroke->miter_limit,
gsk_curve_get_start_point (curve),
gsk_curve_get_end_point (&stroke_data->l),
&tangent1,
@@ -461,7 +674,10 @@ add_segments (StrokeData *stroke_data,
append_right (stroke_data, &stroke_data->r);
add_line_join (stroke_data->right,
- stroke_data->stroke,
+ force_round_join ? GSK_LINE_JOIN_ROUND
+ : stroke_data->stroke->line_join,
+ stroke_data->stroke->line_width,
+ stroke_data->stroke->miter_limit,
gsk_curve_get_start_point (curve),
gsk_curve_get_end_point (&stroke_data->r),
&tangent1,
@@ -490,6 +706,7 @@ add_segments (StrokeData *stroke_data,
stroke_data->c = *curve;
stroke_data->r = *r;
stroke_data->l = *l;
+ stroke_data->is_first_curve = FALSE;
}
#ifdef STROKE_DEBUG
@@ -527,6 +744,7 @@ add_debug (StrokeData *stroke_data,
}
#endif
+
/* Add a curve to the in-progress stroke. We look at the angle between
* the previous curve and this one to determine on which side we need
* to intersect the curves, and on which to add a join.
@@ -537,142 +755,102 @@ add_curve (StrokeData *stroke_data,
{
GskCurve l, r;
- gsk_curve_offset (curve, - stroke_data->stroke->line_width / 2, &l);
- gsk_curve_offset (curve, stroke_data->stroke->line_width / 2, &r);
-
#ifdef STROKE_DEBUG
add_debug (stroke_data, curve);
#endif
- if (!stroke_data->has_current_curve)
- {
- stroke_data->c0 = *curve;
- stroke_data->r0 = r;
- stroke_data->l0 = l;
- path_builder_move_to_point (stroke_data->right, gsk_curve_get_start_point (&r));
- path_builder_move_to_point (stroke_data->left, gsk_curve_get_start_point (&l));
-
- stroke_data->c = *curve;
- stroke_data->r = r;
- stroke_data->l = l;
-
- stroke_data->has_current_curve = TRUE;
- stroke_data->is_first_curve = TRUE;
- }
- else
- {
- add_segments (stroke_data, curve, &r, &l);
+ gsk_curve_offset (curve, - stroke_data->stroke->line_width / 2, &l);
+ gsk_curve_offset (curve, stroke_data->stroke->line_width / 2, &r);
- stroke_data->is_first_curve = FALSE;
- }
+ add_segments (stroke_data, curve, &r, &l, FALSE);
}
-static gboolean
-cubic_is_simple (const GskCurve *curve)
+static void
+add_curve_round_join (StrokeData *stroke_data,
+ const GskCurve *curve)
{
- const graphene_point_t *pts = curve->curve.points;
- float a1, a2, s;
- graphene_vec2_t t1, t2, t3;
- graphene_vec2_t n1, n2;
-
- get_tangent (&pts[0], &pts[1], &t1);
- get_tangent (&pts[1], &pts[2], &t2);
- get_tangent (&pts[2], &pts[3], &t3);
- a1 = angle_between (&t1, &t2);
- a2 = angle_between (&t2, &t3);
-
- if ((a1 < 0 && a2 > 0) || (a1 > 0 && a2 < 0))
- return FALSE;
+ GskCurve l, r;
- get_normal (&pts[0], &pts[1], &n1);
- get_normal (&pts[2], &pts[3], &n2);
+#ifdef STROKE_DEBUG
+ add_debug (stroke_data, curve);
+#endif
- s = graphene_vec2_dot (&n1, &n2);
+ gsk_curve_offset (curve, - stroke_data->stroke->line_width / 2, &l);
+ gsk_curve_offset (curve, stroke_data->stroke->line_width / 2, &r);
- if (fabs (acos (s)) >= M_PI / 3.f)
- return FALSE;
+ add_segments (stroke_data, curve, &r, &l, TRUE);
+}
- return TRUE;
+static int
+cmpfloat (const void *p1, const void *p2)
+{
+ const float *f1 = p1;
+ const float *f2 = p2;
+ return *f1 < *f2 ? -1 : (*f1 > *f2 ? 1 : 0);
}
static void
-align_points (const graphene_point_t *p,
- const graphene_point_t *a,
- const graphene_point_t *b,
- graphene_point_t *q,
- int n)
+add_degenerate_curve (StrokeData *stroke_data,
+ const GskCurve *curve)
{
- graphene_vec2_t n1;
- float angle;
- float s, c;
+ float t[3];
+ int n;
+ GskCurve c;
+ graphene_point_t p[2];
- get_tangent (a, b, &n1);
- angle = - atan2 (graphene_vec2_get_y (&n1), graphene_vec2_get_x (&n1));
- sincosf (angle, &s, &c);
+ n = find_turning_points (curve, t);
- for (int i = 0; i < n; i++)
+ if (n == 0)
+ add_curve (stroke_data, curve);
+ else if (n == 1)
{
- q[i].x = (p[i].x - a->x) * c - (p[i].y - a->y) * s;
- q[i].y = (p[i].x - a->x) * s + (p[i].y - a->y) * c;
+ p[0] = *gsk_curve_get_start_point (curve);
+ gsk_curve_get_point (curve, t[0], &p[1]);
+ gsk_curve_init_foreach (&c, GSK_PATH_LINE, p, 2, 0);
+ add_curve (stroke_data, &c);
+
+ p[0] = p[1];
+ p[1] = *gsk_curve_get_end_point (curve);
+ gsk_curve_init_foreach (&c, GSK_PATH_LINE, p, 2, 0);
+ add_curve_round_join (stroke_data, &c);
}
-}
-
-/* Get the points where the curvature of curve is
- * zero, or a maximum or minimum, inside the open
- * interval from 0 to 1.
- */
-static int
-cubic_curvature_points (const GskCurve *curve,
- float t[3])
-{
- const graphene_point_t *pts = curve->curve.points;
- graphene_point_t p[4];
- float a, b, c, d;
- float x, y, z;
- float u2, u, tt;
- int n_roots = 0;
-
- align_points (pts, &pts[0], &pts[3], p, 4);
-
- a = p[2].x * p[1].y;
- b = p[3].x * p[1].y;
- c = p[1].x * p[2].y;
- d = p[3].x * p[2].y;
-
- x = - 3*a + 2*b + 3*c - d;
- y = 3*a - b - 3*c;
- z = c - a;
-
- if (fabs (x) >= 0.001)
+ else
{
- tt = -y / (2*x);
- if (0 < tt && tt < 1)
- t[n_roots++] = tt;
-
- u2 = y*y - 4*x*z;
- if (u2 > 0.001)
- {
- u = sqrt (u2);
-
- tt = (-y + u) / (2*x);
- if (0 < tt && tt < 1)
- t[n_roots++] = tt;
-
- tt = (-y - u) / (2*x);
- if (0 < tt && tt < 1)
- t[n_roots++] = tt;
- }
+ qsort (t, n, sizeof (float), cmpfloat);
+
+ p[0] = *gsk_curve_get_start_point (curve);
+ gsk_curve_get_point (curve, t[0], &p[1]);
+ gsk_curve_init_foreach (&c, GSK_PATH_LINE, p, 2, 0);
+ add_curve (stroke_data, &c);
+
+ p[0] = p[1];
+ gsk_curve_get_point (curve, t[1], &p[1]);
+ gsk_curve_init_foreach (&c, GSK_PATH_LINE, p, 2, 0);
+ add_curve_round_join (stroke_data, &c);
+
+ p[0] = p[1];
+ p[1] = *gsk_curve_get_end_point (curve);
+ gsk_curve_init_foreach (&c, GSK_PATH_LINE, p, 2, 0);
+ add_curve_round_join (stroke_data, &c);
}
-
- return n_roots;
}
-static int
-cmpfloat (const void *p1, const void *p2)
+static void
+add_degenerate_conic (StrokeData *stroke_data,
+ const GskCurve *curve)
{
- const float *f1 = p1;
- const float *f2 = p2;
- return *f1 < *f2 ? -1 : (*f1 > *f2 ? 1 : 0);
+ GskCurve c;
+ graphene_point_t p[2];
+
+ p[0] = *gsk_curve_get_start_point (curve);
+ gsk_curve_get_point (curve, 0.5, &p[1]);
+ gsk_curve_init_foreach (&c, GSK_PATH_LINE, p, 2, 0);
+ add_curve (stroke_data, &c);
+
+ p[0] = p[1];
+ p[1] = *gsk_curve_get_end_point (curve);
+ gsk_curve_init_foreach (&c, GSK_PATH_LINE, p, 2, 0);
+ add_curve_round_join (stroke_data, &c);
}
#define MAX_SUBDIVISION 8
@@ -682,7 +860,9 @@ subdivide_and_add_curve (StrokeData *stroke_data,
const GskCurve *curve,
int level)
{
- if (level == 0 || (level < MAX_SUBDIVISION && cubic_is_simple (curve)))
+ if (level == MAX_SUBDIVISION && curve_is_degenerate (curve))
+ add_degenerate_curve (stroke_data, curve);
+ else if (level == 0 || (level < MAX_SUBDIVISION && cubic_is_simple (curve)))
add_curve (stroke_data, curve);
else
{
@@ -736,12 +916,37 @@ conic_is_simple (const GskCurve *curve)
return TRUE;
}
+static gboolean
+conic_is_degenerate (const GskCurve *curve)
+{
+ if (curve->op == GSK_PATH_CONIC)
+ {
+ const graphene_point_t *pts = curve->curve.points;
+ float a;
+ graphene_vec2_t t1, t2;
+
+ get_tangent (&pts[0], &pts[1], &t1);
+ get_tangent (&pts[1], &pts[3], &t2);
+ a = angle_between (&t1, &t2);
+
+ if (a < 0)
+ a += M_PI;
+
+ if (fabs (a) < DEG_TO_RAD (3))
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
static void
subdivide_and_add_conic (StrokeData *stroke_data,
const GskCurve *curve,
int level)
{
- if (level == 0 || (level < MAX_SUBDIVISION && conic_is_simple (curve)))
+ if (level == MAX_SUBDIVISION && conic_is_degenerate (curve))
+ add_degenerate_conic (stroke_data, curve);
+ else if (level == 0 || (level < MAX_SUBDIVISION && conic_is_simple (curve)))
add_curve (stroke_data, curve);
else
{
@@ -779,7 +984,10 @@ cap_and_connect_contours (StrokeData *stroke_data)
else
path_builder_move_to_point (stroke_data->right, r1);
- add_line_cap (stroke_data->right, stroke_data->stroke, r1, l1);
+ add_line_cap (stroke_data->right,
+ stroke_data->stroke->line_cap,
+ stroke_data->stroke->line_width,
+ r1, l1);
if (stroke_data->has_current_curve)
{
@@ -797,7 +1005,10 @@ cap_and_connect_contours (StrokeData *stroke_data)
}
}
- add_line_cap (stroke_data->right, stroke_data->stroke, l0, r0);
+ add_line_cap (stroke_data->right,
+ stroke_data->stroke->line_cap,
+ stroke_data->stroke->line_width,
+ l0, r0);
if (stroke_data->has_current_curve)
{
@@ -831,7 +1042,7 @@ close_contours (StrokeData *stroke_data)
if (stroke_data->has_current_curve)
{
/* add final join and first segment */
- add_segments (stroke_data, &stroke_data->c0, &stroke_data->r0, &stroke_data->l0);
+ add_segments (stroke_data, &stroke_data->c0, &stroke_data->r0, &stroke_data->l0, FALSE);
path_builder_add_curve (stroke_data->right, &stroke_data->r);
path_builder_add_curve (stroke_data->left, &stroke_data->l);
}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
