殷存舉 邵小蘭

（江蘇聯(lián)合職業(yè)技術(shù)學院常州劉國鈞分院，江蘇 常州 213000）

實時碰撞檢測算法中的數(shù)據(jù)緩存優(yōu)化技術(shù)研究

殷存舉 邵小蘭

（江蘇聯(lián)合職業(yè)技術(shù)學院常州劉國鈞分院，江蘇 常州 213000）

在實時碰撞系統(tǒng)中，數(shù)據(jù)緩存的利用率對性能有極大的影響，本文通過重新設(shè)計算法和數(shù)據(jù)結(jié)構(gòu)，并以一種更具預(yù)測性、線性或部分線性的方式訪問數(shù)據(jù)，有效地改善數(shù)據(jù)局域性特征。達到降低數(shù)據(jù)尺寸、提高空間和時間局域性特征進而提高數(shù)據(jù)緩存利用率的目的。

數(shù)據(jù)緩存；訪問頻率；優(yōu)化；數(shù)據(jù)壓縮

1 結(jié)構(gòu)優(yōu)化

針對數(shù)據(jù)緩存的改進措施，首先考查結(jié)構(gòu)和類的優(yōu)化方案，包括以下三點：

（1）降低結(jié)構(gòu)的整體尺寸。使用恰當?shù)奈粩?shù)表示數(shù)字，從而可降低緩存單元中匹配數(shù)據(jù)量以及結(jié)構(gòu)中相關(guān)字段的內(nèi)存讀取次數(shù)。

（2）在結(jié)構(gòu)內(nèi)適當?shù)刂亟M字段。結(jié)構(gòu)內(nèi)的相應(yīng)字段通常按照其自身含義加以分類，但從本質(zhì)上講應(yīng)以訪問模式加以分組，以使字段的訪問-存儲過程相吻合。

（3）根據(jù)數(shù)據(jù)的使用頻率劃分結(jié)構(gòu)。由于結(jié)構(gòu)內(nèi)部相關(guān)字段的訪問頻率不同，可將那些不經(jīng)常訪問的字段置入單一結(jié)構(gòu)中，從而增加頻繁受訪數(shù)據(jù)緩存間的一致性，特別在該結(jié)構(gòu)是數(shù)組或其他聚合型數(shù)據(jù)結(jié)構(gòu)的某一部分時。

許多平臺上的對齊操作將會迫使編譯器對相關(guān)結(jié)構(gòu)實施填充操作，即N字節(jié)字段將實現(xiàn)N字節(jié)對齊。由于填充結(jié)構(gòu)的對齊尺寸往往是該結(jié)構(gòu)中最大N字節(jié)字段的某一倍數(shù)，因此會浪費一部分內(nèi)存空間。考慮到填充操作，按降序排序成員變量將在一定程度上節(jié)省內(nèi)存空間。另外，某些編譯器會提供相應(yīng)的警告，以助于檢測當前內(nèi)存空間的消耗狀態(tài)。

基于MIPS平臺的體系結(jié)構(gòu)往往有相應(yīng)的對齊限制。其中，若定義了下列數(shù)據(jù)結(jié)構(gòu)：

struct X{

int8 a;

int64 b;

int8 c;

int16 d;

int64 e;

float f;

};

struct Y{

int8 a,pad_a[7];

int64 b;

int8 c,pad_c[1];

int16 d,pad_d[2];

int64 e;

float f,pad_f[1];

};

struct Z{

int64 b;

int64 e;

float f;

int16 d;

int8 a;

int8 c;

};

則多數(shù)編譯器將會生成如下結(jié)果：

Sizeof(X)==40，Sizeof(y)==40，Sizeof(z)==24（這里，假設(shè)float類型為4字節(jié)）。與排序后的結(jié)構(gòu)Z相比，結(jié)構(gòu)X的填充數(shù)據(jù)占據(jù)了全部內(nèi)存空間的40%（如結(jié)構(gòu)Y所示）。其他縮減結(jié)構(gòu)尺寸的相關(guān)方法如下：

