import "includes/structs";

struct Varyings {
    float4 positionCS : SV_Position;
    nointerpolation uint instance;
    float2 texCoordEM : U_TEXCOORD;
}

struct GuiText {
    float4 color;
    // Index into _GlyphData
    uint glyph;
    float2 bottomLeftSSPX;
    float fontSizePX;
}

struct GlyphData {
    float2 bottomLeftEM;
    float2 sizeEM;
    // Index into _BandData of the first vertical/horizontal band data.
    // `bandPtr.x` refers to vertical bands and `bandPtr.y` refers to horizontal
    // bands.
    uint2 bandPtr;
    // Number of vertical/horizontal bands. `bandCount.x` is the number of
    // vertical bands and `bandCount.y` is the number of horizontal bands.
    uint2 bandCount;
}

[[vk::binding(0, 0)]] ConstantBuffer<GlobalUniforms> _Global;
[[vk::binding(1, 0)]] StructuredBuffer<GuiText> _Instances;

[[vk::binding(0, 1)]] StructuredBuffer<GlyphData> _GlyphData;
[[vk::binding(1, 1)]] StructuredBuffer<half2> _ControlPoints;
[[vk::binding(2, 1)]] StructuredBuffer<uint> _BandData;

static const float2 VERTICES[4] = {
    float2(0, 1),
    float2(1, 1),
    float2(0, 0),
    float2(1, 0),
};

// Classify a quadratic Bézier curve based on the sign bits of the ray-relative
// Y coordinates. Returns `(t2 << 1) | t1` where `t1` and `t2` are bits
// signifying the root eligibility; `t1` possibly adding one to the winding
// number and `t2` possibly subtracting one from the winding number.
uint classifyQuadCurve(float y0, float y1, float y2)
{
    // ┌─────┰────┬────┬────┰────┬────┐
    // │class┃ y2 │ y1 │ y0 ┃ t2 │ t1 │
    // ├─────╂────┼────┼────╂────┼────┤
    // │  A  ┃  0 │  0 │  0 ┃  0 │  0 │
    // │  B  ┃  0 │  0 │  1 ┃  1 │  0 │
    // │  C  ┃  0 │  1 │  0 ┃  1 │  1 │
    // │  D  ┃  0 │  1 │  1 ┃  1 │  0 │
    // │  E  ┃  1 │  0 │  0 ┃  0 │  1 │
    // │  F  ┃  1 │  0 │  1 ┃  1 │  1 │
    // │  G  ┃  1 │  1 │  0 ┃  0 │  1 │
    // │  H  ┃  1 │  1 │  1 ┃  0 │  0 │
    // └─────┸────┴────┴────┸────┴────┘
    //
    // Lookup table constant:
    //  H  G  F  E  D  C  B  A
    // 00 01 11 01 10 11 10 00 = 0x1DB8

    let sign0 = asuint(y0) >> 31;
    let sign1 = asuint(y1) >> 31;
    let sign2 = asuint(y2) >> 31;

    let class = (sign0 << 0) | (sign1 << 1) | (sign2 << 2);
    let shift = 2 * class;

    return (0x2E74U >> shift) & 0b11U;
}

// Find intersections between a quadratic Bézier curve and `y = 0` line by
// solving a quadratic equation.
//
// Returns the X coordinates at witch the intersections occur for roots t1 and
// t2. Imaginary solutions to the quadratic equation will return double root at
// the global minimum.
float2 raycastQuadCurveHorizontally(float2 cp0, float2 cp1, float2 cp2)
{
    static const float EPSILON = 1.0 / 65536.0;

    // When solving for y = 0, we get a quadratic polynomial given by:
    //
    // at² - 2bt + c
    //
    // where:
    // * a = cp0.y - 2 * cp1.y + cp2.y
    // * b = cp0.y - cp1.y
    // * c = cp0.y
    //
    // Let Δ = b² - ac
    // Then:
    //
    // t1 = (b - sqrt(Δ)) / a
    // t2 = (b + sqrt(Δ)) / a

    let a = cp0 - 2.0 * cp1 + cp2;
    let b = cp0 - cp1;
    let c = cp0;

    let Δ = sqrt(max(b.y * b.y - a.y * c.y, 0.0));
    var t = (b.y + float2(-Δ, Δ)) / a.y;

    // If nearly linear, solve -2bt + c = 0 directly
    if (abs(a.y) < EPSILON) {
        t = float2(0.5 * c.y / b.y);
    }

    return (a.x * t - 2.0 * b.x) * t + c.x;
}

// Find intersections between a quadratic Bézier curve and `x = 0` line by
// solving a quadratic equation.
//
// Returns the Y coordinates at witch the intersections occur for roots t1 and
// t2. Imaginary solutions to the quadratic equation will return double root at
// the global minimum.
float2 raycastQuadCurveVertically(float2 cp0, float2 cp1, float2 cp2)
{
    static const float EPSILON = 1.0 / 65536.0;

    let a = cp0 - 2.0 * cp1 + cp2;
    let b = cp0 - cp1;
    let c = cp0;

    let Δ = sqrt(max(b.x * b.x - a.x * c.x, 0.0));
    var t = (b.x + float2(-Δ, Δ)) / a.x;

    if (abs(a.x) < EPSILON) {
        t = float2(0.5 * c.x / b.x);
    }

    return (a.y * t - 2.0 * b.y) * t + c.y;
}

float calculateCoverage(float xCoverage, float yCoverage, float xWeight, float yWeight) {
    static const float EPSILON = 1.0 / 65536.0;

    var coverage = max(
        abs(xCoverage * xWeight + yCoverage * yWeight) / max(xWeight + yWeight, EPSILON),
        min(abs(xCoverage), abs(yCoverage)),
    );
    // non-zero fill rule
    coverage = saturate(coverage);

    return coverage;
}

