[gtk/path-work-rebased: 91/123] curve: Add gsk_curve_offset

[Matthias Clasen <matthiasc src gnome org>]

commit c6de75dabe61fa8a432f1e19fcbcf779ffb93c7f
Author: Matthias Clasen <mclasen redhat com>
Date:   Thu Dec 10 18:19:28 2020 -0500

    curve: Add gsk_curve_offset
    
    This method creates an offset curve from an existing
    curve by just moving the control points laterally.
    
    This will be used in stroking.

 gsk/gskcurve.c        | 152 +++++++++++++++++++++++++++++++++++++++++++++++++-
 gsk/gskcurveprivate.h |   4 ++
 2 files changed, 153 insertions(+), 3 deletions(-)
---
diff --git a/gsk/gskcurve.c b/gsk/gskcurve.c
index 064a777786..3d760efe99 100644
--- a/gsk/gskcurve.c
+++ b/gsk/gskcurve.c
@@ -67,6 +67,9 @@ struct _GskCurveClass
                                                          GskBoundingBox         *bounds);
   void                          (* get_tight_bounds)    (const GskCurve         *curve,
                                                          GskBoundingBox         *bounds);
+  void                          (* offset)              (const GskCurve         *curve,
+                                                         float                   distance,
+                                                         GskCurve               *offset_curve);
 };
 
 /* {{{ Line implementation */
@@ -80,6 +83,60 @@ get_tangent (const graphene_point_t *p0,
   graphene_vec2_normalize (t, t);
 }
 
