三維線框圖的實體模型生成算法研究畢業(yè)論文

1、本科畢業(yè)論文三維線框圖的實體模型生成算法研究作者姓名:學(xué)科專業(yè)：信息與計算科學(xué)專業(yè)導(dǎo)師姓名:教授 完成時間：二o 年五月university of science and technology of chinaa dissertation for bachelor's degreealgorithm for solidifying 3dwireframesauthor name:speciality:information and computational sciencesupervisor:may,finished time:致謝歷時三個多月的畢業(yè)設(shè)計如今已經(jīng)接近尾聲，在此，我要感

2、謝我的導(dǎo)師劉利 剛老師。在大三的時候，劉老師用他獨特的學(xué)習(xí)方法、幽默的語言風(fēng)格、認真負 責(zé)的態(tài)度和不斷向前的精神，將我一步步代入計算機圖形學(xué)的領(lǐng)域，使我對計算 機圖形學(xué)產(chǎn)生了濃厚的興趣，同吋也使我的編程能力得到了很大的提高。在畢業(yè) 設(shè)計期間，劉老師也給了我很多幫助。劉老師會經(jīng)常關(guān)心我的進度，不斷給我提 出新的目標(biāo)。在我遇到問題的吋候，劉老師也會耐心地和我討論，并提出一些他 的想法，引導(dǎo)我逐步解決問題。同時，我也要感謝這四年來陪伴在我身邊的親人和朋友。在我一次次遇到困 難的時候，是你們在我身邊關(guān)心我、陪伴我、鼓勵我，讓我在逆境中堅持下去, 沒有放棄。摘要4abstract5第1章緒論6§

3、;1研究背景和意義6§1.2相關(guān)工作7第2章初始網(wǎng)格的建立8§2.1結(jié)點的建立8211 建立 endfaces8212 建立一個頂點附近的面9213 求凸包92w清除與柱子連接的面9§2.2柱子的建立1011第3章 三角網(wǎng)格的細分§3.1初始網(wǎng)格的細分113.1.1柱子部分的網(wǎng)格細分113丄2結(jié)點部分的網(wǎng)格細分12§3.2提高整體網(wǎng)格的精度13第4章結(jié)點的自然化15§4.1用b-mesh的方法迭代154.1.1建立虛擬球154.1.2根據(jù)虛擬球建立結(jié)點的網(wǎng)格16§4.2結(jié)點的網(wǎng)格光滑17§4.3 結(jié)果18中國科學(xué)技

4、術(shù)人學(xué)本科畢業(yè)論文第5章總結(jié)與展望22參考文獻24圖目錄1.1線框建筑，圖片來自于15o （a）水晶宮，英國，（b）蓬皮杜中心，法國，（c）火車東站，里斯本62.1建立初始網(wǎng)格的流程圖 103.1柱子上一個面的劃分 123.2三角而的劃分123.3三棱錐線框圖初始網(wǎng)格細分結(jié)果133.4實體化線框網(wǎng)格提高精度前后對比圖 144.1不同a值下生成的三棱錐線框的實體化線框圖 184.2正方體線框生成的實體化線框圖184.3 一個較復(fù)雜的實體化線框圖 194.4 一個柱子半徑不同的實體化線框圖 194.5不同柱子半徑下字母c的線框圖的實體化結(jié)果，（a）柱子半徑0.01（b）柱子半徑0.015 204.

5、6不同柱子半徑下兔子頭的線框圖的實體化結(jié)果，（a）柱子半徑0.01（b）柱子半徑0.014 205.1柱子粗細不同時結(jié)點產(chǎn)生凸起22摘要線框圖是指只包含點集和連接這些點的邊的集合的3d網(wǎng)格，它在建筑和模 型領(lǐng)域有著廣泛的應(yīng)用。然而線框圖網(wǎng)格本身沒有體積，無法具象化，在很多 2d顯示工具，如計算機上，不能分清線框圖邊的前后位置關(guān)系，且線框圖無法 用于模型制作、3d打印等。本文提出并實現(xiàn)了一種生成線框圖的實體模型的算法，用圓柱代替線框圖 中的邊并在圓柱相交的地方增加一個結(jié)點將這些圓柱相連。該算法先通過改進 前人的算法生成一個柱子為邊數(shù)較少的正多棱柱的初始網(wǎng)格，再在不改變柱子 形狀的前提下對初始網(wǎng)格

