CUGL 2.3
Cornell University Game Library

#include <CUSpline2.h>
Public Member Functions  
Spline2 ()  
Spline2 (const Vec2 point)  
Spline2 (const Vec2 start, const Vec2 end)  
Spline2 (const Vec2 *points, size_t size)  
Spline2 (const std::vector< Vec2 > &points)  
Spline2 (const Spline2 &spline)  
Spline2 (Spline2 &&spline)  
~Spline2 ()  
Spline2 &  operator= (const Spline2 &spline) 
Spline2 &  operator= (Spline2 &&spline) 
Spline2 &  operator= (const Vec2 point) 
Spline2 &  set (const Vec2 point) 
Spline2 &  set (const Vec2 start, const Vec2 end) 
Spline2 &  set (const Vec2 *points, size_t size) 
Spline2 &  set (const std::vector< float > &points) 
Spline2 &  set (const std::vector< Vec2 > &points) 
Spline2 &  set (const Spline2 &spline) 
size_t  size () const 
bool  isClosed () const 
void  setClosed (bool flag) 
Vec2  getPoint (float tp) const 
void  setPoint (float tp, const Vec2 point) 
Vec2  getAnchor (size_t index) const 
void  setAnchor (size_t index, const Vec2 point) 
bool  isSmooth (size_t index) const 
void  setSmooth (size_t index, bool flag) 
Vec2  getTangent (size_t index) const 
void  setTangent (size_t index, const Vec2 tang, bool symmetric=false) 
Polynomial  getPolynomialX (size_t segment) const 
Polynomial  getPolynomialY (size_t segment) const 
const std::vector< Vec2 > &  getControlPoints () const 
size_t  addAnchor (const Vec2 point) 
size_t  addAnchor (const Vec2 point, const Vec2 tang) 
size_t  addBezier (const Vec2 control1, const Vec2 control2, const Vec2 point) 
size_t  addQuad (const Vec2 control, const Vec2 point) 
void  deleteAnchor (size_t index) 
void  insertAnchor (float param) 
void  clear () 
Vec2  nearestPoint (const Vec2 point) const 
float  nearestParameter (const Vec2 point) const 
Sint64  nearestAnchor (const Vec2 point, float threshold) const 
Sint64  nearestTangent (const Vec2 point, float threshold) const 
Protected Member Functions  
Vec2  getPoint (size_t segment, float tp) const 
void  insertAnchor (size_t segment, float param) 
void  subdivide (size_t segment, float tp, std::vector< Vec2 > &left, std::vector< Vec2 > &rght) const 
Polynomial  getProjectionPolynomial (const Vec2 point, size_t segment) const 
Vec2  getProjectionSlow (const Vec2 point, size_t segment) const 
Vec2  getProjectionFast (const Vec2 point, size_t segment) const 
bool  checkSmooth (size_t index) 
Static Protected Member Functions  
static void  subdivide (const Vec2 *src, float tp, std::vector< Vec2 > &left, std::vector< Vec2 > &rght) 
Friends  
class  SplinePather 
This class represents a spline of cubic beziers.
A bezier spline is a sequence of beziers, where the start of one is the begining of the other. A bezier spline may be open or closed. In a closed spline, the end of the last bezier is the beginning of the first (or in the case of a degenerate bezier, a bezier with the same beginning and end).
A single cubic bezier is represented by the four points. There are the two anchor points P1 and P2. These represent the start and end of the curve.
In addition, each of these points has a tangent: T1 and T2. The curve is defined so that P1 has a right tangent of T1, and P2 has a left tangent of T2. The tangents themselves are given as points, not vectors (so the tangent vector is TnPn). These four points are known as the control points. When we represent a bezier, we typically represent it as a list of four points in this order: P1, T1, T2, and P2.
In a bezier spline, the first anchor point of the next curve is the same as the last anchor point of the previous one. There is no need to duplicate this information. However, the tanget is not a duplicate, since anchor points on the interior of the spline have both a left and right tangent. Therefore, the control point list always has two tangents between any two anchors. Thus bezier spline of n beziers will contain 3n+1 control points.
This class does not contain any drawing functionality at all. If you wish to draw a bezier, create a Path2
with the SplinePather
factory. This factory creates a linesegment approximation of the spline, in much the same way that we approximate circles or ellipses when drawing them. You can then use the many features for drawing a path object, such as extrusion or wireframes.
This class has a lot of advanced methods to detect the nearest anchor, tanget, or curve location to a point. These are designed so that you can edit a bezier in a level editor for your game. These methods determine the part of the bezier closest to you mouse location, so that you can select and edit them.

