2D, HLSL - Nearest point on Line Segment A to Line Segment B (in shader)

Question

TL,DR: What is the best way (in HLSL) to compute the closest point on Line Segment A (defined by float2-s AStart, AExtent) to any point on Line Segment B (similarly so defined)?

I've been wrestling with this function and my current solution (based on Shortest distance between two line segments - which is for 3D) VERY NEARLY works, but has obvious bugs I'm just finding impossible to properly debug within the shader.

This particular math is a bit over my head, and I'm not sure if I adapted it wrong or the approach is having an issue in 2D vs 3D (though that seems unlikely).

Any help here would be SUPER appreciated 9_9

MORE CONTEXT:

So I've been experimenting with a new 2D lighting framework for Unity, and I've got it nearly done except for this final issue.

The gist of the system is that I have shadows being rendered in a shader instead of being constructed into a fully-defined mesh. So far, this seems dramatically more performant, and is enabling things like function-defined shadows instead of requiring concrete meshes to be built (for example: actual circular shadows, instead of the various workaround methods commonly used).

Example: Screenshot of in-progress lighting system

As you can see, circle shadows are working, and I'm trying to enable shadow mesh line segments to have radius to enable a variety of additional shadow types (ex: capsule shadows). My thought was to treat line segments as circles evaluated to be on the "closest point" to a light ray.

If that's not actually the best way, I'm also open for suggestions on better functions! :D

FWIW, here is the current shader code I'm trying to fix:

//UNITY_SHADER_NO_UPGRADE
#ifndef SHADOWCOLLISION_RADIUS_INCLUDED
#define SHADOWCOLLISION_RADIUS_INCLUDED

float SCR_Cross2D(float2 A, float2 B)
{
    return (A.x * B.y) - (A.y * B.x);
}

// Adapted from https://stackoverflow.com/questions/2824478/shortest-distance-between-two-line-segments
// Big thanks to Fnord + Jacob Jensen, this is an annoying amount of math 9_9
float2 SCR_ClosestPointOnA(float2 A0, float2 A1, float2 B0, float2 B1)
{
    float2 A = A1 - A0;
    float lenA = length(A);
    float2 AN = A / lenA;

    float2 B = B1 - B0;
    float lenB = length(B);
    float2 BN = B / lenB;

    float cross = SCR_Cross2D(AN, BN);
    float denom = cross * cross;

    // If lines are parallel (denom ~= 0) test if lines overlap.
    // If they don't overlap then there is a closest point solution.
    // If they do overlap, there are infinite closest positions, but there is a closest distance
    if (denom <= 0.0000001)
    {
        float d0 = dot(AN, B0 - A0);
        float d1 = dot(AN, (B1 - A0));
        if (d0 <= 0 && 0 >= d1) // Is segment B before A?
        {
            return A0;
        }
        else if (d0 >= lenA && lenA <= d1) // Is segment B after A?
        {
            return A1;
        }
        return (A0 + A1) / 2; // whatever, this is a super niche case, who cares
    }

    // Lines criss-cross: Calculate the projected closest points
    float2 Off = B0 - A0;
    float detA = determinant(float3x3(
        Off.x, Off.y, 0, 
        BN.x,  BN.y,  0,
        0,     0,     cross));
    float detB = determinant(float3x3(
        Off.x, Off.y, 0,
        AN.x, AN.y, 0,
        0, 0, cross));

    float t0 = detA / denom;
    float2 AClosest = A0 + (AN * t0); // Projected closest point on segment A
    if (t0 < 0) // Clamp projections
    {
        AClosest = A0;
    }
    else if (t0 > lenA)
    {
        AClosest = A1;
    }
    
    float t1 = detB / denom;
    float2 BClosest = B0 + (BN * t1); // Projected closest point on segment B
    if (t1 < 0) // Clamp projections
    {
        BClosest = B0;
    }
    else if (t1 > lenA)
    {
        BClosest = B1;
    }

    // Clamp projection A
    if (t0 < 0 || t0 > lenA)
    {
        BClosest = B0 + (BN * min(max(dot(BN, (AClosest - B0)), 0), lenB));
    }
    // Clamp projection B
    if (t1 < 0 || t1 > lenB)
    {
        AClosest = A0 + (AN * min(max(dot(AN, (BClosest - A0)), 0), lenA));
    }
    return AClosest;
}

// SPos = Start of shadow line segment
// SVec = Extent of shadow line segment
// SR = Radius of the shadow line segment
// LPos = Position of light
// LVec = Extent of light vector for this sample of the shadow map
// IntersectVal = multiplier of LVec that the light can maximally extend (or 1 if the light should not be blocked)
void ShadowCollision_Radius_float(float2 SPos, float2 SVec, float SR, float2 LPos, float2 LVec, out float IntersectVal)
{
    float2 SClosest = SCR_ClosestPointOnA(SPos, SPos + SVec, LPos, LPos + LVec);

    float lenL2 = dot(LVec, LVec);
    if (lenL2 <= 0.0000001) {
        IntersectVal = 1;
        return;
    }

    float2 Offset = SClosest - LPos;
    const float t = dot(Offset, LVec) / lenL2;
    if (t <= 0) { // Behind light ray, ignore
        IntersectVal = 1;
        return;
    }

    float2 LClosest = LPos + (t * LVec);

    float2 D = SClosest - LClosest;
    float lenD2 = dot(D, D);
    float R2 = SR * SR;

    if (R2 < lenD2) { // Beyond radius of light.
        IntersectVal = 1;
        return;
    }

    float lenM = sqrt(R2 - lenD2);
    float lenL = sqrt(lenL2);
    IntersectVal = max(0, min(1, (distance(LPos, LClosest) - lenM) / lenL));
}

#endif //SHADOWCOLLISION_RADIUS_INCLUDED

2D, HLSL - Nearest point on Line Segment A to Line Segment B (in shader)

0 Answers0