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