inline 
Creates an empty spline.
This is a (super) degenerate spline with no control points; it is open.
cugl::Spline2::Spline2  (  const Vec2  point  ) 
Creates a degenerate spline of one point
This resulting spline consists of a single point, but it is still size 0. That is because it has no segments (and as a degenerate spline, it is open).
This constructor is useful for building up a spline incrementally.
point  The bezier anchor point 
Creates a spline of two points
The minimum spline possible has 4 points: two anchors and two tangents. This sets the start to be the first anchor point, and end to be the second. The tangents, are the same as the anchor points, which means that the tangents are degenerate. This has the effect of making the bezier a straight line from start to end. The spline is open, unless start and end are the same.
start  The first bezier anchor point 
end  The second bezier anchor point 
cugl::Spline2::Spline2  (  const Vec2 *  points, 
size_t  size  
) 
Creates a spline from the given control points.
The control points must be specified in the form
anchor, tangent, tangent, anchor, tangent ... anchor
That is, starts and ends with anchors, and every two anchors have two tangents (right of the first, left of the second) in between. As each point is two floats, the value size must be equal to 2 mod 6.
The created spline is open.
points  The array of control points 
size  The number of points in the array 
cugl::Spline2::Spline2  (  const std::vector< Vec2 > &  points  ) 
Creates a spline from the given control points.
The control points must be specified in the form
anchor, tangent, tangent, anchor, tangent ... anchor
That is, starts and ends with anchors, and every two anchors have two tangents (right of the first, left of the second) in between. The size of this vector must be equal to 1 mod 3.
The created spline is open.
points  The vector of control points 
cugl::Spline2::Spline2  (  const Spline2 &  spline  ) 
Creates a copy of the given spline.
spline  The spline to copy 

inline 
Creates a spline with the resources of the given one
spline  The spline to take from 

inline 
Deletes this spline, releasing all resources

inline 
Adds the given point to the end of the spline, creating a new segment.
Assuming that the spline is open, the new segment will start at the end of the previous last segment and extend it to the given point. This method will add a degenerate left tangent (e.g the tangent point is the same as an anchor point).
As the previous end point could not have been smooth, it will remain that way (so the right tangent of that point will be degenerate – equal to the anchor). Use setSmooth
to change the characteristic of an interior point. If the spline was super degenerate (there were no control points at all), then this method will simply add the given anchor, but keep the segment size as 0.
As closed splines have no end, this method will fail on closed splines. You should use insertAnchor
instead for closed splines.
point  The new anchor point to add to the end 
Adds the given point to the end of the spline, creating a new segment.
Assuming that the spline is open, the new segment will start at the end of the previous last segment and extend it to the given point. The value tang is the left tangent of the new anchor point.
As the previous end point could not have been smooth, it will remain that way (so the right tangent of that point will be degenerate – equal to the anchor). Use setSmooth
to change the characteristic of an interior point. If the spline was super degenerate (there were no control points at all), then this method will simply add the given anchor, but keep the segment size as 0.
As closed splines have no end, this method will fail on closed splines. You should use insertAnchor
instead for closed splines.
point  the new anchor point to add to the end 
tang  the left tangent of the new anchor point 
Adds a (cubic) bezier path from the end of the spline to point.
Assuming that the spline is open, the new segment will start at the end of the previous last segment and extend it to the given point. The given control points will define the right tangent of the previous end point, and the left tangent of point, respectively.
This method will compute whether or not the previous end point is smooth from the new right tangent. If the spline was super degenerate (there were no control points at all), then this method will build the bezier from the origin.
As closed splines have no end, this method will fail on closed splines.
control1  The first bezier control point 
control2  The second bezier control point 
point  The new anchor point 
Adds a (quadratic) bezier path from the end of the spline to point.
Assuming that the spline is open, the new segment will start at the end of the previous last segment and extend it to the given point. The new right and left tangents will be computed from the given quadratic control point.
This method will compute whether or not the previous end point is smooth from the new right tangent. If the spline was super degenerate (there were no control points at all), then this method will build the bezier from the origin.
As closed splines have no end, this method will fail on closed splines.
control  The quadratic control point 
point  The new anchor point 