6、進行網(wǎng)格細分提高網(wǎng)格的精度。然后在結(jié)點部分建立 一些虛擬球并根據(jù)這些虛擬球定義一個隱式曲面，通過迭代使結(jié)點部分的網(wǎng)格 逐漸逼近這個隱式曲面。當(dāng)網(wǎng)格較接近隱式曲面時，可以對整體網(wǎng)格進行細分后 再進行迭代，如此重復(fù)兒次即可得到一個高精度的最終網(wǎng)格。該方法能對三維線 框圖生成實體模型，生成的實體模型可以準(zhǔn)確表達出原線框圖的幾何信息，且生 成模型表面是光滑的，整個模型看起來美觀、自然。關(guān)鍵詞：線框圖實體化高精度 bmesh 3d模型abstracta wireframe consists of a set of vertices and a set of edges connecting those

7、vertices. wireframes are widely used in architecture and model fields. however, a wireframe has no volume and is not concrete. when showed on a 2d display tool like a computer, it is hard to tell which edge of the wireframe is on front and which is at the back. also, wireframes cannot be made as mod

8、els or be 3d printedthis dissertation proposes and implements an algorithm to build a solidifying 3d model for a wireframe. in this method, cylinders were used to replace edges in the wireframe and were connected with 3d joints which were created at vertices in the wireframe. first, an initial mesh

9、was created by improving previous research. the pipes of the initial mesh are regular polygon prisms. the initial mesh was then subdivided to make it become a higher detailed mesh. after that, virtual balls were created at every joint and an implicit surface was defined with these virtual balls. the

10、 vertices at the joints were evolved to make the mesh approach to the implicit surface. being closing to the implicit surface, the mesh was subdivided and evolved again. the subdividing and evolving steps were repeated several times until the mesh becomes highly detailed. the final resulting mesh ca

11、n convey all information of the wireframe, and is smooth and looks beautiful and natural.key words: wireframes, solidifying, high precision, bmesh, 3d model第1章緒論3d模型網(wǎng)格通常是由點、邊、面三部分構(gòu)成，而線框圖是指僅由點和連接 這些點的邊構(gòu)成而沒有面信息的3d模型網(wǎng)格。相比于普通3d模型網(wǎng)格，線框 圖有占用空間小、易于傳輸、可以看到內(nèi)部結(jié)構(gòu)等優(yōu)點，但由于線框圖忽略了面 的信息，所以無法看出線框圖的哪部分是空心哪部分是實心9。因此對于很

12、多 可以忽略面信息的模型，線框圖就是一種比較好的表達方式。§1.1研究背景和意義線框圖在很多領(lǐng)域都有廣泛的應(yīng)用，比如建筑領(lǐng)域。很多建筑的支架都是由 線框構(gòu)成，而還有一些建筑本身就是由線框圖構(gòu)成的。圖1展示了一些線框建 筑，其中(a)水晶宮通常被作為預(yù)制組件建筑的第一個例子4。而隨著線框圖 在建筑領(lǐng)域越來越重要，很多建筑的模型，如飛機的模型、房屋的模型等也開始 用線框圖來展示。圖1.1線框建筑，圖片來目于15。(a)水晶宮，英國，(b)蓬皮杜屮心，法國, (c)火車東站，里斯本然而，線框圖只是一個抽彖概念，它的點和邊都沒有體積，但在線框建筑、3d打印等實際應(yīng)用中，要求輸入的3d模型必須

13、具有體積。同吋，在用計算機等 2d的顯示工具顯示時，線框圖并不能完整的傳達如邊的前后位置關(guān)系等3d 信息9。而實體化線框圖可以較好的避免這些缺點。實體化線框圖是指將線框圖中所有邊由3d柱子代替，并在這些柱子的相 交處，即線框圖中點的位置附近創(chuàng)立一個3d的結(jié)點將這些柱子連接起來的 3d模型。實體化線框圖可以將線框圖轉(zhuǎn)化成有一個體積的3d模型網(wǎng)格，可以直接按 照實體化線框圖建立出能傳達原線框圖中所有信息的實際物體，且可以在2d顯 示工具上通過實體化線框圖肓觀地看出線框圖的幾何結(jié)構(gòu)。§1.2相關(guān)工作kempen在cad和三維模型的研究中提出一種關(guān)于預(yù)制組件建筑的算法8, srinivasa

14、n等人做了一些對于含有很多洞和手柄的模型的生成的研究12-14,但 這些都不完全適用于線框圖。solidifying wireframes15屮給出了一種生成實體化線框圖的算法，該算法 可以將絕大部分線框圖轉(zhuǎn)化成實體化線框圖，生成的實體化線框圖表面是一個 二維流形曲面，而很多算法都要求輸入的網(wǎng)格表面是個二維流形曲面3, 5, 110 該算法還可以允許用戶自由調(diào)節(jié)實體化線框圖中3d柱子的粗細、橫截面形狀。 同時，該算法已被寫入3d模型設(shè)計軟件中1,14,用戶可以方便地通過簡單的 操作生成實體化線框圖。但該算法只是一個基本的生成算法，其中點、邊、面的 個數(shù)都較少，精度不夠高，而且結(jié)點和柱子之間的連

