淺談實體建模：歷史、現狀與未來

鄒 強

淺談實體建模：歷史、現狀與未來

鄒 強

(浙江大學CAD&CG國家重點實驗室，浙江 杭州 310027)

實體建模技術是CAD軟件的“功能心臟”，相關基礎理論與算法是CAD發展歷史上最關鍵的成果之一，成功回答了為使計算機能夠輔助產品設計與制造，需在計算機中存什么幾何信息以及怎么存的問題。本文對實體建模的主要歷史發展脈絡做了簡要介紹，同時對各發展階段的關鍵問題以及研究現狀進行了討論，最后選取了3個方向對實體建模的未來做出展望,重點關注從Computer-Aided Design到Computer-Automated Design的發展趨勢。

CAD；幾何建模；實體建模；參數化建模；直接建模；結構建模；智能CAD

1 概 述

實體建模技術是計算機輔助設計(computer- aided design，CAD)領域60余年發展過程中最重要的成果之一，回答了CAX (computer-aided X)任務中最基本的問題：為使計算機能夠輔助產品設計制造，需在計算機中存儲哪些幾何信息以及怎么存。

實體建模算法庫組成了CAD軟件的幾何建模內核。而該內核如何做到自主可控，彌補與國際主流內核如Parasolid，ACIS的巨大差距，是解決我國所面臨的工業軟件“卡脖子”問題的重點。為此，實體建模技術對我國具有重要意義。

本文將梳理實體建模的歷史發展脈絡，敘述其基礎理論、關鍵算法與難點、以及這些難點的解決現狀。同時，本文還將對實體建模的未來作出展望，重點關注Computer-Aided Design向Computer- Automated Design發展的趨勢。

1.1 從CAD到幾何建模

產品即人造物理實體，產品模型指這一實體的計算機表示(即一種數據結構)，而CAD即是使用計算機來構建、查詢和編輯產品模型。CAD的概念于上世紀50年代末在MIT被提出[1]，主要為滿足：

(1) 構建產品的計算機模型并對之進行處理，以滿足二戰后發展起來的數控機床對自動生成加工路徑的需求[2]，實質上是為了滿足機器與機器間的協作需求；

(2) 構建一個可以讓人和計算機一起協作的設計系統，其中人負責創造性任務，而計算機負責機械式任務[3-4]，如圖1所示，實質上是為了滿足人與機器間的協作需求。

圖1 CAD系統中人與計算機的分工

從這2個需求(尤其是第2個)出發，CAD的具體內涵會非常豐富。但不久后，人們意識到CAD應當聚焦于產品建模、產品分析和產品制造這3個內容，因其更基礎、本質[3]。但同期也有其他領域在研究產品分析和產品制造，這3個內容最終分流成今天熟知的CAD，CAE (computer-aided engineering)和CAM (computer-aided manufacturing)。

具體到CAD，產品建模的任務旨在需要構建能夠支撐產品全生命周期所需全部信息的數字模型。這些信息以產品的幾何形狀為核心(圖2)，并伴有材料、工藝等非幾何信息[5]。在實際數字模型中，材料、工藝等信息均可在幾何模型的基礎之上以標記的形式來存儲。正因為如此，CAD建模往往重點關注幾何建模。到目前為止，主要的CAD幾何建模方法有：線框建模、曲面建模、實體建模、參數化建模以及直接建模，如圖3所示。

圖2 產品幾何信息在產品全生命周期中的作用

圖3 CAD幾何建模方法發展總括圖

1.2 從幾何建模到實體建模

在眾多幾何建模方法[6]中，線框建模到曲面建模再到實體建模是CAD建模技術發展的初期階段，其主要關注產品幾何信息該以何種數學模型來表示的問題。具體的發展脈絡可參見文獻[7]。

其中，線框模型，不管是2D還是3D，利用產品的邊或輪廓來描述幾何形狀。2D線框模型直接復制傳統工程制圖，也是第一代CAD原型系統“Sketchpad”所采用的方式[8]。3D線框模型的提出是為了解決2D線框模型每變換一個視角，都要重新繪制的問題(通過對3D線框模型進行投影操作，可自動得到任意方向的視圖)。然而，線框模型存在2個重要缺陷：歧義性和無效性，如圖4所示。無歧義性和確保有效性對CAD建模至關重要，因為CAD追求模型的真實性，與追求真實感的圖形學不同[6,9]。

圖4 線框模型的缺陷((a)歧義性；(b)無效性)[7]

為解決上述問題，人們提出曲面模型，對線框模型進行“蒙皮”[10]。同時，二戰后工業界對汽車和飛機等復雜曲面設計制造的需求也促進了曲面模型的發展[6]。人們提出了一系列巧妙的曲面表示和操作方法，從Coons曲面到Bezier曲面到B-spline曲面再到其改進型NURBS曲面，詳細地發展脈絡見文獻[11]。

然而，僅有曲面信息仍無法徹底解決歧義性和無效性問題，如真實世界中并不存在零厚度物體，而且每個物體都有內外之分。為此，實體模型被提出[12-13]，其特點在于對產品幾何信息進行了完整的表示，從點到邊到面再到體。因其具有信息完整性，任何幾何性質(如轉動慣量)也都可以被計算機自動計算出來[14]。

1.3 從實體建模到參數化/直接建模

實體模型因其信息完整性而適合表示產品幾何信息。然而，基本的實體建模方法，即CSG (constructive solid geometry)[15]和B-rep (boundary representation)[16]，存在重要缺陷：實體模型一旦被構建便難以修改[17]。因此，早期實體建模方法一般僅被用作記錄已經設計好并且不會發生變動的產品，對整個設計過程，尤其是早期概念設計階段，幫助不大[7,18]。

為解決這一問題，參數化建模在80年代末被提出[2]。其基本思路是在實體模型的基礎上添加一層關聯(associativity)信息，即在組成實體模型的幾何元素之間添加關聯信息，如此，模型上的局部變動可以按設計好的方式自動傳播到模型的其他區域[18]。關聯信息一般以幾何約束(如距離、相切、共軸等)的方式給出，并使得模型形狀被參數化到某幾個控制參數上，即模型形狀是這些控制參數的一個函數[19-20]。至此，通過在實體建模之上添加一層關聯信息，人們獲得了參數驅動的實體模型變動能力。

值得一提的是，人們又在“實體+關聯”的基礎之上，添加一層語義信息，形成了特征建模方法[2,21-22]。簡而言之，特征是對實體模型中幾何元素的一種歸組，同組元素會被一起引用，并被賦予特殊地設計或制造語義。

總之，參數化建模給實體建模帶來了3個益處[18,20,23]：①自動的變動傳播；②模型/設計重用；③設計、制造語義在實體模型中的表達。

參數化建模雖然有效，但模型只能在預先設計好的空間(由幾何約束系統決定)里變動[24-25]，使得參數化建模難以適用需要對模型進行自由編輯的場景，尤其是在概念設計階段[17,26-29]。針對這一問題，直接建模在2010年左右被提出[30]。與參數化建模中通過參數調整來間接式地修改實體模型不同，直接建模允許設計師對實體模型的幾何元素進行直接式的交互編輯。直接建模方法有3個優點：

(1) 直觀的交互方式使其能夠適用于概念設計；

(2) 極高的建模自由度和效率，因為直接建模操作能將一個實體模型變形到任意形狀；

(3) 高效的模型更新，因其采用局部模型更新方法。

上文簡述了實體建模技術的由來與歷史，下面將對實體建模、參數化建模和直接建模的關鍵技術進行討論。

2 實體建模1.0 (早期發展)

如前文所述，產品幾何信息在產品計算機模型中占據著核心位置。但是在設計領域，尤其是機械設計領域，幾何信息的具體內涵和定義是什么？人們在回答這一問題的過程中逐漸形成了實體建模理論與算法體系，簡述如下。

2.1 實體數學定義

有界性是指實體的任意點到原點的距離均是有界的。如一個10 mm×10 mm×10 mm的立方體就是有界的，而平面是無界的。這一條件是顯然的，現實世界中并不存在無限大的工業產品。

半解析性是指實體的邊界由半解析曲面組成。解析曲面指曲面上每點的(某個)鄰域可展開成收斂級數。這一約束條件是為了剔除如圖5所示的高階振蕩曲面，將實體邊界限定為平順變化的曲面。半解析曲面是指曲面的邊也是解析的。這是由于產品邊界往往不是由一張曲面就能完整表達的，需要多張曲面縫合在一起才能表達，半解析曲面就是對縫合處的邊提出具體要求。

圖5 非解析曲面例子[6]

正則性是指實體是三維的，在數學上表達為實體與其內點集合的閉包是相等的，如圖6所示。這一約束條件是為了防止實體不包含邊界點(not closed)，或者含有一維點集及二維點集，如圖7所示。

圖6 正則性定義示例

上述3個約束條件雖然可以完整刻畫大部分機械產品的形狀特性，但仍然允許實體具有非流形(non-manifold)邊界。為此，人們又在r-set的基礎之上添加了流形邊界的約束條件，即實體邊界上每個點的鄰域都是二維的[34]。這在數學上表達為實體邊界上每個點的(某個)鄰域和二維圓盤是同胚的，而同胚指2個點集之間具有連續的、一一對應的映射。這一約束條件是為了防止實體出現如圖8所示的線接觸或點接觸。這種情況在現實世界中是不可能的，因為其在接觸處具有無窮大應力。

圖7 非正則實體圖例((a)非閉合模型；(b)帶二維點集模型)

圖8 具有非流形邊界的實體圖例

2.2 實體模型表示

上述實體定義是產品幾何信息的數學抽象，即數學模型，實體模型是在數學抽象基礎之上的計算表示，即計算機模型(本質是一種數據結構)。在過去的50年里，人們提出了多種實體模型格式，詳見文獻[6,14,35-36]。其中，CSG和B-rep是最常用的。

B-rep實體模型存儲實體的邊界，實體的內部由邊界推導而出(如使用Winding numbers[37]，parity[38]，以及in/out counting[36]等方法)。如圖9(a)所示，一個B-rep實體模型實質上僅存儲組成該實體的邊界面，包括其背后的幾何曲面(carrying surfaces)，以及這些面之間的拓撲鄰接關系[10]。通過鄰接關系，可以對曲面進行裁剪、縫合，最終生成邊界面。實際的B-rep數據結構往往會在此基礎之上添加一些冗余信息，如頂點、邊以及鄰接關系，以加快幾何查詢的速度[6]。

CSG實體模型存儲實體的構建歷史，如圖9(b)所示。其使用布爾操作將多個簡單實體模型組合成復雜實體模型[15]。故其主要包含2個操作：體元生成(如立方體、圓柱體)與布爾操作(如體元求交集、求并集)。與B-rep的顯式存儲方式不同，CSG是一種隱式表示方法，模型內部只存儲操作步驟，不存儲操作結果，實體最終的形狀由所記錄的構建歷史推導而來[39]。實際的CSG數據結構往往是一個二叉樹，其中葉子節點存儲體元的定義信息，中間節點存儲布爾、剛體變換等操作。

圖9 實體模型圖例

CSG實體模型的主要優點有：①保證有界性質；②保證邊界曲面半解析性質；③保證正則性。缺點有：①無法保證邊界的流形性質，如圖10所示；②模型表示不唯一(一個模型對應多個CSG樹)。

圖10 CSG無法保證邊界的流形性質[34]

B-rep實體模型的主要優點有：①模型表示具有唯一性；②(理論上)可以表示任意復雜的實體；③由于是顯式表示，可直接用于后續模型處理。其缺點有：①無法保證所存儲實體模型的正則性和流形性質(一般情況下可保證有限體積性質和半解析性質)；②計算不魯棒問題；③當模型比較復雜時，存儲量比CSG大。

可以看出，B-rep和CSG具有一定的互補性。正因為如此，現代實體建模系統一般采用B-rep和CSG相混合的表示格式[18,40-43]。CSG的二叉樹結構作為骨架，B-rep模型替代了CSG中的體元，同時二叉樹的中間節點不僅存儲操作步驟，還存儲部分運算結果，比如重要邊界面的信息。存儲這些中間信息目的是為了將操作從布爾擴大至一些局部操作，如偏移、圓角等[16,40,44-45]。這些操作需引用被操作對象(即實體模型的某一局部幾何元素)，故而對這些對象進行存儲或標記至關重要。

2.3 實體建模算法

實體建模算法指構建和編輯實體模型的算法，一般分為3個層次實現：①底層數值算法；②中層幾何/拓撲計算；③上層實體操作。

其中上層實體操作主要包括布爾、過渡(圓角/倒角)、偏移、抽殼、掃掠、拔模、修復等1Euler操作文獻[16,152]也是實體建模的重要操作，但似乎現代幾何建模內核里面的幾何操作都不再基于Euler操作來實現了。。這些操作在背后調用中層的幾何計算或拓撲判定，主要包括求交、投影、成員判別、排序、曲面擬合等。如，2個B-rep實體模型間的布爾操作實質上調用的是曲面求交和成員判別2個操作。而幾何計算/拓撲判定又會調用底層的數值算法來做解算，主要包括線性/非線性方程組求解、數值優化等通用數值算法。

此處不對具體的數值算法、幾何計算/拓撲判定或實體操作的研究現狀進行詳述，而是對其中具有一般性的魯棒性問題進行討論。實體建模中的魯棒性問題主要有3個來源：

(1) 由于底層數值算法存在表示誤差(來源于浮點舍入誤差)、數值計算誤差(來源于數值求解或優化方法，常常伴隨計算步驟的增加而累加)以及中層幾何計算存在不完全表達誤差(來源于利用低階曲線曲面對高階曲線曲面進行近似所帶來的誤差)等表示和計算誤差，以其計算結果為基礎所做的邏輯性的拓撲判定可能發生不一致的情況，比如交線分支選擇錯誤，鄰接關系不對稱、無傳遞性等問題[46-49]。這方面典型的情況有布爾操作時曲面求交誤差所引起的成員判別失誤。

(2) 即使不存在任何表示和計算誤差，拓撲判定結果也可能與幾何數據不一致，并最終導致無效的實體模型。這種情況的根本原因在于B-rep數據結構要求拓撲和幾何保持一致，才能保證模型的有效性。然而，拓撲和幾何數據在B-rep中又是分離的，幾何數據的變動不會自動反映到拓撲數據中，反之亦然[50]。正因為此，有些拓撲數據雖然從自身來看是有效的，但和幾何一結合就會產生失效模型[51]。這方面典型的情況有模型修復時拓撲修正決策引發如圖8所示模型自交(注意不是曲面自交)。所謂拓撲修正是指對無效模型(即：是B-rep模型，但不滿足實體條件，如邊界不是流形的)的拓撲進行調整，以使之變為有效模型。

(3) 永久命名問題(此處不討論，詳見3.1節)。

從上述討論可以看出，實體建模中的魯棒性問題本質是幾何-拓撲不一致問題，其原因不全在數值誤差，反而更在于拓撲判定的正確性。

為解決由數值誤差引起的魯棒性問題(即來源(1))，一個自然的思路是將底層算法換用精確計算，如符號計算方法、有理數方法等[52-57]，但是這些方法往往在通用性或效率方面存在問題，并不實用。另一個思路是使用容差來保證即使存在計算誤差，拓撲判定仍是正確的[49,58-60]，如圖11所示。這種方法在理論上可完美解決幾何-拓撲不一致問題，實現魯棒建模，也是工業界所采用的方法，但是目前的容差設計方法主要以人工規則和閾值試錯的方式給出，尚缺少系統的方法。特別地，容差會在多個不同局部累積增大，當其相遇時，會發生不一致情況，進而導致錯誤的拓撲判定。

圖11 容差建模((a)對立方體進行裁剪；(b)具有容差的相交線)[58]

總體而言，實體建模1.0 (至80年代末)奠定了實體建模的理論和算法基礎。但是基礎算法方面仍存在種種問題，尤其是魯棒性問題，如魯棒求交、魯棒圓角等。

3 實體建模2.0 (中期發展)

實體建模在80年代末和90年代迎來重大發展，走向參數化建模[2]。簡言之，參數化模型是在前述B-rep與CSG混合模型的基礎之上增加了幾何約束[20,61]。(幾何約束其實早在第一代CAD系統“Sketchpad”上就已使用[8]。)盡管人們嘗試了多種參數化建模技術，詳見文獻[18]，主流的方法由以下3個部分組成[17,62-63]：

(1) 2D草圖繪制。用戶首先在繪圖平面上指定幾何圖元(點與邊)的拓撲，然后在其間添加幾何約束[64]。

(2) 3D特征生成。對所繪制的二維草圖進行拉伸、旋轉等操作，以生成三維實體特征(存儲為B-rep模型)，類似于CSG中的體元。

(3) 特征組合。將生成的3D特征與之前的特征進行布爾等操作，使之與CSG類似。

所有特征生成與組合的步驟又被稱為建模歷史，當其中一個步驟的參數發生變動，所有被記錄在建模歷史中的步驟都會按順序更新，并最終生成新的實體模型。于是有了參數驅動的實體模型變動。

從上述3個步驟中可以看出，參數化建模所帶來的新問題主要有2個：①如何確保建模歷史中所有引用對象的有效性，即所謂永久命名(或拓撲命名)問題；②如何求解用戶給定的幾何約束系統，即所謂幾何約束求解問題。當然，還有特征識別、維護等問題，由于這些問題與高層語義更相關，而非底層的拓撲、幾何、約束等，此處不展開討論，參見文獻[22,65-66]。

3.1 永久命名

在參數化建模中，當一個參數值發生變動，CAD軟件就會根據建模歷史重新生成模型。由于特征間具有“父-子”依賴關系，若這種關系在重生成過程中發生丟失或產生歧義，那么模型重生成就會失敗，如圖12所示。這一問題在90年代初被發現[24,41,67]，隨后人們提出了多種方法[68-69]，但這方面的研究很少，目前尚無系統地解決方案。

圖12 永久命名問題示例[18](此處，引用歧義指倒角操作所引用的邊在被槽一切為二之后，對哪條邊施加倒角操作存在歧義)

所有永久命名方法均致力于尋找B-rep模型在參數變動下的不變量。一種典型的不變量是以幾何元素間的拓撲關系為主，輔以形狀類型或相對位置，這方面典型的工作見文獻[70–72]。后來，人們又在此基礎上添加建模歷史，即幾何元素的生成與變動歷史，提高命名的魯棒性，這方面典型的工作有文獻[72-78]。這一方法目前已經被工業界廣泛使用。值得一提的是，其中文獻[75]的工作來自于我國華中科技大學，已成為永久命名方面的經典算法。

除上述方法外，Shapiro將拓撲學引入永久命名的研究中，提出了拓撲不變2實質上，Shapiro給出的條件是允許拓撲變化的，但是這種變化需滿足模型的邊界面發生連續變形。的必要條件[41,79-81]，這為研究各種永久命名方法的適用范圍提供了理論基礎。另外，人們還從特征語義的角度研究了參數變動下的不變量[82-83]，從限定參數變動域的角度來避免出現永久命名問題[84-86]。然而，這些工作多以純理論研究為主，尚未應用于實際。

混合幾何、拓撲和建模歷史來處理永久命名問題是目前工業界常用的方法，如幾何內核Open CasCade即采用類似文獻[70]中的方法。然而，這類方法往往需要混雜ad hoc規則，不夠系統，也不能完整解決永久命名問題，尤其是難以處理發生大拓撲變動的情形。永久命名問題亟需新的思路，形成一個系統的解決方案。

3.2 幾何約束求解

幾何約束求解涉及2大問題：欠、過約束系統處理和恰定約束系統分解。其中約束處理是為了將用戶輸入的一個非恰定的約束系統修正為恰定約束系統，而約束分解是為了將一個大的約束系統分解為多個子系統，然后分別解算，以提高求解效率。

3.2.1 幾何約束分析與分解

在過去的30余年里，人們提出了多種方法來分析幾何約束系統的約束狀態以及對其進行分解[43,87-88]。其大致可以分為4類：直接求解法、邏輯推演法、圖匹配法和擾動法。其中，直接求解法最為簡單，利用數值計算方法(如Newton-Raphson和homotopy)或者符號計算方法(如Grobner bases和Wu-Ritt triangulation)對幾何系統進行直接解算。如果求解成功，則為恰定約束；如果失敗，則其約束狀態由求解中間過程信息給出。目前，此類方法由于計算效率太低已經很少被實際采用[43]。

邏輯推演法[89-90]以一組幾何公理和推演規則為基礎，測試一個給定的幾何約束系統是否可以被邏輯推演出來。如果成功，那么該系統是恰定的；如果存在額外的幾何約束，那么該系統是過約束；反之，該系統為欠約束。這種方法本質上是將數學中的公理化思想應用到幾何約束分析與求解中，具有很高的數學價值。然而，目前所制定的幾何公理和推演規則離能夠實際應用還遠遠不夠。

與上述直接處理幾何約束的方法不同，圖匹配法將一個給定的幾何約束系統首先轉化為一個圖，然后以圖上的性質來間接地反映原幾何約束系統的性質。該方法有2條發展脈絡，其一致力于在圖中識別出一些特殊子圖，這些子圖會對應固定的幾何形狀或約束求解策略。這一思想首先由OWEN[91]提出，隨后BOUMA等[92-94]對子圖種類進行了有效擴充。其二致力于使用自由度分析來提取圖中恰定的子系統。這一思想首先由BARDORD[95]和SERRANO[96]提出，隨后AIT-AOUDIA等[97-99]對具體地提取算法做了補充。2001年文獻[87]針對這 2條脈絡進行了詳細的總結，并使用“分解-組合”這樣一個抽象框架來統一表述上述方法。這之后，圖匹配法雖然仍有所發展，如文獻[100]，但整個基礎框架保持不變。值得一提的是，我國中科院和華中科技大學的學者在這類方法上也做出了重要貢獻[101-102]。

盡管圖匹配法在工業界得到了廣泛應用(如DCM和LGS)，但其存在重大缺陷：不能處理具有約束依賴(除了最簡單的結構性依賴)的系統[103]。其原因在于當幾何約束系統轉化成圖后，只有約束系統內的組合類信息(combinatorial information)被保留，所有幾何信息均被丟棄，而很多約束依賴卻與幾何約束系統當時所處的幾何形狀息息相關。

為克服上述缺陷，擾動法[103]于2006年被提出。其基本思路是對約束系統的變量施加一個微小擾動，然后分析約束系統的反應，不同的反應模式就對應了不同的約束狀態。擾動法最重要的結論是：由于幾何約束系統是非線性的，其反應隨擾動施加位置的不同而有所變化，但是在一些代表性位置，擾動法的分析結果具有一般性[103]。文獻[104]給出了計算代表性位置的算法。這一方法由MICHELUCCI等[103,105-106]首先提出，最近在文獻[107-108]中得到實際應用，在文獻[30]中提升了其通用性(該問題討論見文獻[109])。完整解決其通用性問題尚需新的發展。

總體而言，幾何約束分析與分解雖然在算法和應用上取得了長足進步，但幾個根本問題一直未得到解決：

(1) 仍缺少有效的恰定約束狀態判定準則。目前廣泛使用的基于自由度的判定準則缺乏理論保證，尤其是針對3D幾何約束系統。實際例子也已經多次證實此類準則會失效[103,110]。

(2) 仍無法做到最優分解。整個約束系統求解的效率由最大子系統的規模決定，因而需要將每個子系統的規模降到最低，但目前尚缺少有效的算法。

(3) 仍無法高效求解大型3D幾何約束系統。其原因一方面是因為缺少有效的判定準則，約束分解的魯棒性問題突出；另一方面，傳統基于分解的思路難以應對大型系統，也許并行計算是一個突破口。

(4) 仍無法自動處理多解選擇問題。理論上，恰定幾何約束系統解的個數與約束數量是指數關系。如何自動在這么多解中選擇出用戶想要的解是長久以來一直存在的一個問題，這方面研究很少，而工業界多采用基于規則的方法，尚缺少系統的解決方案。

3.2.2 幾何約束系統處理

約束處理的核心任務是在系統中添加或刪除約束，以消除欠、過約束狀態，形成恰定約束系統，其難點在于：能夠滿足條件的約束往往不唯一，需要對候選約束進行設計語義方面的評價并依此做出排序。

與約束分析和分解相比，約束處理方面的研究工作較少，進展也很小[88,111]。初期的典型工作如文獻[98,112]，其思路是應用文獻[113]中的最大加權方法，即給每個候選約束賦予一定的權重，然后從中選擇那些能夠形成最大加權總和的約束子集。這一方法的有效性嚴重依賴于權重的設計，而現有工作多采用基于ad hoc規則的方法，很難具有通用性。也有如文獻[114-116]的方法是基于前述圖匹配法來對約束進行選擇，這顯然會繼承圖匹配法的固有缺陷。還有如文獻[117-120]的方法是基于純人工規則，如約束類型等，這些策略也使其缺乏通用性。最近如文獻[107-108,121]的方法是基于擾動法來做選擇，但目前的進展還局限于簡單約束系統[107]、純過約束系統[108]，或一般約束系統但不能完全自動化[121]。

總之，目前尚缺少有效的智能約束處理方法，現有方法仍處于初級發展階段。近來人工智能的快速發展也許會給這一領域帶來新的進步。

4 實體建模3.0 (近期發展)

直接建模技術是實體建模繼參數化建模后又一重要進展。此方法雖然于2010年左右由工業界正式提出，但其相關的技術可追溯到80年代由學術界提出的局部操作概念[16,25,45,122-123]。所謂局部操作是指對B-rep模型的局部幾何元素直接進行編輯的方法，例如圓角、偏移等。直接建模技術就是在tweaking這一局部操作的基礎之上發展起來的。Tweaking允許用戶對B-rep模型的邊界面進行旋轉、平移等修改，但邊界面的變動被嚴格控制在不破壞原有拓撲關系的范圍內。

直接建模放松了上述限制，以獲得對模型進行任意編輯的能力(圖13)，并將之重命名為push-pull操作。Push-pull操作是初期直接建模技術唯一支持的操作，但目前已得到了極大地擴充，如刪除面操作等。從最近的發展來看，任何允許用戶對實體模型的幾何元素(點、邊、面)進行直接編輯(包括移動、刪除、合并、分割等)的操作都可以歸到直接建模[30]。

圖13 直接建模圖例((a)原模型；(b)編輯后模型[30])

與參數化建模中用戶通過幾何約束來顯式、完整地表達設計意圖，而計算機機械式地求解幾何約束來更新模型不同，在直接建模中，用戶只指定部分幾何元素的目標位置(即只表達部分設計意圖)，其他幾何元素如何協調地進行變動(主要是拓撲更新[30])由計算機自主推斷(即計算機補全用戶設計意圖)。如此，用戶得以減負，并獲得直觀、快捷的模型編輯能力，而計算機是加負，需要變得更智能。如圖14所示，如果計算機沒有自主性，將得到一個失效模型。

圖14 直接建模中的協調更新問題[124]

在直接建模中，關鍵難點在于存在多個模型更新方案，有些不能給出有效的實體模型，有些雖然可以給出有效模型，但是不符合預期(與用戶設計意圖不一致)，一般而言，僅有一個方案是既能給出有效模型，又能與設計意圖保持一致的，如圖15所示。故而，直接建模的核心問題是方案決策問題(而參數化建模的核心問題是求解計算問題)。

圖15 直接建模中的決策問題

針對這一問題，目前有2個思路：基于規則的以及基于連續性原理的?；谝巹t的方法[25,125-127]一般針對特定種類的實體模型和直接建模操作設計一組規則，來對模型進行更新。目前，這類方法已經可以魯棒處理由平面組成的B-rep模型，但其他種類模型仍存在問題?；谶B續性原理的方法[30,124]以模型更新時，其變動必須連續作為總要求，并將之轉化成對幾何元素的定量約束條件，從而實現對模型更新方案的系統決策。目前，這類方法已經可以魯棒處理由平面和二次曲面組成的B-rep模型，但是尚不能處理含有自由曲面的B-rep模型。

總體而言，直接建模最核心的問題是對模型更新方案進行決策，其關鍵挑戰在于決策方法的系統性，從而實現魯棒的模型更新。當前的問題主要集中于[121,128]：

(1) 如何在直接編輯中保持設計語義(如邊界面連接處的連續性)；

(2) 如何魯棒地直接編輯帶自由曲面的實體模型；

(3) 如何直接編輯參數化模型。

5 實體建模4.0 (未來發展)

實體建模的未來發展是多樣的，此處僅能就某幾個方面做出討論，分別從新方法解決舊問題、新需求帶來新問題、新技術帶來新發展3個方面展開。

5.1 從支持詳細設計到支持全過程設計——參數/直接融合建模

實體建模自誕生以來就一直被詬病為不能支撐全過程設計，僅對詳細設計階段有效，對概念設計階段幫助不大[7]。人們往往只有在已經確定了設計細節后，才使用參數化CAD軟件來建模[17,26-29]。直接建模帶來了直觀、任意的實體模型編輯能力，使其能夠支撐概念設計。

然而，在目前的CAD系統中，參數化建模功能和直接建模功能是割裂的，分別支持詳細設計階段和概念設計階段。如何無縫融合直接建模與參數化建模，解決長期以來大家期望的在一個統一的建模方法中同時支持概念設計和詳細設計，是下一代CAD建模技術亟需解決的問題。

當前的融合方法尚無法達到無縫融合[129]。最常用的方法是以參數化建模為主干，將直接建模簡單地當成一個特征加入到建模歷史中，如圖16(a)所示。這種基于“偽特征”的融合方法，會導致原設計語義的錯亂或丟失，如圖16(b)所示。理想的融合方法是基于直接建模操作重定義特征模型，實現模型中設計語義的智能維護，如圖16(c)所示，如此，詳細設計階段的參數語義在概念設計階段不會被直接建模操作所破壞。

圖16 基于“偽特征”融合方法的缺陷((a)建模歷史；(b)增大X的尺寸不會給出紅圈中理想的模型更新，而是造成模型重生成失敗，其原因在于邊界面F2的丟失(見藍圈中模型)；(c)無縫融合應該基于直接建模操作重定義被操作特征，實現參數模型中設計語義的智能維護)

參數/直接無縫融合的關鍵難點在于如何將舊的幾何約束系統(代表設計語義)與直接建模作用后新的B-rep模型進行同步：直接建模作用后，CAD模型的邊界表示(即B-rep模型)會發生變動，但是其建模歷史(即特性信息，主要包括幾何約束)仍保持不變，如此，計算機需要將B-rep模型的變動同步成為特性的變動(即需要更新特性信息以使得特征模型對應的B-rep模型和直接建模作用后的B-rep模型保持一致)。人們已經對此做了一些嘗試[121,128]，其核心思想是將直接建模操作轉譯為特征重定義，比如幾何約束增刪、參數調整、特征調序等。這些方法在一些特定情形下取得了很好的結果，但在智能性和自動化程度上尚有很大進步空間。

5.2 從Computer-Aided Design 到Computer-Automated Design——復雜結構建模、設計、仿真與制造

3D打印(或增材制造)技術的快速發展使得制造具有復雜微觀結構的產品成為可能，如圖17所示。與傳統實體建模中研究的復雜曲面完全不同，這種復雜結構在形狀復雜度、數據規模量等方面發生了質的變化，對幾何建模理論、幾何表示數據結構、模型操作魯棒性、自動化設計等方面都提出了新的需求，也帶來了全新的問題。這將會給實體建模的基礎理論和關鍵算法帶來本質變化，主要包括：

(1) 實體的定義需要擴展。如前所述，傳統實體概念所定義的對象是具有剛性、均質特性的產品，而復雜結構可能是剛性也可能是非剛性的(甚至是多模態的)，同時其還具有異質、多材料等特點?，F有實體定義不能覆蓋這些特點，需要被擴展以適用復雜結構。

(2) 復雜結構幾何表示方法需要發展。復雜結構具有很高的“表面體積比”，這使得傳統B-rep表示方法難以適用，否則將造成極大的存儲消耗。如何實現復雜結構的輕量化表示，是當前復雜結構建模亟需解決的問題。目前的隱式表示[130]、參數表示[131]、圖表示[132]、網格壓縮表示[133]以及混合表示等方法都具有很大的局限性，往往只能處理特定類型的復雜結構[134]，與此同時，這些表示方法所能處理的結構復雜度仍非常有限，特別是難以處理如圖17所示超復雜結構(這些結構如果以STL格式存儲，將達到幾百G存儲量)。故而，發展新的統一高效復雜結構表示數據結構是當前需攻克的核心難題。

(3) 復雜結構自動設計方法需要發展。復雜結構的幾何-性能-工藝具有強耦合的特點，這使得其難以像傳統零件一樣由人來設計，而是需要由計算機來自動設計，同時復雜結構所具有的豐富多樣的幾何細節，也讓人工設計變得不可能。這些需求都促使工程設計從Computer-Aided Design向Computer-Automated Design發展。自動設計的關鍵問題落在CAD/CAE/CAM的一體化，旨在形成設計與性能和工藝仿真的自動化閉環，對CAD設計模型，通過CAE/CAM軟件分析其性能和工藝，指導設計調整，反復迭代，達成設計目標，生成最優結構。形成這一自動化閉環的核心挑戰在于CAD/CAE/CAM模型表示統一化[135]；然而，CAD模型面向制造和裝配，CAE模型面向仿真計算，CAM模型面向工藝規劃與控制，這三者的數據屬性各不相同，但又互有重疊，故而設計一個既能滿足設計、仿真、制造需求，又不重復存儲數據，且不同屬性數據能聯動的產品表示數據結構是極具挑戰的，即CAD/CAE/CAM統一模型表示需要滿足三大極具挑戰的要求：信息完整性、信息無冗余性、信息關聯性。這方面的工作近年來進展很大，主要集中于結構優化(或稱為拓撲優化、生成式設計，詳見文獻[136])，但是這些工作大多聚焦于CAD/CAE一體化，少數考慮CAM數據的工作也僅局限于簡單工藝模型或約束[137]。

圖17 簡單、復雜、高度復雜結構實例[137-141]

5.3 智能CAD、云CAD

智能計算、云計算、并行計算以及虛擬現實等新一代計算技術將對CAD的發展有極大促進作用。

智能計算技術將推動CAD從設計師主導的人工建模向計算機主導的智能建模發展。通過機器學習，計算機將能夠在一定程度上對設計師的設計、制造意圖進行預測，從而實現對設計、制造語義的自動補全和識別，并將之轉換為實體建模操作，這將極大地降低設計師的建模負擔，尤其是在概念設計和工藝規劃階段。(本文中智能CAD的涵義并不包括下述功能：根據給定功能要求自動優化出產品形狀或結構，這主要涉及機械式的優化算法，而非設計、制造意圖的理解。)

虛擬現實技術、自然語言處理技術、計算機視覺技術將促使CAD系統從二維交互向三維智能交互發展，如通過手勢、語言、草圖來交互[142-145]，也會推動正、逆向設計的融合[146–150]。智能建模與智能交互相結合，正、逆向設計相互融合將極大提高產品設計的效率。然而值得一提的是，這一發展不要求實體建?；A理論和算法發生本質變化，更多的是在現有CAD技術基礎上添加一層智能技術。

云計算帶來了計算資源平臺的變遷，這將使得CAD向“計算在云上而交互在本地”的模式發展。這一發展主要會帶來2個需求：①快速“云-端”傳輸；②并行實體建模算法。其中，需求①顯而易見，CAD建模的交互是實時的，故而云上的建模結果需要快速傳輸到本地，并作實時繪制。需求②的原因在于云CAD并不是簡單將幾何建模內核搬到云上，然后針對每個用戶開一個建模線程(這種方式只是在套用云概念，和桌面CAD沒有本質區別)，而是需要對用戶操作(尤其是多人協同設計情況下，協同CAD系統的經典工作請參見文獻[151])背后所調用的算法和資源進行管理、優化配置，合并相同類型計算，并行化不同類型計算，這本質上是要求實體建模算法向并行化發展?？梢钥闯?，云CAD和智能CAD不同，其對實體表示格式和操作算法都提出了本質變化要求。

另外，并行計算也能給實體建模中的一些老難題提供新思路。如，針對超大規模裝配模型顯示和編輯問題，并行計算可部分解決其中的效率問題。再如，針對實體建模魯棒操作這個歷史性難題，可以使用并行計算的高效率來換取曲面求交等計算的高精度，從而在一定程度上解決由計算誤差帶來的魯棒性問題。傳統上，需要在精度和效率之間平衡，進而造成不可控的計算誤差。

6 總 結

本文對實體建模的發展歷史作了簡要梳理，按三段來介紹：早期實體建?；A理論與算法(50年代末到80年代末)，中期參數化建模(80年代末到2000年代末)，以及近期直接建模(2010年左右至今)。同時對各發展階段的關鍵算法與難題以及其研究現狀進行了討論，對尚未形成系統解決方案的難題進行了重點評述。最后選取了3個方向對實體建模的未來做出展望。

值得注意的是，文中梳理的歷史發展并不全面，僅涉及主要脈絡。另外，未來展望也不全面，未來實體建模的發展必定是多樣化而深刻的，特別是從Computer-Aided Design到Computer-Automated Design的發展趨勢。這些發展也將給學術界和工業界帶來眾多有意義并且有趣的科研問題。

[1] COONS S, MANN R W. Computer-aided design related to the engineering design process[R]. Cambridge: M.I.T. Electronic Systems Laboratory, 1960.

[2] SHAH J, MA?NTYLA? M. Parametric and feature-based CAD/CAM: concepts, techniques, and applications[EB/OL]. [2022-05-19]. https://www.researchgate.net/publication/44371716_Parametric_and_feature_based_CADCAM_concepts_techniques_and_applications_Jami_J_shah_Martti_Mantyla.

[3] COONS S A. An outline of the requirements for a computer-aided design system[C]//Proceedings of the Spring Joint Computer Conference. New York: ACM Press, 1963: 299-304.

[4] ROSS DT. Computer-aided design: a statement of objectives[R].Cambridge: Massachusetts Institute of Technology, 1960.

[5] REQUICHA A A G. GEOMETRIC MODELING?: a First course 6-2, fundamental algorithms[R].Los Angeles: Univevsity of Southern California, 1999: 1-28.

[6] REQUICHA A A G. Representations for rigid solids: theory, methods, and systems[J]. ACM Computing Surveys, 1980, 12(4): 437-464.

[7] STAFF N A O E, COMPTON W D, ENGINEERING N A O. Design and Analysis of Integrated Manufacturing Systems[M]. Washington DC: National Academies Press, 1988: 167-199.

[8] SUTHERLAND I E. Sketchpad a man-machine graphical communication system[J]. SIMULATION, 1964, 2(5): R-3.

[9] REQUICHA A A G, VOELCKER H B. Solid modeling: current status and research directions[J]. IEEE Computer Graphics and Applications, 1983, 3(7): 25-37.

[10] BRAID I C. Geometric modelling[M]//Advances in computer graphics I. Berlin: Springer Berlin, 1986: 325-362.

[11] COHEN E, LYCHE T, RIESENFELD R F. MCAD: Key historical developments[J]. Computer Methods in Applied Mechanics and Engineering, 2010, 199(5-8): 224-228.

[12] VOELCKER H B, REQUICHA A A G. Geometric modeling of mechanical parts and processes[J]. Computer, 1977, 10(12): 48-57.

[13] BRAID I C. The synthesis of solids bounded by many faces[J]. Communications of the ACM, 1975, 18(4): 209-216.

[14] SHAPIRO V. Solid modeling[M]//Handbook of computer aided geometric design. Amsterdam: Elsevier, 2002: 473-518.

[15] REQUICHA A A G. Constructive solid geometry[EB/OL]. [2022-06-19]. https://www.zhangqiaokeyan.com/ntis-science- repoort-thesis/020711454048.html.

[16] STROUD I. Boundary Representation Modelling Techniques[M]. London: Springer London, 2006.

[17] CAMBA J D, CONTERO M, COMPANY P. Parametric CAD modeling: an analysis of strategies for design reusability[J]. Computer-Aided Design, 2016, 74: 18-31.

[18] SHAH J J. Designing with Parametric CAD: classification and comparison of construction techniques[M]//Geometric modelling. Boston: Springer US, 2001: 53-68.

[19] HOFFMANN C M, JOAN-ARINYO R. Parametric modeling[M]//Handbook of computer aided geometric design. Amsterdam: Elsevier, 2002: 519-541.

[20] ROLLER D. An approach to computer-aided parametric design[J]. Computer-Aided Design, 1991, 23(5): 385-391.

[21] SHAH J J, ROGERS M T. Functional requirements and conceptual design of the Feature-Based Modelling System[J]. Computer-Aided Engineering Journal, 1988, 5(1): 9.

[22] SHAH J J, ANDERSON D, KIM Y S, et al. A discourse on geometric feature recognition from CAD models[J]. Journal of Computing and Information Science in Engineering, 2001, 1(1): 41-51.

[23] CAMBA J D, CONTERO M. Assessing the impact of geometric design intent annotations on parametric model alteration activities[J]. Computers in Industry, 2015, 71: 35-45.

[24] CHEN X P, HOFFMANN C M. On editability of feature-based design[J]. Computer-Aided Design, 1995, 27(12): 905-914.

[25] ROSSIGNAC J R. Issues on feature-based editing and interrogation of solid models[J]. Computers & Graphics, 1990, 14(2): 149-172.

