/*
* Symmetric Power Basis - Bernstein Basis conversion routines
*
* Authors:
* Marco Cecchetti <mrcekets at gmail.com>
* Nathan Hurst <njh@mail.csse.monash.edu.au>
*
* Copyright 2007-2008 authors
*
* modify it either under the terms of the GNU Lesser General Public
* License version 2.1 as published by the Free Software Foundation
* (the "LGPL") or, at your option, under the terms of the Mozilla
* Public License Version 1.1 (the "MPL"). If you do not alter this
* notice, a recipient may use your version of this file under either
* the MPL or the LGPL.
*
* You should have received a copy of the LGPL along with this library
* in the file COPYING-LGPL-2.1; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
* You should have received a copy of the MPL along with this library
* in the file COPYING-MPL-1.1
*
* The contents of this file are subject to the Mozilla Public License
* Version 1.1 (the "License"); you may not use this file except in
* compliance with the License. You may obtain a copy of the License at
*
* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
* OF ANY KIND, either express or implied. See the LGPL or the MPL for
* the specific language governing rights and limitations.
*/
#include <iostream>
namespace Geom
{
/*
* Symmetric Power Basis - Bernstein Basis conversion routines
*
* some remark about precision:
* interval [0,1], subdivisions: 10^3
* - bezier_to_sbasis : up to degree ~72 precision is at least 10^-5
* up to degree ~87 precision is at least 10^-3
* - sbasis_to_bezier : up to order ~63 precision is at least 10^-15
* precision is at least 10^-14 even beyond order 200
*
* interval [-1,1], subdivisions: 10^3
* - bezier_to_sbasis : up to degree ~21 precision is at least 10^-5
* up to degree ~24 precision is at least 10^-3
* - sbasis_to_bezier : up to order ~11 precision is at least 10^-5
* up to order ~13 precision is at least 10^-3
*
* interval [-10,10], subdivisions: 10^3
* - bezier_to_sbasis : up to degree ~7 precision is at least 10^-5
* up to degree ~8 precision is at least 10^-3
* - sbasis_to_bezier : up to order ~3 precision is at least 10^-5
* up to order ~4 precision is at least 10^-3
*
* references:
* this implementation is based on the following article:
* J.Sanchez-Reyes - The Symmetric Analogue of the Polynomial Power Basis
*/
inline
double binomial(unsigned int n, unsigned int k)
{
}
inline
int sgn(unsigned int j, unsigned int k)
{
assert (j >= k);
// we are sure that j >= k
return ((j-k) & 1u) ? -1 : 1;
}
/** Changes the basis of p to be bernstein.
\param p the Symmetric basis polynomial
\returns the Bernstein basis polynomial
if the degree is even q is the order in the symmetrical power basis,
if the degree is odd q is the order + 1
n is always the polynomial degree, i. e. the Bezier order
sz is the number of bezier handles.
*/
{
size_t q, n;
bool even;
if (sz == 0)
{
{
even = true;
--q;
n = 2*q;
}
else
{
even = false;
n = 2*q-1;
}
}
else
{
n = sz-1;
even = false;
}
double Tjk;
for (size_t k = 0; k < q; ++k)
{
for (size_t j = k; j < n-k; ++j) // j <= n-k-1
{
}
}
if (even)
{
}
// the resulting coefficients are with respect to the scaled Bernstein
// basis so we need to divide them by (n, j) binomial coefficient
for (size_t j = 1; j < n; ++j)
{
}
}
{
if (sz == 0) {
}
}
/** Changes the basis of p to be Bernstein.
\param p the D2 Symmetric basis polynomial
\returns the D2 Bernstein basis polynomial
sz is always the polynomial degree, i. e. the Bezier order
*/
{
}
/** Changes the basis of p to be Bernstein.
\param p the D2 Symmetric basis polynomial
\returns the D2 Bernstein basis cubic polynomial
Bezier is always cubic.
For general asymmetric case, fit the SBasis function value at midpoint
For parallel, symmetric case, find the point of closest approach to the midpoint
For parallel, anti-symmetric case, fit the SBasis slope at midpoint
*/
{
double midx = 0;
double midy = 0;
double numer;
double denom;
double div;
THROW_RANGEERROR("size of sb is too small");
}
return; // cubic bezier estimate is exact
// calculate first derivatives of x and y wrt t
for (int i = 0; i < 2; ++i) {
}
}
}
// calculate midpoint at t = 0.5
div = 2;
div *= 4;
}
div = 2;
div *= 4;
}
// is midpoint in hull: if not, the solution will be ill-conditioned, LP Bug 1428683
return;
// calculate Bezier control arms
&& ((std::abs(xprime[1]) > EPSILON) || (std::abs(yprime[1]) > EPSILON))) { // degenerate handle at 0 : use distance of closest approach
delx[0] = 0;
dely[0] = 0;
&& ((std::abs(xprime[0]) > EPSILON) || (std::abs(yprime[0]) > EPSILON))) { // degenerate handle at 1 : ditto
delx[1] = 0;
dely[1] = 0;
} else if (std::abs(xprime[1]*yprime[0] - yprime[1]*xprime[0]) > // general case : fit mid fxn value
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]);
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]);
return;
for (int i = 0; i < 2; ++i) {
}
} else if ((xprime[0]*xprime[1] < 0) || (yprime[0]*yprime[1] < 0)) { // symmetric case : use distance of closest approach
} else { // anti-symmetric case : fit mid slope
// calculate slope at t = 0.5
midx = 0;
div = 1;
div *= 4;
}
midy = 0;
div = 1;
div *= 4;
}
for (int i = 0; i < 2; ++i) {
}
} else { // linear case
for (int i = 0; i < 2; ++i) {
}
}
}
}
/** Changes the basis of p to be sbasis.
\param p the Bernstein basis polynomial
\returns the Symmetric basis polynomial
if the degree is even q is the order in the symmetrical power basis,
if the degree is odd q is the order + 1
n is always the polynomial degree, i. e. the Bezier order
*/
{
double Tjk;
for (size_t k = 0; k < q; ++k)
{
for (size_t j = k; j < q; ++j)
{
}
for (size_t j = k+1; j < q; ++j)
{
}
}
if (even)
{
for (size_t k = 0; k < q; ++k)
{
}
}
}
/** Changes the basis of d2 p to be sbasis.
\param p the d2 Bernstein basis polynomial
\returns the d2 Symmetric basis polynomial
if the degree is even q is the order in the symmetrical power basis,
if the degree is odd q is the order + 1
n is always the polynomial degree, i. e. the Bezier order
*/
{
double Tjk;
for (size_t k = 0; k < q; ++k)
{
for (size_t j = k; j < q; ++j)
{
}
for (size_t j = k+1; j < q; ++j)
{
}
}
if (even)
{
for (size_t k = 0; k < q; ++k)
{
}
}
}
} // end namespace Geom
#if 0
/*
* This version works by inverting a reasonable upper bound on the error term after subdividing the
* curve at $a$. We keep biting off pieces until there is no more curve left.
*
* Derivation: The tail of the power series is $a_ks^k + a_{k+1}s^{k+1} + \ldots = e$. A
* subdivision at $a$ results in a tail error of $e*A^k, A = (1-a)a$. Let this be the desired
* tolerance tol $= e*A^k$ and invert getting $A = e^{1/k}$ and $a = 1/2 - \sqrt{1/4 - A}$
*/
void
subpath_from_sbasis_incremental(Geom::OldPathSetBuilder &pb, D2<SBasis> B, double tol, bool initial) {
const unsigned k = 2; // cubic bezier
double te = B.tail_error(k);
//std::cout << "tol = " << tol << std::endl;
while(1) {
double a = A;
if(A < 1) {
if(a > 1) a = 1; // clamp to the end of the segment
} else
a = 1;
assert(a > 0);
//std::cout << "te = " << te << std::endl;
//std::cout << "A = " << A << "; a=" << a << std::endl;
if (initial) {
initial = false;
}
// move to next piece of curve
if(a >= 1) break;
te = B.tail_error(k);
}
}
#endif
namespace Geom{
/** Make a path from a d2 sbasis.
\param p the d2 Symmetric basis polynomial
\returns a Path
If only_cubicbeziers is true, the resulting path may only contain CubicBezier curves.
*/
void build_from_sbasis(Geom::PathBuilder &pb, D2<SBasis> const &B, double tol, bool only_cubicbeziers) {
if (!B.isFinite()) {
THROW_EXCEPTION("assertion failed: B.isFinite()");
}
} else {
// sbasis_to_bezier(bez, B, 4);
}
} else {
}
}
/** Make a path from a d2 sbasis.
\param p the d2 Symmetric basis polynomial
\returns a Path
If only_cubicbeziers is true, the resulting path may only contain CubicBezier curves.
*/
}
/** Make a path from a d2 sbasis.
\param p the d2 Symmetric basis polynomial
\returns a Path
If only_cubicbeziers is true, the resulting path may only contain CubicBezier curves.
TODO: some of this logic should be lifted into svg-path
*/
path_from_piecewise(Geom::Piecewise<Geom::D2<Geom::SBasis> > const &B, double tol, bool only_cubicbeziers) {
for(unsigned i = 0; ; i++) {
if ( (i+1 == B.size())
{
//start of a new path
//last line seg already there (because of .closePath())
goto no_add;
}
//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.
}
if (i+1 >= B.size()) {
break;
}
} else {
}
}
}
}
/*
Local Variables:
mode:c++
c-file-style:"stroustrup"
c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
indent-tabs-mode:nil
fill-column:99
End:
*/
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :