synfig-core/trunk/src/synfig/curve_helper.h

   1 /* === S Y N F I G ========================================================= */
   2 /*!     \file curve_helper.h
   3 **      \brief Curve Helper Header
   4 **
   5 **      $Id: curve_helper.h,v 1.1.1.1 2005/01/04 01:23:14 darco Exp $
   6 **
   7 **      \legal
   8 **      Copyright (c) 2002 Robert B. Quattlebaum Jr.
   9 **
  10 **      This software and associated documentation
  11 **      are CONFIDENTIAL and PROPRIETARY property of
  12 **      the above-mentioned copyright holder.
  13 **
  14 **      You may not copy, print, publish, or in any
  15 **      other way distribute this software without
  16 **      a prior written agreement with
  17 **      the copyright holder.
  18 **      \endlegal
  19 */
  20 /* ========================================================================= */
  21
  22 /* === S T A R T =========================================================== */
  23
  24 #ifndef __SYNFIG_CURVE_HELPER_H
  25 #define __SYNFIG_CURVE_HELPER_H
  26
  27 /* === H E A D E R S ======================================================= */
  28 #include <ETL/bezier>
  29
  30 #include "rect.h"
  31 #include "real.h"
  32 #include "vector.h"
  33
  34 #include <vector>
  35
  36 /* === M A C R O S ========================================================= */
  37
  38 /* === T Y P E D E F S ===================================================== */
  39
  40 /* === C L A S S E S & S T R U C T S ======================================= */
  41
  42 namespace synfig {
  43
  44 //line helper functions
  45 inline Real line_point_distsq(const Point &p1, const Point &p2,
  46                                                                                 const Point &p, float &t)
  47 {
  48         Vector v,vt;
  49
  50         v = p2 - p1;
  51         vt = p - p1;
  52
  53         t = v.mag_squared() > 1e-12 ? (vt*v)/v.mag_squared() : 0; //get the projected time value for the current line
  54
  55         //get distance to line segment with the time value clamped 0-1
  56         if(t >= 1)      //use p+v
  57         {
  58                 vt += v; //makes it pp - (p+v)
  59                 t = 1;
  60         }else if(t > 0) //use vt-proj
  61         {
  62                 vt -= v * t; // vt - proj_v(vt) //must normalize the projection vector to work
  63         }else
  64         {
  65                 t = 0;
  66         }
  67
  68         //else use p
  69         return vt.mag_squared();
  70 }
  71
  72
  73 //----- RAY CLASS AND FUNCTIONS --------------
  74 struct Ray
  75 {
  76         Point   p;
  77         Vector  v;
  78
  79         Ray() {}
  80         Ray(const Point &pin, const Vector &vin):p(pin), v(vin) {}
  81 };
  82
  83 /* This algorithm calculates the INTERSECTION of 2 line segments
  84         (not the closest point or anything like that, just intersection)
  85         //parameter values returned are [0,1]
  86 */
  87 int intersect(const Point &p1, const Vector &v1, float &t1,
  88                                 const Point &p2, const Vector &v2, float &t2);
  89
  90 inline bool intersect_line_segments(const Point &a, const Point &b, float &tout,
  91                                                                                 const Point &c, const Point &d, float &sout)
  92 {
  93         Vector v1(b-a), v2(d-c);
  94
  95         //ok so treat both lines as parametric (so we can find the time values simultaneously)
  96         float t,s;
  97
  98         if( intersect(a,v1,t, b,v2,s) && t >= 0 && t <= 1 && s >= 0 && s <= 1 )
  99         {
 100                 tout = t;
 101                 sout = s;
 102                 return true;
 103         }
 104
 105         return false;
 106 }
 107
 108 //Find the closest point on the curve to a point (and return it's distance, and time value)
 109 Real find_closest(const etl::bezier<Point> &curve, const Point &point, float step, Real *closest, float *t);
 110
 111 //----------- Rectangle helper functions ---------------
 112
 113 template < typename T >
 114 inline void Bound(etl::rect<T> &r, const etl::bezier<Point> &b)
 115 {
 116         r.set_point(b[0][0],b[0][1]);
 117         r.expand(b[1][0],b[1][1]);
 118         r.expand(b[2][0],b[2][1]);
 119         r.expand(b[3][0],b[3][1]);
 120 }
 121
 122 /*template < typename T >
 123 inline bool intersect(const etl::rect<T> &r1, const etl::rect<T> &r2)
 124 {
 125         return (r1.minx < r2.maxx) &
 126                         (r2.minx < r1.maxx) &
 127                         (r1.miny < r2.maxy) &
 128                         (r2.miny < r1.maxy);
 129 }*/
 130
 131 //----- Convex Hull of a Bezier Curve --------------
 132 struct BezHull
 133 {
 134         Point   p[4];
 135         int             size;
 136
 137         void Bound(const etl::bezier<Point> &b);
 138 };
 139
 140 //Line Intersection
 141 int intersect(const Rect &r1, const Point &p, const Vector &v);
 142 int intersect(const Rect &r1, const Point &p); //inside or to the right
 143 int intersect(const BezHull &bh, const Point &p, const Vector &v);
 144 //int intersect(const etl::bezier<Point> &b, const Point &p, const Vector &v);
 145 int intersect(const etl::bezier<Point> &b, const Point &p); //for use in containment tests for regions
 146
 147 //Curve intersection object
 148 class CIntersect
 149 {
 150 public:
 151         struct SCurve;
 152 private:
 153         void recurse_intersect(const SCurve &left, const SCurve &right, int depth = 0);
 154
 155 public:
 156         //size should be equal
 157         typedef std::vector< std::pair<float,float > >  intersect_set;
 158         intersect_set   times;
 159
 160         int             max_depth;
 161
 162         CIntersect();
 163
 164         bool operator()(const etl::bezier<Point> &b1, const etl::bezier<Point> &b2);
 165 };
 166
 167 }; // END of namespace studio
 168
 169 /* === E N D =============================================================== */
 170
 171 #endif