燕楠　林支慨

摘? 要：為了將任意模型使用球體進行密實填充，提出了一種基于包圍盒與碰撞的模型填充算法。該算法首先生成模型的軸對稱包圍盒;其次在包圍盒內產生任意數(shù)量球體并進行剛體碰撞，碰撞后的球體將會在包圍盒的范圍內均勻分布;最后采用判斷法線方向算法篩選出模型內部的球體并保留至最終結果。通過實例證明，該算法能夠根據(jù)輸入的球體填充數(shù)量及孔隙率快速生成模型內的緊密填充球體。該算法對于模型的適應性高，生成速度快，具有2，000萬三角網(wǎng)格的模型僅需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）

點陣結構在工程中無處不在，出現(xiàn)在許多不同尺度的物體中：從橋梁和塔樓中的大型桁架結構，到摩托車和自行車的輕質金屬部件，再到納米級的微結構，如納米纖維等[1-2]。人們在自然界中發(fā)現(xiàn)了球體堆積結構，如蜂窩中的六邊形圖案[3]和由等邊三角形組成的底層晶格結構，經過研究發(fā)現(xiàn)點陣結構與球體堆積有著緊密的關系[4]，這些緊密（切向接觸）堆積的球體可以構成以球心為頂點、以邊為中心連接桿的點陣結構。

在三維空間中實現(xiàn)最大堆積密度的兩種等半徑球體堆積模式分別是面心立方堆積和六角密堆積[5]，如圖1所示。在面心立方堆積中，14 個球體排列在立方體的頂點和面的中心，任何兩個切向接觸的球體中心由一根梁連接，由此產生的點陣結構稱為八角單胞[6]。六角密堆積經常出現(xiàn)在自然界的類晶體結構中[5]，在六角密堆積中球體排列為上下兩個六邊形，以及夾在兩個六邊形之間的三角形，由此產生的點陣結構稱為六角單胞。綜上可以得出結論：給出三維幾何模型并為其內部找到緊密的球體堆積，從球體堆積構建點陣結構，這樣會產生符合預期的內部支撐。

本文提出了一種基于模型包圍盒與球體碰撞的算法，該算法可以生成模型內部緊密堆積的球體，首先構建模型的包圍盒，在包圍盒內生成球體后進行碰撞，最后篩選出模型內的球體作為模型的堆積球體。

2? ?相關工作（Related work）

在二維空間中有圓的包裝填充問題，問題給出了一組具有非均勻半徑的圓，目的是找到可以將這一組圓裝入的最小圖形，通常圖形也是圓形的。此類問題的一個實際生活實例是找到最小的孔，使不同半徑的電線束可以穿過該孔[7]，這個問題在文獻[7]和文獻[8]中得到解決，解決的兩種方法都基于生成初始配置，然后通過縮小域和模擬搖動圓圈來迭代改進。

文獻[9]在重復元素組成的自由形式建筑設計中受到啟發(fā)，將圓和球體應用于曲面中，并引入圓形填料網(wǎng)格的概念。圓形填料網(wǎng)格由三角網(wǎng)格組成，在三角網(wǎng)格中三角形的內圓形成一個堆積，即兩個擁有公共邊的三角形，這兩個三角形的內圓在該邊上具有相同的接觸點。文獻[9]最后提出了一個基于優(yōu)化的框架來證明圓形填充網(wǎng)格可以適應任意自由形式的幾何體。

在三維中，球體填充及其泛化方法——氣泡填充已經可以作為工具應用于性能良好的網(wǎng)格模型上[10-11]。這兩種方法利用了填充球體和模型網(wǎng)格中心之間的二元性，但是受到域形狀的影響，使用有限元逼近時存在很大誤差，因此最好使用規(guī)則的類Delaunay來進行三角剖分[12]。然而在這類文獻及方法中，填充球體允許相鄰球體之間重疊或者具有小間隙，所以并不是經典意義上相鄰球體具有切向接觸的堆積。

嚴格按照切向接觸的球體堆積與文獻[13]和文獻[14]更相關，其中文獻[13]考慮了各種尺寸的無界域中的球體填充。但與我們研究最接近的工作是文獻[14]，它將最大數(shù)量的等半徑球體填充到多面體容器中，并通過簡單凸多面體的示例進行驗證，這些凸多面體內部可以包含一些多面體障礙物，例如多邊形棱柱、凸多面體錐體和二面角。相比之下，我們的方法支持任意自由形式邊界并且計算速度也相對較快。

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

目前常見的包圍盒有球形包圍盒（Sphere）、軸對稱包圍盒（Axis-Aligned Bounding Box）、方向包圍盒（Oriented Bounding Box）。選用軸對稱包圍盒是因為它可以根據(jù)被包圍對象的形狀特點盡可能緊密地包圍對象，而且相對其他包圍盒算法生成速度快，構造簡單。

軸對稱包圍盒的生成需要六個值，這六個值分別代表包圍盒在每個坐標軸上的最大值、最小值，即、、

、、、，這六個值的生成需要對模型中所有頂點坐標進行掃描，并求出各個軸分量的最大值與最小值即可，也就是說所有模型上的點都滿足以下條件：

之后將軸對稱包圍盒的六個參數(shù)分為以下兩組：

其中，是三個坐標軸最小值的集合，是三個坐標軸最大值的集合。在知道了軸對稱包圍盒的六個參數(shù)之后，就可以求得軸對稱包圍盒的幾何中心，如公式（3）所示。包圍盒的中心將會在下一部分“球體碰撞”中使用。

4? ?球體碰撞（Sphere collision）

