GeometryUtils.hlsl

// Given a triangle edge defined by 2 verts, calculate 2 new verts that define the same edge,
// pushed outwards enough to cover centroids of any pixels which may intersect the triangle.
void OffsetEdge(float2 v1, float2 v2, float2 pixelSize, out float2 v1Offset, out float2 v2Offset)
{
    // Find the normal of the edge
    float2 edge = v2 - v1;
    float2 normal = normalize(float2(-edge.y, edge.x));

    // Find the amount to offset by. This is the semidiagonal of the pixel box in the same quadrant as the normal.
    float2 semidiagonal = pixelSize / sqrt(2.0);
    semidiagonal *= float2(normal.x > 0 ? 1 : -1, normal.y > 0 ? 1 : -1);

    // Offset the edge
    v1Offset = v1 + semidiagonal;
    v2Offset = v2 + semidiagonal;
}

// Given 2 lines defined by 2 points each, find the intersection point.
float2 LineIntersect(float2 p1, float2 p2, float2 p3, float2 p4, float eps = 0.0f)
{
    // Line p1p2 represented as a1x + b1y = c1
    float a1 = p2.y - p1.y;
    float b1 = p1.x - p2.x;
    float c1 = a1 * p1.x + b1 * p1.y;

    // Line p3p4 represented as a2x + b2y = c2
    float a2 = p4.y - p3.y;
    float b2 = p3.x - p4.x;
    float c2 = a2 * p3.x + b2 * p3.y;

    float determinant = a1 * b2 - a2 * b1;
    if (abs(determinant) <= eps) // Parallel lines - return any valid point.
        return p1;

    float x = b2 * c1 - b1 * c2;
    float y = a1 * c2 - a2 * c1;
    return float2(x, y) / determinant;
}

// Check which side the point p is on, relative to the line cp1-cp2.
// Optionally with an epsilon value within which points are considered outside.
bool IsInside(float2 p, float2 cp1, float2 cp2, float eps = 0.0f)
{
    return (cp2.x - cp1.x) * (p.y - cp1.y) - (cp2.y - cp1.y) * (p.x - cp1.x) >= eps;
}

// Clip a polygon with a line defined by two points, in place.
// https://en.wikipedia.org/wiki/Sutherland-Hodgman_algorithm
void ClipPolygonWithLine(inout float2 polygon[6], inout uint polygonLength, float2 cp1, float2 cp2, float inside_eps = 0.0f, float parallel_eps = 0.0f)
{
    float2 result[6];
    uint resultLength = 0;

    for (uint i = 0; i < polygonLength; i++)
    {
        float2 s = polygon[i];
        float2 e = polygon[(i + 1) % polygonLength];

        if (IsInside(e, cp1, cp2, inside_eps)) // At least one endpoint is inside
        {
            if (!IsInside(s, cp1, cp2, inside_eps)) // Only the end point is inside, add the intersection
            {
                result[resultLength] = LineIntersect(cp1, cp2, s, e, parallel_eps);
                resultLength++;
            }
            result[resultLength] = e;
            resultLength++;
        }
        else if (IsInside(s, cp1, cp2, inside_eps)) // Only the start point is inside, add the intersection
        {
            result[resultLength] = LineIntersect(cp1, cp2, s, e, parallel_eps);
            resultLength++;
        }
    }

    polygonLength = resultLength;
    for (uint p = 0; p < polygonLength; p++)
        polygon[p] = result[p];
}

// Clip a polygon to the bounding box of a texel at the given position
bool ClipPolygonWithTexel(float2 texelPosition, inout float2 polygon[6], inout uint polygonLength, float inside_eps = 0.0f, float parallel_eps = 0.0f)
{
    // Get the bounding box of the texel to clip with.
    float2 clipPolygon[4] =
    {
        texelPosition + float2(-0.5, -0.5),
        texelPosition + float2(0.5, -0.5),
        texelPosition + float2(0.5, 0.5),
        texelPosition + float2(-0.5, 0.5),
    };

    // Clip to each edge of the quad
    for (uint edge = 0; edge < 4; edge++)
    {
        ClipPolygonWithLine(polygon, polygonLength, clipPolygon[edge], clipPolygon[(edge + 1) % 4], inside_eps, parallel_eps);
    }

    return polygonLength > 0;
}

// Read the parent triangle of a vertex from a vertex buffer, and transform it to the desired space.
void ReadParentTriangle(StructuredBuffer<float2> vertexBuffer, uint vertexId, float4 scaleAndOffset, out float2 tri[3])
{
    uint triId = vertexId / 3;
    uint baseVertexId = triId * 3;
    tri[0] = vertexBuffer[baseVertexId + 0].xy * scaleAndOffset.xy + scaleAndOffset.zw;
    tri[1] = vertexBuffer[baseVertexId + 1].xy * scaleAndOffset.xy + scaleAndOffset.zw;
    tri[2] = vertexBuffer[baseVertexId + 2].xy * scaleAndOffset.xy + scaleAndOffset.zw;

    // Flip the winding order if it doesn't follow Unity's convention
    float2 edgeAB = tri[1] - tri[0];
    float2 edgeAC = tri[2] - tri[0];
    bool flipWinding = ((edgeAB.x * edgeAC.y) - (edgeAB.y * edgeAC.x)) > 0;

    if (flipWinding)
    {
        float2 temp = tri[1];
        tri[1] = tri[2];
        tri[2] = temp;
    }
}

// Given an effective resolution, a triangle, and a specific vertex [0; 2], calculate a new position for the
// vertex, which will result in conservative rasterization when fed to a non-conservative rasterizer.
void ExpandTriangleForConservativeRasterization(
    uint2 resolution,
    float2 tri[3],
    uint vertexId,
    out float4 triangleAABB,
    out float4 vertex,
    float eps = 0.0f)
{
    float2 pixelSize = (1.0 / resolution);

    // Calculate the AABB to clip off the overly conservative edges
    float2 aabbMin = min(min(tri[0], tri[1]), tri[2]);
    float2 aabbMax = max(max(tri[0], tri[1]), tri[2]);
    triangleAABB = (float4(aabbMin - (pixelSize / 2), aabbMax + (pixelSize / 2))) * resolution.xyxy;

    // Get offset lines
    float2 v1Off1, v2Off1;
    OffsetEdge(tri[0], tri[1], pixelSize, v1Off1, v2Off1);
    float2 v2Off2, v3Off2;
    OffsetEdge(tri[1], tri[2], pixelSize, v2Off2, v3Off2);
    float2 v3Off3, v1Off3;
    OffsetEdge(tri[2], tri[0], pixelSize, v3Off3, v1Off3);

    // Find their intersections. This is the new triangle
    tri[0] = LineIntersect(v1Off1, v2Off1, v3Off3, v1Off3, eps);
    tri[1] = LineIntersect(v2Off2, v3Off2, v1Off1, v2Off1, eps);
    tri[2] = LineIntersect(v3Off3, v1Off3, v2Off2, v3Off2, eps);
    vertex = float4(tri[vertexId % 3]*2-1, 0, 1);
    #if UNITY_UV_STARTS_AT_TOP
    vertex.y = -vertex.y;
    #endif
}