1 /* === S Y N F I G ========================================================= */
2 /*! \file curve_helper.h
3 ** \brief Curve Helper Header
4 **
5 ** $Id$
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
line_point_distsq(const Point & p1,const Point & p2,const Point & p,float & t)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
RayRay80 Ray() {}
RayRay81 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
intersect_line_segments(const Point & a,const Point & b,float & tout,const Point & c,const Point & d,float & sout)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 its 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 >
Bound(etl::rect<T> & r,const etl::bezier<Point> & b)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 synfig
169
170 /* === E N D =============================================================== */
171
172 #endif
173