[26] MONEDERO J. Parametric design: a review and some experiences[J]. Automation in Construction, 2000, 9(4): 369-377.

[27] ANDREWS P T J, SHAHIN T M M, SIVALOGANATHAN S. Design reuse in a CAD environment—four case studies[J]. Computers & Industrial Engineering, 1999, 37(1-2): 105-109.

[28] BETTIG B, BAPAT V, BHARADWAJ B. Limitations of parametric operators for supporting systematic design[C]// 2005 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference.New York: ASME, 2008: 131-142.

[29] BROWNP. CAD: do computers aid the design process after all?[J]. Intersect: The Stanford Journal of Science, Technology and Society, 2009, 2(1): 52-66.

[30] ZOU Q, FENG H Y. Push-pull direct modeling of solid CAD models[J]. Advances in Engineering Software, 2019, 127: 59-69.

[31] REQUICHA A A G. Mathematical models of rigid solid objects[EB/OL]. [2022-06-01]. https://www. zhangqiaokeyan. covn/ntis-science-report_other_thesis/020711446637.html.

[32] REQUICHA A A G. Representation of rigid solid objects[M]//Lecture notes in computer science. Berlin: Springer, 2006: 1-78.

[33] REQUICHA A A G, VOELCKER H B. Solid modeling: a historical summary and contemporary assessment[J]. IEEE Computer Graphics and Applications, 1982, 2(2): 9-24.

[34] MANTYLA M. A note on the modeling space of Euler operators[J]. Computer Vision, Graphics, and Image Processing, 1984, 26(1): 45-60.

[35] BAER A, EASTMAN C, HENRION M. Geometric modelling: a survey[J]. Computer-Aided Design, 1979, 11(5): 253-272.

[36] BOTSCH M, KOBBELT L, PAULY M, et al. Polygon Mesh Processing[M]. Wellesley: A K Peters, 2010: 1-250.

[37] JACOBSON A, KAVAN L, SORKINE-HORNUNG O. Robust inside-outside segmentation using generalized winding numbers[J]. ACM Transactions on Graphics, 2013, 32(4): 33.

[38] BRIDSON R, FEDKIW R, ANDERSON J. Robust treatment of collisions, contact and friction for cloth animation[C]// SIGGRAPH '05: ACM SIGGRAPH 2005 Courses. New York: ACM Press, 2005: 2-es.

[39] REQUICHA A A G, VOELCKER H B. Boolean operations in solid modeling: boundary evaluation and merging algorithms[J]. Proceedings of the IEEE, 1985, 73(1): 30-44.

[40] ROSSIGNAC J R, REQUICHA A A G. Offsetting operations in solid modelling[J]. Computer Aided Geometric Design, 1986, 3(2): 129-148.

[41] SHAPIRO V, VOSSLER D L. What is a parametric family of solids?[C]//The 3rd ACM Symposium on Solid Modeling and Applications. New York: ACM Press, 1995: 43-54.

[42] BODEIN Y, ROSE B, CAILLAUD E. Explicit reference modeling methodology in parametric CAD system[J]. Computers in Industry, 2014, 65(1): 136-147.

[43] BETTIG B, HOFFMANN C M. Geometric constraint solving in parametric computer-aided design[J]. Journal of Computing and Information Science in Engineering, 2011, 11(2): 1.

[44] BRAID I. Non-local blending of boundary models[J]. Computer-Aided Design, 1997, 29(2): 89-100.

[45] GRAYER A R. Alternative approaches in geometric modelling[J]. Computer-Aided Design, 1980, 12(4): 189-192.

[46] Michelucci D. An Introduction to the Robustness Issue[EB/OL]. [2022-05-21]. https://ufrsciencestech.u-bourgo gne.fr/master/mil-tc5/tmp/PAPERS/cadcam-swiss.pdf.

[47] HOFFMANN C M. Robustness in geometric computations[J]. Journal of Computing and Information Science in Engineering, 2001, 1(2): 143-155.

[48] ROSSIGNAC J R. Through the cracks of the solid modeling milestone[M]//From object modelling to advanced visual communication. Heidelberg: Springer, 1994: 1-75.

[49] HU C Y, PATRIKALAKIS N M, YE X Z. Robust interval solid modelling Part I: representations[J]. Computer-Aided Design, 1996, 28(10): 807-817.

[50] ZOU Q, FENG H Y. Push-pull direct modeling of solid CAD models[J]. Advances in Engineering Software, 2019, 127: 59-69.

[51] SHEN G L, SAKKALIS T, PATRIKALAKIS N. Analysis of boundary representation model rectification[C]//The 6th ACM Symposium on Solid Modeling and Applications. New York: ACM Press, 2001: 149-158.

[52] BERBERICH E, EIGENWILLIG A, HEMMER M, et al. Exacus: efficient and exact algorithms for curves and surfaces[M]//Algorithms - ESA 2005. Berlin: Springer, 2005: 155-166.

[53] KEYSER J, CULVER T, FOSKEY M, et al. ESOLID—a system for exact boundary evaluation[J]. Computer-Aided Design, 2004, 36(2): 175-193.

[54] BENOUAMER M, MICHELUCCI D, PéROCHE B. Error-free boundary evaluation using lazy rational arithmetic: a detailed implementation[M]. New York: ACM Press, 1993: 115-26.

[55] TRETTNER P, NEHRING-WIRXEL J, KOBBELT L. EMBER: exact mesh booleans via efficient & robust local arrangements[J]. ACM Transactions on Graphics, 2022, 41(4): 39.

[56] WANG C C L, MANOCHA D. Efficient boundary extraction of BSP solids based on clipping operations[J]. IEEE Transactions on Visualization and Computer Graphics, 2013, 19(1): 16-29.

[57] BERNSTEIN G, FUSSELL D. Fast, exact, linear booleans[J]. Computer Graphics Forum, 2009, 28(5): 1269-1278.

[58] JACKSON D J. Boundary representation modelling with local tolerances[C]//The 3rd ACM Symposium on Solid Modeling and Applications. New York: ACM Press, 1995: 247-254.

[59] STROUD I, NAGY H. Solid modeling and CAD systems?: how to survive a CAD system[EB/OL]. [2022-06-10]. https://www. researchgate.net/publication/267018694_solid_modelling_and_CAD_systems_How_to_survive_a_CAD_system.

[60] QI J C, SHAPIRO V. ε-Topological formulation of tolerant solid modeling[J]. Computer-Aided Design, 2006, 38(4): 367-377.

[61] ROSSIGNAC J R. Constraints in constructive solid geometry[C]//1986 Workshop on Interactive 3D graphics. New York: ACM Press, 1987: 93-110.

[62] MUN D, HAN S, KIM J, et al. A set of standard modeling commands for the history-based parametric approach[J]. Computer-Aided Design, 2003, 35(13): 1171-1179.

[63] HOFFMANN C M, JOAN-ARINYO R. On user-defined features[J]. Computer-Aided Design, 1998, 30(5): 321-332.

[64] BETTIG B, SHAH J. Derivation of a standard set of geometric constraints for parametric modeling and data exchange[J]. Computer-Aided Design, 2001, 33(1): 17-33.

[65] BIDARRA R, BRONSVOORT W F. Semantic feature modelling[J]. Computer-Aided Design, 2000, 32(3): 201-225.

[66] LI L, ZHENG Y F, YANG M L, et al. A survey of feature modeling methods: historical evolution and new development[J]. Robotics and Computer-Integrated Manufacturing, 2020, 61: 101851.

[67] HOFFMANN C M. On the semantics of generative geometry representations[C]//1993 Design Technical Conferences. New York: ASME, 2021: 411-419.

[68] MARCHEIX D, PIERRA G. A survey of the persistent Naming problem[C]//The 7th ACM Symposium on Solid Modeling and Applications. New York: ACM Press, 2002: 13-22.

[69] FARJANA S H, HAN S. Mechanisms of persistent identification of topological entities in CAD systems: a review[J]. Alexandria Engineering Journal, 2018, 57(4): 2837-2849.

[70] CAPOYLEAS V, CHEN X P, M HOFFMANN C. Generic Naming in generative, constraint-based design[J]. Computer- Aided Design, 1996, 28(1): 17-26.

[71] WANG Y, 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.

[72] BABA-ALI M, MARCHEIX D, SKAPIN X. A method to improve matching process by shape characteristics in parametric systems[J]. Computer-Aided Design and Applications, 2009, 6(3): 341-350.

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

