拓撲元素的命名機制研究綜述

摘要:在基于歷史的參數化特征造型系統中，拓撲元素的命名和特征模型重新生成時拓撲元素的正確辨識是一個關鍵問題。此文基于參數化系統的模型表示方法，探討了拓撲元素永久命名問題，分析了解決該問題的4 個基本條件及其內在關系，將拓撲元素永久命名問題分為唯一命名及其辨識問題和模型重建階段拓撲結構發生改變時的語義辨識問題2個層面展開研究，并對其他相關研究中的名字問題進行了概述。

關鍵詞:拓撲元素;命名機制;綜述;CAD;建模

中圖分類號:TP391.72文獻標識碼:A文章編號:1009-3044(2009)32-9066-03

A Research Summary of Persistent Naming Problem for Topological Entities

LIAO Hua-feng

(Minxi Vocational and Technical College， Longyan 364000， China)

Abstract: To correctly identify topological entities by naming the re-evaluation of the model is one of the fundamental issues In history-based parametric feature modeling systems. This paper is based on the expression of the parametric feature modeling systems. It has analyze 4 basic conditions to solve the persistent topological naming problem，and their internal relationships. There are 2 categories in the persistent naming problem:uniquely name and retrieve topological entities，and how to retrieve topological entities as the topological structure is changed during the re-evaluation process. It also studied to other name question to carry on the outline related.

Key words: topological entities; naming problem; research summary; CAD; modeling

基于歷史的造型系統需要在零件模型的主拓撲實體元素(面、邊、點) 上關聯附加的特征信息，有了這些關聯信息，模型就可以依據它們自動生成。但是模型通過約束的自動生成會導致許多語義上的問題[1-2]。特別地，當用戶交互式地對幾何模型進行定義時，缺乏一個能對所引用的幾何元素進行通用描述的機制，而這正是三維參數化造型系統長期以來所期盼解決的問題，這種機制也是新一代的造型系統有別于傳統系統的一個顯著特征。它所涉及的一個基本問題就是如何標識模型中的拓撲實體，即拓撲命名。在此基礎上可以保證在零件模型重建時這些被引用的拓撲實體依然能夠被識別出來。

據統計，大約80%的設計是通過修改現有設計結果來完成的[3]。目前主流的三維CAD 系統都是基于歷史的參數化特征造型系統，簡稱參數化系統。參數化系統面臨著一系列問題，其中一個就是拓撲元素永久命名問題[4]，Bidarra等[5]將該問題歸結為當前參數化系統需要解決的6個基本問題之一。拓撲元素永久命名這一術語于1995年、1996 年被Kripac[6]、Capoyleas等[7]系統地提出后，相關問題的研究一直持續到現在。

在基于歷史的參數化特征造型系統中， 變動設計通過編輯已有特征模型并基于設計歷史重新計算生成結果物體來實現。然而，在現有CAD系統中，模型編輯后的新物體可能與設計意圖不一致，有時甚至會導致設計結果無法自動生成。產生這個問題的根本原因在于:在特征模型構造過程中所引用的拓撲元素(由用戶交互選取)在模型重新生成時不能被正確地找到。這就要求對被引用拓撲元素在設計歷史中有一個合理的記錄方法以及模型重新生成時相應拓撲元素的正確辨識方法，這就是拓撲元素的命名與辨識問題。

1 拓撲元素的辨識機制

拓撲元素辨識的目的是在新實體模型中找出符合用戶意圖的被引用元素。當特征模型修改后實體模型的拓撲結構發生變化時，現有方法會得到不滿足用戶意圖的辨識結果。主要是不能正確辨識消失元素、分離元素、合并元素以及分割元素等。

針對特征模型修改后拓撲元素的不同變化情況，我們認為拓撲元素的辨識機制應該滿足如下要求:

1) 當新舊實體模型的拓撲結構相同時，要能在新模型中辨識出與舊模型中元素對應的唯一拓撲元素;

2) 對消失元素，要能明確判別出新實體模型中沒有與舊實體模型中被引用元素對應的拓撲元素;

