
// CommonStrokeTessellatorArcLength.hpp - arc length evaluation for polar stroking

#ifndef __CommonStrokeTessellatorArcLength_hpp__
#define __CommonStrokeTessellatorArcLength_hpp__

#include "CommonStrokeTessellatorPrivate.hpp"
#include "CommonStrokeTessellatorMath.hpp"

#include <Cg/distance.hpp>
#include <Cg/dot.hpp>

#ifndef ARC_LENGTH_TEXGEN
@ expect ARC_LENGTH_TEXGEN to be defined
#endif

#define COUNT_ADD_OPS 1

STATIC float sqdist(const vec2 a, const vec2 b)
{
    const vec2 d = a-b;
    return dot(d,d);
}

float StrokeTessellatorMETHOD biggerDistance(CPtype Pa, vec2 Na,
                                             CPtype Pb, vec2 Nb,
                                             float scale)
{
    assert(dot(Na, Nb) > 0);

#if AFFINE
    CONST vec2 Pa_neg = Pa.xy - scale*Na;
    CONST vec2 Pb_neg = Pb.xy - scale*Nb;

    CONST vec2 Pa_pos = Pa.xy + scale*Na;
    CONST vec2 Pb_pos = Pb.xy + scale*Nb;
#else
    CONST vec2 Pa_neg = (Pa.xy - scale*Na*Pa.z)/Pa.z;
    CONST vec2 Pb_neg = (Pb.xy - scale*Nb*Pb.z)/Pb.z;

    CONST vec2 Pa_pos = (Pa.xy + scale*Na*Pa.z)/Pa.z;
    CONST vec2 Pb_pos = (Pb.xy + scale*Nb*Pb.z)/Pb.z;
#endif

    CONST float sq_dist1 = sqdist(Pa_neg, Pb_neg);
    CONST float sq_dist2 = sqdist(Pa_pos, Pb_pos);

    if (sq_dist1 > sq_dist2) {
        return sqrt(sq_dist1);
    } else {
        return sqrt(sq_dist2); 
    }
}

float StrokeTessellatorMETHOD ribSeparation(uint prior_rib_index, float t, CPtype p, vec2 normal)
{
    CONST ParametricDirection prior_pd = evalRibIndex(prior_rib_index);
    CONST float prior_t = prior_pd.t;
    // Guard against the prior_t being slightly larger than this rib's t.
    if (prior_t <= t) {
        CONST CPtype prior_p = evalSegmentPosition(prior_pd);
        // Compute the Euclidean distance from this rib to the prior rib.
        // We assume this length is very close to the true (possible curved)
        // arc length of the curve between the ribs because the turning
        // angle is small.
        // XXX this has a bias that consistently under-estimates the true arc length.
        vec2 prior_normal = prior_pd.normal;
#if !AFFINE
        if (p.z <= 0 || prior_p.z <= 0) {
            // negative W means this spine would be discarded by the rasterizer.
            return 0;
        }
#endif
        return biggerDistance(p, normal, prior_p, prior_normal, stroke_radius_fraction);
    } else {
        // If the prior_t is larger, just return zero for the distance.
        assert(prior_t - t < 0.001);    // Assert the difference is small.
        return 0;
    }
}

#define BUFMASK (524288-1)  // XXX put me someplace better
void StrokeTessellatorMETHOD writeSegmentArcLength(uint rib_index, float segment_arc_length)
{
    CONST uint link_offset_ndx = linkOffsetIndex(primitiveID_x_x_x[0]);
    CONST uint offset = link_offset[link_offset_ndx+0];
    // Write segment as negative value to indicate it is not accumulated
    // with all the prior segment arc lengths (yet).
    segment_distance[(offset+rib_index-1) & BUFMASK] = -segment_arc_length;
}

