針對大規模應用的歐拉-拉格朗日組合數據表示方法

作者：Jiang Zhang

在科學應用中，模擬的數據輸出形式主要有兩種。一種是歐拉表示，也就是通常說的體數據，在固定的格點上記錄數據信息，不過對於格點之間的區域往往需要插值。另一種是拉格朗日表示，即粒子數據，記錄了離散粒子在數據場內的運動，其缺點是在一些感興趣的區域可能沒有粒子出現。在傳統方法里，這兩種數據表示形式在不同的分析任務中往往是獨立存儲和訪問的。 為了提高計算效率，我們需要一種將兩者進行結合的高效的組合表示形式。這篇文章[1]針對這一問題提出了一種歐拉-拉格朗日聯合表示方法，可以對兩種形式的原始模擬輸出數據同時進行重組織，提高了數據載入和一些基本數據操作的效率。

圖1 歐拉-拉格朗日的組合數據表示方法的主要部分

如圖1所示，該方法在預處理階段將原始的體數據和粒子數據組織成歐拉-拉格朗日單元的格式。基於這種數據結構，作者開發了一系列數據分析操作工具，例如條件查詢，不同數據形式的轉換，缺失時間步插值，以及軌跡的構建等。除此之外，該數據結構還可用於高效地對大規模數據進行多解析度子集的採樣。接下來會對這些內容一一介紹。

圖2 (a) 單獨的歐拉格點和拉格朗日粒子. (b) 歐拉-拉格朗日的組合數據形式

歐拉-拉格朗日單元是一種組合數據結構。在每個單元中，歐拉信息包含了格點的位置，相關的標量或矢量值，以及一系列鄰接格點，拉格朗日信息包含了一系列指向每個粒子的向量，以及該粒子的ID和標量或矢量值。圖2(a)展示了兩種數據形式，其中黑色的實心圓表示格點，紅色表示粒子。圖2(a)將兩種數據形式組織成了組合單元，每個單元由其中心的格點和指向該格點的若干粒子組成。

圖3 組合單元在硬碟中的存儲形式

這種組合單元在硬碟中的存儲形式如圖3所示，主要包含兩個方面。一個是歐拉位置信息，包括格點位置，每個格點的一系列鄰接格點，以及一個幫助索引文件（用於記錄鄰接格點的數目信息），這三種信息都是單獨存放在不同的文件。另一個是時變數據信息，按照時間步組織存儲。在每個時間步里，每個歐拉變數，拉格朗日向量，以及每個拉格朗日變數，都被單獨存儲在不同的文件。除此之外，也有一個幫助索引文件，用於記錄起始讀位置和每個單元的粒子樹目。

圖4 組合單元在內存中的組織形式

當組合單元被讀取到內存中時，數據會被組織成更緊密的塊，如圖4所示。具體來講，內存中的每個塊保存了單元的基本信息，包括格點位置和歐拉變數，相關聯的粒子數目，以及鄰接格點。幫助索引此時變成了指向粒子（包括其位置向量和拉格朗日變數）的指針和指向鄰接格點索引的指針。

圖5 基於歐拉信息的條件組合單元查詢示例

基於這種組合數據結構，我們可以進行一些基礎的數據操作。第一種是條件查詢，可以根據歐拉或拉格朗日的查詢條件去匹配滿足要求的單元並載入到內存中。圖5給出了一個例子，通過設置查詢條件（歐拉變數值比較高），可以將符合要求的單元，包括歐拉格點和拉格朗日粒子，逐一搜索出來並以可視化的方式呈現出來。第二種是兩種形式之間的轉換。我們可以將拉格朗日變數映射到歐拉格點上，也可以將歐拉數據值映射到拉格朗日粒子上。第三種是針對體數據和粒子數據時間解析度不一致時，在缺失的時間步上利用已有時間步上的歐拉變數／拉格朗日變數進行插值。最後一種是粒子軌跡的構建，需要檢索單元以從中找到ID相同的粒子。

圖6 基於固定比率(unbiased sampling)和固定數目(biased sampling)的採樣方法示例

此外，對於大規模數據，我們可以從中採樣出多解析度的數據子集。這主要是針對粒子數據過大造成視覺遮擋的問題。採樣方法有兩種，一種是在每個單元里採樣固定比率的粒子，另一種是在每個單元里採樣固定數目的粒子。前一種方法保留了數據域每個部分的相對粒子密度，後一種方法則突出了歐拉格點密度高的區域的粒子密度（因為非結構化數據的感興趣區域往往是格點密集的地方），如圖6所示例子。

圖7 組合結構和八叉樹以及k-d樹的預處理時間的對比

圖7展示了這種組合結構和八叉樹以及k-d樹的預處理時間的對比。可以看到，歐拉-拉格朗日組合結構花費了更多的時間，這是因為其預處理涵蓋了將粒子和格點相關聯的這部分計算。在後面的數據操作中，通過圖8可以看到，組合結構相比於八叉樹和k-d樹，其效率基本上都有了很大的提高。這也證明了該結構在不同數據操作中的有效性。

圖8 不同方法數據操作時間花費的對比

通過以上介紹可以看到，這種歐拉-拉格朗日組合結構就是將模擬輸出的體數據和粒子數據在存儲和讀入時結合到了一起，支持快速易用的數據載入和操作。雖然犧牲了更多的時間用於預處理，在不同的數據分析任務中還是提高了效率。實際上，可視化中經常會碰到多源或者異構的數據，當我們需要一起進行分析時，可以像這篇文章一樣，將它們更好地組織起來，能夠節省我們在數據可視化和探索時的時間等開銷。

End.

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！