15、接顯得生硬不自然，有明顯 的棱角，結(jié)點本身也有很多棱角，不夠光滑。b-mesh6中提供了一種根據(jù)用戶輸入的骨骼球和骨骼來確定一個高精度曲面 的方法。該方法由用戶輸入一些骨骼和骨骼球，首先根據(jù)這些骨骼球和骨骼插入一 些屮間球（后面將骨骼球和屮間球統(tǒng)稱為虛擬球）。然后將所有虛擬球按照與它相 連的虛擬球數(shù)量的多少分為葉子結(jié)點、連接結(jié)點和關(guān)節(jié)結(jié)點16。將骨骼從關(guān)節(jié)結(jié) 點處分成若干分支并分別利用該分支上的虛擬球作出初始網(wǎng)格，不同分支的連接 處通過求凸包的方式建立網(wǎng)格。再通過所有虛擬球確定一個隱式場，根據(jù)該隱式 場可以確定一個隱式曲面，最后通過迭代的方法逼近這個隱式曲面并進行修正， 在迭代和修正的過程中不

16、斷細分網(wǎng)格，使網(wǎng)格精度提高。該方法牛成的曲面看上去 較美觀、自然。本文提出一種算法,在solidifying wireframes的基礎(chǔ)上,通過增加點、邊、 面的個數(shù)提高實體化線框圖的精度，并且利用b-mesh屮的方法對結(jié)點部分進行 迭代使結(jié)點以及結(jié)點和柱子的連接部分都是光滑的，整個網(wǎng)格看起來更自然、美 觀。該算法生成的所有柱子都是圓柱，且不同的柱子半徑可以不同。第2章初始網(wǎng)格的建立本文中初始三角網(wǎng)格的建立與solidifying wireframes 15中基本類似，和 solidifying wireframes中不同的是，為了使網(wǎng)格看上去較自然，須保證原線框圖 中的毎個頂點都包含在該頂點

17、對應(yīng)的結(jié)點內(nèi)。所以對生成網(wǎng)格中的每個結(jié)點，都 需要在原線框圖中該結(jié)點對應(yīng)的頂點附近多加一個小多邊形然后再求凸包。該 算法一共分為兩步，第一步是在原線框圖中每個頂點的位置上建立一個結(jié)點，第 二步是在原線框圖中所有邊的位置上建立一個柱子連接兩個結(jié)點。由于最終需要生成的柱子是圓柱，所以建立初始網(wǎng)格時假設(shè)所有柱子的都 是正多棱柱。且為了提高算法的效率，一開始柱子橫截面的多邊形邊數(shù)可以選取 較小的數(shù)，在進行了第4章結(jié)點的自然化的操作之后，再對網(wǎng)格進行細分，具體 細分細節(jié)會在3.2節(jié)說明。這里定義正多邊形的半徑為該止多邊形中心點到正多邊形的一個頂點的距 離，即正多邊形的外接圓半徑。用戶可以通過輸入每個柱子

18、橫截面正多邊形的的 半徑、邊數(shù)來確定這個柱子的形狀。§2.1結(jié)點的建立初始網(wǎng)格中結(jié)點的大小、形狀和與該結(jié)點連接的柱子的位置、個數(shù)、橫截面 有關(guān)，結(jié)點的建立分為如下四步進行。2.1.1 建立 end-faces對于原線框圖中的每一條邊，先對這條邊建立一個虛擬的柱子，柱子的橫截 面為一用戶輸入的正多邊形，正多邊形的中點均落在這條邊上。柱子的兩端橫截 面的中點位置是原圖中該邊對應(yīng)的兩個頂點的位置。將兩端的多邊形橫截面分 別定義為這兩個頂點的一個end-face,其中每個end-face對應(yīng)的軸的方向為l±l這 個end-face對應(yīng)的頂點指向這條邊的另一個頂點的方向。通過遍歷原圖

19、中的所 有邊，可以求出原圖中所有頂點的所有end-faceso但對于每個頂點，此時它們的end-faces是相互交叉的，要通過將它們沿軸 平移的方法來避免交叉，且為了方便后續(xù)操作，平移后這些end-faces應(yīng)該都分 布在由它們組成的凸包的表面。平移的距離通過下述方法求出。對于每個頂點對 應(yīng)的任意兩個cnd-faccs,求出這兩個cnd-faccs的半徑中的較大值rm，將這兩個 end-faces平移直到以這兩個end-faces的中心為圓心、rm為半徑的兩個圓不相 交為止，求出這個最小平移距離。將該頂點對應(yīng)的所有end-faces兩兩進行上述操 作，求出所有最小平移距離中的最大值i。最終將這

