淺談實(shí)體建模：歷史、現(xiàn)狀與未來

鄒 強(qiáng)

淺談實(shí)體建模：歷史、現(xiàn)狀與未來

鄒 強(qiáng)

(浙江大學(xué)CAD&CG國家重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310027)

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

CAD；幾何建模；實(shí)體建模；參數(shù)化建模；直接建模；結(jié)構(gòu)建模；智能CAD

1 概 述

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

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

本文將梳理實(shí)體建模的歷史發(fā)展脈絡(luò)，敘述其基礎(chǔ)理論、關(guān)鍵算法與難點(diǎn)、以及這些難點(diǎn)的解決現(xiàn)狀。同時，本文還將對實(shí)體建模的未來作出展望，重點(diǎn)關(guān)注Computer-Aided Design向Computer- Automated Design發(fā)展的趨勢。

1.1 從CAD到幾何建模

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

(1) 構(gòu)建產(chǎn)品的計算機(jī)模型并對之進(jìn)行處理，以滿足二戰(zhàn)后發(fā)展起來的數(shù)控機(jī)床對自動生成加工路徑的需求[2]，實(shí)質(zhì)上是為了滿足機(jī)器與機(jī)器間的協(xié)作需求；

(2) 構(gòu)建一個可以讓人和計算機(jī)一起協(xié)作的設(shè)計系統(tǒng)，其中人負(fù)責(zé)創(chuàng)造性任務(wù)，而計算機(jī)負(fù)責(zé)機(jī)械式任務(wù)[3-4]，如圖1所示，實(shí)質(zhì)上是為了滿足人與機(jī)器間的協(xié)作需求。

圖1 CAD系統(tǒng)中人與計算機(jī)的分工

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

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

圖2 產(chǎn)品幾何信息在產(chǎn)品全生命周期中的作用

圖3 CAD幾何建模方法發(fā)展總括圖

1.2 從幾何建模到實(shí)體建模

在眾多幾何建模方法[6]中，線框建模到曲面建模再到實(shí)體建模是CAD建模技術(shù)發(fā)展的初期階段，其主要關(guān)注產(chǎn)品幾何信息該以何種數(shù)學(xué)模型來表示的問題。具體的發(fā)展脈絡(luò)可參見文獻(xiàn)[7]。

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

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

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

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

1.3 從實(shí)體建模到參數(shù)化/直接建模

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

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

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

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

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

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

(2) 極高的建模自由度和效率，因?yàn)橹苯咏２僮髂軐⒁粋€實(shí)體模型變形到任意形狀；

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

上文簡述了實(shí)體建模技術(shù)的由來與歷史，下面將對實(shí)體建模、參數(shù)化建模和直接建模的關(guān)鍵技術(shù)進(jìn)行討論。

2 實(shí)體建模1.0 (早期發(fā)展)

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

2.1 實(shí)體數(shù)學(xué)定義

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

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

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

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

圖6 正則性定義示例

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

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

圖8 具有非流形邊界的實(shí)體圖例

2.2 實(shí)體模型表示

上述實(shí)體定義是產(chǎn)品幾何信息的數(shù)學(xué)抽象，即數(shù)學(xué)模型，實(shí)體模型是在數(shù)學(xué)抽象基礎(chǔ)之上的計算表示，即計算機(jī)模型(本質(zhì)是一種數(shù)據(jù)結(jié)構(gòu))。在過去的50年里，人們提出了多種實(shí)體模型格式，詳見文獻(xiàn)[6,14,35-36]。其中，CSG和B-rep是最常用的。

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

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

圖9 實(shí)體模型圖例

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

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

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

可以看出，B-rep和CSG具有一定的互補(bǔ)性。正因?yàn)槿绱耍F(xiàn)代實(shí)體建模系統(tǒng)一般采用B-rep和CSG相混合的表示格式[18,40-43]。CSG的二叉樹結(jié)構(gòu)作為骨架，B-rep模型替代了CSG中的體元，同時二叉樹的中間節(jié)點(diǎn)不僅存儲操作步驟，還存儲部分運(yùn)算結(jié)果，比如重要邊界面的信息。存儲這些中間信息目的是為了將操作從布爾擴(kuò)大至一些局部操作，如偏移、圓角等[16,40,44-45]。這些操作需引用被操作對象(即實(shí)體模型的某一局部幾何元素)，故而對這些對象進(jìn)行存儲或標(biāo)記至關(guān)重要。

