王者荣耀用的帧同步,帧同步需要用定点数。
因为帧同步需要每台机器上,给定相同的输入,都能得到确定相同的结果。浮点数不行,为什么?
1.精度不准确:十进制小数转二进制,存在转不尽;
2.运算不确定:不同机器运行有差异。例如a+b+c可能表示为(a+b)+c也可能a+(b+c)
王者实现的定点数:
数值以int形式保存,提供结构VInt,其中:
scalar设为0.001
实际存储为原值的1000倍。
小数以分子+分母的long形式保存,提供结构VFactor。
提供数学工具类IntMath,做基础数学运算
public static ulong Sqrt64(ulong a)
{
ulong num = 0uL;
ulong num2 = 0uL;
for (int i = 0; i < 32; i++)
{
num2 <<= 1;
num <<= 2;
num += a >> 62;
a <<= 2;
if (num2 < num)
{
num2++;
num -= num2;
num2++;
}
}
return (num2 >> 1) & 0xFFFFFFFFu;
}
public static long Divide(long a, long b)
{
//确定ab同号还是异号
//符号位异或,相同为0不同为1
//与long的最小值,把数值位清空(实则多余)
//右移63位,取出值0或1
long num = ((a ^ b) & long.MinValue) >>> 63;
//如果同号,值为1;如果异号,值为-1
long num2 = num * -2 + 1;
//加上负数的一半,实现四舍五入
return (a + b / 2 * num2) / b;
}
查表
public static VFactor sin(long nom, long den)
{
//根据传进来的弧度,找到“第几份”
//提前把2π分为4096份
//弧度/2π获得[0,1]占比,然后*4096找到第几份
int index = SinCosLookupTable.getIndex(nom, den);
//返回查表结果,sin表是*FACTOR=10000之后的
return new VFactor(SinCosLookupTable.sin_table[index], SinCosLookupTable.FACTOR);
}
public static int SinCosLookupTable.getIndex(long nom, long den)
{
//传进来的nom和den是分子和分母,以弧度表示
//我们要知道弧度在整个的占比,就用弧度/2π
//然后分成了4096份,找到第几份,于是弧度/2π*4096
//分子先*4096*10000
nom *= NOM_MUL;
//分母先*2π*10000,也就是62832
den *= 62832;
//计算结果
int num = (int)(nom / den);
//最后与一下MASK=4095,把结果限制在[0,4095]
return num & MASK;
}
BITS = 12;
MASK = ~(-1 << BITS);
//COUNT=4096,为了把一圈分成4096份
COUNT = MASK + 1;
FACTOR = 10000;
//避免小数运算
NOM_MUL = FACTOR * COUNT;
类似求Sin
public static VFactor acos(long nom, long den)
{
//首先mom/den的值在[-1,1]之间
//*512再+512,把值在[0,1024]之间
int value = (int)Divide(nom * AcosLookupTable.HALF_COUNT, den) + AcosLookupTable.HALF_COUNT;
//进一步clamp,如果上一步的值小于-1或者大于1
//即上一步的值小于0或者大于1014
value = Mathf.Clamp(value, 0, AcosLookupTable.COUNT);
//查表 返回结果 表里的值是*10000的
return new VFactor
{
nom = AcosLookupTable.table[value],
den = 10000L
};
}
COUNT = 1024;
HALF_COUNT = COUNT >> 1;
public static VFactor atan2(int y, int x)
{
//把x和y转到第一象限
//存好num和num2,后面把值再转回去
//第二象限,π-θ
//第三象限,θ-π
//第四象限,-θ
//31416就是π*10000
int num;
int num2;
if (x < 0)
{
if (y < 0)
{
x = -x;
y = -y;
num = 1;
}
else
{
x = -x;
num = -1;
}
num2 = -31416;
}
else
{
if (y < 0)
{
y = -y;
num = -1;
}
else
{
num = 1;
}
num2 = 0;
}
//缩放
//让最大变成127就行
int dIM = Atan2LookupTable.DIM;
long num3 = dIM - 1;
long b = ((x >= y) ? x : y);
int num4 = (int)Divide(x * num3, b);
int num5 = (int)Divide(y * num3, b);
//查表,二维数组转为一维数组
int num6 = Atan2LookupTable.table[num5 * dIM + num4];
//返回结果,注意结果是第一象限的,要把值转回去
return new VFactor
{
nom = (num6 + num2) * num,
den = 10000L
};
}
BITS = 7;
BITS2 = BITS << 1;
MASK = ~(-1 << BITS2);
COUNT = MASK + 1;
DIM = IntMath.Sqrt(COUNT);
public static bool IsPowerOfTwo(int x)
{
return (x & (x - 1)) == 0;
}
public static int CeilPowerOfTwo(int x)
{
x--;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x++;
return x;
}
public static void SegvecToLinegen(ref VInt2 segSrc, ref VInt2 segVec, out long a, out long b, out long c)
{
a = segVec.y;
b = -segVec.x;
c = (long)segVec.x * (long)segSrc.y - (long)segSrc.x * (long)segVec.y;
}
private static bool IsPointOnSegment(ref VInt2 segSrc, ref VInt2 segVec, long x, long y)
{
long num = x - segSrc.x;
long num2 = y - segSrc.y;
return segVec.x * num + segVec.y * num2 >= 0 && num * num + num2 * num2 <= segVec.sqrMagnitudeLong;
}
public static bool IntersectSegment(ref VInt2 seg1Src, ref VInt2 seg1Vec, ref VInt2 seg2Src, ref VInt2 seg2Vec, out VInt2 interPoint)
{
SegvecToLinegen(ref seg1Src, ref seg1Vec, out var a, out var b, out var c);
SegvecToLinegen(ref seg2Src, ref seg2Vec, out var a2, out var b2, out var c2);
long num = a * b2 - a2 * b;
if (num != 0L)
{
long num2 = Divide(b * c2 - b2 * c, num);
long num3 = Divide(a2 * c - a * c2, num);
bool result = IsPointOnSegment(ref seg1Src, ref seg1Vec, num2, num3) && IsPointOnSegment(ref seg2Src, ref seg2Vec, num2, num3);
interPoint.x = (int)num2;
interPoint.y = (int)num3;
return result;
}
interPoint = VInt2.zero;
return false;
}
public static bool PointInPolygon(ref VInt2 pnt, VInt2[] plg)
{
if (plg == null || plg.Length < 3)
{
return false;
}
bool flag = false;
int num = 0;
int num2 = plg.Length - 1;
while (num < plg.Length)
{
VInt2 vInt = plg[num];
VInt2 vInt2 = plg[num2];
if ((vInt.y <= pnt.y && pnt.y < vInt2.y) || (vInt2.y <= pnt.y && pnt.y < vInt.y))
{
int num3 = vInt2.y - vInt.y;
long num4 = (long)(pnt.y - vInt.y) * (long)(vInt2.x - vInt.x) - (long)(pnt.x - vInt.x) * (long)num3;
if (num3 > 0)
{
if (num4 > 0)
{
flag = !flag;
}
}
else if (num4 < 0)
{
flag = !flag;
}
}
num2 = num++;
}
return flag;
}
public static bool SegIntersectPlg(ref VInt2 segSrc, ref VInt2 segVec, VInt2[] plg, out VInt2 nearPoint, out VInt2 projectVec)
{
nearPoint = VInt2.zero;
projectVec = VInt2.zero;
if (plg == null || plg.Length < 2)
{
return false;
}
bool result = false;
long num = -1L;
int num2 = -1;
for (int i = 0; i < plg.Length; i++)
{
VInt2 seg2Vec = plg[(i + 1) % plg.Length] - plg[i];
if (IntersectSegment(ref segSrc, ref segVec, ref plg[i], ref seg2Vec, out var interPoint))
{
long sqrMagnitudeLong = (interPoint - segSrc).sqrMagnitudeLong;
if (num < 0 || sqrMagnitudeLong < num)
{
nearPoint = interPoint;
num = sqrMagnitudeLong;
num2 = i;
result = true;
}
}
}
if (num2 >= 0)
{
VInt2 vInt = plg[(num2 + 1) % plg.Length] - plg[num2];
VInt2 vInt2 = segSrc + segVec - nearPoint;
long num3 = (long)vInt2.x * (long)vInt.x + (long)vInt2.y * (long)vInt.y;
if (num3 < 0)
{
num3 = -num3;
vInt = -vInt;
}
long sqrMagnitudeLong2 = vInt.sqrMagnitudeLong;
projectVec.x = (int)Divide(vInt.x * num3, sqrMagnitudeLong2);
projectVec.y = (int)Divide(vInt.y * num3, sqrMagnitudeLong2);
}
return result;
}