疫情隔離的日子里重新開始看recast項(xiàng)目的代碼。本篇對項(xiàng)目中一些相對奇怪的代碼片段做一個總結(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;
}

原理：
如果一個數(shù)不是2的整數(shù)次冪，比如13(二進(jìn)制1101)，
a.先把它的從最高位的1向下的所有位都補(bǔ)為1(得到1111)
b.再加1，就得到了想要的值(10000)
那么如何把所有位都補(bǔ)為1呢？
首先每個數(shù)總有一個最高位為1，把這個1復(fù)制一份放到右邊，就得到了兩個相鄰的1。把這兩個1復(fù)制一份再放到右邊，就得到了4個相鄰的1。以此類推。而對于32位整數(shù)來說，只要重復(fù)執(zhí)行5次就足夠處理所有情況了。
以100000為例
100000->110000->111100->111111

對于本身就是2的整數(shù)次冪的數(shù)來說，把它先減1，就可以和上面的情況統(tǒng)一起來了

代碼2：獲取參數(shù)v取2為底的對數(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，二分法
對于0~0xffffffff的數(shù)來說
先跟0xffff比，如果大于，則至log2之后至少為1<<4，剩下的看左半邊就行；如果不大于，則左半邊全是0，只要看右半邊就行
這樣就把一個32位的問題退化到了一個16位的問題。以此類推，累計(jì)求值得到結(jié)果。

以上兩個函數(shù)配合使用，可以求出要表示一個數(shù)值，至少需要多少二進(jìn)制位

m_tileBits = dtIlog2(dtNextPow2((unsigned int)params->maxTiles));

代碼3：將參數(shù)x對齊到它最接近的4的整數(shù)倍

例如：
輸入0得到0
輸入1得到4
輸入5得到8
輸入9得到12

inline int dtAlign4(int x) { return (x+3) & ~3; }

代碼4：得到某個編號在8鄰域中對位的編號

對應(yīng)關(guān)系：
0-4
1-5
2-6
3-7

inline int dtOppositeTile(int side) { return (side+4) & 0x7; }

8鄰域

代碼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ī)），用來做采樣抖動

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位整數(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;
}