3) 對分離元素，要能在新實體模型中辨識出與舊實體模型中被引用元素對應的所有元素;

4) 對合并元素，要能在新實體模型中辨識出以舊實體模型中被引用元素與其它元素合并而來的元素;

5) 對舊實體模型中被切割或發生變化的被引用元素，要能在新實體模型中辨識出與被引用元素有最接近的影響特征、影響面和非影響面的拓撲元素。

2 拓撲元素命名問題

2.1 永久命名問題

記PM為參數化模型;PMI(p0，p1，…，pk)為參數化模型實例;BM為邊界模型;PMoriginal為原始參數化模型;PMmodified為經過修改的參數化模型;BMold為原始邊界模型;BMnew為參數化模型修改后重新生成的邊界模型。則PM和BM的關系可以用圖1表示。 圖1中，PMI0 (p0， p1， p2)通過3個造型命令生成:P0生成1個立方體;P1在立方體的一個面上開1個盲槽;P2選擇一條邊做倒圓操作。當用戶修改PMI0中槽的長度參數t0為t0'時， 得到PMI1。根據PMI1可以自動生成BM1。

記TS(BMi)為邊界模型BMi的拓撲結構;TE(BMi， Tj)為邊界模型BMi中的拓撲元素Tj;RN(TE(BMi， Tj)) 為邊界模型BMi中的拓撲元素Tj在PM中的引用名字;BM(PMi)為參數化模型PMi對應的邊界模型。則命名機制需要滿足以下條件:

條件1 任意TE(BMi ， Tj )， TE( BMi ， Tk)， j≠k， 滿足RN (TE(BMi， Tj) )≠RN (TE(BMi ， Tk) )，即同一BM中的任何不同的拓撲元素在PM中的引用名字必須相互區別。

條件2 任意BMi，BMj，如果TS ( BMi ) =TS ( BMj)，滿足RN (TE (Bi， Tk)) = RN(TE( Bj ， Tk))，即任何2個拓撲結構相同的BM ，其對應的拓撲元素在PM中的引用名字必須相同。

條件3 如果TS ( BM ( PMmodified ))≠TS(BM ( PMoriginal))，即修改造成BMnew相對于BMold的拓撲結構發生變化時，由PMmodified應該生成和BMold最相近的BM。

條件4 提供盡可能自由、靈活的模型編輯能力。

這4個條件存在內在聯系。條件1是建模階段必須滿足的，條件2和條件3都是重建階段(辨識階段) 所期望達到的。如果模型重建階段沒有發生拓撲結構改變，條件1和條件2互為充分必要條件，只要條件1滿足，條件2自然滿足，兩者本質上是同一個問題，屬于第一個層面問題的2個不同側面，可以稱為唯一命名和辨識問題。

如果模型重建階段拓撲結構發生改變，條件1僅僅是拓撲元素的永久命名問題的必要條件，并不充分。因為條件3包含有語義問題，具有不確定性，

過分追求條件4則會加重條件3的不確定性。要緩解條件3的不確定性，則又要犧牲條件4 中的要求。兩者屬于第二個層面中的一對矛盾，可以稱為拓撲結構改變情況下的處理問題。

2.2 基于面的拓撲實體層次命名

2.2.1 拓撲面命名

以原始特征體上的拓撲面作為命名的基礎實體，無疑是很自然的選擇，這是因為:

1) 零件體上的拓撲邊和拓撲點可能是無源拓撲邊和拓撲點。

2) 零件體上的拓撲面都可以在原始特征體上找到對應的源。這樣零件體的拓撲面的命名就可以轉化到原始特征體的拓撲面上。

3) 零件體和其上的拓撲實體處于不斷的變化過程中，而原始特征體上的拓撲面卻處于一種相對穩定的狀態中。