protected 
Returns true if the anchor point at the given index should be smooth.
An anchor point should be smooth if the it is not an end point and the left and right tangents are (suitably) parallel.
index  The anchor point index 

inline 
Clears all control points, producing a degenerate spline.
void cugl::Spline2::deleteAnchor  (  size_t  index  ) 
Deletes the anchor point at the given index.
The point is deleted as well as both of its tangents (left and right). All remaining anchors after the deleted one will shift their indices down by one. Deletion is allowed on closed splines; the spline will remain closed after deletion.
If an open spline has n segments, then it has n+1 anchors. Similiarly, a closed spline had n anchors. The value index should be in the appropriate range.
index  the anchor index to delete 
Vec2 cugl::Spline2::getAnchor  (  size_t  index  )  const 
Returns the anchor point at the given index.
If an open spline has n segments, then it has n+1 anchors. Similiarly, a closed spline has n anchors. The value index should be in the appropriate range.
index  the anchor index (0..n+1 or 0..n) 

inline 
Returns the spline control points.
If the spline has n segments, then the list will have 6n+2 elements in it, representing the n+1 anchor points and the 2n tangents. The values will alternate
anchor, tangent, tangent, anchor, tangent ... anchor
This is true even if the curve is closed. In that case, the first and last anchor points will be the same.

inline 
Returns the spline point for parameter tp.
A bezier spline is a parameterized curve. For a single bezier, it is parameterized with tp in 0..1, with tp = 0 representing the first anchor and tp = 1 representing the second. In the spline, we generalize this idea, where tp is an anchor if it is an int, and is inbetween the anchors floor(tp) and ceil(tp) otherwise.
tp  the parameterization value 

protected 
Returns the spline point for parameter tp.
This method is like the public getPoint(), except that it is restricted to a single bezier segment. A bezier is parameterized with tp in 0..1, with tp = 0 representing the first anchor and tp = 1 representing the second. This method is used by the public getPoint() to compute its value.
segment  the bezier segment to select from 
tp  the parameterization value 
Polynomial cugl::Spline2::getPolynomialX  (  size_t  segment  )  const 
Returns the xaxis bezier polynomial for the given segment.
Bezier polynomials define the curve parameterization. They are two dimension polynomials that give a point. Rather than extend polynomial to support multidimensional data, we extract each axis separately.
We also cannot define a single polynomial for the entire spline, but we can do it for each segment. The result is a cubic poly, hence the name Spline2.
Polynomial cugl::Spline2::getPolynomialY  (  size_t  segment  )  const 
Returns the yaxis bezier polynomial for the given segment.
Bezier polynomials define the curve parameterization. They are two dimension polynomials that give a point. Rather than extend polynomial to support multidimensional data, we extract each axis separately.
We also cannot define a single polynomial for the entire spline, but we can do it for each segment. The result is a cubic poly, hence the name Spline2.
Returns the parameterization of the nearest point on the bezier segment.
The value is effectively the projection of the point onto the parametrized curve. See getPoint() for an explanation of how the parameterization work.
The value is effectively the projection of the point onto the parametrized curve. See getPoint() for an explanation of how the parameterization work. We compute this value using the projection polynomial, described at
http://jazzros.blogspot.com/2011/03/projectingpointonbeziercurve.html
The value returned is a pair of the parameter, and its distance value. This allows us to compare this result to other segments, picking the best value for the entire spline.
This algorithm uses the projection polynomial, and searches for roots to find the best (max of 5) candidates. However, root finding may fail, do to singularities in Bairstow's Method. If the root finder fails, then the first element of the pair will be 1 (an invalid parameter).
point  the point to project 
segment  the bezier segment to project upon 