bool StrokeTessellatorMETHOD reverseScanLink(uint from_segment_index, uint to_segment_ndx,
                                            INOUTPARAM(float) total_dist, INOUTPARAM(uint) add_ops)
{
    // For this link, loop backwards from from_segment_index until to_segment_ndx...
    for (uint j=from_segment_index, segment_ndx; j!=to_segment_ndx; j = segment_ndx) {
        add_ops++;
        // Be careful to wrap j modulo the segment distance buffer size when decrementing j
        // to determine the segment distance index.
        segment_ndx = (j-1)&BUFMASK;
        // Read the (possibly negated) distance from 
        CONST float dist = segment_distance[segment_ndx];
        CONST int raw_dist = floatBitsToInt(dist);
        if (raw_dist < 0) {
            total_dist += -dist;
        } else {
            total_dist += dist;
            return true;  // Found an already accumulated distance so now done.
        }
    }
    // Failed to find an accumulated distance so keep accumulating prior links.
    return false;
}

float StrokeTessellatorMETHOD accumulateAccmulatedArcLength(uint rib_index)
{
    // Second pass accumulates the arc distance from prior segments by
    // scanning backward.  When a negative distance is encountered, the
    // absolute value of that distance is accumulated and the reverse
    // scanning continues.  When all prior segments are exhausted OR
    // a non-negative distance is encountered, the process stops.
    // If there's a non-negative distance, it too is accumulated to
    // obtain a cummulative arc length for this and all prior segments.
    // Finally, this accumulated arc length is written to
    // the segment's slot as a positive value.  The idea here is prior
    // threads may have already provide an incremental cummulative arc
    // length so use that.
    uint this_link_ndx = primitiveID_x_x_x[0];
    CONST uint this_link_offset_ndx = linkOffsetIndex(this_link_ndx);
    CONST uint this_start_segment_ndx = link_offset[this_link_offset_ndx+0];
    CONST uint this_rib_ndx = (this_start_segment_ndx + rib_index) & BUFMASK;

    float total_dist = 0;
    uint add_ops = 0;

    // First scan backward from this rib's current link...
    if (reverseScanLink(this_rib_ndx, this_start_segment_ndx, total_dist, add_ops)) {
        // Now have a fully accumulated distance so no further looking needed for prior links.
    } else {
        // Still don't have a fully accumulated distance so
        // loop backwards to through the prior links...
        for (uint i=this_link_ndx, link_ndx; i > 0; i = link_ndx) {
            // Map the link's index to its [start,end) segment distance range.
            link_ndx = i-1;
            CONST uint link_offset_ndx = linkOffsetIndex(link_ndx);
            CONST uint start_segment_ndx = link_offset[link_offset_ndx+0];
            CONST uint end_segment_ndx   = link_offset[link_offset_ndx+1];

            // Scan backward through segments of this link...
            if (reverseScanLink(end_segment_ndx, start_segment_ndx, total_dist, add_ops)) {
                // Now have a fully accumulated distance so no further looking needed for prior links.
                break;
            }
        }
    }
    // By this point we have a fully accumulated total distance either because we
    // 1) scanned all the links to the very beginning of the path (hopefully rare beyond the early ribs), or
    // 2) we encountered an accumulated distance allowing us to accumulate it and stop early.

    // Here we write the accumulated arc length back to our segment's slot.
    if (rib_index > 0) {
        CONST uint segment_to_update_ndx = (this_rib_ndx-1) & BUFMASK;
        segment_distance[segment_to_update_ndx] = total_dist;
#if COUNT_ADD_OPS
        segment_add_ops[segment_to_update_ndx] = add_ops;
#endif
    }
    return total_dist;
}

// Returns zero, except when pass_number==1 when cummulative arc length is returned.
float StrokeTessellatorMETHOD processArcLength(uint rib_index, float t, CPtype p, vec2 normal)
{
    // Is CPU configured to gather arc length?
    if (link_offset == NULL) {
        // No, just return.
        assert(pass_number == 0);
        return 0;
    }
    if (pass_number == 0) {
        if (rib_index > 0) {
            // Write this segment's arc length on first pass (also the "stencil" step).
            CONST float segment_arc_length = ribSeparation(rib_index-1, t, p, normal);
            writeSegmentArcLength(rib_index, segment_arc_length);
        }
    } else if (pass_number == 1) {
        return accumulateAccmulatedArcLength(rib_index);
    }
    return 0;
}

#endif // __CommonStrokeTessellatorArcLength_hpp__