[74] AGBODAN D, MARCHEIX D, PIERRA G, et al. A topological entity matching technique for geometric parametric models[C]//2003 Shape Modeling International. New York: IEEE Press, 2003: 235-244.

[75] WU J J, ZHANG T B, ZHANG X F, et al. A face based mechanism for Naming, recording and retrieving topological entities[J]. Computer-Aided Design, 2001, 33(10): 687-698.

[76] MUN D W, HAN S H. Identification of topological entities and Naming mapping for parametric CAD model exchanges[J]. International Journal of CAD/CAM, 2005, 5(1): 69-81.

[77] CHEON S U, MUN D, HAN S, et al. Name matching method using topology merging and splitting history for exchange of feature-based CAD models[J]. Journal of Mechanical Science and Technology, 2012, 26(10): 3201-3212.

[78] FARJANA S H, HAN S, MUN D. Implementation of persistent identification of topological entities based on macro-parametrics approach[J]. Journal of Computational Design and Engineering, 2016, 3(2): 161-177.

[79] RAGHOTHAMA S, SHAPIRO V. Boundary representation deformation in parametric solid modeling[J]. ACM Transactions on Graphics, 1998, 17(4): 259-286.

[80] RAGHOTHAMA S, SHAPIRO V. Topological framework for part families[J]. Journal of Computing and Information Science in Engineering, 2002, 2(4): 246-255.

[81] RAGHOTHAMA S, SHAPIRO V. Necessary conditions for boundary representation variance[C]//The 13th Annual Symposium on Computational Geometry. New York: ACM Press, 1997: 77-86.

[82] MARTIN K, WANG W P. Geometric modeling and processing 2000. Theory and applications[M]. New York: IEEE Press, 2002: 1-4.

[83] BIDARRA R, NYIRENDA P J, BRONSVOORT W F. A feature-based solution to the persistent Naming problem[J]. Computer-Aided Design and Applications, 2005, 2(1-4): 517-526.

[84] VAN DER MEIDEN H A, BRONSVOORT W F. Tracking topological changes in parametric models[J]. Computer Aided Geometric Design, 2010, 27(3): 281-293.

[85] HOFFMANN C M, KIM K J. Towards valid parametric CAD models[J]. Computer-Aided Design, 2001, 33(1): 81-90.

[86] TANG Z H, ZOU Q, GAO S M. Towards computing complete parameter ranges in parametric modeling[EB/OL]. [2022-05-19]. https://arxiv.org/abs/2206.08698.

[87] HOFFMAN C M, LOMONOSOV A, SITHARAM M. Decomposition plans for geometric constraint problems, part II: new algorithms[J]. Journal of Symbolic Computation, 2001, 31(4): 409-427.

[88] ZOU Q, TANG Z H, FENG H Y, et al. A review on geometric constraint solving[EB/OL]. [2022-04-21]. https://arxiv.org/ abs/2202.13795.

[89] DUFOURD J F, MATHIS P, SCHRECK P. Geometric construction by assembling solved subfigures[J]. Artificial Intelligence, 1998, 99(1): 73-119.

[90] JOAN-ARINYO R, SOTO A. A correct rule-based geometric constraint solver[J]. Computers & Graphics, 1997, 21(5): 599-609.

[91] OWEN J C. Algebraic solution for geometry from dimensional constraints[C]//The 1st ACM Symposium on Solid Modeling Foundations and CAD/CAM Applications. New York: ACM Press, 1991: 397-407.

[92] BOUMA W, FUDOS I, HOFFMANN C, et al. Geometric constraint solver[J]. Computer-Aided Design, 1995, 27(6): 487-501.

[93] FUDOS I, HOFFMANN C M. A graph-constructive approach to solving systems of geometric constraints[J]. ACM Transactions on Graphics, 1997, 16(2): 179-216.

[94] GAO X S, HOFFMANN C M, YANG W Q. Solving spatial basic geometric constraint configurations with locus intersection[C]//The 7th ACM Symposium on Solid Modeling and Applications. New York: ACM Press, 2002: 95-104.

[95] BARDORD L A. A graphical, language-based editor for generic solid models represented by constraints[M]. Ithaca: Cornell University, 1987.

[96] SERRANO D. Constraint management in conceptual design[EB/OL]. [2022-06-29]. https://www.researchgate.net/ publication/243764572_Constraints_in_conceptual_design.

[97] AIT-AOUDIA S, JEGOU R, MICHELUCCI D. Reduction of constraint systems[EB/OL]. [2022-05-17]. https://arxiv.org/ abs/1405.6131.

[98] LATHAM R S, MIDDLEDITCH A E. Connectivity analysis: a tool for processing geometric constraints[J]. Computer-Aided Design, 1996, 28(11): 917-928.

[99] HOFFMANN C M, LOMONOSOV A, SITHARAM M. Finding solvable subsets of constraint graphs[M]//Principles and practice of constraint programming-CP97. Berlin: Springer, 1997: 463-477.

[100]HIDALGO M, JOAN-ARINYO R. H-graphs: a new representation for tree decompositions of graphs[J]. Computer-Aided Design, 2015, 67-68: 38-47.

[101]GAO X S, LIN Q, ZHANG G F. A C-tree decomposition algorithm for 2D and 3D geometric constraint solving[J]. Computer-Aided Design, 2006, 38(1): 1-13.

[102]XIA H J, WANG B X, CHEN L P, et al. 3D geometric constraint solving using the method of kinematic analysis[J]. The International Journal of Advanced Manufacturing Technology, 2008, 35(7): 711-722.

[103]MICHELUCCI D, FOUFOU S. Geometric constraint solving: the witness configuration method[J]. Computer-Aided Design, 2006, 38(4): 284-299.

[104]KUBICKI A, MICHELUCCI D, FOUFOU S. Witness computation for solving geometric constraint systems[C]//2014 Science and Information Conference. New York: IEEE Press, 2014: 759-770.

[105]THIERRY S E B, SCHRECK P, MICHELUCCI D, et al. Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems[J]. Computer-Aided Design, 2011, 43(10): 1234-1249.

[106]FOUFOU S, MICHELUCCI D. Interrogating witnesses for geometric constraint solving[J]. Information and Computation, 2012, 216: 24-38.

[107]MOINET M, MANDIL G, SERRE P. Defining tools to address over-constrained geometric problems in computer aided design[J]. Computer-Aided Design, 2014, 48: 42-52.

[108]HU H, KLEINER M, PERNOT J P. Over-constraints detection and resolution in geometric equation systems[J]. Computer- Aided Design, 2017, 90: 84-94.

[109]ZOU Q, FENG H Y. On limitations of the witness configuration method for geometric constraint solving in CAD modeling[EB/OL]. [2022-05-15]. https://arxiv.org/abs/1904. 00526.

[110]HALLER K, LEE-ST JOHN A, SITHARAM M, et al. Body-and-cad geometric constraint systems[J]. Computational Geometry, 2012, 45(8): 385-405.

[111]HU H, KLEINER M, PERNOT J P, et al. Correction to: geometric over-constraints detection: a survey[J]. Archives of Computational Methods in Engineering, 2021, 28(7): 5037.

[112]JERMANN C, HOSOBE H. A constraint hierarchies approach to geometric constraints on sketches[C]//2008 ACM Symposium on Applied Computing. New York: ACM Press, 2008: 1843-1844.

[113]BORNING A, FREEMAN-BENSON B, WILSON M. Constraint hierarchies[J]. LISP and Symbolic Computation, 1992, 5(3): 223-270.

[114]JOAN-ARINYO R, SOTO-RIERA A, VILA-MARTA S, et al. Transforming an under-constrained geometric constraint problem into a well-constrained one[C]//The 8th ACM Symposium on Solid Modeling and Applications. New York: ACM Press, 2003: 33-44.

[115]HOFFMANN C M, SITHARAM M, YUAN B. Making constraint solvers more usable: overconstraint problem[J]. Computer-Aided Design, 2004, 36(4): 377-399.

[116]ZHANG G F, GAO X S. Well-constrained completion and decomposition for under-constrained geometric constraint problems[J]. International Journal of Computational Geometry & Applications, 2006, 16(5/6): 461-478.

[117]MURUGAPPAN S, SELLAMANI S, RAMANI K. Towards beautification of freehand sketches using suggestions[C]//The 6th Eurographics Symposium on Sketch-Based Interfaces and Modeling. New York: ACM Press, 2009: 69-76.

