CUCubicSpline.h

//
//  CUCubicSpline.h
//  Cornell Extensions to Cocos2D
//
//  This module provides a class that represents a spline of cubic beziers. A
//  bezier spline is just a sequence of beziers joined together, so that the end
//  of one is the beginning of the other. Cubic beziers have four control points,
//  two for the vertex anchors and two for their tangents.
//
//  Cocos2d does have a lot of spline support.  In addition to cubic beziers, it
//  also has quadratic beziers, cardinal splines, and Catmull-Rom splines.  However,
//  in true Cocos2d fashion, these are all tightly coupled with drawing code.  We do
//  not want splines embedded with drawing code.  We want a mathematics object that
//  we can adjust and compute with. Hence the purpose of this class.  We chose
//  cubic splines because they are the most natural for editting (as seen in
//  Adobe Illustrator).
//
//  If you want to draw a CubicSpline, use the allocPath() method to allocate a Poly2
//  value for the spline.  We have to turn shapes into polygons to draw them anyway,
//  and this allows us to do all of the cool things we can already do with paths,
//  like extrude them or create wireframes.
//
//  Math data types are much lighter-weight than other objects, and are intended to
//  be copied.  That is why we do not use reference counting for these objects.
//
//  Author: Walker White
//  Version: 11/24/15
//
#ifndef __CU_CUBIC_SPLINE_H__
#define __CU_CUBIC_SPLINE_H__

#include "CUPoly2.h"

NS_CC_BEGIN

class Polynomial;

#define DEFAULT_TOLERANCE   0.25

#pragma mark -
#pragma mark CubicSpline

class CC_DLL CubicSpline {
protected:
    
    int _size;
    
    vector<Vec2> _points;
    
    vector<bool>  _smooth;
    
    bool _closed;

    
public:
    enum Criterion {
        FLAT,
        
        DISTANCE,
        
        SPACING
    };

    
#pragma mark Constructors

    CubicSpline() : CubicSpline(Vec2::ZERO,Vec2::ZERO)    {   }
    
    CubicSpline(const Vec2& point) : CubicSpline(point,point)  {    }
    
    CubicSpline(const Vec2& start, const Vec2& end);

    CubicSpline(const float* points, int size, int offset=0);

    CubicSpline(const vector<float>& points);

    CubicSpline(const vector<Vec2>& points);

    CubicSpline(const CubicSpline& spline);

    ~CubicSpline() { }


#pragma mark Attribute Accessors

    int getSize() const { return _size; }
    
    bool getClosed() const { return _closed; }
    
    void setClosed(bool flag);
    
    Vec2 getPoint(float tp) const { return getPoint((int)tp,tp-(int)tp); }

    void setPoint(float tp, const Vec2& point);
    
    Vec2 getAnchor(int index) const;
    
    void setAnchor(int index, const Vec2& point);

    bool getSmooth(int index) const;
    
    void setSmooth(int index, bool flag);

    Vec2 getTangent(int index) const;

    void setTangent(int index, const Vec2& tang, bool symmetric=false);
    
    Polynomial getPolynomialX(int segment) const;

    Polynomial getPolynomialY(int segment) const;

    const vector<Vec2> getControlPoints() const { return _points; }

    
#pragma mark Anchor Editting Methods

    int addAnchor(const Vec2& point) { return addAnchor(point,point); }

    int addAnchor(const Vec2& point, const Vec2& tang);
    
    void deleteAnchor(int index);
    
    void insertAnchor(float param)  { insertAnchor((int)param,param-(int)param); }
    

#pragma mark Nearest Point Methods

    Vec2 nearestPoint(const Vec2& point) const { return getPoint(nearestParameter(point)); }

    float nearestParameter(const Vec2& point) const;
    
    int nearestAnchor(const Vec2& point, float threshold) const;

    int nearestTangent(const Vec2& point, float threshold) const;

    
#pragma mark Polygon Approximation

    vector<Vec2> approximate(float tolerance=DEFAULT_TOLERANCE,
                             Criterion criterion=Criterion::DISTANCE) const;

    vector<float> approximateParameters(float tolerance=DEFAULT_TOLERANCE,
                                       Criterion criterion=Criterion::DISTANCE) const;
    
    vector<Vec2> approximateTangents(float tolerance=DEFAULT_TOLERANCE,
                                     Criterion criterion=Criterion::DISTANCE) const;
    
    vector<Vec2> approximateNormals(float tolerance=DEFAULT_TOLERANCE,
                                    Criterion criterion=Criterion::DISTANCE) const;

    CubicSpline refine(float tolerance=DEFAULT_TOLERANCE,
                      Criterion criterion=Criterion::DISTANCE) const;
    
#pragma mark Rendering Data

    Poly2* allocPath(float tolerance=DEFAULT_TOLERANCE,
                     Criterion criterion=Criterion::DISTANCE) const;

    Poly2* allocTangents() const;

    Poly2* allocAnchors(float radius, int segments=4) const;

    Poly2* allocHandles(float radius, int segments=4) const;


#pragma mark Internal Helpers
protected:
    Vec2 getPoint(int segment, float tp) const;
    
    void insertAnchor(int segment, float param);
    
    void subdivide(int segment, float tp, vector<Vec2>& left, vector<Vec2>& rght) const {
        subdivide(_points,6*segment,tp,left,rght);
    }

    static void subdivide(const vector<Vec2>& src, int soff, float tp,
                          vector<Vec2>& left, vector<Vec2>& rght);


    Polynomial getProjectionPolynomial(const Vec2& point, int segment) const;
    
    Vec2 getProjectionSlow(const Vec2& point, int segment) const;
    
    Vec2 getProjectionFast(const Vec2& point, int segment) const;



#pragma mark Recursive Data Generation
private:
    enum Buffer {
        /* No data, just count amounts */
        EMPTY,
        /* Put curve points into the list */
        POINTS,
        /* Put curve parameters into the list */
        PARAMETERS,
        /* Put tangent points into the list */
        TANGENTS,
        /* Put normals vectors into the list */
        NORMALS,
        /* Put all control points into the list */
        ALL
    };
    
    static int generate_data(const vector<Vec2>& src, int soff, float tp,
                             float tolerance, Criterion criterion,
                             void* buffer, Buffer bufferType, int depth);

};

NS_CC_END
#endif /* defined(__CU_CUBIC_SPLINE_H__) */