利用并行八叉樹劃分技術開展復雜構型航天器放氣污染分析研究

焦子龍，姜利祥，黃建國，孫繼鵬，朱云飛

（北京衛星環境工程研究所 可靠性與環境工程技術重點實驗室，北京 100094）

利用并行八叉樹劃分技術開展復雜構型航天器放氣污染分析研究

焦子龍，姜利祥，黃建國，孫繼鵬，朱云飛

（北京衛星環境工程研究所 可靠性與環境工程技術重點實驗室，北京 100094）

放氣污染對航天器造成的有害影響需要定量評估。放氣產物分子的輸運過程可以采用 Monte-Carlo方法模擬，并用射線表示放氣分子輸運軌跡。如此一來，即轉換為射線追蹤問題。由于航天器構型復雜，射線追蹤的計算很耗時，所以有必要研究其加速算法。文章將復雜構型航天器表面用三角形非結構網格表示，利用八叉樹劃分技術開展分子運動軌跡與表面相交的加速模擬計算。同時，在基于共享內存多核計算平臺，利用OpenMP API軟件實現了計算的并行化。該方法在對空間站的實例計算中顯著提高了運算速度，并對空間站的污染情況進行了初步評價分析。

航天器；放氣污染；模擬計算；復雜構型；八叉樹；并行計算

0 引言

在航天器結構中，廣泛應用碳纖維/環氧復合材料、熱控涂層材料、隔熱材料、膠粘劑等[1-3]。航天器在軌運行過程中，這些材料在真空、高低溫、粒子輻射等環境中將發生質量損失，統稱為放氣[4]。這不僅影響材料本身的性能，還會對航天器造成污染。例如歐洲的Rosetta彗星探測器在利用四極質譜計探測彗星周圍氣體成分時，發現探測器材料放氣對探測結果產生了嚴重影響[5]。Cassini探測器在軌飛行中材料放氣使其窄視角相機受到嚴重污染，造成圖像出現光暈現象，不得不進行了長時間的加熱除氣[6]。因此，有必要對航天器用材料提出嚴格的放氣控制要求。

除需對材料放氣進行嚴格控制外，還需要定量評估放氣帶來的影響。國內外對放氣污染評估分析方法進行了廣泛研究。例如，針對國際空間站的污染分析與評估，ESA和 NASA分別開發了COMOVA和NASAN污染分析軟件[7]。這2款軟件均采用Monte-Carlo方法，并用射線來表征分子的輸運過程，包括分子從放氣源表面出射，在航天器周圍運動、碰撞，在敏感表面被吸附等過程。

航天器構型復雜，射線追蹤的計算很耗時，因此有必要研究其加速算法。本文將計算機圖形學中常用到的射線追蹤加速方法即并行八叉樹劃分技術引入復雜構型航天器的放氣污染分析中，并在OpenMP API軟件平臺上開展了模擬分析，獲得了很好的加速效果。

1 放氣污染計算

1.1 蒙特卡羅方法

粒子在軌道環境中傳輸分為直接流和背景散射返回流，對這些粒子流可以采用試驗粒子蒙特卡羅方法（Test Particle Monte-Carlo, TPMC）進行模擬。TPMC方法基于硬球碰撞（二體彈性碰撞）模型，采用統計方法對大量放氣分子的運動、碰撞和軌跡進行模擬計算，以獲得相應的散射分布和返回流比率，具體計算方法和步驟可參見文獻[8-10]。

1.2 八叉樹劃分算法

八叉樹（octa-tree）算法是一種常用的空間劃分技術，具有數據結構簡單、集合運算高效、節點遍歷運算易于實現等優點，是射線追蹤普遍采用的加速方法，如圖1所示。

圖1 八叉樹空間劃分示意圖Fig.1 Sketch of octa-tree subdivision

