數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)圖形學(xué)中的應(yīng)用

摘要：計(jì)算機(jī)圖形的產(chǎn)生對(duì)于生成、處理和顯示有關(guān)計(jì)算機(jī)的基本原理和算法起到了至關(guān)重要的作用?；诖?，計(jì)算機(jī)可以給使用者提供大量的、具有強(qiáng)烈視覺沖擊力的漂亮畫面。隨著計(jì)算機(jī)技術(shù)和計(jì)算機(jī)圖形學(xué)的不斷發(fā)展，數(shù)據(jù)結(jié)構(gòu)和計(jì)算機(jī)圖形學(xué)的研究逐漸增多。文章從計(jì)算機(jī)圖形學(xué)的角度出發(fā)，對(duì)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)圖形學(xué)中的應(yīng)用進(jìn)行了分析，以期為相關(guān)研究人員提供幫助。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu);計(jì)算機(jī)圖形學(xué);應(yīng)用

中圖法分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A

Application of data structure in computer graphics

XIA Chunmei

（Baoshan University，Baoshan，Yunnan 678000，China）

Abstract：The generation of computer graphics plays a vital role in generating， processing and displaying the fundamental principles and algorithms of computers. Based on this， the computer can provide users with a large number of beautiful pictures with strong visual impact. With the continuous development of computer technology and computer graphics， the research on data structure and computer graphics is gradually increasing. From the perspective of computer graphics， this paper analyzes the application of data structure in computer graphics， in order to provide help for related researchers.

Key words： data structure， computer graphics，application

計(jì)算機(jī)圖形學(xué)是現(xiàn)代信息科技的產(chǎn)物，也是數(shù)據(jù)結(jié)構(gòu)的重要組成部分。計(jì)算機(jī)圖形學(xué)是在信息技術(shù)的基礎(chǔ)上，通過對(duì)數(shù)據(jù)的綜合和分析，把數(shù)據(jù)轉(zhuǎn)換成圖像[1]。計(jì)算機(jī)圖形學(xué)技術(shù)改變了資料的顯示方式，并廣泛應(yīng)用于各個(gè)行業(yè)，取得了事半功倍的效果。圖像的信息比較復(fù)雜，數(shù)據(jù)的關(guān)系會(huì)影響圖像的最終形態(tài)[2]。為了準(zhǔn)確地產(chǎn)生圖像信息，就需要對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行不斷優(yōu)化。

1幾何建模技術(shù)的應(yīng)用

1.1拓?fù)浜蛶缀涡畔?/p>

幾何建模技術(shù)在計(jì)算機(jī)圖形學(xué)中占有舉足輕重的地位。幾何建模技術(shù)是結(jié)構(gòu)和數(shù)據(jù)計(jì)算的核心，它能構(gòu)建數(shù)學(xué)模型，精確地設(shè)計(jì)幾何結(jié)構(gòu)[3]。

在計(jì)算機(jī)中建立幾何模型，首先要將資料進(jìn)行集成，然后對(duì)其進(jìn)行三次構(gòu)造，以不斷提升資料處理效率。數(shù)據(jù)的精確程度愈高，則幾何結(jié)構(gòu)愈具科學(xué)性。幾何建模技術(shù)的應(yīng)用不僅要采集圖像信息，還要采集非圖像信息。以幾何信息為例，三維物體的幾何信息是由點(diǎn)、線、面三種信息組成的龐雜信息結(jié)構(gòu)，必須捕獲空間數(shù)據(jù)，并依據(jù)坐標(biāo)系統(tǒng)進(jìn)行準(zhǔn)確定位。在確定數(shù)據(jù)區(qū)域時(shí)，應(yīng)采用數(shù)學(xué)方法對(duì)坐標(biāo)進(jìn)行記錄。對(duì)于曲線、表面等采用多種方法進(jìn)行擬合，以維持其原始形態(tài)[4]。三維模型在實(shí)際操作中經(jīng)常會(huì)發(fā)生變形，需要對(duì)三坐標(biāo)的偏移、旋轉(zhuǎn)等進(jìn)行跟蹤。由于采用矩陣操作可以捕獲變化的數(shù)據(jù)，所以需要采用矩陣的方法。在定義形態(tài)時(shí)，不能只依賴幾何信息，而要將拓?fù)湫畔⒌染C合起來，使多種信息相互融合。