[118]MILLS B I, LANGBEIN F C, MARSHALL A D, et al. Estimate of frequencies of geometric regularities for use in reverse engineering of simple mechanical components[EB/OL]. [2022-06-15]. https://www.researchgate.net/publication/20001 8274_Estimate_of_Frequencies_of_Geometric_Regularities_for_use_in_Reverse_Engineering_of_Simple_Mechanical_Components?channel=doi&linkld=0912f50b8c3cbzea23000000&showFulltes=true.

[119]ZOU H L, LEE Y T. Constraint-based beautification and dimensioning of 3D polyhedral models reconstructed from 2D sketches[J]. Computer-Aided Design, 2007, 39(11): 1025-1036.

[120]LANGBEIN F C, MARSHALL A D, MARTIN R R. Choosing consistent constraints for beautification of reverse engineered geometric models[J]. Computer-Aided Design, 2004, 36(3): 261-278.

[121]ZOU Q, FENG H Y. A decision-support method for information inconsistency resolution in direct modeling of CAD models[J]. Advanced Engineering Informatics, 2020, 44: 101087.

[122]STROUD I, XIROUCHAKIS P C. CAGD—computer-aided gravestone design[J]. Advances in Engineering Software, 2006, 37(5): 277-286.

[123]FAHLBUSCH K-P, ROSER TD. HP PE/SolidDesigner: dynamic modeling for three-dimensional computer-aided design[J]. Hewlett-Packard Journal, 1995, 46: 6-13.

[124]ZOU Q, FENG H Y. A robust direct modeling method for quadric B-rep models based on geometry–topology inconsistency tracking[J]. Engineering With Computers, 2022, 38(4): 3815-3830.

[125]WOO Y, LEE S H. Volumetric modification of solid CAD models independent of design features[J]. Advances in Engineering Software, 2006, 37(12): 826-835.

[126]KIM BC, Mun DW. Stepwise volume decomposition for the modification of B-rep models[J]. The International Journal of Advanced Manufacturing Technology, 2014, 75: 1393-403.

[127]FU J, CHEN X, GAO S M. Automatic synchronization of a feature model with direct editing based on cellular model[J]. Computer-Aided Design and Applications, 2017, 14(5): 680-692.

[128]QIN X L, TANG Z H, GAO S M. Automatic update of feature model after direct modeling operation[J]. Computer-Aided Design and Applications, 2020, 18(1): 170-185.

[129]ZOU Q. Parametric/direct CAD integration[EB/OL]. [2022- 05-17]. https://arxiv.org/abs/2203.02252.

[130]DING J H, ZOU Q, QU S, et al. STL-free design and manufacturing paradigm for high-precision powder bed fusion[J]. CIRP Annals, 2021, 70(1): 167-170.

[131]MASSARWI F, MACHCHHAR J, ANTOLIN P, et al. Hierarchical, random and bifurcation tiling with heterogeneity in micro-structures construction via functional composition[J]. Computer-Aided Design, 2018, 102: 148-159.

[132]GUPTA A, ALLEN G, ROSSIGNAC J. QUADOR: QUADric-of-revolution beams for lattices[J]. Computer-Aided Design, 2018, 102: 160-170.

[133]CHOUGRANI L, PERNOT J P, VéRON P, et al. Lattice structure lightweight triangulation for additive manufacturing[J]. Computer-Aided Design, 2017, 90: 95-104.

[134]DONG G Y, TANG Y L, ZHAO Y F. A survey of modeling of lattice structures fabricated by additive manufacturing[J]. Journal of Mechanical Design, 2017, 139(10): 100906.

[135]SHAPIRO V, TSUKANOV I, GRISHIN A. Geometric issues in computer aided design/computer aided engineering integration[J]. Journal of Computing and Information Science in Engineering, 2011, 11(2): 1.

[136]WU J, SIGMUND O, GROEN J P. Topology optimization of multi-scale structures: a review[J].Structural and Multidisciplinary Optimization, 2021, 63(3): 1455-1480.

[137]DING J H, ZOU Q, QU S, et al. STL-free design and manufacturing paradigm for high-precision powder bed fusion[J]. CIRP Annals, 2021, 70(1): 167-170.

[138]LIU S J, LIU T, ZOU Q, et al. Memory-efficient modeling and slicing of large-scale adaptive lattice structures[J]. Journal of Computing and Information Science in Engineering, 2021: 1-16.

[139]GUPTA A, ALLEN G, ROSSIGNAC J. QUADOR: QUADric- of-revolution beams for lattices[J]. Computer-Aided Design, 2018, 102: 160-170.

[140]MASSARWI F, MACHCHHAR J, ANTOLIN P, et al. Hierarchical, random and bifurcation tiling with heterogeneity in micro-structures construction via functional composition[J]. Computer-Aided Design, 2018, 102: 148-159.

[141]LIU S J, LIU T, ZOU Q, et al. Memory-efficient modeling and slicing of large-scale adaptive lattice structures[J]. Journal of Computing and Information Science in Engineering, 2021: 1-16.

[142]LI C J, PAN H, BOUSSEAU A, et al. Free2CAD: parsing freehand drawings into CAD commands[J]. ACM Transactions on Graphics, 2022, 41(4): 93.

[143]LI C J, PAN H, BOUSSEAU A, et al. Sketch2CAD: sequential CAD modeling by sketching in context[J]. ACM Transactions on Graphics, 2020, 39(6): 164.

[144]SEFF A, ZHOU W D, RICHARDSON N, et al. Vitruvion: a generative model of parametric CAD sketches[EB/OL]. [2022-05-30]. https://arxiv.org/abs/2109.14124.

[145]GANIN Y, BARTUNOV S, LI Y N, et al. Computer-aided design as language[M]//Advances in neural information processing systems 2021. Cambridge: MIT Press, 2021: 5885-5897.

[146]UY M A, CHANG Y, SUNG M, et al. Point2Cyl: reverse engineering 3D objects from point clouds to extrusion cylinders[C]//2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2022: 11840-11850.

[147]GUO H X, LIU S L, PAN H, et al. ComplexGen: CAD reconstruction by B-rep chain complex generation[EB/OL]. [2022-05-18]. https://arxiv.org/abs/2205.1457.

[148]WU R D, XIAO C, ZHENG C X. DeepCAD: a deep generative network for computer-aided design models[C]//2021 IEEE/CVF International Conference on Computer Vision. New York: IEEE Press, 2022: 6752-6762.

[149]XU X H, PENG W Z, CHENG C Y, et al. Inferring CAD modeling sequences using zone graphs[C]//2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2021: 6058-6066.

[150]LAMBOURNE J G, WILLIS K D D, JAYARAMAN P K, et al. BRepNet: a topological message passing system for solid models[C]//2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2021: 12768-12777.

[151]LI M, GAO S M, WANG C C L. Real-time collaborative design with heterogeneous CAD systems based on neutral modeling commands[J]. Journal of Computing and Information Science in Engineering, 2007, 7(2): 113-125.

[152]EASTMAN C M, WEILER K J. Geometric modeling using the Euler operators[R]. Pittsburgh: Carnegie Mellon University; 1979.

A note on solid modeling: history, state of the art, future

ZOU Qiang

(State Key Lab of CAD&CG, Zhejiang University, Hangzhou Zhejiang 310027, China)

Solid modeling is a technique underlying CAD software as we see it today, and its theories and algorithms are among the most fundamental milestones in the historical development of CAD. Basically, it has answered the question of what geometric information a computer should store and how to store/manipulate them in order for the computer to aid the processes of design and manufacturing. This paper provides abrief review on the historical development of solid modeling, its fundamental research problems, as well as their challenges and state of the art. It then concludes with three prospective trends of solid modeling, especially the promising paradigm shift from “Computer-Aided Design” to “Computer-Automated Design”.

CAD; geometric modeling; solid modeling; parametric modeling; direct modeling; structure modeling; intelligent CAD

TP 391

10.11996/JG.j.2095-302X.2022060987

A

2095-302X(2022)06-0987-15

2022-07-31；

：2022-10-12

國家自然科學基金項目(62102355)；浙江省自然科學基金項目(LQ22F020012)

鄒 強(1990-)，男，研究員，博士。主要研究方向為CAD。E-mail：qiangzou@cad.zju.edu.cn

31 July，2022；

12 October，2022

National Natural Science Foundation of China (62102355), Natural Science Foundation of Zhejiang Province (LQ22F020012)

ZOU Qiang (1990-), professor, Ph.D. His main research interest covers CAD. E-mail：qiangzou@cad.zju.edu.cn