Logo Search packages:      
Sourcecode: inkscape version File versions

int Geom::bezier_fit_cubic_full ( Point  bezier[],
int  split_points[],
Point const   data[],
int const   len,
Point const &  tHat1,
Point const &  tHat2,
double const   error,
unsigned const   max_beziers 
)

Fit a multi-segment Bezier curve to a set of digitized points, without possible weedout of identical points and NaNs.

Precondition:
data is uniqued, i.e. not exist i: data[i] == data[i + 1].
Parameters:
max_beziers Maximum number of generated segments
Result array, must be large enough for n. segments * 4 elements.

Definition at line 199 of file bezier-utils.cpp.

References chord_length_parameterize(), compute_max_error_ratio(), darray_center_tangent(), generate_bezier(), is_zero(), and reparameterize().

Referenced by bezier_fit_cubic_r(), fit_and_split(), and sp_spiral_fit_and_draw().

{
    int const maxIterations = 4;   /* std::max times to try iterating */
    
    if(!(bezier != NULL) ||
       !(data != NULL) ||
       !(len > 0) ||
       !(max_beziers >= 1) ||
       !(error >= 0.0))
        return -1;

    if ( len < 2 ) return 0;

    if ( len == 2 ) {
        /* We have 2 points, which can be fitted trivially. */
        bezier[0] = data[0];
        bezier[3] = data[len - 1];
        double const dist = distance(bezier[0], bezier[3]) / 3.0;
        if (IS_NAN(dist)) {
            /* Numerical problem, fall back to straight line segment. */
            bezier[1] = bezier[0];
            bezier[2] = bezier[3];
        } else {
            bezier[1] = ( is_zero(tHat1)
                          ? ( 2 * bezier[0] + bezier[3] ) / 3.
                          : bezier[0] + dist * tHat1 );
            bezier[2] = ( is_zero(tHat2)
                          ? ( bezier[0] + 2 * bezier[3] ) / 3.
                          : bezier[3] + dist * tHat2 );
        }
        BEZIER_ASSERT(bezier);
        return 1;
    }

    /*  Parameterize points, and attempt to fit curve */
    unsigned splitPoint;   /* Point to split point set at. */
    bool is_corner;
    {
        double *u = new double[len];
        chord_length_parameterize(data, u, len);
        if ( u[len - 1] == 0.0 ) {
            /* Zero-length path: every point in data[] is the same.
             *
             * (Clients aren't allowed to pass such data; handling the case is defensive
             * programming.)
             */
            delete[] u;
            return 0;
        }

        generate_bezier(bezier, data, u, len, tHat1, tHat2, error);
        reparameterize(data, len, u, bezier);

        /* Find max deviation of points to fitted curve. */
        double const tolerance = sqrt(error + 1e-9);
        double maxErrorRatio = compute_max_error_ratio(data, u, len, bezier, tolerance, &splitPoint);

        if ( fabs(maxErrorRatio) <= 1.0 ) {
            BEZIER_ASSERT(bezier);
            delete[] u;
            return 1;
        }

        /* If error not too large, then try some reparameterization and iteration. */
        if ( 0.0 <= maxErrorRatio && maxErrorRatio <= 3.0 ) {
            for (int i = 0; i < maxIterations; i++) {
                generate_bezier(bezier, data, u, len, tHat1, tHat2, error);
                reparameterize(data, len, u, bezier);
                maxErrorRatio = compute_max_error_ratio(data, u, len, bezier, tolerance, &splitPoint);
                if ( fabs(maxErrorRatio) <= 1.0 ) {
                    BEZIER_ASSERT(bezier);
                    delete[] u;
                    return 1;
                }
            }
        }
        delete[] u;
        is_corner = (maxErrorRatio < 0);
    }

    if (is_corner) {
        assert(splitPoint < unsigned(len));
        if (splitPoint == 0) {
            if (is_zero(tHat1)) {
                /* Got spike even with unconstrained initial tangent. */
                ++splitPoint;
            } else {
                return bezier_fit_cubic_full(bezier, split_points, data, len, unconstrained_tangent, tHat2,
                                                error, max_beziers);
            }
        } else if (splitPoint == unsigned(len - 1)) {
            if (is_zero(tHat2)) {
                /* Got spike even with unconstrained final tangent. */
                --splitPoint;
            } else {
                return bezier_fit_cubic_full(bezier, split_points, data, len, tHat1, unconstrained_tangent,
                                                error, max_beziers);
            }
        }
    }

    if ( 1 < max_beziers ) {
        /*
         *  Fitting failed -- split at max error point and fit recursively
         */
        unsigned const rec_max_beziers1 = max_beziers - 1;

        Point recTHat2, recTHat1;
        if (is_corner) {
            if(!(0 < splitPoint && splitPoint < unsigned(len - 1)))
               return -1;
            recTHat1 = recTHat2 = unconstrained_tangent;
        } else {
            /* Unit tangent vector at splitPoint. */
            recTHat2 = darray_center_tangent(data, splitPoint, len);
            recTHat1 = -recTHat2;
        }
        int const nsegs1 = bezier_fit_cubic_full(bezier, split_points, data, splitPoint + 1,
                                                     tHat1, recTHat2, error, rec_max_beziers1);
        if ( nsegs1 < 0 ) {
#ifdef BEZIER_DEBUG
            g_print("fit_cubic[1]: recursive call failed\n");
#endif
            return -1;
        }
        assert( nsegs1 != 0 );
        if (split_points != NULL) {
            split_points[nsegs1 - 1] = splitPoint;
        }
        unsigned const rec_max_beziers2 = max_beziers - nsegs1;
        int const nsegs2 = bezier_fit_cubic_full(bezier + nsegs1*4,
                                                     ( split_points == NULL
                                                       ? NULL
                                                       : split_points + nsegs1 ),
                                                     data + splitPoint, len - splitPoint,
                                                     recTHat1, tHat2, error, rec_max_beziers2);
        if ( nsegs2 < 0 ) {
#ifdef BEZIER_DEBUG
            g_print("fit_cubic[2]: recursive call failed\n");
#endif
            return -1;
        }

#ifdef BEZIER_DEBUG
        g_print("fit_cubic: success[nsegs: %d+%d=%d] on max_beziers:%u\n",
                nsegs1, nsegs2, nsegs1 + nsegs2, max_beziers);
#endif
        return nsegs1 + nsegs2;
    } else {
        return -1;
    }
}


Generated by  Doxygen 1.6.0   Back to index