在拓?fù)湫畔⒅?，幾何形狀的拓?fù)湫畔c(diǎn)線和平面的聯(lián)系。其中，點(diǎn)線面的關(guān)系分為三種：一是連接，二是接近，三是邊界。具體而言，在點(diǎn)線面中其實(shí)有9種不同的結(jié)構(gòu)形式。以立方體而言，在拓?fù)潢P(guān)系中，需要依靠符號(hào)、數(shù)據(jù)、箭頭等識(shí)別和歸納拓?fù)湫畔?。根?jù)需要，可以調(diào)整拓?fù)潢P(guān)系。通常情況下，為了保證拓?fù)浣Y(jié)構(gòu)的信息一一對(duì)應(yīng)，必須找到兩個(gè)或更多的拓?fù)潢P(guān)系。如果沒有足夠的拓?fù)湫畔?，則需要通過幾何信息來完成。無論是幾何、拓?fù)涞刃畔?，都能用?shù)學(xué)方法得到，也能用運(yùn)算推理得到。實(shí)際上，數(shù)學(xué)推導(dǎo)都是耗時(shí)的，互相推演會(huì)讓數(shù)據(jù)處理變得遲緩。如果這種關(guān)系太過復(fù)雜，就會(huì)占用很多的存儲(chǔ)器。所以，在構(gòu)造幾何形狀時(shí)，必須做好拓?fù)潢P(guān)系的調(diào)整和數(shù)據(jù)結(jié)構(gòu)的優(yōu)化工作。

1.2幾何模型和數(shù)據(jù)結(jié)構(gòu)

常用的模型有線框模型、表面模型和實(shí)體模型。以線框模型為例，它依賴線框架來表現(xiàn)形狀，如表示一個(gè)立方體的過程中，可以使用頂點(diǎn)和邊界，將頂點(diǎn)的坐標(biāo)信息存儲(chǔ)在計(jì)算機(jī)中，然后將這些頂點(diǎn)連接在一起，組成一個(gè)線框，從而建立一個(gè)三維模型。與其他模型相比，該模型具有數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單、數(shù)據(jù)量小以及對(duì)儀器總體性能的要求較低的特點(diǎn)。線框模型中的數(shù)據(jù)信息易于加工，難以處理，因此點(diǎn)和線是建立三維模型的關(guān)鍵。立體外形與棱線相交，從而便于平面立體視圖的輸出。平面立體圖的使用非常廣泛，在進(jìn)行形態(tài)行為的仿真時(shí)，往往需要建立線框模型，并將其輸出。

線框模型也有缺陷，即線框模型只包含點(diǎn)和線的信息，不能將平面信息和線段結(jié)合起來，所以很少用于物理研究。雖然表面模型中有一個(gè)線框架模型，但它添加了平面信息，可以輸出截面?；趯?duì)點(diǎn)和線的描述，在曲面模型中加入表面結(jié)構(gòu)，使數(shù)據(jù)結(jié)構(gòu)更加合理。在曲面模型中，三維形狀的每一條邊都被劃分為不同的數(shù)字。曲面模型依然是基于線框的模式，它增加了指針內(nèi)容，使線條相互聯(lián)系。三表結(jié)構(gòu)改變了計(jì)算機(jī)的傳統(tǒng)存儲(chǔ)模式，極大地節(jié)約了內(nèi)存[5]。但是，由于數(shù)據(jù)的信息量很大，因此在檢索過程中會(huì)花費(fèi)很多的時(shí)間。與其他模型相比，曲面模型的數(shù)據(jù)處理方式比較簡(jiǎn)單，交線和剖面線問題能夠迅速地求解，但是每個(gè)模塊之間的聯(lián)系卻很少—只有一個(gè)面塊，無法完整地解釋形狀的位置。例如，實(shí)體模型超越了引線框架和曲面模型，定義了實(shí)體的實(shí)心，建立了一個(gè)全新的數(shù)據(jù)模型。在建立模型時(shí)，首先在物體的側(cè)面找出一個(gè)圓點(diǎn)，再給出一個(gè)外法向量，并對(duì)其進(jìn)行解釋。在此基礎(chǔ)上，對(duì)實(shí)體進(jìn)行描述，將大量數(shù)據(jù)信息存儲(chǔ)在三表結(jié)構(gòu)中。與其他模型相比，該模型在數(shù)據(jù)結(jié)構(gòu)形式、數(shù)據(jù)集成、物理參數(shù)計(jì)算等方面得到了改善。

