diff options
Diffstat (limited to 'Build/source/texk/lcdf-typetools/lcdf-typetools-src/liblcdf/bezier.cc')
-rw-r--r-- | Build/source/texk/lcdf-typetools/lcdf-typetools-src/liblcdf/bezier.cc | 170 |
1 files changed, 85 insertions, 85 deletions
diff --git a/Build/source/texk/lcdf-typetools/lcdf-typetools-src/liblcdf/bezier.cc b/Build/source/texk/lcdf-typetools/lcdf-typetools-src/liblcdf/bezier.cc index c296a4b4aa3..eb1ea73dc9a 100644 --- a/Build/source/texk/lcdf-typetools/lcdf-typetools-src/liblcdf/bezier.cc +++ b/Build/source/texk/lcdf-typetools/lcdf-typetools-src/liblcdf/bezier.cc @@ -2,7 +2,7 @@ /* bezier.{cc,hh} -- cubic Bezier curves * - * Copyright (c) 1998-2019 Eddie Kohler + * Copyright (c) 1998-2023 Eddie Kohler * * This program is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by the Free @@ -27,14 +27,14 @@ Bezier::make_bb() const noexcept { _bb = 0; for (int i = 1; i < 4; i++) { - if (_p[i].x > bb_right_x()) - _bb = (_bb & ~0x03) | (i << 0); - else if (_p[i].x < bb_left_x()) - _bb = (_bb & ~0x0C) | (i << 2); - if (_p[i].y > bb_top_x()) - _bb = (_bb & ~0x30) | (i << 4); - else if (_p[i].y < bb_bottom_x()) - _bb = (_bb & ~0xC0) | (i << 6); + if (_p[i].x > bb_right_x()) + _bb = (_bb & ~0x03) | (i << 0); + else if (_p[i].x < bb_left_x()) + _bb = (_bb & ~0x0C) | (i << 2); + if (_p[i].y > bb_top_x()) + _bb = (_bb & ~0x30) | (i << 4); + else if (_p[i].y < bb_bottom_x()) + _bb = (_bb & ~0xC0) | (i << 6); } } @@ -47,7 +47,7 @@ bool Bezier::is_flat(double t) const noexcept { return (_p[2].on_segment(_p[0], _p[3], t) - && _p[1].on_segment(_p[0], _p[3], t)); + && _p[1].on_segment(_p[0], _p[3], t)); } static Point @@ -56,12 +56,12 @@ eval_bezier(Point *b_in, int degree, double u) assert(degree < 4); Point b[4]; for (int i = 0; i <= degree; i++) - b[i] = b_in[i]; + b[i] = b_in[i]; double m = 1.0 - u; for (int i = 1; i <= degree; i++) - for (int j = 0; j <= degree - i; j++) - b[j] = b[j]*m + b[j+1]*u; + for (int j = 0; j <= degree - i; j++) + b[j] = b[j]*m + b[j+1]*u; return b[0]; } @@ -71,8 +71,8 @@ Bezier::eval(double u) const noexcept Bezier b = *this; double m = 1.0 - u; for (int i = 1; i < 4; i++) - for (int j = 0; j < 4 - i; j++) - b._p[j] = m * b._p[j] + u * b._p[j+1]; + for (int j = 0; j < 4 - i; j++) + b._p[j] = m * b._p[j] + u * b._p[j+1]; return b._p[0]; } @@ -104,45 +104,45 @@ Bezier::in_bb(const Point &p, double tolerance) const noexcept { ensure_bb(); if (bb_right() + tolerance < p.x - || bb_left() - tolerance > p.x - || bb_top() + tolerance < p.y - || bb_bottom() - tolerance > p.y) - return false; + || bb_left() - tolerance > p.x + || bb_top() + tolerance < p.y + || bb_bottom() - tolerance > p.y) + return false; else - return true; + return true; } double Bezier::hit_recurse(const Point &p, double tolerance, double leftd, - double rightd, double leftt, double rightt) const noexcept + double rightd, double leftt, double rightt) const noexcept { Bezier left, right; double middled, resultt; if (is_flat(tolerance)) { - if (p.on_segment(_p[0], _p[3], tolerance)) - return (leftt + rightt) / 2; - else - return -1; + if (p.on_segment(_p[0], _p[3], tolerance)) + return (leftt + rightt) / 2; + else + return -1; } if (leftd < tolerance * tolerance) - return leftt; + return leftt; if (rightd < tolerance * tolerance) - return rightt; + return rightt; if (!in_bb(p, tolerance)) - return -1; + return -1; halve(left, right); middled = (right._p[0] - p).squared_length(); resultt = left.hit_recurse - (p, tolerance, leftd, middled, leftt, (leftt + rightt) / 2); + (p, tolerance, leftd, middled, leftt, (leftt + rightt) / 2); if (resultt >= 0) - return resultt; + return resultt; return right.hit_recurse - (p, tolerance, middled, rightd, (leftt + rightt) / 2, rightt); + (p, tolerance, middled, rightd, (leftt + rightt) / 2, rightt); } bool @@ -165,14 +165,14 @@ void Bezier::segmentize(Vector<Point> &v, bool first) const { if (is_flat(0.5)) { - if (first) - v.push_back(_p[0]); - v.push_back(_p[3]); + if (first) + v.push_back(_p[0]); + v.push_back(_p[3]); } else { - Bezier left, right; - halve(left, right); - left.segmentize(v, first); - right.segmentize(v, false); + Bezier left, right; + halve(left, right); + left.segmentize(v, first); + right.segmentize(v, false); } } @@ -191,10 +191,10 @@ chord_length_parameterize(const Point *d, int nd, Vector<double> &result) result.reserve(nd); result.push_back(0); for (int i = 1; i < nd; i++) - result.push_back(result.back() + Point::distance(d[i-1], d[i])); + result.push_back(result.back() + Point::distance(d[i-1], d[i])); double last_dist = result.back(); for (int i = 1; i < nd; i++) - result[i] /= last_dist; + result[i] /= last_dist; } static inline double @@ -226,14 +226,14 @@ B3(double u) static Bezier generate_bezier(const Point *d, int nd, const Vector<double> ¶meters, - const Point &left_tangent, const Point &right_tangent) + const Point &left_tangent, const Point &right_tangent) { Point *a0 = new Point[nd]; Point *a1 = new Point[nd]; for (int i = 0; i < nd; i++) { - a0[i] = left_tangent * B1(parameters[i]); - a1[i] = right_tangent * B2(parameters[i]); + a0[i] = left_tangent * B1(parameters[i]); + a1[i] = right_tangent * B2(parameters[i]); } double c[2][2], x[2]; @@ -241,14 +241,14 @@ generate_bezier(const Point *d, int nd, const Vector<double> ¶meters, int last = nd - 1; for (int i = 0; i < nd; i++) { - c[0][0] += Point::dot(a0[i], a0[i]); - c[0][1] += Point::dot(a0[i], a1[i]); - c[1][1] += Point::dot(a1[i], a1[i]); - - Point tmp = d[i] - (d[0] * (B0(parameters[i]) + B1(parameters[i])) - + d[last] * (B2(parameters[i]) + B3(parameters[i]))); - x[0] += Point::dot(a0[i], tmp); - x[1] += Point::dot(a1[i], tmp); + c[0][0] += Point::dot(a0[i], a0[i]); + c[0][1] += Point::dot(a0[i], a1[i]); + c[1][1] += Point::dot(a1[i], a1[i]); + + Point tmp = d[i] - (d[0] * (B0(parameters[i]) + B1(parameters[i])) + + d[last] * (B2(parameters[i]) + B3(parameters[i]))); + x[0] += Point::dot(a0[i], tmp); + x[1] += Point::dot(a1[i], tmp); } c[1][0] = c[0][1]; @@ -259,18 +259,18 @@ generate_bezier(const Point *d, int nd, const Vector<double> ¶meters, // finally, derive alpha values if (det_c0_c1 == 0.0) - det_c0_c1 = c[0][0]*c[1][1] * 10e-12; + det_c0_c1 = c[0][0]*c[1][1] * 10e-12; double alpha_l = det_x_c1 / det_c0_c1; double alpha_r = det_c0_x / det_c0_c1; // if alpha negative, use the Wu/Barsky heuristic if (alpha_l < 0.0 || alpha_r < 0.0) { - double distance = Point::distance(d[0], d[last]) / 3; - return Bezier(d[0], d[0] + left_tangent*distance, - d[last] + right_tangent*distance, d[last]); + double distance = Point::distance(d[0], d[last]) / 3; + return Bezier(d[0], d[0] + left_tangent*distance, + d[last] + right_tangent*distance, d[last]); } else - return Bezier(d[0], d[0] + left_tangent*alpha_l, - d[last] + right_tangent*alpha_r, d[last]); + return Bezier(d[0], d[0] + left_tangent*alpha_l, + d[last] + right_tangent*alpha_r, d[last]); } static double @@ -280,11 +280,11 @@ newton_raphson_root_find(const Bezier &b, const Point &p, double u) Point b_det[3]; for (int i = 0; i < 3; i++) - b_det[i] = (b_pts[i+1] - b_pts[i]) * 3; + b_det[i] = (b_pts[i+1] - b_pts[i]) * 3; Point b_det_det[2]; for (int i = 0; i < 2; i++) - b_det_det[i] = (b_det[i+1] - b_det[i]) * 2; + b_det_det[i] = (b_det[i+1] - b_det[i]) * 2; Point b_u = b.eval(u); Point b_det_u = eval_bezier(b_det, 2, u); @@ -292,31 +292,31 @@ newton_raphson_root_find(const Bezier &b, const Point &p, double u) double numerator = Point::dot(b_u - p, b_det_u); double denominator = Point::dot(b_det_u, b_det_u) + - Point::dot(b_u - p, b_det_det_u); + Point::dot(b_u - p, b_det_det_u); return u - numerator/denominator; } static void reparameterize(const Point *d, int nd, Vector<double> ¶meters, - const Bezier &b) + const Bezier &b) { for (int i = 0; i < nd; i++) - parameters[i] = newton_raphson_root_find(b, d[i], parameters[i]); + parameters[i] = newton_raphson_root_find(b, d[i], parameters[i]); } static double compute_max_error(const Point *d, int nd, const Bezier &b, - const Vector<double> ¶meters, int *split_point) + const Vector<double> ¶meters, int *split_point) { *split_point = nd/2; double max_dist = 0.0; for (int i = 1; i < nd - 1; i++) { - double dist = (b.eval(parameters[i]) - d[i]).squared_length(); - if (dist >= max_dist) { - max_dist = dist; - *split_point = i; - } + double dist = (b.eval(parameters[i]) - d[i]).squared_length(); + if (dist >= max_dist) { + max_dist = dist; + *split_point = i; + } } return max_dist; } @@ -327,12 +327,12 @@ fit0(const Point *d, int nd, Point left_tangent, Point right_tangent, { // Use a heuristic for small regions (only two points) if (nd == 2) { - double dist = Point::distance(d[0], d[1]) / 3; - result.push_back(Bezier(d[0], - d[0] + dist*left_tangent, - d[1] + dist*right_tangent, - d[1])); - return; + double dist = Point::distance(d[0], d[1]) / 3; + result.push_back(Bezier(d[0], + d[0] + dist*left_tangent, + d[1] + dist*right_tangent, + d[1])); + return; } // Parameterize points and attempt to fit curve @@ -344,21 +344,21 @@ fit0(const Point *d, int nd, Point left_tangent, Point right_tangent, int split_point; double max_error = compute_max_error(d, nd, b, parameters, &split_point); if (max_error < error) { - result.push_back(b); - return; + result.push_back(b); + return; } // if error not too large, try iteration and reparameterization if (max_error < error*error) - for (int i = 0; i < 4; i++) { - reparameterize(d, nd, parameters, b); - b = generate_bezier(d, nd, parameters, left_tangent, right_tangent); - max_error = compute_max_error(d, nd, b, parameters, &split_point); - if (max_error < error) { - result.push_back(b); - return; - } - } + for (int i = 0; i < 4; i++) { + reparameterize(d, nd, parameters, b); + b = generate_bezier(d, nd, parameters, left_tangent, right_tangent); + max_error = compute_max_error(d, nd, b, parameters, &split_point); + if (max_error < error) { + result.push_back(b); + return; + } + } // fitting failed -- split at max error point and fit again Point center_tangent = ((d[split_point-1] - d[split_point+1])/2).normal(); |