射线与三角形求交：Möller–Trumbore 算法详解与证明

前言

这篇文章是我和 AI 一来一回聊出来的。

起因只是一个很小的问题：射线与三角形求交，除了「先求射线与平面的交点、再判断点是否在三角形内」这个老办法，Möller–Trumbore 那个一口气解出 $t,u,v$ 的做法究竟是怎么来的？结果问题越追越多——为什么这里冒出一个克莱姆法则？克莱姆法则本身为什么成立？混合积为什么能写成行列式？由于很多数学知识遗忘了，于是就这么一路问下去，把原本只会照抄公式的地方，逐个变成了能自己推出结论的地方。

收获比预期大。以前看这类实现，眼里只是一串叉乘和点乘；现在知道每一步在算什么、为什么可以那样重排，以及符号最容易在哪一步翻车。怕自己忘，也怕以后只记得结论不记得原因，就把这次讨论整理成了这篇。

确定性哈希随机决胜：低成本、可复现的平局策略

在游戏开发中，我们经常需要从一组候选项中选出“最优解”。当多个候选项的主评分完全相同时，一个容易被忽略的问题就出现了：平局时该选谁？，如果只依赖于判别时的不等号，那么结果必然是“偏置”的。

我是在一次网格密度搜索中遇到这个问题的。最终采用的方案是确定性哈希随机决胜（Deterministic Hash-based Random Tie-breaking）：用一次随机取种，为每个候选项生成可复现的伪随机优先级，在不收集全部平局候选的情况下完成决胜。

从网格密度搜索说起

假设地图由一个二维网格表示，每个格子记录该位置是否存在目标。搜索时，用一个固定尺寸的矩形窗口遍历所有合法位置，计算窗口覆盖范围内的目标数量，也就是该窗口的密度，实现中采用的就是经典的二维前缀和算法。

背景

某些穿透型子弹弹道较粗，如果索敌模式选择最近的敌人，就会“耿直”地以最近的敌人为目标发射子弹，导致索敌看起来很呆，只命中很少的敌人。其实很多时候，目标周围有很多敌人，由于弹道较粗，只要稍微调整下发射角度就可以命中一堆敌人。

问题定义

穿透型宽弹道的子弹，可以看作一个矩形弹道，子弹起点 start （取 XZ 平面的二维坐标），初始方向 dir ，子弹射程 length ，子弹半宽 halfWidth ，给定主目标 targetEntity ，在保证主目标包含在这个矩形区域内，调整弹道角度，期望以覆盖更多敌人。

一开始会想针目标计算左右边界角度 [targetMinAngle, targetMaxAngle] ，然后以子弹起点为圆心，射程为半径进行怪物查询，查询后对每个目标依次求得 [monsterMinAngle, monsterMaxAngle] 边界，最后求得最大重叠区域的角度。但是这其中的关键点是角度，处理过程中会频繁进行角度、三角函数、反三角函数的转换，这在定点数游戏里一方面性能开销较大，另一方面多次转换后误差也会叠加。

轻量级模块仓库与事件系统设计

设计目标

在 Unity 项目中提供一套轻量级的全局模块仓库和事件系统。模块的生命周期与游戏进程一致：启动后按需创建或显式注册，在游戏运行期间持续存活，并在游戏关闭时统一释放。

业务代码通过以下接口使用系统：

1
2
3
4
5
6

ModuleRepository.GetOrCreate<T>();
ModuleRepository.Register(myModule);
EventModule.Subscribe<T>(callback);
EventModule.Unsubscribe<T>(callback);
eventData.Fire();
eventData.FireDeferred(EventDispatchPhase.Update);

Arch ECS 学习笔记

这份笔是我学习Github开源项目Arch ECS后的学习代码，通过断点调试 + 与AI交流完成碎片化记录，最终再交由AI整合完成。主要内容包含Archetype ECS结构学习，以及一些项目里用到的技巧总结。

在学习过程中发现了两处问题，一处是BitSet的Any处包含冗余的循环代码；一处是CommandBuffer部分的SparseSet里创建SparseArray时传参错误。目前已经提交了PR。

总体结构

Arch 的核心数据关系可以先记成这张图：

迭代器方法

简单写一个迭代器方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void Start()
{
    foreach (var e in Iterator())
    {
        Console.WriteLine(e);
    }
}

IEnumerable<int> Iterator()
{
    Console.WriteLine("00");
    yield return 1;
    Console.WriteLine("11");
    yield return 2;
    Console.WriteLine("22");
}

上面的迭代器方法，在内部，编译器会生成一个匿名类，代码如下：

• 仔细观察会发现，这个匿名类同时继承IEnumerator和IEnumerable，意味着它同时负责生产迭代器和迭代。
• 状态点数字的含义：-1代表正在执行/当前不处于挂起点；-2代表尚未枚举或者已经Dispose；大于等于0代表各个恢复点

边函数光栅化 (Edge Function Rasterization)

算法简介

边函数光栅化，又称 Pineda’s Algorithm，由 Juan Pineda 于 1988 年 SIGGRAPH 论文 A Parallel Algorithm for Polygon Rasterization 提出。它是现代 GPU 硬件光栅化的基础算法。

核心思想：多边形的每条边将平面划分为两个半平面，点在多边形内部当且仅当它在所有边的内侧半平面内。

数学本质

射线检测法

经常用于判断点是否在多边形内部，可用于处理非凸多边形，不要求顺时针逆时针，该算法的思路十分巧妙：

从目标点向任意约定方向，通常选 右侧（X 轴正方向） 发射一条无限长的水平射线，统计这条射线与多边形边的相交次数

• 奇数 → 点在多边形内部
• 偶数 → 点在多边形外部

不多介绍，下文主要说下算法的两个形式和优化变体。

稀疏集

SparseSet（稀疏集） 是一种专为有界整数 ID设计的高性能集合数据结构，核心优势是插入、删除、查询、清空均为 O (1) 时间复杂度，且遍历高效、缓存友好。它通过稀疏数组（sparse）+ 密集数组（dense）+ 元素计数（n） 实现，广泛用于游戏引擎（如 ECS）、编译器、图算法等场景。

核心结构

SparseSet 由三部分组成：

• dense[]（密集数组）：按插入顺序存储集合中的实际元素值，仅包含存在的元素，内存紧凑、遍历高效。
• sparse[]（稀疏数组）：以元素值为索引，存储该元素在 dense 数组中的下标位置；未存在的元素对应位置值无意义。
• count（元素计数）：记录当前集合中元素的总数，dense[0…count-1] 为有效元素。

算法图解

ORCA避障算法，出自2011年的一篇论文《Optimal Reciprocal Collision Avoidance》。该算法的思想不算复杂，但实现上有很多细节需要注意。网上已有很多对该算法的讲解，但是大多都比较粗略，很多细节并未详解，缺少很多图解来帮助理解，因此本文着重通过图解的形式，辅以文字，来剖析该算法的思想，并对关键源码进行解释。

速度障碍（VO, Velocity Obstacle）

如图所示，假设存在A、B两个对象，它们以图中的速度（速度是向量，包含方向和模大小）运动。