| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include <2geom/bezier.h> | ||
| 2 | #include <2geom/point.h> | ||
| 3 | #include <2geom/solver.h> | ||
| 4 | #include <algorithm> | ||
| 5 | |||
| 6 | namespace Geom { | ||
| 7 | |||
| 8 | /*** Find the zeros of the parametric function in 2d defined by two beziers X(t), Y(t). The code subdivides until it happy with the linearity of the bezier. This requires an n^2 subdivision for each step, even when there is only one solution. | ||
| 9 | * | ||
| 10 | * Perhaps it would be better to subdivide particularly around nodes with changing sign, rather than simply cutting in half. | ||
| 11 | */ | ||
| 12 | |||
| 13 | #define SGN(a) (((a)<0) ? -1 : 1) | ||
| 14 | |||
| 15 | /* | ||
| 16 | * Forward declarations | ||
| 17 | */ | ||
| 18 | unsigned | ||
| 19 | crossing_count(Geom::Point const *V, unsigned degree); | ||
| 20 | static unsigned | ||
| 21 | control_poly_flat_enough(Geom::Point const *V, unsigned degree); | ||
| 22 | static double | ||
| 23 | compute_x_intercept(Geom::Point const *V, unsigned degree); | ||
| 24 | |||
| 25 | const unsigned MAXDEPTH = 64; /* Maximum depth for recursion */ | ||
| 26 | |||
| 27 | const double BEPSILON = ldexp(1.0,-MAXDEPTH-1); /*Flatness control value */ | ||
| 28 | |||
| 29 | unsigned total_steps, total_subs; | ||
| 30 | |||
| 31 | /* | ||
| 32 | * find_bezier_roots : Given an equation in Bernstein-Bezier form, find all | ||
| 33 | * of the roots in the interval [0, 1]. Return the number of roots found. | ||
| 34 | */ | ||
| 35 | void | ||
| 36 | ✗ | find_parametric_bezier_roots(Geom::Point const *w, /* The control points */ | |
| 37 | unsigned degree, /* The degree of the polynomial */ | ||
| 38 | std::vector<double> &solutions, /* RETURN candidate t-values */ | ||
| 39 | unsigned depth) /* The depth of the recursion */ | ||
| 40 | { | ||
| 41 | ✗ | total_steps++; | |
| 42 | ✗ | const unsigned max_crossings = crossing_count(w, degree); | |
| 43 | ✗ | switch (max_crossings) { | |
| 44 | ✗ | case 0: /* No solutions here */ | |
| 45 | ✗ | return; | |
| 46 | |||
| 47 | ✗ | case 1: | |
| 48 | /* Unique solution */ | ||
| 49 | /* Stop recursion when the tree is deep enough */ | ||
| 50 | /* if deep enough, return 1 solution at midpoint */ | ||
| 51 | ✗ | if (depth >= MAXDEPTH) { | |
| 52 | ✗ | solutions.push_back((w[0][Geom::X] + w[degree][Geom::X]) / 2.0); | |
| 53 | ✗ | return; | |
| 54 | } | ||
| 55 | |||
| 56 | // I thought secant method would be faster here, but it'aint. -- njh | ||
| 57 | |||
| 58 | ✗ | if (control_poly_flat_enough(w, degree)) { | |
| 59 | ✗ | solutions.push_back(compute_x_intercept(w, degree)); | |
| 60 | ✗ | return; | |
| 61 | } | ||
| 62 | ✗ | break; | |
| 63 | } | ||
| 64 | |||
| 65 | /* Otherwise, solve recursively after subdividing control polygon */ | ||
| 66 | |||
| 67 | //Geom::Point Left[degree+1], /* New left and right */ | ||
| 68 | // Right[degree+1]; /* control polygons */ | ||
| 69 | ✗ | std::vector<Geom::Point> Left( degree+1 ), Right(degree+1); | |
| 70 | |||
| 71 | ✗ | casteljau_subdivision(0.5, w, Left.data(), Right.data(), degree); | |
| 72 | ✗ | total_subs ++; | |
| 73 | ✗ | find_parametric_bezier_roots(Left.data(), degree, solutions, depth+1); | |
| 74 | ✗ | find_parametric_bezier_roots(Right.data(), degree, solutions, depth+1); | |
| 75 | } | ||
| 76 | |||
| 77 | |||
| 78 | /* | ||
| 79 | * crossing_count: | ||
| 80 | * Count the number of times a Bezier control polygon | ||
| 81 | * crosses the 0-axis. This number is >= the number of roots. | ||
| 82 | * | ||
| 83 | */ | ||
| 84 | unsigned | ||
| 85 | ✗ | crossing_count(Geom::Point const *V, /* Control pts of Bezier curve */ | |
| 86 | unsigned degree) /* Degree of Bezier curve */ | ||
| 87 | { | ||
| 88 | ✗ | unsigned n_crossings = 0; /* Number of zero-crossings */ | |
| 89 | |||
| 90 | ✗ | int old_sign = SGN(V[0][Geom::Y]); | |
| 91 | ✗ | for (unsigned i = 1; i <= degree; i++) { | |
| 92 | ✗ | int sign = SGN(V[i][Geom::Y]); | |
| 93 | ✗ | if (sign != old_sign) | |
| 94 | ✗ | n_crossings++; | |
| 95 | ✗ | old_sign = sign; | |
| 96 | } | ||
| 97 | ✗ | return n_crossings; | |
| 98 | } | ||
| 99 | |||
| 100 | |||
| 101 | |||
| 102 | /* | ||
| 103 | * control_poly_flat_enough : | ||
| 104 | * Check if the control polygon of a Bezier curve is flat enough | ||
| 105 | * for recursive subdivision to bottom out. | ||
| 106 | * | ||
| 107 | */ | ||
| 108 | static unsigned | ||
| 109 | ✗ | control_poly_flat_enough(Geom::Point const *V, /* Control points */ | |
| 110 | unsigned degree) /* Degree of polynomial */ | ||
| 111 | { | ||
| 112 | /* Find the perpendicular distance from each interior control point to line connecting V[0] and | ||
| 113 | * V[degree] */ | ||
| 114 | |||
| 115 | /* Derive the implicit equation for line connecting first */ | ||
| 116 | /* and last control points */ | ||
| 117 | ✗ | const double a = V[0][Geom::Y] - V[degree][Geom::Y]; | |
| 118 | ✗ | const double b = V[degree][Geom::X] - V[0][Geom::X]; | |
| 119 | ✗ | const double c = V[0][Geom::X] * V[degree][Geom::Y] - V[degree][Geom::X] * V[0][Geom::Y]; | |
| 120 | |||
| 121 | ✗ | const double abSquared = (a * a) + (b * b); | |
| 122 | |||
| 123 | //double distance[degree]; /* Distances from pts to line */ | ||
| 124 | ✗ | std::vector<double> distance(degree); /* Distances from pts to line */ | |
| 125 | ✗ | for (unsigned i = 1; i < degree; i++) { | |
| 126 | /* Compute distance from each of the points to that line */ | ||
| 127 | ✗ | double & dist(distance[i-1]); | |
| 128 | ✗ | const double d = a * V[i][Geom::X] + b * V[i][Geom::Y] + c; | |
| 129 | ✗ | dist = d*d / abSquared; | |
| 130 | ✗ | if (d < 0.0) | |
| 131 | ✗ | dist = -dist; | |
| 132 | } | ||
| 133 | |||
| 134 | |||
| 135 | // Find the largest distance | ||
| 136 | ✗ | double max_distance_above = 0.0; | |
| 137 | ✗ | double max_distance_below = 0.0; | |
| 138 | ✗ | for (unsigned i = 0; i < degree-1; i++) { | |
| 139 | ✗ | const double d = distance[i]; | |
| 140 | ✗ | if (d < 0.0) | |
| 141 | ✗ | max_distance_below = std::min(max_distance_below, d); | |
| 142 | ✗ | if (d > 0.0) | |
| 143 | ✗ | max_distance_above = std::max(max_distance_above, d); | |
| 144 | } | ||
| 145 | |||
| 146 | ✗ | const double intercept_1 = (c + max_distance_above) / -a; | |
| 147 | ✗ | const double intercept_2 = (c + max_distance_below) / -a; | |
| 148 | |||
| 149 | /* Compute bounding interval*/ | ||
| 150 | ✗ | const double left_intercept = std::min(intercept_1, intercept_2); | |
| 151 | ✗ | const double right_intercept = std::max(intercept_1, intercept_2); | |
| 152 | |||
| 153 | ✗ | const double error = 0.5 * (right_intercept - left_intercept); | |
| 154 | |||
| 155 | ✗ | if (error < BEPSILON) | |
| 156 | ✗ | return 1; | |
| 157 | |||
| 158 | ✗ | return 0; | |
| 159 | ✗ | } | |
| 160 | |||
| 161 | |||
| 162 | |||
| 163 | /* | ||
| 164 | * compute_x_intercept : | ||
| 165 | * Compute intersection of chord from first control point to last | ||
| 166 | * with 0-axis. | ||
| 167 | * | ||
| 168 | */ | ||
| 169 | static double | ||
| 170 | ✗ | compute_x_intercept(Geom::Point const *V, /* Control points */ | |
| 171 | unsigned degree) /* Degree of curve */ | ||
| 172 | { | ||
| 173 | ✗ | const Geom::Point A = V[degree] - V[0]; | |
| 174 | |||
| 175 | ✗ | return (A[Geom::X]*V[0][Geom::Y] - A[Geom::Y]*V[0][Geom::X]) / -A[Geom::Y]; | |
| 176 | } | ||
| 177 | |||
| 178 | }; | ||
| 179 | |||
| 180 | /* | ||
| 181 | Local Variables: | ||
| 182 | mode:c++ | ||
| 183 | c-file-style:"stroustrup" | ||
| 184 | c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) | ||
| 185 | indent-tabs-mode:nil | ||
| 186 | fill-column:99 | ||
| 187 | End: | ||
| 188 | */ | ||
| 189 | // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : | ||
| 190 |