2.3 實(shí)體建模算法

實(shí)體建模算法指構(gòu)建和編輯實(shí)體模型的算法，一般分為3個層次實(shí)現(xiàn)：①底層數(shù)值算法；②中層幾何/拓?fù)溆嬎悖虎凵蠈訉?shí)體操作。

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

此處不對具體的數(shù)值算法、幾何計算/拓?fù)渑卸ɑ驅(qū)嶓w操作的研究現(xiàn)狀進(jìn)行詳述，而是對其中具有一般性的魯棒性問題進(jìn)行討論。實(shí)體建模中的魯棒性問題主要有3個來源：

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

(2) 即使不存在任何表示和計算誤差，拓?fù)渑卸ńY(jié)果也可能與幾何數(shù)據(jù)不一致，并最終導(dǎo)致無效的實(shí)體模型。這種情況的根本原因在于B-rep數(shù)據(jù)結(jié)構(gòu)要求拓?fù)浜蛶缀伪３忠恢?，才能保證模型的有效性。然而，拓?fù)浜蛶缀螖?shù)據(jù)在B-rep中又是分離的，幾何數(shù)據(jù)的變動不會自動反映到拓?fù)鋽?shù)據(jù)中，反之亦然[50]。正因?yàn)榇?，有些拓?fù)鋽?shù)據(jù)雖然從自身來看是有效的，但和幾何一結(jié)合就會產(chǎn)生失效模型[51]。這方面典型的情況有模型修復(fù)時拓?fù)湫拚龥Q策引發(fā)如圖8所示模型自交(注意不是曲面自交)。所謂拓?fù)湫拚侵笇o效模型(即：是B-rep模型，但不滿足實(shí)體條件，如邊界不是流形的)的拓?fù)溥M(jìn)行調(diào)整，以使之變?yōu)橛行Ｐ汀?/p>

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

從上述討論可以看出，實(shí)體建模中的魯棒性問題本質(zhì)是幾何-拓?fù)洳灰恢聠栴}，其原因不全在數(shù)值誤差，反而更在于拓?fù)渑卸ǖ恼_性。

為解決由數(shù)值誤差引起的魯棒性問題(即來源(1))，一個自然的思路是將底層算法換用精確計算，如符號計算方法、有理數(shù)方法等[52-57]，但是這些方法往往在通用性或效率方面存在問題，并不實(shí)用。另一個思路是使用容差來保證即使存在計算誤差，拓?fù)渑卸ㄈ允钦_的[49,58-60]，如圖11所示。這種方法在理論上可完美解決幾何-拓?fù)洳灰恢聠栴}，實(shí)現(xiàn)魯棒建模，也是工業(yè)界所采用的方法，但是目前的容差設(shè)計方法主要以人工規(guī)則和閾值試錯的方式給出，尚缺少系統(tǒng)的方法。特別地，容差會在多個不同局部累積增大，當(dāng)其相遇時，會發(fā)生不一致情況，進(jìn)而導(dǎo)致錯誤的拓?fù)渑卸ā?/p>

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

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

3 實(shí)體建模2.0 (中期發(fā)展)

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

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

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

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

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

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

3.1 永久命名

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

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

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

除上述方法外，Shapiro將拓?fù)鋵W(xué)引入永久命名的研究中，提出了拓?fù)洳蛔?實(shí)質(zhì)上，Shapiro給出的條件是允許拓?fù)渥兓?，但是這種變化需滿足模型的邊界面發(fā)生連續(xù)變形。的必要條件[41,79-81]，這為研究各種永久命名方法的適用范圍提供了理論基礎(chǔ)。另外，人們還從特征語義的角度研究了參數(shù)變動下的不變量[82-83]，從限定參數(shù)變動域的角度來避免出現(xiàn)永久命名問題[84-86]。然而，這些工作多以純理論研究為主，尚未應(yīng)用于實(shí)際。

