使用八叉樹模擬水和煙霧 Simulating Water and Smoke with an Octree Data Structure 論文閱讀筆記

這篇具有很好參考價值的文章主要介紹了使用八叉樹模擬水和煙霧 Simulating Water and Smoke with an Octree Data Structure 論文閱讀筆記。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

原文：

Losasso, Frank, Frédéric Gibou, and Ron Fedkiw. “Simulating water and smoke with an octree data structure.” Acm siggraph 2004 papers. 2004. 457-462.

引言

這篇文章擴展了 [Popinet 2003] 的工作，拓展到表面自由流，并且使得八叉樹不受限制

自適應(yīng)網(wǎng)格劃分的一個缺點是，它的模板不是均勻的，進而導(dǎo)致泊松方程中的系數(shù)矩陣是非對稱的

我覺得他這個模板的意思就是，離散化速度的二階導(dǎo)的這個離散的模板吧
或者說是格式？
比如對于最簡單的均勻網(wǎng)格，對于某一個網(wǎng)格，考慮它的前后左右上下，因為是對稱的，所以只需要三個方向，up right front 三個變量。以自己為中心，自己有一個 center 變量。所以構(gòu)建矩陣的時候，每一個網(wǎng)格都有自己的一套 up = 0 right = 0 front = 0 center = 1。如果上方向是流體，那么 up = -c, center += c。這種模板？

[Popinet 2003] 對于這個非均勻的方程組是使用多級泊松求解器來求解的

但是 [Day et al. 1998] 指出這種方法在處理具有高頻細節(jié)的物體的時候存在問題

這種方法也難以處理界面，比如空氣與水的界面

本身界面的準確表達就是很困難的

[Suss-man et al. 1999] 提出了在界面處涂抹密度的方法（聽起來這個涂抹就是一種混合？）

界面上的波是由壓力差導(dǎo)致的，這種涂抹就是在減小高頻的壓力差，所以會消除細節(jié)

這篇文章堅持使用八叉樹作為自適應(yīng)方法，雖然一般情況下這會導(dǎo)致非均勻的泊松方程組，但是這篇文章使用了特殊的設(shè)計，根據(jù)這種設(shè)計，他們得到的泊松方程仍然是對稱正定的

雖然“使用了特殊的設(shè)計”并不是它的原話，但是我覺得他是這個意思？

以往的工作

求解 NS 方程，半拉格朗日求解平流，火、云、粒子爆炸、粘性流、氣泡和表面張力、水花和泡沫

SPH

八叉樹上的 SDF

SDF 的重新初始化

速度外推

半拉格朗日法求解水平集可能耗散比較大，導(dǎo)致質(zhì)量損失嚴重

粒子水平集法的耗散可能更少

使用四叉樹的水平集演化

但是這些研究都沒有考慮到水的界面

水的界面，不就是水平集的一個應(yīng)用嗎？有點不理解

自適應(yīng)網(wǎng)格細化 adaptive mesh refinement (AMR) 通常使用多個不同分辨率的網(wǎng)格，重疊在一起

一開始這是為了研究激波的，所以塊狀結(jié)構(gòu)能夠減少切換網(wǎng)格層次所帶來的偽激波反射

但是，如果不考慮激波，那么就可以使用不受限的八叉樹

這里講的是它的靈感來源？

八叉樹

壓強存儲在格子中心，速度存儲在面上（MAC 網(wǎng)格），其他標量存儲在格子節(jié)點

他說使用節(jié)點存儲標量很方便，因為它的插值方便（我怎么不覺得）

使用八叉樹模擬水和煙霧 Simulating Water and Smoke with an Octree Data Structure 論文閱讀筆記,Fluid Simulation,筆記

粗粒化是把小單元合并成大單元

在這個過程中，節(jié)點中的舊值，要么被刪除，要么保持不變；面上的舊值經(jīng)過平均賦給新值

我一開始想，這里講的“節(jié)點中的舊值”，包不包括網(wǎng)格中心上的值？

使用八叉樹模擬水和煙霧 Simulating Water and Smoke with an Octree Data Structure 論文閱讀筆記,Fluid Simulation,筆記

畫了一下，八個塊變成一個塊，最后的大塊的中心的那個壓強應(yīng)該是平均來的才對，之前那個位置是存別的標量的頂點的位置……所以他指的“節(jié)點中的舊值”應(yīng)該是不包括網(wǎng)格中心的值

那他這里就說少了一個情況啊……算了

細化是從一個大單元細分成多個小單元。邊的半點上的值來自兩端頂點的平均值，面中心的頂點的新值來源于這個面的四個角點的平均值。細分后的面上的速度，是來源于細分后的頂點上的速度的平均。而細分后的頂點上的速度，來源于他周圍四個細分前的面的平均。

這個"細分前"、"細分后"定語都是我自己加的
我覺得這個細分后的頂點上的速度的來源很奇怪啊，不是所有細分后的頂點都是周圍四個面，也有周圍兩個面的。那對于這個兩個面的，是不是只是兩個面的速度的平均？
下面是我畫的，獲得細分后的頂點上的速度的兩種情況的示意圖

使用八叉樹模擬水和煙霧 Simulating Water and Smoke with an Octree Data Structure 論文閱讀筆記,Fluid Simulation,筆記

對于所有變量，我們將邊上的 T 形連接節(jié)點約束為從該邊上的鄰居進行線性插值。類似地，面上的 T 形連接節(jié)點被限制為周圍四個角值的平均值。參見，[Westermann et al. 1999]

這個是真的有點難理解，只好機翻了

八叉樹上的 NS 方程

散度算子

泊松方程

$\nabla^2 p = \nabla \cdot u^* / \Delta t$

他把泊松方程應(yīng)用在體積上，得到

