【摘要】：礦井水災(zāi)是煤礦地質(zhì)災(zāi)害的重要方面,它嚴重影響著煤礦的安全生產(chǎn),并對工作人員的生命安全造成威脅。隨著計算機軟硬件的發(fā)展以及GPU技術(shù)的興起,計算機圖形學(xué)得到了快速發(fā)展。隨著3D模擬的廣泛應(yīng)用,自然景物模擬也已經(jīng)成為圖形學(xué)領(lǐng)域的研究熱點之一,如對煙、河流、云霧等流體的模擬已經(jīng)成為了具有挑戰(zhàn)性的研究課題。本文是基于SPH方法的流體模擬,將模擬區(qū)域化為一系列攜帶某一特定材料屬性的粒子,利用每個粒子的運動確定整體的運動形態(tài),所有粒子的運動都可以通過其支持域內(nèi)的全部粒子的運動屬性加權(quán)得到,并且在每個時間步(整個模擬時間可劃分為若干個時間步)內(nèi)需要對每個粒子的鄰近粒子進行搜索,從而確定粒子在當(dāng)前時間及下一個時間步的運動屬性。因此,在整個模擬過程中,鄰近粒子搜索算法對系統(tǒng)的運行效率起著決定性作用。本文從縮小鄰域搜索范圍的角度對鄰近粒子搜索算法進行優(yōu)化,以達到更快、更準的搜索到鄰近粒子的目的。首先介紹了直接鄰域搜索算法,鏈表搜索算法,樹形搜索算法的基本原理,然后對鄰域搜索算法提出了改進。改進后的搜索算法通過確定粒子周圍區(qū)域來縮小搜索范圍。因為粒子的運動只受鄰域粒子的影響,所以我們對上一時間步的信息進行存儲,根據(jù)上一步的信息確定本時間步的搜索范圍,從而獲得鄰域粒子。然后基于N-S方程,使用SPH方法建立礦井水災(zāi)模型,并對模型數(shù)據(jù)進行解算。最后使用Unity3D虛幻引擎進行仿真實驗。在外部TXT文件中設(shè)置粒子的初始信息,包括粒子的初始位置、數(shù)量、顏色、材質(zhì)等,利用Unity3D的外部數(shù)據(jù)讀取接口,讀取粒子信息,創(chuàng)建水滴粒子并進行初始化。建立Obi Emmiter腳本并提供鄰域粒子搜索算法的封裝接口 Fluid Phase,對Fluid Phase進行賦值,選擇不同的鄰域粒子搜索算法進行仿真實驗,使用SPH方法進行解算,將解算結(jié)果進行存儲,并對粒子屬性進行賦值,最后使用時間步積分,更新粒子每個時刻的狀態(tài),從而實現(xiàn)整體的水災(zāi)蔓延效果。最后對使用不同鄰域搜索算法的仿真實驗數(shù)據(jù)進行分析,得出改進搜索算法可以提高系統(tǒng)的運行效率。
【學(xué)位授予單位】：山東科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP301.6;TD745
【圖文】：

邐ｍ＾逡逑圖２．１直接搜索算法思路圖逡逑Ｆｉｇ２．１邋Ｄｉｒｅｃｔ邋ｓｅａｒｃｈ邋ａｌｇｏｒｉｔｈｍ逡逑直接搜索算法的數(shù)據(jù)結(jié)構(gòu)和基本原理很容易理解，在內(nèi)存中的操作流程如圖逡逑２．２所示：逡逑粒子邐粒子邐粒子邋邐邋粒子Ｎ逡逑索粒子邐粒子邐粒子邋邐邋粒子Ｎ逡逑圖２．２直接搜索算法遍歷思想逡逑Ｆｉｇ２．２邋Ｐｒｉｎｃｉｐｌｅ邋ｏｆ邋ｄｉｒｅｃｔ邋ｓｅａｒｃｈ邋ａｌｇｏｒｉｔｈｍ逡逑２．１．２直接搜索算法分析逡逑直接搜索算法的本質(zhì)是對支持域內(nèi)的所有粒子進行遍歷，在遍歷的過程中獲逡逑取粒子的屬性信息。分析上圖可知，當(dāng)搜索粒子１的鄰近粒子時，需要遍歷除了逡逑粒子１以外的所有粒子，然后計算這些粒子到粒子１的距離，并與粒子１的支持逡逑域半徑的大小比較，將距離小于粒子１支持域半徑的粒子篩選出來。使用這種方逡逑法可以求出支持域內(nèi)每個粒子的鄰近粒子。這種方法可以將支持域內(nèi)的粒子全部逡逑搜索到，但是每一步都需要進行重復(fù)搜索，假設(shè)支持域內(nèi)有Ｍ個粒子，那么就逡逑需要遍歷Ｍ（Ｍ邋－邋１）次才能將這些粒子的鄰域粒子全部獲取到，由此可以得到時逡逑間復(fù)雜度為0（ｍ２）

邐邋粒子Ｎ逡逑圖２．２直接搜索算法遍歷思想逡逑Ｆｉｇ２．２邋Ｐｒｉｎｃｉｐｌｅ邋ｏｆ邋ｄｉｒｅｃｔ邋ｓｅａｒｃｈ邋ａｌｇｏｒｉｔｈｍ逡逑２．１．２直接搜索算法分析逡逑直接搜索算法的本質(zhì)是對支持域內(nèi)的所有粒子進行遍歷，在遍歷的過程中獲逡逑取粒子的屬性信息。分析上圖可知，當(dāng)搜索粒子１的鄰近粒子時，需要遍歷除了逡逑粒子１以外的所有粒子，然后計算這些粒子到粒子１的距離，并與粒子１的支持逡逑域半徑的大小比較，將距離小于粒子１支持域半徑的粒子篩選出來。使用這種方逡逑法可以求出支持域內(nèi)每個粒子的鄰近粒子。這種方法可以將支持域內(nèi)的粒子全部逡逑搜索到，但是每一步都需要進行重復(fù)搜索，假設(shè)支持域內(nèi)有Ｍ個粒子，那么就逡逑需要遍歷Ｍ（Ｍ邋－邋１）次才能將這些粒子的鄰域粒子全部獲取到，由此可以得到時逡逑間復(fù)雜度為0（ｍ２），如果粒子數(shù)量過多，那么時間耗費就更大，效率較低，因逡逑此這種方法只適合粒子數(shù)量較少的情況。逡逑２．２鏈表搜索算法逡逑鏈表搜索算法的基本原理是在支持域內(nèi)建立一個靜態(tài)的網(wǎng)格

只需要對粒子周圍的２７個網(wǎng)格進行搜索，鏈表搜索算法與直接搜索算法相逡逑比，明顯可以縮短搜索時間，但是它的準確性不如直接搜索算法［４２］，其基本思想逡逑如圖２．３所示：逡逑Ｑ邋？邐｜邐0邋！邋0逡逑？邋ｔ邋0邋１邋ｍｒｍ逡逑邐｜＿＿%肌懾危懾危懾五義�？邋ｉ�

本文編號：2748214