
// CPUStrokeTessellator.hpp - interface to evaluate polar stroking geometry on CPU

#ifndef __CPUStrokeTessellator_hpp__
#define __CPUStrokeTessellator_hpp__

#include <cmath>
#include <vector>
#include <stdio.h>

#include <Cg/vector/xyzw.hpp>
#include <Cg/double.hpp>
#include <Cg/vector.hpp>
#include <Cg/matrix.hpp>

#include <Cg/length.hpp>
#include <Cg/radians.hpp>
#include <Cg/floatToIntBits.hpp>

#include <GL/glew.h>  // for GLuint

using namespace Cg;

#include "../StrokeTessellatorSettings.hpp"
#include "../StrokeTessellator.hpp"
#include "../StrokerShaderConfig.hpp"

#include "../common/CommonStrokeTessellatorTypes.hpp"

extern bool use_native_atan2;

struct StrokingResults {
#ifdef __GNUC__  // Workaround for gcc 4.8.4 complaining in STL headers about Cg::__CGvector<float,2> not being a type
    float2 bogus;
#endif
    std::vector<float2> polar_offset;  // In stroking space (window space or affine portion).
    std::vector<float2> normal;

    // Clip-space position of offset curve samples: middle, positive offset, and negative offset.
    std::vector<float3> Pmid;
    std::vector<float3> Ppos;
    std::vector<float3> Pneg;

    std::vector<float> t;
    std::vector<float3> p;  // essentially Pmid_obj

    std::vector<float3> Ppos_obj;
    std::vector<float3> Pneg_obj;
    std::vector<float2> frieze_height;

    std::vector<float2> gradient;   // 1st order gradient, could be (0,0) when gradient_direction reamins valid
    std::vector<float2> gradient2;  // 2nd order gradient
    std::vector<float> curvature;
    std::vector<float3> Pradius;
    std::vector<float3> Pinfinite;
    std::vector<float> theta;

    size_t Ppos_min_ndx;
    size_t Pneg_min_ndx;
    size_t Ppos_max_ndx;
    size_t Pneg_max_ndx;

    float Pneg_min_angle;
    float Ppos_min_angle;
    float Pneg_max_angle;
    float Ppos_max_angle;

    void reset();
    StrokingResults();

    inline int numRibs() {
        return int(Pmid.size());
    }
    inline int numQuads() {
        // Number of quadrilaterals is one less than number of ribs.
        int ribs = numRibs();
        if (ribs >= 2) {
            return ribs-1;
        } else {
            return 0;
        }
    }
};

class FakeGLSLTypes {
public:
    // GLSL compatibility types.
    typedef float2 vec2;
    typedef float3 vec3;
    typedef float4 vec4;
    typedef int2 ivec2;
    typedef double2 dvec2;
    typedef unsigned int uint;
};

// Class to provide fake level-of-detail outputs.
class CPUFakeTessellator : public FakeGLSLTypes {
protected:
    // Tessellation control shader inputs
    uint gl_PrimitiveID;

    // Tessellation control shader outputs
    int gl_TessLevelInner[2];
    float gl_TessLevelOuter[4];

    CPUFakeTessellator();

public:
    bool isCulled();
    void setPrimitiveID(uint id) {
        gl_PrimitiveID = id;
    }

protected:
    uint atomicAdd(uint& value, uint bias) {
        uint old_value = value;
        value += bias;
        return old_value;
    }
    void memoryBarrierBuffer() {
        // On the GPU, this waits on the completion of all memory
        // accesses resulting from the use of buffer variables and
        // then returns with no other effect. 
        //
        // On the CPU, this does nothing.
    }

    // Grr, three names for the same function:
    // HLSL uses asint
    // GLSL uses floatBitsToInt
    // Cg uses floatToIntBits
    int floatBitsToInt(float v) {
        return floatToIntBits(v);
    }
};

struct PathDrawState {
    double accumulated_path_length;

    // Arc length texture coordinate generation
    unsigned int next_distance_offset;
    std::vector<unsigned int> link_offset;
    std::vector<float> segment_distance;
    std::vector<unsigned int> segment_add_ops;

public:
    PathDrawState();
    void dumpBuffers(size_t links);
};