[shader("vertex")]
Varyings vertexMain(uint vertexID : SV_VulkanVertexID, uint instanceID : SV_VulkanInstanceID) {
    Varyings out;

    let vertex = VERTICES[vertexID];
    let instance = _Instances[instanceID];
    let glyph = _GlyphData[instance.glyph];
    let normal = 2.0 * vertex - 1.0;

    let sizePX = instance.fontSizePX * glyph.sizeEM;

    let positionSSPX = vertex * sizePX + instance.bottomLeftSSPX;
    let dilatedPositionSSPX = positionSSPX + 0.5 * normal;
    let dilatedPositionCS = float4(mul(_Global.matrixSSPXtoCS, float3(positionSSPX, 1.0)), 0.0, 1.0);

    let texCoordEM = vertex * glyph.sizeEM + glyph.bottomLeftEM;
    let dilatedTexCoordEM = texCoordEM + (0.5 / instance.fontSizePX) * normal;

    out.positionCS = dilatedPositionCS;
    out.instance = instanceID;
    out.texCoordEM = dilatedTexCoordEM;
    return out;
}

[shader("fragment")]
float4 fragmentMain(Varyings frag) : SV_Target {
    let instance = _Instances[frag.instance];
    let glyph = _GlyphData[instance.glyph];

    let emPerPX = fwidth(frag.texCoordEM);
    let pxPerEM = 1.0 / emPerPX;

    let bandF = float2(glyph.bandCount) * (frag.texCoordEM - glyph.bottomLeftEM) / glyph.sizeEM;
    let band = uint2(clamp(bandF, float2(0, 0), float2(glyph.bandCount - 1U)));

    // --- HORIZONTAL BAND -----------------------------------------------------

    var xCoverage = 0.0;
    var xWeight = 0.0;

    let horizontalBandPtr = glyph.bandPtr.y + band.y;
    let horizontalBandData = _BandData[horizontalBandPtr];
    let horizontalBandCurvePtr = horizontalBandPtr + (horizontalBandData >> 16);
    let horizontalBandCurveCount = horizontalBandData & 0xFFFF;

    for (uint horizontalBandCurveID = 0; horizontalBandCurveID < horizontalBandCurveCount; horizontalBandCurveID++) {
        let cpPtr = _BandData[horizontalBandCurvePtr + horizontalBandCurveID];
        let cp0 = float2(_ControlPoints[cpPtr]) - frag.texCoordEM;
        let cp1 = float2(_ControlPoints[cpPtr + 1]) - frag.texCoordEM;
        let cp2 = float2(_ControlPoints[cpPtr + 2]) - frag.texCoordEM;

        if (max(max(cp0.x, cp1.x), cp2.x) * pxPerEM.x < -0.5) break;

        let rootFlags = classifyQuadCurve(cp0.y, cp1.y, cp2.y);
        if (rootFlags != 0U) {

            let result = raycastQuadCurveHorizontally(cp0, cp1, cp2) * pxPerEM.x;

            // consider t1 at X position result.x
            if ((rootFlags & 0b01U) != 0U) {
                xCoverage += saturate(result.x + 0.5);
                xWeight = max(xWeight, saturate(1.0 - abs(result.x) * 2.0));
            }

            // consider t2 at X position result.y
            if ((rootFlags & 0b10U) != 0U) {
                xCoverage -= saturate(result.y + 0.5);
                xWeight = max(xWeight, saturate(1.0 - abs(result.y) * 2.0));
            }
        }
    }

    // --- VERTICAL BAND -------------------------------------------------------

    var yCoverage = 0.0;
    var yWeight = 0.0;

    let verticalBandPtr = glyph.bandPtr.x + band.x;
    let verticalBandData = _BandData[verticalBandPtr];
    let verticalBandCurvePtr = verticalBandPtr + (verticalBandData >> 16);
    let verticalBandCurveCount = verticalBandData & 0xFFFF;

    for (uint verticalBandCurveID = 0; verticalBandCurveID < verticalBandCurveCount; verticalBandCurveID++) {
        let cpPtr = _BandData[verticalBandCurvePtr + verticalBandCurveID];
        let cp0 = float2(_ControlPoints[cpPtr]) - frag.texCoordEM;
        let cp1 = float2(_ControlPoints[cpPtr + 1]) - frag.texCoordEM;
        let cp2 = float2(_ControlPoints[cpPtr + 2]) - frag.texCoordEM;

        if (max(max(cp0.y, cp1.y), cp2.y) * pxPerEM.y < -0.5) break;

        let rootFlags = classifyQuadCurve(cp0.x, cp1.x, cp2.x);
        if (rootFlags != 0U) {

            let result = raycastQuadCurveVertically(cp0, cp1, cp2) * pxPerEM.y;

            // consider t1 at Y position result.x
            if ((rootFlags & 0b01U) != 0U)
            {
                yCoverage -= saturate(result.x + 0.5);
                yWeight = max(yWeight, saturate(1.0 - abs(result.x) * 2.0));
            }

            // consider t2 at Y position result.y
            if ((rootFlags & 0b10U) != 0U)
            {
                yCoverage += saturate(result.y + 0.5);
                yWeight = max(yWeight, saturate(1.0 - abs(result.y) * 2.0));
            }
        }
    }

    // --- RESOLVE -------------------------------------------------------------

    let coverage = calculateCoverage(xCoverage, yCoverage, xWeight, yWeight) * instance.color.a;
    return float4(
        coverage * instance.color.rgb,
        coverage,
    );
}