[gtk/wip/matthiasc/lottie-stroke] wip: reorganize intersection code
- From: Matthias Clasen <matthiasc src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/wip/matthiasc/lottie-stroke] wip: reorganize intersection code
- Date: Thu, 3 Dec 2020 12:46:20 +0000 (UTC)
commit fe32c8b9c78511a66d6c84b6bb26e0bcb271bfda
Author: Matthias Clasen <mclasen redhat com>
Date: Thu Dec 3 01:44:19 2020 -0500
wip: reorganize intersection code
gsk/gskpathstroke.c | 763 ++++++++++++++++++++++++++++++++--------------------
1 file changed, 472 insertions(+), 291 deletions(-)
---
diff --git a/gsk/gskpathstroke.c b/gsk/gskpathstroke.c
index 615137e59c..4704652195 100644
--- a/gsk/gskpathstroke.c
+++ b/gsk/gskpathstroke.c
@@ -56,6 +56,20 @@ direction_vector (const graphene_point_t *p0,
graphene_vec2_normalize (t, t);
}
+static void
+find_point_on_line (const graphene_point_t *p1,
+ const graphene_point_t *p2,
+ const graphene_point_t *q,
+ float *t)
+{
+ float tx = p2->x - p1->x;
+ float ty = p2->y - p1->y;
+ float sx = q->x - p1->x;
+ float sy = q->y - p1->y;
+
+ *t = (tx*sx + ty*sy) / (tx*tx + ty*ty);
+}
+
static void
get_bezier (const graphene_point_t *points,
int length,
@@ -235,64 +249,6 @@ split_bezier3d (const graphene_point3d_t *p,
split_bezier3d_recurse (p, l, t, left, right, &lpos, &rpos);
}
-/* Given control points and weight for a rational quadratic
- * Bezier and t, create two sets of the same that give the
- * same curve as the original and split the curve at t.
- */
-static void
-split_conic (const graphene_point_t points[3],
- float weight,
- float t,
- graphene_point_t lp[3],
- graphene_point_t rp[3],
- float *lw,
- float *rw)
-{
- graphene_point3d_t p[3];
- graphene_point3d_t left[3], right[3];
- int i;
-
- /* do de Casteljau in homogeneous coordinates... */
- for (i = 0; i < 3; i++)
- {
- p[i].x = points[i].x;
- p[i].y = points[i].y;
- p[i].z = 1;
- }
-
- p[1].x *= weight;
- p[1].y *= weight;
- p[1].z *= weight;
-
- split_bezier3d (p, 3, t, left, right);
-
- /* then project the control points down */
- for (i = 0; i < 3; i++)
- {
- lp[i].x = left[i].x / left[i].z;
- lp[i].y = left[i].y / left[i].z;
- rp[i].x = right[i].x / right[i].z;
- rp[i].y = right[i].y / right[i].z;
- }
-
- /* normalize the outer weights to be 1 by using
- * the fact that weights w_i and c*w_i are equivalent
- * for any nonzero constant c
- */
- for (i = 0; i < 3; i++)
- {
- left[i].z /= left[0].z;
- right[i].z /= right[2].z;
- }
-
- /* normalize the inner weight to be 1 by using
- * the fact that w_0*w_2/w_1^2 is a constant for
- * all equivalent weights.
- */
- *lw = left[1].z / sqrt (left[2].z);
- *rw = right[1].z / sqrt (right[0].z);
-}
-
/* not sure this is useful for anything in particular */
static void
get_conic_shoulder_point (const graphene_point_t p[3],
@@ -311,68 +267,6 @@ acceptable (float t)
return 0 <= t && t <= 1;
}
-/* Solve N = 0 where N is the numerator of derivative of P/Q, with
- * P = (1-t)^a + 2t(1-t)wb + t^2c
- * Q = (1-t)^2 + 2t(1-t)w + t^2
- */
-static int
-get_conic_extrema (float a, float b, float c, float w, float t[10])
-{
- float q, tt;
- int n = 0;
- float w2 = w*w;
- float wac = (w - 1)*(a - c);
-
- if (wac != 0)
- {
- q = - sqrt (a*a - 4*a*b*w2 + 4*a*c*w2 - 2*a*c + 4*b*b*w2 - 4*b*c*w2 + c*c);
-
- tt = (- q + 2*a*w - a - 2*b*w + c)/(2*wac);
-
- if (acceptable (tt))
- t[n++] = tt;
-
- tt = (q + 2*a*w - a - 2*b*w + c)/(2*wac);
-
- if (acceptable (tt))
- t[n++] = tt;
- }
-
- if (w * (b - c) != 0 && a == c)
- t[n++] = 0.5;
-
- if (w == 1 && a - 2*b + c != 0)
- {
- tt = (a - b) / (a - 2*b + c);
- if (acceptable (tt))
- t[n++] = tt;
- }
-
- return n;
-}
-
-static void
-get_conic_bounds (const graphene_point_t p[3],
- float w,
- graphene_rect_t *bounds)
-{
- graphene_point_t q;
- float t[10];
- int i, n;
-
- graphene_rect_init (bounds, p[0].x, p[0].y, 0, 0);
- graphene_rect_expand (bounds, &p[2], bounds);
-
- n = get_conic_extrema (p[0].x, p[1].x, p[2].x, w, t);
- n += get_conic_extrema (p[0].y, p[1].y, p[2].y, w, &t[n]);
-
- for (i = 0; i < n; i++)
- {
- get_conic (p, w, t[i], &q);
- graphene_rect_expand (bounds, &q, bounds);
- }
-}
-
/* compute the angle between a, b and c in the range of [0, 360] */
static float
three_point_angle (const graphene_point_t *a,
@@ -516,50 +410,6 @@ get_cubic_roots (float pa,
return n_roots;
}
-static int
-get_cubic_extrema (float pa,
- float pb,
- float pc,
- float pd,
- float roots[2])
-{
- float a, b, c;
- float d, t;
- int n_roots = 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);
- t = (-b + d)/(2*a);
- if (acceptable (t))
- roots[n_roots++] = t;
- t = (-b - d)/(2*a);
- if (acceptable (t))
- roots[n_roots++] = t;
- }
- else
- {
- t = -b / (2*a);
- if (acceptable (t))
- roots[n_roots++] = t;
- }
- }
- else if (fabs (b) > 0.0001)
- {
- t = -c / b;
- if (acceptable (t))
- roots[n_roots++] = t;
- }
-
- return n_roots;
-}
-
/* Compute q = p + d * n */
static void
scale_point (const graphene_point_t *p,
@@ -663,58 +513,420 @@ line_curve_intersection (const graphene_point_t *a,
return n;
}
+typedef struct _Curve Curve;
+typedef struct _CurveClass CurveClass;
+
+struct _Curve
+{
+ CurveClass *class;
+ graphene_point_t p[4];
+ float weight;
+};
+
+struct _CurveClass
+{
+ const char *name;
+ void (* get_bounds) (Curve *self, graphene_rect_t *bounds);
+ void (* get_point) (Curve *self, float t, graphene_point_t *point);
+ void (* split) (Curve *self, float t, Curve *left, Curve *right);
+};
+
+static void
+line_segment_get_bounds (Curve *c, graphene_rect_t *bounds)
+{
+ graphene_rect_init (bounds, c->p[0].x, c->p[0].y, 0, 0);
+ graphene_rect_expand (bounds, &c->p[1], bounds);
+}
+
+static void
+line_segment_get_point (Curve *c, float t, graphene_point_t *point)
+{
+ point->x = (1 - t) * c->p[0].x + t * c->p[1].x;
+ point->y = (1 - t) * c->p[0].y + t * c->p[1].y;
+}
+
+static void init_line_segment (Curve *c,
+ graphene_point_t *a,
+ graphene_point_t *b);
+
+static void
+line_segment_split (Curve *c, float t, Curve *left, Curve *right)
+{
+ graphene_point_t p;
+
+ line_segment_get_point (c, t, &p);
+ init_line_segment (left, &c->p[0], &p);
+ init_line_segment (right, &p, &c->p[1]);
+}
+
+static CurveClass LINE_SEGMENT_CLASS =
+{
+ "LineSegment",
+ line_segment_get_bounds,
+ line_segment_get_point,
+ line_segment_split
+};
+
+static void
+init_line_segment (Curve *c,
+ graphene_point_t *a,
+ graphene_point_t *b)
+{
+ c->class = &LINE_SEGMENT_CLASS;
+ c->p[0] = *a;
+ c->p[1] = *b;
+}
+
+static void
+cubic_get_point (Curve *c, float t, graphene_point_t *point)
+{
+ get_bezier (c->p, 4, t, point);
+}
+
+static int
+get_cubic_extrema (float pa,
+ float pb,
+ float pc,
+ float pd,
+ float roots[2])
+{
+ float a, b, c;
+ float d, t;
+ int n_roots = 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);
+ t = (-b + d)/(2*a);
+ if (acceptable (t))
+ roots[n_roots++] = t;
+ t = (-b - d)/(2*a);
+ if (acceptable (t))
+ roots[n_roots++] = t;
+ }
+ else
+ {
+ t = -b / (2*a);
+ if (acceptable (t))
+ roots[n_roots++] = t;
+ }
+ }
+ else if (fabs (b) > 0.0001)
+ {
+ t = -c / b;
+ if (acceptable (t))
+ roots[n_roots++] = t;
+ }
+
+ return n_roots;
+}
+
static void
-get_curve_bounds (const graphene_point_t pts[4],
- graphene_rect_t *bounds)
+cubic_get_bounds (Curve *c, graphene_rect_t *bounds)
{
graphene_point_t p;
- float t[2];
+ float t[4];
int n, i;
- graphene_rect_init (bounds, pts[0].x, pts[0].y, 0, 0);
- graphene_rect_expand (bounds, &pts[3], bounds);
+ graphene_rect_init (bounds, c->p[0].x, c->p[0].y, 0, 0);
+ graphene_rect_expand (bounds, &c->p[3], bounds);
- n = get_cubic_extrema (pts[0].x, pts[1].x, pts[2].x, pts[3].x, t);
+ n = get_cubic_extrema (c->p[0].x, c->p[1].x, c->p[2].x, c->p[3].x, t);
+ n += get_cubic_extrema (c->p[0].y, c->p[1].y, c->p[2].y, c->p[3].y, &t[n]);
for (i = 0; i < n; i++)
{
- get_cubic (pts, t[i], &p);
+ cubic_get_point (c, t[i], &p);
graphene_rect_expand (bounds, &p, bounds);
}
+}
+
+static void init_cubic (Curve *c,
+ graphene_point_t p[4]);
+
+static void
+cubic_split (Curve *c, float t, Curve *left, Curve *right)
+{
+ split_bezier (c->p, 4, t, left->p, right->p);
+ init_cubic (left, left->p);
+ init_cubic (right, right->p);
+}
+
+static CurveClass CUBIC_CLASS =
+{
+ "Cubic",
+ cubic_get_bounds,
+ cubic_get_point,
+ cubic_split
+};
+
+static void
+init_cubic (Curve *c,
+ graphene_point_t p[4])
+{
+ c->class = &CUBIC_CLASS;
+ c->p[0] = p[0];
+ c->p[1] = p[1];
+ c->p[2] = p[2];
+ c->p[3] = p[3];
+}
+
+static void
+conic_get_point (Curve *c, float t, graphene_point_t *point)
+{
+ get_rational_bezier (c->p, (float [3]) { 1, c->weight, 1}, 3, t, point);
+}
+
+/* Solve N = 0 where N is the numerator of derivative of P/Q, with
+ * P = (1-t)^a + 2t(1-t)wb + t^2c
+ * Q = (1-t)^2 + 2t(1-t)w + t^2
+ */
+static int
+get_conic_extrema (float a, float b, float c, float w, float t[10])
+{
+ float q, tt;
+ int n = 0;
+ float w2 = w*w;
+ float wac = (w - 1)*(a - c);
+
+ if (wac != 0)
+ {
+ q = - sqrt (a*a - 4*a*b*w2 + 4*a*c*w2 - 2*a*c + 4*b*b*w2 - 4*b*c*w2 + c*c);
+
+ tt = (- q + 2*a*w - a - 2*b*w + c)/(2*wac);
+
+ if (acceptable (tt))
+ t[n++] = tt;
+
+ tt = (q + 2*a*w - a - 2*b*w + c)/(2*wac);
+
+ if (acceptable (tt))
+ t[n++] = tt;
+ }
+
+ if (w * (b - c) != 0 && a == c)
+ t[n++] = 0.5;
+
+ if (w == 1 && a - 2*b + c != 0)
+ {
+ tt = (a - b) / (a - 2*b + c);
+ if (acceptable (tt))
+ t[n++] = tt;
+ }
+
+ return n;
+}
+
+static void
+conic_get_bounds (Curve *c,
+ graphene_rect_t *bounds)
+{
+ graphene_point_t p;
+ float t[10];
+ int i, n;
+
+ graphene_rect_init (bounds, c->p[0].x, c->p[0].y, 0, 0);
+ graphene_rect_expand (bounds, &c->p[2], bounds);
+
+ n = get_conic_extrema (c->p[0].x, c->p[1].x, c->p[2].x, c->weight, t);
+ n += get_conic_extrema (c->p[0].y, c->p[1].y, c->p[2].y, c->weight, &t[n]);
- n = get_cubic_extrema (pts[0].y, pts[1].y, pts[2].y, pts[3].y, t);
for (i = 0; i < n; i++)
{
- get_cubic (pts, t[i], &p);
+ conic_get_point (c, t[i], &p);
graphene_rect_expand (bounds, &p, bounds);
}
}
+static void init_conic (Curve *c,
+ graphene_point_t p[3],
+ float weight);
+
+static void
+conic_split (Curve *c, float t, Curve *left, Curve *right)
+{
+ /* Given control points and weight for a rational quadratic
+ * Bezier and t, create two sets of the same that give the
+ * same curve as the original and split the curve at t.
+ */
+ graphene_point3d_t p[3];
+ graphene_point3d_t l[3], r[3];
+ int i;
+
+ /* do de Casteljau in homogeneous coordinates... */
+ for (i = 0; i < 3; i++)
+ {
+ p[i].x = c->p[i].x;
+ p[i].y = c->p[i].y;
+ p[i].z = 1;
+ }
+
+ p[1].x *= c->weight;
+ p[1].y *= c->weight;
+ p[1].z *= c->weight;
+
+ split_bezier3d (p, 3, t, l, r);
+
+ /* then project the control points down */
+ for (i = 0; i < 3; i++)
+ {
+ left->p[i].x = l[i].x / l[i].z;
+ left->p[i].y = l[i].y / l[i].z;
+ right->p[i].x = r[i].x / r[i].z;
+ right->p[i].y = r[i].y / r[i].z;
+ }
+
+ /* normalize the outer weights to be 1 by using
+ * the fact that weights w_i and c*w_i are equivalent
+ * for any nonzero constant c
+ */
+ for (i = 0; i < 3; i++)
+ {
+ l[i].z /= l[0].z;
+ r[i].z /= r[2].z;
+ }
+
+ /* normalize the inner weight to be 1 by using
+ * the fact that w_0*w_2/w_1^2 is a constant for
+ * all equivalent weights.
+ */
+ left->weight = l[1].z / sqrt (l[2].z);
+ right->weight = r[1].z / sqrt (r[0].z);
+
+ init_conic (left, left->p, left->weight);
+ init_conic (right, right->p, right->weight);
+}
+
+static CurveClass CONIC_CLASS =
+{
+ "Conic",
+ conic_get_bounds,
+ conic_get_point,
+ conic_split
+};
+
+static void
+init_conic (Curve *c,
+ graphene_point_t p[3],
+ float weight)
+{
+ c->class = &CONIC_CLASS;
+ c->p[0] = p[0];
+ c->p[1] = p[1];
+ c->p[2] = p[2];
+ c->weight = weight;
+};
+
+static void
+curve_get_bounds (Curve *curve, graphene_rect_t *bounds)
+{
+ curve->class->get_bounds (curve, bounds);
+}
+
static void
-curve_intersection_recurse (const graphene_point_t pts1[4],
- const graphene_point_t pts2[4],
- float t1,
- float t2,
- float s1,
- float s2,
- float t[9],
- float s[9],
- graphene_point_t q[9],
- int *pos)
+curve_get_point (Curve *curve, float t, graphene_point_t *point)
+{
+ curve->class->get_point (curve, t, point);
+}
+
+static void
+curve_split (Curve *curve, float t, Curve *left, Curve *right)
+{
+ curve->class->split (curve, t, left, right);
+}
+
+static void
+init_curve (Curve *c,
+ GskPathOperation op,
+ graphene_point_t p[4],
+ float w)
+{
+ switch (op)
+ {
+ case GSK_PATH_CLOSE:
+ case GSK_PATH_LINE:
+ init_line_segment (c, &p[0], &p[1]);
+ break;
+
+ case GSK_PATH_CURVE:
+ init_cubic (c, p);
+ break;
+
+ case GSK_PATH_CONIC:
+ init_conic (c, p, w);
+ break;
+
+ case GSK_PATH_MOVE:
+ default:
+ g_assert_not_reached ();
+ }
+}
+
+static int
+line_segment_intersection (const graphene_point_t *p1,
+ const graphene_point_t *p2,
+ const graphene_point_t *p3,
+ const graphene_point_t *p4,
+ float *t,
+ float *s,
+ graphene_point_t *p)
+{
+ float a1 = p2->x - p1->x;
+ float b1 = p2->y - p1->y;
+
+ float a2 = p4->x - p3->x;
+ float b2 = p4->y - p3->y;
+
+ float det = a1 * b2 - a2 * b1;
+ float tt, ss;
+
+ if (det != 0)
+ {
+ tt = ((p3->x - p1->x) * b2 - (p3->y - p1->y) * a2) / det;
+ ss = ((p3->y - p1->y) * a2 - (p3->x - p1->x) * b1) / det;
+
+ if (acceptable (tt) && acceptable (ss))
+ {
+ p->x = p1->x + tt * (p2->x - p1->x);
+ p->y = p1->y + tt * (p2->y - p1->y);
+
+ *t = tt;
+ *s = ss;
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
+static void
+intersection_recurse (Curve *c1,
+ Curve *c2,
+ float t1,
+ float t2,
+ float s1,
+ float s2,
+ float *t,
+ float *s,
+ graphene_point_t *q,
+ int n,
+ int *pos)
{
graphene_rect_t b1, b2;
float d;
float e;
-
- graphene_point_t p11[4];
- graphene_point_t p12[4];
- graphene_point_t p21[4];
- graphene_point_t p22[4];
+ Curve p11, p12, p21, p22;
if (*pos == 9)
return;
- get_curve_bounds (pts1, &b1);
- get_curve_bounds (pts2, &b2);
+ curve_get_bounds (c1, &b1);
+ curve_get_bounds (c2, &b2);
if (!graphene_rect_intersection (&b1, &b2, NULL))
return;
@@ -727,43 +939,66 @@ curve_intersection_recurse (const graphene_point_t pts1[4],
{
t[*pos] = t1 + d;
s[*pos] = s1 + e;
- get_cubic (pts1, 0.5, &q[*pos]);
+ curve_get_point (c1, 0.5, &q[*pos]);
(*pos)++;
return;
}
- split_bezier (pts1, 4, 0.5, p11, p12);
- split_bezier (pts2, 4, 0.5, p21, p22);
+ curve_split (c1, 0.5, &p11, &p12);
+ curve_split (c2, 0.5, &p21, &p22);
- curve_intersection_recurse (p11, p21, t1, t1 + d, s1, s1 + e, t, s, q, pos);
- curve_intersection_recurse (p11, p22, t1, t1 + d, s1 + e, s2, t, s, q, pos);
- curve_intersection_recurse (p12, p21, t1 + d, t2, s1, s1 + e, t, s, q, pos);
- curve_intersection_recurse (p12, p22, t1 + d, t2, s1 + e, s2, t, s, q, pos);
+ intersection_recurse (&p11, &p21, t1, t1 + d, s1, s1 + e, t, s, q, n, pos);
+ intersection_recurse (&p11, &p22, t1, t1 + d, s1 + e, s2, t, s, q, n, pos);
+ intersection_recurse (&p12, &p21, t1 + d, t2, s1, s1 + e, t, s, q, n, pos);
+ intersection_recurse (&p12, &p22, t1 + d, t2, s1 + e, s2, t, s, q, n, pos);
}
/* Place intersections between the curves in q, and
- * their Bezier positions in t and s.
- * Return the number of intersections found (0 to 9).
+ * their Bezier positions in t and s, up to n.
+ * Return the number of intersections found.
*/
static int
-curve_intersection (const graphene_point_t pts1[4],
- const graphene_point_t pts2[4],
- float t[9],
- float s[9],
- graphene_point_t q[9])
+curve_intersection (Curve *c1,
+ Curve *c2,
+ float *t,
+ float *s,
+ graphene_point_t *q,
+ int n)
{
- int pos = 0;
+ int i, pos;
- curve_intersection_recurse (pts1, pts2, 0, 1, 0, 1, t, s, q, &pos);
- return pos;
+ if (c1->class == &LINE_SEGMENT_CLASS && c2->class == &LINE_SEGMENT_CLASS)
+ {
+ return line_segment_intersection (&c1->p[0], &c1->p[1], &c2->p[0], &c2->p[1], t, s, q);
+ }
+ else if (c1->class == &LINE_SEGMENT_CLASS && c2->class == &CUBIC_CLASS)
+ {
+ pos = line_curve_intersection (&c1->p[0], &c1->p[1], c2->p, s, q);
+ for (i = 0; i < pos; i++)
+ find_point_on_line (&c1->p[0], &c1->p[1], &q[i], &t[i]);
+ return pos;
+ }
+ else if (c1->class == &CUBIC_CLASS && c2->class == &LINE_SEGMENT_CLASS)
+ {
+ pos = line_curve_intersection (&c2->p[0], &c2->p[1], c1->p, t, q);
+ for (i = 0; i < pos; i++)
+ find_point_on_line (&c2->p[0], &c2->p[1], &q[i], &s[i]);
+ return pos;
+ }
+ else
+ {
+ pos = 0;
+ intersection_recurse (c1, c2, 0, 1, 0, 1, t, s, q, n, &pos);
+ return pos;
+ }
}
-
typedef struct
{
GskPathOperation op;
int n_pts;
graphene_point_t pts[4]; /* points of the curve */
+ float w;
graphene_point_t r[4]; /* offset to the right */
graphene_point_t l[4]; /* offset to the left */
@@ -877,12 +1112,11 @@ compute_intersections (PathOpData *op1,
if (fabs (op1->angle[1] - 180.f) >= 1)
{
- graphene_point_t left[4];
- graphene_point_t right[4];
graphene_point_t p[9];
float t[9];
float s[9];
int i, n;
+ Curve c1, c2, cl, cr;
if (!line_intersection (&op1->r[op1->n_pts - 2], &op1->r[op1->n_pts - 1],
&op2->r[0], &op2->r[1],
@@ -894,93 +1128,40 @@ compute_intersections (PathOpData *op1,
&op1->le[1]))
midpoint (&op1->l[op1->n_pts - 1], &op2->l[0], &op1->le[1]);
- if (op1->n_pts == 2 && op2->n_pts == 4)
- {
- if (op1->angle[1] > 180.f)
- {
- n = line_curve_intersection (&op1->r[0], &op1->r[1], op2->r, t, p);
- if (n > 0)
- {
- i = find_smallest (t, n);
- op1->re[1] = p[i];
- split_bezier (op2->r, 4, t[i], left, right);
- for (i = 0; i < 4; i++)
- op2->r[i] = right[i];
- }
- }
- else
- {
- n = line_curve_intersection (&op1->l[0], &op1->l[1], op2->l, t, p);
- if (n > 0)
- {
- i = find_smallest (t, n);
- op1->le[1] = p[i];
- split_bezier (op2->l, 4, t[i], left, right);
- for (i = 0; i < 4; i++)
- op2->l[i] = right[i];
- }
- }
- }
- else if (op1->n_pts == 4 && op2->n_pts == 2)
+ if (op1->angle[1] > 180.f)
{
- if (op1->angle[1] > 180.f)
+ init_curve (&c1, op1->op, op1->r, op1->w);
+ init_curve (&c2, op2->op, op2->r, op2->w);
+ n = curve_intersection (&c1, &c2, t, s, p, 9);
+ if (n > 0)
{
- n = line_curve_intersection (&op2->r[0], &op2->r[1], op1->r, t, p);
- if (n > 0)
- {
- i = find_largest (t, n);
- op1->re[1] = p[i];
- split_bezier (op1->r, 4, t[i], left, right);
- for (i = 0; i < 4; i++)
- op1->r[i] = left[i];
- }
- }
- else
- {
- n = line_curve_intersection (&op2->l[0], &op2->l[1], op1->l, t, p);
- if (n > 0)
- {
- i = find_largest (t, n);
- op1->le[1] = p[i];
- split_bezier (op1->l, 4, t[i], left, right);
- for (i = 0; i < 4; i++)
- op1->l[i] = left[i];
- }
+ i = find_largest (t, n);
+ curve_split (&c1, t[i], &cl, &cr);
+ for (i = 0; i < op1->n_pts; i++)
+ op1->r[i] = cl.p[i];
+ op1->re[1] = op1->r[op1->n_pts - 1];
+ i = find_smallest (s, n);
+ curve_split (&c2, s[i], &cl, &cr);
+ for (i = 0; i < op2->n_pts; i++)
+ op2->r[i] = cr.p[i];
}
}
- else if (op1->n_pts == 4 && op2->n_pts == 4)
+ else
{
- if (op1->angle[1] > 180.f)
- {
- n = curve_intersection (op1->r, op2->r, t, s, p);
- if (n > 0)
- {
- i = find_largest (t, n);
- split_bezier (op1->r, 4, t[i], left, right);
- for (i = 0; i < 4; i++)
- op1->r[i] = left[i];
- op1->re[1] = op1->r[3];
- i = find_smallest (s, n);
- split_bezier (op2->r, 4, s[i], left, right);
- for (i = 0; i < 4; i++)
- op2->r[i] = right[i];
- }
- }
- else
+ init_curve (&c1, op1->op, op1->l, op1->w);
+ init_curve (&c2, op2->op, op2->l, op2->w);
+ n = curve_intersection (&c1, &c2, t, s, p, 9);
+ if (n > 0)
{
- n = curve_intersection (op1->l, op2->l, t, s, p);
- if (n > 0)
- {
- i = find_largest (t, n);
- split_bezier (op1->l, 4, t[i], left, right);
- for (i = 0; i < 4; i++)
- op1->l[i] = left[i];
- op1->le[1] = op1->l[3];
- i = find_smallest (s, n);
- split_bezier (op2->l, 4, s[i], left, right);
- for (i = 0; i < 4; i++)
- op2->l[i] = right[i];
- }
+ i = find_largest (t, n);
+ curve_split (&c1, t[i], &cl, &cr);
+ for (i = 0; i < op1->n_pts; i++)
+ op1->l[i] = cl.p[i];
+ op1->le[1] = op1->l[op1->n_pts - 1];
+ i = find_smallest (s, n);
+ curve_split (&c2, s[i], &cl, &cr);
+ for (i = 0; i < op2->n_pts; i++)
+ op2->l[i] = cr.p[i];
}
}
}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