（1）從已存儲值可輕易計算得到的數(shù)據(jù)值則不要存儲于結(jié)構(gòu)中，以避免額外的緩存讀取操作。

（2）可能的話，盡量使用小尺寸的整型數(shù)據(jù)。

（3）采用位域表示法而非布爾值。盡量不采用Bool類型的標志變量，可將全部標志封裝至某一位域中。Bool變量的尺寸是依賴于機器環(huán)境的，其范圍從一個字節(jié)至長整型數(shù)據(jù)不等。將多個標志存儲于位格式中，可將所需內(nèi)存空間至少減少至1/8，通常為1/32甚至更少。

（4）采用偏移量而非用于索引數(shù)據(jù)結(jié)構(gòu)的指針。指針通常為4字節(jié)（或更多）固定尺寸變量，而偏移量的尺寸可根據(jù)索引項的數(shù)量產(chǎn)生變化。例如，2字節(jié)偏移量可索引包含216個對象的數(shù)組。

由于緩存失效將導(dǎo)致計算開銷急劇增加，因此必須謹慎處理壓縮/非壓縮數(shù)據(jù)。

需要指出的是，在某些系統(tǒng)結(jié)構(gòu)中，上述方案可能會帶來額外的cpu計算開銷。例如，附加指令要求針對小尺寸整型數(shù)據(jù)或位域中的某一位進行操作。隨著指令運行數(shù)量的增加，緩存壓力也將會隨之增長，進而會逐漸抵消緩存優(yōu)勢。因此，對代碼進行優(yōu)化測試不失為一種較好的解決方案——理想情況下，可對變化前后的代碼分別進行測試，從而采取相應(yīng)的改進方案。

對相關(guān)字段加以記錄實現(xiàn)起來并非易事。在某些情況下，多個字段將存儲于同一緩存單元中，尤其是多個字段被同時訪問時?？疾橄铝星闆r，位置、速度以及加速字段經(jīng)常被同時訪問，因而對其進行合并存儲將會增加執(zhí)行效率。多數(shù)情況下，確定字段的最佳排列方式其過程往往比較復(fù)雜。理想情況下，編譯器將會參考前次運行信息并在后續(xù)編譯過程中自動執(zhí)行相應(yīng)的字段記錄。然而，相應(yīng)的語言標準很可能并不包含字段記錄這一功能，且當前基本不存在相應(yīng)的編譯器能夠支持該優(yōu)化操作。一種較好的字段重組方案是通過訪問函數(shù)間接地獲取結(jié)構(gòu)中的字段。這里，可臨時性地設(shè)置這些函數(shù)，以測試字段的訪問頻率并記錄哪些字段被同時訪問。另外，在某些情況下，對結(jié)構(gòu)進行填充操作將會有效改善程序的計算性能，具體體現(xiàn)為：這將使被訪問的兩個鄰接字段位于同一緩存內(nèi)。

考慮到結(jié)構(gòu)字段的訪問頻率，可將其劃分為兩個不同的獨立結(jié)構(gòu)：高頻被訪問字段結(jié)構(gòu)和低頻被訪問字段結(jié)構(gòu)，應(yīng)分別對其分配內(nèi)存空間并加以存儲。另外，各個高頻字段結(jié)構(gòu)中均嵌入低頻字段結(jié)構(gòu)的鏈接指針。此處，雖然只能對低頻字段結(jié)構(gòu)實現(xiàn)間接訪問并增加了些許計算開銷，但相應(yīng)的主結(jié)構(gòu)（高頻被訪字段結(jié)構(gòu)）將變得更加緊湊，并可實現(xiàn)高效的數(shù)據(jù)緩存。另外，由于結(jié)構(gòu)的訪問方式不同，不必一定采用鏈接指針。例如，使用單獨的索引即可同時訪問高頻被訪字段數(shù)組和低頻被訪字段數(shù)組。

下面的示例顯示了結(jié)構(gòu)的劃分過程且不使用鏈接指針。這里，相關(guān)代碼用于遍歷結(jié)構(gòu)數(shù)組，當某元素具有最大值Value時，則增加該元素的count字段值。