20、個頂點對應(yīng)的所有end-faces 分別沿軸平移一個相同的大于等于i的距離，為了方便后續(xù)操作，取平移距離略 大于i較好，這里取平移距離為1.21和所有end-faces半徑屮的最大值。2.1.2建立一個頂點附近的面按上述方法建立好end-faces ,有些頂點的end-faces都在同一側(cè)，這會使得 后面建立凸包時所建立的凸包離該頂點較遠。為了避免這一點，對于原圖中的每 一個頂點，需要在該頂點附近也建立一個多邊形面，多邊形的邊數(shù)取和end-faces 邊數(shù)相同即可，半徑可取該頂點的所有end-faces半徑中的最大值。多邊形的中 點設(shè)立在頂點的位置，其所在平面法向通過下述方法求出。求出這個頂點

21、所有 end-faces的法向的平均值，這個平均值即為上述多邊形所在平面的法向，為了加 快算法的速度，也可以將這個多邊形面沿著它的法向平移一小段距離。2.1.3求凸包現(xiàn)在圍繞每個頂點己經(jīng)建立好了一些多邊形面，包括end-faces和一個在頂 點附近的面。取出這些而的所有頂點，對這些頂點求凸包2,生成的凸包就是 該結(jié)點初始網(wǎng)格的形狀。由2.l1節(jié)屮的算法，所有end-faces上的頂點都在凸包 上，但2.1.2節(jié)屮建立的面的頂點不一定在凸包上，所以生成凸包后還需刪除所 有不在凸包上的頂點，即此時所有度為0的頂點。2.1.4清除與柱子連接的面2.1.3節(jié)中生成的凸包是一個封閉三角網(wǎng)格，但最終凸包要

22、與柱子相連，所 以需要刪除凸包和柱子連接的面，即所有end-faces ±的面。由于每個end-face 都在凸包表面，所以只需刪除所有頂點來自同一個end-face的三角面即可?？梢?在生成end-faces時對每個頂點標(biāo)記它的來源end-face,然后直接遍歷凸包上的 所有面找岀其中所有頂點都來自同一個end-face的面并將它們刪除。§2.2柱子的建立在結(jié)點建立好之后，柱子的建立較為簡單。由于end-faces ±的所有面都已 刪除，所以只需將每兩個相對的end-faces相連，即對每兩個相對的end-faces, 將它們每兩條相對的邊連接成一個長方形的面即

23、可。小結(jié) 這章講述了在柱子是正多棱柱的情況下，當(dāng)用戶輸入柱子的邊數(shù)、半徑后 該如何建立一個封閉u沒有自交的實體化線框圖初始網(wǎng)格，主要解決了如何創(chuàng) 建結(jié)點并使結(jié)點看起來較飽滿的問題。一個止方體線框圖的實體化線框圖初始 網(wǎng)格的建立如圖2所示，其中（a）是初始的正方體線框圖，（b）是end-faces的建 立，（c）是頂點附近的面的建立，（d）是對每個結(jié)點求凸包，（e）是清除結(jié)點與柱 子連接的面，（f）是柱子部分的建立。(d)(f)圖2.1建立初始網(wǎng)格的流程圖三角網(wǎng)格的細分為了使最終生成三角網(wǎng)格自然、光滑，首先需要對于上一章中的初始網(wǎng)格插 入一些點以提高三角網(wǎng)格的精度。而岀于算法效率考慮，一開始生成

24、的網(wǎng)格柱子 橫截面多邊形的邊數(shù)較少，此時三角網(wǎng)格的細分也應(yīng)當(dāng)較粗糙，細分出的三角面 邊長較長，而隨著網(wǎng)格逐漸接近目標(biāo)網(wǎng)格，應(yīng)當(dāng)適量增加整個網(wǎng)格的精度，這時 就需要對三角網(wǎng)格再次進行細分。§3.1初始網(wǎng)格的細分初始網(wǎng)格中頂點較稀疏，精度不高，要生成高精度的網(wǎng)格，必須先對其進行 細分。細分后應(yīng)該沒有過長的邊，所以可以通過限制最長邊的長度來實現(xiàn)。對初 始網(wǎng)格的細分可以分為柱子部分和結(jié)點部分分別實現(xiàn)，但柱子和結(jié)點連接的邊 界（即所有end-faces）要保留，不能進行細分。定義細分后的最長邊長為l。設(shè) 所有end-faces中最長的邊長為im，因為end-faces上的邊不能進行細分，所以l

