基于包围盒与碰撞的模型填充算法研究

燕楠　林支慨

摘  要：为了将任意模型使用球体进行密实填充，提出了一种基于包围盒与碰撞的模型填充算法。该算法首先生成模型的轴对称包围盒;其次在包围盒内产生任意数量球体并进行刚体碰撞，碰撞后的球体将会在包围盒的范围内均匀分布;最后采用判断法线方向算法筛选出模型内部的球体并保留至最终结果。通过实例证明，该算法能够根据输入的球体填充数量及孔隙率快速生成模型内的紧密填充球体。该算法对于模型的适应性高，生成速度快，具有2，000万三角网格的模型仅需20 秒即可生成内部填充球体，为生成点阵结构模型进一步奠定了基础。

关键词：模型填充;包围盒;球体碰撞

中图分类号：TP301.6     文献标识码：A

Research on Model Filling Algorithm based on Bounding Box and Collision

YAN Nan1， LIN Zhikai2

（1.School of Optical-Electrical and Computer Engineering， University of Shanghai for Science and Technology， Shanghai 200093， China;

2.School of Mechanical Engineering， University of Shanghai for Science and Technology， Shanghai 200093， China）

yannan19920423@163.com; 1012287837@qq.com

Abstract： In order to densely fill any model with sphere， this paper proposes a model filling algorithm based on bounding box and collision. First， the algorithm has an axisymmetric bounding box of the model generated， and then any number of spheres are generated in the bounding box and are collided with rigid bodies. The collided spheres will be evenly distributed within the bounding box. Finally， the algorithm of judging normal direction is used to filter out the spheres inside the model and retain them to the result. Examples have shown that the algorithm can quickly generate the tightly filled spheres in the model according to the filling quantity and porosity of the input sphere. The proposed algorithm has high adaptability to the model and the generation speed is fast. For a model with 20 million triangular meshes， it takes only 20 seconds to generate the internally filled sphere， which further lays the foundation for the generation of the lattice structure model.

Keywords： model filling; bounding box; sphere collision

1   引言（Introduction）

點阵结构在工程中无处不在，出现在许多不同尺度的物体中：从桥梁和塔楼中的大型桁架结构，到摩托车和自行车的轻质金属部件，再到纳米级的微结构，如纳米纤维等[1-2]。人们在自然界中发现了球体堆积结构，如蜂窝中的六边形图案[3]和由等边三角形组成的底层晶格结构，经过研究发现点阵结构与球体堆积有着紧密的关系[4]，这些紧密（切向接触）堆积的球体可以构成以球心为顶点、以边为中心连接杆的点阵结构。

在三维空间中实现最大堆积密度的两种等半径球体堆积模式分别是面心立方堆积和六角密堆积[5]，如图1所示。在面心立方堆积中，14 个球体排列在立方体的顶点和面的中心，任何两个切向接触的球体中心由一根梁连接，由此产生的点阵结构称为八角单胞[6]。六角密堆积经常出现在自然界的类晶体结构中[5]，在六角密堆积中球体排列为上下两个六边形，以及夹在两个六边形之间的三角形，由此产生的点阵结构称为六角单胞。综上可以得出结论：给出三维几何模型并为其内部找到紧密的球体堆积，从球体堆积构建点阵结构，这样会产生符合预期的内部支撑。

本文提出了一种基于模型包围盒与球体碰撞的算法，该算法可以生成模型内部紧密堆积的球体，首先构建模型的包围盒，在包围盒内生成球体后进行碰撞，最后筛选出模型内的球体作为模型的堆积球体。

2   相关工作（Related work）

在二维空间中有圆的包装填充问题，问题给出了一组具有非均匀半径的圆，目的是找到可以将这一组圆装入的最小图形，通常图形也是圆形的。此类问题的一个实际生活实例是找到最小的孔，使不同半径的电线束可以穿过该孔[7]，这个问题在文献[7]和文献[8]中得到解决，解决的两种方法都基于生成初始配置，然后通过缩小域和模拟摇动圆圈来迭代改进。

文献[9]在重复元素组成的自由形式建筑设计中受到启发，将圆和球体应用于曲面中，并引入圆形填料网格的概念。圆形填料网格由三角网格组成，在三角网格中三角形的内圆形成一个堆积，即两个拥有公共边的三角形，这两个三角形的内圆在该边上具有相同的接触点。文献[9]最后提出了一个基于优化的框架来证明圆形填充网格可以适应任意自由形式的几何体。

在三维中，球体填充及其泛化方法——气泡填充已经可以作为工具应用于性能良好的网格模型上[10-11]。这两种方法利用了填充球体和模型网格中心之间的二元性，但是受到域形状的影响，使用有限元逼近时存在很大误差，因此最好使用规则的类Delaunay来进行三角剖分[12]。然而在这类文献及方法中，填充球体允许相邻球体之间重叠或者具有小间隙，所以并不是经典意义上相邻球体具有切向接触的堆积。