struct S{

int32 value;

int32 count;

...

}elem[1000];

//Find the index of the element with largest value

int index=0;

for(int i=0;int＜1000;i++)

if(elem[i].value＞elem[index].value)index=i;

//Increment the count field of that element

elem[index].count++;

如果上述基于結(jié)構(gòu)數(shù)組的搜索過程視為核心操作，則應(yīng)將結(jié)構(gòu)S劃分為高頻受訪字段結(jié)構(gòu)（S1）和低頻受訪字段結(jié)構(gòu)S2.上述代碼可改寫為：

//Hot fields of S

struct S1{

Int32 value;

}elem1[100];

//Code fields of S

struct S2{

Int32 count;

...

}elem2[1000];

//Find the index of the element with largest value

int index=0;

for(int i=0;int＜1000;i++)

if(elem1[i].value＞elem1[index].value)indexer=i;

//increment the count field of that element

elem2[index].count++;

因此，全部value字段在內(nèi)存皆呈現(xiàn)連續(xù)排列狀態(tài)，即不再被結(jié)構(gòu)S中的count字段和其他字段分割。因此，最大值value的搜索速度將提高2倍。（除了count字段，如果還能析取出其他低頻受訪字段，搜索速度還有更大的提升空間）。

類似于結(jié)構(gòu)的低頻/高頻劃分，編譯器和鏈接器同樣也可以根據(jù)該原理對代碼進行重組，因而可對調(diào)用頻率較低的函數(shù)或部分函數(shù)進行移動，降低調(diào)用函數(shù)-被調(diào)函數(shù)之間的沖突，將會減少指令緩存中的操作次數(shù)。一類優(yōu)化算法則是使用了“軟件著色技術(shù)”這一概念并對代碼（或數(shù)據(jù)）進行排列，進而將受訪頻率較高的數(shù)據(jù)項映射至不同的緩存單元中（各緩存單元可視為彼此不同的顏色值）。但目前為止，還很少有相應(yīng)的編譯器能夠?qū)崿F(xiàn)緩存著色技術(shù)。雖然該方案可實現(xiàn)手工處理，但一旦代碼產(chǎn)生變化，全部過程也需要重新處理。

2 頂點數(shù)據(jù)的量化操作和壓縮操作

針對碰撞檢測代碼，除去數(shù)據(jù)結(jié)構(gòu)自身之外，頂點的表達方式也是十分重要的，因為它們構(gòu)成了數(shù)據(jù)的主要組成部分。雖然頂點的x、y、z值常采用浮點數(shù)加以存儲，但也可對其實施量化操作。例如，可使用3個16位的整型值加以表示。相應(yīng)的量化計算可有效地實現(xiàn)網(wǎng)格頂點的對齊操作，因此須謹慎處理以避免四邊形或其他大型碰撞測試圖元產(chǎn)生共面現(xiàn)象。

在某些情況下，還可以對頂點數(shù)據(jù)實現(xiàn)進一步的編碼。例如，對于小型場景世界，頂點可編碼位32位整型數(shù)據(jù)，其中頂點的x、y值分別占據(jù)11位，z值則包含10位，如圖1所示。

圖1 量化為32位整型數(shù)據(jù)的頂點值

當采用相對于前一頂點的偏移量來表示其他頂點時，頂點數(shù)據(jù)將會占用更少的內(nèi)存空間。例如。在計算由頂點表示的AABB時，可將其中心點作為固定原點，并根據(jù)該原點計算其他頂點的偏移距離。這里，額外開銷僅為采用全精度表示的原點，其他頂點通過較少的幾個數(shù)據(jù)位即可實現(xiàn)。

例如，考查下列5個16位整型隨機頂點：A=（30086，15857，9358），B=（30189，15969，9285），C=（30192，15771，9030），D=（29971，15764，9498），E=（30304，15888，9133）。上述頂點也可以采用基于頂點（30138，15866，9264）的16位偏移量加以表示：（-52，-9，121）、（51，103，21）、（54，-95，-234）、（-162，-102，234），（166，22，-131）這里，量化頂點可采用9位數(shù)值加以存儲，相對于原點格式，這節(jié)省了大量的內(nèi)存空間。