其基本過程是：構建包含所有空間對象的長方體包圍盒作為根節點；再對該包圍盒進行細分，即沿3個坐標軸方向將其分為8個大小相等的子立方體；接著檢查每個子立方體，如果子立方體內空間對象的個數不大于給定的閾值，則停止分解該子立方體，否則，需要對該子立方體繼續進行8等分，直到內部空間對象數低于給定閾值。

采用八叉樹劃分后，當需要求解射線與空間對象的交點時，不需要判斷射線與每個空間對象是否相交，而只需對與射線相交的包圍盒中的空間對象進行判斷（即先對包圍盒進行簡單的求交運算，然后略過與射線不相交的包圍盒），從而達到減少求交次數和計算時間的目的。

Agate等人[11]提出了一種自頂向下的八叉樹搜索算法，充分利用了八叉樹的空間結構特性，與其他算法相比，計算速度更快。

射線可用參數方程表示，即

起點矢量為O=[Ox,Oy,Oz]T，方向矢量為D=[l,m,n]T。在判斷射線是否與坐標軸平行的八叉樹子節點相交之前，可先求出射線與子節點邊界相交的t值：

其中x0和x1分別為子節點的x坐標值的下邊界和上邊界。

類似地可以求出0yt、1yt、0zt、1zt。然后再求出tmin和tmax：

當沿八叉樹從根節點向下搜索時，可以利用空間劃分的特性加速計算。八叉樹子節點劃分采用中間平面，因此其子節點的任一方向的t值恰好是對應父節點t值的一半。然后，確定射線進入節點的平面，再根據射線的參數確定后續的相交節點。如果該節點包含空間對象，則將其加入待求交點空間對象列表。遞歸調用搜索過程，直到射線穿出八叉樹為止。最后求出射線與前述空間對象列表每個元素相交的t值，則最小t值對應的空間對象即為所求結果。

1.3 并行處理技術

隨著計算機技術的發展，為了解決單核心CPU處理能力難以繼續提高的瓶頸，多核心CPU技術得到了飛速發展和廣泛應用。因此模擬計算中應充分利用多核CPU的計算加速能力。在確定計算硬件條件后，接下來的主要工作是計算程序的并行化編程。

多核CPU屬于共享存儲的對稱多處理器[12]。OpenMP是為共享存儲環境編寫并行程序而設計的一個應用編程接口，支持Fortran、C/C++語言。OpenMP標準中包括一套編譯指導語句和一個支持函數庫。在并行執行程序時，它采用 Fork/Join方式。其基本流程是：程序開始時只有一個主線程，即程序中的串行部分都由主線程執行，而并行部分則通過派生（Fork）其他線程來執行。待并行執行程序結束后（Join）才能執行后面非并行部分代碼，如圖2所示。

分析TPMC算法計算過程，可以在網格循環部分和試驗粒子循環部分進行并行。若在試驗粒子循環部分采用并行，則需要進行多次的線程派生注銷操作，效率低。因此，需要在網格循環級別進行并行，即在C/C++語言中具體實現方法是需要在循環前加入“#pragma omp parallel for”編譯指導語句。

圖2 共享存儲并行程序的并行執行流程Fig.2 Flowchart of parallel program on shared memory machine

2 計算結果

2.1 圓盤返回流

對文獻[10]中介紹的圓盤返回流進行計算，顯示了八叉樹劃分算法的加速效果。算例的模型如圖3所示。計算結果為返回流比率，即與背景分子碰撞后返回放氣表面的分子數與總放氣分子數的比。算例的輸入參數見表1。

圖3 模型示意圖Fig.3 Model sketch

表1 算例輸入參數Table 1 Input parameters for test case

對粗網格（90個三角形網格）和細網格（1128個三角形網格）2種情況進行了比較計算。網格劃分如圖4所示。

圖4 兩種網格劃分示意圖Fig.4 Comparison between coarse meshes and fine meshes

計算機硬件配置為Intel Core2 Duo E7500雙核CPU、內存4 GB、操作系統Windows XP。文獻[10]中的計算結果為 1.367 7×10-6，本文的計算結果為1.326 2×10-6，二者偏差為3%，符合度較好。加速效果如表2所示。