2表示數(shù)據(jù)結(jié)構(gòu)的方法

在描述形狀和產(chǎn)生復(fù)雜形狀時(shí)通常需要使用邊界法。邊界法主要用輪廓線劃分，確定輪廓線以表達(dá)立體圖像。三維實(shí)體可以采用邊界的形式來表達(dá)，但是必須對(duì)數(shù)據(jù)的結(jié)構(gòu)進(jìn)行分級(jí)管理，并對(duì)其進(jìn)行分層記錄。數(shù)據(jù)結(jié)構(gòu)包括體表、面表、環(huán)表等，將體表的點(diǎn)線面融入數(shù)據(jù)結(jié)構(gòu)中，可以使體表的外形更加完整。在數(shù)據(jù)結(jié)構(gòu)中，拓?fù)湫畔⒑蛶缀涡畔⒌恼Z義一致—既是獨(dú)立的，又是相互關(guān)聯(lián)的。邊界法是一種十分普遍的方法，許多技術(shù)人員在進(jìn)行幾何建模時(shí)，往往會(huì)選擇邊界法。

美國學(xué)者將翼緣結(jié)構(gòu)引入造型體系中，以使其更好的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的建模。翼緣結(jié)構(gòu)是于二十世紀(jì)七十年代提出的，它的研究對(duì)象是各種不同的多面體。翼緣結(jié)構(gòu)的核心在于如何處理各邊間的關(guān)系，其中，邊是幾何形狀中的一個(gè)重要元素。翼緣結(jié)構(gòu)中，邊與面之間的關(guān)系密切，兩側(cè)各有一個(gè)鄰面，而四個(gè)邊的頂點(diǎn)相連。在采用翼邊結(jié)構(gòu)時(shí)，需要將幾何形狀的信息（如頂點(diǎn)信息、邊面信息等）存儲(chǔ)起來，并對(duì)其進(jìn)行記錄。翼側(cè)結(jié)構(gòu)再現(xiàn)了三個(gè)維度的結(jié)合規(guī)則，從而可以在訪問過程中迅速獲取有價(jià)值的信息。通常采用的是雙鏈存儲(chǔ)格式，它可以將數(shù)據(jù)進(jìn)行分區(qū)，并將其分成不同的級(jí)別。并且，通過跟蹤節(jié)點(diǎn)，能夠準(zhǔn)確地確定數(shù)據(jù)的位置。在確定形狀參數(shù)后，計(jì)算機(jī)可以實(shí)現(xiàn)三維形狀的自動(dòng)生成和構(gòu)造。邊框結(jié)構(gòu)具有更強(qiáng)的數(shù)據(jù)處理能力，但是所占用的空間更大。而采用雙三表結(jié)構(gòu)可以改進(jìn)機(jī)翼結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)，并在某種程度上減少了數(shù)據(jù)信息的存儲(chǔ)空間，使其具有廣闊的應(yīng)用前景。

3計(jì)算機(jī)圖形學(xué)中數(shù)據(jù)結(jié)構(gòu)的應(yīng)用

3.1幾何建模中數(shù)據(jù)結(jié)構(gòu)的應(yīng)用