若原點可在頂點間浮動，則還能夠進一步地節(jié)省內(nèi)存空間。亦即，可通過前一頂點計算偏移量，因而能夠有效地實現(xiàn)數(shù)據(jù)壓縮。該方案適用于索引網(wǎng)格，其中，頂點順序可實現(xiàn)隨機混合，這將有助于獲取較好的壓縮率。綜上所述，可對頂點A～E按照D、Ａ、Ｂ、Ｅ、Ｃ這一順序加以重組，首頂點表示為（29971，15764，9498），且后續(xù)頂點分別為（115，93，-113）、（103，112，-100）、（115，-81，-122）、（-112，-117，-73）。因此，頂點分量可采用8位數(shù)據(jù)加以表示。

由于葉節(jié)點中的數(shù)據(jù)一般僅跨越場景世界中的某一小部分，因而空間劃分算法可與量化格式的葉節(jié)點數(shù)據(jù)結(jié)合使用。另外，局部數(shù)據(jù)的量化操作不但可以節(jié)省內(nèi)存空間，還能夠?qū)崿F(xiàn)坐標值的全范圍表示。如果相關(guān)葉節(jié)點數(shù)據(jù)待壓縮后實現(xiàn)緩沖存儲，其額外的壓縮消耗通?？梢苑謹偟姆绞郊右缘窒Ａ钊~節(jié)點數(shù)據(jù)相對于某一原點（該原點表示父節(jié)點的空間位置）實現(xiàn)存儲，則可增加該處理過程的健壯性。此時，相關(guān)計算將圍繞此原點進行，從而可實現(xiàn)較高的精確度。

3 結(jié)論

本文從結(jié)構(gòu)優(yōu)化和頂點數(shù)據(jù)的量化操作和壓縮操作兩個方面論述了如何有效地改善數(shù)據(jù)局域性特征。達到降低數(shù)據(jù)尺寸、提高空間和時間局域性特征，進而提高數(shù)據(jù)緩存利用率的目的。對提高碰撞檢測系統(tǒng)的性能有一定的指導(dǎo)意義。

[1]張國飚，張華，劉滿祿，等．基于空間剖分的碰撞檢測算法研究[J]．計算機工程與應(yīng)用，2014，50(07)：46-49．

[2]宋城虎，閔林，朱琳，等．基于包圍盒和空間分解的碰撞檢測算法[J]．計算機技術(shù)與發(fā)展，2014(01)：57-60．

[3]謝世富，馬立元，劉鵬遠，等．虛擬環(huán)境下運動線纜碰撞檢測算法研究與實現(xiàn)[J]．系統(tǒng)仿真學報，2013，25(8)：1865-1870．

[4]付躍文，梁加紅，李猛，等．基于多智能體粒子群的快速碰撞檢測算法研究[J]．系統(tǒng)仿真學報，201325(8)：1876-1880．

[5]張應(yīng)中，范超，羅曉芳．凸多面體連續(xù)碰撞檢測的運動軌跡分離軸算法[J]．計算機輔助設(shè)計與圖形學學報，2013，25(1)：7-14．

[6]陸睿，劉卉．基于完全二叉樹BVH的自碰撞檢測算法[J]．計算機應(yīng)用與軟件，2012，29(12)：282-285．

Research on Data Cache Optimization of Real-time Collision DetectionAlgorithm

Yin Cunju Shao Xiaolan
（Changzhou Liu Guojun Vocational Technology College,Changzhou 21300,Jiangsu）

In the real-time collision system,data cache utilization rate has a great effect on the performance.This paper redesigns the algorithms and data structures and access to data in a more predictive,linear or partially linear way.It effectively improves data locality characteristics.It achieves to reduce the data size,to improve the spatial and temporal characteristics,and to improve the efficiency of data cache.

data cache;access frequency;optimization;data compression

TP333

A

1008-6609(2016)05-0054-03

殷存舉，男，山東費縣人，碩士，副教授，研究方向：智能信息處理。