基于包圍盒與碰撞的模型填充算法研究

燕楠　林支慨

摘? 要：為了將任意模型使用球體進(jìn)行密實(shí)填充，提出了一種基于包圍盒與碰撞的模型填充算法。該算法首先生成模型的軸對(duì)稱(chēng)包圍盒;其次在包圍盒內(nèi)產(chǎn)生任意數(shù)量球體并進(jìn)行剛體碰撞，碰撞后的球體將會(huì)在包圍盒的范圍內(nèi)均勻分布;最后采用判斷法線方向算法篩選出模型內(nèi)部的球體并保留至最終結(jié)果。通過(guò)實(shí)例證明，該算法能夠根據(jù)輸入的球體填充數(shù)量及孔隙率快速生成模型內(nèi)的緊密填充球體。該算法對(duì)于模型的適應(yīng)性高，生成速度快，具有2，000萬(wàn)三角網(wǎng)格的模型僅需20 秒即可生成內(nèi)部填充球體，為生成點(diǎn)陣結(jié)構(gòu)模型進(jìn)一步奠定了基礎(chǔ)。

關(guān)鍵詞：模型填充;包圍盒;球體碰撞

中圖分類(lèi)號(hào)：TP301.6? ? ?文獻(xiàn)標(biāo)識(shí)碼：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）

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

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

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

2? ?相關(guān)工作（Related work）

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

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

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

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

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

目前常見(jiàn)的包圍盒有球形包圍盒（Sphere）、軸對(duì)稱(chēng)包圍盒（Axis-Aligned Bounding Box）、方向包圍盒（Oriented Bounding Box）。選用軸對(duì)稱(chēng)包圍盒是因?yàn)樗梢愿鶕?jù)被包圍對(duì)象的形狀特點(diǎn)盡可能緊密地包圍對(duì)象，而且相對(duì)其他包圍盒算法生成速度快，構(gòu)造簡(jiǎn)單。

軸對(duì)稱(chēng)包圍盒的生成需要六個(gè)值，這六個(gè)值分別代表包圍盒在每個(gè)坐標(biāo)軸上的最大值、最小值，即、、

、、、，這六個(gè)值的生成需要對(duì)模型中所有頂點(diǎn)坐標(biāo)進(jìn)行掃描，并求出各個(gè)軸分量的最大值與最小值即可，也就是說(shuō)所有模型上的點(diǎn)都滿(mǎn)足以下條件：

之后將軸對(duì)稱(chēng)包圍盒的六個(gè)參數(shù)分為以下兩組：

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

4? ?球體碰撞（Sphere collision）

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

4.1? ?球體群生成

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

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

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

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

4.2? ?碰撞算法

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

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

（2）對(duì)剛性球體進(jìn)行碰撞。

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

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

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

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

5? 篩選模型內(nèi)部球體（Filter spheres inside the model）

判斷球體是否在模型內(nèi)部是根據(jù)模型的法線方向與球體的球心位置。模型中每一個(gè)三角網(wǎng)格都有法線方向，因?yàn)槊恳黄际侨切?，由三角形可以得出該三角形所在的平面方程。由球體的球心向平面做投影，最后計(jì)算球心到投影點(diǎn)的方向是否和法線方向一致，如果球心與所有三角網(wǎng)格的法線方向一致，則證明球體在模型內(nèi)部。

模型每一片都由三個(gè)點(diǎn)、、

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

其中又可以根據(jù)三個(gè)點(diǎn)的坐標(biāo)值分別求出：

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

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

將投影點(diǎn)代入平面方程化簡(jiǎn)后可以得到：

最后將代入公式（11）即可得到投影點(diǎn)的坐標(biāo)。

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

6? ?實(shí)例驗(yàn)證（Example verification）

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

7? ?結(jié)論（Conclusion）

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

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

參考文獻(xiàn)（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].巖土力學(xué)，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.

作者簡(jiǎn)介：

燕? ?楠（1992-），男，碩士生.研究領(lǐng)域：計(jì)算機(jī)圖形學(xué).

林支慨（1996-），男，碩士生.研究領(lǐng)域：有限元分析.