$V_{cell} \nabla^2 p =V_{cell} \nabla \cdot u^* / \Delta t$

不知道怎么就這樣直接得到的

或許他是默認，對于整個體積，物理量都是一樣的，所以相當于 $\int 1 dV = V$ ？

然后他說用格林公式，或者說是高斯公式吧？把體積分轉(zhuǎn)換成面積分

這里就是它處理八叉樹的部分了，我猜，不同分辨率的網(wǎng)格的相接可以轉(zhuǎn)換為一個大的網(wǎng)格面和多個小的網(wǎng)格面的重疊，這樣的情況？

現(xiàn)在等式左右兩個都可以這么轉(zhuǎn)換。只看對于速度散度的轉(zhuǎn)換，相等于考慮一個散度算子。轉(zhuǎn)換成面積分的話，只有垂直于面的分量才有效，所以速度乘以了一個法向量

然后我猜他是要強調(diào)處理一個大面和多個小面的重疊，所以才不寫成 $(u_{face} \cdot n) A_{face}$

而是寫成求和的形式

$V_{cell} \nabla \cdot u^* = \sum_{faces} (u_{face} \cdot n) A_{face}$

重新看他畫的網(wǎng)格

使用八叉樹模擬水和煙霧 Simulating Water and Smoke with an Octree Data Structure 論文閱讀筆記,Fluid Simulation,筆記

后面他印證了我的想法，這么寫就是為了適應(yīng)一個面和多個小面重疊的情況

使用八叉樹模擬水和煙霧 Simulating Water and Smoke with an Octree Data Structure 論文閱讀筆記,Fluid Simulation,筆記

然后導(dǎo)數(shù)就可以把大面和小面聯(lián)系起來，真的很奇妙，雖然從泰勒展開的直接上是消掉了常數(shù)項，但是不知道為什么就這么直接得到了

然后壓強的拉普拉斯算子的轉(zhuǎn)換到面積分的過程，只是在壓力梯度上套用散度算子

使用八叉樹模擬水和煙霧 Simulating Water and Smoke with an Octree Data Structure 論文閱讀筆記,Fluid Simulation,筆記

壓力梯度

使用八叉樹模擬水和煙霧 Simulating Water and Smoke with an Octree Data Structure 論文閱讀筆記,Fluid Simulation,筆記

如果是兩個大小相同的，那么就是壓強梯度 py

如果是為了在網(wǎng)格 1 和 2 之間的話，那么首先在 p1 和 p10 之間插值得到 pa，然后在 pa 和 p2 之間得到壓強梯度 px hat

但是 px hat 不在面上，所以可能會采用更加復(fù)雜的離散化的方法，比如使用 pa p2 p6 來構(gòu)造壓強梯度，例如 [Chen et al. 1997]

但是這種復(fù)雜的離散化方法就導(dǎo)致了泊松方程的非對稱性

因為 1 和 2 之間的壓強梯度會依賴于 p10 和 p6，這就是明顯網(wǎng)格 1 依賴于某一個方向上的壓強了。相反地，網(wǎng)格 6 不太可能依賴于網(wǎng)格 1，因為網(wǎng)格 6 已經(jīng)和一個相等大小的網(wǎng)格 2 并列了。即使依賴了，也不會對稱

之后感覺是精華的部分，就是他為了消除這種依賴，進而得到對稱的結(jié)構(gòu)所做的事

之前說 px hat 不在面上，所以采用了更加復(fù)雜的離散化措施，這是一個導(dǎo)致不對稱性的原因。所以現(xiàn)在他就干脆不用復(fù)雜的離散化措施，就直接令 px hat 代表面上的壓強梯度，也就是網(wǎng)格 1 與網(wǎng)格 2 之間的壓強梯度

然后不對稱性的第二個原因是 pa 由 p1 和 p6 插值，會依賴 p6。那么他就直接令 pa = p1，不要這個插值了

經(jīng)過這一通化簡，計算網(wǎng)格 1 和網(wǎng)格 2 之間的壓強梯度就只用到網(wǎng)格 1 和 2 的壓強了

他這里就認為，引入了 $O(\Delta x)$ 級別的誤差是可以接受的

那么現(xiàn)在網(wǎng)格 1 和網(wǎng)格 2 之間是對稱的了

現(xiàn)在泊松方程組就是對稱的了

準確度

他認為半拉格朗日平流是一階，現(xiàn)在壓強求解是一階，也只是兩個的精度相同

但是它的測試是精度還是挺好的

煙霧

水

總結(jié)

后面的都無關(guān)緊要了

總之他這個文章的核心就是，現(xiàn)在八叉樹的兩個網(wǎng)格就只考慮彼此，暴力忽略其他網(wǎng)格，就這么得到了對稱的模板

忽然發(fā)現(xiàn)稱為模板隱含著一個很優(yōu)雅的事情，就是它可以包括某個點是流體或者是固體的情況

這樣，我們只需要最后討論一下邊界條件怎么放進來就好了，一開始推公式的時候就不用想邊界

好酷啊

使用八叉樹模擬水和煙霧 Simulating Water and Smoke with an Octree Data Structure 論文閱讀筆記,Fluid Simulation,筆記

總之好羨慕啊，我現(xiàn)在的心情就跟我第一次看到半拉格朗日平流的 stable fluid 一樣，感覺這么簡單但是有效的東西，他們就能夠研究到，然后發(fā)出來，就很優(yōu)雅，很有應(yīng)用上的美感的這么一件事文章來源地址http://www.zghlxwxcb.cn/news/detail-825343.html

到了這里，關(guān)于使用八叉樹模擬水和煙霧 Simulating Water and Smoke with an Octree Data Structure 論文閱讀筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！