鄒 強(qiáng)

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

鄒 強(qiáng)

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

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

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

1 概 述

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

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

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

1.1 從CAD到幾何建模

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

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

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

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

從這2個(gè)需求(尤其是第2個(gè))出發(fā)，CAD的具體內(nèi)涵會(huì)非常豐富。但不久后，人們意識(shí)到CAD應(yīng)當(dāng)聚焦于產(chǎn)品建模、產(chǎn)品分析和產(chǎn)品制造這3個(gè)內(nèi)容，因其更基礎(chǔ)、本質(zhì)[3]。但同期也有其他領(lǐng)域在研究產(chǎn)品分析和產(chǎn)品制造，這3個(gè)內(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)記的形式來(lái)存儲(chǔ)。正因?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é)模型來(lái)表示的問(wèn)題。具體的發(fā)展脈絡(luò)可參見(jiàn)文獻(xiàn)[7]。

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

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

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

然而，僅有曲面信息仍無(wú)法徹底解決歧義性和無(wú)效性問(wèn)題，如真實(shí)世界中并不存在零厚度物體，而且每個(gè)物體都有內(nèi)外之分。為此，實(shí)體模型被提出[12-13]，其特點(diǎn)在于對(duì)產(chǎn)品幾何信息進(jìn)行了完整的表示，從點(diǎn)到邊到面再到體。因其具有信息完整性，任何幾何性質(zhì)(如轉(zhuǎn)動(dòng)慣量)也都可以被計(jì)算機(jī)自動(dòng)計(jì)算出來(lái)[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è)計(jì)好并且不會(huì)發(fā)生變動(dòng)的產(chǎn)品，對(duì)整個(gè)設(shè)計(jì)過(guò)程，尤其是早期概念設(shè)計(jì)階段，幫助不大[7,18]。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖6 正則性定義示例

上述3個(gè)約束條件雖然可以完整刻畫(huà)大部分機(jī)械產(chǎn)品的形狀特性，但仍然允許實(shí)體具有非流形(non-manifold)邊界。為此，人們又在r-set的基礎(chǔ)之上添加了流形邊界的約束條件，即實(shí)體邊界上每個(gè)點(diǎn)的鄰域都是二維的[34]。這在數(shù)學(xué)上表達(dá)為實(shí)體邊界上每個(gè)點(diǎn)的(某個(gè))鄰域和二維圓盤(pán)是同胚的，而同胚指2個(gè)點(diǎn)集之間具有連續(xù)的、一一對(duì)應(yīng)的映射。這一約束條件是為了防止實(shí)體出現(xiàn)如圖8所示的線接觸或點(diǎn)接觸。這種情況在現(xiàn)實(shí)世界中是不可能的，因?yàn)槠湓诮佑|處具有無(wú)窮大應(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ì)算表示，即計(jì)算機(jī)模型(本質(zhì)是一種數(shù)據(jù)結(jié)構(gòu))。在過(guò)去的50年里，人們提出了多種實(shí)體模型格式，詳見(jiàn)文獻(xiàn)[6,14,35-36]。其中，CSG和B-rep是最常用的。

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

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

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

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

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

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

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

2.3 實(shí)體建模算法

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

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

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

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

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

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

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

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

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

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

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

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

(1) 2D草圖繪制。用戶首先在繪圖平面上指定幾何圖元(點(diǎn)與邊)的拓?fù)洌缓笤谄溟g添加幾何約束[64]。

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

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

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

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

3.1 永久命名

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

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

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

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

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

3.2 幾何約束求解

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

3.2.1 幾何約束分析與分解

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

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

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

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

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

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

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

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

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

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

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

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

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

總之，目前尚缺少有效的智能約束處理方法，現(xiàn)有方法仍處于初級(jí)發(fā)展階段。近來(lái)人工智能的快速發(fā)展也許會(huì)給這一領(lǐng)域帶來(lái)新的進(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]。所謂局部操作是指對(duì)B-rep模型的局部幾何元素直接進(jìn)行編輯的方法，例如圓角、偏移等。直接建模技術(shù)就是在tweaking這一局部操作的基礎(chǔ)之上發(fā)展起來(lái)的。Tweaking允許用戶對(duì)B-rep模型的邊界面進(jìn)行旋轉(zhuǎn)、平移等修改，但邊界面的變動(dòng)被嚴(yán)格控制在不破壞原有拓?fù)潢P(guān)系的范圍內(nèi)。

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

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

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

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

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

圖15 直接建模中的決策問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1) 實(shí)體的定義需要擴(kuò)展。如前所述，傳統(tǒng)實(shí)體概念所定義的對(duì)象是具有剛性、均質(zhì)特性的產(chǎn)品，而復(fù)雜結(jié)構(gòu)可能是剛性也可能是非剛性的(甚至是多模態(tài)的)，同時(shí)其還具有異質(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表示方法難以適用，否則將造成極大的存儲(chǔ)消耗。如何實(shí)現(xiàn)復(fù)雜結(jié)構(gòu)的輕量化表示，是當(dāng)前復(fù)雜結(jié)構(gòu)建模亟需解決的問(wèn)題。目前的隱式表示[130]、參數(shù)表示[131]、圖表示[132]、網(wǎng)格壓縮表示[133]以及混合表示等方法都具有很大的局限性，往往只能處理特定類型的復(fù)雜結(jié)構(gòu)[134]，與此同時(shí)，這些表示方法所能處理的結(jié)構(gòu)復(fù)雜度仍非常有限，特別是難以處理如圖17所示超復(fù)雜結(jié)構(gòu)(這些結(jié)構(gòu)如果以STL格式存儲(chǔ)，將達(dá)到幾百G存儲(chǔ)量)。故而，發(fā)展新的統(tǒng)一高效復(fù)雜結(jié)構(gòu)表示數(shù)據(jù)結(jié)構(gòu)是當(dāng)前需攻克的核心難題。

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

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

5.3 智能CAD、云CAD

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

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

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

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

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

6 總 結(jié)

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

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

[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

國(guó)家自然科學(xué)基金項(xiàng)目(62102355)；浙江省自然科學(xué)基金項(xiàng)目(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