混合幾何、拓?fù)浜徒v史來處理永久命名問題是目前工業(yè)界常用的方法，如幾何內(nèi)核Open CasCade即采用類似文獻(xiàn)[70]中的方法。然而，這類方法往往需要混雜ad hoc規(guī)則，不夠系統(tǒng)，也不能完整解決永久命名問題，尤其是難以處理發(fā)生大拓?fù)渥儎拥那樾?。永久命名問題亟需新的思路，形成一個系統(tǒng)的解決方案。

3.2 幾何約束求解

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

3.2.1 幾何約束分析與分解

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

邏輯推演法[89-90]以一組幾何公理和推演規(guī)則為基礎(chǔ)，測試一個給定的幾何約束系統(tǒng)是否可以被邏輯推演出來。如果成功，那么該系統(tǒng)是恰定的；如果存在額外的幾何約束，那么該系統(tǒng)是過約束；反之，該系統(tǒng)為欠約束。這種方法本質(zhì)上是將數(shù)學(xué)中的公理化思想應(yīng)用到幾何約束分析與求解中，具有很高的數(shù)學(xué)價值。然而，目前所制定的幾何公理和推演規(guī)則離能夠?qū)嶋H應(yīng)用還遠(yuǎn)遠(yuǎn)不夠。

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

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

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

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

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

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

(3) 仍無法高效求解大型3D幾何約束系統(tǒng)。其原因一方面是因?yàn)槿鄙儆行У呐卸?zhǔn)則，約束分解的魯棒性問題突出；另一方面，傳統(tǒng)基于分解的思路難以應(yīng)對大型系統(tǒng)，也許并行計算是一個突破口。

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

3.2.2 幾何約束系統(tǒng)處理

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

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

總之，目前尚缺少有效的智能約束處理方法，現(xiàn)有方法仍處于初級發(fā)展階段。近來人工智能的快速發(fā)展也許會給這一領(lǐng)域帶來新的進(jìn)步。

4 實(shí)體建模3.0 (近期發(fā)展)

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

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

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

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

圖14 直接建模中的協(xié)調(diào)更新問題[124]

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

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

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

總體而言，直接建模最核心的問題是對模型更新方案進(jìn)行決策，其關(guān)鍵挑戰(zhàn)在于決策方法的系統(tǒng)性，從而實(shí)現(xiàn)魯棒的模型更新。當(dāng)前的問題主要集中于[121,128]：

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

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

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

5 實(shí)體建模4.0 (未來發(fā)展)

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

5.1 從支持詳細(xì)設(shè)計到支持全過程設(shè)計——參數(shù)/直接融合建模

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

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

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

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

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

5.2 從Computer-Aided Design 到Computer-Automated Design——復(fù)雜結(jié)構(gòu)建模、設(shè)計、仿真與制造

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

(1) 實(shí)體的定義需要擴(kuò)展。如前所述，傳統(tǒng)實(shí)體概念所定義的對象是具有剛性、均質(zhì)特性的產(chǎn)品，而復(fù)雜結(jié)構(gòu)可能是剛性也可能是非剛性的(甚至是多模態(tài)的)，同時其還具有異質(zhì)、多材料等特點(diǎn)?，F(xiàn)有實(shí)體定義不能覆蓋這些特點(diǎn)，需要被擴(kuò)展以適用復(fù)雜結(jié)構(gòu)。

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

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

圖17 簡單、復(fù)雜、高度復(fù)雜結(jié)構(gòu)實(shí)例[137-141]

5.3 智能CAD、云CAD

智能計算、云計算、并行計算以及虛擬現(xiàn)實(shí)等新一代計算技術(shù)將對CAD的發(fā)展有極大促進(jìn)作用。

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

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

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

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

6 總 結(jié)

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

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

[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

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

鄒 強(qiáng)(1990-)，男，研究員，博士。主要研究方向?yàn)镃AD。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