protected 
Returns the projection polynomial for the given point.
The projection polynomial is used to find the nearest value to point on the spline, as described at
http://jazzros.blogspot.com/2011/03/projectingpointonbeziercurve.html
There is no one projection polynomial for the entire spline. Each segment bezier has its own polynomial.
point  the point to project 
segment  the bezier segment to project upon 
Returns the parameterization of the nearest point on the bezier segment.
The value is effectively the projection of the point onto the parametrized curve. See getPoint() for an explanation of how the parameterization work.
This version does not use the projection polynomial. Instead, it picks a parameter resolution and walks the entire length of the curve. The result is both slow and inexact (as the actual point may be inbetween chose parameters). This version is only picked when getProjectionFast fails because of an error with root finding.
The value returned is a pair of the parameter, and its distance value. This allows us to compare this result to other segments, picking the best value for the entire spline.
point  the point to project 
segment  the bezier segment to project upon 
Vec2 cugl::Spline2::getTangent  (  size_t  index  )  const 
Returns the tangent at the given index.
Tangents are specified as points, not vectors. To get the tangent vector for an anchor, you must subtract the anchor from its tangent point. Hence a curve is degenerate when the tangent and the anchor are the same.
If a spline has n segments, then it has 2n tangents. This is true regardless of whether it is open or closed. The value index should be in the appropriate range. An even index is a right tangent, while an odd index is a left tangent. If the spline is closed, then 2n1 is the left tangent of the first point.
index  the tangent index (0..2n) 

inline 
Inserts a new anchor point at parameter tp.
Inserting an anchor point does not change the curve. It just makes an existing point that was not an anchor, now an anchor. This is the natural behavior for inserting an index, as seen in Adobe Illustrator.
A bezier spline is a parameterized curve. For a single bezier, it is parameterized with tp in 0..1, with tp = 0 representing the first anchor and tp = 1 representing the second. In the spline, we generalize this idea, where tp is an anchor if it is an int, and is inbetween the anchors floor(tp) and ceil(tp) otherwise.
The tangents of the new anchor point will be determined by de Castlejau's. This is the natural behavior for inserting an anchor mid bezier, as seen in Adobe Illustrator.
param  the parameterization value 

protected 
Inserts a new anchor point at parameter tp.
Inserting an anchor point does not change the curve. It just makes an existing point that was not an anchor, now an anchor. This is the natural behavior for inserting an index, as seen in Adobe Illustrator.
This version of insertAnchor() specifies the segment for insertion, simplifying the parameterization. For a single bezier, it is parameterized with tp in 0..1, with tp = 0 representing the first anchor and tp = 1 representing the second.
The tangents of the new anchor point will be determined by de Castlejau's. This is the natural behavior for inserting an anchor mid bezier, as seen in Adobe Illustrator.
segment  the bezier segment to insert into 
param  the parameterization value 

