第7章圖形的表示圖形的表示方法一直是計算機圖形學關注的主要問題。在計算機圖形學發展的旱期，計算機圖形系統的性能較差，線框模型是表示三維物體的主要方法。線框模型僅僅通過定義物體邊界的直線和曲線來表示三維物體，其特點是模型簡單目運算速度較快，但由于每一條直線或四線都是單獨構造出來的，不存在面的信息，因此三維物體信息的表示不全面，在許多場合不能滿足要求。事實上，研究表示復雜形體的模型與數據結構是計算機造型等技術的關鍵。經過近20年的發展，買體的邊界表示法、掃描表示法、構造的實體幾何法及八叉樹表示法等已經發展成熟。圖形的表示方法是研究如何利用計算機圖形系統采表示、控制、分析和輸出三維形體，是計算機圖形學的一個重要研究領域，它不但是CAD/CAM和CIMS系統的核心技術，還是實現計算機輔助設計的技術基礎。本章將重點學習實體的邊界表示及其數據結構，包括圖形表示的基本概念l掃描表示法、構造的實體幾何法、八叉樹表示法。7.1、實體與圖形7.2、實體表示的三種模型7.3、邊界表示法7.4、掃描表示法7.5、構造的實體幾何法7.6、八叉樹表示法7.1實體與圖形實體的定義圖形的基本元素圖形的幾何信息與拓撲信息直至20世紀70年代末期，關于三維物體的表示和構造并未建立起嚴密的理論，多數情況下靠用戶來檢查物體模型的有效性、惟一性和完備性。隨著模型復雜程度的提高，以及實體模型作為計算機輔助設計中某些應用的輸入而加以運算和處理，使得通過人的干預來檢查模型的有效性變得越來越困難。要想通過計算機表示、構造一個實體，首選必須對什么是實體右一個確切的定義，并據此檢查所構造的實體的有效性。什么是客觀存在的有效實體呢？有效實體一般具有一定的形狀、封閉的邊界或表面，內部連通，占據有限的空間，經過運算后，仍是有效的物體。美國沃爾克爾（H.B.Voelcker）及雷契切（A.A.G.Requicha）等人基于點集拓撲的理論，認為三維空間中的物體是空間中點的集合。從點集拓撲的領域概念出發，通過定義點集的閉包給出正則集的定義。組成三維物體的點的集合可以分為內部點和邊界點兩部分，即由內點和邊界點共同組成。由內部點構成的點集的閉包就是正則集。三維空間中點集的正則集就是三維正則形體，也就是有效的實體。數學中的點、線、面是其所代表的真實世界中的對象中的一種抽象，它們之間存在著一定的差距。例如，數學中的平面是二維的，它沒有厚度，體積為0；而在真實世界中，一張紙無論多么薄，它也是一個三維體具有一定的體積。這種差距造成了在計算機中以數學方法描述的形體可能是無效的，即在真實世界中可能不存在。盡管在有的情況下要構造無效形體，但用于計算機輔助設計與制造系統設計生產的形體必須是有效的，所以在實體造型中必須保證實體的有效性，原則上的標準是要求“客觀存在”。7.1.2圖形的基本元素構成三維實體的點、線（邊）、面、環、體是典型的層次結構，如圖7.1所示。圖7.2（a）是構成圖形的基本元素：點、線（邊）、面、環、體；圖7.2（b）也是構成圖形的基本元素：環。

點是最基本的0維集合元素，分為端點、頂點、交點、切點和孤立點等。邊的端點稱為點，點不能出現在邊的內部，也不能孤立地位于物體的內、物體外或面內，頂點是（面邊界）中兩條不共線的線段的交點。在形體定義中一般不允許存在孤立點。點是幾何造型中的基本元素，自由曲線、曲面或其他形體均可用有序的點集表示。用計算機存儲、管理、輸出形體的實質就是對點集及其連接關系的處理。

邊是一維幾何元素，是兩相鄰面的基本交線，直線由其端點確定，曲線是由一系列數據點和控制點表示的，規則曲線可以由顯示或隱式方程表示。一條邊有且只有兩個相鄰面。兩個端點確定一條邊，這兩個端點分別稱為該邊的起點和終點。假設Q是一個形體，E（Q）是形體的邊的集合，則在ЭQ（形體的邊界）中E（Q）是滿足下列條件的所有線段的集合：邊e的兩個端點屬于V（Q）（所有頂點的集合）；邊e中沒有一個內部點屬于V（Q）；邊e上每個點都有兩個不同的面，即存在兩個面使得邊形體Q的邊框線WF(Q)是由有序對（V(Q),E(Q)）所組成的。