幾何建模是計(jì)算機(jī)輔助設(shè)計(jì)中的一個(gè)重要環(huán)節(jié)，它的主要作用是建立對(duì)象模型，并將其轉(zhuǎn)化為數(shù)據(jù)，從而達(dá)到對(duì)圖形的精細(xì)調(diào)整，更好地為使用者所掌握和應(yīng)用。幾何建模技術(shù)主要包括幾何圖形的呈現(xiàn)、幾何形體的計(jì)算、幾何形體的構(gòu)造。隨著社會(huì)經(jīng)濟(jì)和科技的發(fā)展和進(jìn)步，計(jì)算機(jī)圖形圖像處理技術(shù)得到了迅速發(fā)展。同時(shí)，它的應(yīng)用范圍也得到了很大的擴(kuò)展。其在建筑設(shè)計(jì)、數(shù)控設(shè)計(jì)、機(jī)械設(shè)計(jì)、室內(nèi)設(shè)計(jì)、服裝設(shè)計(jì)等領(lǐng)域都起到了關(guān)鍵作用。

3.1.1立體外形基礎(chǔ)信息

首先，使用計(jì)算機(jī)建立一個(gè)立體圖形的展示模型，當(dāng)計(jì)算機(jī)要讀取3D 圖形的資料時(shí)，必須要有辨識(shí)的能力。所以，必須用計(jì)算機(jī)來定義和計(jì)算三維形狀，以便輕松地讀取和修改相關(guān)數(shù)據(jù)，并在圖形的加工中進(jìn)行多種處理，從而保證形狀的完整性和精確度。在此過程中，為了更好地完成對(duì)圖像的控制，還必須提供非圖像的重要信息。

（1）三維形狀的幾何資料

幾何學(xué)信息可以表示歐氏空間中三維立體圖形的“點(diǎn)-線”平面的尺寸和坐標(biāo)關(guān)系。一般通過數(shù)學(xué)方法，在特定的坐標(biāo)系中標(biāo)注和顯示三維物體的幾何信息，并用坐標(biāo)值代表這些點(diǎn)，這些點(diǎn)之間有許多條線，這些線線相互連接，構(gòu)成了不同的平面。在確定三維形體的轉(zhuǎn)動(dòng)、縮放、移動(dòng)、變化后，可以很容易地用集合體的變化描述三維形體，從而更容易把握三維形體。

（2）立體形狀的結(jié)構(gòu)特征

僅以幾何信息來描述立體形態(tài)并不完整、精確，托普信息是立體形態(tài)信息中的重要組成部分。托普信息實(shí)際上是一種關(guān)于三維物體的連接、邊界關(guān)系和相鄰關(guān)系的描述。三維形態(tài)的三個(gè)基本結(jié)構(gòu)信息之間的聯(lián)系共計(jì)九種從屬關(guān)系，囊括了所有的拓?fù)潢P(guān)系。在實(shí)際應(yīng)用中，可以根據(jù)需要選取合適的拓?fù)浣Y(jié)構(gòu)。一般來講，一個(gè)完整的立體圖形包含兩種或更多的拓?fù)潢P(guān)系信息。由此可以看出，三維圖形的拓?fù)渑c幾何信息之間有著緊密的聯(lián)系，如果某一種信息不存在，那么另一種信息就毫無意義。不同的拓?fù)浣Y(jié)構(gòu)所需的幾何信息也有所不同。

3.1.2三維立體幾何建模

（1）線型框架。由三個(gè)面的頂點(diǎn)和邊構(gòu)成的形狀叫做線框架。這是計(jì)算機(jī)在制作立方體時(shí)所采用的方法，它相對(duì)簡(jiǎn)單，只要將立方體的頂點(diǎn)和邊緣輸入計(jì)算機(jī)中，就可以繪制出一個(gè)立體的立體圖形，這就可以很容易地將線框圖繪制出來。它的數(shù)據(jù)結(jié)構(gòu)很簡(jiǎn)單，但卻無法解決大多數(shù)復(fù)雜的問題，如處理求交和消隱等問題。

（2）曲面形狀。以線框架模型為基礎(chǔ)，將平面信息添加到平面上，就可以構(gòu)成曲面模型。一般情況下，有兩種方法可以創(chuàng)建曲面模型，一是“頂點(diǎn)+邊+面”的方法，即將上述信息添加到線框模型上;二是用一根新的指針，將所有的線條串聯(lián)在一起，這可以得到更多的信息，這種方法比較復(fù)雜，可以用三個(gè)表格來表達(dá)。