// Massaged version of StrokeTessellatorSettings, embedded within CPUStrokeTessellatorUniforms
class CPUStrokeTessellatorSettingsUniforms {
protected:
    bool trivial_culling;
    const float max_turning_angle_delta;   // In radians
    const float min_window_stroke_radius;  // zero means no minimum window stroke radius adjustment
    const int draw_inside_of_round_joins;
#if SUPPORT_POLAR_VISUALIZE
    int extra_steps;  // Number of extra steps to be added between intervals of like signed curvature.
#endif

public:
    CPUStrokeTessellatorSettingsUniforms(const StrokeTessellatorSettings &init, StrokeConfigTypes::ShadingMode shading_mode = StrokeConfigTypes::CONSTANT_COLOR);

    void setTrivialCulling(bool do_culling) {
        trivial_culling = do_culling;
    }
    bool TrivialCulling() const {
        return trivial_culling;
    }
    float MaxTurningAngleDelta() const {
        return max_turning_angle_delta;
    }
#if SUPPORT_POLAR_VISUALIZE
    int ExtraSteps() const {
        return extra_steps;
    }
#endif
};

// Segregate uniforms to its own sub-class.
class CPUStrokeTessellatorUniforms
    : public FakeGLSLTypes
    , protected StrokeTessellator
    , public CPUStrokeTessellatorSettingsUniforms
{
protected:
    float stroke_radius;           // Half the stroke width
    float stroke_radius_fraction;  // Half the stroke width times arc length factor, for arc length computations.

    // Decoder ring for max_join_steps:
    // 0 = flat
    // 1 = bevel
    // 2 = triangular
    // max_strips*max_ribs_per_strip=round
    // -1 = miter revert
    // -2 = miter truncate
    int max_join_steps;
    float effective_miter_limit;  // Limit on how many join steps when non-negative; negative values indicates miter mode
    // miter_extension_limit should be 2x miter limit for miter truncate to match NV_path_rendering & Qt miter limit meaning
    float miter_extension_limit;  // computed from effective_miter_limit by ComputeMiterExtensionLimit
    // Enumeration for cap_placement_to_type bitfields: 0 = none, 1 = round, 2 = triangular, 3 = square
    uint cap_placement_to_type;  // 4 8-bit fields: initial (7:0), terminal (15:8), dash intial (23:16), dash-terminal (31:24)
    float4 viewport_scale;   // stored as (0.5*width,0.5*height,1/(width*0.5),1/(height*0.5))

    // Uniforms for evalPerspectiveThetaChange
    float4 u1234;  // u1, u2, u3, u4
    float4 ab1ab2; // a1, b1, a2, b2
    float4 c1c2;   // c1, c2

    // Uniforms for arc length texture coordinate generation
    uint next_distance_offset_dummy;
    uint& next_distance_offset;
    uint pass_number;  // 0 for segment arc length computation, 1 for segment arc length accumulation.
    uint path_offset;  // Current path's offset into link_offset buffer;
    uint* link_offset;
    float* segment_distance;
    uint* segment_add_ops;
    float arc_length_texgen_scale;

    CPUStrokeTessellatorUniforms(const StrokeTessellatorSettings&);
    CPUStrokeTessellatorUniforms(const StrokeTessellatorSettings&, StrokeConfigTypes::ShadingMode shading_mode, PathDrawState& state);
    CPUStrokeTessellatorUniforms(const StrokeTessellatorSettings&, StrokeConfigTypes::ShadingMode shading_mode, PathDrawState& state, float stroke_width, float arc_length_extension, int max_join_steps, float effective_miter_limit, unsigned int cap_placement_to_type);

private:
    float ComputeMiterExtensionLimit(float effective_miter_limit) const;  // Used by ctors to initialize extension_miter_limit.
public:
    void loadTransformUniforms(const float3x3& inverse_object_to_window_space);
    void setStrokeRadius(float radius);
    void setStrokeWidth(float width);
    void setStrokeRadiusFraction(float value);
    void setMaxJoinSteps(int max_join_steps);
    void setCapMask(unsigned int cap_mask);
    void setEffectiveMiterLimit(float v);

    // Methods for arc length texture coordinate generation
    void setPassNumber(int v) {
        pass_number = v;
    }
    void setPathOffset(uint v) {
        path_offset = v;
    }
};

