[發(fā)明專利]一種三維空間復合體對象間拓撲關系的分析方法

無效

• 申請?zhí)枺?/td>: 200910025902.X
• 申請日: 2009-03-13
• 公開（公告）號: CN101504777A
• 公開（公告）日: 2009-08-12
• 發(fā)明（設計）人: 秦小麟;張駿
• 申請（專利權）人: 南京航空航天大學
• 主分類號: G06T17/00
• 分類號: G06T17/00
• 代理公司: 南京經緯專利商標代理有限公司
• 代理人: 許 方

技術領域

本發(fā)明涉及一種三維空間復合體對象間拓撲關系的分析方法，主要用于分析三維空間復合體對象間的拓撲關系，屬于計算機圖形學領域。

背景技術

三維空間對象間存在著多種關系，如度量關系、順序關系、拓撲關系等，其中最為有用的是拓撲關系，拓撲關系是指拓撲變換(平移、縮放、旋轉)下的不變量，如空間對象間是否相離、相離或相交等。拓撲關系是最基本的空間關系，它體現(xiàn)了空間實體在空間上的一種不依賴于幾何形變的內在聯(lián)系。拓撲關系的計算在地理信息系統(tǒng)(GIS)中尤為重要，有無拓撲關系的計算、建立與分析，被認為是GIS的重要特征之一。拓撲關系在空間信息查詢、提高空間信息輸入的準確性等多方面都有重要的應用。

體對象是三維空間中最為常見的一類空間對象，典型的如云團、煤層、城市建筑等都可抽象為空間多面體。體對象間的拓撲分析在很多領域如軍事、氣象、交通等都具有重要的應用價值。因此具有空間分析能力的系統(tǒng)必須提供對三維空間體對象的支持。

由于三維空間對象的復雜，開放地理空間協(xié)會(open?geometric?consortium，OGC)和國際標準化組織ISO只提出了二維點、線、面之間必須實現(xiàn)的拓撲分析操作，至今尚未對三維空間體對象間的分析有明確的要求。因此現(xiàn)有系統(tǒng)都定義了各自的實現(xiàn)，有著不同的針對性。三維空間地理信息系統(tǒng)如ESRI公司的Imagine?VisualGIS、適普公司的IMAGIS等僅能解決三維空間體對象的表示問題，而尚不具備三維空間拓撲分析能力。具備一定空間數(shù)據(jù)存儲能力的一些數(shù)據(jù)庫系統(tǒng)如Oracle?spatial、PostGIS等僅實現(xiàn)了二維空間對象的存儲與拓撲分析能力，對三維空間對象特別是體對象并不提供支持。現(xiàn)在也已有了一些商業(yè)的和開源的用于拓撲分析操作的計算幾何程序庫，如LEDA、CGAL、ERIT等，但僅能分析得出空間體對象是否相交，而無法得出其他更為詳細的拓撲關系，無法分析更為復雜的空間體對象間的拓撲關系。

文獻[Held?M.ERIT-A?collection?of?efficient?and?reliable?intersection?tests.Journal?ofGraphics，1997，2(4)：25-44]提出了一套名為ERIT(efficient?and?reliable?intersection?tests)拓撲分析程序庫，它實現(xiàn)了包括判斷線段、三角形、圓柱體等三維空間對象之間相交與否的基本拓撲分析操作，被應用于碰撞檢測[Klosowski?J?T，Held?M，Mitchell?J?S?B，Sowizral?H，Zikan?K.Efficient?collision?detection?using?bounding?volume?hierarchies?of?k-DOPs.IEEETransaction?on?Visualization?and?Computer?Graphics，1998，4(1)：21-36]。但該算法只能在已知空間對象類型的情況下，充分考慮其所具有的幾何性質，如事先確定球體的中心、半徑，圓柱體的中軸線等，再進行相交關系的判斷。因此僅能分析簡單空間對象間的拓撲關系，無法對復雜體對象間拓撲關系進行分析。

文獻[Granados?M，Hachenberger?P，Hert?S，Kettner?L，Mehlhorn?K，Seel?M.Booleanoperations?on?3D?selective?Nef?complexes?data?structure，algorithms，and?implementation.Proc.1lth?Annu.Europ.Sympos.Algorithms(ESA’03)，LNCS?2832，2003，654-666]提出了利用選擇Nef復形(selective?Nef?complex)進行三維空間體對象布爾操作的算法，它采用選擇Nef復形表示的Nef多面體進行空間體對象間的布爾操作，如交、并、補等。但該方法三維分析能力不足，僅能判斷是否相交或相離等簡單拓撲關系，缺乏對復雜拓撲關系的表達能力。

總體來看，當前國內外對三維空間體對象特別是復雜三維空間體對象之間的拓撲關系分析研究得較少，缺乏成熟的系統(tǒng)。

發(fā)明內容

本發(fā)明要解決的技術問題是針對現(xiàn)有技術存在的缺陷提出一種三維空間復合體對象間拓撲關系的分析方法。

本發(fā)明一種三維空間復合體對象間拓撲關系的分析方法，其特征在于包含以下步驟：