game-spatial-queries

游戏空间查询

使用此技能，将游戏中的拾取、碰撞、包含关系和距离问题转化为带有明确约束和失败情形的小型几何系统。

主要来源：Oleksandr Kaleniuk 所著《Geometry for Programmers》 （https://www.manning.com/books/geometry-for-programmers），经改编和转述，尤其参考第 3、4 和 9 章。其他来源：Tomas Moller 和 Ben Trumbore 撰写的“Fast, Minimum Storage Ray-Triangle Intersection” （https://dl.acm.org/doi/10.1145/1198555.1198746）。

核心工作流

1. 将查询表述为谓词或测量值：命中／未命中、内部／外部、最近距离、有符号侧、交点或参数值。
2. 尽可能转换到最简单的局部基底中。三角形、线段、平面和物体局部基底通常能将查询简化为边界检查。
3. 先推导参数，再应用约束。在代码中清晰呈现约束，不要把它们隐藏在一个庞大的表达式里。
4. 找出表示退化情况的分母、方向或长度值。
5. 选择数值策略：精确整数谓词、与尺度相关的 epsilon、包含边界、排除边界或保守回退。
6. 测试命中、未命中、边界、平行、退化和近退化情况。
7. 如果查询会影响游戏手感，请添加调试可视化。

查询模式

射线与三角形相交

将射线表示为 R = P + t*d，其中 t >= 0。将三角形上的点表示为 S = A + u*AB + v*AC，其中 u >= 0、v >= 0 且 u + v <= 1。

求解 R = S，然后：

• 如果共享分母为零，或小到不符合数值策略，则拒绝。
• 如果 t < 0，则拒绝。
• 如果 u < 0、v < 0 或 u + v > 1，则拒绝。
• 返回命中距离 t、类似重心坐标的参数 u 和 v，以及需要时的命中点。

点是否位于三角形内

优先采用以下方法之一：

• 将三角形变换到其局部基底，并检查 0 <= u、0 <= v、u + v <= 1。
• 使用二维叉积计算一致的边方向符号。
• 如果调用方还需要插值权重，则使用重心坐标。

确定边上的点是否算作内部点。测试必须涵盖所选的边界策略和反向的三角形绕序。

点到平面的有符号距离

从两条不平行边构造平面法线。将单位化的法线与平面上任意一点到查询点的向量做点积。如果侧向很重要，就保留符号；只有计算无符号距离时才取绝对值。

线段和最近点查询

将点投影到线段方向上，把参数限制在 [0, 1]，然后计算点到限制后的位置的距离。进行单位化之前，先拒绝零长度线段或对其作特殊处理。

退化几何策略

• 不得单位化零长度向量。
• 退化三角形不得生成不稳定的基底或法线。
• 射线与平面平行时必须明确处理：无命中、处理共面情况，或使用回退查询。
• 对于很小的分母，必须制定与尺度相关的策略。在不同世界尺度下，固定 epsilon 往往不合适。
• 边界是否包含必须符合游戏需求：选择工具通常需要包含边界；碰撞分离通常需要保守检查。

实现检查清单

• 函数名应说明几何类型和边界策略。
• 输入应注明坐标空间和单位。
• 明确说明绕序假设。
• 在进行除法之前处理分母和零长度情况。
• 返回类型应向调用方提供足够的信息：bool、距离、命中点、法线、重心权重或拒绝原因。
• 测试应包含常规情况、未命中、边／顶点情况、反向绕序、平行情况、退化情况以及大／小尺度情况。

常见错误

• 明明使用对象局部坐标就能轻松完成查询，却在全局空间中计算。
• 查询只返回 bool，但后续还需要命中距离或法线。
• 比较浮点数与零时没有明确的处理策略。
• 忘记法线和重心坐标取决于绕序。
• 将“未命中”和“输入几何无效”视为相同的调试信号。