class CPUStrokeTessellatorInterface
    : public FakeGLSLTypes
{
public:
    // Types used in findInflectionPoints
#if 1
    typedef dvec2 VECTOR;
    typedef double SCALAR;
#else
    typedef vec2 VECTOR;
    typedef float SCALAR;
#endif

protected:
    static const int NUM_THREADS = 32;

    // Control point type
    // These is sometimes float2 in the GPU code!
    typedef float3 CPtype;   // Transformed control point type (on GPU, float3 when rational points or non-affine transform; otherwise float2)
    typedef float3 CPOtype;  // Original control point type (on GPU, float3 when rational control points; otherwise float2)

//// Vertex shader to tessellation control shader interface:

    int vertex_id[6]; // vertex ID
    float3 hpos[6];
    // Stroking-space (object or window) input and output control points
    CPtype v[6];
    // Object-space input and output control points
    float3 v_orig[6];

//// Tessellator control shader to tessellation evaluation interface:

    CPtype cp[NUM_THREADS];        // control points in space for stroking
    CPOtype cp_orig[NUM_THREADS];  // original control points in space for stroking

    // Values computed by "control" shader, and used by "evaluation" shader
    float delta[NUM_THREADS];  // 0, D0A, D0AB, delta_D0AB1
    float theta[NUM_THREADS];  // theta0, thetaA, thetaB, theta1
    float tbounds[NUM_THREADS];  // 0,tA,tB,1

    // link_state:
    //   [1] = isCapOrNonRoundJoin, [1]==2 = round join, [1]==0, isNeitherJoinNorCap
    //   [2] = isQuadratic
    //   [3]!=0 = treat_as_miter, [3]<0 = square
    int link_state[NUM_THREADS];

    // Monomial cubic gradient coefficients (A, B, and C)
    float A_C[NUM_THREADS];  // A.x, C.x, A.y, C.y
    float B_bogus[NUM_THREADS];  // B.x, B.y, and bogus Z and W

    // orientationBitMask = sign of sgnCurvature0A, sgnCurvatureAB, sgnCurvatureB0
    uint row_columns_orientationBitMask_steps[NUM_THREADS];  // // rows, columns, orientationBitMask, steps

    // Integer temporary for inter-thread communication (not used by evaluation shader).
    int int_tmp[NUM_THREADS];      // XXX not really used by CPU code (yet?)
    float delta_alt[NUM_THREADS];  // XXX not really used by CPU code (yet?)
    VECTOR v1[NUM_THREADS];        // XXX not really used by CPU code (yet?)
    SCALAR v2[NUM_THREADS];        // XXX not really used by CPU code (yet?)

    uint primitiveID_x_x_x[NUM_THREADS];  // primitiveID, unused, unused, unused
    float delta_steps[NUM_THREADS];  // 0, D0A_steps, D0AB_steps, delta_D0AB1_steps

    float dtheta_dsteps[NUM_THREADS];

    // Tessellation evaluation shader outputs
    vec2 pervertex_offset;  // Normal vector.
    vec2 pervertex_radius;  // vec2(-radius,radius) or, for joins and caps, vec2(0,+/-radius);
    CPtype pervertex_p;
    float pervertex_t;  // output for CPU only
    float pervertex_arc_length;

    CPUStrokeTessellatorInterface();
    void print(FILE* fp) const;
};

