疫情隔离的日子里重新开始看recast项目的代码。本篇对项目中一些相对奇怪的代码片段做一个总结
代码1：获取不小于参数v的最小的2的整数次幂
例如：
输入1输出1
输入3输出4
输入5输出8
inline unsigned int nextPow2(unsigned int v)
{
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
return v;
}
原理：
如果一个数不是2的整数次幂，比如13(二进制1101)，
a.先把它的从最高位的1向下的所有位都补为1(得到1111)
b.再加1，就得到了想要的值(10000)
那么如何把所有位都补为1呢？
首先每个数总有一个最高位为1，把这个1复制一份放到右边，就得到了两个相邻的1。把这两个1复制一份再放到右边，就得到了4个相邻的1。以此类推。而对于32位整数来说，只要重复执行5次就足够处理所有情况了。
以100000为例
100000->110000->111100->111111
对于本身就是2的整数次幂的数来说，把它先减1，就可以和上面的情况统一起来了
代码2：获取参数v取2为底的对数的整数部分
inline unsigned int ilog2(unsigned int v)
{
unsigned int r;
unsigned int shift;
r = (v > 0xffff) << 4; v >>= r;
shift = (v > 0xff) << 3; v >>= shift; r |= shift;
shift = (v > 0xf) << 2; v >>= shift; r |= shift;
shift = (v > 0x3) << 1; v >>= shift; r |= shift;
r |= (v >> 1);
return r;
}
原理：其实就是找到最高位的1，二分法
对于0~0xffffffff的数来说
先跟0xffff比，如果大于，则至log2之后至少为1<<4，剩下的看左半边就行；如果不大于，则左半边全是0，只要看右半边就行
这样就把一个32位的问题退化到了一个16位的问题。以此类推，累计求值得到结果。
以上两个函数配合使用，可以求出要表示一个数值，至少需要多少二进制位
m_tileBits = dtIlog2(dtNextPow2((unsigned int)params->maxTiles));
代码3：将参数x对齐到它最接近的4的整数倍
例如：
输入0得到0
输入1得到4
输入5得到8
输入9得到12
inline int dtAlign4(int x) { return (x+3) & ~3; }
代码4：得到某个编号在8邻域中对位的编号
对应关系：
0-4
1-5
2-6
3-7
inline int dtOppositeTile(int side) { return (side+4) & 0x7; }
8邻域
代码5：将3维坐标hash映射到1<<12的范围内
static const int VERTEX_BUCKET_COUNT = (1<<12);
inline int computeVertexHash(int x, int y, int z)
{
const unsigned int h1 = 0x8da6b343; // Large multiplicative constants;
const unsigned int h2 = 0xd8163841; // here arbitrarily chosen primes
const unsigned int h3 = 0xcb1ab31f;
unsigned int n = h1 * x + h2 * y + h3 * z;
return (int)(n & (VERTEX_BUCKET_COUNT-1));
}
代码6：获取[-1,1]之间的随机数（近似随机），用来做采样抖动
inline float getJitterX(const int i)
{
return (((i * 0x8da6b343) & 0xffff) / 65535.0f * 2.0f) - 1.0f;
}
inline float getJitterY(const int i)
{
return (((i * 0xd8163841) & 0xffff) / 65535.0f * 2.0f) - 1.0f;
}
代码7：对32位整数做hash映射
inline unsigned int dtHashRef(dtPolyRef a)
{
a += ~(a<<15);
a ^= (a>>10);
a += (a<<3);
a ^= (a>>6);
a += ~(a<<11);
a ^= (a>>16);
return (unsigned int)a;
}