表2 計算時間對比Table 2 Comparison of calculation time

可以看出，在網格數較多時，八叉樹的加速效果極為顯著。并且，加速系數可用ncell/(klog8ncell)近似表示，其中k為八叉樹子節點中空間單元的最大個數，本文中設置為 8，ncell表示總的空間單元個數。

并行加速比定義為S=T串/T并，即串行執行時間與并行執行時間的比值，當并行加速比等于計算內核數時，稱為線性加速。本文中加速比接近計算內核數2，說明算法具有較好的加速特性。當計算任務復雜，需要較短時間獲得結果時，可通過簡單增加線程數目實現。

2.2 空間站污染仿真分析

對特定空間站構型下的污染分布狀況進行了初步分析。空間站構型取自文獻[13]，共劃分24 166個三角形網格，網格劃分情況如圖5所示。可以看出，在表面曲率變化大的部位進行了自動加密，使得網格能夠較精確地貼合表面。

圖5 空間站網格劃分Fig.5 Meshing of a space station

已有試驗證明太陽電池板放氣較為嚴重[14]，因此污染源選擇其中一塊面積較大的太陽電池板。軌道大氣來流速度方向為-z，其他參數與2.1節中算例一致。該計算采用雙線程,耗時 387.822 s。計算結果如圖6所示，顯示的是從污染源釋放的分子直接運動或經過與大氣分子碰撞后運動至其他表面的情況，即單位面積表面網格上的入射分子數。結果表明，污染分布與污染源及敏感表面之間的視角因子成正比。因此，與污染源距離越近，污染越嚴重。圖6(a)中正對污染源的位置所受污染最為嚴重。圖6(b)中，背對污染源的表面，未受到污染影響。從圖6中還可以發現由于表面遮擋造成的污染分布不均勻。污染源表面以及與其處于同平面的另一個太陽電池板也有分子沉積，這是由于污染分子與軌道大氣分子碰撞后返回而形成的。

圖6 污染分布計算結果Fig.6 The calculated contamination distribution

3 結束語

航天器的放氣污染需要定量評估其影響。采用Monte-Carlo方法進行模擬，用射線表征放氣分子的輸運過程，可將污染輸運過程轉化為射線追蹤問題。由于航天器構型復雜，射線追蹤的計算很耗時。本文將復雜構型航天器表面用三角形非結構網格表示，用八叉樹劃分算法開展分子運動軌跡與表面相交的加速計算。同時，利用基于共享內存多核計算平臺的OpenMP軟件實現了計算的并行化。計算實例證明該算法可大大地提高計算速度，且與串行計算結果一致。此外，上述算法還可應用于輻射傳熱角系數計算、空間粒子輻射影響分析等。

（

）

[1]陳烈民.航天器結構與機構[M].北京: 中國科學技術出版社, 2005: 63-70

[2]侯增祺, 胡金剛.航天器熱控制技術: 原理及其應用[M].北京: 中國科學技術出版社, 2007: 129-140

[3]陳樹海.衛星結構中的非金屬材料[J].上海航天, 2004, 21(3): 39-44 CHEN S H.Nonmetal materials in satellite structure[J].Aerospace Shanghai, 2004, 21(3): 39-44

[4]MILLER S K R, BANKS B.Degradation of spacecraft materials in the space environment[J].MRS Bulletin, 2010, 35(1): 20-24

[5]SCHLAPPI B, ALTWEGG K, BALSIGER H, et al.Characterization of the gaseous spacecraft environment of Rosetta by ROSINA[C]//3rdAIAA Atmospheric Space Environments Conference.Honolulu, HI, United States: American Institute for Aeronautics and Astronautics, 2011: 1-8

[6]HAEMMERLE V R, GERHARD J H.Cassini camera contamination anomaly: experiences and lessons learned: AIAA 2006-5834[R]

