語義特征造型的拓撲元素編碼機制

摘 要:針對現有拓撲元素標志與編碼方法都是面向基于歷程的造型系統，無法完全滿足與歷程無關語義特征造型的需要這一問題，提出一種以特征為基礎的拓撲元素標志方法，并歸納出了一種統一格式的拓撲元素編碼方法。當拓撲元素發生分裂時，給出了區分分裂面和分裂邊的方法及編碼格式;根據模型修改前后拓撲元素的不同變化情況，提出虛拓撲元素和子邊的概念及編碼格式，通過保留模型中拓撲元素間的拓撲關系，實現與歷程無關的模型修改操作，并將該方法在自主開發的語義特征造型系統(HUST-CAID)中加以實現。

關鍵詞:與歷程無關; 拓撲元素; 編碼; 虛拓撲元素; 子邊

中圖分類號:TP391 文獻標志碼:A

文章編號:1001-3695(2010)03-0938-03

doi:10.3969/j.issn.1001-3695.2010.03.035

Coding mechanism for topological entities in semantic feature modeling

GAO Xue-yao， SUN Li-juan

(School of Computer Science Technology， Harbin University of Science Technology， Harbin 150080， China)

Abstract:The naming and coding for topological entities were all for history-based modeling systems， which could not entirely support history-independent semantic feature modeling.This paper proposed a feature-based method for naming topological entities， and proposed a uniform coding method of topological entities. Gave differentiate methods and coding format for the split faces and edges. And proposed virtual topological entity and sub-edge according to topological entities variation after model modifying. Remained relations between topological entities to realize history-independent model modification. The proposed method was realized in HUST-CAID.

Key words:history-independent; topological entity; coding; virtual topological entity; sub-edge

拓撲元素的命名與編碼是參數化造型系統的關鍵技術[1]，Bronsvoort等人[2]把它歸結為目前參數化特征造型系統需要解決的六大問題之一。Kripac[3]設計了一個拓撲標志系統，把被引用的拓撲元素ID從拓撲標志系統映射到新模型中的相應元素。蘇曉鋒等人[4]提出一種面和邊的編碼方法，并按照子面參數域在父面參數域上的順序對子面排序以區分分裂面。陳正鳴等人[5]利用面的方向性定義了三類面面進出關系，并以此表示拓撲元素的局部拓撲信息。Zheng等人[6]用步驟ID和內部ID命名面，用子面的鄰接面區分子面，并用鄰接面命名邊和頂點。Yan等人[7]提出一種基于幾何連續性的參數族確定方法，并以此建立幾何和拓撲元素在新舊模型中的映射方法。Wang等人[8]定義了名字傳遞圖(NPG)來實現拓撲實體名的一致性傳遞，給出了辨識初始拓撲實體的規則與算法。Wu等人[9]提出一種基于圖的拓撲元素編碼與解碼方法，并結合參數化信息實現新舊模型的相似性匹配。

以上方法都是針對基于歷程的造型系統，而語義特征造型不基于設計歷程，是造型系統一個新的發展方向，上述方法無法完全滿足語義特征造型的需要。在與歷程無關的語義特征造型系統中修改模型，只需在現有模型上進行操作，無須根據設計歷程重構整個模型。本文提出一種基于特征的拓撲元素標志與編碼方法，并根據與歷程無關模型修改的動態、可逆的特點，提出子邊和虛拓撲元素的概念及編碼方法，以實現與歷程無關的模型修改操作。

1 拓撲元素的標志

三維空間中的直線可用兩個相交的面來表示，點可用三個相交于一點的面來表示。將這一思想應用到拓撲實體的標志與編碼上，拓撲邊通過兩個鄰接面的組合來表示，拓撲點通過三個鄰接面的組合來表示。具體方法為:以特征為基礎，首先對特征實體的面進行標志與編碼，然后利用面的拓撲名對邊和點進行標志與編碼。

1.1 面標志