class CPUStrokeTessellator
    : public CPUFakeTessellator
    , public CPUStrokeTessellatorUniforms
    , CPUStrokeTessellatorInterface
{
public:
    enum StrokeSpaceEnum {
        WINDOW_SPACE,
        EYE_SPACE,
        OBJECT_SPACE
    };

private:
    StrokeSpaceEnum stroke_space;
    float3x3 modelview;             // Modelview
    float3x3 projection;            // Projection
    float3x3 modelview_projection;  // Modelview=>Projection

    float3x3 object_to_window_space;  // transform to window space
    float3x3 inverse_object_to_window_space;  // transform to window space

    float angleDelta_stash[3];  // XXX for setSteps

    // Extra saved results: D01, D12, D23
    float2 grad_cp[3];
    float stashed_D0AB1;
    int stashed_link_type;

    StrokingResults* results;

    // Control helper functions
    bool transformIsAffine() const;
    bool isAlmostZero(float a) const;
    bool useHalfSteps() const;
    int analyzeLink();
    bool triviallyAccepted();
    bool dilatedTrivialCulling(int link_type);
    bool trivialCulling(int link_type);
    vec3 transformOffsetControlPointToClipSpace(int ndx, vec2 offset, float scale);
    void discardPatch();
    void passVectorCoefficients(vec2 A, vec2 B, vec2 C);
#if !AFFINE
    void computeRationalQuadraticVectorCoefficients();
#endif
    void computeConicVectorCoefficients(float k);
    void computeParabolicVectorCoefficients(vec2 delta01alt, vec2 delta23alt);
    bool polarQuadraticStroking();
    bool polarAffineParabolicStroking();
    bool polarRationalQuadraticStroking();
    vec2 findInflectionPoints(vec2 delta01, vec2 delta12, INOUTPARAM(bool) is_loop);
    float angleDifference(float a, float b, float c, bool is_loop);
    bool polarCubicStroking(int link_type);
    float miterHandling(int link_type, float clamped_steps);
    //// Control helper functions to "fake" outputting a patch
    void emitPatch(int W, int H);
    ivec2 getPatchWidthHeight(int strips, int steps_per_strip);
    void outputGridPatch(ivec2 WH);
    void writeLinkOffsetBuffer(uint offset, uint steps);
    void outputArcLengthState(uint steps);
    void establishSteps(float steps);
    ivec2 computeOrderedBlendingGrid(int clamped_steps);
    ivec2 computeUnorderedBlendingGrid(float clamped_steps);
    void outputLinkPatch(float clamped_steps);
    void discardLinkPatch();

    // Evaluation helper functions
    void adjustOffsetForMiter(uint i, INOUTPARAM(vec2) effective_offset) const;
    CPtype evalCurvePosition(float t);
    CPtype evalQuadraticBezierPosition(float t) const;
    CPtype evalCubicBezierPosition(float t) const;
    ParametricDirection evalCurveSampleInRange(float theta, float t_min, float t_max) const;
    ParametricDirection evalCurveSample(uint ndx, float delta_theta) const;
    int thetaToIndex(float theta_s) const;

    float evalGradientCoordinate(CPOtype p, vec3 coeffs) const;

    float indexedRibToDeltaThetaWithHalfSteps(uint ndx, uint i) const;
    float indexedRibToUniformSpacedDeltaTheta(uint ndx, uint i) const;
    float indexedRibToDeltaTheta(uint ndx, uint i) const;

    float indexToFractionalIndex(uint i, uint steps) const;
    float scaled_Theta_to_scaled_theta(int size, float scaled_Theta) const;
    ParametricDirection evalTransformedRibIndex(uint i) const;

    ParametricDirection evalDeltaStepRibIndex(uint ndx) const;
    ParametricAngle evalTangentChangeMapRibIndex(uint i) const;
    ParametricDirection evalConformalRibIndex(uint i) const;

    // Stash results in StrokingResults registered with setStrokingResults.
    void stashOffset(uint i, vec2 offset);
    void stashNormal(uint i, vec2 normal);
    void stashTheta(uint i, float theta);
    void stashParametricT(uint i, float t);

    float biggerDistance(CPtype Pa, vec2 Na, CPtype Pb, vec2 Nb, float scale);
    float ribSeparation(uint prior_rib_index, float t, CPtype p, vec2 normal);
    uint linkOffsetIndex(uint primitive_id) const;
    void writeSegmentArcLength(uint rib_index, float segment_arc_length);
    bool reverseScanLink(uint from_segment_index, uint to_segment_ndx, INOUTPARAM(float) total_dist, INOUTPARAM(uint) add_ops);
    float accumulateAccmulatedArcLength(uint rib_index);
    float processArcLength(uint rib_index, float t, CPtype p, vec2 normal);
    void writeSegmentInfo(uint rib_index, float t, CPtype p, vec2 normal, float texture_t);

public:  // EqualGradientDirectionDeltaCubicSplitter uses these interfaces.
    ParametricDirection evalRibIndex(uint i) const;
    float2 startDirection() const;
    float2 endDirection() const;

private:
    float3 evalPosition(float t) const;
    ThetaPosition makeThetaPosition(float theta, CPtype position) const;
    ThetaPosition evalTangentChangeMapRib(uint i) const;
    // Structure for evalRib to accept; GPU version also has row_mod3 for poison patch mode.
    struct RibIndexResult {
        uint i;
        RibIndexResult(uint v)
            : i(v)
        {}
    };
#if AFFINE
    // GPU uses this simpler version; CPU doesn't actually.
    vec2 evalSegmentPosition(ParametricDirection pd);
#else
    vec3 evalSegmentPosition(ParametricDirection pd);
#endif
    void evalRib(RibIndexResult rib);
    void evalRib(uint i);

    float3 adjustEdge(const float3 Pedge, const float3 Pmid, const float3 p, const float2 effective_offset, float stroke_radius) const;

    // Helpers to setupLink
    float linkControlProcess(int link_type);
    float linkControlClipProcess(int link_type);
    void linkControlShader();

    void verifyIncreasingT(StrokingResults& results) const;

    // Used by setupLink
    void setupLinkControlPoints(const float3 vin[6], const GLuint ndx[6]);

public:
    void setStrokeSpace(StrokeSpaceEnum ss);
    void setTransforms(const float3x3& mv, const float3x3& p, const float3x3& mvp, const float2& ws);
    void setIdentityTransforms();
    bool invalidTransforms();
    void setupLink(const float3 v[6], const GLuint ndx[6]);

    CPUStrokeTessellator(const StrokeTessellatorSettings &init);
    CPUStrokeTessellator(const StrokeTessellatorSettings &init, StrokeConfigTypes::ShadingMode shading_mode, PathDrawState& state);
    CPUStrokeTessellator(const StrokeTessellatorSettings &init, StrokeConfigTypes::ShadingMode shading_mode, PathDrawState& state, float stroke_width, float arc_length_extension, float max_turning_angle_delta, int max_join_steps, float effective_miter_limit, unsigned int cap_placement_to_type);

    void setStrokingResults(StrokingResults*);

    void evalRibs(StrokingResults& results);

    float Tbound(int i) const {
        return tbounds[i];
    }
    StrokeSpaceEnum StrokeSpace() const {
        return stroke_space;
    }
    float2 ViewportScale() const {
        return viewport_scale.xy;
    }
    float3x3 ModelviewProjectionMatrix() const {
        return modelview_projection;
    }
    float3x3 ModelViewMatrix() const {
        return modelview;
    }
    const float2& GradCp(int i) const {
        assert(i < 3);
        assert(i >= 0);
        return grad_cp[i];
    }
    void setSteps(uint steps);

    // Control-Evaluation interface methods.
    uint Steps() const;
    uint OrientationBitMask() const;

    bool IsQuadratic() const;
    bool IsJoinOrCap() const;
    float GetD0AB1() const {
        return stashed_D0AB1;
    }
    float2 A() const {
        return float2(A_C[0], A_C[2]);
    }
    float2 B() const {
        return float2(B_bogus[0], B_bogus[1]);
    }
    float2 C() const {
        return float2(A_C[1], A_C[3]);
    }
    float3 Cp(uint ndx) const {
        return cp[ndx];
    }
    float3x3 ObjectToWindowSpaceMatrix() const {
        return object_to_window_space;
    }
    float3x3 WindowToObjectSpaceMatrix() const {
        return inverse_object_to_window_space;
    }
    int LinkType() const {
        return stashed_link_type;
    }
    bool LinkTypeIsCurved(int link_type) const;
    bool LinkTypeIsCurved() const;
    float StrokeRadius() const {
        return stroke_radius;
    }
    bool LinkTypeIsQuadratic() const;
    void GetQuadraticControlPoints(float3 cps[3]) const;
    void GetCubicControlPoints(float3 cps[4]) const;
    void GetCubicControlPoints(double3 cps[4]) const;

    void print(FILE* fp) const;

    typedef void (*TessellateOffsetFunc)(int rib_index, const float2 p[2], float t, void* handle);
    typedef void (*TessellatePositionFunc)(int rib_index, const float2& p, float t, void* handle);

private:
    bool setupGradientControlPoints(float3 link_control_points[], GLuint ndx[]);
    bool completeLinkSetup(int link_type, float3 link_control_points[], GLuint ndx[]);
protected:
    bool setupCubic(const float2 cp_orig[4]);
private:
    bool setupQuadratic(const float2 cp_orig[3]);
    bool setupConic(const float2 cp_orig[3], float interp_w);
    void tessellateRibOffsets(TessellateOffsetFunc func, void* handle);
    void tessellateRibPosition(TessellatePositionFunc func, void* handle);
    void tessellateRibRationalPosition(TessellatePositionFunc func, void* handle);

public:
    bool tessellateCubicOffsets(TessellateOffsetFunc func, void* handle, const float2 cp_orig[4]);
    bool tessellateQuadraticOffsets(TessellateOffsetFunc func, void* handle, const float2 cp_orig[3]);
    bool tessellateConicOffsets(TessellateOffsetFunc func, void* handle, const float2 cp_orig[3], float interp_w);

    bool tessellateCubicPosition(TessellatePositionFunc func, void* handle, const float2 cp_orig[4]);
    bool tessellateQuadraticPosition(TessellatePositionFunc func, void* handle, const float2 cp_orig[3]);
    bool tessellateConicPosition(TessellatePositionFunc func, void* handle, const float2 cp_orig[3], float interp_w);
};

#endif // __CPUStrokeTessellator_hpp__