（3）實(shí)體化模式。實(shí)體模型是以 P 點(diǎn)為平面中心，添加實(shí)體（圖1）。實(shí)體模型的作用就是確定物體的具體位置。

3.2應(yīng)用數(shù)據(jù)結(jié)構(gòu)“消隱”的方法

為了使計(jì)算機(jī)圖形不再具有多重含義，而且要充分表現(xiàn)出真實(shí)的感覺，在立體圖像中，必須去除無形的線條和表面，使其表現(xiàn)得更為精確。這種計(jì)算機(jī)繪制方法稱為“消隱”。“消隱”技術(shù)主要涵蓋數(shù)據(jù)結(jié)構(gòu)、圖形繪制和“消隱”算法等。

消隱算法：讓物體的三維面朝向物體的方向進(jìn)行計(jì)算，然后根據(jù)計(jì)算結(jié)果，可以確定物體的前后方向。而朝后是看不見的，所以不必把它的邊畫出來。

數(shù)據(jù)結(jié)構(gòu)：面表、環(huán)表、頂點(diǎn)表是“消隱”數(shù)據(jù)的重要組成部分。立體形體的不同面的棱角數(shù)量被存儲(chǔ)在面環(huán)表格中，如果從形體內(nèi)部觀察，構(gòu)成身體各面的頂點(diǎn)在立體坐標(biāo)系統(tǒng)中的坐標(biāo)值被存儲(chǔ)在一個(gè)面環(huán)表格中。

圖形渲染：在完成“消隱”算法和數(shù)據(jù)結(jié)構(gòu)后，就需要編寫程序來進(jìn)行“消隱”運(yùn)算。

4結(jié)論

數(shù)據(jù)結(jié)構(gòu)是指由計(jì)算機(jī)組織和儲(chǔ)存數(shù)據(jù)。在計(jì)算機(jī)圖形圖像技術(shù)出現(xiàn)以前，處理數(shù)據(jù)結(jié)構(gòu)的方式是以符號(hào)為主導(dǎo)，而在計(jì)算機(jī)圖形圖像技術(shù)問世以后，資料結(jié)構(gòu)成為關(guān)鍵。這對(duì)計(jì)算機(jī)圖形學(xué)的產(chǎn)生具有重大的影響。隨著計(jì)算機(jī)圖形圖像技術(shù)的發(fā)展，其將會(huì)廣泛應(yīng)用于社會(huì)的各個(gè)方面，因此在計(jì)算機(jī)圖形學(xué)中數(shù)據(jù)結(jié)構(gòu)將會(huì)得到廣泛應(yīng)用。

參考文獻(xiàn)：

[1]王艷芳，鞏曉秋.計(jì)算機(jī)圖形學(xué)與圖形圖像的處理技術(shù)研究[J].科技資訊，2022，20（4）：16?18.

[2]周保林，孔浩，張子鋒，等.簡(jiǎn)析計(jì)算機(jī)圖形學(xué)中數(shù)據(jù)結(jié)構(gòu)的應(yīng)用[ J].計(jì)算機(jī)編程技巧與維護(hù)，2021（4）：132?133+145.

[3]劉敏.基于計(jì)算機(jī)圖形學(xué)和圖形圖像處理技術(shù)有關(guān)思考[J].電子商務(wù)，2020（12）：76?77.

[4]周曉青.計(jì)算機(jī)圖形學(xué)中數(shù)據(jù)結(jié)構(gòu)的應(yīng)用途徑[J].計(jì)算機(jī)編程技巧與維護(hù)，2019（11）：134?136.

[5]申作林，沙晨明.三角網(wǎng)格文件的格式處理在3D 打印技術(shù)中的應(yīng)用[J].黑龍江科學(xué)，2017，8（2）：18?22+25.

作者簡(jiǎn)介：

夏春梅（1979—），本科，講師，研究方向：計(jì)算機(jī)教育。