基本形狀特征主要由掃略操作和旋轉操作生成，具有可明確定義的面。本文規定其各個面的標志規則為:以特征名和面在特征內部的名字共同確定。當特征依附于某一個基準面(依附面)時，規定與該基準面相接的面為特征的底面，與之相對的面是頂面。描述規則為(feature_instance_name. feature_element_ID)。

由掃略和旋轉操作生成基本形狀特征時，可能生成多個側面，需要對這些側面進行區分。掃略操作分為平掃(拉伸)和廣義掃。平掃生成特征側面的數量與草圖輪廓邊的數量相等，可將各個側面的編號直接對應于草圖邊的編號。廣義掃的路徑是二維或三維連續線段，每一條草圖邊對應的側面數可以是多個。因此先給草圖輪廓邊分配ID編號，然后對掃描路徑P進行分段，最后依據路徑段號P和輪廓ID號對各個側面進行標志。描述規則為(sweep.side_P_ID)。對于旋轉操作生成的特征，首先給各輪廓邊編號，判斷各輪廓邊的起點到旋轉軸的距離，將具有最小值的邊記為基準邊，將下一條邊的ID記為1，其他后續各邊ID依次加1，然后根據編號對各旋轉側面進行標志。描述規則為(rotate.side_ID)。

當特征面分裂為若干個子面時，需要對這些子面加以區分。本文借鑒文獻[4]的方法并加以改進:按照子面在父面參數域上的順序對子面進行排序，并保留父面ID，用于說明拓撲元素的變化情況。假設特征所在局部坐標系為u-v-w坐標系，首先對父面進行參數化，然后求出各個子面在父面上的參數域，按照先u后v最后w方向的順序對各個子面排序。描述規則為(feature_instance_name. feature_element_ID， f_ID)。在圖1中，block特征的頂面被兩個slot特征分裂為四個子面，它們的父面ID即feature_instance_name. feature_element_ID都是block.top，子面ID即f_ID，分別為f1、f2、f3、f4。父面block.top為平面，因此忽略子面在w方向上的排序。

1.2 邊標志

特征相交、修改等操作都會引起邊的變化。對邊的頻繁引用要求正確區分各條邊。拓撲邊可由兩個鄰接面惟一確定，邊的端點由另一個面與這兩個相鄰面相交形成，因此可以通過由特征定義的拓撲面來標志拓撲邊。描述規則為(adjacent_feature_faces)， (end_faces)。其中，adjacent_feature_faces為邊的兩個鄰接面，end_faces為邊的兩個端點所在的起始面和終止面。例如圖2中的e1邊表示為(block.top，block.side1)， (block.side4， blindslot.side1)。

當模型中存在曲面時，兩個面相交產生的邊可能多于一條。圖3中圓柱體的頂面與圓槽的側面相交生成兩條邊，這兩條邊的adjacent_feature_faces都是cylinder.top和roundslot.side，end_faces都是cylinder.side，無法正確區分。這種情況可以通過參考線reference來解決:定義一條有方向的參考線，規定沿參考線的方向前進，行進方向的左側區域為正，以此將需要區分的拓撲元素劃分在參考線的兩側，以進行識別。描述規則為(adjacent_feature_faces)， (end_faces， reference.orientation)。其中，reference.orientation用來說明要區分的拓撲元素位于參考線的哪一側。對于圖3中的兩條邊，通過定義一條位于cylinder的頂面且與兩條相交邊平行的參考線reference1來區分:

e1:(cylinder.top， roundslot.side)， (cylinder.side， roundslot.side， reference1.positive)

e2:(cylinder.top， roundslot.side)， (cylinder.side， roundslot.side， reference1.negative)

以上例子中，定義的參考線是直線。圖4中，在長方體的頂面開一個環形槽，形成內外兩條封閉環形邊，要區分這兩條邊需要定義一條封閉的曲線參考線:令參考線通過環形槽的中心線。因此，兩條環形邊可以分別表示為

e1:(block.top， roundslot.side)， (reference.positive)