严格按照切向接触的球体堆积与文献[13]和文献[14]更相关，其中文献[13]考虑了各种尺寸的无界域中的球体填充。但与我们研究最接近的工作是文献[14]，它将最大数量的等半径球体填充到多面体容器中，并通过简单凸多面体的示例进行验证，这些凸多面体内部可以包含一些多面体障碍物，例如多边形棱柱、凸多面体锥体和二面角。相比之下，我们的方法支持任意自由形式边界并且计算速度也相对较快。

3  包围盒生成算法（Bounding box generation algorithm）

目前常见的包围盒有球形包围盒（Sphere）、轴对称包围盒（Axis-Aligned Bounding Box）、方向包围盒（Oriented Bounding Box）。选用轴对称包围盒是因为它可以根据被包围对象的形状特点尽可能紧密地包围对象，而且相对其他包围盒算法生成速度快，构造简单。

轴对称包围盒的生成需要六个值，这六个值分别代表包围盒在每个坐标轴上的最大值、最小值，即、、

、、、，这六个值的生成需要对模型中所有顶点坐标进行扫描，并求出各个轴分量的最大值与最小值即可，也就是说所有模型上的点都满足以下条件：

之后将轴对称包围盒的六个参数分为以下两组：

其中，是三个坐标轴最小值的集合，是三个坐标轴最大值的集合。在知道了轴对称包围盒的六个参数之后，就可以求得轴对称包围盒的几何中心，如公式（3）所示。包围盒的中心将会在下一部分“球体碰撞”中使用。

4   球体碰撞（Sphere collision）

球体碰撞主要分为两步：首先生成初始球体群;之后使用生成的球体群在包围盒内进行碰撞。算法中需要用户输入的数据为孔隙率、填充球的数目，以及初始球体群的数目。

4.1   球体群生成

球体群的生成，是在模型的包围盒内随机生成 个等半径球体，生成的球体拥有两个参数：半径以及球心位置。球体的半径是根据用户输入的孔隙率经过计算得出的，孔隙率的公式为：

其中，为包围盒的体积，为碰撞之后所有球体的体积。和的公式为：

式中，为包围盒内填充球的数目，需要用户确定。将上述公式代入孔隙率公式，经过变换后可以得出半径的计算公式：

球心包含三个值，分别是、、，这三个数值分别代表球心的、、坐標位置。、、是使用随机函数在包围盒的范围内随机生成的，即三个数值都需要满足公式（1）的要求。将随机生成球心的算法重复 次并结合计算得出的半径，就可以得到球体群。

4.2   碰撞算法

球体碰撞算法是根据刚体碰撞规则进行的，首先固定一个球体为刚性球体，这个球体也称为被固定的球体。在刚性球体半径内如果有其他球体，则这些球体全部会被刚性球体“弹开”，刚性球体将所有范围内球体“弹开”之后加入固定数组内，最后输出结果为固定数组内的球体。碰撞算法主要分为以下三步：

（1）从待碰撞数组中取出一个球体作为刚性球体。

（2）对刚性球体进行碰撞。

（3）被碰撞过的球体加入待碰撞数组，刚性球体在碰撞过后加入固定数组。

因为待碰撞数组在算法首次运行时为空，所以需要模型中包围盒的中心来辅助进行，在球体群中选出距离包围盒的中心最近的球体并将该球体添加进待碰撞数组。之后取出待碰撞数组内球体作为刚性球体，计算刚性球体与球体群内球体的距离，根据欧式距离公式计算：

其中，、、、、、分别为刚性球体与球体群内球体的球心坐标值，根据计算出来的与之间的关系可以分为两种情况：，则说明两个球体之间不存在碰撞问题直接跳过;，则说明两个球体之间存在碰撞问题，继续进行碰撞。碰撞是刚性球体不移动，将被碰撞的球体朝着方向移动距离，其中方向与距离的计算公式如下：

其中，将被碰撞的球体移动之后，加入待碰撞数组之前分为两种情况进行处理：如果被碰撞的球体和固定数组内的球体经过碰撞算法计算再次发生碰撞则直接删除该球体;如果没有与固定数组内球体碰撞则将该球体放入待排序数组内。最后重复上述算法步骤，直到待碰撞数组为空得到最后确定的固定数组，固定数组内的球体是均匀分布在包围盒内的球体。

5  筛选模型内部球体（Filter spheres inside the model）

