← Back to branch summary

~valavanisalex/ubuntu/precise/inkscape/fix-943984

« back to all changes in this revision

Viewing changes to src/2geom/bezier.h

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2009-12-24 16:10:36 UTC
  • Revision ID: james.westby@ubuntu.com-20091224161036-low9f46u1pveqd6i
Tags: 0.47.0-1ubuntu2
Brown paper bag update: actually use the correct version of the
source tree.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/2geom/bezier.h
46
46
inline Coord subdivideArr(Coord t, Coord const *v, Coord *left, Coord *right, unsigned order) {
47
47
/*
48
48
 *  Bernstein : 
49
 
 *      Evaluate a Bernstein function at a particular parameter value
 
49
 *      Evaluate a Bernstein function at a particular parameter value
50
50
 *      Fill in control points for resulting sub-curves.
51
51
 * 
52
52
 */
53
53
 
54
54
    unsigned N = order+1;
55
 
    std::valarray<Coord> vtemp(2*N);
 
55
    std::valarray<Coord> row(N);
56
56
    for (unsigned i = 0; i < N; i++)
57
 
        vtemp[i] = v[i];
 
57
        row[i] = v[i];
58
58
 
59
59
    // Triangle computation
60
60
    const double omt = (1-t);
61
61
    if(left)
62
 
        left[0] = vtemp[0];
 
62
        left[0] = row[0];
63
63
    if(right)
64
 
        right[order] = vtemp[order];
65
 
    double *prev_row = &vtemp[0];
66
 
    double *row = &vtemp[N];
 
64
        right[order] = row[order];
67
65
    for (unsigned i = 1; i < N; i++) {
68
66
        for (unsigned j = 0; j < N - i; j++) {
69
 
            row[j] = omt*prev_row[j] + t*prev_row[j+1];
 
67
            row[j] = omt*row[j] + t*row[j+1];
70
68
        }
71
69
        if(left)
72
70
            left[i] = row[0];
73
71
        if(right)
74
72
            right[order-i] = row[order-i];
75
 
        std::swap(prev_row, row);
76
73
    }
77
 
    return (prev_row[0]);
 
74
    return (row[0]);
78
75
/*
79
76
    Coord vtemp[order+1][order+1];
80
77
 
97
94
            return (vtemp[order][0]);*/
98
95
}
99
96
 
 
97
template <typename T>
 
98
inline T bernsteinValueAt(double t, T const *c_, unsigned n) {
 
99
    double u = 1.0 - t;
 
100
    double bc = 1;
 
101
    double tn = 1;
 
102
    T tmp = c_[0]*u;
 
103
    for(unsigned i=1; i<n; i++){
 
104
        tn = tn*t;
 
105
        bc = bc*(n-i+1)/i;
 
106
        tmp = (tmp + tn*bc*c_[i])*u;
 
107
    }
 
108
    return (tmp + tn*t*c_[n]);
 
109
}
 
110
 
100
111
 
101
112
class Bezier {
102
113
private:
225
236
    //inline Coord const &operator[](unsigned ix) const { return c_[ix]; }
226
237
    inline void setPoint(unsigned ix, double val) { c_[ix] = val; }
227
238
 
228
 
    /* This is inelegant, as it uses several extra stores.  I think there might be a way to
229
 
     * evaluate roughly in situ. */
230
 
 
 
239
    /**
 
240
    *  The size of the returned vector equals n_derivs+1.
 
241
    */
231
242
    std::vector<Coord> valueAndDerivatives(Coord t, unsigned n_derivs) const {
232
 
        std::vector<Coord> val_n_der;
 
243
        /* This is inelegant, as it uses several extra stores.  I think there might be a way to
 
244
         * evaluate roughly in situ. */
 
245
 
 
246
         // initialize return vector with zeroes, such that we only need to replace the non-zero derivs
 
247
        std::vector<Coord> val_n_der(n_derivs + 1, Coord(0.0));
 
248
 
 
249
        // initialize temp storage variables
233
250
        std::valarray<Coord> d_(order()+1);
234
 
        unsigned nn = n_derivs + 1;     // the size of the result vector equals n_derivs+1 ...
235
 
        if(nn > order())
236
 
            nn = order()+1;             // .. but with a maximum of order() + 1!
237
 
        for(unsigned i = 0; i < size(); i++)
 
251
        for (unsigned i = 0; i < size(); i++) {
238
252
            d_[i] = c_[i];
239
 
        for(unsigned di = 0; di < nn; di++) {
240
 
            val_n_der.push_back(subdivideArr(t, &d_[0], NULL, NULL, order() - di));
241
 
            for(unsigned i = 0; i < order() - di; i++) {
 
253
        }
 
254
 
 
255
        unsigned nn = n_derivs + 1;
 
256
        if(n_derivs > order()) {
 
257
            nn = order()+1; // only calculate the non zero derivs
 
258
        }
 
259
        for (unsigned di = 0; di < nn; di++) {
 
260
            //val_n_der[di] = (subdivideArr(t, &d_[0], NULL, NULL, order() - di));
 
261
            val_n_der[di] = bernsteinValueAt(t, &d_[0], order() - di);
 
262
            for (unsigned i = 0; i < order() - di; i++) {
242
263
                d_[i] = (order()-di)*(d_[i+1] - d_[i]);
243
264
            }
244
265
        }
245
 
        val_n_der.resize(n_derivs);
 
266
 
246
267
        return val_n_der;
247
268
    }
248
269
 
257
278
        find_bernstein_roots(&const_cast<std::valarray<Coord>&>(c_)[0], order(), solutions, 0, 0.0, 1.0);
258
279
        return solutions;
259
280
    }
 
281
    std::vector<double> roots(Interval const ivl) const {
 
282
        std::vector<double> solutions;
 
283
        find_bernstein_roots(&const_cast<std::valarray<Coord>&>(c_)[0], order(), solutions, 0, ivl[0], ivl[1]);
 
284
        return solutions;
 
285
    }
260
286
};
261
287
 
262
288