e2:(block.top， roundslot.side)， (reference.negative)

由于這兩條邊為封閉邊，沒有起點與終點，end_faces忽略不計。

這里給出定義參考線的原則:參考線(包括直線和曲線)必須與特征的某些基準面、基準軸線或對稱面相關聯，如通過或垂直于軸線、與基準面重合或垂直等;參考線與特征的某條基準線確定一個平面，使要區分的兩條邊在該平面上的投影落在參考線的兩側;在該平面上，沿參考線的方向前進，行進方向的左側區域為正;當特征的位置發生變化時，參考線的位置也相應地發生變化。

1.3 點標志

在實體的拓撲關系中，頂點可看成面的交點，它的鄰接面集刻畫了其拓撲局部性質。因此頂點可以由其鄰接面集來表示，如圖5中的點v1為(block.top， slot.side2， block.side1)。

在有些情況下，僅由鄰接面集無法惟一確定頂點，如圖3中的邊e1、e2的四個頂點的鄰接面都為cylinder.top，roundslot.side和cylinder.side。這種情況可借助參考線來區分，描述規則為(adjacent_feature_faces)， (reference. orientation)。在圖3中定義一條與reference1垂直的參考線reference2(圖3中虛線所示)，因此四個頂點分別表示為

v1:(cylinder.top， roundslot.side， cylinder.side)， (reference1. positive， reference2.negative)

v2:(cylinder.top， roundslot.side， cylinder.side)， (reference1. negative， reference2.negative)

v3:(cylinder.top， roundslot.side， cylinder.side)， (reference1. negative， reference2.positive)

v4:(cylinder.top， roundslot.side， cylinder.side)， (reference1. positive， reference2.positive)

2 拓撲元素的編碼

在與歷程無關的造型系統中，設計人員對模型進行修改，只需在現有模型上進行操作和編輯，而無須根據設計歷程重構整個模型。例如將圖6中的圓槽向右拖動，使e1與e2邊重合。該操作使長方體頂面分裂而成的子面f2消失。若再次修改模型，將圓槽移回原處，則f2應被正確恢復。

通過上述例子可以看出，與歷程無關的模型操作是動態可逆的。在模型修改過程中，會出現某些拓撲元素互相重合或消失的情況，隨著進一步的操作，這些元素可能再次出現。因此，與傳統的基于歷程的造型方法不同，對操作過程中消失或重合的拓撲元素不能作簡單的刪除或合并，而要保留初始模型中特征拓撲元素間的拓撲關系，不改變特征所擁有的屬性。為了實現上述操作過程，根據前面分析的拓撲元素標志方法，本文歸納出一種統一格式的拓撲元素編碼方法，并根據模型修改前后拓撲元素的不同變化情況，提出虛拓撲元素和子邊的概念，以實現與歷程無關的模型操作過程。

2.1 面與虛面的編碼

根據拓撲面的標志方法，將面的編碼格式統一表示為

face_ID=(featureID， type， index， PID， split， addi)

FeatureID表示該面所屬的特征的標號。

Type表示面的類型，其值為-1表示底面，0表示頂面，1表示由掃略操作生成的側面，2表示旋轉操作生成的側面。

當有多個連續側面時，用index記錄各個側面的編號。對于底面和頂面，index的值為0。

當type為1時，用PID表示掃略特征的路徑編號。當PID的值為1時，表示拉伸或廣義掃的第一段路徑;當大于等于2時，表示廣義掃后續各段路徑的編號。對于底面和頂面，PID為0。當type為2時，該面為旋轉側面，此時PID用來記錄旋轉角度。

Split表示面是否發生了分裂，其值為0表示沒有發生分裂，為1表示發生分裂。當面發生分裂時，置其split=1，并按照前述方法對分裂子面進行排序。為了避免出現編碼位空閑而導致過多空間浪費的情況，本文為分裂的子面重新分配空間并進行編碼，形成面分裂表faceSplitTable。子面編碼格式為subface_ID=(featureID，type，index，PID，split，fID)。其中，fID表示子面的編號，其余各項的含義與前面所述相同，用于惟一表示子面的父面。