25、 的取值主要取決于所有end-faces的邊長，且應(yīng)該略大于lm，這里取l為1.5im 較好。3.1.1柱子部分的網(wǎng)格細分柱子部分的細分相對簡單，可以將初始網(wǎng)格中柱子部分的每個長方形面按 圖3的方式進行細分（假設(shè)每個長方形的短邊均為end-faces ±的邊），先將長方 形沿長邊等分成幾個小長方形，再將每個小長方形沿對角線分成兩個小三角形。 其中要保證每個小長方形的斜邊長度不能超過l,取l為1.5im時，為了保證網(wǎng) 格中沒有太小的角度，最好使每個小長方形盡量接近正方形，可以通過下述方法 得到。計算出大長方形的長邊長為i，短邊長為lb，將大長方形的長邊等分為n 份，使大長方形分成n個小

26、長方形，其中門=中1。然后再將所有的小長方形從 對角線處分成兩個小三角形即可，對于每一個柱子，劃分小三角形的方向應(yīng)該相 同。圖3.1柱子上一個面的劃分3.1.2結(jié)點部分的網(wǎng)格細分結(jié)點部分本身是三角網(wǎng)格，只需將每個大三角形分成兒個小三角形即可。這 里采取一個等分長邊的方法，如下所述。其中所有end-faces ±的邊都直接看成不 能再細分的邊，即在下述過程中將end-faces上的所有邊的長度看成是小于l的, 取l = 1.51m時，end-faces上所有邊本身都小于l,故可以不特殊考慮end-faces 上的邊。對每個結(jié)點，遍歷該結(jié)點上的所有三角面，對每個三角面，求出它三條邊的 長

27、度，分別設(shè)為h二12 = ho若三條邊長度都小于等于l,即ln hn bn b，則保留這個三角面，不對 其進行細分。若三條邊中有且僅有一條邊長度大于l,即h >l>i2> i3,則取長度為h 的邊的中點，將該邊等分成兩條邊，三角面的劃分如圖3.2(a)所示。若三條邊中有且僅有兩條邊長度大于l,即h > l2> l > 13,則分別取 長度為h和12的邊的中點，將它們分別等分成兩條邊，三角面的劃分如圖 3.2(b)所示。若三條邊長度均大于l,即h > 12 > 13 > l,則分別取三條邊的中點，將三 條邊均等分成兩條邊，三角面的劃分如圖3.

28、2(c)所示。h(a)(b)h(c)圖3.2三角面的劃分對一個三棱錐線框圖初始網(wǎng)格進行網(wǎng)格細分的結(jié)果如圖3.3所示，其中(a) 為細分前的三角網(wǎng)格，(b)為細分后的三角網(wǎng)格。(a)(b)圖3.3三棱錐線框圖初始網(wǎng)格細分結(jié)果§3.2提高整體網(wǎng)格的精度在進行了第4章結(jié)點自然化的操作，使網(wǎng)格接近于目標(biāo)網(wǎng)格之后，應(yīng)對網(wǎng)格 再次進行細分操作以進一步提高網(wǎng)格的精度。這次的細分和之前的不同的是，柱 子和結(jié)點連接的邊界，即end-faces也要進行細分。細分方法如下，該方法每次 可將網(wǎng)格精度提高一倍，即將最長邊長l縮短一半。先對end-faces進行細分。要將最長邊長l縮短一半，當(dāng)多邊形邊數(shù)不太少

29、的時候，可以近似看做將end-faces的邊數(shù)增加一倍。只需對每個end-faces,在 其所有頂點所確定的圓上，在每兩個相鄰頂點中間再插入一個頂點即可。對于柱子部分，可以刪除原來的柱子，并對新建立的end-faces用2.2節(jié)的 方法重新牛成柱子并采用3.1.1節(jié)中的方法重新進行細分即可，此時，取新的l 為原來的l的一半即可。對于結(jié)點部分，可以采用類似于3.1.2節(jié)中的方法。但由于結(jié)點的邊界部分, 即end-faces被改變，所以不能直接采用3.2節(jié)的方法。每個end-face中的每條 邊都被分成了兩條邊，且當(dāng)多邊形邊數(shù)不太少的時候，新插入的點接近于這條邊 的中點，分成的兩條邊也接近于等分這

30、條邊分出的兩條邊。所以，在采用3.2 節(jié)中的方法時，將原cnd-faccs ±的每一條邊均看成是長邊，且在細分包含這條 邊的三角面時，將這條邊的兩個頂點之間新插入的點看成是這條邊的中點，插入 這個點所分出的兩條邊看成是將這條邊等分后的兩條邊，之后新end-faces ±的 邊都看成是不可再細分的邊。和柱子部分一樣取新的l為原來的l的一半即可。圖3.4是一個實體化線框網(wǎng)格提高精度前和提高精度后的對比圖，(a)為提 咼精丿艾前的網(wǎng)格，(b)為提咼精度后的網(wǎng)格。(a)(b)圖3.4實體化線框網(wǎng)格提高精度前后對比圖小結(jié) 這章解決了牛成高精度網(wǎng)格中必要的一步，網(wǎng)格細分的問題。提岀了一