拓撲實體的名字(簡稱拓撲名) 和所依附的特征面之間是一種依存關系，在此稱為屬性關系，是一對一的關系。建立拓撲名和特征面的屬性關系的屬性機制包含了編碼的添加、查詢、清空和替換等方法。而拓撲名的刪除方法則由特征面在外部提供。當然，屬性機制中最為重要的還是拓撲名發生刪除、存活、拼合和分裂時對應的處理方法。各種對應的處理方法要求能夠保證拓撲名信息不被丟失，即具有可得性， 這樣就可以依據某種方式查詢得到。這是對各種方法的最低限度的要求。

2.2.2 層次命名記錄

拓撲實體的命名記錄實質上是對拓撲實體的記錄，是通過記錄拓撲實體的拓撲名來記錄拓撲實體本身。

對于正則的3D形體，在幾何上，3D空間中的直線可以用兩個相交的面來表示，而點可以用兩條相交的直線來表示。同樣，可以將這一思想拓展到零件拓撲實體的命名上來，3D實體上的拓撲邊的拓撲名可以用其鄰面拓撲名的組合來表示，3D實體上的拓撲點的拓撲名可以用其鄰邊的拓撲名的組合來表示。

實際上，對于拓撲點，由于其拓撲名是用其鄰邊的拓撲名組合來實現的，而邊的拓撲名又可以用邊的鄰面的組合來實現，因此拓撲點的拓撲名可以用其鄰面的拓撲名來表示。在幾何上，一個3D點可以用3個面的交集來實現。

最終，拓撲元素的命名體系是一種基于面拓撲名的層次結構體系，拓撲邊的拓撲名以面的拓撲名為基礎，拓撲點的拓撲名以邊的拓撲名為基礎，最終轉化到以面的拓撲名為基礎。在零件體上，每一個拓撲面都有拓撲名附著在其上，而拓撲邊和拓撲點的拓撲名是需要時才進行計算，計算得到的拓撲名結果并不附著在拓撲邊或拓撲點上。

2.2.3 拓撲名傳播

在原始特征體上的拓撲面命名完成以后，需要將此原始特征體和零件體進行布爾運算。布爾運算的發生，必然涉及到拓撲實體的刪除、存活、拼合和分裂等，因此對應于布爾運算，原始特征體和零件體上的特征面的拓撲名也必需有對應的傳播方式來處理。

1) 拓撲名刪除傳播。布爾運算導致了某個特征面被刪除，而且該特征面上的拓撲名也相應地被刪除。

2) 拓撲名存活傳播。某個特征面在布爾運算發生后仍然在零件體上，沒有被分裂或與其他的面發生拼合，該特征面上的拓撲名不發生任何變化。

3) 拓撲名分裂傳播。某個特征面在布爾運算發生后仍然在零件體上，并且被分裂成兩個或兩個以上的特征面，該特征面上的拓撲名將遷移到其所分裂成的特征面上，稱此時發生了拓撲名分裂傳播。

4) 拓撲名拼合傳播。零件體上的特征面F1和F2被拼合成特征面F，面F的拓撲名與面F1的拓撲名相同，F1為拼合前零件體上的特征面。

2.3 拓撲元素標號

拓撲元素標號為一整型碼，不同的拓撲元素都有不同的標號，而合并元素擁有多個標號。拓撲元素的標號由四部分組成:第1部分表示元素所屬特征的特征號，或為導致生成元素產生的特征的特征號;第2部分用一個碼位表示拓撲元素的類型，1，2和3分別表示特征的面、邊和點，4和5分別表示生成邊和生成點;第3部分表示此拓撲元素的原始元素的特定編號;第4部分碼位用以區分結果物體中標號的前三部分相同的拓撲元素。對物體中的派生元素，其標號記錄了此拓撲元素的原始特征號、原始元素標號、類型(面、邊和點) 等信息;對生成元素，其標號記錄了此拓撲元素的類型(生成邊、生成點)、導致它產生的特征的特征號。

