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

殷存舉 邵小蘭

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

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

殷存舉 邵小蘭

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

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

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

1 結構優(yōu)化

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

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

（2）在結構內適當?shù)刂亟M字段。結構內的相應字段通常按照其自身含義加以分類，但從本質上講應以訪問模式加以分組，以使字段的訪問-存儲過程相吻合。

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

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

基于MIPS平臺的體系結構往往有相應的對齊限制。其中，若定義了下列數(shù)據結構：

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ù)編譯器將會生成如下結果：

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

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

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

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

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

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

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

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

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

下面的示例顯示了結構的劃分過程且不使用鏈接指針。這里，相關代碼用于遍歷結構數(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++;

如果上述基于結構數(shù)組的搜索過程視為核心操作，則應將結構S劃分為高頻受訪字段結構（S1）和低頻受訪字段結構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字段在內存皆呈現(xiàn)連續(xù)排列狀態(tài)，即不再被結構S中的count字段和其他字段分割。因此，最大值value的搜索速度將提高2倍。（除了count字段，如果還能析取出其他低頻受訪字段，搜索速度還有更大的提升空間）。

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

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

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

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

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

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

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

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

3 結論

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

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

[2]宋城虎，閔林，朱琳，等．基于包圍盒和空間分解的碰撞檢測算法[J]．計算機技術與發(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]張應中，范超，羅曉芳．凸多面體連續(xù)碰撞檢測的運動軌跡分離軸算法[J]．計算機輔助設計與圖形學學報，2013，25(1)：7-14．

[6]陸睿，劉卉．基于完全二叉樹BVH的自碰撞檢測算法[J]．計算機應用與軟件，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

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