· 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 个世界单位。因此,严格要求保留任意非零薄面的资产工具不能直接采用这个阈值,应提高输入精度或只对精确共线输入回退。碰撞运行时若已经规定小于该比例的面属于无效面,回退才与上游合同一致。

回退比较的是完整线段,不是三个顶点
只在退化时比较 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”补丁,会掩盖真正的架构选择:几何层究竟要保存极薄的有效面,还是把它归并为稳定的一维形状。