疫情隔離的日子里重新開(kāi)始看recast項(xiàng)目的代碼恒界。本篇對(duì)項(xiàng)目中一些相對(duì)奇怪的代碼片段做一個(gè)總結(jié)
代碼1：獲取不小于參數(shù)v的最小的2的整數(shù)次冪
例如：
輸入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;
}
原理：
如果一個(gè)數(shù)不是2的整數(shù)次冪实蓬，比如13(二進(jìn)制1101)融师，
a.先把它的從最高位的1向下的所有位都補(bǔ)為1(得到1111)
b.再加1现诀，就得到了想要的值(10000)
那么如何把所有位都補(bǔ)為1呢匣砖？
首先每個(gè)數(shù)總有一個(gè)最高位為1磺箕，把這個(gè)1復(fù)制一份放到右邊搂捧，就得到了兩個(gè)相鄰的1卵贱。把這兩個(gè)1復(fù)制一份再放到右邊滥沫，就得到了4個(gè)相鄰的1侣集。以此類推。而對(duì)于32位整數(shù)來(lái)說(shuō)兰绣，只要重復(fù)執(zhí)行5次就足夠處理所有情況了世分。
以100000為例
100000->110000->111100->111111
對(duì)于本身就是2的整數(shù)次冪的數(shù)來(lái)說(shuō)，把它先減1狭魂，就可以和上面的情況統(tǒng)一起來(lái)了
代碼2：獲取參數(shù)v取2為底的對(duì)數(shù)的整數(shù)部分
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;
}
原理：其實(shí)就是找到最高位的1罚攀，二分法
對(duì)于0~0xffffffff的數(shù)來(lái)說(shuō)
先跟0xffff比，如果大于雌澄，則至log2之后至少為1<<4斋泄，剩下的看左半邊就行；如果不大于镐牺，則左半邊全是0炫掐，只要看右半邊就行
這樣就把一個(gè)32位的問(wèn)題退化到了一個(gè)16位的問(wèn)題。以此類推睬涧，累計(jì)求值得到結(jié)果募胃。
以上兩個(gè)函數(shù)配合使用，可以求出要表示一個(gè)數(shù)值畦浓，至少需要多少二進(jìn)制位
m_tileBits = dtIlog2(dtNextPow2((unsigned int)params->maxTiles));
代碼3：將參數(shù)x對(duì)齊到它最接近的4的整數(shù)倍
例如：
輸入0得到0
輸入1得到4
輸入5得到8
輸入9得到12
inline int dtAlign4(int x) { return (x+3) & ~3; }
代碼4：得到某個(gè)編號(hào)在8鄰域中對(duì)位的編號(hào)
對(duì)應(yīng)關(guān)系：
0-4
1-5
2-6
3-7
inline int dtOppositeTile(int side) { return (side+4) & 0x7; }
代碼5：將3維坐標(biāo)hash映射到1<<12的范圍內(nèi)
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]之間的隨機(jī)數(shù)（近似隨機(jī)）痹束，用來(lái)做采樣抖動(dòng)
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：對(duì)32位整數(shù)做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;
}