inline 
Returns true if the spline is closed.
A closed spline is one where the first and last anchor are the same. Hence the first and last tangents are tangents (right, and left, respectively) of the same point. This is relevant for the setTangent() method, particularly if the change is meant to be symmetric.
When closing a spline, the end point is not a smooth point. This can be changed by calling setSmooth
.
A closed spline has no end. Therefore, anchors cannot be added to a closed spline. They may only be inserted between two other anchors.
bool cugl::Spline2::isSmooth  (  size_t  index  )  const 
Returns the smoothness for the anchor point at the given index.
A smooth anchor is one in which the derivative of the curve at the anchor is continuous. Practically, this means that the left and right tangents are always parallel. Only a nonsmooth anchor may form a "hinge".
If an open spline has n segments, then it has n+1 anchors. However, the two end anchors can never be smooth. A closed spline with the same number of segments has n anchors, but all anchors have the potential to be smooth.
index  the anchor index (0..n+1 or 0..n) 
Sint64 cugl::Spline2::nearestAnchor  (  const Vec2  point, 
float  threshold  
)  const 
Returns the index of the anchor nearest the given point.
If there is no anchor whose distance to point is less than the square root of threshold (we use lengthSquared for speed), then this method returns 1.
point  the point to compare 
threshold  the distance threshold for picking an anchor 
float cugl::Spline2::nearestParameter  (  const Vec2  point  )  const 
Returns the parameterization of the nearest point on the spline.
The value is effectively the projection of the point onto the parametrized curve. See getPoint() for an explanation of how the parameterization work. We compute this value using the projection polynomial, described at
http://jazzros.blogspot.com/2011/03/projectingpointonbeziercurve.html
point  the point to project 
Returns the nearest point on the spline to the given point.
The value is effectively the projection of the point onto the curve. We compute this point using the projection polynomial, described at
http://jazzros.blogspot.com/2011/03/projectingpointonbeziercurve.html
The point returned does not need to be an anchor point. It can be anywhere on the curve. This allows us a way to select a nonanchor point with the mouse (such as to add a new anchor point) in a level editor or other program.
point  the point to project 
Sint64 cugl::Spline2::nearestTangent  (  const Vec2  point, 
float  threshold  
)  const 
Returns the index of the tangent nearest the given point.
If there is no tangent whose distance to point is less than the square root of threshold (we use lengthSquared for speed), then this method returns 1.
point  the point to compare 
threshold  the distance threshold for picking a tangent 
Sets this spline to be a copy of the given spline.
spline  The spline to copy 
Sets this spline to be a degenerate degenerate of one point
This resulting spline consists of a single point, but it is still size 0. That is because it has no segments (and as a degenerate spline, it is open).
This assignment is useful for building up a spline incrementally.
point  The bezier anchor point 
Sets this spline to have the resources of the given one
spline  The spline to take from 
Sets this spline to be a copy of the given spline.
spline  The spline to copy 
Spline2 & cugl::Spline2::set  (  const std::vector< float > &  points  ) 
Sets this spline to have the given control points.
The control points must be specified in the form
anchor, tangent, tangent, anchor, tangent ... anchor
That is, starts and ends with anchors, and every two anchors have two tangents (right of the first, left of the second) in between. As each point is two floats, the size of the vector must be equal to 2 mod 6.
This method makes the spline is open.
points  The vector of control points as floats 
Sets this spline to have the given control points.
The control points must be specified in the form
anchor, tangent, tangent, anchor, tangent ... anchor
That is, starts and ends with anchors, and every two anchors have two tangents (right of the first, left of the second) in between. The size of this vector must be equal to 1 mod 3.
This method makes the spline is open.
points  The vector of control points 
Sets this spline to have the given control points.
The control points must be specified in the form
anchor, tangent, tangent, anchor, tangent ... anchor
That is, starts and ends with anchors, and every two anchors have two tangents (right of the first, left of the second) in between. As each point is two floats, the value size must be equal to 2 mod 6.
This method makes the spline is open.
points  The array of control points 
size  The number of points in the array 
Sets this spline to be a degenerate degenerate of one point
This resulting spline consists of a single point, but it is still size 0. That is because it has no segments (and as a degenerate spline, it is open).
This assignment is useful for building up a spline incrementally.
point  The bezier anchor point 
Sets this spline to be a line between two points
The minimum spline possible has 4 points: two anchors and two tangents. This sets the start to be the first anchor point, and end to be the second. The tangents, are the same as the anchor points, which means that the tangents are degenerate. This has the effect of making the bezier a straight line from start to end. The spline is open, unless start and end are the same.
start  The first bezier anchor point 
end  The second bezier anchor point 
void cugl::Spline2::setAnchor  (  size_t  index, 
const Vec2  point  
) 
Sets the anchor point at the given index.
This method will change both the anchor and its associated tangets. The new tangents will have the same relative change in position. As a result, the bezier will still have the same shape locally. This is the natural behavior for changing an anchor, as seen in Adobe Illustrator.
If an open spline has n segments, then it has n+1 anchors. Similiarly, a closed spline had n anchors. The value index should be in the appropriate range.
index  the anchor index (0..n+1 or 0..n) 
point  the new value to assign 
void cugl::Spline2::setClosed  (  bool  flag  ) 
Sets whether the spline is closed.
A closed spline is one where the first and last anchor are the same. Hence the first and last tangents are tangents (right, and left, respectively) of the same point. This is relevant for the setTangent() method, particularly if the change is meant to be symmetric.
When closing a spline, the end point is not a smooth point. This can be changed by calling setSmooth
.
A closed spline has no end. Therefore, anchors cannot be added to a closed spline. They may only be inserted between two other anchors.
flag  Whether the spline is closed 
void cugl::Spline2::setPoint  (  float  tp, 
const Vec2  point  
) 
Sets the spline point at parameter tp.
A bezier spline is a parameterized curve. For a single bezier, it is parameterized with tp in 0..1, with tp = 0 representing the first anchor and tp = 1 representing the second. In the spline, we generalize this idea, where tp is an anchor if it is an int, and is inbetween the anchors floor(tp) and ceil(tp) otherwise.
In this method, if tp is an int, it will just reassign the associated anchor value. Otherwise, this will insert a new anchor point at that parameter. This has a sideeffect of changing the parameterization values for the curve, as the number of beziers has increased.
tp  the parameterization value 
point  the new value to assign 
void cugl::Spline2::setSmooth  (  size_t  index, 
bool  flag  
) 
Sets the smoothness for the anchor point at the given index.
A smooth anchor is one in which the derivative of the curve at the anchor is continuous. Practically, this means that the left and right tangents are always parallel. Only a nonsmooth anchor may form a "hinge".
If you set a nonsmooth anchor to smooth, it will adjust the tangents accordingly. In particular, it will average the two tangents, making them parallel. This is the natural behavior for changing an smoothness, as seen in Adobe Illustrator.
If an open spline has n segments, then it has n+1 anchors. However, the two end anchors can never be smooth. A closed spline with the same number of segments has n anchors, but all anchors have the potential to be smooth.
index  the anchor index (0..n+1 or 0..n) 
flag  the anchor smoothness 
void cugl::Spline2::setTangent  (  size_t  index, 
const Vec2  tang,  
bool  symmetric = false 

) 
Sets the tangent at the given index.
Tangents are specified as points, not vectors. To get the tangent vector for an anchor, you must subtract the anchor from its tangent point. Hence a curve is degenerate when the tangent and the anchor are the same.
If the associated anchor point is smooth, changing the direction of the tangent vector will also change the direction of the other tangent vector (so that they remain parallel). However, changing only the magnitude will have no effect, unless symmetric is true. In that case, it will modify the other tangent so that it has the same magnitude and parallel direction. This is the natural behavior for changing a tangent, as seen in Adobe Illustrator.
If a spline has n segments, then it has 2n tangents. This is true regardless of whether it is open or closed. The value index should be in the appropriate range. An even index is a right tangent, while an odd index is a left tangent. If the spline is closed, then 2n1 is the left tangent of the first point.
index  the tangent index (0..2n) 
tang  the new value to assign 
symmetric  whether to make the other tangent symmetric 

inline 
Returns the number of segments in this spline
Each segment is a bezier. To use the bezier methods associated with this class, you will need to know the correct segment.

staticprotected 
Applies de Castlejau's to a bezier, putting the result in left & right
de Castlejau's takes a parameter tp in (0,1) and splits the bezier into two, preserving the geometric information, but not the parameterization. The control points for the resulting two beziers are stored in left and right.
This static method is not restricted to the current spline. It can work from any list of control points (and offset into those control points). This is useful for recursive subdivision.
src  the control point list for the bezier 
tp  the parameter to split at 
left  vector to store the left bezier 
rght  vector to store the right bezier 

inlineprotected 
Applies de Castlejau's to the given segment, putting the result in left & right
de Castlejau's takes a parameter tp in (0,1) and splits the bezier into two, preserving the geometric information, but not the parameterization. The control points for the resulting two beziers are stored in left and right.
segment  the bezier segment of this spine 
tp  the parameter to split at 
left  vector to store the left bezier 
rght  vector to store the right bezier 

friend 
Convert splines into paths