1//----------------------------------------------------------------------------
2// Anti-Grain Geometry - Version 2.4
3// Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com)
4// Copyright (C) 2005 Tony Juricic (tonygeek@yahoo.com)
5//
6// Permission to copy, use, modify, sell and distribute this software
7// is granted provided this copyright notice appears in all copies.
8// This software is provided "as is" without express or implied
9// warranty, and with no claim as to its suitability for any purpose.
10//
11//----------------------------------------------------------------------------
12// Contact: mcseem@antigrain.com
13//          mcseemagg@yahoo.com
14//          http://www.antigrain.com
15//----------------------------------------------------------------------------
16
17#ifndef AGG_CURVES_INCLUDED
18#define AGG_CURVES_INCLUDED
19
20#include "agg_array.h"
21
22namespace agg
23{
24
25    // See Implementation agg_curves.cpp
26
27    //--------------------------------------------curve_approximation_method_e
28    enum curve_approximation_method_e
29    {
30        curve_inc,
31        curve_div
32    };
33
34    //--------------------------------------------------------------curve3_inc
35    class curve3_inc
36    {
37    public:
38        curve3_inc() :
39          m_num_steps(0), m_step(0), m_scale(1.0) { }
40
41        curve3_inc(double x1, double y1,
42                   double x2, double y2,
43                   double x3, double y3) :
44            m_num_steps(0), m_step(0), m_scale(1.0)
45        {
46            init(x1, y1, x2, y2, x3, y3);
47        }
48
49        void reset() { m_num_steps = 0; m_step = -1; }
50        void init(double x1, double y1,
51                  double x2, double y2,
52                  double x3, double y3);
53
54        void approximation_method(curve_approximation_method_e) {}
55        curve_approximation_method_e approximation_method() const { return curve_inc; }
56
57        void approximation_scale(double s);
58        double approximation_scale() const;
59
60        void angle_tolerance(double) {}
61        double angle_tolerance() const { return 0.0; }
62
63        void cusp_limit(double) {}
64        double cusp_limit() const { return 0.0; }
65
66        void     rewind(unsigned path_id);
67        unsigned vertex(double* x, double* y);
68
69    private:
70        int      m_num_steps;
71        int      m_step;
72        double   m_scale;
73        double   m_start_x;
74        double   m_start_y;
75        double   m_end_x;
76        double   m_end_y;
77        double   m_fx;
78        double   m_fy;
79        double   m_dfx;
80        double   m_dfy;
81        double   m_ddfx;
82        double   m_ddfy;
83        double   m_saved_fx;
84        double   m_saved_fy;
85        double   m_saved_dfx;
86        double   m_saved_dfy;
87    };
88
89
90
91
92
93    //-------------------------------------------------------------curve3_div
94    class curve3_div
95    {
96    public:
97        curve3_div() :
98            m_approximation_scale(1.0),
99            m_distance_tolerance_square(0.0),
100            m_angle_tolerance(0.0),
101            m_count(0)
102        {}
103
104        curve3_div(double x1, double y1,
105                   double x2, double y2,
106                   double x3, double y3) :
107            m_approximation_scale(1.0),
108            m_angle_tolerance(0.0),
109            m_count(0)
110        {
111            init(x1, y1, x2, y2, x3, y3);
112        }
113
114        void reset() { m_points.remove_all(); m_count = 0; }
115        void init(double x1, double y1,
116                  double x2, double y2,
117                  double x3, double y3);
118
119        void approximation_method(curve_approximation_method_e) {}
120        curve_approximation_method_e approximation_method() const { return curve_div; }
121
122        void approximation_scale(double s) { m_approximation_scale = s; }
123        double approximation_scale() const { return m_approximation_scale;  }
124
125        void angle_tolerance(double a) { m_angle_tolerance = a; }
126        double angle_tolerance() const { return m_angle_tolerance;  }
127
128        void cusp_limit(double) {}
129        double cusp_limit() const { return 0.0; }
130
131        void rewind(unsigned)
132        {
133            m_count = 0;
134        }
135
136        unsigned vertex(double* x, double* y)
137        {
138            if(m_count >= m_points.size()) return path_cmd_stop;
139            const point_d& p = m_points[m_count++];
140            *x = p.x;
141            *y = p.y;
142            return (m_count == 1) ? path_cmd_move_to : path_cmd_line_to;
143        }
144
145    private:
146        void bezier(double x1, double y1,
147                    double x2, double y2,
148                    double x3, double y3);
149        void recursive_bezier(double x1, double y1,
150                              double x2, double y2,
151                              double x3, double y3,
152                              unsigned level);
153
154        double               m_approximation_scale;
155        double               m_distance_tolerance_square;
156        double               m_angle_tolerance;
157        unsigned             m_count;
158        pod_bvector<point_d> m_points;
159    };
160
161
162
163
164
165
166
167    //-------------------------------------------------------------curve4_points
168    struct curve4_points
169    {
170        double cp[8];
171        curve4_points() {}
172        curve4_points(double x1, double y1,
173                      double x2, double y2,
174                      double x3, double y3,
175                      double x4, double y4)
176        {
177            cp[0] = x1; cp[1] = y1; cp[2] = x2; cp[3] = y2;
178            cp[4] = x3; cp[5] = y3; cp[6] = x4; cp[7] = y4;
179        }
180        void init(double x1, double y1,
181                  double x2, double y2,
182                  double x3, double y3,
183                  double x4, double y4)
184        {
185            cp[0] = x1; cp[1] = y1; cp[2] = x2; cp[3] = y2;
186            cp[4] = x3; cp[5] = y3; cp[6] = x4; cp[7] = y4;
187        }
188        double  operator [] (unsigned i) const { return cp[i]; }
189        double& operator [] (unsigned i)       { return cp[i]; }
190    };
191
192
193
194    //-------------------------------------------------------------curve4_inc
195    class curve4_inc
196    {
197    public:
198        curve4_inc() :
199            m_num_steps(0), m_step(0), m_scale(1.0) { }
200
201        curve4_inc(double x1, double y1,
202                   double x2, double y2,
203                   double x3, double y3,
204                   double x4, double y4) :
205            m_num_steps(0), m_step(0), m_scale(1.0)
206        {
207            init(x1, y1, x2, y2, x3, y3, x4, y4);
208        }
209
210        curve4_inc(const curve4_points& cp) :
211            m_num_steps(0), m_step(0), m_scale(1.0)
212        {
213            init(cp[0], cp[1], cp[2], cp[3], cp[4], cp[5], cp[6], cp[7]);
214        }
215
216        void reset() { m_num_steps = 0; m_step = -1; }
217        void init(double x1, double y1,
218                  double x2, double y2,
219                  double x3, double y3,
220                  double x4, double y4);
221
222        void init(const curve4_points& cp)
223        {
224            init(cp[0], cp[1], cp[2], cp[3], cp[4], cp[5], cp[6], cp[7]);
225        }
226
227        void approximation_method(curve_approximation_method_e) {}
228        curve_approximation_method_e approximation_method() const { return curve_inc; }
229
230        void approximation_scale(double s);
231        double approximation_scale() const;
232
233        void angle_tolerance(double) {}
234        double angle_tolerance() const { return 0.0; }
235
236        void cusp_limit(double) {}
237        double cusp_limit() const { return 0.0; }
238
239        void     rewind(unsigned path_id);
240        unsigned vertex(double* x, double* y);
241
242    private:
243        int      m_num_steps;
244        int      m_step;
245        double   m_scale;
246        double   m_start_x;
247        double   m_start_y;
248        double   m_end_x;
249        double   m_end_y;
250        double   m_fx;
251        double   m_fy;
252        double   m_dfx;
253        double   m_dfy;
254        double   m_ddfx;
255        double   m_ddfy;
256        double   m_dddfx;
257        double   m_dddfy;
258        double   m_saved_fx;
259        double   m_saved_fy;
260        double   m_saved_dfx;
261        double   m_saved_dfy;
262        double   m_saved_ddfx;
263        double   m_saved_ddfy;
264    };
265
266
267
268    //-------------------------------------------------------catrom_to_bezier
269    inline curve4_points catrom_to_bezier(double x1, double y1,
270                                          double x2, double y2,
271                                          double x3, double y3,
272                                          double x4, double y4)
273    {
274        // Trans. matrix Catmull-Rom to Bezier
275        //
276        //  0       1       0       0
277        //  -1/6    1       1/6     0
278        //  0       1/6     1       -1/6
279        //  0       0       1       0
280        //
281        return curve4_points(
282            x2,
283            y2,
284            (-x1 + 6*x2 + x3) / 6,
285            (-y1 + 6*y2 + y3) / 6,
286            ( x2 + 6*x3 - x4) / 6,
287            ( y2 + 6*y3 - y4) / 6,
288            x3,
289            y3);
290    }
291
292
293    //-----------------------------------------------------------------------
294    inline curve4_points
295    catrom_to_bezier(const curve4_points& cp)
296    {
297        return catrom_to_bezier(cp[0], cp[1], cp[2], cp[3],
298                                cp[4], cp[5], cp[6], cp[7]);
299    }
300
301
302
303    //-----------------------------------------------------ubspline_to_bezier
304    inline curve4_points ubspline_to_bezier(double x1, double y1,
305                                            double x2, double y2,
306                                            double x3, double y3,
307                                            double x4, double y4)
308    {
309        // Trans. matrix Uniform BSpline to Bezier
310        //
311        //  1/6     4/6     1/6     0
312        //  0       4/6     2/6     0
313        //  0       2/6     4/6     0
314        //  0       1/6     4/6     1/6
315        //
316        return curve4_points(
317            (x1 + 4*x2 + x3) / 6,
318            (y1 + 4*y2 + y3) / 6,
319            (4*x2 + 2*x3) / 6,
320            (4*y2 + 2*y3) / 6,
321            (2*x2 + 4*x3) / 6,
322            (2*y2 + 4*y3) / 6,
323            (x2 + 4*x3 + x4) / 6,
324            (y2 + 4*y3 + y4) / 6);
325    }
326
327
328    //-----------------------------------------------------------------------
329    inline curve4_points
330    ubspline_to_bezier(const curve4_points& cp)
331    {
332        return ubspline_to_bezier(cp[0], cp[1], cp[2], cp[3],
333                                  cp[4], cp[5], cp[6], cp[7]);
334    }
335
336
337
338
339    //------------------------------------------------------hermite_to_bezier
340    inline curve4_points hermite_to_bezier(double x1, double y1,
341                                           double x2, double y2,
342                                           double x3, double y3,
343                                           double x4, double y4)
344    {
345        // Trans. matrix Hermite to Bezier
346        //
347        //  1       0       0       0
348        //  1       0       1/3     0
349        //  0       1       0       -1/3
350        //  0       1       0       0
351        //
352        return curve4_points(
353            x1,
354            y1,
355            (3*x1 + x3) / 3,
356            (3*y1 + y3) / 3,
357            (3*x2 - x4) / 3,
358            (3*y2 - y4) / 3,
359            x2,
360            y2);
361    }
362
363
364
365    //-----------------------------------------------------------------------
366    inline curve4_points
367    hermite_to_bezier(const curve4_points& cp)
368    {
369        return hermite_to_bezier(cp[0], cp[1], cp[2], cp[3],
370                                 cp[4], cp[5], cp[6], cp[7]);
371    }
372
373
374    //-------------------------------------------------------------curve4_div
375    class curve4_div
376    {
377    public:
378        curve4_div() :
379            m_approximation_scale(1.0),
380            m_distance_tolerance_square(0.0),
381            m_angle_tolerance(0.0),
382            m_cusp_limit(0.0),
383            m_count(0)
384        {}
385
386        curve4_div(double x1, double y1,
387                   double x2, double y2,
388                   double x3, double y3,
389                   double x4, double y4) :
390            m_approximation_scale(1.0),
391            m_angle_tolerance(0.0),
392            m_cusp_limit(0.0),
393            m_count(0)
394        {
395            init(x1, y1, x2, y2, x3, y3, x4, y4);
396        }
397
398        curve4_div(const curve4_points& cp) :
399            m_approximation_scale(1.0),
400            m_angle_tolerance(0.0),
401            m_count(0)
402        {
403            init(cp[0], cp[1], cp[2], cp[3], cp[4], cp[5], cp[6], cp[7]);
404        }
405
406        void reset() { m_points.remove_all(); m_count = 0; }
407        void init(double x1, double y1,
408                  double x2, double y2,
409                  double x3, double y3,
410                  double x4, double y4);
411
412        void init(const curve4_points& cp)
413        {
414            init(cp[0], cp[1], cp[2], cp[3], cp[4], cp[5], cp[6], cp[7]);
415        }
416
417        void approximation_method(curve_approximation_method_e) {}
418
419        curve_approximation_method_e approximation_method() const
420        {
421            return curve_div;
422        }
423
424        void approximation_scale(double s) { m_approximation_scale = s; }
425        double approximation_scale() const { return m_approximation_scale;  }
426
427        void angle_tolerance(double a) { m_angle_tolerance = a; }
428        double angle_tolerance() const { return m_angle_tolerance;  }
429
430        void cusp_limit(double v)
431        {
432            m_cusp_limit = (v == 0.0) ? 0.0 : pi - v;
433        }
434
435        double cusp_limit() const
436        {
437            return (m_cusp_limit == 0.0) ? 0.0 : pi - m_cusp_limit;
438        }
439
440        void rewind(unsigned)
441        {
442            m_count = 0;
443        }
444
445        unsigned vertex(double* x, double* y)
446        {
447            if(m_count >= m_points.size()) return path_cmd_stop;
448            const point_d& p = m_points[m_count++];
449            *x = p.x;
450            *y = p.y;
451            return (m_count == 1) ? path_cmd_move_to : path_cmd_line_to;
452        }
453
454    private:
455        void bezier(double x1, double y1,
456                    double x2, double y2,
457                    double x3, double y3,
458                    double x4, double y4);
459
460        void recursive_bezier(double x1, double y1,
461                              double x2, double y2,
462                              double x3, double y3,
463                              double x4, double y4,
464                              unsigned level);
465
466        double               m_approximation_scale;
467        double               m_distance_tolerance_square;
468        double               m_angle_tolerance;
469        double               m_cusp_limit;
470        unsigned             m_count;
471        pod_bvector<point_d> m_points;
472    };
473
474
475    //-----------------------------------------------------------------curve3
476    class curve3
477    {
478    public:
479        curve3() : m_approximation_method(curve_div) {}
480        curve3(double x1, double y1,
481               double x2, double y2,
482               double x3, double y3) :
483            m_approximation_method(curve_div)
484        {
485            init(x1, y1, x2, y2, x3, y3);
486        }
487
488        void reset()
489        {
490            m_curve_inc.reset();
491            m_curve_div.reset();
492        }
493
494        void init(double x1, double y1,
495                  double x2, double y2,
496                  double x3, double y3)
497        {
498            if(m_approximation_method == curve_inc)
499            {
500                m_curve_inc.init(x1, y1, x2, y2, x3, y3);
501            }
502            else
503            {
504                m_curve_div.init(x1, y1, x2, y2, x3, y3);
505            }
506        }
507
508        void approximation_method(curve_approximation_method_e v)
509        {
510            m_approximation_method = v;
511        }
512
513        curve_approximation_method_e approximation_method() const
514        {
515            return m_approximation_method;
516        }
517
518        void approximation_scale(double s)
519        {
520            m_curve_inc.approximation_scale(s);
521            m_curve_div.approximation_scale(s);
522        }
523
524        double approximation_scale() const
525        {
526            return m_curve_inc.approximation_scale();
527        }
528
529        void angle_tolerance(double a)
530        {
531            m_curve_div.angle_tolerance(a);
532        }
533
534        double angle_tolerance() const
535        {
536            return m_curve_div.angle_tolerance();
537        }
538
539        void cusp_limit(double v)
540        {
541            m_curve_div.cusp_limit(v);
542        }
543
544        double cusp_limit() const
545        {
546            return m_curve_div.cusp_limit();
547        }
548
549        void rewind(unsigned path_id)
550        {
551            if(m_approximation_method == curve_inc)
552            {
553                m_curve_inc.rewind(path_id);
554            }
555            else
556            {
557                m_curve_div.rewind(path_id);
558            }
559        }
560
561        unsigned vertex(double* x, double* y)
562        {
563            if(m_approximation_method == curve_inc)
564            {
565                return m_curve_inc.vertex(x, y);
566            }
567            return m_curve_div.vertex(x, y);
568        }
569
570    private:
571        curve3_inc m_curve_inc;
572        curve3_div m_curve_div;
573        curve_approximation_method_e m_approximation_method;
574    };
575
576
577
578
579
580    //-----------------------------------------------------------------curve4
581    class curve4
582    {
583    public:
584        curve4() : m_approximation_method(curve_div) {}
585        curve4(double x1, double y1,
586               double x2, double y2,
587               double x3, double y3,
588               double x4, double y4) :
589            m_approximation_method(curve_div)
590        {
591            init(x1, y1, x2, y2, x3, y3, x4, y4);
592        }
593
594        curve4(const curve4_points& cp) :
595            m_approximation_method(curve_div)
596        {
597            init(cp[0], cp[1], cp[2], cp[3], cp[4], cp[5], cp[6], cp[7]);
598        }
599
600        void reset()
601        {
602            m_curve_inc.reset();
603            m_curve_div.reset();
604        }
605
606        void init(double x1, double y1,
607                  double x2, double y2,
608                  double x3, double y3,
609                  double x4, double y4)
610        {
611            if(m_approximation_method == curve_inc)
612            {
613                m_curve_inc.init(x1, y1, x2, y2, x3, y3, x4, y4);
614            }
615            else
616            {
617                m_curve_div.init(x1, y1, x2, y2, x3, y3, x4, y4);
618            }
619        }
620
621        void init(const curve4_points& cp)
622        {
623            init(cp[0], cp[1], cp[2], cp[3], cp[4], cp[5], cp[6], cp[7]);
624        }
625
626        void approximation_method(curve_approximation_method_e v)
627        {
628            m_approximation_method = v;
629        }
630
631        curve_approximation_method_e approximation_method() const
632        {
633            return m_approximation_method;
634        }
635
636        void approximation_scale(double s)
637        {
638            m_curve_inc.approximation_scale(s);
639            m_curve_div.approximation_scale(s);
640        }
641        double approximation_scale() const { return m_curve_inc.approximation_scale(); }
642
643        void angle_tolerance(double v)
644        {
645            m_curve_div.angle_tolerance(v);
646        }
647
648        double angle_tolerance() const
649        {
650            return m_curve_div.angle_tolerance();
651        }
652
653        void cusp_limit(double v)
654        {
655            m_curve_div.cusp_limit(v);
656        }
657
658        double cusp_limit() const
659        {
660            return m_curve_div.cusp_limit();
661        }
662
663        void rewind(unsigned path_id)
664        {
665            if(m_approximation_method == curve_inc)
666            {
667                m_curve_inc.rewind(path_id);
668            }
669            else
670            {
671                m_curve_div.rewind(path_id);
672            }
673        }
674
675        unsigned vertex(double* x, double* y)
676        {
677            if(m_approximation_method == curve_inc)
678            {
679                return m_curve_inc.vertex(x, y);
680            }
681            return m_curve_div.vertex(x, y);
682        }
683
684    private:
685        curve4_inc m_curve_inc;
686        curve4_div m_curve_div;
687        curve_approximation_method_e m_approximation_method;
688    };
689
690
691
692
693}
694
695#endif
696