判断球体是否在模型内部是根据模型的法线方向与球体的球心位置。模型中每一个三角网格都有法线方向，因为每一片都是三角形，由三角形可以得出该三角形所在的平面方程。由球体的球心向平面做投影，最后计算球心到投影点的方向是否和法线方向一致，如果球心与所有三角网格的法线方向一致，则证明球体在模型内部。

模型每一片都由三个点、、

组成，三个点组成的平面方程一般式为，将点数值代入方程中化简可得：

其中又可以根据三个点的坐标值分别求出：

将、、这三个值代入公式（9）中可以得到的值，最后得到平面方程。

从固定数组内取出球体，由球体的球心向平面方程做投影，投影点为，则：

将投影点代入平面方程化简后可以得到：

最后将代入公式（11）即可得到投影点的坐标。

得到投影点坐标之后，计算投影点与球心之间的向量（公式（8）），如果与该片的法线方向相同，则继续验证模型的下一片，直到模型全部片验证完毕，则证明球体在模型内部;如果与法线方向相反，证明该球体的球心在模型外部，则直接删除该球体。使用上述方法验证固定球体数组，最后可以得到输出球体，即全部在模型内部的球体。

6   实例验证（Example verification）

本文提出的填充方法仅适用于封闭的表面模型，对于不封闭的模型暂时无法进行填充。填充模型实例选用了三种不同的模型，即立方体模型、圆环模型及斯坦福兔子模型，填充使用的数据以及计算得出的半径和填充模型所需要的时间如表1所示，模型原图以及模型填充后示意图如图2所示。

7   结论（Conclusion）

目前的填充算法在切向接触与填充时间之间无法做到完美平衡，并且在模型较为复杂时会出现丢失模型精确度、填充不完整等问题。文中填充方法计算速度快，可以根据模型的初始数据和用户给出的参数任意变换模型的填充效果，对于复杂模型和各种凸凹模型都具有一定的适应性。

但是文中算法相较于其他的填充方法牺牲了一部分的切向接触，即填充之后的球体有可能具有一定的距离，所以将来的工作会重点在填充紧密度上做出进一步优化，使其达到更好的效果。

参考文献（References）

[1] GIL L， ANDREU A. Shape and cross-section optimisation of a truss structure[J]. Computers and Structures， 2001， 79（7）： 681-689.

[2] GOUPEE A J， Vel S S. Transient multiscale thermoelastic analysis of functionally graded materials[J]. Composite Structures， 2010， 92（6）：1372-1390.

[3] NAZZI F. The hexagonal shape of the honeycomb cells depends on the construction behavior of bees[J]. Scientific Reports， 2016， 32（6）：28-37.

[4] SOSIN B V， RODIN D， SLIUSARENKO H， et al. The construction of conforming-to-shape truss lattice structures via 3D sphere packing[J]. Computer-Aided Design， 2021， 132（2）：102-112.

[5] CONWAY J H， SLOANE N J A. Sphere packing， lattice and groups[M]. Berlin： Springer Science & Business Media， 2013：63-93.

[6] FULLER R B. Synergetics： Explorations in the geometry of thinking[M]. London： Macmillan Publishing Co. Inc.， 1975：   40-138.

[7] SUGIHARA K， KIM D S. Disk packing for the estimation of the size of a wire bundle[J]. Japan Journal of Industrial and Applied Mathematics， 2004， 21（3）：259-278.

[8] KALLRATH J， RYU J， SONG C， et al. Near optimal minimal convex hulls of disks[J]. Journal of Global Optimization， 2021， 80（6）：1-44.

[9] SCHIFTNER A， HOBINGER M， WALLNER J， et al. Packing circles and spheres on surfaces[J]. ACM Transactions on Graphics （TOG）， 2009， 28（5）：1-8.

[10] LIU J F， LI S X， CHEN Y Q. A fast and practical method to pack spheres for mesh generation[J]. Acta Mechanica Sinica， 2008， 24（4）：439-447.

[11] LO S H， WANG W X. Generation of tetrahedral mesh of variable element size by sphere packing over an unbounded 3D domain[J]. Computer Methods in Applied Mechanics and Engineering， 2004， 194（48）：5002-5018.

[12] 王秀菊，石崇，李德杰，等.基于距離和局部Delaunay三角化控制的颗粒离散元模型填充方法研究[J].岩土力学，2015，36（007）：2081-2087.

[13] CONWAY J H， TORQUATO S. Packing， tiling， and covering with tetrahedra[J]. Proceedings of the National Academy of Sciences of the United States of America， 2006， 103（28）：10612-10617.

[14] STOYAN Y， YASKOV G. Packing congruent spheres into a multi-connected polyhedral domain[J]. International Transactions in Operational Research， 2013， 20（1）：79-99.

作者简介：

燕   楠（1992-），男，硕士生.研究领域：计算机图形学.

林支慨（1996-），男，硕士生.研究领域：有限元分析.