31、 種針對柱子部分和結(jié)點部分分別操作的細分方法且可以保持柱子和結(jié)點之間用 來連接的end-faces不變，并且提出了一種可以將整體網(wǎng)格精度提高一倍的方法, 在end-faces上加入一倍的點的同時對柱子和結(jié)點部分分別細分。第4章結(jié)點的自然化網(wǎng)格細分可以提高網(wǎng)格的精度但并沒有改變整體網(wǎng)格的外觀，為了使整個 網(wǎng)格看起來更自然、光滑，需要在保持柱子不改變的同吋移動結(jié)點中各頂點的位 置。§4.1用b-mesh的方法迭代b-mesh屮提供了一種通過骨骼球和骨架建立3d模型網(wǎng)格的算法，這里 利用其中的部分算法以達到結(jié)點自然化的目的，需要沿原圖中邊的方向建立一 些虛擬的球再根據(jù)這些球建立一個隱式曲面

32、以確定最終網(wǎng)格的位置最后通過迭 代逼近最終曲面。4.1.1建立虛擬球?qū)τ诿恳粋€結(jié)點，將該結(jié)點對應(yīng)的原線框圖中的頂點設(shè)為0,該結(jié)點上所有 cnd-faccs的中心點分別設(shè)為pi、p2、 、pn，其中n為該結(jié)點的cnd-faccs數(shù)。 分別以這些end-faces的中心點即pi> p2> 、pn為球心建立虛擬的球，設(shè)這 些球為bi、b2> 、bn，這些球的半徑和它們的球心所對應(yīng)的end-faces的半 徑相同，分別設(shè)為rw> r20、rnoo然后再以0點為球心建立一個虛擬 的球，設(shè)這個球為bo,該球的半徑ro是與該結(jié)點的所有end-faces半徑有關(guān)的 函數(shù)，這里取ro =

33、 rmax，其中rmax為該結(jié)點的所有end-faces半徑中的最大值。之后在頂點和各end-faces中點的連線,即0pi> op2、 、opn上,等距創(chuàng) 立一些虛擬的球，且不同連線上和鄰兩個虛擬球球心的距離應(yīng)該基本相同，設(shè)這 個距離為d。設(shè)opj (i = 1,2,，n)的長度為dj,則在0 pi (i = 1,2,，n) 上，需等距地取ni = rai-1個點作為球心。將opi上的這些球除了 bi和bo 外，按球心從pi點到0點的順序排列依次設(shè)為bii、bi2、bg,它們球心的位 置分別設(shè)為pii、pi 、pin，則pij的位置可以用下式表示：p7j = 丄百6。1ru+1這e個球

34、的半徑取決于它們與bj、bo之間的距離以及bj、bo的半徑，設(shè)這m 個球的半徑依次為尺1、尺2、rin，則rij = j ro +一 尺0。1n/4-1“ru+1除此之外，還需在各頂點到各end-faces中心點連線的延長線上也等距地創(chuàng)立一些虛擬球。其中對于任意i (i = 1, 2, ，n), opi的延長線上虛擬球之 間的距離應(yīng)該與opi上的虛擬球之間的距離相等，opi的延長線上虛擬 球總共占的長度dei與4.2節(jié)中常數(shù)q有關(guān)，由4.1.2節(jié)可知這個關(guān)系 dei>ari0，所以可以取dei= arioo設(shè)opi上相鄰兩個虛擬球之間的距 離是，則由上述算法可以推出dj=吐。在opi延長

