MassBattleFastTrig.h
Source/MassBattle/Public/Math/MassBattleFastTrig.h
概述 Overview
float 域查表三角函数库,面向 float 原生的热区(float 版移动/物理处理器、网格子系统查询)。与 FFix64 定点库(见 Math/MassBattleFixedPoint.h)使用同一套烘焙常数表技术,但输入输出都是 float——省去定点 ↔ float 的转换开销。查表与插值只做表读 + IEEE 加/乘:同版本锁步双端计算结果位级一致(确定性不受影响),跨版本结果漂移 ~1e-6(已接受)。精度契约:sin/asin 绝对误差 ≤ ~9e-7、atan2 ≤ ~2.7e-7,远在插件 TrigTol(2e-5)之内。全部函数 FORCEINLINE,角度单位为弧度(与 FMath 同约定)。表数据来自同目录的生成文件 MassBattleFastTrigLUT.inc(由 Tools/FixMathBench/gen_lut.py 生成,手改无效)。
A float-domain table-lookup trigonometry library aimed at float-native hot zones (the float move/physics processors, grid-subsystem queries). It uses the same baked-constant-table technique as the FFix64 fixed-point library (see Math/MassBattleFixedPoint.h) but is float-in / float-out — no conversion tax. Lookup + interpolation is table reads + IEEE add/mul only: same-build lockstep peers compute IDENTICAL bits (determinism unaffected); cross-version results shift by ~1e-6 (accepted). Accuracy contract: absolute error ≤ ~9e-7 (sin/asin), ≤ ~2.7e-7 (atan2) — far inside the plugin's TrigTol (2e-5). Every function is FORCEINLINE; all angles in RADIANS (same convention as FMath). The table data comes from the sibling generated file MassBattleFastTrigLUT.inc (regenerated by Tools/FixMathBench/gen_lut.py; hand edits are void).
实测性能(FixMathBench 基准,MSVC x64 /O2,1M 次操作):Atan2 ~4.5 ns 对 CRT atan2f ~7.2 ns(快 1.6 倍,最大误差 ~2.7e-7 rad);Asin ~8.2 ns 对 asinf ~9.1 ns(最大误差 ~9e-7);Sin ~6.7 ns 对 sinf ~8.0 ns(适用于嵌入 FFix64 不便的区域——若手上只有一个 float 输入,优先 FFix64::Sin,含转换共 3.7 ns)。
Measured performance (FixMathBench harness, MSVC x64 /O2, 1M ops): Atan2 ~4.5 ns vs CRT atan2f ~7.2 ns (1.6x faster, max err ~2.7e-7 rad); Asin ~8.2 ns vs asinf ~9.1 ns (max err ~9e-7); Sin ~6.7 ns vs sinf ~8.0 ns (for zones where embedding FFix64 is awkward — prefer FFix64::Sin (3.7 ns incl. conversions) when a single float input is all you have).
表几何常数 Table Geometry
| 名称 Name | 类型 Type | 值 | 说明 Description |
|---|---|---|---|
SinLutSize | constexpr int32 | 4096 | sin 表在 [0, 2π) 上的区间数(表另含一个精确回绕端点)。Intervals of the sin table over [0, 2π) (the table holds one extra exact-wrap endpoint). |
SinLutScale | constexpr float | 651.898686f | 4096 / 2π——弧度转表下标的乘法系数。4096 / 2π — the radian-to-table-index multiplier. |
AtanLutScale | constexpr float | 8192.0f | atan 表在 [0, 1] 上的区间数——2 的幂,乘法即可完成索引(无除法)。Intervals of the atan table over [0, 1] — a power of two, so indexing is a multiply (no division). |
TwoPiD / InvTwoPiD | constexpr double | 6.283185…/其倒数6.283185… / its reciprocal | 双精度 2π 与 1/2π,供 Reduce 归约使用。Double-precision 2π and 1/2π used by the Reduce step. |
HalfPi / Pi | constexpr float | 1.5707963… / 3.1415926… | π/2 与 π 常数(象限修正、acos/asin 换算用)。π/2 and π constants (quadrant fix-ups, acos/asin conversion). |
函数 Functions
内联无分支 floor:MSVC 的 SSE2 基线 floor() 是一次 CRT 调用(实测 ~5 ns),而 cvtt + comis + sub 只有三条指令。实现为「截断取整,截断值大于原值则再减 1」。本库的输入域是 |rad/2π| < 2^28,远在 int64 安全范围内,故截断不会溢出。
Inline branchless floor: MSVC's SSE2-baseline floor() is a CRT call (~5 ns measured); cvtt + comis + sub is three instructions. Implemented as "truncate, then subtract 1 if the truncation went up". The input domain here is |rad/2π| < 2^28, far inside int64, so the truncation cannot overflow.
Input
| 参数 Param | 类型 Type | 说明 Description |
|---|---|---|
X | double | 待取整值;约定输入域 |X| 远小于 2^63(本库实际 < 2^28 量级)。Value to floor; the input domain is assumed far below 2^63 (this library stays around < 2^28). |
Output
返回 ⌊X⌋(double)。无副作用。
Returns ⌊X⌋ (double). No side effects.
把任意弧度归约到 [0, 2π),全程双精度:rad - 2π·⌊rad/2π⌋。为什么不用 float:float 域的 rad - Tau*k 在 |rad| > ~10 时发生灾难性相消(实测 sin 误差 9e-6),双精度把归约角保持精确到 ~1e-9。这是全库精度的根基。
Reduces any radian to [0, 2π) entirely in double precision: rad - 2π·⌊rad/2π⌋. Why not float: a float-domain rad - Tau*k cancels catastrophically for |rad| > ~10 (measured 9e-6 sin error); double keeps the reduced angle exact to ~1e-9. This is the foundation of the whole library's accuracy.
Input
| 参数 Param | 类型 Type | 说明 Description |
|---|---|---|
Rad | float | 任意弧度值(可正可负、可远大于 2π)。Any radian value (signed, may be far beyond 2π). |
Output
返回 [0, 2π) 内的等价角(float)。无副作用。
Returns the equivalent angle in [0, 2π) (float). No side effects.
正弦(弧度),最大绝对误差 ~9e-7。流程:Reduce 归约 → 乘 SinLutScale 得表坐标 U ∈ [0, 4096) → 取整数下标 I 与小数部分 T → 表内线性插值 GFastSinTab[I] + (GFastSinTab[I+1] − GFastSinTab[I])·T。
Sine (radians), max abs err ~9e-7. Flow: Reduce → multiply by SinLutScale to get table coordinate U ∈ [0, 4096) → integer index I + fraction T → linear table interpolation GFastSinTab[I] + (GFastSinTab[I+1] − GFastSinTab[I])·T.
Input
| 参数 Param | 类型 Type | 说明 Description |
|---|---|---|
Rad | float | 角度(弧度)。Angle in radians. |
Output
返回 sin(Rad)(float)。无副作用。
Returns sin(Rad) (float). No side effects.
余弦(弧度)= Sin(Rad + π/2),共享同一次归约路径。
Cosine (radians) = Sin(Rad + π/2), sharing the same reduction path.
Input
| 参数 Param | 类型 Type | 说明 Description |
|---|---|---|
Rad | float | 角度(弧度)。Angle in radians. |
Output
返回 cos(Rad)(float)。无副作用。
Returns cos(Rad) (float). No side effects.
一次调用同时求 sin 与 cos,只做一次归约与一次表坐标换算:得到 sin 的表坐标 U 后,cos 的表坐标直接用 U2 = U + 1024(表坐标平移 π/2 = 1024 格),越界(U2 ≥ 4096)减回一个周期,再各自插值。比分别调用 Sin+Cos 省一次归约。
Computes sin and cos in one call with one reduction and one coordinate conversion: after obtaining the sin table coordinate U, the cos coordinate is simply U2 = U + 1024 (a π/2 shift = 1024 table cells), wrapped back by one period when U2 ≥ 4096, then each side interpolates. Saves one reduction versus calling Sin + Cos separately.
Input
| 参数 Param | 类型 Type | 说明 Description |
|---|---|---|
Rad | float | 角度(弧度)。Angle in radians. |
OutSin / OutCos | float& | 输出引用,分别接收 sin(Rad) 与 cos(Rad)。Output references receiving sin(Rad) and cos(Rad) respectively. |
Output
无返回值。副作用:写入两个输出引用。
No return value. Side effect: writes the two output references.
[0, 1] 域反正切的查表核心:2 的幂索引(A × 8192,乘法即下标,无除法)+ 线性插值。供 Atan2 内部使用,不面向外部调用者(输入必须已在 [0, 1])。
The [0, 1]-domain arctangent table core: power-of-two indexing (A × 8192, a multiply is the index, no division) + linear interpolation. Used internally by Atan2; not intended for external callers (the input must already lie in [0, 1]).
Input
| 参数 Param | 类型 Type | 说明 Description |
|---|---|---|
A | float | 比值,必须在 [0, 1] 区间。The ratio; must be within [0, 1]. |
Output
返回 atan(A)(弧度,float)。无副作用。
Returns atan(A) in radians (float). No side effects.
四象限反正切(弧度),最大绝对误差 ~2.7e-7。流程:X == 0 时直接按 Y 符号返回 ±π/2(Y 也为 0 返回 0);否则取 |Y|、|X|,先选出 ≤ 1 的比值再查表——Ay ≤ Ax 时 AtanPos(Ay/Ax),反之 π/2 − AtanPos(Ax/Ay)(整条路径只有一次除法、无 >1 分支);最后按 X、Y 符号做象限修正(X < 0 时结果为 ±(π − Base))。
Four-quadrant arctangent (radians), max abs err ~2.7e-7. Flow: X == 0 returns ±π/2 by the sign of Y (0 when Y is 0 too); otherwise take |Y|, |X| and pick the ≤ 1 ratio up front — AtanPos(Ay/Ax) when Ay ≤ Ax, else π/2 − AtanPos(Ax/Ay) (one division total, no >1 branch); finally quadrant fix-ups by the signs of X and Y (X < 0 yields ±(π − Base)).
Input
| 参数 Param | 类型 Type | 说明 Description |
|---|---|---|
Y | float | 分子(通常是方向向量的 Y 分量)。Numerator (typically the Y component of a direction vector). |
X | float | 分母(方向向量的 X 分量;为 0 时走垂直特判)。Denominator (the X component; 0 takes the vertical special case). |
Output
返回 atan2(Y, X)(弧度,float),(X, Y) = (0, 0) 时返回 0。无副作用。
Returns atan2(Y, X) in radians (float); 0 for (X, Y) = (0, 0). No side effects.
反正弦(弧度):atan2(x, sqrt(1−x²))——直接建 asin 表在 |x|→1 处极点病态,而 atan 表天然化解了极点条件化问题。|x| > 1(越界)返回 0,与 FFix64::Asin 同契约。符号按原输入恢复。
Arcsine (radians): atan2(x, sqrt(1−x²)) — a direct asin table is ill-conditioned near |x| = 1, while the atan table absorbs that pole conditioning. Out-of-domain |x| > 1 returns 0 (same contract as FFix64::Asin). The original sign is restored at the end.
Input
| 参数 Param | 类型 Type | 说明 Description |
|---|---|---|
X | float | 正弦值,有效域 [−1, 1];越界返回 0。Sine value, valid domain [−1, 1]; out of range returns 0. |
Output
返回 asin(X)(弧度,float);|X| > 1 时返回 0。无副作用。
Returns asin(X) in radians (float); 0 when |X| > 1. No side effects.
反余弦(弧度)= π/2 − asin(x)。越界语义继承自 Asin(|x| > 1 时返回 π/2)。
Arccosine (radians) = π/2 − asin(x). Out-of-domain semantics inherit from Asin (π/2 when |x| > 1).
Input
| 参数 Param | 类型 Type | 说明 Description |
|---|---|---|
X | float | 余弦值,有效域 [−1, 1]。Cosine value, valid domain [−1, 1]. |
Output
返回 acos(X)(弧度,float)。无副作用。
Returns acos(X) in radians (float). No side effects.
管线角色 Pipeline Role
本库是纯函数工具集,不持有状态、不参与管线调度;以下直接消费者均在发布树 grep 验证:Processors/MassBattleAgentMoveProcessor.cpp(Asin 用于旋转扫掠弧占位、Acos 用于朝向夹角、Atan2 用于偏航解算、Cos 用于最大可行走坡度换算)、Processors/MassBattleAgentMoveProcessorFP.cpp(定点路径中的 Asin 扫掠占位)、Processors/MassBattlePhysicsProcessor.cpp(Asin——独立物理引擎的扫掠弧占位)、Components/MassBattleAgentComponent.cpp(Atan2 目标朝向角)、Subsystems/MassBattleHashGridSubsystem.cpp(Cos——每查询一次的锥半角查表)。此外 MassBattleAgentBehaviorProcessor.cpp、MassBattleAgentTraceProcessor.cpp、MassBattleLootMonoProcessor.cpp 亦包含对 MassBattleFastTrig:: 的直接调用。
A pure-function utility library — stateless, not part of any pipeline scheduling. Direct consumers verified by grep in the release tree: Processors/MassBattleAgentMoveProcessor.cpp (Asin for rotational sweep-arc occupancy, Acos for orientation angles, Atan2 for yaw solving, Cos for max-walkable-slope conversion), Processors/MassBattleAgentMoveProcessorFP.cpp (Asin sweep occupancy inside the fixed-point path), Processors/MassBattlePhysicsProcessor.cpp (Asin for the standalone physics engine's sweep-arc occupancy), Components/MassBattleAgentComponent.cpp (Atan2 for target orientation), Subsystems/MassBattleHashGridSubsystem.cpp (Cos — one table lookup per query for cone half-angles). MassBattleAgentBehaviorProcessor.cpp, MassBattleAgentTraceProcessor.cpp and MassBattleLootMonoProcessor.cpp also contain direct MassBattleFastTrig:: calls.
补充说明 Notes
查表数据 GFastSinTab(4096 + 回绕端点)与 GFastAtanTab(8192 + 端点)是 MassBattleFastTrigLUT.inc 中的 inline constexpr float[]——生成文件,改动会被重新生成覆盖。确定性边界:同版本双端位级一致的前提是「烘焙常数表 + 纯 IEEE 加/乘」,跨版本表重生成可能带来 ~1e-6 的结果漂移(官方接受)。若调用点只有单个 float 输入且不介意转换,FFix64 路径(含转换 3.7 ns)快于本库的 Sin。
The table data GFastSinTab (4096 + wrap endpoint) and GFastAtanTab (8192 + endpoint) are inline constexpr float[] in MassBattleFastTrigLUT.inc — a generated file; hand edits will be overwritten on regeneration. Determinism boundary: same-build bit-identical results rest on "baked constant tables + IEEE add/mul only"; regenerating the tables across versions may shift results by ~1e-6 (officially accepted). If a call site has a single float input and can afford the conversion, the FFix64 path (3.7 ns including conversions) beats this library's Sin.