convergent-curve-ordering.cpp

#include "convergent-curve-ordering.h"

#include "arithmetics.hpp"
#include "Vector2.hpp"

/*
 * For non-degenerate curves A(t), B(t) (ones where all control points are distinct) both originating at P = A(0) = B(0) = *corner,
 * we are computing the limit of
 *
 *     sign(crossProduct( A(t / |A'(0)|) - P, B(t / |B'(0)|) - P ))
 *
 * for t -> 0 from 1. Of note is that the curves' parameter has to be normed by the first derivative at P,
 * which ensures that the limit approaches P at the same rate along both curves - omitting this was the main error of earlier versions of deconverge.
 *
 * For degenerate cubic curves (ones where the first control point equals the origin point), the denominator |A'(0)| is zero,
 * so to address that, we approach with the square root of t and use the derivative of A(sqrt(t)), which at t = 0 equals A''(0)/2
 * Therefore, in these cases, we replace one factor of the cross product with A(sqrt(2*t / |A''(0)|)) - P
 *
 * The cross product results in a polynomial (in respect to t or t^2 in the degenerate case),
 * the limit of sign of which at zero can be determined by the lowest order non-zero derivative,
 * which equals to the sign of the first non-zero polynomial coefficient in the order of increasing exponents.
 *
 * The polynomial's constant and linear terms are zero, so the first derivative is definitely zero as well.
 * The second derivative is assumed to be zero (or near zero) due to the curves being convergent - this is an input requirement
 * (otherwise the correct result is the sign of the cross product of their directions at t = 0).
 * Therefore, we skip the first and second derivatives.
 */

namespace msdfgen {

static void simplifyDegenerateCurve(Point2 *controlPoints, int &order) {
    if (order == 3 && (controlPoints[1] == controlPoints[0] || controlPoints[1] == controlPoints[3]) && (controlPoints[2] == controlPoints[0] || controlPoints[2] == controlPoints[3])) {
        controlPoints[1] = controlPoints[3];
        order = 1;
    }
    if (order == 2 && (controlPoints[1] == controlPoints[0] || controlPoints[1] == controlPoints[2])) {
        controlPoints[1] = controlPoints[2];
        order = 1;
    }
    if (order == 1 && controlPoints[0] == controlPoints[1])
        order = 0;
}

int convergentCurveOrdering(const Point2 *corner, int controlPointsBefore, int controlPointsAfter) {
    if (!(controlPointsBefore > 0 && controlPointsAfter > 0))
        return 0;
    Vector2 a1, a2, a3, b1, b2, b3;
    a1 = *(corner-1)-*corner;
    b1 = *(corner+1)-*corner;
    if (controlPointsBefore >= 2)
        a2 = *(corner-2)-*(corner-1)-a1;
    if (controlPointsAfter >= 2)
        b2 = *(corner+2)-*(corner+1)-b1;
    if (controlPointsBefore >= 3) {
        a3 = *(corner-3)-*(corner-2)-(*(corner-2)-*(corner-1))-a2;
        a2 *= 3;
    }
    if (controlPointsAfter >= 3) {
        b3 = *(corner+3)-*(corner+2)-(*(corner+2)-*(corner+1))-b2;
        b2 *= 3;
    }
    a1 *= controlPointsBefore;
    b1 *= controlPointsAfter;
    // Non-degenerate case
    if (a1 && b1) {
        double as = a1.length();
        double bs = b1.length();
        // Third derivative
        if (double d = as*crossProduct(a1, b2) + bs*crossProduct(a2, b1))
            return sign(d);
        // Fourth derivative
        if (double d = as*as*crossProduct(a1, b3) + as*bs*crossProduct(a2, b2) + bs*bs*crossProduct(a3, b1))
            return sign(d);
        // Fifth derivative
        if (double d = as*crossProduct(a2, b3) + bs*crossProduct(a3, b2))
            return sign(d);
        // Sixth derivative
        return sign(crossProduct(a3, b3));
    }
    // Degenerate curve after corner (control point after corner equals corner)
    int s = 1;
    if (a1) { // !b1
        // Swap aN <-> bN and handle in if (b1)
        b1 = a1;
        a1 = b2, b2 = a2, a2 = a1;
        a1 = b3, b3 = a3, a3 = a1;
        s = -1; // make sure to also flip output
    }
    // Degenerate curve before corner (control point before corner equals corner)
    if (b1) { // !a1
        // Two-and-a-half-th derivative
        if (double d = crossProduct(a3, b1))
            return s*sign(d);
        // Third derivative
        if (double d = crossProduct(a2, b2))
            return s*sign(d);
        // Three-and-a-half-th derivative
        if (double d = crossProduct(a3, b2))
            return s*sign(d);
        // Fourth derivative
        if (double d = crossProduct(a2, b3))
            return s*sign(d);
        // Four-and-a-half-th derivative
        return s*sign(crossProduct(a3, b3));
    }
    // Degenerate curves on both sides of the corner (control point before and after corner equals corner)
    { // !a1 && !b1
        // Two-and-a-half-th derivative
        if (double d = sqrt(a2.length())*crossProduct(a2, b3) + sqrt(b2.length())*crossProduct(a3, b2))
            return sign(d);
        // Third derivative
        return sign(crossProduct(a3, b3));
    }
}

int convergentCurveOrdering(const EdgeSegment *a, const EdgeSegment *b) {
    Point2 controlPoints[12];
    Point2 *corner = controlPoints+4;
    Point2 *aCpTmp = controlPoints+8;
    int aOrder = int(a->type());
    int bOrder = int(b->type());
    if (!(aOrder >= 1 && aOrder <= 3 && bOrder >= 1 && bOrder <= 3)) {
        // Not implemented - only linear, quadratic, and cubic curves supported
        return 0;
    }
    for (int i = 0; i <= aOrder; ++i)
        aCpTmp[i] = a->controlPoints()[i];
    for (int i = 0; i <= bOrder; ++i)
        corner[i] = b->controlPoints()[i];
    if (aCpTmp[aOrder] != *corner)
        return 0;
    simplifyDegenerateCurve(aCpTmp, aOrder);
    simplifyDegenerateCurve(corner, bOrder);
    for (int i = 0; i < aOrder; ++i)
        corner[i-aOrder] = aCpTmp[i];
    return convergentCurveOrdering(corner, aOrder, bOrder);
}

}