35、線上以dj為距離等距地n +1取riei個點，其中£g=器，以這g個點為球心，尺為半徑建立g個虛擬球即可。4.1.2根據(jù)虛擬球建立結(jié)點的網(wǎng)格在上一小結(jié)中，已經(jīng)在每一個結(jié)點附近創(chuàng)立了一些虛擬球，這些虛擬球決定 了該結(jié)點的外形，下面需要根據(jù)這些虛擬球確定最終網(wǎng)格。在建立了虛擬球后，b-mesh6中提供了一種算法可以根據(jù)這些虛擬球構(gòu)造 一個隱式曲面。對每一個結(jié)點分別進行操作。取該結(jié)點的所有虛擬球，將這些球從1開始編號， 場函數(shù)怙根據(jù)這些球定義一個標(biāo)量場。首先，對其中的每一個球定義一個 的(1一(紺"尺(4.1)0, r>ri其中：嚴(yán)=(x -+ (y - c)2 + (z-

36、 c*)2(4.2)ri = arj, g是該結(jié)點的第i個虛擬球的半徑，(c',c',c')是第i個虛擬球的球心,x y za是一個大于1的常數(shù)，a的選取會影響到最終網(wǎng)格的形狀。t (刃=t = 01然后，將該結(jié)點處的隱式曲面的定義為：(43)其中t是一個參數(shù)，t控制了隱式曲面離這些虛擬球表面的距離，可以看出t 值越大，隱式曲面越接近虛擬球。由于最終結(jié)點部分要和柱子部分自然相連，所 以應(yīng)該使隱式曲面和虛擬球相切，選定合適的t值即可達到這個效果。但這個隱式曲面不容易直接求出，所以用迭代算法來逼近這個曲面。將第 3章中細分過后的網(wǎng)格看作一個可以移動的曲而s(t),這個曲面將

37、根據(jù)上而定 義的標(biāo)量場進行迭代。移動曲面是2d的移動邊界7的一個擴展?？梢詫⑶?面上每個點的運動軌跡看作時間t的函數(shù)r(t)odx=t)f (久 k, t, )(4.4)dt其中魚表示速度,fl = -空是法向量,t是標(biāo)量場,移動速度函數(shù)f區(qū)k, t,) dt|vt|是一個由位置、法向量、曲率、標(biāo)量場t等決定的有符號的標(biāo)量函數(shù)。其中，s(0) 是初始網(wǎng)格。移動速度函數(shù)f由標(biāo)量場和目標(biāo)值決定，定義如下：f 區(qū) k, t,)=t (刃一 ttarget(4.5)該定義保證了離目標(biāo)位置越遠的點移動速度越快。所以移動曲面網(wǎng)格上的一個頂點妝t)的迭代公式如下：乂(t += x(t) + h區(qū)t)f區(qū))a

38、t(4.6)其中虹是時間步長。進行多次迭代后，網(wǎng)格將逐漸逼近隱式曲面。§4.2結(jié)點的網(wǎng)格光滑對每個結(jié)點，3.2節(jié)和4.1節(jié)中的方法均可能會導(dǎo)致一些網(wǎng)格自交且最終曲 面并不是完全光滑。為了使網(wǎng)格變得光滑，采取一種基于laplace算子的光滑算 法。在離散網(wǎng)格中對于頂點w的laplace算子可以用下式進行近似：1 £l(vi) = d (£v)(4.7)'ven(i)其屮di是頂點vi的度，n(i)是頂點vi鄰域的指標(biāo)集，l值的模越小代表著該點 附近越光滑。所以采取下述迭代公式對網(wǎng)格上的每個頂點進行光滑：vnew = void + 入 l(void)(4.8)

39、其中入是每一步迭代的步長，在0到1之間，vdd是原始頂點的位置，vnew是迭 代后該頂點的位置。該方法相當(dāng)于是每步將每個頂點向其鄰域所有頂點的中心 移動一定距禺0上述光滑算法是僅對結(jié)點進行的，但僅對結(jié)點進行光滑會導(dǎo)致結(jié)點和柱子 z間的連接顯得不自然，所以在執(zhí)行完光滑算法消除自交z后要重新進行上一 節(jié)的操作，在最終在執(zhí)行完上一節(jié)的操作后結(jié)點部分仍然會有一些細微的褶皺， 且結(jié)點和柱子之間的連接很難完全光滑，這時可以對整個網(wǎng)格利用光滑算法進 行光滑，但此時光滑算法會使柱子變細，所以迭代次數(shù)不宜過多。§4.3結(jié)果對一個三棱錐線框圖進行測試，該三棱錐線框圖的所有柱子半徑相等，其中 一開始取柱子

40、橫截面多邊形邊數(shù)為6,進行2次3.2節(jié)中的細分操作，最終柱子 橫截面多邊形邊數(shù)為24。結(jié)果如圖4所示，其中（a）為a = 1.2時生成的實體 化線框圖，（b）為a = 1.5時生成的實體化線框圖?？梢钥吹絘越大，結(jié)點凸起 越明顯，同時結(jié)點內(nèi)側(cè)也越柔和。(a)(b)圖4.1不同a值下生成的三棱錐線框的實體化線框圖下面所描述的三個結(jié)果均是在a = 1.2時，取起始柱子橫截面多邊形邊數(shù)為6,進行2次3.2節(jié)中的細分操作，最終柱子橫截面多邊形邊數(shù)為24的情況下進行測試的。圖4.2是對一個所有柱子半徑相等的止方體線框進行測試的測試結(jié)果。圖4.2正方體線框牛成的實體化線框圖圖4.3是一個對較復(fù)雜線框圖的測

