Subversion Repositories Scribus

Rev

Rev 15347 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
15347 fschmid 1
/*
2
 * bezier.h
12065 fschmid 3
 *
4
 * Copyright 2007  MenTaLguY <mental@rydia.net>
5
 * Copyright 2007  Michael Sloan <mgsloan@gmail.com>
6
 * Copyright 2007  Nathan Hurst <njh@njhurst.com>
7
 *
8
 * This library is free software; you can redistribute it and/or
9
 * modify it either under the terms of the GNU Lesser General Public
10
 * License version 2.1 as published by the Free Software Foundation
11
 * (the "LGPL") or, at your option, under the terms of the Mozilla
12
 * Public License Version 1.1 (the "MPL"). If you do not alter this
13
 * notice, a recipient may use your version of this file under either
14
 * the MPL or the LGPL.
15
 *
16
 * You should have received a copy of the LGPL along with this library
17
 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
18122 mrdocs 18
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
12065 fschmid 19
 * You should have received a copy of the MPL along with this library
20
 * in the file COPYING-MPL-1.1
21
 *
22
 * The contents of this file are subject to the Mozilla Public License
23
 * Version 1.1 (the "License"); you may not use this file except in
24
 * compliance with the License. You may obtain a copy of the License at
25
 * http://www.mozilla.org/MPL/
26
 *
27
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
28
 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
29
 * the specific language governing rights and limitations.
30
 *
31
 */
32
 
33
#ifndef SEEN_BEZIER_H
34
#define SEEN_BEZIER_H
35
 
36
#include "coord.h"
15347 fschmid 37
#include <valarray>
12065 fschmid 38
#include "isnan.h"
15347 fschmid 39
#include "bezier-to-sbasis.h"
12065 fschmid 40
#include "d2.h"
41
#include "solver.h"
42
#include <boost/optional/optional.hpp>
43
 