球體碰撞主要分為兩步：首先生成初始球體群;之后使用生成的球體群在包圍盒內進行碰撞。算法中需要用戶輸入的數(shù)據(jù)為孔隙率、填充球的數(shù)目，以及初始球體群的數(shù)目。

4.1? ?球體群生成

球體群的生成，是在模型的包圍盒內隨機生成 個等半徑球體，生成的球體擁有兩個參數(shù)：半徑以及球心位置。球體的半徑是根據(jù)用戶輸入的孔隙率經過計算得出的，孔隙率的公式為：

其中，為包圍盒的體積，為碰撞之后所有球體的體積。和的公式為：

式中，為包圍盒內填充球的數(shù)目，需要用戶確定。將上述公式代入孔隙率公式，經過變換后可以得出半徑的計算公式：

球心包含三個值，分別是、、，這三個數(shù)值分別代表球心的、、坐標位置。、、是使用隨機函數(shù)在包圍盒的范圍內隨機生成的，即三個數(shù)值都需要滿足公式（1）的要求。將隨機生成球心的算法重復 次并結合計算得出的半徑，就可以得到球體群。

4.2? ?碰撞算法

球體碰撞算法是根據(jù)剛體碰撞規(guī)則進行的，首先固定一個球體為剛性球體，這個球體也稱為被固定的球體。在剛性球體半徑內如果有其他球體，則這些球體全部會被剛性球體“彈開”，剛性球體將所有范圍內球體“彈開”之后加入固定數(shù)組內，最后輸出結果為固定數(shù)組內的球體。碰撞算法主要分為以下三步：

（1）從待碰撞數(shù)組中取出一個球體作為剛性球體。

（2）對剛性球體進行碰撞。

（3）被碰撞過的球體加入待碰撞數(shù)組，剛性球體在碰撞過后加入固定數(shù)組。

因為待碰撞數(shù)組在算法首次運行時為空，所以需要模型中包圍盒的中心來輔助進行，在球體群中選出距離包圍盒的中心最近的球體并將該球體添加進待碰撞數(shù)組。之后取出待碰撞數(shù)組內球體作為剛性球體，計算剛性球體與球體群內球體的距離，根據(jù)歐式距離公式計算：

其中，、、、、、分別為剛性球體與球體群內球體的球心坐標值，根據(jù)計算出來的與之間的關系可以分為兩種情況：，則說明兩個球體之間不存在碰撞問題直接跳過;，則說明兩個球體之間存在碰撞問題，繼續(xù)進行碰撞。碰撞是剛性球體不移動，將被碰撞的球體朝著方向移動距離，其中方向與距離的計算公式如下：

其中，將被碰撞的球體移動之后，加入待碰撞數(shù)組之前分為兩種情況進行處理：如果被碰撞的球體和固定數(shù)組內的球體經過碰撞算法計算再次發(fā)生碰撞則直接刪除該球體;如果沒有與固定數(shù)組內球體碰撞則將該球體放入待排序數(shù)組內。最后重復上述算法步驟，直到待碰撞數(shù)組為空得到最后確定的固定數(shù)組，固定數(shù)組內的球體是均勻分布在包圍盒內的球體。

5? 篩選模型內部球體（Filter spheres inside the model）

判斷球體是否在模型內部是根據(jù)模型的法線方向與球體的球心位置。模型中每一個三角網(wǎng)格都有法線方向，因為每一片都是三角形，由三角形可以得出該三角形所在的平面方程。由球體的球心向平面做投影，最后計算球心到投影點的方向是否和法線方向一致，如果球心與所有三角網(wǎng)格的法線方向一致，則證明球體在模型內部。

模型每一片都由三個點、、

組成，三個點組成的平面方程一般式為，將點數(shù)值代入方程中化簡可得：

其中又可以根據(jù)三個點的坐標值分別求出：

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

從固定數(shù)組內取出球體，由球體的球心向平面方程做投影，投影點為，則：

將投影點代入平面方程化簡后可以得到：

最后將代入公式（11）即可得到投影點的坐標。

得到投影點坐標之后，計算投影點與球心之間的向量（公式（8）），如果與該片的法線方向相同，則繼續(xù)驗證模型的下一片，直到模型全部片驗證完畢，則證明球體在模型內部;如果與法線方向相反，證明該球體的球心在模型外部，則直接刪除該球體。使用上述方法驗證固定球體數(shù)組，最后可以得到輸出球體，即全部在模型內部的球體。

6? ?實例驗證（Example verification）

本文提出的填充方法僅適用于封閉的表面模型，對于不封閉的模型暫時無法進行填充。填充模型實例選用了三種不同的模型，即立方體模型、圓環(huán)模型及斯坦福兔子模型，填充使用的數(shù)據(jù)以及計算得出的半徑和填充模型所需要的時間如表1所示，模型原圖以及模型填充后示意圖如圖2所示。

7? ?結論（Conclusion）

目前的填充算法在切向接觸與填充時間之間無法做到完美平衡，并且在模型較為復雜時會出現(xiàn)丟失模型精確度、填充不完整等問題。文中填充方法計算速度快，可以根據(jù)模型的初始數(shù)據(jù)和用戶給出的參數(shù)任意變換模型的填充效果，對于復雜模型和各種凸凹模型都具有一定的適應性。

但是文中算法相較于其他的填充方法犧牲了一部分的切向接觸，即填充之后的球體有可能具有一定的距離，所以將來的工作會重點在填充緊密度上做出進一步優(yōu)化，使其達到更好的效果。

參考文獻（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-），男，碩士生.研究領域：有限元分析.