分子動(dòng)力學(xué)模擬中通用索引方法及其應(yīng)用

分子動(dòng)力學(xué)模擬中的通用索引方法及應(yīng)1引分子動(dòng)力學(xué)模擬中的通用索引方法及應(yīng)1引不同分法不同分法2通用索直觀想法與直觀算法的直接對應(yīng)，改變了傳統(tǒng)的直觀想法對應(yīng)不直觀算法的格局，有利于序?qū)崿F(xiàn)。考慮完整性，本節(jié)首先介紹目前廣直觀想法與直觀算法的直接對應(yīng)，改變了傳統(tǒng)的直觀想法對應(yīng)不直觀算法的格局，有利于序?qū)崿F(xiàn)?？紤]完整性，本節(jié)首先介紹目前廣泛采用的背景網(wǎng)格索引，然后介紹空間多級樹據(jù)結(jié)構(gòu)以及基于空間多級樹的快速搜索索引方法方法如有限元計(jì)算中常用的連接關(guān)表方法不適合整體動(dòng)態(tài)計(jì)算，在這里不再介紹背景網(wǎng)格索對于點(diǎn)物體或尺寸均勻的小物體果其空間分布不是特別適合用背景網(wǎng)行索引。這種方法廣泛用于分子動(dòng)力學(xué)、隨機(jī)模擬方法（MC、光滑粒子動(dòng)力學(xué)（SPH、質(zhì)點(diǎn)(MPM)、離散元方法中用來搜索緊鄰分子、粒子、物體。對于每個(gè)物體，可以給定一點(diǎn)作為這個(gè)物體的代表位置，一般選這個(gè)物體的中心或特征點(diǎn)。這樣，每個(gè)物體都可用空的點(diǎn)來定位背景網(wǎng)格索引[6]的思路是：根據(jù)空間所有物體的位置設(shè)定一個(gè)箱子能夠存放這些物將這個(gè)箱子按照長、寬及高分成規(guī)則的小箱子，將物體根據(jù)其空間位置放入相應(yīng)的小箱中。這樣就對空間物體建立了一種索引。在搜索物體時(shí)，根據(jù)搜索條件選擇合適的幾個(gè)小網(wǎng)格，搜索圓區(qū)域中的物體時(shí)，不用全部搜索，僅需計(jì)算與圓區(qū)域重疊的有哪些網(wǎng)格（粗框綠色矩形進(jìn)入這些網(wǎng)格搜索這些網(wǎng)格內(nèi)的物體即可圖 物體的背景網(wǎng)格索引示意建立背景網(wǎng)格索引時(shí)，由于對進(jìn)入網(wǎng)格的物體可以用數(shù)組保存，因此需要設(shè)計(jì)數(shù)組小，當(dāng)物體在空間分布不均勻時(shí)會浪費(fèi)內(nèi)存。更方便的方法是采用鏈表,如圖2所示。建背景網(wǎng)格索引的算法如下(以二維空間為例圖 背景網(wǎng)格上的物體鏈表示小，當(dāng)物體在空間分布不均勻時(shí)會浪費(fèi)內(nèi)存。更方便的方法是采用鏈表,如圖2所示。建背景網(wǎng)格索引的算法如下(以二維空間為例圖 背景網(wǎng)格上的物體鏈表示意⑴根據(jù)搜索要求設(shè)定網(wǎng)格尺寸⑵檢查空間物體確定系統(tǒng)尺寸(x0,x1(y0,y1x0y1y01計(jì)算網(wǎng)格數(shù)組大小(I,J)，其中I1，⑶動(dòng)態(tài)開設(shè)網(wǎng)格數(shù)組⑷對每個(gè)物體A，根據(jù)其空間位置(xA,yA)計(jì)算其所屬的網(wǎng)格單元(i,j)，其xAx0yAy0ij將這個(gè)物體從鏈表尾部插入到此網(wǎng)格單元的鏈表中，如圖3所示，其中紅色圓點(diǎn)表物體所在網(wǎng)格單元格點(diǎn)g(i,j)，藍(lán)色圓點(diǎn)代表物體Ag(i,j)obj代表格單元格點(diǎn)指向的物體。具體插入步驟分兩步，如下Anextg(i,j)objg(i,j)objA圖 將物體插入網(wǎng)格鏈表的示意圖，（a）插入鏈表前，（b）插入鏈表搜索給定區(qū)域內(nèi)物體的算法如下⑴計(jì)算與給定搜索區(qū)域重疊的圖 將物體插入網(wǎng)格鏈表的示意圖，（a）插入鏈表前，（b）插入鏈表搜索給定區(qū)域內(nèi)物體的算法如下⑴計(jì)算與給定搜索區(qū)域重疊的網(wǎng)格單元，對這些網(wǎng)格單元循環(huán)⑵對每個(gè)網(wǎng)格單元內(nèi)的物體循環(huán)，查找符合要求的物單元包含的物體數(shù)。背景網(wǎng)格索引的搜索計(jì)算量與關(guān)聯(lián)網(wǎng)格的數(shù)量(Ngrid)和網(wǎng)格平均內(nèi)含N體數(shù)(Nobj)有關(guān)，一般為(Ngrid)，其 1。由于網(wǎng)格單元越大，則關(guān)聯(lián)網(wǎng)格元越少，網(wǎng)格平均內(nèi)含物體數(shù)越多；網(wǎng)格單元越小，則關(guān)聯(lián)網(wǎng)格單元越多，網(wǎng)格平均內(nèi)含體數(shù)越少，同時(shí)隨著網(wǎng)格單元變小，內(nèi)存量會增加，因此需要選擇合理的網(wǎng)格大小從而最程度減小計(jì)算量。一般選擇網(wǎng)格平均內(nèi)含物數(shù)目在3~5之間的背景網(wǎng)格?？梢酝ㄟ^預(yù)先1/x)(y算物體的平均密度給出網(wǎng)格尺寸，例如，二維選擇 N1/x)(yz N，其中為網(wǎng)格平均內(nèi)含物體數(shù)背景網(wǎng)格索引的優(yōu)點(diǎn)在于數(shù)據(jù)結(jié)構(gòu)簡單，在物體尺寸均勻和物體空間分布均勻時(shí)計(jì)（（2）由于物體的尺寸不進(jìn)入索引，當(dāng)物體尺寸不均勻時(shí)，難以支持；（3）維空間或體空間分布極不均勻時(shí)，需要的內(nèi)存量和搜索計(jì)算量很大，代價(jià)很高空間多級樹及通用快速搜空間多級樹及通用快速搜2.2.1空間多級離散點(diǎn)離散點(diǎn)物體的空間多級樹管理區(qū)域示意（a）二維離散點(diǎn)，（b）三維離散點(diǎn)圖圖5空間多級樹管理物體的示意圖。每行的矩形方塊表示枝（左邊框內(nèi)，體，黑色水平虛線箭頭表示屬于同一枝的子枝間的鏈⑴建立樹就是從一個(gè)物體出發(fā)尋找一個(gè)能裝下物體的最?、沤渚褪菑囊粋€(gè)物體出發(fā)尋找一個(gè)能裝下物體的最小枝，其尺寸是最小分辨圖6建立三角形樹示意圖（a）三角形物體，（b）成一個(gè)分辨率為σ的枝，（c）將的變成翻倍到能容納三角形物體，（d）建立的三角形物體樹箭頭代表枝上懸掛的三角“/”代表樹根，灰⑵向樹上添加一個(gè)物體的思路是先擴(kuò)展樹以包含此物體，然后將物體掛到合適的枝上心所在象限產(chǎn)生當(dāng)前枝的干s。將r連接為其子枝，將s設(shè)置為樹根。(b)回到上一步(a)。7A和B為三角形物體，O1識，a是三級子枝的標(biāo)識，B0B7-c（左邊是枝的標(biāo)識，右邊是枝容納的物體圖樹上添加物體示意圖，(a)調(diào)整樹根已容納物體圖樹上添加物體示意圖，(a)調(diào)整樹根已容納物體B，(b)將B物體掛到相應(yīng)子枝，(c)應(yīng)的空間多級樹結(jié)構(gòu)從樹上刪除一個(gè)物體8圖從樹上刪除一個(gè)物體示意圖，(a)找到需刪除物體所在枝a，(b)刪除a枝上物體，(c)除空枝a，(d)刪除空枝I體所在象限，產(chǎn)生當(dāng)前枝的子枝。通過調(diào)用這四個(gè)函數(shù)，對任意空間維數(shù)中任何形狀物體2.2.2SHT的快速搜2.2.2SHT的快速搜條件搜結(jié)束。否則，出棧一枝b;③檢查b的每個(gè)子枝，將子枝中的候選枝入棧；④檢查b掛的物IVAB在圓內(nèi)。這樣,在各級樹枝層次上避免搜索很多樹枝中的物體,速減小.這樣搜索計(jì)算量僅與多級樹的總級別成正比平面三角形分布和空間劃9速減小.這樣搜索計(jì)算量僅與多級樹的總級別成正比平面三角形分布和空間劃9對應(yīng)的空間多級快速搜索圓形區(qū)域中物體的過程極值搜極值搜距離A最近的點(diǎn)。快速搜索不是依次計(jì)算比較中每一點(diǎn)到A距離，而LBBBBo循環(huán):計(jì)算oS，如果比候選值S，oLSS，oLSBZZZZ的上限比L某個(gè)值域枝C的下限小，刪除C后面的所有同級值域枝；如果L中某個(gè)值域枝的上限比Z的下限小，放棄Z，否則將Z插入到鏈表L中。在插入過程中，鏈表L中的值域枝的排序,12平面點(diǎn)分布和空間劃圖 與圖12對應(yīng)的空間多級圖 快速搜索距離A點(diǎn)最近點(diǎn)的過圖 快速搜索距離A點(diǎn)最近點(diǎn)的過程計(jì)算一個(gè)物體的函數(shù)值，用3應(yīng)空間多級樹和基于空間多級樹的快速搜索不僅提供了空間物體集合高效3應(yīng)空間多級樹和基于空間多級樹的快速搜索不僅提供了空間物體集合高效通用的空間引，而且提供了數(shù)據(jù)有效管理手段?；谶@種技術(shù)，大部分應(yīng)用問題都可以用統(tǒng)一計(jì)算框處理。文中將帶有物理屬性的物體稱為物元，比如帶有能量、質(zhì)量、動(dòng)量、角動(dòng)量屬性的子、分子團(tuán)，帶有密度、相成分的顆粒，帶有晶向的晶粒，帶有密度、能量屬性的有限大部分分析問題可以歸結(jié)為從已有的物元集合構(gòu)造另一種具有應(yīng)用要求屬性的其他物元合，例如離散動(dòng)力學(xué)問題可以歸結(jié)為：已有物元集合按照物理規(guī)則演變（物理體屬性改物理體重新再構(gòu)造）的過程。下面將分別介紹通用索引在最短路徑問題、空間剖分、團(tuán)簇構(gòu)分析、原子類型鑒別以及界面構(gòu)造等方面的應(yīng)用最短路徑問最短路徑問題[9]是圖論研究中的一個(gè)經(jīng)典問題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成）中結(jié)點(diǎn)之間的最短路最短路徑不僅僅指一般地理意義上的最短距離引申到其它度量，如時(shí)間、費(fèi)用、線路容量等。最短路徑算法的選擇與實(shí)現(xiàn)是通道路線設(shè)計(jì)的基礎(chǔ)是計(jì)算機(jī)科學(xué)與地址信息科學(xué)等領(lǐng)域的研究熱點(diǎn)，很多網(wǎng)絡(luò)相關(guān)問題都可以納入最短路問題的范疇之中。經(jīng)典的圖論與不斷發(fā)展完善的計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)及算法的有效結(jié)合使得的最短路徑算法不斷涌現(xiàn)郵遞員最短路徑問題是給定N個(gè)城市，尋找一條最短的環(huán)路，可以遍歷這些城市。這代表性的NP問題，因?yàn)樽顑?yōu)的路徑需要比較所有的環(huán)路。最為簡單應(yīng)用實(shí)例，此處給出種近似解稱為迷宮。近似解的算法可以簡單描述為：依次將點(diǎn)加入回路中，將其中一條邊改造為過加入點(diǎn)的兩條邊線，改進(jìn)后回路不自相交，且回路最短，如圖15所示BPA圖采用空間多級樹實(shí)現(xiàn)算法的預(yù)備工作是設(shè)計(jì)快速搜索器。這里提供了包含三個(gè)極值索和一個(gè)條件搜索的設(shè)計(jì)方案，其中，每個(gè)極值搜索需要引入一個(gè)求值函數(shù)和圖采用空間多級樹實(shí)現(xiàn)算法的預(yù)備工作是設(shè)計(jì)快速搜索器。這里提供了包含三個(gè)極值索和一個(gè)條件搜索的設(shè)計(jì)方案，其中，每個(gè)極值搜索需要引入一個(gè)求值函數(shù)和兩個(gè)評估數(shù)，條件搜索需要引入一個(gè)條件函數(shù)和一個(gè)判別函數(shù)⑴極小值快速搜索器MS1：在二維點(diǎn)樹上搜索離給定固定點(diǎn)r0最近的點(diǎn)；求值函數(shù)value(p)rp，評估函數(shù)M(b)m(b)cbmax(cb2db別是枝的值域上、下⑵極小值快速搜索器MS2：在二維點(diǎn)樹上搜索離給定線段AB兩端相連的折線最短點(diǎn)；其求值函數(shù)value(P)rPrP，2db，那么評估函數(shù)形式如下A,BAC，BBC，A22drM(b)b 2drb rrBA，B ， ABA，Bm(b)cr ⑶極小值快速搜索器MS3：給定一點(diǎn)P，在二維線段樹上搜索線段AB，使得它與線端點(diǎn)連接的折線減去原線段得到的值最小。求值函數(shù)為value(AB)rPrPrA;同上，按照枝的外接C評估，圓心為cb,半徑為2db。評估函數(shù)形式如下M(b)2(2dbrPcb，Pm(b)max(c32d P Pm(b)max(c32d P b⑷條件快速搜索器CS1：給定線段AB，在二維線段樹上搜索線段ab，使得它與給定ABxrA1x)rByra1y)rb，得到(xy0x0ycondition(ab)判別函數(shù)如下ABbmaycontain(b)至此，預(yù)備工作完畢。迷宮構(gòu)造算法如下⑴初始用平面上給定離散點(diǎn)構(gòu)造點(diǎn)樹tp；從樹上任意摘下一點(diǎn)P0；用MS1類搜索器在tpP3（P0P1）；構(gòu)造線段P0-P1，用它建立線段樹tl；構(gòu)造線段P1-P2，將其掛在tl上構(gòu)造線段P2-P0，將其掛在樹tl上⑵生成連tp上摘下一個(gè)點(diǎn)P,s；②如果P是空的,結(jié)束程序；③用MS3tlLL1L1LtlLP線并tl上，回到步驟①；如果非空L堆棧s中,回到步驟③16是連40000個(gè)隨機(jī)點(diǎn)構(gòu)造出的迷宮，其中(a)是整體圖，(b)是局域放大圖圖連接40000個(gè)隨機(jī)點(diǎn)構(gòu)造出的迷宮。(a)是整體圖，(b)是局域放圖連接40000個(gè)隨機(jī)點(diǎn)構(gòu)造出的迷宮。(a)是整體圖，(b)是局域放大圖Delaunay剖分的快速構(gòu)造圖 二維Delaunay剖分中加入一個(gè)新的三角形；(b)將這些三角形圖 二維Delaunay剖分中加入一個(gè)新的三角形；(b)將這些三角形的內(nèi)部線掉，保留外界線段；(c)將每一個(gè)外界線與相連，形成新的三角形⑴條件快速搜索CS1：給定點(diǎn)r0，在球接四面體樹上搜索包含此點(diǎn)的球接四面體CTcondition(CT),半徑為maycontain(b)cb ⑵條件快速CS2：給定三個(gè)P1P2P3，在球接四面體樹上搜索以此三點(diǎn)為頂點(diǎn)P1,bCTP2,cCTcondition(CT)maycontain(b)圖二維正方形[0,4]×[0,4]區(qū)域中隨機(jī)分布的離散點(diǎn)構(gòu)造的Delaunay剖分，(b)是中黑色小矩形區(qū)域的局部放大圖三維球型區(qū)域中隨機(jī)分布的離散點(diǎn)構(gòu)造的Delaunay剖nn+1{r1,r2rn1構(gòu)造外接球。球心坐標(biāo)ccAB，球半徑為(c圖三維球型區(qū)域中隨機(jī)分布的離散點(diǎn)構(gòu)造的Delaunay剖nn+1{r1,r2rn1構(gòu)造外接球。球心坐標(biāo)ccAB，球半徑為(cr2。1 2r11112r22，，A Bi210r210rnn0nn10團(tuán)簇構(gòu)造算法及其分析方應(yīng)的空間多級樹為t；②刪除t上所有存在大于分辨率邊長的四面體；構(gòu)造單個(gè)團(tuán)簇：③C->s上。⑤繼續(xù)過程④，直到iC->s上。⑤繼續(xù)過程④，直到i樹為空。構(gòu)造所有團(tuán)簇：⑥將構(gòu)造好的團(tuán)簇C添加到團(tuán)圖二維空間[0,1]×[0,1]區(qū)域中1000個(gè)隨機(jī)離散點(diǎn)計(jì)算得到的團(tuán)簇結(jié)構(gòu)，(a)是團(tuán)簇（b）是相應(yīng)的團(tuán)簇邊圖三維空間中5000個(gè)隨機(jī)離散點(diǎn)計(jì)算得到的團(tuán)簇結(jié)圖三維空間中5000個(gè)隨機(jī)離散點(diǎn)計(jì)算得到的團(tuán)簇結(jié)缺陷原子分3.4.1能量法及對稱參數(shù)3.4.1能量法及對稱參數(shù)s距的2倍，因此球半徑可以選為最緊鄰間距的13.4.2鍵對分析技結(jié)構(gòu)分析的鍵對分析技術(shù)就可以更精密地鑒別缺陷類型。鍵對分析技術(shù)的原理是：根據(jù)兩端原子的間接連接情況標(biāo)志結(jié)構(gòu)分析的鍵對分析技術(shù)就可以更精密地鑒別缺陷類型。鍵對分析技術(shù)的原理是：根據(jù)兩端原子的間接連接情況標(biāo)志鍵類型；根據(jù)一個(gè)原子的所有鍵的類型標(biāo)志原子類型原子間距小于一個(gè)給定尺R（成鍵距離）的兩個(gè)原子之間的連接定義為鍵。這里鍵的概念為了方便敘述借用的化學(xué)中一個(gè)名詞，并沒有電子波函數(shù)交疊等量子化學(xué)的涵。成鍵間距一般選為完整晶格最近間距的 倍。在預(yù)先不知道晶格常數(shù)的情況下，擇徑向分布函數(shù)第一峰對應(yīng)的間距的 倍。這樣選擇使拓?fù)浞治隹梢跃哂幸欢闺S機(jī)擾能力鍵類型標(biāo)鍵類型取決于鍵兩端原子的間接成鍵的特性?？梢詫⑴c這兩個(gè)原子都成鍵的原子選出來，用它們間的連接來標(biāo)識鍵類型具體來講可以用三個(gè)數(shù)字編碼標(biāo)識一個(gè)鍵的類型。設(shè)鍵兩端原子為A,B；與A,B都鍵的原子構(gòu)成一個(gè)集合c。第一c的元素?cái)?shù)目；第二位表示c中原子中成鍵的目；第三位表示c中原子的最大配位數(shù)與A和B原子都成鍵的原子共有4個(gè)（H、I、C、D）4表示這些原子中成鍵的數(shù)DCEABFGIHJKLM圖22鍵類型標(biāo)識的示意完整晶體中鍵的標(biāo)識很容易計(jì)算出來：對于fcc原子中的421；hcp晶體中的鍵661,200,100,311,211,411432542,300,400,原子類型標(biāo),661,200,100,311,211,411432542,300,400,原子類型標(biāo),鍵對分析算rorbrcmaycontain(b)其中，dbb立方體邊長的一半&rprcrc&rprcrcdb&&rbrbrprc其中，dbb立方體邊長的一半分布函數(shù)，根據(jù)徑向分布函數(shù)的第一極大值對應(yīng)的原子間距，給出成鍵距離。a，VCS1tpa（rc的原子）ba-b,CS2tpabrc的原子對mna-b100l+10m+nB的鍵類型比較，如果是新類型，存入鍵類型數(shù)組B，將鍵類型分布矢量V的相應(yīng)的分量上aVAV子類型數(shù)組，記錄a原子類型為V。效果展是在圖采用鍵對分析技術(shù)計(jì)算得到的層錯(cuò)結(jié)構(gòu)和位錯(cuò)結(jié)圖采用鍵對分析技術(shù)計(jì)算得到的層錯(cuò)結(jié)構(gòu)和位錯(cuò)結(jié)圖采用鍵對分析技術(shù)計(jì)算得到的空洞表面和位錯(cuò)結(jié)界面構(gòu)造算 由空間無序點(diǎn)構(gòu)造物體表面的包裹-雕刻算由空間無序點(diǎn)構(gòu)造物體表面是計(jì)算幾何中的重要問題，目前的算法可以分為四類、變形法包裹算⑴極小值搜索器包裹算⑴極小值搜索器圖搜索半面轉(zhuǎn)動(dòng)時(shí)最先遇到value(p)angle(x,其中xx?rPrAyy?rPrA為點(diǎn)的局部坐標(biāo)Pxy(rArBrB?rBPxy(rArBE??為投影算符，E為恒等算符ASorBM(b)，E??為投影算符，E為恒等算符ASorBM(b)，rA,B/Sbb 0ABm(b)max(0,vaule(c)3d/P))A,Brb bcb是b，db⑵條件快速搜索P1,DP2BP1,P2①初始化：P1 圖26包裹算法的初始化過程示意圖。(a)繞P1P2旋轉(zhuǎn)碰到Q1點(diǎn)繞P1P1旋轉(zhuǎn)碰到Q2，(c)繞Q1Q2旋轉(zhuǎn)碰到Q3，(d)初始三角形界②形成P1 圖26包裹算法的初始化過程示意圖。(a)繞P1P2旋轉(zhuǎn)碰到Q1點(diǎn)繞P1P1旋轉(zhuǎn)碰到Q2，(c)繞Q1Q2旋轉(zhuǎn)碰到Q3，(d)初始三角形界②形成包從三角形邊樹tl摘下一個(gè)三角形邊L，L為空，結(jié)束程序，否則找到對應(yīng)的三形。用MS1搜索器在點(diǎn)樹tp上搜索三角形繞L旋轉(zhuǎn)最先碰到的點(diǎn)P,L的頂La、LbP構(gòu)造三角形LbLaP，。LbLaP掛到三角形樹ttCS1搜索器在三角形tb索與PLa共邊的三角形邊，如果找到（見圖27-a）tb上摘下，如果找不到（見圖b）LaP生成三角形邊，掛到三角形邊樹上。對LaP采用同樣操作PPPP圖27兩種情況。(a)LaP不在邊樹上，(b)LaP在邊樹雕刻算雕刻算法涉及到PPPP圖27兩種情況。(a)LaP不在邊樹上，(b)LaP在邊樹雕刻算雕刻算法涉及到雕刻方法和雕刻標(biāo)準(zhǔn)。雕刻過程中要保證沒有點(diǎn)在雕刻時(shí)被雕刻掉而且雕刻后表面盡量光滑。光滑的表面曲率很小，對應(yīng)于雕刻掉的四面體的外接球半徑大。對于待雕刻的三角形ABC來說，雕刻過程意味著尋找當(dāng)前面包圍區(qū)域內(nèi)部點(diǎn)P，使角形頂點(diǎn)ABC和P成的球冠具有最小高度28所示對一個(gè)三角形面來說，雕刻的停止條件是外接球的半徑小于給定值。對于表面均勻樣的物體這個(gè)判據(jù)符合要求，而對于非均勻采樣（曲率大，采樣點(diǎn)密）的表面構(gòu)造，應(yīng)保證曲率與局部采樣點(diǎn)間距相關(guān)。采用球冠高與三角形外接圓的比值，即雕刻ch/判據(jù)比較合適，這個(gè)判據(jù)能同時(shí)適應(yīng)兩種情形。雕刻算法是圖28雕刻算法的原(rrrr (rB圖28雕刻算法的原(rrrr (rBrA)(rCrA(r，n r 給出ABC外接圓半徑r，圓心o，和法線方向n；通過求解方rcro(rr)22 r value(p) 2rb)MMM 2r0m(b)mm，rn2r2 其中，2 obbmP點(diǎn)為Q2點(diǎn)時(shí)，球冠具有最大球冠高M(jìn)(rBrA)(rCrA圖29b枝的外接球與球冠ABCP相切的兩種情況。圖29b枝的外接球與球冠ABCP相切的兩種情況。其中，黑色圓代表b的外接球，藍(lán)色直線代表三角形ABC的外接圓，綠色和紅色圓代表球冠ABCP，Q1和Q2為交點(diǎn)雕刻算法如下tt。設(shè)置雕刻結(jié)束臨界值ccri2.0，設(shè)置界面樹tt0為空。否則，用MS搜索器查找最淺的點(diǎn)p，計(jì)算雕刻度c，判斷是否滿足cccri，如果滿足，不雕刻，將三角形T掛在界面樹tt0上。如果不滿足，將三角形T的每條邊與點(diǎn)p分別③回到步驟②界面tt0上所有的表面構(gòu)成物體的表面算法展30fcc晶體中兩個(gè)納米空洞和一個(gè)點(diǎn)缺陷邊界上的均勻點(diǎn)集由包裹算法給出的殼及雕刻出的表面。圖31是由多連通單個(gè)物體表面隨機(jī)采樣點(diǎn)構(gòu)造出的包裹凸殼和雕刻的表面。圖32是由多個(gè)物體表面隨機(jī)采樣點(diǎn)構(gòu)造出的表面和包裹面圖30包裹-雕刻算法過程，（a）勻離散點(diǎn)（b）包裹過程包圖30包裹-雕刻算法過程，（a）勻離散點(diǎn)（b）包裹過程包裹凸殼(d)雕刻過程(e)表（a）均勻離散點(diǎn)（b）包裹凸殼(e)表圖31由兩個(gè)物體隨機(jī)采樣9000點(diǎn)重構(gòu)的表（a）均勻離散點(diǎn)（b）包裹凸(e)表圖32由一個(gè)復(fù)雜物體隨機(jī)采樣點(diǎn)重構(gòu)的表 滾球法由空間無序點(diǎn)尋找物理區(qū)域界滾球法算⑴構(gòu)造極值搜索器給定定向三角形ABC和 滾球法由空間無序點(diǎn)尋找物理區(qū)域界滾球法算⑴構(gòu)造極值搜索器給定定向三角形ABC和指定的AB，在點(diǎn)樹上搜索三角形上方的半徑為r的球旋轉(zhuǎn)時(shí)遇到的第一個(gè)點(diǎn)。求值函數(shù)構(gòu)造過程如下：計(jì)算初始旋轉(zhuǎn)球的球心位置ro及局rrroAP(rrroA,? ,?r)2，oBr 2roC計(jì)算旋轉(zhuǎn)后的球心位置rn及在局部坐標(biāo)中的坐標(biāo)x,y,z，具體公式Pxy(rorAr2(r r2(rnrB)2，xx?(rnrAr2(r r2(rnrB)2，xx?(rnrA),yy?r2(r value(p)angle(x,y圖33三角形ABC的旋轉(zhuǎn)示評估函數(shù)構(gòu)造過程如下：按照枝的外接球與旋轉(zhuǎn)球（球心在）相切計(jì)算切點(diǎn)位置22,rrrrrr3d 1B b此方程有兩個(gè)根rM1,rm1,對應(yīng)空間兩個(gè)點(diǎn)M1和M(b)三角形外接圓在外接球，其他情m(b)三角形外接圓在外接球其他情綠色和紅色為滾球，M1m1M1旋轉(zhuǎn)后對應(yīng)最小旋轉(zhuǎn)角的滾旋轉(zhuǎn)前的滾旋轉(zhuǎn)旋轉(zhuǎn)后對應(yīng)最大旋轉(zhuǎn)角的滾圖滾球與b的外旋轉(zhuǎn)后對應(yīng)最小旋轉(zhuǎn)角的滾旋轉(zhuǎn)前的滾旋轉(zhuǎn)旋轉(zhuǎn)后對應(yīng)最大旋轉(zhuǎn)角的滾圖滾球與b的外接球相切的兩種情況示意圖，圖中黑色圓點(diǎn)代表旋轉(zhuǎn)軸⑵構(gòu)造極值搜索MS2：給定一個(gè)點(diǎn)，在點(diǎn)樹上搜索離此點(diǎn)最近的點(diǎn)。求值函數(shù)為value(p)，其中rpp的坐標(biāo)；評估函數(shù)為M(b)cb3db,m(b)max(cb 3db,0)其中cbb的中心坐標(biāo)dbb方體半寬⑶構(gòu)造極值搜索MS3：給定一個(gè)點(diǎn)和轉(zhuǎn)軸，在點(diǎn)樹上搜索大小固定的球繞指定轉(zhuǎn)旋轉(zhuǎn)時(shí)遇到的第一個(gè)點(diǎn)。算法與MS1基本相同，此處不再重復(fù)⑷構(gòu)造條件搜索器CS1:給定兩個(gè)p1,p2，在邊樹上搜索對應(yīng)的邊BD，p1和p2的端點(diǎn)。條件函數(shù)為Bp1,Dp2按照枝的外接球S進(jìn)行評估，判別函數(shù)如下 p1,p2滾球法算法如下①初始設(shè)定滾球的半徑，球心初始P0。用給定的離散點(diǎn)構(gòu)造點(diǎn)樹tp;用搜索器MS2搜②滾球法構(gòu)造表面算法效果展圖35由離散空間點(diǎn)構(gòu)造空洞表面效果(a)給定離散點(diǎn)，(b)用滾球法給出圖36由離散空間點(diǎn)構(gòu)造空圖36由離散空間點(diǎn)構(gòu)造空洞表面的空間多級樹通用索引C++類結(jié)構(gòu)及實(shí)數(shù)據(jù)結(jié)構(gòu)利c++面向?qū)ο蟮膬?yōu)勢，根據(jù)通用性要求使類的繼承結(jié)構(gòu)從抽象到具體分呈現(xiàn)，樹的動(dòng)態(tài)構(gòu)造在抽象類中實(shí)現(xiàn)，快速搜索在形式類中實(shí)現(xiàn)。這種處理使得應(yīng)用類的A1空間多級樹圖A-1A1空間多級樹圖A-1樹枝的繼承結(jié)抽象枝類Branchclass{intBranch*father; Branch*son; Branch*brother;Object空間枝類2{Branch2D(intlevel,doublesz,doublexxc,doubleyyc);doublexc,double抽象物體類class{voidbuild(Branch抽象物體類class{voidbuild(Branch*&tree,double //由當(dāng)前物體以dd的分辨率構(gòu)造樹booladd_to(Branch*&Object*next_obj;//virtualBranch*create_branch_include_me(doublemsize)=0//產(chǎn)生一個(gè)尺寸為msize*2m的枝,//以枝b為參考位置，在當(dāng)前物體所在象限位置產(chǎn)生b的干//以枝b在象限位置產(chǎn)生bvirtualboolin_branch(Branch*b)=0；//判斷當(dāng)前物體是否包含于枝b},形式物體類形式物體類的數(shù)據(jù)結(jié)構(gòu)含有空間參數(shù)（位置，尺寸{virtualBranch*create_branch_uplevel(Branch*);virtualBranch*create_branch_uplevel(Branch*);virtualboolin_branch(Branch*);classBody3D:public{Body3D(doublexx,doubleyy,doublezz,doublexs,doubleys,doublezs)；virtualBranch*create_branch_uplevel(Branch*);virtualboolin_branch(Branch*);double形式物體類在實(shí)現(xiàn)四個(gè)虛函數(shù)create_branch_include_me{A2快速搜索class{voidscreen(Objectclass{voidscreen(Object voidObject*search_obj()=0;BranchintObject條件搜索類{virtualObject*search_obj();virtualboolcondition(Object*o)=0;intBranchBranchObject應(yīng)用條件搜索類{virtualboolcondition(Object*o);virtualboolmaycontain{virtualboolcondition(Object*o);virtualboolmaycontain(Branch*b);InCirTet3D_Searcher搜索類中condition函數(shù)判別給定球接四面體是否包含點(diǎn){virtualObject*search_obj();virtualvoidmin_max_value(Branch*b,double&min,double&max)=0;virtualdoublevalue(Object*o)=0;Object*desired; doublemvalue; …應(yīng)用極值搜索類{virtualvoidmin_max_value(Branch*b,double&min,double&max);virtualdoublevalue(Object*o); A3空間多級樹及快速搜索的使用方A3空間多級樹及快速搜索的使用方classAtom3D:publicPoint3Ddoublevx,vy,vz, Brancha-…a-//將物體掛在樹treettreeBranch*ttree=0;…//將物體掛在樹tree使用快速搜索器搜索物體的方法：通過繼承形式搜索器（Condition_Searcher對于conditionmay_be_contained_inMinimum_Searchervaluemax_min函數(shù)下面程序段通過繼承Condition_Searcher定義了一個(gè)應(yīng)用條件搜索器 bool{下面程序段通過繼承Condition_Searcher定義了一個(gè)應(yīng)用條件搜索器 bool{Bool A_Condition_Searcher*cs=new 下面程序段通過繼承Minimum_Searcher定義了一個(gè)應(yīng)用極值搜索器doubleA_Minimum_SearchervoidA_Minimum_Searcher::max_min(Branch*b,double&max,A_Minimum_Searcher*ms=new//initializethesearch參考文DierkRaabe,ComputationalMaterialsScience:TheSimulationofMaterialsMicrostructuresandProperties,Wiley-VCH1998.K.S.Kumar,H.VanSwygenhoven,S.Suresh,Mechanicalbehaviorofnanocrystallinemetalsandalloys-ActaMaterialia51(2003)5743–5774.Kelchner,Plimpton,Hamilton,PhysRevB,58,11085Ackland,Jones,PhysRevB,73,054104Faken,Jonsson,ComputMaterSci,2,279G.Michael，K.Stephan，Z.Gerhard，“NumericalSimulationinMolecularDynamics”，Springer-VerlagBerlinHeidelberg2007.MarkdeMarkdeBerg,MarcvanKreveld,MarkOvermars,andOtfriedSchwarzkopf,ComputationalGeometry(2ndrevisededitioned.),Springer-Verlag,2000.DonaldKnuth,SortingandSearching,TheArtofComputerProgramming,Volume3(Thirded.),Addison-Wesley,1997.Moore,E.F.(1959)."Theshortestpaththroughamaze".ProceedingsofanInternationalSymposiumontheTheoryofSwitching(Cambridge,Massachusetts,2–5April1957).Cambridge:HarvardUniversityPress.pp.deBerg,Mark;OtfriedCheong,MarcvanKreveld,MarkOvermars(2008).ComputationalGeometry:AlgorithmsandApplications.Springer-Verlag.ISBN978-3-540-77973-5.AmentP.EffectsofionizationgradientsonInertial-Confinement-Fusioncapsulehydrodynamicsstability.PhysRevLett,2008,101:115004deVries1PC,HuaMD,McDonaldDC,etal.ScalingofrotationandmomentumconfinementinJETplasmas.NuclFusion,2008,48:065006BowlerBP,WallerWH,MegeathST,etal.Aninfraredcensusofstarformationinthehorseheadnebula.AstronJ,2009,137:3685—3699HernquistL.HierarchicalN-bodymethods.ComputPhysCommun,1988,48:107—MakinoJ.Vectorizationofatreecode.JComputPhys,1990,87:148—HidakaY,ChoiEM,MastovskyI,etal.Observationoflargearraysofplasmafilamentsinairbreakdownby1.5-MW110-GHzgyrotronpulses.PhysRevLett,2008,100:035003NogaretT,RodneyD,FivelM,etal.Clearbandformationsimulatedbydislocationdynamics:Roleofhelicalturnsandpile-ups.JNuclMater,2008,380:22—29KotsiantisSB,PintelasPE.Recentadvancesinclustering:Abrief