面是形體上有限非零的區域，可由一個外環河若干個內環確定其范圍。一個面可無內環，但必須有且只有一個外環，即R3中非空、連續、共面切封閉的子集，稱之為面F，其邊界（記為ЭF）是有限條線段的并集，Pt表示含有F的惟一平面。面是形體表面的一部分，切具有方向性。面有正面、反面，一般外法線方向表示該面得正向，若一個面得外法矢量向外，則此面是正向面；反之，則為反向面。區分正向面和反向面在面與面求教交、交線分類、真實圖形顯示等方面都很重要。在幾何造型中常有平面、二次曲面、雙三次參數曲面等形式。環是有序的有向邊組成的面得封閉邊界。環中的邊不能相交，相鄰的邊共享一個端點。環有內、外之分，確定面的最大外界面得環稱為外環，通常其邊按逆時針方向排序，而把確定面中內孔或凸臺邊界的環稱為內環，其邊與相應外環排序的方向相反，通常按順時針方向排序。按這種方式定義，在面上沿著邊的方向前進，面得內部始終在走向的左側。

體是由封閉表面圍成的有效空間，是三維幾何元素；一個形體Q是空間中非空、有界的封閉子集。其邊界（記為ЭQ）是有限個面得并集，而外殼是形體的最大邊界。一個單位立方體可以定義為其中一個表面可表示為必須注意：并沒有規定形體必須是一個連續的封閉集合，目的是為了擴大幾何造型的域，使得形體可以由不連續的體素組成。具有有限個參數，且簡單的連續封閉的形體稱為體素，如長方體、圓柱體、圓錐、球、環等。集合{P|F(P)<=0}稱為半空間，其中P為R3中的一點，F為一個平面，當F=0時，表示一個平面，這個平面的半空間可以由定義的平面加上在平面某一側的所有點組成。顯然一個長方體可以看成是6個平面半空間的交（圖7.2（d））。7.1.3圖形的幾何信息與拓撲信息線框模型在表示三維空間中的物體時會出現圖形的幾何信息和拓撲信息丟失等問題。圖形對象中存在大量的圖形信息和非圖形信息，他們是正確表示圖形對象的基本信息。圖形信息又包括幾何信息和拓撲信息，幾何信息是指圖形的幾何分量（如點、邊、面）在三維空間的位置和大小的信息，用來表示形體的幾何性質和度量關系；拓撲信息則是指組成形體的基本圖形元素的幾何分量的數量及其相互之間連接關系的信息，用來表示形體之間的連接關系；非圖形信息是指圖形對象的線型、顏色、亮度以及與該圖形對象相對應的體積、比重、質量等物理信息。在這里，我們只討論圖形的幾何信息與拓撲信息。1.圖形的幾何信息一個圖形的幾何信息是指構成幾何圖形的各幾何分量的數學表達式及各幾何分量間的相互關系。幾何信息主要包括對組成圖形的基本圖形元素及其相互關系的不睡和描述。點是0維圖形基本元素，可不是為三元組（x,y,z）;直線式1維基本圖形元素，可用直線方程表示為平面可用平面方程表示為二次曲面可用二次曲面的一般方程來描述：對一般的自由曲面，常用coons曲面、Bezier曲面、B樣條曲面及他們的線性組合來表示。值得注意的是，僅僅將組成三維形體的各種基本圖形元素表示出來是不夠的，圖形對象的幾何信息中還包括限定圖形對象范圍的各類圖形元素的邊界條件，圖形元素的數學表示與邊界條件構成圖形對象的幾何信息，在實際應用中，經常要把幾何分量的數學表達式相應的邊界條件結合起來應用。用數學方程表示圖形的圖形表示方法，便于計算機進行處理。在實際的圖形表示中使用最多的是圖形的參數方程表示法。對于不規則圖形，因無法用方程描述，常常采用各種近似方法。此外，用方程表示圖形只刻畫了圖形的形狀，而對于其他屬性則需要另外的說明。一般地，畫出了形體的棱線與輪廓線就能惟一地將圖形表示出來。如圖7.3，8個頂點可以定義一個長方體，但還不足以識別他，如果定義了棱線，則無論怎樣放置長方體都能惟一的不是他。這種用一組輪廓線表示形體的模型就是線框模型。對于多面體，由于其輪廓線和棱線通常是一致的，所以多面體的線框模型更便于識別（如圖7.4）。但對于非平面多面體，如圓柱、球等形體，其輪廓線隨觀察角度的改變而改變，無法用一組固定的輪廓線來表示他們（如圖7.5）。線框模型與形體之間不存在一一對應關系，他僅僅通過給定的輪廓線約束所表示形體之間的邊界面，而在輪廓線之間的部分，形體的表面可以任意變化。沒有形體的表面信息，是不適合真實感的現實的，并且還可能是不是的形體產生二義性。根據不同的應用需要，對幾何信息的要求也不同。例如，在矢量式輸入輸出設備中，以描述輪廓線為主，實體中的頂點的幾何信息最為重要；在光柵掃描式的輸入輸出設備中，主要是處理明暗度和陰影圖，面的幾何信息較為重要。但是。僅用幾何信息來描述幾何圖形還不夠充分，常會出現幾何實體表示上的二義性或多義性。表示一個實體除了需要幾何信息外，還需要提供幾何分量之間的相互連接關系，即拓撲信息。2.圖形的拓撲信息平面多面體是指表面由平面多邊形構成的三維物體，是實體中最常見、應用的最廣泛的一種，它也可以用來近似地表示曲面體。在具有二維流行性質的平面多面體中，每一條邊連接兩個面，且僅連接兩個面。簡單多面體指的是那些經過連續的幾何形變可以變換為一個球的多面體，也就是與球拓撲等價的那些多面體（如圖7.6）。實體可以采用詳細記錄構成物體的多有幾何元素——域、殼、體、面、環、邊、點的幾何信息及其相互連接關系的拓撲信息的層次、拓撲結構方法來表示。幾何信息形成物體邊界表示的“骨架”，而物體的拓撲關系則猶如附著在這“骨架“上的肌肉。通常，多面體在頂點、棱邊和面這三類元素之間共有點-點、點-線、點-面；線-點、線-線、線-面；面-點、面-線、面-面等9種不同類型的拓撲關系，如圖7.7所示，即在這里符號“-->“表示指針，即可以從它的左端求出它的右端。例如，V-->{e}表示由一個頂點找出相交于此頂點的所有邊，而F-->{e}則表示由一個面找出該面所有的邊，等等。根據不同的需要，對拓撲關系的要求也不一樣。對矢量式圖形系統，可由這些拓撲關系知道如何從頂點連接成邊、面等幾何圖元；在線、面消隱算法中，希望知道面得相鄰性，即F