在特征建模中，拓撲元素標號的產生分兩步進行:首先根據特征的生成方式(如掃成、旋轉) 對特征體的邊界元素賦以特定的標號，結果物體中的派生元素直接繼承其原始元素的標號，這樣結果物體中的派生元素標號的前三部分由其原始元素決定;再調整物體中有相同標號的不同元素(通過調整其標號的第4部分) 并創建生成元素的標號以保證物體中不同的拓撲元素有不同的標號。每個派生元素標號的前三部分記錄了其原始元素標號，它不會因模型變動而變化。這是因為特征體的邊界元素標號由特征體的生成方式本身決定。基于此，不管拓撲元素在模型編輯后如何變化，我們總可以找到其原始元素而得到那些不變的信息，如該拓撲元素的原始特征等。

2.4 拓撲元素的局部拓撲信息

根據元素標號可以區分物體中的不同拓撲元素，但它所具有的信息尚不足以確定模型編輯后新老實體模型中拓撲元素的對應關系。為了有效支持拓撲元素的辨識，對于模型中被引用的拓撲元素，在其名中放入它的局部拓撲信息，通過其局部拓撲信息刻劃出它的深層次語義。鑒于物體中的面總是來源于特征體的邊界面，而特征體的邊界面標號由特征的生成方式確定，它不會因特征參數的變動而變化。

2.5 其他相關研究中的命名問題

1) 參數化模型交換中的名字對應問題。一些研究者探索異構CAD系統之間參數化模型的交換。交換參數化模型時，需要完成異構CAD系統之間造型命令的互譯，其中一個重要的工作是要完成異構CAD系統之間拓撲元素的名字對應。名字對應完成后，再由各個CAD系統內建的名字機制產生邊界模型，從而完成異構CAD系統之間參數化模型的交換。

2) 集中式協同建模系統中的名字問題。在典型(如基于Web的系統)的集中式協同建模系統中，各個協同站點發出的造型命令被發送給中央服務器;中央服務器將各個協同站點發出的造型命令按照一個統一的順序執行，完成造型操作，并在服務器上生成新的實體模型;將面片化之后的可視化模型返回各個協同站點。在這種體系結構下，為了將服務器上的實體模型和各個協同站點上的可視化模型關聯起來，需要命名機制。

3) 復制式協同建模系統中的名字問題。各個協作站點發出的操作立即在本地執行，然后將該命令發送到各個遠程協同站點執行，各個協同站點通過交換造型命令進行密切的協作。各個協同站點發出的造型命令中包含拓撲元素的名字，由于造型命令在不同站點上的亂序執行，名字問題成為其中一個有待解決的議題。

3 結論

本文對命名機制現狀進行了綜述。在第一個層面中，建模階段的唯一命名就能夠解決模型重建過程中的辨識問題。在第二個層面中，若引用拓撲對象本身，其本質上是一個語義辨識問題。拓撲元素的辨識與用戶的設計意圖緊密相關，但很難把體現在具體拓撲元素中的設計意圖加以嚴格準確的數學描述，因有時設計意圖是隱式地體現在設計過程中的。所以要嚴格證明一個拓撲元素辨識方法的正確與合理性十分困難。

參考文獻:

[1] Hoffmann C M. On the Semantics of Generative Geometry Representations [J]. ASME， Design Automation Conference， 1993(2):411-420.

[2] Capoyleas V， Chen X， Hottmann C M. Generic Naming in Generative [J].Constraint-Based Design. CAD， 1996，28(1): 17-26.

[3] Shah J J. Parametric and feature-based CAD/CAM: concepts， techniques， applications[M]. New York: John Wiley and Sons Inc.， 1995.

[4] Srinivas Raghothama ， Vadim Shapiro1 Boundary representation deformation in parametric solid modeling[J]. ACM Transactions on Graphics， 1998，17(4): 259-286.

[5] Bidarra R， Bronsvoort W F. Semantic feature modeling [J]. Computer-Aided Design， 2000，32(3): 201-225.

[6] Kripac J. A mechanism for persistently naming topological entities in history-based parametric solid models[C]//Proceedings of the 3rd ACM symposium on Solid modeling and applications， Salt Lake City， Utah: ACM Press， 1995:21-30.

[7] Capoyleas V， Chen X， Hoffman C M. Generic naming in generative， constraint-based design[J]. Computer-Aided Design， 1996，28(1): 17-26.

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