· 6 分钟阅读 · 2215 字

三角形退化成线段后,最近点查询不能继续除以面积

三角形顶点依次为 A=(0,0,0)、B=(2,0,0)、C=(4,0,0),查询点是 P=(3,2,0)。三个顶点完全共线,几何对象已经没有内部;如果仍把叉积当作平面法线,并计算 dot(P-A,N)/|N|²,分子与分母同时为零,投影点三个分量都会变成 NaN。这个结果随后进入距离、碰撞法线或角色贴地逻辑时,错误已经离开了最容易定位的几何边界。

同一输入仍有确定答案。退化三角形覆盖的是 x 轴上从 0 到 4 的线段,最近点为 Q=(3,0,0),平方距离为 4。本篇的 C# 探针在面域判定之前检查面积与边长的相对比例;达到退化阈值时,不再构造平面,而是分别求 AB、BC、CA 三条闭线段的最近点,再选择平方距离最小者。

自然光书桌上的共线顶点、查询点与最短连接;概念摄影,不是测试现场

面域分支的前提是二维区域仍然存在

非退化三角形的最近点可以落在七类 Voronoi 区域:三个顶点、三条边或面内部。实现按点积符号逐步排除区域,只在最后的面内部使用重心组合。固定正常输入 A=(0,0,0)、B=(2,0,0)、C=(0,2,0)、P=(1.5,1.5,1) 落在 BC 区域,返回 Q=(1,1,0);另一个旋转到 y=z 平面的固定三维样本返回面内部点 (0.5,0.5,0.5)。

共线时,七区域分类所依赖的二维面域消失。单纯在最终除法前钳制分母并不能恢复几何语义:钳制值会制造一个并不存在的面,并让结果取决于常量尺度。这里使用 areaSquared <= 1e-24 * maxEdgeSquared² 作为分支条件。左侧是叉积长度平方,右侧以最长边平方的平方归一尺度;整体比值无量纲,避免把一个固定世界单位 epsilon 同时套在厘米道具和千米地形上。以最长边为底,叉积长度等于底乘高,因此该条件等价于高与最长边之比不超过 1e-12。

这项阈值不是纯粹的数值保护,它会改变近退化但仍有非零面积的几何。固定窄三角形 A=(0,0)、B=(1,0)、C=(2,1e-13) 中,点 (1,2e-14) 位于真实三角形内部,精确距离为零;线段回退返回 (1,0),误差为 2e-14 个世界单位。因此,严格要求保留任意非零薄面的资产工具不能直接采用这个阈值,应提高输入精度或只对精确共线输入回退。碰撞运行时若已经规定小于该比例的面属于无效面,回退才与上游合同一致。

固定正常样本、共线样本、分支条件与窄三角近似误差;左图为 XY 投影,Z 值见标注

回退比较的是完整线段,不是三个顶点

只在退化时比较 A、B、C 三个顶点仍会漏掉线段内部的答案。当前样本的 Q 位于 B 与 C 之间,到任一端点都更远。每条边先计算投影参数 t=dot(P-A,B-A)/|B-A|²,再钳制到 [0,1];零长度边把 t 固定为零。三条候选按 AB、BC、CA 的顺序比较,只有严格更短才替换,因此距离相同时保留稳定区域名。三个顶点全部重合时,结果稳定为 AB 的起点,不依赖容器顺序。

核心文件是 .tmp/daily-labs/2026-11-06-1930/TriangleClosest.cs,调用链为 Program → TriangleClosest.Find → FindOnEdges / Voronoi regions → Result。返回值同时携带点、平方距离、区域和策略,调用者不必根据坐标反猜本次走了三角形还是退化路径。

public readonly record struct Vec3(double X, double Y, double Z)
{
    public static Vec3 operator +(Vec3 a, Vec3 b) => new(a.X + b.X, a.Y + b.Y, a.Z + b.Z);
    public static Vec3 operator -(Vec3 a, Vec3 b) => new(a.X - b.X, a.Y - b.Y, a.Z - b.Z);
    public static Vec3 operator *(Vec3 a, double s) => new(a.X * s, a.Y * s, a.Z * s);
    public double LengthSquared => Dot(this, this);
    public bool IsFinite => double.IsFinite(X) && double.IsFinite(Y) && double.IsFinite(Z);
    public static double Dot(Vec3 a, Vec3 b) => a.X * b.X + a.Y * b.Y + a.Z * b.Z;
    public static Vec3 Cross(Vec3 a, Vec3 b) => new(
        a.Y * b.Z - a.Z * b.Y,
        a.Z * b.X - a.X * b.Z,
        a.X * b.Y - a.Y * b.X);
}

public readonly record struct ClosestResult(Vec3 Point, double DistanceSquared, string Region, string Strategy);

public static class TriangleClosest
{
    private const double RelativeAreaSquared = 1e-24;