+static void
+get_normal (const graphene_point_t *p0,
+            const graphene_point_t *p1,
+            graphene_vec2_t        *n)
+{
+  graphene_vec2_init (n, p0->y - p1->y, p1->x - p0->x);
+  graphene_vec2_normalize (n, n);
+}
+
+/* Compute q = p + d * n */
+static void
+scale_point (const graphene_point_t *p,
+             const graphene_vec2_t  *n,
+             float                   d,
+             graphene_point_t       *q)
+{
+  q->x = p->x + d * graphene_vec2_get_x (n);
+  q->y = p->y + d * graphene_vec2_get_y (n);
+}
+
+/* Set p to the intersection of the lines through a, b and c, d.
+ * Return the number of intersections found (0 or 1)
+ */
+static int
+line_intersection (const graphene_point_t *a,
+                   const graphene_point_t *b,
+                   const graphene_point_t *c,
+                   const graphene_point_t *d,
+                   graphene_point_t       *p)
+{
+  float a1 = b->y - a->y;
+  float b1 = a->x - b->x;
+  float c1 = a1*a->x + b1*a->y;
+
+  float a2 = d->y - c->y;
+  float b2 = c->x - d->x;
+  float c2 = a2*c->x+ b2*c->y;
+
+  float det = a1*b2 - a2*b1;
+
+  if (fabs (det) < 0.001)
+    {
+      p->x = NAN;
+      p->y = NAN;
+      return 0;
+    }
+  else
+    {
+      p->x = (b2*c1 - b1*c2) / det;
+      p->y = (a1*c2 - a2*c1) / det;
+      return 1;
+    }
+}
+
 static void
 gsk_line_curve_init_from_points (GskLineCurve           *self,
                                  GskPathOperation        op,
@@ -238,6 +295,23 @@ gsk_line_curve_get_bounds (const GskCurve  *curve,
   gsk_bounding_box_init (bounds, &pts[0], &pts[1]);
 }
 
+static void
+gsk_line_curve_offset (const GskCurve *curve,
+                       float           distance,
+                       GskCurve       *offset_curve)
+{
+  const GskLineCurve *self = &curve->line;
+  const graphene_point_t *pts = self->points;
+  graphene_vec2_t n;
+  graphene_point_t p[4];
+
+  get_normal (&pts[0], &pts[1], &n);
+  scale_point (&pts[0], &n, distance, &p[0]);
+  scale_point (&pts[1], &n, distance, &p[1]);
+
+  gsk_curve_init (offset_curve, gsk_pathop_encode (GSK_PATH_LINE, p));
+}
+
 static const GskCurveClass GSK_LINE_CURVE_CLASS = {
   gsk_line_curve_init,
   gsk_line_curve_init_foreach,
@@ -253,7 +327,8 @@ static const GskCurveClass GSK_LINE_CURVE_CLASS = {
   gsk_line_curve_get_start_end_tangent,
   gsk_line_curve_get_start_end_tangent,
   gsk_line_curve_get_bounds,
-  gsk_line_curve_get_bounds
+  gsk_line_curve_get_bounds,
+  gsk_line_curve_offset
 };
 
 /* }}} */
@@ -566,6 +641,39 @@ gsk_curve_curve_get_tight_bounds (const GskCurve  *curve,
     }
 }
 
+static void
+gsk_curve_curve_offset (const GskCurve *curve,
+                        float           distance,
+                        GskCurve       *offset)
+{
+  const GskCurveCurve *self = &curve->curve;
+  const graphene_point_t *pts = self->points;
+  graphene_vec2_t n;
+  graphene_point_t p[4];
+  graphene_point_t m1, m2, m3, m4;
+
+  /* Simply scale control points, a la Tiller and Hanson */
+  get_normal (&pts[0], &pts[1], &n);
+  scale_point (&pts[0], &n, distance, &p[0]);
+  scale_point (&pts[1], &n, distance, &m1);
+
+  get_normal (&pts[1], &pts[2], &n);
+  scale_point (&pts[1], &n, distance, &m2);
+  scale_point (&pts[2], &n, distance, &m3);
+
+  get_normal (&pts[2], &pts[3], &n);
+  scale_point (&pts[2], &n, distance, &m4);
+  scale_point (&pts[3], &n, distance, &p[3]);
+
+  if (!line_intersection (&p[0], &m1, &m2, &m3, &p[1]))
+    p[1] = m1;
+
+  if (!line_intersection (&m2, &m3, &m4, &p[3], &p[2]))
+    p[2] = m4;
+
+  gsk_curve_curve_init_from_points (&offset->curve, p);
+}
+
 static const GskCurveClass GSK_CURVE_CURVE_CLASS = {
   gsk_curve_curve_init,
   gsk_curve_curve_init_foreach,
@@ -581,7 +689,8 @@ static const GskCurveClass GSK_CURVE_CURVE_CLASS = {
   gsk_curve_curve_get_start_tangent,
   gsk_curve_curve_get_end_tangent,
   gsk_curve_curve_get_bounds,
-  gsk_curve_curve_get_tight_bounds
+  gsk_curve_curve_get_tight_bounds,
+  gsk_curve_curve_offset
 };
 
 /* }}} */
@@ -1145,6 +1254,34 @@ gsk_conic_curve_get_tight_bounds (const GskCurve *curve,
     }
 }
 
+static void
+gsk_conic_curve_offset (const GskCurve *curve,
+                        float           distance,
+                        GskCurve       *offset)
+{
+  const GskConicCurve *self = &curve->conic;
+  const graphene_point_t *pts = self->points;
+  graphene_vec2_t n;
+  graphene_point_t p[4];
+  graphene_point_t m1, m2;
+
+  /* Simply scale control points, a la Tiller and Hanson */
+  get_normal (&pts[0], &pts[1], &n);
+  scale_point (&pts[0], &n, distance, &p[0]);
+  scale_point (&pts[1], &n, distance, &m1);
+
+  get_normal (&pts[1], &pts[3], &n);
+  scale_point (&pts[1], &n, distance, &m2);
+  scale_point (&pts[3], &n, distance, &p[3]);
+
+  if (!line_intersection (&p[0], &m1, &m2, &p[3], &p[1]))
+    p[1] = m1;
+
+  p[2] = pts[2];
+
+  gsk_conic_curve_init_from_points (&offset->conic, p);
+}
+
 static const GskCurveClass GSK_CONIC_CURVE_CLASS = {
   gsk_conic_curve_init,
   gsk_conic_curve_init_foreach,
@@ -1160,7 +1297,8 @@ static const GskCurveClass GSK_CONIC_CURVE_CLASS = {
   gsk_conic_curve_get_start_tangent,
   gsk_conic_curve_get_end_tangent,
   gsk_conic_curve_get_bounds,
-  gsk_conic_curve_get_tight_bounds
+  gsk_conic_curve_get_tight_bounds,
+  gsk_conic_curve_offset
 };
 
 /* }}} */
@@ -1302,6 +1440,14 @@ gsk_curve_get_tight_bounds (const GskCurve  *curve,
   get_class (curve->op)->get_tight_bounds (curve, bounds);
 }
 
+void
+gsk_curve_offset (const GskCurve *curve,
+                  float           distance,
+                  GskCurve       *offset_curve)
+{
+  get_class (curve->op)->offset (curve, distance, offset_curve);
+}
+
 /* }}} */
 
 /* vim:set foldmethod=marker expandtab: */
diff --git a/gsk/gskcurveprivate.h b/gsk/gskcurveprivate.h
index e194f52886..cec1956716 100644
--- a/gsk/gskcurveprivate.h
+++ b/gsk/gskcurveprivate.h
@@ -136,6 +136,10 @@ int                     gsk_curve_intersect                     (const GskCurve
                                                                  graphene_point_t       *p,
                                                                  int                     n);
 
+void                    gsk_curve_offset                        (const GskCurve         *curve,
+                                                                 float                   distance,
+                                                                 GskCurve               *offset_curve);
+
 G_END_DECLS
 
 #endif /* __GSK_CURVE_PRIVATE_H__ */