Addi為附加位，用于處理在模型修改過程中消失或重合的拓撲元素。對于這類拓撲元素，本文不將其刪除或合并，而是將其轉換為虛拓撲元素，保留其引用和拓撲關系，不顯示在模型的幾何邊界上。用addi位處理這種情況，addi的值為1表示該面構成模型的幾何邊界，為0表示消失或與其他面重合，即該面為虛面。虛面表示為vFace_ID=(featureID， type， index， PID， split， addi)。此時addi的值為0。

當拓撲面分裂為若干子面時，將該面的標志號轉換為虛標號，并生成子面編碼。若子面在操作過程中消失，則將該子面編碼轉換為虛標號，表示為虛子面:vsubface_ID=(featureID， type， index， PID， fID， addi)。此時addi的值也為0。

2.2 邊與虛邊的編碼

根據拓撲邊的標志方法，將邊的編碼格式統一表示為

edge_ID=(adjFaceIDs， endFaceIDs， RefOriCode， addi)

AdjFaceIDs表示生成此邊的兩個鄰接面。

EndFaceIDs表示邊的兩個端點所在的起始面和終止面。當所區分的邊為環形封閉邊時，endFaceIDs的值為0。

RefOriCode用于區分該邊位于參考線的哪一側，當它的值為-1時，表示沿參考線方向行進時，該邊在參考線的右側，為1表示在左側。無須用參考線區分時，refOriCode的缺省值為0。

Addi的含義與面編碼中的含義相同。

當被引用的邊消失或不構成模型的幾何邊界時，將該邊表示為虛邊:vEdge_ID=(vadjFaceIDs， endFaceIDs， refOriCode， addi)。其中，vadjFaceIDs表示該虛邊的兩個鄰接面，且至少有一個鄰接面是虛面;addi的值此時置0。

2.3 點與虛點的編碼

根據拓撲點的標志方法，將點的編碼格式統一表示為vertexID=(adjFaceIDs，refOriCode)。其中，adjFaceIDs表示點的三個鄰接面;RefOriCode的含義與邊編碼中的含義相同，缺省值為0。

虛拓撲點表示為vertexID=(vadjFaceIDs，refOriCode， addi)。其中，vadjFaceIDs表示該虛點的三個鄰接面，且其中至少有一個鄰接面是虛面;此時addi的值置0。

2.4 子邊及其編碼

模型修改過程中，若有拓撲元素發生重合，可能出現將一條邊劃分為若干段，而其中幾段不構成模型幾何邊界的情況。對此，本文提出子邊的概念:屬性相同的拓撲元素(主要是面和邊)重合，使拓撲邊上生成新拓撲點，這些拓撲點將拓撲邊劃分為幾段，每一段都是該拓撲邊的一段子邊。

當模型中存在重合面或重合邊時，子邊的生成方法如下:

a) 求重合拓撲元素(面或邊)在幾何模型上的交集，記錄構成該交集的拓撲邊及邊的端點。

b) 判斷哪些端點分別位于原拓撲元素的互相相交或重合的邊上。

c) 用這些端點對所在拓撲邊進行分段，每一段都是原拓撲邊的一段子邊。位于交集內部的子邊標號為虛標號。

子邊的編碼格式為subEdge_ID=(edgeID， adjFaceIDs， vendFaceIDs， addi)。其中，edgeID為子邊所屬拓撲邊的標號;adjFaceIDs表示該子邊的兩個鄰接面;vendFaceIDs為子邊的起止面，且其中至少有一個來自于與該邊重合的拓撲邊的起止面;addi的含義與面、邊編碼中的含義相同。

