利用并行八叉树划分技术开展复杂构型航天器放气污染分析研究

焦子龙，姜利祥，黄建国，孙继鹏，朱云飞

（北京卫星环境工程研究所 可靠性与环境工程技术重点实验室，北京 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