| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Symmetric Power Basis - Bernstein Basis conversion routines | ||
| 3 | * | ||
| 4 | * Authors: | ||
| 5 | * Marco Cecchetti <mrcekets at gmail.com> | ||
| 6 | * Nathan Hurst <njh@mail.csse.monash.edu.au> | ||
| 7 | * | ||
| 8 | * Copyright 2007-2008 authors | ||
| 9 | * | ||
| 10 | * This library is free software; you can redistribute it and/or | ||
| 11 | * modify it either under the terms of the GNU Lesser General Public | ||
| 12 | * License version 2.1 as published by the Free Software Foundation | ||
| 13 | * (the "LGPL") or, at your option, under the terms of the Mozilla | ||
| 14 | * Public License Version 1.1 (the "MPL"). If you do not alter this | ||
| 15 | * notice, a recipient may use your version of this file under either | ||
| 16 | * the MPL or the LGPL. | ||
| 17 | * | ||
| 18 | * You should have received a copy of the LGPL along with this library | ||
| 19 | * in the file COPYING-LGPL-2.1; if not, write to the Free Software | ||
| 20 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | ||
| 21 | * You should have received a copy of the MPL along with this library | ||
| 22 | * in the file COPYING-MPL-1.1 | ||
| 23 | * | ||
| 24 | * The contents of this file are subject to the Mozilla Public License | ||
| 25 | * Version 1.1 (the "License"); you may not use this file except in | ||
| 26 | * compliance with the License. You may obtain a copy of the License at | ||
| 27 | * http://www.mozilla.org/MPL/ | ||
| 28 | * | ||
| 29 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY | ||
| 30 | * OF ANY KIND, either express or implied. See the LGPL or the MPL for | ||
| 31 | * the specific language governing rights and limitations. | ||
| 32 | */ | ||
| 33 | |||
| 34 | |||
| 35 | #include <2geom/sbasis-to-bezier.h> | ||
| 36 | #include <2geom/d2.h> | ||
| 37 | #include <2geom/choose.h> | ||
| 38 | #include <2geom/path-sink.h> | ||
| 39 | #include <2geom/exception.h> | ||
| 40 | #include <2geom/convex-hull.h> | ||
| 41 | |||
| 42 | #include <iostream> | ||
| 43 | |||
| 44 | |||
| 45 | |||
| 46 | |||
| 47 | namespace Geom | ||
| 48 | { | ||
| 49 | |||
| 50 | /* | ||
| 51 | * Symmetric Power Basis - Bernstein Basis conversion routines | ||
| 52 | * | ||
| 53 | * some remark about precision: | ||
| 54 | * interval [0,1], subdivisions: 10^3 | ||
| 55 | * - bezier_to_sbasis : up to degree ~72 precision is at least 10^-5 | ||
| 56 | * up to degree ~87 precision is at least 10^-3 | ||
| 57 | * - sbasis_to_bezier : up to order ~63 precision is at least 10^-15 | ||
| 58 | * precision is at least 10^-14 even beyond order 200 | ||
| 59 | * | ||
| 60 | * interval [-1,1], subdivisions: 10^3 | ||
| 61 | * - bezier_to_sbasis : up to degree ~21 precision is at least 10^-5 | ||
| 62 | * up to degree ~24 precision is at least 10^-3 | ||
| 63 | * - sbasis_to_bezier : up to order ~11 precision is at least 10^-5 | ||
| 64 | * up to order ~13 precision is at least 10^-3 | ||
| 65 | * | ||
| 66 | * interval [-10,10], subdivisions: 10^3 | ||
| 67 | * - bezier_to_sbasis : up to degree ~7 precision is at least 10^-5 | ||
| 68 | * up to degree ~8 precision is at least 10^-3 | ||
| 69 | * - sbasis_to_bezier : up to order ~3 precision is at least 10^-5 | ||
| 70 | * up to order ~4 precision is at least 10^-3 | ||
| 71 | * | ||
| 72 | * references: | ||
| 73 | * this implementation is based on the following article: | ||
| 74 | * J.Sanchez-Reyes - The Symmetric Analogue of the Polynomial Power Basis | ||
| 75 | */ | ||
| 76 | |||
| 77 | /** Changes the basis of p to be bernstein. | ||
| 78 | \param p the Symmetric basis polynomial | ||
| 79 | \returns the Bernstein basis polynomial | ||
| 80 | |||
| 81 | if the degree is even q is the order in the symmetrical power basis, | ||
| 82 | if the degree is odd q is the order + 1 | ||
| 83 | n is always the polynomial degree, i. e. the Bezier order | ||
| 84 | sz is the number of bezier handles. | ||
| 85 | */ | ||
| 86 | 67361 | void sbasis_to_bezier (Bezier & bz, SBasis const& sb, size_t sz) | |
| 87 | { | ||
| 88 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 67361 times.
|
67361 | assert(sb.size() > 0); |
| 89 | |||
| 90 | size_t q, n; | ||
| 91 | bool even; | ||
| 92 |
2/2✓ Branch 0 taken 67357 times.
✓ Branch 1 taken 4 times.
|
67361 | if (sz == 0) |
| 93 | { | ||
| 94 | 67357 | q = sb.size(); | |
| 95 |
2/2✓ Branch 8 taken 54877 times.
✓ Branch 9 taken 12480 times.
|
67357 | if (sb[q-1][0] == sb[q-1][1]) |
| 96 | { | ||
| 97 | 54877 | even = true; | |
| 98 | 54877 | --q; | |
| 99 | 54877 | n = 2*q; | |
| 100 | } | ||
| 101 | else | ||
| 102 | { | ||
| 103 | 12480 | even = false; | |
| 104 | 12480 | n = 2*q-1; | |
| 105 | } | ||
| 106 | } | ||
| 107 | else | ||
| 108 | { | ||
| 109 |
1/2✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
|
4 | q = (sz > 2*sb.size()-1) ? sb.size() : (sz+1)/2; |
| 110 | 4 | n = sz-1; | |
| 111 | 4 | even = false; | |
| 112 | } | ||
| 113 |
1/2✓ Branch 1 taken 67361 times.
✗ Branch 2 not taken.
|
67361 | bz.clear(); |
| 114 |
1/2✓ Branch 1 taken 67361 times.
✗ Branch 2 not taken.
|
67361 | bz.resize(n+1); |
| 115 |
2/2✓ Branch 0 taken 111324 times.
✓ Branch 1 taken 67361 times.
|
178685 | for (size_t k = 0; k < q; ++k) |
| 116 | { | ||
| 117 | 111324 | int Tjk = 1; | |
| 118 |
2/2✓ Branch 0 taken 326071 times.
✓ Branch 1 taken 111324 times.
|
437395 | for (size_t j = k; j < n-k; ++j) // j <= n-k-1 |
| 119 | { | ||
| 120 | 326071 | bz[j] += (Tjk * sb[k][0]); | |
| 121 | 326071 | bz[n-j] += (Tjk * sb[k][1]); // n-k <-> [k][1] | |
| 122 | // assert(Tjk == binomial(n-2*k-1, j-k)); | ||
| 123 | 326071 | binomial_increment_k(Tjk, n-2*k-1, j-k); | |
| 124 | } | ||
| 125 | } | ||
| 126 |
2/2✓ Branch 0 taken 54877 times.
✓ Branch 1 taken 12484 times.
|
67361 | if (even) |
| 127 | { | ||
| 128 | 54877 | bz[q] += sb[q][0]; | |
| 129 | } | ||
| 130 | // the resulting coefficients are with respect to the scaled Bernstein | ||
| 131 | // basis so we need to divide them by (n, j) binomial coefficient | ||
| 132 | 67361 | int bcj = n; | |
| 133 |
2/2✓ Branch 0 taken 142803 times.
✓ Branch 1 taken 67361 times.
|
210164 | for (size_t j = 1; j < n; ++j) |
| 134 | { | ||
| 135 | 142803 | bz[j] /= bcj; | |
| 136 | // assert(bcj == binomial(n, j)); | ||
| 137 | 142803 | binomial_increment_k(bcj, n, j); | |
| 138 | } | ||
| 139 | 67361 | bz[0] = sb[0][0]; | |
| 140 | 67361 | bz[n] = sb[0][1]; | |
| 141 | 67361 | } | |
| 142 | |||
| 143 | 2 | void sbasis_to_bezier(D2<Bezier> &bz, D2<SBasis> const &sb, size_t sz) | |
| 144 | { | ||
| 145 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
|
2 | if (sz == 0) { |
| 146 | 1 | sz = std::max(sb[X].size(), sb[Y].size())*2; | |
| 147 | } | ||
| 148 | 2 | sbasis_to_bezier(bz[X], sb[X], sz); | |
| 149 | 2 | sbasis_to_bezier(bz[Y], sb[Y], sz); | |
| 150 | 2 | } | |
| 151 | |||
| 152 | /** Changes the basis of p to be Bernstein. | ||
| 153 | \param p the D2 Symmetric basis polynomial | ||
| 154 | \returns the D2 Bernstein basis polynomial | ||
| 155 | |||
| 156 | sz is always the polynomial degree, i. e. the Bezier order | ||
| 157 | */ | ||
| 158 | 1 | void sbasis_to_bezier (std::vector<Point> & bz, D2<SBasis> const& sb, size_t sz) | |
| 159 | { | ||
| 160 |
1/2✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
|
1 | D2<Bezier> bez; |
| 161 |
1/2✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
|
1 | sbasis_to_bezier(bez, sb, sz); |
| 162 |
1/2✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
|
1 | bz = bezier_points(bez); |
| 163 | 2 | } | |
| 164 | |||
| 165 | /** Changes the basis of p to be Bernstein. | ||
| 166 | \param p the D2 Symmetric basis polynomial | ||
| 167 | \returns the D2 Bernstein basis cubic polynomial | ||
| 168 | |||
| 169 | Bezier is always cubic. | ||
| 170 | For general asymmetric case, fit the SBasis function value at midpoint | ||
| 171 | For parallel, symmetric case, find the point of closest approach to the midpoint | ||
| 172 | For parallel, anti-symmetric case, fit the SBasis slope at midpoint | ||
| 173 | */ | ||
| 174 | 1 | void sbasis_to_cubic_bezier (std::vector<Point> & bz, D2<SBasis> const& sb) | |
| 175 | { | ||
| 176 | 1 | double delx[2], dely[2]; | |
| 177 | 1 | double xprime[2], yprime[2]; | |
| 178 | 1 | double midx = 0; | |
| 179 | 1 | double midy = 0; | |
| 180 | double midx_0, midy_0; | ||
| 181 | 1 | double numer[2], numer_0[2]; | |
| 182 | double denom; | ||
| 183 | double div; | ||
| 184 | |||
| 185 |
3/6✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 1 times.
|
1 | if ((sb[X].size() == 0) || (sb[Y].size() == 0)) { |
| 186 | ✗ | THROW_RANGEERROR("size of sb is too small"); | |
| 187 | } | ||
| 188 | |||
| 189 |
1/2✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
|
1 | sbasis_to_bezier(bz, sb, 4); // zeroth-order estimate |
| 190 |
3/6✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
|
1 | if ((sb[X].size() < 3) && (sb[Y].size() < 3)) |
| 191 | 1 | return; // cubic bezier estimate is exact | |
| 192 | ✗ | Geom::ConvexHull bezhull(bz); | |
| 193 | |||
| 194 | // calculate first derivatives of x and y wrt t | ||
| 195 | |||
| 196 | ✗ | for (int i = 0; i < 2; ++i) { | |
| 197 | ✗ | xprime[i] = sb[X][0][1] - sb[X][0][0]; | |
| 198 | ✗ | yprime[i] = sb[Y][0][1] - sb[Y][0][0]; | |
| 199 | } | ||
| 200 | ✗ | if (sb[X].size() > 1) { | |
| 201 | ✗ | xprime[0] += sb[X][1][0]; | |
| 202 | ✗ | xprime[1] -= sb[X][1][1]; | |
| 203 | } | ||
| 204 | ✗ | if (sb[Y].size() > 1) { | |
| 205 | ✗ | yprime[0] += sb[Y][1][0]; | |
| 206 | ✗ | yprime[1] -= sb[Y][1][1]; | |
| 207 | } | ||
| 208 | |||
| 209 | // calculate midpoint at t = 0.5 | ||
| 210 | |||
| 211 | ✗ | div = 2; | |
| 212 | ✗ | for (auto i : sb[X]) { | |
| 213 | ✗ | midx += (i[0] + i[1])/div; | |
| 214 | ✗ | div *= 4; | |
| 215 | } | ||
| 216 | |||
| 217 | ✗ | div = 2; | |
| 218 | ✗ | for (auto i : sb[Y]) { | |
| 219 | ✗ | midy += (i[0] + i[1])/div; | |
| 220 | ✗ | div *= 4; | |
| 221 | } | ||
| 222 | |||
| 223 | // is midpoint in hull: if not, the solution will be ill-conditioned, LP Bug 1428683 | ||
| 224 | |||
| 225 | ✗ | if (!bezhull.contains(Geom::Point(midx, midy))) | |
| 226 | ✗ | return; | |
| 227 | |||
| 228 | // calculate Bezier control arms | ||
| 229 | |||
| 230 | ✗ | midx = 8*midx - 4*bz[0][X] - 4*bz[3][X]; // re-define relative to center | |
| 231 | ✗ | midy = 8*midy - 4*bz[0][Y] - 4*bz[3][Y]; | |
| 232 | ✗ | midx_0 = sb[X].size() > 1 ? sb[X][1][0] + sb[X][1][1] : 0; // zeroth order estimate | |
| 233 | ✗ | midy_0 = sb[Y].size() > 1 ? sb[Y][1][0] + sb[Y][1][1] : 0; | |
| 234 | |||
| 235 | ✗ | if ((std::abs(xprime[0]) < EPSILON) && (std::abs(yprime[0]) < EPSILON) | |
| 236 | ✗ | && ((std::abs(xprime[1]) > EPSILON) || (std::abs(yprime[1]) > EPSILON))) { // degenerate handle at 0 : use distance of closest approach | |
| 237 | ✗ | numer[0] = midx*xprime[1] + midy*yprime[1]; | |
| 238 | ✗ | denom = 3.0*(xprime[1]*xprime[1] + yprime[1]*yprime[1]); | |
| 239 | ✗ | delx[0] = 0; | |
| 240 | ✗ | dely[0] = 0; | |
| 241 | ✗ | delx[1] = -xprime[1]*numer[0]/denom; | |
| 242 | ✗ | dely[1] = -yprime[1]*numer[0]/denom; | |
| 243 | ✗ | } else if ((std::abs(xprime[1]) < EPSILON) && (std::abs(yprime[1]) < EPSILON) | |
| 244 | ✗ | && ((std::abs(xprime[0]) > EPSILON) || (std::abs(yprime[0]) > EPSILON))) { // degenerate handle at 1 : ditto | |
| 245 | ✗ | numer[1] = midx*xprime[0] + midy*yprime[0]; | |
| 246 | ✗ | denom = 3.0*(xprime[0]*xprime[0] + yprime[0]*yprime[0]); | |
| 247 | ✗ | delx[0] = xprime[0]*numer[1]/denom; | |
| 248 | ✗ | dely[0] = yprime[0]*numer[1]/denom; | |
| 249 | ✗ | delx[1] = 0; | |
| 250 | ✗ | dely[1] = 0; | |
| 251 | ✗ | } else if (std::abs(xprime[1]*yprime[0] - yprime[1]*xprime[0]) > // general case : fit mid fxn value | |
| 252 | ✗ | 0.002 * std::abs(xprime[1]*xprime[0] + yprime[1]*yprime[0])) { // approx. 0.1 degree of angle | |
| 253 | ✗ | double test1 = (bz[1][Y] - bz[0][Y])*(bz[3][X] - bz[0][X]) - (bz[1][X] - bz[0][X])*(bz[3][Y] - bz[0][Y]); | |
| 254 | ✗ | double test2 = (bz[2][Y] - bz[0][Y])*(bz[3][X] - bz[0][X]) - (bz[2][X] - bz[0][X])*(bz[3][Y] - bz[0][Y]); | |
| 255 | ✗ | if (test1*test2 < 0) // reject anti-symmetric case, LP Bug 1428267 & Bug 1428683 | |
| 256 | ✗ | return; | |
| 257 | ✗ | denom = 3.0*(xprime[1]*yprime[0] - yprime[1]*xprime[0]); | |
| 258 | ✗ | for (int i = 0; i < 2; ++i) { | |
| 259 | ✗ | numer_0[i] = xprime[1 - i]*midy_0 - yprime[1 - i]*midx_0; | |
| 260 | ✗ | numer[i] = xprime[1 - i]*midy - yprime[1 - i]*midx; | |
| 261 | ✗ | delx[i] = xprime[i]*numer[i]/denom; | |
| 262 | ✗ | dely[i] = yprime[i]*numer[i]/denom; | |
| 263 | ✗ | if (numer_0[i]*numer[i] < 0) // check for reversal of direction, LP Bug 1544680 | |
| 264 | ✗ | return; | |
| 265 | } | ||
| 266 | ✗ | if (std::abs((numer[0] - numer_0[0])*numer_0[1]) > 10.0*std::abs((numer[1] - numer_0[1])*numer_0[0]) // check for asymmetry | |
| 267 | ✗ | || std::abs((numer[1] - numer_0[1])*numer_0[0]) > 10.0*std::abs((numer[0] - numer_0[0])*numer_0[1])) | |
| 268 | ✗ | return; | |
| 269 | ✗ | } else if ((xprime[0]*xprime[1] < 0) || (yprime[0]*yprime[1] < 0)) { // symmetric case : use distance of closest approach | |
| 270 | ✗ | numer[0] = midx*xprime[0] + midy*yprime[0]; | |
| 271 | ✗ | denom = 6.0*(xprime[0]*xprime[0] + yprime[0]*yprime[0]); | |
| 272 | ✗ | delx[0] = xprime[0]*numer[0]/denom; | |
| 273 | ✗ | dely[0] = yprime[0]*numer[0]/denom; | |
| 274 | ✗ | delx[1] = -delx[0]; | |
| 275 | ✗ | dely[1] = -dely[0]; | |
| 276 | } else { // anti-symmetric case : fit mid slope | ||
| 277 | // calculate slope at t = 0.5 | ||
| 278 | ✗ | midx = 0; | |
| 279 | ✗ | div = 1; | |
| 280 | ✗ | for (auto i : sb[X]) { | |
| 281 | ✗ | midx += (i[1] - i[0])/div; | |
| 282 | ✗ | div *= 4; | |
| 283 | } | ||
| 284 | ✗ | midy = 0; | |
| 285 | ✗ | div = 1; | |
| 286 | ✗ | for (auto i : sb[Y]) { | |
| 287 | ✗ | midy += (i[1] - i[0])/div; | |
| 288 | ✗ | div *= 4; | |
| 289 | } | ||
| 290 | ✗ | if (midx*yprime[0] != midy*xprime[0]) { | |
| 291 | ✗ | denom = midx*yprime[0] - midy*xprime[0]; | |
| 292 | ✗ | numer[0] = midx*(bz[3][Y] - bz[0][Y]) - midy*(bz[3][X] - bz[0][X]); | |
| 293 | ✗ | for (int i = 0; i < 2; ++i) { | |
| 294 | ✗ | delx[i] = xprime[0]*numer[0]/denom; | |
| 295 | ✗ | dely[i] = yprime[0]*numer[0]/denom; | |
| 296 | } | ||
| 297 | } else { // linear case | ||
| 298 | ✗ | for (int i = 0; i < 2; ++i) { | |
| 299 | ✗ | delx[i] = (bz[3][X] - bz[0][X])/3; | |
| 300 | ✗ | dely[i] = (bz[3][Y] - bz[0][Y])/3; | |
| 301 | } | ||
| 302 | } | ||
| 303 | } | ||
| 304 | ✗ | bz[1][X] = bz[0][X] + delx[0]; | |
| 305 | ✗ | bz[1][Y] = bz[0][Y] + dely[0]; | |
| 306 | ✗ | bz[2][X] = bz[3][X] - delx[1]; | |
| 307 | ✗ | bz[2][Y] = bz[3][Y] - dely[1]; | |
| 308 | ✗ | } | |
| 309 | |||
| 310 | /** Changes the basis of p to be sbasis. | ||
| 311 | \param p the Bernstein basis polynomial | ||
| 312 | \returns the Symmetric basis polynomial | ||
| 313 | |||
| 314 | if the degree is even q is the order in the symmetrical power basis, | ||
| 315 | if the degree is odd q is the order + 1 | ||
| 316 | n is always the polynomial degree, i. e. the Bezier order | ||
| 317 | */ | ||
| 318 | 558 | void bezier_to_sbasis (SBasis & sb, Bezier const& bz) | |
| 319 | { | ||
| 320 |
1/2✓ Branch 1 taken 558 times.
✗ Branch 2 not taken.
|
558 | size_t n = bz.order(); |
| 321 | 558 | size_t q = (n+1) / 2; | |
| 322 | 558 | size_t even = (n & 1u) ? 0 : 1; | |
| 323 |
1/2✓ Branch 1 taken 558 times.
✗ Branch 2 not taken.
|
558 | sb.clear(); |
| 324 |
1/2✓ Branch 3 taken 558 times.
✗ Branch 4 not taken.
|
558 | sb.resize(q + even, Linear(0, 0)); |
| 325 | 558 | int nck = 1; | |
| 326 |
2/2✓ Branch 0 taken 1007 times.
✓ Branch 1 taken 558 times.
|
1565 | for (size_t k = 0; k < q; ++k) |
| 327 | { | ||
| 328 | 1007 | int Tjk = nck; | |
| 329 |
2/2✓ Branch 0 taken 1471 times.
✓ Branch 1 taken 1007 times.
|
2478 | for (size_t j = k; j < q; ++j) |
| 330 | { | ||
| 331 |
1/2✓ Branch 2 taken 1471 times.
✗ Branch 3 not taken.
|
1471 | sb[j][0] += (Tjk * bz[k]); |
| 332 |
1/2✓ Branch 2 taken 1471 times.
✗ Branch 3 not taken.
|
1471 | sb[j][1] += (Tjk * bz[n-k]); // n-j <-> [j][1] |
| 333 | // assert(Tjk == sgn(j, k) * binomial(n-j-k, j-k) * binomial(n, k)); | ||
| 334 | 1471 | binomial_increment_k(Tjk, n-j-k, j-k); | |
| 335 | 1471 | binomial_decrement_n(Tjk, n-j-k, j-k+1); | |
| 336 | 1471 | Tjk = -Tjk; | |
| 337 | } | ||
| 338 | 1007 | Tjk = -nck; | |
| 339 |
2/2✓ Branch 0 taken 464 times.
✓ Branch 1 taken 1007 times.
|
1471 | for (size_t j = k+1; j < q; ++j) |
| 340 | { | ||
| 341 |
1/2✓ Branch 2 taken 464 times.
✗ Branch 3 not taken.
|
464 | sb[j][0] += (Tjk * bz[n-k]); |
| 342 |
1/2✓ Branch 2 taken 464 times.
✗ Branch 3 not taken.
|
464 | sb[j][1] += (Tjk * bz[k]); // n-j <-> [j][1] |
| 343 | // assert(Tjk == sgn(j, k) * binomial(n-j-k-1, j-k-1) * binomial(n, k)); | ||
| 344 | 464 | binomial_increment_k(Tjk, n-j-k-1, j-k-1); | |
| 345 | 464 | binomial_decrement_n(Tjk, n-j-k-1, j-k); | |
| 346 | 464 | Tjk = -Tjk; | |
| 347 | } | ||
| 348 | // assert(nck == binomial(n, k)); | ||
| 349 | 1007 | binomial_increment_k(nck, n, k); | |
| 350 | } | ||
| 351 |
2/2✓ Branch 0 taken 18 times.
✓ Branch 1 taken 540 times.
|
558 | if (even) |
| 352 | { | ||
| 353 |
2/2✓ Branch 1 taken 9 times.
✓ Branch 2 taken 9 times.
|
18 | int Tjk = q & 1 ? -1 : 1; |
| 354 |
2/2✓ Branch 0 taken 9 times.
✓ Branch 1 taken 18 times.
|
27 | for (size_t k = 0; k < q; ++k) |
| 355 | { | ||
| 356 |
1/2✓ Branch 3 taken 9 times.
✗ Branch 4 not taken.
|
9 | sb[q][0] += (Tjk * (bz[k] + bz[n-k])); |
| 357 | // assert(Tjk == sgn(q,k) * binomial(n, k)); | ||
| 358 | 9 | binomial_increment_k(Tjk, n, k); | |
| 359 | 9 | Tjk = -Tjk; | |
| 360 | } | ||
| 361 | // assert(Tjk == binomial(n, q)); | ||
| 362 |
1/2✓ Branch 2 taken 18 times.
✗ Branch 3 not taken.
|
18 | sb[q][0] += Tjk * bz[q]; |
| 363 |
2/4✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 18 times.
✗ Branch 6 not taken.
|
18 | sb[q][1] = sb[q][0]; |
| 364 | } | ||
| 365 |
1/2✓ Branch 2 taken 558 times.
✗ Branch 3 not taken.
|
558 | sb[0][0] = bz[0]; |
| 366 |
1/2✓ Branch 2 taken 558 times.
✗ Branch 3 not taken.
|
558 | sb[0][1] = bz[n]; |
| 367 | 558 | } | |
| 368 | |||
| 369 | /** Changes the basis of d2 p to be sbasis. | ||
| 370 | \param p the d2 Bernstein basis polynomial | ||
| 371 | \returns the d2 Symmetric basis polynomial | ||
| 372 | |||
| 373 | if the degree is even q is the order in the symmetrical power basis, | ||
| 374 | if the degree is odd q is the order + 1 | ||
| 375 | n is always the polynomial degree, i. e. the Bezier order | ||
| 376 | */ | ||
| 377 | 1 | void bezier_to_sbasis (D2<SBasis> & sb, std::vector<Point> const& bz) | |
| 378 | { | ||
| 379 | 1 | size_t n = bz.size() - 1; | |
| 380 | 1 | size_t q = (n+1) / 2; | |
| 381 | 1 | size_t even = (n & 1u) ? 0 : 1; | |
| 382 |
1/2✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
|
1 | sb[X].clear(); |
| 383 |
1/2✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
|
1 | sb[Y].clear(); |
| 384 |
1/2✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
|
1 | sb[X].resize(q + even, Linear(0, 0)); |
| 385 |
1/2✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
|
1 | sb[Y].resize(q + even, Linear(0, 0)); |
| 386 | 1 | int nck = 1; | |
| 387 |
2/2✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
|
6 | for (size_t k = 0; k < q; ++k) |
| 388 | { | ||
| 389 | 5 | int Tjk = nck; | |
| 390 |
2/2✓ Branch 0 taken 15 times.
✓ Branch 1 taken 5 times.
|
20 | for (size_t j = k; j < q; ++j) |
| 391 | { | ||
| 392 |
1/2✓ Branch 4 taken 15 times.
✗ Branch 5 not taken.
|
15 | sb[X][j][0] += (Tjk * bz[k][X]); |
| 393 |
1/2✓ Branch 4 taken 15 times.
✗ Branch 5 not taken.
|
15 | sb[X][j][1] += (Tjk * bz[n-k][X]); |
| 394 |
1/2✓ Branch 4 taken 15 times.
✗ Branch 5 not taken.
|
15 | sb[Y][j][0] += (Tjk * bz[k][Y]); |
| 395 |
1/2✓ Branch 4 taken 15 times.
✗ Branch 5 not taken.
|
15 | sb[Y][j][1] += (Tjk * bz[n-k][Y]); |
| 396 | // assert(Tjk == sgn(j, k) * binomial(n-j-k, j-k) * binomial(n, k)); | ||
| 397 | 15 | binomial_increment_k(Tjk, n-j-k, j-k); | |
| 398 | 15 | binomial_decrement_n(Tjk, n-j-k, j-k+1); | |
| 399 | 15 | Tjk = -Tjk; | |
| 400 | } | ||
| 401 | 5 | Tjk = -nck; | |
| 402 |
2/2✓ Branch 0 taken 10 times.
✓ Branch 1 taken 5 times.
|
15 | for (size_t j = k+1; j < q; ++j) |
| 403 | { | ||
| 404 |
1/2✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
|
10 | sb[X][j][0] += (Tjk * bz[n-k][X]); |
| 405 |
1/2✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
|
10 | sb[X][j][1] += (Tjk * bz[k][X]); |
| 406 |
1/2✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
|
10 | sb[Y][j][0] += (Tjk * bz[n-k][Y]); |
| 407 |
1/2✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
|
10 | sb[Y][j][1] += (Tjk * bz[k][Y]); |
| 408 | // assert(Tjk == sgn(j, k) * binomial(n-j-k-1, j-k-1) * binomial(n, k)); | ||
| 409 | 10 | binomial_increment_k(Tjk, n-j-k-1, j-k-1); | |
| 410 | 10 | binomial_decrement_n(Tjk, n-j-k-1, j-k); | |
| 411 | 10 | Tjk = -Tjk; | |
| 412 | } | ||
| 413 | // assert(nck == binomial(n, k)); | ||
| 414 | 5 | binomial_increment_k(nck, n, k); | |
| 415 | } | ||
| 416 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
|
1 | if (even) |
| 417 | { | ||
| 418 | ✗ | int Tjk = q & 1 ? -1 : 1; | |
| 419 | ✗ | for (size_t k = 0; k < q; ++k) | |
| 420 | { | ||
| 421 | ✗ | sb[X][q][0] += (Tjk * (bz[k][X] + bz[n-k][X])); | |
| 422 | ✗ | sb[Y][q][0] += (Tjk * (bz[k][Y] + bz[n-k][Y])); | |
| 423 | // assert(Tjk == sgn(q,k) * binomial(n, k)); | ||
| 424 | ✗ | binomial_increment_k(Tjk, n, k); | |
| 425 | ✗ | Tjk = -Tjk; | |
| 426 | } | ||
| 427 | // assert(Tjk == binomial(n, q)); | ||
| 428 | ✗ | sb[X][q][0] += Tjk * bz[q][X]; | |
| 429 | ✗ | sb[X][q][1] = sb[X][q][0]; | |
| 430 | ✗ | sb[Y][q][0] += Tjk * bz[q][Y]; | |
| 431 | ✗ | sb[Y][q][1] = sb[Y][q][0]; | |
| 432 | } | ||
| 433 |
1/2✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
|
1 | sb[X][0][0] = bz[0][X]; |
| 434 |
1/2✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
|
1 | sb[X][0][1] = bz[n][X]; |
| 435 |
1/2✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
|
1 | sb[Y][0][0] = bz[0][Y]; |
| 436 |
1/2✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
|
1 | sb[Y][0][1] = bz[n][Y]; |
| 437 | 1 | } | |
| 438 | |||
| 439 | } // namespace Geom | ||
| 440 | |||
| 441 | #if 0 | ||
| 442 | /* | ||
| 443 | * This version works by inverting a reasonable upper bound on the error term after subdividing the | ||
| 444 | * curve at $a$. We keep biting off pieces until there is no more curve left. | ||
| 445 | * | ||
| 446 | * Derivation: The tail of the power series is $a_ks^k + a_{k+1}s^{k+1} + \ldots = e$. A | ||
| 447 | * subdivision at $a$ results in a tail error of $e*A^k, A = (1-a)a$. Let this be the desired | ||
| 448 | * tolerance tol $= e*A^k$ and invert getting $A = e^{1/k}$ and $a = 1/2 - \sqrt{1/4 - A}$ | ||
| 449 | */ | ||
| 450 | void | ||
| 451 | subpath_from_sbasis_incremental(Geom::OldPathSetBuilder &pb, D2<SBasis> B, double tol, bool initial) { | ||
| 452 | const unsigned k = 2; // cubic bezier | ||
| 453 | double te = B.tail_error(k); | ||
| 454 | assert(B[0].std::isfinite()); | ||
| 455 | assert(B[1].std::isfinite()); | ||
| 456 | |||
| 457 | //std::cout << "tol = " << tol << std::endl; | ||
| 458 | while(1) { | ||
| 459 | double A = std::sqrt(tol/te); // pow(te, 1./k) | ||
| 460 | double a = A; | ||
| 461 | if(A < 1) { | ||
| 462 | A = std::min(A, 0.25); | ||
| 463 | a = 0.5 - std::sqrt(0.25 - A); // quadratic formula | ||
| 464 | if(a > 1) a = 1; // clamp to the end of the segment | ||
| 465 | } else | ||
| 466 | a = 1; | ||
| 467 | assert(a > 0); | ||
| 468 | //std::cout << "te = " << te << std::endl; | ||
| 469 | //std::cout << "A = " << A << "; a=" << a << std::endl; | ||
| 470 | D2<SBasis> Bs = compose(B, Linear(0, a)); | ||
| 471 | assert(Bs.tail_error(k)); | ||
| 472 | std::vector<Geom::Point> bez = sbasis_to_bezier(Bs, 2); | ||
| 473 | reverse(bez.begin(), bez.end()); | ||
| 474 | if (initial) { | ||
| 475 | pb.start_subpath(bez[0]); | ||
| 476 | initial = false; | ||
| 477 | } | ||
| 478 | pb.push_cubic(bez[1], bez[2], bez[3]); | ||
| 479 | |||
| 480 | // move to next piece of curve | ||
| 481 | if(a >= 1) break; | ||
| 482 | B = compose(B, Linear(a, 1)); | ||
| 483 | te = B.tail_error(k); | ||
| 484 | } | ||
| 485 | } | ||
| 486 | |||
| 487 | #endif | ||
| 488 | |||
| 489 | namespace Geom{ | ||
| 490 | |||
| 491 | /** Make a path from a d2 sbasis. | ||
| 492 | \param p the d2 Symmetric basis polynomial | ||
| 493 | \returns a Path | ||
| 494 | |||
| 495 | If only_cubicbeziers is true, the resulting path may only contain CubicBezier curves. | ||
| 496 | */ | ||
| 497 | ✗ | void build_from_sbasis(Geom::PathBuilder &pb, D2<SBasis> const &B, double tol, bool only_cubicbeziers) { | |
| 498 | ✗ | if (!B.isFinite()) { | |
| 499 | ✗ | THROW_EXCEPTION("assertion failed: B.isFinite()"); | |
| 500 | } | ||
| 501 | ✗ | if(tail_error(B, 3) < tol || sbasis_size(B) == 2) { // nearly cubic enough | |
| 502 | ✗ | if( !only_cubicbeziers && (sbasis_size(B) <= 1) ) { | |
| 503 | ✗ | pb.lineTo(B.at1()); | |
| 504 | } else { | ||
| 505 | ✗ | std::vector<Geom::Point> bez; | |
| 506 | // sbasis_to_bezier(bez, B, 4); | ||
| 507 | ✗ | sbasis_to_cubic_bezier(bez, B); | |
| 508 | ✗ | pb.curveTo(bez[1], bez[2], bez[3]); | |
| 509 | ✗ | } | |
| 510 | } else { | ||
| 511 | ✗ | build_from_sbasis(pb, compose(B, Linear(0, 0.5)), tol, only_cubicbeziers); | |
| 512 | ✗ | build_from_sbasis(pb, compose(B, Linear(0.5, 1)), tol, only_cubicbeziers); | |
| 513 | } | ||
| 514 | ✗ | } | |
| 515 | |||
| 516 | /** Make a path from a d2 sbasis. | ||
| 517 | \param p the d2 Symmetric basis polynomial | ||
| 518 | \returns a Path | ||
| 519 | |||
| 520 | If only_cubicbeziers is true, the resulting path may only contain CubicBezier curves. | ||
| 521 | */ | ||
| 522 | Path | ||
| 523 | ✗ | path_from_sbasis(D2<SBasis> const &B, double tol, bool only_cubicbeziers) { | |
| 524 | ✗ | PathBuilder pb; | |
| 525 | ✗ | pb.moveTo(B.at0()); | |
| 526 | ✗ | build_from_sbasis(pb, B, tol, only_cubicbeziers); | |
| 527 | ✗ | pb.flush(); | |
| 528 | ✗ | return pb.peek().front(); | |
| 529 | ✗ | } | |
| 530 | |||
| 531 | /** Make a path from a d2 sbasis. | ||
| 532 | \param p the d2 Symmetric basis polynomial | ||
| 533 | \returns a Path | ||
| 534 | |||
| 535 | If only_cubicbeziers is true, the resulting path may only contain CubicBezier curves. | ||
| 536 | TODO: some of this logic should be lifted into svg-path | ||
| 537 | */ | ||
| 538 | PathVector | ||
| 539 | ✗ | path_from_piecewise(Geom::Piecewise<Geom::D2<Geom::SBasis> > const &B, double tol, bool only_cubicbeziers) { | |
| 540 | ✗ | Geom::PathBuilder pb; | |
| 541 | ✗ | if(B.size() == 0) return pb.peek(); | |
| 542 | ✗ | Geom::Point start = B[0].at0(); | |
| 543 | ✗ | pb.moveTo(start); | |
| 544 | ✗ | for(unsigned i = 0; ; i++) { | |
| 545 | ✗ | if ( (i+1 == B.size()) | |
| 546 | ✗ | || !are_near(B[i+1].at0(), B[i].at1(), tol) ) | |
| 547 | { | ||
| 548 | //start of a new path | ||
| 549 | ✗ | if (are_near(start, B[i].at1()) && sbasis_size(B[i]) <= 1) { | |
| 550 | ✗ | pb.closePath(); | |
| 551 | //last line seg already there (because of .closePath()) | ||
| 552 | ✗ | goto no_add; | |
| 553 | } | ||
| 554 | ✗ | build_from_sbasis(pb, B[i], tol, only_cubicbeziers); | |
| 555 | ✗ | if (are_near(start, B[i].at1())) { | |
| 556 | //it's closed, the last closing segment was not a straight line so it needed to be added, but still make it closed here with degenerate straight line. | ||
| 557 | ✗ | pb.closePath(); | |
| 558 | } | ||
| 559 | ✗ | no_add: | |
| 560 | ✗ | if (i+1 >= B.size()) { | |
| 561 | ✗ | break; | |
| 562 | } | ||
| 563 | ✗ | start = B[i+1].at0(); | |
| 564 | ✗ | pb.moveTo(start); | |
| 565 | } else { | ||
| 566 | ✗ | build_from_sbasis(pb, B[i], tol, only_cubicbeziers); | |
| 567 | } | ||
| 568 | } | ||
| 569 | ✗ | pb.flush(); | |
| 570 | ✗ | return pb.peek(); | |
| 571 | ✗ | } | |
| 572 | |||
| 573 | } | ||
| 574 | |||
| 575 | /* | ||
| 576 | Local Variables: | ||
| 577 | mode:c++ | ||
| 578 | c-file-style:"stroustrup" | ||
| 579 | c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) | ||
| 580 | indent-tabs-mode:nil | ||
| 581 | fill-column:99 | ||
| 582 | End: | ||
| 583 | */ | ||
| 584 | // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : | ||
| 585 |