[7]ROUSSEL J F, SOARES C E, SCHMIDL W D.Development and validation of a new return flux model for International Space Station[C]//Optical System Contamination: Effects, Measurements, and Control VII, Proceedings of SPIE, 2002, 4774: 172-183

[8]焦子龍, 龐賀偉.航天器分子污染返回流計算方法[J].宇航學報, 2009, 30(2): 415-421 JIAO Z L, PANG H W.Simulation methods for return flux of molecular contamination[J].Journal of Astronautics, 2009, 30(2): 415-421

[9]焦子龍.航天器分子污染計算方法綜述[J].航天器環境工程, 2010, 27(2): 181-189 JIAO Z L.Review on simulation method for spacecraft molecular contamination[J].Spacecraft Environment Engineering, 2010, 27(2): 181-189

[10]FAN C, GEE C, FONG M C.Monte Carlo simulation of molecular flux on simple spacecraft surfaces due to selfand ambient-scatter of outgassing molecules: AIAA 1993-2867[R]

[11]AGATE M, GRIMSDALE R L, LISTER P F.The HERO algorithm for ray tracing octa-trees[M]//GRIMSDALER L, STRASSER W.Advances in computer graphics hardware IV.New York: Springer-Verlag, 1991: 23-27

[12]周偉明.多核計算與程序設計[M].武漢: 華中科技大學出版社, 2009: 5-10

[13]翟睿瓊, 姜海富, 田東波, 等.空間站原子氧環境仿真研究[J].裝備環境工程, 2014, 11(3): 35-39 ZHAI R Q, JIANG H F, TIAN D B.et al.Simulation of atomic oxygen interaction with space station[J].Equipment Environmental Engineering, 2014, 11(3): 35-39

[14]焦子龍, 龐賀偉, 易忠, 等.航天器真空熱試驗污染物成分分析[J].航天器環境工程, 2010, 27(6): 711-714 JIAO Z L, PANG H W, YI Z.et al.Analysis of contaminant components of spacecraft thermal vacuum test[J].Spacecraft Environment Engineering, 2010, 27(6): 711-714

（編輯：肖福根）

Parallel and octa-tree-based acceleration of outgassing contamination simulation for spacecraft of complex geometries

JIAO Zilong, JIANG Lixiang, HUANG Jianguo, SUN Jipeng, ZHU Yunfei
(Science and Technology on Reliability and Environmental Engineering Laboratory, Beijing Institute of Spacecraft Environment Engineering, Beijing 100094, China)

The organic materials used in spacecraft may outgas under the space environment, including, mainly, the vacuum, the high & low temperature, and the influence of the ionization irradiation.The outgassing product has harmful effects on the spacecraft itself.So a quantitative assessment of the contamination effects is necessary.The molecular transport process is modeled by the Monte-Carlo method, with the rays representing the molecule trajectories, to simulate the motion process of a large number of molecules.Thus the transport process is transformed into a ray tracing problem.Due to the complexity of the spacecraft configurations, the ray tracing computation might be very time consuming, therefore, it is extremely necessary to have an accelerating algorithm.In this paper, the complex geometry of the spacecraft surface is modeled with triangular unstructured grids, the octa-tree space subdivision technology is used to accelerate the molecular motion and surface intersection calculations.At the same time, based on the shared memory multi-core computing platform, the OpenMP API is used to implement parallel computing for the simulation.The test case shows a significant acceleration in the calculation, and the developed method is applied to the contamination analysis of a space station.

spacecraft; outgassing contamination; simulation computation; complex geometries; octa-tree; parallel computing

X502

：A

：1673-1379(2016)06-0601-05

10.3969/j.issn.1673-1379.2016.06.005

焦子龍（1979—），男，博士學位，高級工程師，從事航天器特殊空間環境效應分析、試驗及防護技術研究。E-mail: novanova2009@163.com。

2016-04-01；

：2016-11-10