    public static ClosestResult Find(Vec3 point, Vec3 a, Vec3 b, Vec3 c)
    {
        if (!point.IsFinite || !a.IsFinite || !b.IsFinite || !c.IsFinite)
            throw new ArgumentException("coordinates must be finite");

        Vec3 ab = b - a, ac = c - a, bc = c - b;
        double scaleSquared = Math.Max(ab.LengthSquared, Math.Max(ac.LengthSquared, bc.LengthSquared));
        double areaSquared = Vec3.Cross(ab, ac).LengthSquared;
        if (!double.IsFinite(scaleSquared) || !double.IsFinite(areaSquared))
            throw new ArgumentOutOfRangeException(nameof(a), "intermediate exceeds numeric range");
        if (scaleSquared == 0 || areaSquared <= RelativeAreaSquared * scaleSquared * scaleSquared)
            return FindOnEdges(point, a, b, c);

        Vec3 ap = point - a;
        double d1 = Vec3.Dot(ab, ap), d2 = Vec3.Dot(ac, ap);
        EnsureFinite(d1, d2);
        if (d1 <= 0 && d2 <= 0) return Result(point, a, "A", "triangle");

        Vec3 bp = point - b;
        double d3 = Vec3.Dot(ab, bp), d4 = Vec3.Dot(ac, bp);
        EnsureFinite(d3, d4);
        if (d3 >= 0 && d4 <= d3) return Result(point, b, "B", "triangle");

        double vc = d1 * d4 - d3 * d2;
        EnsureFinite(vc);
        if (vc <= 0 && d1 >= 0 && d3 <= 0)
            return Result(point, a + ab * (d1 / (d1 - d3)), "AB", "triangle");

        Vec3 cp = point - c;
        double d5 = Vec3.Dot(ab, cp), d6 = Vec3.Dot(ac, cp);
        EnsureFinite(d5, d6);
        if (d6 >= 0 && d5 <= d6) return Result(point, c, "C", "triangle");

        double vb = d5 * d2 - d1 * d6;
        EnsureFinite(vb);
        if (vb <= 0 && d2 >= 0 && d6 <= 0)
            return Result(point, a + ac * (d2 / (d2 - d6)), "CA", "triangle");

        double va = d3 * d6 - d5 * d4;
        EnsureFinite(va);
        if (va <= 0 && d4 - d3 >= 0 && d5 - d6 >= 0)
        {
            double w = (d4 - d3) / ((d4 - d3) + (d5 - d6));
            return Result(point, b + bc * w, "BC", "triangle");
        }

        double inverse = 1.0 / (va + vb + vc);
        double v = vb * inverse, wFace = vc * inverse;
        return Result(point, a + ab * v + ac * wFace, "face", "triangle");
    }

    private static ClosestResult FindOnEdges(Vec3 point, Vec3 a, Vec3 b, Vec3 c)
    {
        var candidates = new[]
        {
            Segment(point, a, b, "AB"), Segment(point, b, c, "BC"), Segment(point, c, a, "CA")
        };
        ClosestResult best = candidates[0];
        for (int i = 1; i < candidates.Length; i++)
            if (candidates[i].DistanceSquared < best.DistanceSquared) best = candidates[i];
        return best;
    }

    private static ClosestResult Segment(Vec3 point, Vec3 a, Vec3 b, string region)
    {
        Vec3 edge = b - a;
        double lengthSquared = edge.LengthSquared;
        double projection = Vec3.Dot(point - a, edge);
        EnsureFinite(lengthSquared, projection);
        double t = lengthSquared == 0 ? 0 : Math.Clamp(projection / lengthSquared, 0, 1);
        return Result(point, a + edge * t, region, "edge-fallback");
    }

    private static ClosestResult Result(Vec3 source, Vec3 closest, string region, string strategy)
    {
        double distanceSquared = (source - closest).LengthSquared;
        EnsureFinite(distanceSquared);
        return new(closest, distanceSquared, region, strategy);
    }

    private static void EnsureFinite(params double[] values)
    {
        if (values.Any(value => !double.IsFinite(value)))
            throw new ArgumentOutOfRangeException("intermediate exceeds numeric range");
    }
}

受控随机样本验证区域选择,不替代退化断言

2026-11-06 使用 .NET 9 Release 构建并运行:

cd "$WORK_DIR"
dotnet build .tmp/daily-labs/2026-11-06-1930/TriangleClosestLab.csproj -c Release
dotnet run --project .tmp/daily-labs/2026-11-06-1930/TriangleClosestLab.csproj -c Release --no-build
build: exit=0, warnings=0, errors=0
run: exit=0, passed=21, failed=0, skipped=0
naive_collinear_finite=false
fixed_degenerate: Q=(3,0,0), distanceSquared=4, region=BC, strategy=edge-fallback
fixed_narrow: Q=(1,0,0), approximation_error=2e-14
random_cases=10000, face_cases=1537, boundary_cases=8463
max_error=2.5121479338940403e-15
elapsed_ms=47.1541

随机测试以固定种子 711061930 生成 10,000 个位于 XY 平面的轴对齐直角三角形,边长范围为 [0.1,5.1),查询点覆盖三角形内外并带 z 偏移。参照路径先投影到平面,以重心判断面内;面外则独立比较三条线段。它验证当前区域分支在这类受控非退化输入上的一致性,不代表任意三维、极端长宽比或次正规数都已覆盖。旋转三维平面由固定样本补充,非有限坐标和导致中间量溢出的极端范围则明确拒绝。

耗时只记录这次正确性进程,不是碰撞查询性能数据。params 形式的有限性检查也会产生临时数组;接入高频窄阶段时可以改成无分配的定长重载,但不能因此删除溢出门禁。

最近点也不足以独自定义接触响应。当查询点恰在线段上时,距离为零,差向量没有方向;退化线段本身同样没有唯一面法线。几何层因此只交付点、平方距离、区域和策略,不凭空补一条法线。角色控制器或接触求解器若需要分离方向,应由运动方向、前一接触法线及明确的恢复规则决定;返回有限最近点,并不意味着已经建立完整的碰撞接触。

共线输入的线段回退是精确几何:三条边的并集等于退化三角形覆盖的闭线段。近退化输入的同一路径则是资产或运行时合同规定的近似,阈值必须和允许丢弃的薄面尺度一起评审。把两者写成同一个“防 NaN”补丁,会掩盖真正的架构选择:几何层究竟要保存极薄的有效面,还是把它归并为稳定的一维形状。