[gtk/path-work-rebased: 27/36] curve: Use GskBoundingBox
- From: Matthias Clasen <matthiasc src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/path-work-rebased: 27/36] curve: Use GskBoundingBox
- Date: Thu, 7 Apr 2022 03:51:35 +0000 (UTC)
commit cf793f94acf7694e71a2198b5ec4385ff864371a
Author: Matthias Clasen <mclasen redhat com>
Date: Mon Mar 21 01:26:51 2022 -0400
curve: Use GskBoundingBox
gsk/gskcurve.c | 49 +++++++---------
gsk/gskcurveintersect.c | 35 ++++++-----
gsk/gskcurveprivate.h | 8 ++-
testsuite/gsk/curve.c | 150 ++++++++++++++++++++++++++++++++++++++++++++++--
4 files changed, 188 insertions(+), 54 deletions(-)
---
diff --git a/gsk/gskcurve.c b/gsk/gskcurve.c
index 1e6673062e..2f1894f297 100644
--- a/gsk/gskcurve.c
+++ b/gsk/gskcurve.c
@@ -64,9 +64,9 @@ struct _GskCurveClass
void (* get_end_tangent) (const GskCurve *curve,
graphene_vec2_t *tangent);
void (* get_bounds) (const GskCurve *curve,
- graphene_rect_t *bounds);
+ GskBoundingBox *bounds);
void (* get_tight_bounds) (const GskCurve *curve,
- graphene_rect_t *bounds);
+ GskBoundingBox *bounds);
void (* offset) (const GskCurve *curve,
float distance,
GskCurve *offset_curve);
@@ -291,13 +291,12 @@ gsk_line_curve_get_start_end_tangent (const GskCurve *curve,
static void
gsk_line_curve_get_bounds (const GskCurve *curve,
- graphene_rect_t *bounds)
+ GskBoundingBox *bounds)
{
const GskLineCurve *self = &curve->line;
const graphene_point_t *pts = self->points;
- graphene_rect_init (bounds, pts[0].x, pts[0].y, 0, 0);
- graphene_rect_expand (bounds, &pts[1], bounds);
+ gsk_bounding_box_init (bounds, &pts[0], &pts[1]);
}
static void
@@ -598,15 +597,14 @@ gsk_curve_curve_get_end_tangent (const GskCurve *curve,
static void
gsk_curve_curve_get_bounds (const GskCurve *curve,
- graphene_rect_t *bounds)
+ GskBoundingBox *bounds)
{
const GskCurveCurve *self = &curve->curve;
const graphene_point_t *pts = self->points;
- graphene_rect_init (bounds, pts[0].x, pts[0].y, 0, 0);
- graphene_rect_expand (bounds, &pts[1], bounds);
- graphene_rect_expand (bounds, &pts[2], bounds);
- graphene_rect_expand (bounds, &pts[3], bounds);
+ gsk_bounding_box_init (bounds, &pts[0], &pts[3]);
+ gsk_bounding_box_expand (bounds, &pts[1]);
+ gsk_bounding_box_expand (bounds, &pts[2]);
}
static inline gboolean
@@ -660,15 +658,14 @@ get_cubic_extrema (float pa, float pb, float pc, float pd, float t[2])
static void
gsk_curve_curve_get_tight_bounds (const GskCurve *curve,
- graphene_rect_t *bounds)
+ GskBoundingBox *bounds)
{
const GskCurveCurve *self = &curve->curve;
const graphene_point_t *pts = self->points;
float t[4];
int n;
- graphene_rect_init (bounds, pts[0].x, pts[0].y, 0, 0);
- graphene_rect_expand (bounds, &pts[3], bounds);
+ gsk_bounding_box_init (bounds, &pts[0], &pts[3]);
n = 0;
n += get_cubic_extrema (pts[0].x, pts[1].x, pts[2].x, pts[3].x, &t[n]);
@@ -679,7 +676,7 @@ gsk_curve_curve_get_tight_bounds (const GskCurve *curve,
graphene_point_t p;
gsk_curve_curve_get_point (curve, t[i], &p);
- graphene_rect_expand (bounds, &p, bounds);
+ gsk_bounding_box_expand (bounds, &p);
}
}
@@ -1379,15 +1376,14 @@ gsk_conic_curve_get_end_tangent (const GskCurve *curve,
}
static void
-gsk_conic_curve_get_bounds (const GskCurve *curve,
- graphene_rect_t *bounds)
+gsk_conic_curve_get_bounds (const GskCurve *curve,
+ GskBoundingBox *bounds)
{
const GskCurveCurve *self = &curve->curve;
const graphene_point_t *pts = self->points;
- graphene_rect_init (bounds, pts[0].x, pts[0].y, 0, 0);
- graphene_rect_expand (bounds, &pts[1], bounds);
- graphene_rect_expand (bounds, &pts[3], bounds);
+ gsk_bounding_box_init (bounds, &pts[0], &pts[3]);
+ gsk_bounding_box_expand (bounds, &pts[1]);
}
/* Solve N = 0 where N is the numerator of (P/Q)', with
@@ -1431,8 +1427,8 @@ get_conic_extrema (float a, float b, float c, float w, float t[4])
}
static void
-gsk_conic_curve_get_tight_bounds (const GskCurve *curve,
- graphene_rect_t *bounds)
+gsk_conic_curve_get_tight_bounds (const GskCurve *curve,
+ GskBoundingBox *bounds)
{
const GskConicCurve *self = &curve->conic;
float w = gsk_conic_curve_get_weight (self);
@@ -1440,8 +1436,7 @@ gsk_conic_curve_get_tight_bounds (const GskCurve *curve,
float t[8];
int n;
- graphene_rect_init (bounds, pts[0].x, pts[0].y, 0, 0);
- graphene_rect_expand (bounds, &pts[3], bounds);
+ gsk_bounding_box_init (bounds, &pts[0], &pts[3]);
n = 0;
n += get_conic_extrema (pts[0].x, pts[1].x, pts[3].x, w, &t[n]);
@@ -1452,7 +1447,7 @@ gsk_conic_curve_get_tight_bounds (const GskCurve *curve,
graphene_point_t p;
gsk_conic_curve_get_point (curve, t[i], &p);
- graphene_rect_expand (bounds, &p, bounds);
+ gsk_bounding_box_expand (bounds, &p);
}
}
@@ -1559,7 +1554,7 @@ gsk_conic_curve_get_curvature (const GskCurve *curve,
p[2] = curve->conic.points[3];
w1[0] = (1 - t) + t*w;
- w1[1] = (1 - t)*w + t;
+w1[1] = (1 - t)*w + t;
w2 = (1 - t)*w1[0] + t*w1[1];
@@ -1743,14 +1738,14 @@ gsk_curve_get_end_tangent (const GskCurve *curve,
void
gsk_curve_get_bounds (const GskCurve *curve,
- graphene_rect_t *bounds)
+ GskBoundingBox *bounds)
{
get_class (curve->op)->get_bounds (curve, bounds);
}
void
gsk_curve_get_tight_bounds (const GskCurve *curve,
- graphene_rect_t *bounds)
+ GskBoundingBox *bounds)
{
get_class (curve->op)->get_tight_bounds (curve, bounds);
}
diff --git a/gsk/gskcurveintersect.c b/gsk/gskcurveintersect.c
index 1aa4c5b5ce..310ac40e68 100644
--- a/gsk/gskcurveintersect.c
+++ b/gsk/gskcurveintersect.c
@@ -363,7 +363,7 @@ curve_intersect_recurse (const GskCurve *curve1,
int *pos)
{
GskCurve p11, p12, p21, p22;
- graphene_rect_t b1, b2;
+ GskBoundingBox b1, b2;
float d1, d2;
if (*pos == n)
@@ -372,14 +372,14 @@ curve_intersect_recurse (const GskCurve *curve1,
gsk_curve_get_tight_bounds (curve1, &b1);
gsk_curve_get_tight_bounds (curve2, &b2);
- if (!graphene_rect_intersection (&b1, &b2, NULL))
+ if (!gsk_bounding_box_intersection (&b1, &b2, NULL))
return;
d1 = (t1r - t1l) / 2;
d2 = (t2r - t2l) / 2;
- if (b1.size.width < 0.1 && b1.size.height < 0.1 &&
- b2.size.width < 0.1 && b2.size.height < 0.1)
+ if (b1.max.x - b1.min.x < 0.1 && b1.max.y - b1.min.y < 0.1 &&
+ b2.max.x - b2.min.x < 0.1 && b2.max.y - b2.min.y < 0.1)
{
graphene_point_t c;
t1[*pos] = t1l + d1;
@@ -426,18 +426,12 @@ static void
get_bounds (const GskCurve *curve,
float tl,
float tr,
- graphene_rect_t *bounds)
+ GskBoundingBox *bounds)
{
GskCurve c;
gsk_curve_segment (curve, tl, tr, &c);
gsk_curve_get_tight_bounds (&c, bounds);
-
- /* FIXME this is working around inadequacies of
- * graphene_rect_t as bounding box
- */
- bounds->size.width += 0.0001;
- bounds->size.height += 0.0001;
}
static void
@@ -453,7 +447,7 @@ general_intersect_recurse (const GskCurve *curve1,
int n,
int *pos)
{
- graphene_rect_t b1, b2;
+ GskBoundingBox b1, b2;
float d1, d2;
if (*pos == n)
@@ -462,14 +456,14 @@ general_intersect_recurse (const GskCurve *curve1,
get_bounds (curve1, t1l, t1r, &b1);
get_bounds (curve2, t2l, t2r, &b2);
- if (!graphene_rect_intersection (&b1, &b2, NULL))
+ if (!gsk_bounding_box_intersection (&b1, &b2, NULL))
return;
d1 = (t1r - t1l) / 2;
d2 = (t2r - t2l) / 2;
- if (b1.size.width < 0.1 && b1.size.height < 0.1 &&
- b2.size.width < 0.1 && b2.size.height < 0.1)
+ if (b1.max.x - b1.min.x < 0.1 && b1.max.y - b1.min.y < 0.1 &&
+ b2.max.x - b2.min.x < 0.1 && b2.max.y - b2.min.y < 0.1)
{
graphene_point_t c;
t1[*pos] = t1l + d1;
@@ -547,24 +541,27 @@ curve_self_intersect (const GskCurve *curve,
m = gsk_curve_intersect (&cs, &ce, tt, ss, pp, 3);
+ g_print ("found %d intersections:", m);
+ for (int i = 0; i < m; i++) g_print (" %f", tt[i]);
+ g_print ("\n");
if (m > 1)
{
- if (tt[0] != 1)
+ if (fabs (tt[0] - 1) > 1e-4)
{
t1[0] = t2[0] = tt[0] * s;
p[0] = pp[0];
}
- else if (tt[1] != 1)
+ else if (fabs (tt[1] - 1) > 1e-4)
{
t1[0] = t2[0] = tt[1] * s;
p[0] = pp[1];
}
- if (ss[0] != 0)
+ if (fabs (ss[0]) > 1e-4)
{
t1[1] = t2[1] = s + ss[0] * (1 - s);
p[1] = pp[0];
}
- else if (ss[1] != 0)
+ else if (fabs (ss[1]) > 1e-4)
{
t1[1] = t2[1] = s + ss[1] * (1 - s);
p[1] = pp[1];
diff --git a/gsk/gskcurveprivate.h b/gsk/gskcurveprivate.h
index 108add18b4..5af65f6fa9 100644
--- a/gsk/gskcurveprivate.h
+++ b/gsk/gskcurveprivate.h
@@ -22,6 +22,7 @@
#define __GSK_CURVE_PRIVATE_H__
#include "gskpathopprivate.h"
+#include "gskboundingboxprivate.h"
G_BEGIN_DECLS
@@ -59,6 +60,9 @@ struct _GskConicCurve
gboolean has_coefficients;
+ /* points[0], points[1], points[3] are the control points,
+ * points[2].x is the weight
+ */
graphene_point_t points[4];
graphene_point_t num[3];
@@ -124,9 +128,9 @@ void gsk_curve_get_start_tangent (const GskCurve
void gsk_curve_get_end_tangent (const GskCurve *curve,
graphene_vec2_t *tangent);
void gsk_curve_get_bounds (const GskCurve *curve,
- graphene_rect_t *bounds);
+ GskBoundingBox *bounds);
void gsk_curve_get_tight_bounds (const GskCurve *curve,
- graphene_rect_t *bounds);
+ GskBoundingBox *bounds);
int gsk_curve_intersect (const GskCurve *curve1,
const GskCurve *curve2,
diff --git a/testsuite/gsk/curve.c b/testsuite/gsk/curve.c
index 7bae660ac5..5b6106e377 100644
--- a/testsuite/gsk/curve.c
+++ b/testsuite/gsk/curve.c
@@ -116,6 +116,36 @@ test_curve_points (void)
}
}
+static void
+test_curve_bounds (void)
+{
+ for (int i = 0; i < 100; i++)
+ {
+ GskCurve c;
+ GskBoundingBox bounds;
+ GskBoundingBox bounds2;
+ graphene_point_t p;
+
+ init_random_curve (&c);
+
+ gsk_curve_get_tight_bounds (&c, &bounds);
+ gsk_curve_get_bounds (&c, &bounds2);
+
+ g_assert_true (gsk_bounding_box_contains_point (&bounds, gsk_curve_get_start_point (&c)));
+ g_assert_true (gsk_bounding_box_contains_point (&bounds, gsk_curve_get_end_point (&c)));
+ g_assert_true (gsk_bounding_box_contains_point (&bounds2, gsk_curve_get_start_point (&c)));
+ g_assert_true (gsk_bounding_box_contains_point (&bounds2, gsk_curve_get_end_point (&c)));
+
+ for (int j = 0; j < 20; j++)
+ {
+ float t = g_test_rand_double_range (0, 1);
+ gsk_curve_get_point (&c, t, &p);
+ g_assert_true (gsk_bounding_box_contains_point (&bounds, &p));
+ g_assert_true (gsk_bounding_box_contains_point (&bounds2, &p));
+ }
+ }
+}
+
/* at this point the subdivision stops and the decomposer
* violates tolerance rules
*/
@@ -293,6 +323,31 @@ test_line_line_intersection (void)
g_assert_true (graphene_point_near (&p, &GRAPHENE_POINT_INIT (10, 10), 0.0001));
}
+static void
+test_line_line_end_intersection (void)
+{
+ GskCurve c1, c2;
+ graphene_point_t p1[2], p2[2];
+ float t1, t2;
+ graphene_point_t p;
+ int n;
+
+ graphene_point_init (&p1[0], 10, 0);
+ graphene_point_init (&p1[1], 10, 100);
+ graphene_point_init (&p2[0], 10, 100);
+ graphene_point_init (&p2[1], 100, 10);
+
+ gsk_curve_init (&c1, gsk_pathop_encode (GSK_PATH_LINE, p1));
+ gsk_curve_init (&c2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+ n = gsk_curve_intersect (&c1, &c2, &t1, &t2, &p, 1);
+
+ g_assert_cmpint (n, ==, 1);
+ g_assert_cmpfloat_with_epsilon (t1, 1, 0.0001);
+ g_assert_cmpfloat_with_epsilon (t2, 0, 0.0001);
+ g_assert_true (graphene_point_near (&p, &GRAPHENE_POINT_INIT (10, 100), 0.0001));
+}
+
static void
test_line_curve_intersection (void)
{
@@ -301,7 +356,7 @@ test_line_curve_intersection (void)
float t1[9], t2[9];
graphene_point_t p[9];
int n;
- graphene_rect_t b;
+ GskBoundingBox b;
graphene_point_init (&p1[0], 0, 100);
graphene_point_init (&p1[1], 50, 100);
@@ -321,10 +376,37 @@ test_line_curve_intersection (void)
g_assert_true (graphene_point_near (&p[0], &GRAPHENE_POINT_INIT (50, 50), 0.0001));
gsk_curve_get_tight_bounds (&c1, &b);
- graphene_rect_contains_point (&b, &p[0]);
+ gsk_bounding_box_contains_point (&b, &p[0]);
gsk_curve_get_tight_bounds (&c2, &b);
- graphene_rect_contains_point (&b, &p[0]);
+ gsk_bounding_box_contains_point (&b, &p[0]);
+}
+
+static void
+test_line_curve_end_intersection (void)
+{
+ GskCurve c1, c2;
+ graphene_point_t p1[4], p2[2];
+ float t1[9], t2[9];
+ graphene_point_t p[9];
+ int n;
+
+ graphene_point_init (&p1[0], 0, 100);
+ graphene_point_init (&p1[1], 50, 100);
+ graphene_point_init (&p1[2], 50, 0);
+ graphene_point_init (&p1[3], 100, 0);
+ graphene_point_init (&p2[0], 100, 0);
+ graphene_point_init (&p2[1], 100, 100);
+
+ gsk_curve_init (&c1, gsk_pathop_encode (GSK_PATH_CURVE, p1));
+ gsk_curve_init (&c2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+ n = gsk_curve_intersect (&c1, &c2, t1, t2, p, 1);
+
+ g_assert_cmpint (n, ==, 1);
+ g_assert_cmpfloat_with_epsilon (t1[0], 1, 0.0001);
+ g_assert_cmpfloat_with_epsilon (t2[0], 0, 0.0001);
+ g_assert_true (graphene_point_near (&p[0], &GRAPHENE_POINT_INIT (100, 0), 0.0001));
}
static void
@@ -360,7 +442,7 @@ test_curve_curve_intersection (void)
float t1[9], t2[9];
graphene_point_t p[9];
int n;
- graphene_rect_t b;
+ GskBoundingBox b;
graphene_point_init (&p1[0], 0, 0);
graphene_point_init (&p1[1], 33.333, 100);
@@ -383,10 +465,61 @@ test_curve_curve_intersection (void)
g_assert_cmpfloat (t2[1], >, 0.5);
gsk_curve_get_tight_bounds (&c1, &b);
- graphene_rect_contains_point (&b, &p[0]);
+ gsk_bounding_box_contains_point (&b, &p[0]);
gsk_curve_get_tight_bounds (&c2, &b);
- graphene_rect_contains_point (&b, &p[0]);
+ gsk_bounding_box_contains_point (&b, &p[0]);
+}
+
+static void
+test_curve_curve_end_intersection (void)
+{
+ GskCurve c1, c2;
+ graphene_point_t p1[4], p2[4];
+ float t1[9], t2[9];
+ graphene_point_t p[9];
+ int n;
+
+ graphene_point_init (&p1[0], 0, 0);
+ graphene_point_init (&p1[1], 33.333, 100);
+ graphene_point_init (&p1[2], 66.667, 0);
+ graphene_point_init (&p1[3], 100, 100);
+ graphene_point_init (&p2[0], 100, 100);
+ graphene_point_init (&p2[1], 100, 0);
+ graphene_point_init (&p2[2], 20, 0);
+ graphene_point_init (&p2[3], 10, 0);
+
+ gsk_curve_init (&c1, gsk_pathop_encode (GSK_PATH_CURVE, p1));
+ gsk_curve_init (&c2, gsk_pathop_encode (GSK_PATH_CONIC, p2));
+
+ n = gsk_curve_intersect (&c1, &c2, t1, t2, p, 9);
+
+ g_assert_cmpint (n, ==, 1);
+ g_assert_cmpfloat_with_epsilon (t1[0], 1, 0.0001);
+ g_assert_cmpfloat_with_epsilon (t2[0], 0, 0.0001);
+}
+
+static void
+test_curve_curve_end_intersection2 (void)
+{
+ GskCurve c, c1, c2;
+ graphene_point_t p1[4];
+ float t1[9], t2[9];
+ graphene_point_t p[9];
+ int n;
+
+ graphene_point_init (&p1[0], 200, 100);
+ graphene_point_init (&p1[1], 300, 300);
+ graphene_point_init (&p1[2], 100, 300);
+ graphene_point_init (&p1[3], 300, 100);
+
+ gsk_curve_init (&c, gsk_pathop_encode (GSK_PATH_CURVE, p1));
+
+ gsk_curve_split (&c, 0.5, &c1, &c2);
+
+ n = gsk_curve_intersect (&c1, &c2, t1, t2, p, 9);
+
+ g_assert_cmpint (n, ==, 2);
}
static void
@@ -682,13 +815,18 @@ main (int argc, char *argv[])
g_test_init (&argc, &argv, NULL);
g_test_add_func ("/curve/points", test_curve_points);
+ g_test_add_func ("/curve/bounds", test_curve_bounds);
g_test_add_func ("/curve/tangents", test_curve_tangents);
g_test_add_func ("/curve/decompose", test_curve_decompose);
g_test_add_func ("/curve/decompose-curve", test_curve_decompose_curve);
g_test_add_func ("/curve/intersection/line-line", test_line_line_intersection);
+ g_test_add_func ("/curve/intersection/line-line-end", test_line_line_end_intersection);
g_test_add_func ("/curve/intersection/line-curve", test_line_curve_intersection);
+ g_test_add_func ("/curve/intersection/line-curve-end", test_line_curve_end_intersection);
g_test_add_func ("/curve/intersection/line-curve-none", test_line_curve_none_intersection);
g_test_add_func ("/curve/intersection/curve-curve", test_curve_curve_intersection);
+ g_test_add_func ("/curve/intersection/curve-curve-end", test_curve_curve_end_intersection);
+ g_test_add_func ("/curve/intersection/curve-curve-end2", test_curve_curve_end_intersection2);
g_test_add_func ("/curve/intersection/curve-curve-max", test_curve_curve_max_intersection);
g_test_add_func ("/curve/intersection/horizontal-line", test_curve_intersection_horizontal_line);
g_test_add_func ("/curve/split", test_curve_split);
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