44
namespace Geom {
45
 
46
inline Coord subdivideArr(Coord t, Coord const *v, Coord *left, Coord *right, unsigned order) {
15347 fschmid 47
        const unsigned size=order+1;
48
        std::vector<Coord> vtemp(v,v+size);
12065 fschmid 49
 
15347 fschmid 50
    //storing left/right coordinates
51
    std::vector<Coord> nodata(size);
52
        if(left  == NULL)left=&nodata[0];
53
        if(right == NULL)right=&nodata[0];
12665 jghali 54
 
15347 fschmid 55
    /* Copy control points      */
56
        left[0]     = vtemp[0];
57
    right[order]= vtemp[order];
12065 fschmid 58
 
15347 fschmid 59
    /* Triangle computation     */
60
    for (unsigned i = 1; i < size; ++i) {
61
        for (unsigned j = 0; j < size - i; ++j) {
62
            vtemp[j] = lerp(t, vtemp[j], vtemp[j+1]);
12065 fschmid 63
        }
15347 fschmid 64
                left[i]       =vtemp[0];
65
                right[order-i]=vtemp[order-i];
12065 fschmid 66
    }
67
 
15347 fschmid 68
    return (vtemp[0]);
12065 fschmid 69
}
70
 
71
 
72
class Bezier {
73
private:
15347 fschmid 74
    std::vector<Coord> c_;
12065 fschmid 75
 
76
    friend Bezier portion(const Bezier & a, Coord from, Coord to);
77
 
15347 fschmid 78
    friend Interval bounds_fast(Bezier const & b);
12065 fschmid 79
 
80
    friend Bezier derivative(const Bezier & a);
81
 
82
protected:
15347 fschmid 83
    Bezier(Coord const c[], unsigned ord) : c_(c,c+ord+1){
12065 fschmid 84
        //std::copy(c, c+order()+1, &c_[0]);
85
    }
86
 
87
public:
88
    unsigned int order() const { return c_.size()-1;}
89
    unsigned int size() const { return c_.size();}
15347 fschmid 90
 
91
    Bezier() :c_(32) {}
12065 fschmid 92
    Bezier(const Bezier& b) :c_(b.c_) {}
93
    Bezier &operator=(Bezier const &other) {
94
        if ( c_.size() != other.c_.size() ) {
95
            c_.resize(other.c_.size());
96
        }
97
        c_ = other.c_;
98
        return *this;
99
    }
100
 
101
    struct Order {
102
        unsigned order;
103
        explicit Order(Bezier const &b) : order(b.order()) {}
104
        explicit Order(unsigned o) : order(o) {}
105
        operator unsigned() const { return order; }
106
    };
107
 
108
    //Construct an arbitrary order bezier
15347 fschmid 109
    Bezier(Order ord) : c_(ord.order+1) {
12065 fschmid 110
        assert(ord.order ==  order());
111
    }
112
 
15347 fschmid 113
    explicit Bezier(Coord c0) : c_(1) {
12065 fschmid 114
        c_[0] = c0;
115
    }
116
 
117
    //Construct an order-1 bezier (linear Bézier)
15347 fschmid 118
    Bezier(Coord c0, Coord c1) : c_(2) {
12065 fschmid 119
        c_[0] = c0; c_[1] = c1;
120
    }
121
 
122
    //Construct an order-2 bezier (quadratic Bézier)
15347 fschmid 123
    Bezier(Coord c0, Coord c1, Coord c2) : c_(3) {
12065 fschmid 124
        c_[0] = c0; c_[1] = c1; c_[2] = c2;
125
    }
126
 
127
    //Construct an order-3 bezier (cubic Bézier)
15347 fschmid 128
    Bezier(Coord c0, Coord c1, Coord c2, Coord c3) : c_(4) {
12065 fschmid 129
        c_[0] = c0; c_[1] = c1; c_[2] = c2; c_[3] = c3;
130
    }
131
 
132
    inline unsigned degree() const { return order(); }
133
 
134
    //IMPL: FragmentConcept
135
    typedef Coord output_type;
15347 fschmid 136
    inline bool isZero() const {
12065 fschmid 137
        for(unsigned i = 0; i <= order(); i++) {
138
            if(c_[i] != 0) return false;
139
        }
140
        return true;
141
    }
142
    inline bool isConstant() const {
143
        for(unsigned i = 1; i <= order(); i++) {
144
            if(c_[i] != c_[0]) return false;
145
        }
146
        return true;
147
    }
148
    inline bool isFinite() const {
149
        for(unsigned i = 0; i <= order(); i++) {
15347 fschmid 150
            if(!is_finite(c_[i])) return false;
12065 fschmid 151
        }
152
        return true;
153
    }
154
    inline Coord at0() const { return c_[0]; }
155
    inline Coord at1() const { return c_[order()]; }
156
 
15347 fschmid 157
    inline Coord valueAt(double t) const {
158
        return subdivideArr(t, &c_[0], NULL, NULL, order());
12065 fschmid 159
    }
160
    inline Coord operator()(double t) const { return valueAt(t); }
161
 
15347 fschmid 162
    inline SBasis toSBasis() const {
163
        return bezier_to_sbasis(&c_[0], order());
164
    }
12065 fschmid 165
 
166
    //Only mutator
167
    inline Coord &operator[](unsigned ix) { return c_[ix]; }
15347 fschmid 168
    inline Coord const &operator[](unsigned ix) const { return c_[ix]; }
12065 fschmid 169
    inline void setPoint(unsigned ix, double val) { c_[ix] = val; }
15347 fschmid 170
 
171
    /* This is inelegant, as it uses several extra stores.  I think there might be a way to
172
     * evaluate roughly in situ. */
173
 
12065 fschmid 174
    std::vector<Coord> valueAndDerivatives(Coord t, unsigned n_derivs) const {
15347 fschmid 175
        std::vector<Coord> val_n_der;
12665 jghali 176
 
15347 fschmid 177
        unsigned nn = n_derivs;
178
        if(nn > order())
179
            nn = order();
180
                val_n_der.reserve(n_derivs);
12665 jghali 181
 
15347 fschmid 182
                std::vector<Coord> d_(c_);
12065 fschmid 183
        for(unsigned di = 0; di < nn; di++) {
15347 fschmid 184
            val_n_der.push_back(subdivideArr(t, &d_[0], NULL, NULL, order() - di));
12065 fschmid 185
            for(unsigned i = 0; i < order() - di; i++) {
186
                d_[i] = (order()-di)*(d_[i+1] - d_[i]);
187
            }
188
        }
12665 jghali 189
 
15347 fschmid 190
        val_n_der.resize(n_derivs);
12065 fschmid 191
        return val_n_der;
192
    }
15347 fschmid 193
 
12065 fschmid 194
    std::pair<Bezier, Bezier > subdivide(Coord t) const {
195
        Bezier a(Bezier::Order(*this)), b(Bezier::Order(*this));
15347 fschmid 196
        subdivideArr(t, &c_[0], &a.c_[0], &b.c_[0], order());
12065 fschmid 197
        return std::pair<Bezier, Bezier >(a, b);
198
    }
199
 
200
    std::vector<double> roots() const {
201
        std::vector<double> solutions;
15347 fschmid 202
        find_bernstein_roots(&c_[0], order(), solutions, 0, 0.0, 1.0);
12065 fschmid 203
        return solutions;
204
    }
205
};
206
 
207
//TODO: implement others
208
inline Bezier operator+(const Bezier & a, double v) {
209
    Bezier result = Bezier(Bezier::Order(a));
210
    for(unsigned i = 0; i <= a.order(); i++)
211
        result[i] = a[i] + v;
212
    return result;
213
}
214
 
215
inline Bezier operator-(const Bezier & a, double v) {
216
    Bezier result = Bezier(Bezier::Order(a));
217
    for(unsigned i = 0; i <= a.order(); i++)
218
        result[i] = a[i] - v;
219
    return result;
220
}
221
 
222
inline Bezier operator*(const Bezier & a, double v) {
223
    Bezier result = Bezier(Bezier::Order(a));
224
    for(unsigned i = 0; i <= a.order(); i++)
225
        result[i] = a[i] * v;
226
    return result;
227
}
228
 
229
inline Bezier operator/(const Bezier & a, double v) {
230
    Bezier result = Bezier(Bezier::Order(a));
231
    for(unsigned i = 0; i <= a.order(); i++)
232
        result[i] = a[i] / v;
233
    return result;
234
}
235
 
236
inline Bezier reverse(const Bezier & a) {
237
    Bezier result = Bezier(Bezier::Order(a));
238
    for(unsigned i = 0; i <= a.order(); i++)
239
        result[i] = a[a.order() - i];
240
    return result;
241
}
242
 
243
inline Bezier portion(const Bezier & a, double from, double to) {
244
    //TODO: implement better?
15347 fschmid 245
        std::vector<Coord> res(a.order()+1);
12065 fschmid 246
    if(from == 0) {
247
        if(to == 1) { return Bezier(a); }
15347 fschmid 248
        subdivideArr(to, &a.c_[0], &res[0], NULL, a.order());
12665 jghali 249
        return Bezier(&res[0], a.order());
12065 fschmid 250
    }
15347 fschmid 251
    subdivideArr(from, &a.c_[0], NULL, &res[0], a.order());
12665 jghali 252
    if(to == 1) return Bezier(&res[0], a.order());
15347 fschmid 253
    std::vector<Coord> res2(a.order()+1);
12665 jghali 254
    subdivideArr((to - from)/(1 - from), &res[0], &res2[0], NULL, a.order());
255
    return Bezier(&res2[0], a.order());
12065 fschmid 256
}
257
 
258
// XXX Todo: how to handle differing orders
259
inline std::vector<Point> bezier_points(const D2<Bezier > & a) {
260
    std::vector<Point> result;
261
    for(unsigned i = 0; i <= a[0].order(); i++) {
262
        Point p;
263
        for(unsigned d = 0; d < 2; d++) p[d] = a[d][i];
264
        result.push_back(p);
265
    }
266
    return result;
267
}
268
 
269
inline Bezier derivative(const Bezier & a) {
15347 fschmid 270
    if(a.order() == 1) return Bezier(0.0);
12065 fschmid 271
    Bezier der(Bezier::Order(a.order()-1));
15347 fschmid 272
 
12065 fschmid 273
    for(unsigned i = 0; i < a.order(); i++) {
274
        der.c_[i] = a.order()*(a.c_[i+1] - a.c_[i]);
275
    }
276
    return der;
277
}
278
 
279
inline Bezier integral(const Bezier & a) {
280
    Bezier inte(Bezier::Order(a.order()+1));
15347 fschmid 281
 
12065 fschmid 282
    inte[0] = 0;
283
    for(unsigned i = 0; i < inte.order(); i++) {
284
        inte[i+1] = inte[i] + a[i]/(inte.order());
285
    }
286
    return inte;
287
}
288
 
15347 fschmid 289
inline Interval bounds_fast(Bezier const & b) {
290
    return Interval::fromArray(&b.c_[0], b.size());
12065 fschmid 291
}
292
 
293
//TODO: better bounds exact
15347 fschmid 294
inline Interval bounds_exact(Bezier const & b) {
12065 fschmid 295
    return bounds_exact(b.toSBasis());
296
}
297
 
15347 fschmid 298
inline Interval bounds_local(Bezier const & b, Interval i) {
299
    return bounds_fast(portion(b, i.min(), i.max()));
12065 fschmid 300
    //return bounds_local(b.toSBasis(), i);
301
}
302
 
303
inline std::ostream &operator<< (std::ostream &out_file, const Bezier & b) {
304
    for(unsigned i = 0; i < b.size(); i++) {
305
        out_file << b[i] << ", ";
306
    }
307
    return out_file;
308
}
309
 
310
}
311
#endif //SEEN_BEZIER_H
312
/*
313
  Local Variables:
314
  mode:c++
315
  c-file-style:"stroustrup"
316
  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
317
  indent-tabs-mode:nil
318
  fill-column:99
319
  End:
320
*/
321
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :