· 5 分钟阅读 · 1935 字
长条碰撞体跨过网格后：只登记中心格会漏掉相交对象
一根横向碰撞体覆盖 x 轴的 0.2 到 2.2 米，另一物体覆盖 2.1 到 2.4 米。两者已经重叠 0.1 米，但把它们分别登记到中心所在网格后，同格配对没有产生候选。窄阶段的相交函数即使完全正确，也没有机会修复这个遗漏。
本篇用独立 C# 二维宽阶段探针复现这个问题。单元边长固定为 1 米，A 的 y 范围为 [0.2,0.8]，B 为 [0.3,0.7]。A 的中心在 (1.2,0.5)，B 在 (2.25,0.5)，中心单元分别是 (1,0) 与 (2,0)。完整包围盒登记让 A 同时进入三个单元，B 进入 (2,0)，两者才在公共单元相遇。这里使用轴对齐包围盒，未运行具体引擎或真实刚体求解。
候选集合必须覆盖窄阶段接受的接触
宽阶段允许多报候选，不能漏掉窄阶段可能接受的对象。若两个闭区间 AABB 相交，它们至少共享一个点 p。对 p 的每轴坐标执行 floor(p/size)，这个单元索引必定位于两个包围盒各自的最小、最大索引之间。因此，只要登记这个整数范围中的全部单元，公共单元就存在。
这个证明不依赖物体中心，也不要求碰撞体尺寸小于网格。代价是每个物体可以占用多个桶，候选对可能重复。生产实现需要以排序后的对象 ID 对去重，再交给窄阶段；把重复对象对带进接触求解，会把候选数量问题变成重复施力问题。本探针的 Intersect 只判断两组单元是否相交，不模拟桶、对象生命周期或冲量。
闭区间还有一个容易被“减少登记量”破坏的边界。[-1,0] 与 [0,1] 在 x=0 接触，若窄阶段使用 <= 接受接触，登记也必须让左侧盒子的最大边界进入单元 0。把最大坐标先减去一个固定 epsilon，可能直接删除这个公共单元。epsilon 的米制长度还会随世界尺度改变含义，不能拿来替代接触合同。
负坐标使用向下取整。floor(-0.2) 是 -1，直接转整数却是 0。后一种写法把原点左侧的一段位置塞进右侧单元，破坏统一的单元边界。若所有登记与查询都一致采用截断，单凭这一点不能断言必然漏检；但只要查询范围仍按 floor 推导，两端就在使用不同的空间分区。探针将负坐标索引单独锁定，不把它与中心格反例混为一个原因。
覆盖函数先校验，再返回完整集合
源码位于 .tmp/daily-labs/2026-11-05-1930/GridCoverage.cs。Program → Candidate → Cover 构成当前调用链，Overlap 是独立的闭区间 AABB 参照。
public readonly record struct Box(double MinX, double MinY, double MaxX, double MaxY);
public readonly record struct Cell(int X, int Y);
public static class GridCoverage
{
public static Cell[] Cover(Box b, double size)
{
if (!double.IsFinite(size) || size <= 0 ||
!double.IsFinite(b.MinX) || !double.IsFinite(b.MinY) ||
!double.IsFinite(b.MaxX) || !double.IsFinite(b.MaxY) ||
b.MinX > b.MaxX || b.MinY > b.MaxY)
throw new ArgumentException("invalid bounds or cell size");
int Index(double value)
{
double index = Math.Floor(value / size);
if (index < int.MinValue || index > int.MaxValue || !double.IsFinite(index))
throw new ArgumentOutOfRangeException(nameof(b));
return (int)index;
}
int x0 = Index(b.MinX), x1 = Index(b.MaxX);
int y0 = Index(b.MinY), y1 = Index(b.MaxY);
long nx = (long)x1 - x0 + 1, ny = (long)y1 - y0 + 1;
// 先检查每轴，再乘法，避免跨度乘积溢出。
if (nx > 4096 || ny > 4096 || nx * ny > 4096)
throw new ArgumentOutOfRangeException(nameof(b), "coverage budget exceeded");
var result = new List<Cell>((int)(nx * ny));
for (long y = y0; y <= y1; y++)
for (long x = x0; x <= x1; x++)
result.Add(new Cell((int)x, (int)y));
return result.ToArray();
}
public static bool Overlap(Box a, Box b) =>
a.MinX <= b.MaxX && b.MinX <= a.MaxX &&
a.MinY <= b.MaxY && b.MinY <= a.MaxY;
public static bool Candidate(Box a, Box b, double size) =>
Cover(a, size).Intersect(Cover(b, size)).Any();
}
Cover 对两轴的最小、最大坐标分别计算单元索引，再枚举笛卡尔积。零面积包围盒合法，因为本模型接受点与边接触。倒置边界、非有限输入、不可表示索引或超预算覆盖都会抛出异常；返回集合之前不会修改外部索引。
单轴跨度先提升为 long，循环变量也使用 long，避免索引位于 int 最大值时自增回绕。两轴各自先检查 4096 的上限，再相乘检查总量，避免极端跨度的乘积溢出。4096 是本探针的保护预算，没有性能测试支持它作为引擎默认值。
超预算后不能把覆盖集合截成前 4096 格，再继续当作成功登记。那样最远端的真实接触会从候选中消失。可选的生产策略是把大物体移到粗一级网格或单独列表，并保证查询同时覆盖这条路径。若暂时没有退化路径，就必须把拒绝作为显式错误处理；捕获异常后静默丢弃碰撞体同样违反完备性。多桶更新还需要先拿到完整新集合，再在一致的物理快照中替换旧登记，不能让查询看到更新一半的状态。
固定反例之外，检查整个接受集合
2026-11-05 使用 .NET 9 Release 执行。Check 检查中心登记反例、完整覆盖、闭边界接触、负坐标、同格但不相交、零面积与最大整数索引；Reject 覆盖非法尺度、倒置边界、非有限数与超预算范围。
cd "$WORK_DIR"
dotnet build .tmp/daily-labs/2026-11-05-1930/GridLab.csproj -c Release
dotnet run --project .tmp/daily-labs/2026-11-05-1930/GridLab.csproj -c Release --no-build
build: exit=0, warnings=0, errors=0
run: exit=0, passed=20, failed=0, skipped=0
fixed_a_cells=[(0,0),(1,0),(2,0)]
fixed_b_cells=[(2,0)]
center_only_candidate=false
all_cells_candidate=true
random_pairs=10000, overlaps=2484, candidates=4230, misses=0
elapsed_ms=65.2883
固定种子为 71105。每对第一个盒子的最小坐标位于 [-10,10)，各轴宽度位于 [0,3)；第二个盒子相对第一个最小坐标各轴偏移 [-3,3)，宽度独立生成。程序逐对检查 Overlap(a,b) ⇒ Candidate(a,b)。10,000 对中，精确相交 2,484 对，网格候选 4,230 对，漏检为零；其余 1,746 对说明共格不能直接视作碰撞。这组耗时只描述本次正确性探针，不能作为空间索引吞吐指标。
随机输入没有替代边界断言：接触恰好落在整数网格线、单点盒子和索引极值都由固定用例验证。实现针对同一时刻、有限 double 坐标的 AABB；连续碰撞还需要覆盖时间区间内的扫掠边界。旋转物体也必须先得到保守包围盒，网格不会补偿上游边界偏小。
中心格加邻格搜索也可以成立，但必须根据双方尺寸推导搜索半径；不能让固定九宫格承担任意大碰撞体。若对象尺寸差异很大，完整覆盖产生的多桶登记量会推动分层网格或大物体旁路的选择。无论选哪一种结构，评审应先检查候选是否覆盖窄阶段接受集合，再优化桶数与去重开销。否则换更精确的窄阶段，只会更精确地处理一份缺失的对象列表。