{F};在實體拼合算法中，需要知道頂點的鄰接面，即V

{F}。7.2實體表示的三種模型形體在計算機中常用線框模型、表面模型和實體模型三種模型來表示。線框模型是在計算機圖形學和CAD、CAM領域中最早用來表示形體的模型，并且至今仍在廣泛應用。線框模型是用頂點和棱邊表示形體，其特點是結構簡單，易于理解，并是表面和實體模型的基礎。如前所述，用線框模型表示形體時曲面的輪廓線無法隨視角的變化而改變；線框模型無法給出全部連續的幾何信息，只有頂點和棱邊，不能明確地定義給定的點與形體之間的關系，以致不能用線框模型處理計算機圖形學和CAD、CAM領域中的多數問題，如圖7.8所示。線框模型的優點：（1）結構簡單，設計書內部易于表達和處理；（2）模型所需要的幾何信息就是線段端點坐標。線框模型的缺點是：（1）有二義性，無深度信息：（2）不便于用作幾何形狀的通用表達形式（形體內部）：（3）不能表達表面上點的局部屬性。表面模型是用有向棱邊圍成的有限區域來定義立體的表面．由面的集合來定義形體，圖7．9說明了用表面模型定義形體的方法。表面模型是在線框模型的基礎上．增加有關面、邊(環、邊)信息以及表面特征、棱邊的連接方向等內容。從而可以滿足面與面求交、線面消隱、明暗色彩處理、數控加工等應用問題的需要。但利用表面模型友示形體時，存在不能明確形體與表面關系的問題，表面模型沒有確定形體究竟枉表面的哪一側。圖7.10為表面模型的一個例子。在表面模型的基礎上，實體模型近一步明確定義了面與實體的關系。實體模型和表面模型的主要區別在于實體模型定義了表面外環的額棱邊方向（見圖7.11）.計算機中表示形體，通常用線框、表面和實體三種模型。線框模型和表面模型保存的三維形體信息都不完整，只有實體模型才能夠完整地、無歧義地表示三維形體，如表7.1所示。形體表示的線框、表面和實體模型是抽象的概念模型，并不反映形體在計算機內部的具體表示方式。在世模型的表示中，出現了許多方法，基本上可以分為空間分解表示（單元枚舉、八叉樹分解、單元分解等）、構造表示（CSG）和邊界表示（B-rep）三大類。構造表示是按照生成過程來定義形體的方法，包括掃描表示、構造實體幾何表示和特征表示三種。從使用的角度看，形體表示以特征表示和構造的實體幾何表示（CSG）較為方便；從計算機對形體的存儲管理和操作運算角度看，以邊界表示（B-rep）最為實用。在這一節，我們將介紹邊界表示法、掃描表示法、構造的實體幾何表示法、八叉樹表示法等4種實體的表示方法。7.3變界表示法實體的邊界表示(B-rep)就是按照體、面、環、邊、點的層次，詳細記錄構成形體的所有幾何元素的幾何信息及其相互連接的拓撲關系。該表示法的特點是描述形體的信息既包括幾何信息，又包括拓撲信息。用實體的邊界來表示實體．在計算機內是如何實現的呢？這就是邊界表示的數據結構問題。我們仍以平面多面體為例來討論這一問題。1、實體的邊界表示2、邊界表示的數據結構7.3.1實體的邊界表示邊界模型表示形體的基本幾何元案包括頂點、邊、環、面、體。在進行各種運算和操作中．可以直接取得這些信息。用來定義形體表面的面既可以是平面(稱多面體)．也可以是曲面，形體上的邊既可以是直線段，也可以是的線段。三維物體采用邊界表示最普遍的方式是使用一組包圍物體內部的表面多邊形。存儲幾何信息的方法是建立三表結構，即頂點表、邊表和多邊形面表。頂點坐標值存放在頂點表中；含有指向頂點表指針的邊表，用來為多邊形的每條邊標識頂點。同樣．面表會有指向邊表的指針，出來為每個表面標識其組成的邊。邊界表示的概念不僅能用來表示三維空間的平面多面體，而且可延伸到表示一個面、一條邊。即—個平面多面體可用構成邊界的一系列平面多邊形表示，一個多邊形又可用構成其邊界的一系列邊來表示，而—條邊又可用兩個點來表示。那么，如何在計算機中將面、邊、點信息合理地組織起來以有效地滿足實體的構造、運算及顯示的需要呢？要用實體的邊界信息表示一個實體，必須正確地表示出實體邊界的拓撲信息及幾何信息。所謂拓撲信息．指的是面、邊、點之間的連接關系、鄰近關系及邊界關系，而幾何信息則指的是面、邊、點的位置及大小等幾何數據。由于使用者要頻繁地對實體的面、邊、點進行查找或修改．并且希望盡快地知道這些操作的影響及結果．因此，所設計的數據結構是否便于對實體進行面、邊、點的存放、查找或修改，是一個十分關鍵的問題，必須妥善地加以解決。可是，這并不是一個很容易解決的問題。若我們簡單地用—系列的頂點來表示一個多邊形，即而頂點坐標是按沿多邊形邊界的順序存放的，相鄰兩頂點之間代表一條邊．那么．對于一個簡單的多邊形．這種表示方法是節約空間的。但是，對于一個多面體邊界上的一系列多邊形來說．這種表示方法使用了過多的空間，這是由于被多個多邊形共享的頂點多次重復存儲的緣故。此外，這種表示方法沒有表示出共享邊及共享點的信息。如果我們想通過交互方式拖曳一個頂點及共享這個頂點所有的邊，就必須找到共享這個頂點的全部多邊形．就需要將一個多邊形的頂點坐標與所有其他多邊形的頂點坐標相比較．從而使用過多的計算時間。B-rep表示適用范圍大．原則上能表示所有的形體，而且易于支持形體的持征表示，B-rep表示巳成為當前CAD／CAM系統的主要表示方法。前面巳經提到．實體的面、邊、點之間存征9種不同類型的拓撲關系．在這9種不同類型的拓撲關系中．至少必須選擇兩種才能構成表示一個實體所需的完全的拓撲信息。因此，可能采取的數據結構形式．按所給定的拓撲關系來分，共有等8類．共計502種如果將此8類數據結構形式表示為．那么，當m小時，所存儲的拓撲關系少，因此所需的存儲空間小，但查找時間較長。當m大時，所存儲的拓撲關系多．因而所需的存儲空間大，但查找時間較短。因此，要根據對實體操作的具體要求及計算機系統資源的狀況，妥善選擇一種數據結構，求得時間利空間上的合理折中，以提高整個系統的效率。在使用邊界表示法表示實體的過程中，經常會遇到從一個點查找與該點相連的所有邊，從一條邊查找該邊的鄰面及鄰邊，從一個面開始查找其上的外環和內環等。數據結構是完成這些操作的基礎。實體造型中的數據結構本質上是對形體表示方式所需信息的存儲管理．B-rep表示就需要定義形體的面、環、邊、點及其屬性，以便進行存取、直接查找、間接查找和逆向查找等操作。邊界表示法的數據結構有4種：以面為基礎、以頂點為基礎、以邊為基礎和翼邊結構。7.3.2邊界表示的數據結構以面為基礎的數據結構、按照體、面、頂點坐標的樹結構層次織織元素數據，以頂點-坐標和面-頂點序列兩張關系表表示，如：{頂點(坐標)}；{面(頂點序列)}。以邊為基礎的數據結構．以邊-頂點，頂點-坐標，面-邊三張關系表表示，如：{邊(頂點)}、{頂點(坐標)}、{面(邊)}。四棱錐邊界表示的例子如圖7.12，由4個面組成，且這種表示可以看做是含有體、面、邊、頂點為節點的有向圖；四棱錐邊界表示也可采用基于邊界的三角形分解，即把形體的邊界拆成一些互不重疊的三角形。在幾何造型過程中，通常是把形體的幾何信息和拓撲信息結合在一起進行處理的。我們注意到不同尺寸和形狀的形體可能具有相同的拓撲關系，從而可以來用相同的形體生成過程．并且設計一種數據記錄結構．使之能分別處理形體的幾何信息與拓撲信息，這將提高造型系統的工作效率和質量。除了一般的幾何相交性的計算之外，形體組成元素間的拓撲關系的建立、改變與管理是造型過程中一個困難的問題。在國際、國內研究開發的三維實體造型系統中、采用較多的是翼邊數據結構及半邊結構。1．邊界表示的翼邊結構翼邊數據結構誕生于1972年．由美國斯坦福大學的B.G..波姆嘎特(B.G.Baumgart)等人作為多面體的表示模式提出。所謂翼邊，就是當我們觀察一個平面立體時，每一條棱邊都有左、右兩個鄰面和與之相鄰的四條鄰邊，好像展開的雙翅，故稱翼邊結構(見圖7．13)。通過翼邊結構，可以方便地查找每個元素之間的連接關系。例如，組成一個面的所有的邊、一條邊的所有鄰邊等。這種結構以每一條邊為核心．分別指向從外面觀察這一多面體時所見到的這條邊的上、下兩個頂點、左、右兩個鄰面以及上下左右四條鄰邊。每一個頂點都有一個指針．反過來指向以該頂點為端點的某一條邊；每一個面也有一個指針，反過來指向它的一條邊。翼邊結構由4種節點Solid，Face，Edge和Vertex組成．各節點描述如下：Solid是構成引用的根節點，在任意時刻，會存在幾個數據結構引用。為了存取其中的任何一個．需要有指向其Solid節點的指針。通過指向三個雙向鏈表的指針Solid節點給出對該模型的面、邊和頂點的訪問。所有實體被鏈接到一個雙向鏈表中，這個表通過指向該表的后繼和前趨實體的指針來實現。具體包括；指向Face的鏈表指針、指向Edge的鏈表指針、掐向Vertex的鏈表指針。structsolid{ Idsolidno;/*多面體序號*/ Face*sfaces;/*指向多面體的面*/ Edge*sedges;/*指向多面體的邊*/ Vertex*sverts;/*指向多面體的頂點*/ Solid*nexts;/*指向后一個多面體*/ Solid*prevs;/*指向前多面體*/}；Face是表示多面體的一個小平面。包括指向Face的鏈表首元素的指針、指Face的下—元素的指針。structface{ Idfaceno;/*面的序號*/ Solid*fsolid;/*指向該面所屬的多面體*/ Edge*fedges;/*指向構成該面的邊*/ Vectorfeq;/*平面或曲面方程*/ Face*prevf;/*指向前一個面*/ Face*nextf;/*指向后一個面*/}；Edge由Edge節點構成，是整個數據結構的核心，每個Edge節點代表一條邊．包括Edge的起始頂點指針、Edge的終止頂點指針、Edge的右鄰面的指針、Edge的左鄰面的指針、Edge的右方向向前鄰邊指針、Edge的右方向向后鄰邊指針、Edge的左方向向前鄰邊指針、Edge的左方向向后鄰邊指針。structedge{ Idedgeno/*邊序號*/Vertex*startv;/*指向邊的起始點*/ Vertex*endv;/*指向邊的終點*/ Face*rface;/*指向右鄰面*/ Face*lface;/*指向左鄰面*/ Edge*nedge;/*指向下一條邊*/ Edge*pedge;/*指向前一條邊*/}Vertex由Vertex節點構成，包括頂點坐標(x,y,z)、指向與該Vertex相連的第一條邊指針、指向下一個Vertex節點指針。通過冀邊結構，可以方便地查找各元素之間的連接關系。冀邊結構存儲的信息量大．顯然存儲內容重復，但卻獲得了較高的查找速度。structvertex{ Idvertexno;/*頂點序號*/ Vectorvcoord;/*頂點坐標*/ Vertex*prevv;/*指向前一個頂點*/ Vertex*nextv;/*指向后一個頂點*/}2．邊界表示的半邊結構當實體以邊界模型存儲時．翼邊結構較好地描述了點、邊、面之間的拓撲關系，但它也存在著—些缺陷。半邊數據結構是—種更完善的數據結構，簡稱半邊結構。半邊數據結構與翼邊數據結構的主要區別在于該結構—條物理邊拆分為兩條邊表示，使其中每條邊只與一個鄰接面相文(如圖7．14)，而從中每條邊亦只表示相應物理邊的一半信息．故稱半邊。出于環的定向已有明確規定(外環按逆時針方向，內環按順時針方向)．于是就可用標志位確定邊與面和環的關系。半邊數據結構分為5個層次，即體、面、環、半邊、頂點．每層拓撲元素包含的主要屬性如圖7.15所示。定義一個平面模型是頂點N、邊A和多邊形R的一個平面有向圖{N，A，R}，如圖7.14所示。為表示{N，A，R}，將使用一種5級層次數據結構(圖7.15)。它是由五種節點勸Solod，Face，Loop，HalfEdge和Vertex組成的。structsolid{ Idsolidno;/*多面體序號*/ Face*sfaces;/*指向多面體的面*/ Edge*sedges;/*指向多面體的邊*/ Vertex*sverts;/*指向多面體的頂點*/ Solid*nexts;/*指向后一個多面體*/ Solid*prevs;/*指向前多面體*/}；structface{ Idfaceno;/*面的序號*/ Solid*fsolid;/*指向該面所屬的多面體*/ Loop*floops;/*指向構成該面的環*/ Vectorfeq;/*平面或曲面方程*/ Face*prevf;/*指向前一個面*/ Face*nextf;/*指向后一個面*/}；structloop{ HalfEdge*ledge;/*指向構成環的半邊*/ Face*lface;/*指向該環所屬的面*/ Loop*prevl;/*指向前一個環*/ Loop*nextl;/*指向后一個環*/}structedge{ Idedgeno;/*邊的序號*/ HalfEdge*he1;/*指向左半邊*/ HalfEdge*he2;/*指向右半邊*/ Edge*preve;/*指向前一條邊*/ Edge*nexte;/*指向后一條邊*/}；structhalfedge{ Edge*edge;/*指向半邊的父節點*/ Vertex*vtx;/*指向半邊的起始頂點*/ Loop*wloop;/*指向半邊所屬的環*/ HalfEdge*prv;/*指向前一條半邊*/ HalfEdge*nxt;/*指向后一條半邊*/}；structvertex{ Idvertexno;/*頂點序號*/ HalfEdge*vedge;/*指向以該頂點為起點的半邊*/ Vectorvcoord;/*頂點坐標*/ Vertex*prevv;/*指向前一個頂點*/ Vertex*nextv;/*指向后一個頂點*/}值