位于交集內部的子邊標號為虛標號:vsubEdge_ID= (edgeID，vadjFaceIDs，vendFaceIDs，addi)。其中，vadjFaceIDs為子邊的兩個鄰接面，且至少有一個鄰接面位于交集的內部。該鄰接面的拓撲邊界為生成子邊時所求的圍成該交集的拓撲邊，此鄰接面和它的拓撲邊均不構成模型的幾何邊界，標號記為虛標號，且addi的值為0。

3 方法實現與實例

將本文提出的拓撲元素編碼機制應用到自主開發的語義特征造型系統(HUST-CAID)中，系統采用VC++6.0加以實現，將編碼作為屬性與拓撲元素聯系起來。在特征建模及修改過程中，當拓撲元素發生分裂或重合時，對其進行重新編碼，并用面分裂表faceSplitTable和邊分裂表edgeSplitTable記錄發生分裂的拓撲元素。圖7是初始模型，在基體block上開兩條通槽slot1和slot2。其中slot1是圓槽。在slot2上是一個圓柱cylinder，且不與slot1相交。對模型進行修改，減小slot2的深度，令它與圓柱相交，產生兩條平行交線，并對其中一條進行倒圓角操作。利用本文的拓撲元素標志與編碼機制可正確區分這兩條邊，模型修改結果如圖8所示。

然后拖動圓柱修改其位置，則原來被倒角的邊隨著圓柱位置的改變而消失，倒角也隨之消失。操作結果如圖9所示。

4 結束語

語義特征造型是與歷程無關的造型方法，其建模與修改過程不依賴于造型歷程，具有操作靈活方便的特點，是造型系統的一個新的發展方向，具有良好的發展與應用前景。拓撲元素的命名和編碼是系統實現的一個關鍵問題，本文分析了現有拓撲元素命名方法存在的主要問題，提出了一種支持與歷程無關特征造型的拓撲元素標志與編碼方法。通過保留模型中拓撲元素間的拓撲與引用關系，避免了在基于歷程造型中存在的拓撲元素匹配問題，實現了在模型修改過程中對拓撲元素的惟一標志與編碼。根據特征模型修改前后拓撲元素的變化情況，提出虛拓撲元素和子邊的概念，以實現與歷程無關的模型修改操作，并將該方法在自主開發的語義特征造型系統中加以實現。

參考文獻:

[1]荊樹旭， 何發智， 劉華俊. 拓撲元素永久命名綜述[J]. 計算機輔助設計與圖形學學報， 2007， 19(5): 545-552.

[2]BRONSVOORT W F， BIDARRA R， NYIRENDA P J. Developments in feature modelling[J]. Computer-Aided Design Applications， 2006， 5(3):655-664.

[3]KRIPAC J. A mechanism for persistently naming topological entities in history-based parametric solid models[J]. Computer-Aided Design， 1997， 29(2): 113-122.

[4]蘇曉鋒，黃正東，朱林，等.形狀特征中的拓撲元素編碼體系[J]. 計算機輔助設計與圖形學學報， 2000， 12(2): 137-141.

[5]陳正鳴，高曙明，張鳳軍，等. 一種拓撲元素的命名和辨識方法[J].計算機學報， 2001， 24(11): 1270-1277.

[6]ZHENG Jia-jun， FAN Ming， TONG Ruo-feng， et al. A mechanism for persistently naming topological entities [C]//Proc of the 8th International Conference on Computer Supported Cooperative Work in Design Proceedings. New York: IEEE， 2004: 84-89.

[7]WANG Yan， NNAJI B O. Geometry-based semantic ID for persistent and interoperable reference in feature-based parametric modeling[J]. Computer-Aided Design， 2005， 37(10): 1081-1093.

[8]WANG Yan-wei， WU Jun-jun， CHEN Li-ping， et al. Identity propagation method for tracing alterations of a topological entity in a history-based solid modeling system[J]. Journal of Advanced Manufacturing Technology， 2005， 27(3-4): 305-312.

[9]WU Tao， XI Yi-shan， LI Zhang， et al. Coding and decoding of topological entities in constraint-based variational design [C]//Proc of International Conference on Advances in Product Development and Reliability.2008: 201-208.