41、試結(jié)果，該線框圖包含連接著多條邊的頂 點，且這些邊之間的夾角較小，并包含一個在線框圖內(nèi)部的結(jié)點，該實體化線框 圖的所有柱子半徑相等。圖4.4是一個柱子半徑不同的結(jié)果。圖4.3個較復(fù)雜的實體化線框圖圖4.4 一個柱子半徑不同的實體化線框圖圖4.5和圖4.6是對兩個邊數(shù)較多的線框圖的實體化模型在不同柱子半徑下的 對比圖，其中圖4.5的參數(shù)選取和之前的相同，圖4.6取起始柱子橫截面多邊形邊 數(shù)為3,進行3次3.2節(jié)中的細分操作，最終柱子橫截而多邊形邊數(shù)為24, a的 取值在整個過程中遞減，c（的幾個取值分別依次為3、2、1.5、1.2,兩圖的所有 柱子半徑均相等。(a)(b)圖4.5不同柱子半徑下字

42、母c的線框圖的實體化結(jié)果，(a)柱子半徑0.01 (b) 柱子半徑0.015圖4.6不同柱子半徑下兔子頭的線框圖的實體化結(jié)果，(a)柱子半徑0.01 (b)柱子半徑0.014中國科學(xué)技術(shù)人學(xué)本科畢業(yè)論文小結(jié) 這章通過迭代算法將結(jié)點以及結(jié)點和柱子連接的部分自然化、光滑化，使 得整個網(wǎng)格看起來自然、光滑。在進行完本章的操作后可以再進行3.2節(jié)中的操 作將網(wǎng)格細分，之后對于細分的網(wǎng)格再重新進行本章的操作，重復(fù)幾次后可以使 網(wǎng)格精度提高。這種操作可以提高整個算法的效率。第5章總結(jié)與展望木文提出了一種根據(jù)線框圖生成柱子為圓柱的實體化線框圖的算法。該算 法可以根據(jù)輸入的圓柱半徑自動生成各個結(jié)點，生成的結(jié)點

43、和結(jié)點與柱子的連 接部分都是光滑的，這樣可以使整個網(wǎng)格看起來自然、美觀。但這個算法還有很 多問題，并不能很好的適用于所有情況。該算法對于夾角較小的兩條相鄰邊的適應(yīng)性不是很好。對于較小的角度，往 往需要在迭代時候反復(fù)做很多次光滑操作才能消除網(wǎng)格的白交。但光滑算法本 身對4.1節(jié)的算法有抵消作用，所以這會大大增加整個過程的時間，對于特別小 的角度，即使進行很多次光滑操作也很難避免網(wǎng)格自交。且由于角度小，會使最 初創(chuàng)立的結(jié)點過大，這大大增加了迭代到目標(biāo)網(wǎng)格的難度。對于避免4.1節(jié)算法 所導(dǎo)致的網(wǎng)格自交，可以用courant-friedrichs-lewy (cfl)穩(wěn)定性條件10求 出每一步的最大步

44、長再進行迭代。對于柱子粗細不同的情況，尤其是柱子粗細差異較大的情況，當(dāng)原線框圖網(wǎng) 格都在較細的柱子所對應(yīng)的邊的一側(cè)時，與這根柱子相對應(yīng)的結(jié)點會產(chǎn)生凸起, 如圖5所示。圖5.1柱子粗細不同時結(jié)點產(chǎn)生凸起由于每個結(jié)點連接的柱子個數(shù)、相對位置都不相同，所以對于相同的a值,中國科學(xué)技術(shù)人學(xué)本科畢業(yè)論文不同的結(jié)點需要的t值也不同，使用相同的t值可能會使有些結(jié)點與柱子相連 看上去較自然，有些看上去不自然，可以考慮對不同的結(jié)點手動輸入不同的t 值或者自動選擇結(jié)點附近一些柱子上的點，根據(jù)這些點的t值，粗略計算該結(jié) 點的t值。中國科學(xué)技術(shù)人學(xué)本科畢業(yè)論文參考文獻1 e. akleman, j chen, v.

45、srinivasan. an interactive shape modeling system for robust design of functional 3d shapes. proceedings of acadia 248-257. 2001.2 c. barber, d. dobkin, h. huhdanpaa the quickhull algorithm for convex hulls. acm transactions on mathematical software (toms). 22(4):469-483. 1996.3 e. catmull, j. clark. recursively generated b-spline surfaces on arbitrary topological meshes. computer-aided design. 10(6):350-355. 1978.4 u. caturano, c. sanseverino. solid modeling by low-cost hardware and software: the crystal palace's node. proceedings ofecaade confere