三維實(shí)體造型技術(shù)-第一部分-3.doc

第 6 節(jié) 參數(shù)化設(shè)計(jì)前面談到的造型技術(shù)在具體應(yīng)用于一個(gè)產(chǎn)品模型后，形成了固定的模型數(shù)據(jù),當(dāng)需要改變產(chǎn)品模型的某一數(shù)據(jù)時(shí)，只有刪除該模型，再重新進(jìn)行模型的造型設(shè)計(jì)。這對(duì)于同類(lèi)產(chǎn)品不同型號(hào)的產(chǎn)品設(shè)計(jì)造成了極大的不便。因而在目前流行的 CAD 系統(tǒng)中又創(chuàng)造應(yīng)用了參數(shù)化設(shè)計(jì)技術(shù)，可以對(duì)已有產(chǎn)品模型的數(shù)據(jù)進(jìn)行修改，以形成新的產(chǎn)品模型，從而加快產(chǎn)品設(shè)計(jì)的速度。在新產(chǎn)品的研制過(guò)程中，約70%80% 的成本耗費(fèi)于設(shè)計(jì)階段，因此，如何開(kāi)發(fā)、研究先進(jìn)的設(shè)計(jì)方法和工具以提高產(chǎn)品設(shè)計(jì)的效率是至關(guān)重要的。設(shè)計(jì)是創(chuàng)造性的活動(dòng)，需經(jīng)多次循環(huán)而逐步求精。無(wú)論是全新設(shè)計(jì)或是局部更新設(shè)計(jì)，設(shè)計(jì)師總是在設(shè)計(jì)要求等條件的限制下，自設(shè)計(jì)開(kāi)始的概念設(shè)計(jì)階段，便開(kāi)始將其設(shè)計(jì)活動(dòng)勾畫(huà)在圖紙之上。從概念到具體的結(jié)構(gòu)設(shè)計(jì)，設(shè)計(jì)師的幾乎所有創(chuàng)作活動(dòng)都蘊(yùn)含于產(chǎn)品圖紙(含電子圖檔)的演變與衍生之中。雖然圖形的生成與演變?cè)谠O(shè)計(jì)活動(dòng)中占有基礎(chǔ)性的地位，但并非設(shè)計(jì)活動(dòng)的基本特征和本質(zhì)表現(xiàn)。人工智能學(xué)研究認(rèn)為：設(shè)計(jì)問(wèn)題是約束滿足問(wèn)題(CSP：constraint satisfaction problem), 即給定功能、結(jié)構(gòu)、材料及制造等方面的約束描述，求得設(shè)計(jì)對(duì)象的細(xì)節(jié)。由此而生的參數(shù)化設(shè)計(jì)就是：用幾何約束、工程方程與關(guān)系來(lái)說(shuō)明產(chǎn)品模型的形狀特征，從而達(dá)到設(shè)計(jì)一簇在形狀或功能上具有相似性的設(shè)計(jì)方案。目前能處理的幾何約束類(lèi)型基本上是組成產(chǎn)品形體的幾何實(shí)體公稱(chēng)尺寸關(guān)系和尺寸之間的工程關(guān)系。參數(shù)化設(shè)計(jì)的關(guān)鍵是：幾何約束關(guān)系的提取和表達(dá)、幾何約束的求解以及參數(shù)化幾何模型的構(gòu)造。目前，二維參數(shù)化設(shè)計(jì)技術(shù)已發(fā)展得較為成熟，在參數(shù)化繪圖方面已得到了廣泛應(yīng)用。而三維參數(shù)化造型能處理的問(wèn)題還比較簡(jiǎn)單，能處理的類(lèi)型主要是軸線、平面和軸對(duì)稱(chēng)面；能處理的約束類(lèi)型還很有限，如：(1) 兩個(gè)或多個(gè)平面間的垂直距離；(2) 兩個(gè)或多個(gè)軸線間的垂直距離；(3) 兩個(gè)或多個(gè)平面間的角度；(4) 軸和平面間的垂直距離；(5) 兩個(gè)或多個(gè)軸線間的角度；(6) 軸和平面間的角度；(7) 軸對(duì)稱(chēng)面的半徑等。在參數(shù)化設(shè)計(jì)中，幾何約束關(guān)系的表示形式主要有：(1) 由算術(shù)運(yùn)算符、邏輯比較運(yùn)算符和標(biāo)準(zhǔn)數(shù)學(xué)函數(shù)組成的等式或不等式關(guān)系。它們可以在參數(shù)化造型系統(tǒng)的命令窗口中直接以命令行形式輸入。(2) 曲線關(guān)系。直接把物理實(shí)驗(yàn)曲線或其他特性曲線用于幾何造型。(3) 關(guān)系文件。它是許多關(guān)系命令行語(yǔ)句和特定語(yǔ)句的集合。多種幾何約束關(guān)系，包括聯(lián)立方程組可以寫(xiě)成一種特定格式的文件(即用戶編程), 輸入到計(jì)算機(jī)中，成批驅(qū)動(dòng)幾何設(shè)計(jì)。例如，確定一個(gè)立方體的長(zhǎng)、寬、高的約束條件可以是：立方體的底面積等于 100, 底面周長(zhǎng)等于 50 。(4) 面向人工智能的知識(shí)表達(dá)方式。這種方式將組成幾何形體的約束關(guān)系、幾何與拓?fù)浣Y(jié)構(gòu)用一階邏輯謂詞的形式描述，并寫(xiě)人知識(shí)庫(kù)中。知識(shí)表達(dá)的方式：一方面是以符號(hào)化形式表達(dá)各種類(lèi)型的數(shù)據(jù)，求取符號(hào)解；另一方面是加上基于約束的幾何推理，求取數(shù)值解，從而可在更高程度上實(shí)現(xiàn)機(jī)械產(chǎn)品的智能設(shè)計(jì)。本節(jié)在簡(jiǎn)述參數(shù)化設(shè)計(jì)相關(guān)概念的基礎(chǔ)上，介紹參數(shù)化設(shè)計(jì)的約束推理/求解算法。最后給出一種典型的參數(shù)化設(shè)計(jì)的應(yīng)用實(shí)例。 一基于約束的參數(shù)化設(shè)計(jì)概述基于約束的 CAD 系統(tǒng)并不是傳統(tǒng) CAD 系統(tǒng)的簡(jiǎn)單擴(kuò)展，而是以一種全新的思維和方式來(lái)進(jìn)行產(chǎn)品的創(chuàng)新和修改設(shè)計(jì)。它用約束來(lái)表達(dá)產(chǎn)品模型的形狀特征，定義一組參數(shù)以控制設(shè)計(jì)結(jié)果，從而能夠通過(guò)調(diào)整參數(shù)來(lái)修改設(shè)計(jì)、模型，并能方便地創(chuàng)建一系列在形狀或功能上相似的設(shè)計(jì)方案。 在設(shè)計(jì)過(guò)程中，參數(shù)化草圖輸入大大提高了圖形輸入和幾何造型的效率；產(chǎn)品模型的修改通過(guò)尺寸驅(qū)動(dòng)或參數(shù)驅(qū)動(dòng)實(shí)現(xiàn)。給定幾組參數(shù)值便可實(shí)現(xiàn)系列零件或部件的自動(dòng)生成，約束的修改使對(duì)設(shè)計(jì)目標(biāo)依賴(lài)關(guān)系的描述成為可能。基于約束的參數(shù)化變量化設(shè)計(jì)技術(shù)為初始設(shè)計(jì)、產(chǎn)品模型的修改、系列零件族的生成、多方案比較等提供了強(qiáng)有力的手段，在工程繪圖、實(shí)體造型、裝配、公差分析與綜合、機(jī)構(gòu)仿真、優(yōu)化設(shè)計(jì)、數(shù)控加工(NC) 等領(lǐng)域發(fā)揮著越來(lái)越大的作用。1參數(shù)化設(shè)計(jì)與變量化設(shè)計(jì)參數(shù)化設(shè)計(jì)：是指在構(gòu)造產(chǎn)品模型時(shí)，模型結(jié)構(gòu)在保持模型拓?fù)潢P(guān)系不變的前提下，可隨尺寸參數(shù)或工程參數(shù)的具體數(shù)值變化而自動(dòng)改變，形成新的產(chǎn)品模型。圖 6-1 為一個(gè)實(shí)體模型的視圖。用參數(shù)化設(shè)計(jì)系統(tǒng)構(gòu)造此實(shí)體模型時(shí)，系統(tǒng)將定義各尺寸為參數(shù)變量名 X、Y、U、V、D 等，當(dāng)設(shè)計(jì)者改變參數(shù)變量 U、V、D 分別為 150mm、200mm、160mm 時(shí)，則實(shí)體模型將從如圖 a）的結(jié)構(gòu)變?yōu)閳D b）的結(jié)構(gòu)，但當(dāng) U 的數(shù)值大于 X+D/2 時(shí)，將使實(shí)體中的孔不在實(shí)體內(nèi)部，則從邏輯上是不可能的。因而在改變尺寸變量值時(shí)，應(yīng)滿足一定的條件。a) b)圖 6-1 參數(shù)化設(shè)計(jì)的示意圖從上面的實(shí)例可以看出，參數(shù)化設(shè)計(jì)是使用約束來(lái)實(shí)現(xiàn)設(shè)計(jì)與修改產(chǎn)品的一種方法。約束可以理解為若干個(gè)對(duì)象之間的相互關(guān)系，即限制一個(gè)或多個(gè)對(duì)象滿足一定的關(guān)系、條件。比如上面例子中孔不能存在于實(shí)體之外即為一個(gè)約束?；诩s束的設(shè)計(jì)方法最主要的特點(diǎn)就是：能夠處理用戶對(duì)幾何體施加的一系列約束，而用戶無(wú)需關(guān)心這些約束是如何被滿足的。參數(shù)化設(shè)計(jì) (parametric design)和變量化設(shè)計(jì)（variation design） 是基于約束的設(shè)計(jì)方法中的兩種主要形式。它們都能解決設(shè)計(jì)時(shí)所必須考慮的幾何圖形約束和工程約束等問(wèn)題，具有在幾何圖形尺寸變動(dòng)時(shí)自動(dòng)更新圖形的能力和尺寸驅(qū)動(dòng) (dimension driven)功能。無(wú)論參數(shù)化設(shè)計(jì)系統(tǒng)還是變量化設(shè)計(jì)系統(tǒng)，工程師都可以用幾何約束(如平行、垂直等)和工程約束(通常以工程方程式來(lái)表達(dá)，如模型的性質(zhì)、重量、載荷、可靠性、結(jié)構(gòu)等)來(lái)設(shè)定產(chǎn)品設(shè)計(jì)上的要求。這些系統(tǒng)不僅是在初始的幾何圖形中要能滿足工程約束的設(shè)計(jì)要求，而且在圖形參數(shù)變更時(shí)也要能保持整體工程關(guān)系不變。這樣，工程師就不用再去考慮如何更新設(shè)計(jì)幾何造型以符合設(shè)計(jì)上要求的幾何圖形約束和工程約束關(guān)系，使 CAD 系統(tǒng)能真正捕捉到設(shè)計(jì)者對(duì)產(chǎn)品的設(shè)計(jì)意圖。參數(shù)化設(shè)計(jì)系統(tǒng)和變量化設(shè)計(jì)系統(tǒng)二者表面上看起來(lái)很相似，但它們技術(shù)上的差別主要體現(xiàn)在：約束方程的定義和求解方式上。參數(shù)化設(shè)計(jì)系統(tǒng)：所有約束方程的建立和求解依賴(lài)于創(chuàng)建它們的順序，每個(gè)幾何元素根據(jù)先前已知的幾何元素定位。程序設(shè)計(jì)者要預(yù)設(shè)一些幾何約束，供設(shè)計(jì)工程師在建立幾何圖形時(shí)使用。系統(tǒng)調(diào)用這些預(yù)設(shè)約束的組合，以確定各幾何元素的相關(guān)位置；參數(shù)求解采用順序求解策略，后面的元素求解依賴(lài)于生成它的幾何元素。求解過(guò)程不能逆向進(jìn)行，即求解是過(guò)程式的；參數(shù)化方法注重于幾何圖形元素的鄰域，對(duì)設(shè)計(jì)模型的整體修改比較困難，難以調(diào)整約束依賴(lài)關(guān)系和求解順序，無(wú)法處理特性約束，因此最適用于已完全特性化的設(shè)計(jì)問(wèn)題（即無(wú)需在設(shè)計(jì)方案上作重大改變）, 如具有明確層次依賴(lài)關(guān)系的裝配體設(shè)計(jì)、系列標(biāo)準(zhǔn)件庫(kù)的創(chuàng)建等。變量化設(shè)計(jì)系統(tǒng)：針對(duì)設(shè)計(jì)對(duì)象的操作具有更好的靈活性和自由度，約束的指定是陳述式的，即約束的指定沒(méi)有先后順序之分，約束依賴(lài)關(guān)系可以根據(jù)設(shè)計(jì)者意圖隨意更改；它通常采用并行求解的策略，通過(guò)同時(shí)求解一組約束方程來(lái)確定產(chǎn)品的形狀和尺寸；另外，幾何約束和工程約束可以聯(lián)立整體求解，因而功能更為強(qiáng)大；但是也應(yīng)該看到，大型約束方程組整體求解的效率和穩(wěn)定性顯然不如參數(shù)化設(shè)計(jì)方法。形象地說(shuō)，陳述式的變量化設(shè)計(jì)系統(tǒng)告訴計(jì)算機(jī)做什么，過(guò)程式的參數(shù)化設(shè)計(jì)系統(tǒng)告訴計(jì)算機(jī)怎么做。它們具有各自的適用范圍，用戶可以根據(jù)自己特定的設(shè)計(jì)要求進(jìn)行取舍。當(dāng)前基于約束的設(shè)計(jì)方法研究趨向于將二者有機(jī)地結(jié)合起來(lái)，相互借鑒，優(yōu)勢(shì)互補(bǔ)，以發(fā)揮更大的效益。一般地，如無(wú)特殊說(shuō)明，我們把基于約束的設(shè)計(jì)方法簡(jiǎn)稱(chēng)為參數(shù)化設(shè)計(jì)。2常用的參數(shù)化設(shè)計(jì)方法（1）數(shù)值約束求解方法這是一種面向非線性方程組整體求解的代數(shù)方法，最早由英國(guó)劍橋大學(xué)的 Hillyard 提出。美國(guó) MIT 的 Gossard 研究小組發(fā)展和完善了這一理論，稱(chēng)為變量幾何法。該方法將幾何形狀定義成一系列的特征點(diǎn)，將約束表示成以特征點(diǎn)坐標(biāo)為變?cè)姆蔷€性代數(shù)方程組，通過(guò)數(shù)值迭代方法求解非線性方程組，從而確定幾何細(xì)節(jié)。非線性方程組的求解通?；?Newton-Raphson 迭代法。非線性方程組表示為：, 其中: , 對(duì)于初值 XO, 第 n+1 次迭代的 Xn+1 值由以下迭代公式得到: 其中： 令： 則有: 于是得到：其中，為 Jacobian 矩陣 表示各個(gè)變量的微小位移。,表示方程組的殘差。經(jīng)過(guò)反復(fù)迭代，直至 ,就得到了方程組的解。約束集的有效性可以通過(guò)判斷 Jacobian 矩陣的秩來(lái)實(shí)現(xiàn)。數(shù)值求解的主要優(yōu)點(diǎn)在于：能適應(yīng)較大范圍的約束類(lèi)型，特性約束可以通過(guò)約束方程組的聯(lián)立求解得到處理；但它難以避免數(shù)值方法求解穩(wěn)定性差的問(wèn)題，方程組整體求解的規(guī)模和速度較難得到有效的控制，迭代初值與步長(zhǎng)的選取也會(huì)影響算法的成敗。從用戶的角度看，很難以一組方程式刻畫(huà)幾何元素之間的約束關(guān)系，而且，當(dāng)出現(xiàn)不一致的情況或非預(yù)期的結(jié)果時(shí)，也得不到準(zhǔn)確的反饋。（2）基于規(guī)則的幾何推理方法基于規(guī)則的幾何推理方法運(yùn)用規(guī)則來(lái)建立和執(zhí)行構(gòu)造步驟，又稱(chēng)為規(guī)則構(gòu)造式求解方法。它基于這樣一個(gè)事實(shí)：即在工程圖中的絕大多數(shù)配置都可以通過(guò)直尺、圓規(guī)和量角器繪出，約束通過(guò)構(gòu)造的方式得到滿足。這樣對(duì)用戶來(lái)說(shuō)更顯得自然而且適合于交互式查錯(cuò)。 Aldefeld 采用一個(gè)基于符號(hào)推理和操作的專(zhuān)家系統(tǒng)，建立一個(gè)規(guī)則體系，將幾何形體的約束關(guān)系用一階邏輯謂詞描述，存人知識(shí)庫(kù)中。系統(tǒng)從知識(shí)庫(kù)中提取出有關(guān)信息，通過(guò)推理機(jī)逐步推導(dǎo)出幾何細(xì)節(jié)。推理示意圖如圖 62 所示。圖 62 基于規(guī)則的幾何推理知識(shí)庫(kù)包含某特定幾何模型的知識(shí)，初始內(nèi)容是給定的約束，通過(guò)規(guī)則推理出的事實(shí)不斷累加。規(guī)則庫(kù)收集相關(guān)規(guī)則，通常僅有一個(gè)規(guī)則子集作用于某給定模型，但預(yù)先無(wú)法知道。推理機(jī)是控制部分，其任務(wù)是按某些策略選擇規(guī)則并應(yīng)用于現(xiàn)有事實(shí)。處理的中心點(diǎn)在于模式匹配，即檢驗(yàn)每個(gè)原子表在知識(shí)庫(kù)中是否有所對(duì)應(yīng)。推理的結(jié)論成為新的事實(shí)，推理機(jī)記錄了所有成功的規(guī)則應(yīng)用。幾何推理是要從現(xiàn)有的已知約束中派生出盡可能多的知識(shí)。因此每當(dāng)一個(gè)新的約束得到后，推理過(guò)程啟動(dòng)。所有規(guī)則循環(huán)使用，直至沒(méi)有新的事實(shí)產(chǎn)生。約束處理分為兩個(gè)階段：1) 將幾何約束一一讀入系統(tǒng)，并加入知識(shí)庫(kù)，啟動(dòng)推理機(jī)；將所有可派生的知識(shí)存入系統(tǒng)，一旦某個(gè)約束被刪除，推理機(jī)回溯。2) 在后處理階段，推理機(jī)輸出重建步驟，把規(guī)則名翻譯成相應(yīng)的處理過(guò)程，形成構(gòu)造計(jì)劃，一步步執(zhí)行，從而構(gòu)造出整個(gè)幾何體。（3）基于圖論的約束求解方法這種方法將一般幾何約束系統(tǒng)表示成圖 (graph)的形式，通過(guò)分析約束圖推導(dǎo)出一系列構(gòu)造過(guò)程，再根據(jù)這些構(gòu)造步驟來(lái)導(dǎo)出整個(gè)幾何體。這種方式又稱(chēng)為圖構(gòu)造式求解方法。由于推理過(guò)程基于圖論算法，因而理論嚴(yán)密，速度快，效率高。Fitzrald 構(gòu)造了一種 x 向和 y 向尺寸樹(shù)，如果樹(shù)中出現(xiàn)了圖(即出現(xiàn)了封閉回路), 則表明出現(xiàn)了多余的尺寸約束。該方法只能處理水平和垂直方向的距離尺寸，只適用于簡(jiǎn)單的工程圖形。將尺寸樹(shù)的概念一般化，用圖來(lái)表達(dá)幾何約束系統(tǒng)，其中：頂點(diǎn)代表幾何元素，邊代表幾何元素之間的約束關(guān)系；再引人了循環(huán)尺寸約束，可拓展這一方法，分析約束圖的三連通部分，對(duì)每個(gè)三連通域分別求解。求解過(guò)程是遞歸的，亦即一旦某個(gè)三連通域已知，它就會(huì)在圖上被歸約為一個(gè)頂點(diǎn)，并在歸約圖上成為其他三連通域的成員。若將幾何約束系統(tǒng)抽象為無(wú)向圖，頂點(diǎn)為幾何實(shí)體稱(chēng)為 geom , 一組可獨(dú)立確定相對(duì)形位的幾何實(shí)體集稱(chēng)為 macrogeoms，頂點(diǎn)的自由度及頂點(diǎn)之間的約束度以權(quán)值的形式分別記錄在頂點(diǎn)和弧上。約束機(jī)的求解過(guò)程大致分為兩步：1) 由鏈?zhǔn)剿阉骱铜h(huán)路搜索在圖上找出符合 macro 條件的幾何實(shí)體集，并記為 macro 頂點(diǎn)。 2) 從約束變動(dòng)的 macro 出發(fā)，不斷地尋找上一層 macro, 并識(shí)別其約束模式，調(diào)用相應(yīng)的計(jì)算方法，得到問(wèn)題的解。(4)符號(hào)代數(shù)求解法這種方法將約束集轉(zhuǎn)化為一個(gè)代數(shù)方程組，利用符號(hào)代數(shù)法求解該方程組。該方法雖然能求解一般的非線性代數(shù)方程組，但在運(yùn)行時(shí)間和效率上有待進(jìn)一步改進(jìn)。 （5）基于構(gòu)造過(guò)程的方法基于構(gòu)造過(guò)程的方法在圖形輸入的過(guò)程中借助造型命令自動(dòng)捕捉設(shè)計(jì)者的意圖。這種方法記錄了用戶在造型過(guò)程中的每一步操作，基本思想是：造型操作與幾何約束之間有著對(duì)應(yīng)的關(guān)系。造型過(guò)程能夠用來(lái)管理和維護(hù)反映幾何元素之間約束關(guān)系的內(nèi)部數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)的修改可以通過(guò)修改造型過(guò)程的某一參數(shù)得到。Roller 擴(kuò)展了傳統(tǒng) CAD 系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)，以便更好地捕捉設(shè)計(jì)者的意圖，其主要做法包括：1) 引入三種類(lèi)型的幾何實(shí)體：固定的、可變的和柔性的；2) 通過(guò)對(duì)命令語(yǔ)義的推理，自動(dòng)建立幾何約束關(guān)系；3) 跟蹤構(gòu)造幾何體（輔助線）、面的使用，捕捉構(gòu)造意圖；4) 存儲(chǔ)構(gòu)造順序；5) 生成由傳統(tǒng) CAD 的命令組成的構(gòu)造計(jì)劃；6) 對(duì)于給定的某一組尺寸參數(shù)，執(zhí)行構(gòu)造方案。基于構(gòu)造過(guò)程的方法，對(duì)于結(jié)構(gòu)相同尺寸不同的零件設(shè)計(jì)是十分有效的；但是由于必須嚴(yán)格遵循構(gòu)造過(guò)程，對(duì)于那些設(shè)計(jì)要求不斷變化的設(shè)計(jì)環(huán)境則不太適用，而且難以利用傳統(tǒng) CAD 系統(tǒng)生成的圖形，另外，也無(wú)法處理耦合程度高的循環(huán)約束情形。由于空間問(wèn)題的復(fù)雜性,3D 參數(shù)化方法難以實(shí)現(xiàn)陳述式的表達(dá)、規(guī)劃和求解，因而也多采用基于幾何模型構(gòu)造過(guò)程的方法。二約束推理求解算法基于約束的產(chǎn)品描述方法就是：將產(chǎn)品的功能、特性、形狀等屬性通過(guò)約束的形式表示出來(lái)，然后采用某種算法使這些約束能同時(shí)得到滿足，并在設(shè)計(jì)的整個(gè)過(guò)程中得到一致的維護(hù)。一個(gè)基于約束的產(chǎn)品設(shè)計(jì)過(guò)程，實(shí)際上就是一個(gè)約束指定和約束滿足的過(guò)程，它們不斷循環(huán)求精，直至所有設(shè)計(jì)要求得到滿足。約束是特定元素之間必須滿足的一組關(guān)系。約束滿足問(wèn)題可以通過(guò)一個(gè)有限集以及作用在這個(gè)有限集上的一組關(guān)系來(lái)定義。在一個(gè)約束系統(tǒng) M =(E,C) 中，對(duì)于一個(gè)有限的元素集 E= ei |i =1, ，n ，存在一組關(guān)系 C= cj |j=1, ,m , 其中要求所有 ei 滿足cj(e1, ,ej )。CSP 的主要任務(wù)就是：考察是否存在對(duì)于每一個(gè) ei E, 都可使得每一個(gè) cj C 得到滿足。如果存在這樣的 ei 的解，則能夠把它找出來(lái)。這個(gè)解又稱(chēng)作 M 的一個(gè)實(shí)例，它是任何滿足 C 的元素集合，獲取 M 的實(shí)例是通過(guò)對(duì) C 中變量的賦值實(shí)現(xiàn)的。1約束的表示與分類(lèi)對(duì)于一般的參數(shù)化 CAD 系統(tǒng)，其中的約束分為幾何約束和工程約束。工程約束是指：幾何約束系統(tǒng)中幾何元素之間固有的約束關(guān)系，它反映了產(chǎn)品在工程語(yǔ)義上的設(shè)計(jì)要求，一般以幾何設(shè)計(jì)參數(shù)為變?cè)募s束方程式的形式提供。例如：活塞的直徑往往是由該活塞必須傳遞的功率來(lái)決定的，可以定義如下工程約束：d=f(P), 其中 d 為活塞直徑，P 為活塞傳遞功率，因此根據(jù)傳遞功率可確定活塞的幾何參數(shù)。工程約束的引人使得設(shè)計(jì)者可以直接關(guān)注設(shè)計(jì)的功能要求，從而為主設(shè)計(jì)提供了強(qiáng)有力的支持。本節(jié)主要討論幾何約束的分類(lèi)和描述。幾何約束：包含兩種類(lèi)型：結(jié)構(gòu)約束和尺寸約束。結(jié)構(gòu)約束：是指幾何元素之間的拓?fù)浣Y(jié)構(gòu)關(guān)系，描述了幾何元素的空間相對(duì)位置和連接方式，其屬性值在參數(shù)化設(shè)計(jì)過(guò)程中保持不變。它在工程圖中往往是隱含的，并不明確給出，如平行、垂直、相切等。尺寸約束：是通過(guò)圖上的尺寸標(biāo)注表示的約束，例如距離、角度等。工程圖中的尺寸標(biāo)注是幾何體的一個(gè)直接和自然的描述，從而提供了修改幾何形體的合適方式。尺寸驅(qū)動(dòng)的目的:就是根據(jù)尺寸標(biāo)注值的變化修改圖形，并保持圖形變化前后的拓?fù)浣Y(jié)構(gòu)關(guān)系不變。結(jié)構(gòu)約束和尺寸約束可以統(tǒng)一為一種表示方式，用以下形式表示：C = ( T , 01 , 02 , V )其中: C表示約束；T表示約束類(lèi)型；O1 , 02 分別表示約束對(duì)象；V表示約束值，數(shù)據(jù)類(lèi)型可以是整型或?qū)嵭汀Ｕ停捍斫Y(jié)構(gòu)約束，體現(xiàn)了對(duì)某種幾何拓?fù)浣Y(jié)構(gòu)關(guān)系的肯定，是一種屬性關(guān)系，不含數(shù)量關(guān)系；實(shí)型：代表尺寸約束，有數(shù)量上的關(guān)系。約束值也可能有正負(fù)號(hào)，以體現(xiàn)約束的方向。如圖 63 所示，直線具有方向性,L1 相對(duì)于 L2 的角度約束值為,是因?yàn)閺?Ll 的正向逆時(shí)針旋轉(zhuǎn)到 L2 的正向測(cè)量的角度值為；L2 相對(duì)于 L1 的角度約束值為-，是因?yàn)閺?L2 的正向順時(shí)針旋轉(zhuǎn)到 Ll 的正向測(cè)量的角度值為。圖 63 約束的方向性帶符號(hào)的約束體現(xiàn)了幾何元素之間相互約束的方向性。它對(duì)幾何體拓?fù)浣Y(jié)構(gòu)進(jìn)行了更明確的限定，從而有效地限制了多解情況的發(fā)生。以平行約束為例，見(jiàn)圖 64 給定兩直線平行的約束，并不意味著兩直線的夾角一定是 0。夾角為 0意味著兩直線同向；兩直線也可能反向，這時(shí)兩直線夾角為180。因此可以用符號(hào)區(qū)分兩種不同的平行約束，對(duì)幾何圖形作進(jìn)一步的限定。圖 64 平行約束（1） 結(jié)構(gòu)約束l) 平行 (parallel )約束 (PAR , L1 , L2 , +1 )： 兩直線平行且方向相同。 (PAR , L1 , L2 , -1 )： 兩直線平行且方向相反。2) 垂直 (perpendicular) 約束 (PER , Ll , L2 , +1 )：兩直線垂直 ,L1 逆時(shí)針旋轉(zhuǎn) 90與 L2 重合 ( 見(jiàn) 65(a) 。 (PER , LI , L2 , -1 ): 兩直線垂直 ,L1 順時(shí)針旋轉(zhuǎn) 90與 L2 重合 ( 見(jiàn)圖 65(b )。圖 65 垂直約束3) 兩圓相切約束 (TAN_CC , C1 , C2 , +1 ): 兩圓外切 ( 見(jiàn)圖 66(a) 。 (TAN_CC , C1 , C2 , -l )：兩圓內(nèi)切 ( 見(jiàn)圖 66(b) 。圖 66 兩圓相切約束4) 線圓相切約束 (TAN_LC , L , C , +l )： 線圓相切，圓心在直線的正半平面 (見(jiàn)圖 67(a)。 (TAN_LC , L , C , -l )： 線圓相切，圓心在直線的負(fù)半平面 (見(jiàn)圖 67(b) 。 圖67 線圓相切約束5) 點(diǎn)在直線上(ON_L , P , L , +1 )： 點(diǎn) P 在直線 L 上 ( 見(jiàn)圖 68 )。 圖 68 點(diǎn)在直線上6) 點(diǎn)在圓上(ON_C , P , C , +1 )：點(diǎn) P 在圓 C 上 ( 見(jiàn)圖 69)。圖 69 點(diǎn)在圓上（2）尺寸約束1) 點(diǎn)與點(diǎn)的距離約束(D_PP , P1 , P2 , d )： 點(diǎn) P1 到 P2 的距離是 d( 見(jiàn)圖 610) 。 圖 610 點(diǎn)與點(diǎn)的距離約束2) 點(diǎn)到線的距離約束 (D_PL , P , L , d )： 點(diǎn) P 到直線 L 的距離是 d, 點(diǎn) P 在直線 L 的正半平面（見(jiàn)圖 611（a）。 (D_PL , P , L , -d )： 點(diǎn) P 到直線 L 的距離是 d, 點(diǎn) P 在直線 L 的負(fù)半平面 ( 見(jiàn)圖 611（b）)。圖 611 點(diǎn)到線的距離約束3) 平行線之間的距離約束（如圖） (D_LL , L1 , L2 , d )：直線 L1 與 L2 的距離是 d, L1 與 L2 同向 ( 見(jiàn)圖 611(a) )。 (D_LL , L1 , L2 , -d )： 直線 L1 與 L2 的距離是 d, Ll 與 L2 異向 ( 見(jiàn)圖 611(b) )。 圖 612 平行線之間的距離約束4) 兩直線的角度約束(ANG , Ll , L2 , )： 直線 L1 到直線 L2 的角度是 （見(jiàn)圖 612） 。圖 613 兩直線的角度約束5) 半徑和直徑約束約束對(duì)象的內(nèi)部屬性約束均是一元約束，其約束滿足過(guò)程比較簡(jiǎn)單，只需對(duì)幾何元素進(jìn)行固有參變量的賦值（見(jiàn)圖 613）。圖 614 半徑和直徑約束（3）幾何實(shí)體的自由度自由度指幾何實(shí)體固有的獨(dú)立運(yùn)動(dòng) (自由) 變量的數(shù)目，記為 DOF(e)(degree of freedom), 其中 e 代表某一特定幾何實(shí)體。對(duì)于二維平面上的點(diǎn)和直線，它們的自由變量數(shù)目是 2, 故其自由度也是 2 。對(duì)于平面上的圓，方程 (x-xo)2 + (y-yo)2 = r2 包含了 3 個(gè)自由變量，因而其自由度為 3 。對(duì)于二維平面上的剛體，它具有兩個(gè)平移自由度和一個(gè)轉(zhuǎn)動(dòng)自由度，故剛體自由度為 3, 記為 DOR (degree of rigid)。而對(duì)于三維空間上的剛體, DOR=6 。(4) 約束的約束度由某個(gè)約束引起的相關(guān)幾何實(shí)體自由度的減少量稱(chēng)為該約束的約束度，記為 DOC(c), 其中 c 代表約束類(lèi)型。約束實(shí)質(zhì)上表現(xiàn)為一組約束方程，約束的引入會(huì)限制幾何體的運(yùn)動(dòng)，從而導(dǎo)致了相關(guān)幾何實(shí)體的自由度的減少。幾何約束的約束度 DOC 一般均為 1 。少數(shù)約束 DOC 超過(guò) 1 的約束類(lèi)型可以分解成幾個(gè) DOC 為 1 的基本約束類(lèi)型，這樣便于進(jìn)行約束的管理和維護(hù)。例如兩直線共線約束，其 DOC=2, 可以將它轉(zhuǎn)化成兩條直線平行和距離為 0 的兩個(gè)基本約束，其約束度均為 1 。幾何約束系統(tǒng)中的常見(jiàn)約束均為二元約束，因而該模型中幾何元素及其相互之間的約束關(guān)系可以規(guī)范地以幾何約束圖 (GCG：geometric constraint graph) 的結(jié)構(gòu)來(lái)表達(dá)。在 GCG=(V,E) 中頂點(diǎn)集合 V 代表基本幾何元素，邊集合 E 代表幾何元素之間的幾何約束。初始建立的圖是無(wú)向圖，因?yàn)轫旤c(diǎn)的地位和作用等同，鄰接點(diǎn)之間還沒(méi)建立起依賴(lài)關(guān)系。如圖 6-15 所示的平面圖形，經(jīng)轉(zhuǎn)化后形成 GCG 。它清晰地表明了幾何約束系統(tǒng)內(nèi)部幾何元素及其相互約束關(guān)系。圖 6-15 平面圖形及其 GCGGCG 中的頂點(diǎn)：記錄了幾何元素的類(lèi)型、自由度 DOF 和其他相關(guān)參數(shù)信息；邊：記錄了幾何約束的類(lèi)型、約束度 DOC 和其他信息。邊的權(quán)值的定義取決于特定問(wèn)題解決的需要。例如幾何約束的約束度 DOC 、約束值和約束優(yōu)先權(quán)等都可以被認(rèn)為是 GCG 邊的權(quán)，因而 GCG 是一個(gè)幾何約束網(wǎng)絡(luò)。在圖 6-15中, GCG 含有 10頂點(diǎn)，即 10幾何元素；17 條邊，即 17 個(gè)約束，形成的約束集描述如下： ( ANG , L1 , L3 , d3 ) ( PER , L1 , L4 , +1/-1 )( ON_L , P1 , L1 , +1/-1 )( ON_L , P2 , L1 , +1/-1 )（PER , L1 , L2 , +1/-1 ）( ON_L , P1 , L4 , +1/-1 )（D_PP , Pl , P5 , d2 ） （D_PP , Pl , P2 , d1 ）( ON_L , P2 , L2 , +1/-1 )( ON_L , P3 , L2 , +1/-1 )( ON_C , P3 , C , +1/-1 )( TAN_LC , L2 , C , +1/-1 )( ON_C , P4 , C , +1/-1 )( TAN_LC , L3 , L1 , +1/-1 )( ON_L , P4 , L3 , +1/-1 )( ON_L , P5 , L3 , +1/-1 )( ON_L , P5 , L4 , +1/-1 ) GCG 作為一種圖，繼承了圖的一般概念和性質(zhì)。從直觀上看，一個(gè)被標(biāo)注尺寸的草圖，如果在非退化的情況下存在有限個(gè)的解，那么就認(rèn)為是約束完備的；如果存在無(wú)窮多個(gè)解，就是約束不足的；如果沒(méi)有一個(gè)解存在，那就是約束過(guò)載的。在這里，非退化的情況指：尺寸值是合理的，能夠在結(jié)構(gòu)上生成圖形。例如，標(biāo)注了三條邊長(zhǎng)的三角形，它的約束是合理的和完備的；如果某一邊的長(zhǎng)度大于其余兩邊之和，則該三角形無(wú)法正確生成。這就是出現(xiàn)了退化的情況。下面簡(jiǎn)要介紹幾何約束系統(tǒng)中的幾個(gè)常用概念及性質(zhì)。(l) 約束過(guò)載 (over-constrainted)： 一個(gè)幾何約束系統(tǒng)在結(jié)構(gòu)上是約束過(guò)載的，如果其 GCG 中存在的子圖含有 n 個(gè)頂點(diǎn)和多于 2n-3 條邊。約束過(guò)載的系統(tǒng)又稱(chēng)過(guò)約束系統(tǒng)。(2) 約束不足 (under-constrainted) : 一個(gè)幾何約束系統(tǒng)在結(jié)構(gòu)上是約束不足的，如果它在結(jié)構(gòu)上不是約束過(guò)載并且約束的數(shù)目嚴(yán)格小于 2n-3 。約束不足的系統(tǒng)又稱(chēng)欠約束系統(tǒng)。(3) 約束完備 (well-constrainted): 一個(gè)幾何約束系統(tǒng)在結(jié)構(gòu)上是約束完備的，如果它不是約束過(guò)載的并且其約束數(shù)目等于 2n-3 。約束完備的系統(tǒng)又稱(chēng)完備約束系統(tǒng)，對(duì)外表現(xiàn)為一個(gè)剛體。完備 GCG 一定是邊稀疏的、連通的。過(guò)約束圖形一般不能接受，但不排除工程圖中允許多余但不矛盾的尺寸標(biāo)注，以幫助閱讀者看懂圖形，理解設(shè)計(jì)者的意圖；欠約束系統(tǒng)是廣泛存在而且可以接受的，事實(shí)上在概念設(shè)計(jì)中，系統(tǒng)的初始狀態(tài)必須是欠約束的。在設(shè)計(jì)不斷深化和細(xì)化的過(guò)程中，可持續(xù)對(duì)欠約束系統(tǒng)施加約束，使之一步步走向完備的約束系統(tǒng)。一個(gè)支持概念設(shè)計(jì)的約束求解系統(tǒng)必須能夠處理欠約束的情形。2幾何約束系統(tǒng)的約束建模幾何約束圖 GCG 的建立可以通過(guò)三種方式實(shí)現(xiàn)：第一種：是在作圖過(guò)程中記錄下該操作對(duì)應(yīng)產(chǎn)生的約束。在制圖過(guò)程完成后，GCG 也就建立起來(lái)了。此種方法在制圖的過(guò)程中很自然地實(shí)現(xiàn)了 GCG 的建立，因此能準(zhǔn)確地記錄下圖形所蘊(yùn)含的約束，捕捉設(shè)計(jì)者的意圖；但該方法必須針對(duì)全新的設(shè)計(jì)對(duì)象，對(duì)于已有圖形則無(wú)能為力。第二種：是按己畫(huà)好的草圖手工指定約束。該方法能處理已有圖形，由用戶指定所需約束。但約束指定過(guò)程過(guò)于煩瑣，對(duì)于復(fù)雜的設(shè)計(jì)圖形顯然工作量太大。第三種：是自動(dòng)識(shí)別原有圖形隱含的約束。此方法能自動(dòng)地為已有圖形建立相應(yīng)的約束模型 GCG, 避免了前兩種辦法的不足，但實(shí)現(xiàn)的難度比較大，現(xiàn)有的算法還不夠成熟。因?yàn)榇罅繜o(wú)用和冗余的約束往往被系統(tǒng)識(shí)別出來(lái)，給后繼的推理、排序和求解算法帶來(lái)了很大負(fù)擔(dān)，而且很容易導(dǎo)致過(guò)約束或異常結(jié)果。因此，該方法多用于規(guī)模較小的圖，例如為平移、旋轉(zhuǎn)等三維造型操作提供二維截面圖形。在工程圖中，隱含約束是普遍存在的，例如水平、垂直、平行、相切等結(jié)構(gòu)約束并沒(méi)有在圖上標(biāo)志出來(lái)。隱含約束的確定有一定的規(guī)則，或者說(shuō)是工程常識(shí)，工程設(shè)計(jì)人員容易理解，我們利用計(jì)算機(jī)進(jìn)行識(shí)別也要遵循這些規(guī)則。以下是常見(jiàn)的幾種隱含約束識(shí)別規(guī)則，按識(shí)別的優(yōu)先級(jí)順序排列：(l) 近似水平的直線嚴(yán)格水平，近似鉛垂的直線嚴(yán)格鉛垂；(2) 近似相切的直線、圓和弧嚴(yán)格相切；(3) 近似同心的圓或弧嚴(yán)格同心；(4) 近似共線的兩直線嚴(yán)格共線；（5）近似平行的兩直線嚴(yán)格平行；(6) 近似垂直的兩直線嚴(yán)格垂直；(7) 近似的多個(gè)圓和弧半徑被認(rèn)為相等；(8) 圖形元素之間相互連接。這里有一個(gè)問(wèn)題，究竟近似到什么程度才能被認(rèn)為相等呢? 為此引人兩個(gè)閾值的概念：如圖 616 所示。距離閾值 d：如果兩個(gè)點(diǎn)的距離在距離閾值d 之內(nèi)，則認(rèn)為這兩個(gè)點(diǎn)是同一個(gè)點(diǎn)；同樣，如果點(diǎn)到直線的距離小于d, 那么就可以認(rèn)為點(diǎn)在直線上。角度閾值 ：規(guī)定了兩條直線夾角的限定值，是角度類(lèi)約束的識(shí)別依據(jù)。例如，如果兩條直線的夾角小于可以認(rèn)為兩條直線平行。兩種閾值的大小可以根據(jù)草圖的形狀和準(zhǔn)確程度由用戶設(shè)定。(a) 草圖 (b) 約束識(shí)別后規(guī)整的圖圖 616 距離閾值和角度閾值的概念約束。每當(dāng)一個(gè)幾何元素被系統(tǒng)作為一個(gè)頂點(diǎn)插入到 GCG 時(shí)，都要與 GCG 中已存在的幾何元素按照上述規(guī)則進(jìn)行比較，以生成相應(yīng)的邊。尺寸約束的識(shí)別可以根據(jù)尺寸標(biāo)注的控制點(diǎn)以及標(biāo)注方向，搜索相應(yīng)的控制圖素，建立尺寸標(biāo)注與對(duì)應(yīng)幾何元素的約束關(guān)系。在實(shí)際應(yīng)用中，隱含約束的識(shí)別并不是在約束求解之前就全部完成的，否則會(huì)產(chǎn)生大量不必要的約束，嚴(yán)重影響推理效率。因此，往往是在推理過(guò)程中，由于約束不足而使推理過(guò)程無(wú)法繼續(xù)進(jìn)行時(shí)，才啟動(dòng)隱含約束識(shí)別模塊，按約束優(yōu)先級(jí)有針對(duì)性地識(shí)別某些隱含約束。3幾何約束的推理算法在 GCG 中，每個(gè)約束對(duì)應(yīng)于圖的一條邊，每個(gè)幾何元素對(duì)應(yīng)于圖的一個(gè)頂點(diǎn)。從圖的某一頂點(diǎn)出發(fā)，把所有與它關(guān)聯(lián)的邊變?yōu)橐栽擁旤c(diǎn)為弧尾的出弧，從而增加了相應(yīng)鄰接頂點(diǎn)的入度(或減少其自由度)。如果某頂點(diǎn)的入度達(dá)到了其自由度數(shù)，則變?yōu)橐阎冶惠敵觥Ｆ浞腔〉倪叧蔀橐栽擁旤c(diǎn)為弧尾的出弧，用來(lái)減少與之鄰接的頂點(diǎn)的自由度。通過(guò)廣度優(yōu)先搜索，逐步遞歸地由已知元素推理出未知元素，直到圖中所有頂點(diǎn)的自由度約束均減為 0。這時(shí)無(wú)向圖變?yōu)橛邢驁D，頂點(diǎn)輸出的順序就是拓?fù)渑判虻慕Y(jié)果。（1） 推理步驟1) 預(yù)處理階段：將所有含自反邊的頂點(diǎn)的自由度 DOF(v) 減去自反邊的約束度 DOC（e），同時(shí)在圖中刪掉自反邊。自反邊代表了一類(lèi)一元約束，如半徑、水平、垂直等約束。2) 固定一點(diǎn)作為基點(diǎn)，其自由度 DOF(v)=0, 它成為已知元素，是推理搜索的起點(diǎn)。3) 從基點(diǎn)出發(fā)，遞歸調(diào)用 SEARCH 過(guò)程，直至所有頂點(diǎn)的自由度約束均減為 0。SEARCH 算法過(guò)程說(shuō)明如下：輸入： 已知元素的頂點(diǎn)v 。輸出： 表頭結(jié)點(diǎn)己排好序的有向圖。步驟l： 取已知元素 v 的表頭結(jié)點(diǎn)，從第一個(gè)表頭結(jié)點(diǎn)開(kāi)始，將其插入到已排好序的已知元素表頭結(jié)點(diǎn)的最后。步驟2： 遍歷與 U 關(guān)聯(lián)的所有邊；對(duì)于當(dāng)前邊 e, 取與邊 e 關(guān)聯(lián)的 v 的鄰接頂點(diǎn) v；如果 DOF(v)0, 則 v 為已知元素，繼續(xù)做步驟 2；否則 DOF(v)DOF(v)DOC(e)標(biāo)記邊成為從 v 指向 v的有向?。蝗绻?DOF(v)0, 將 v 壓入臨時(shí)堆找 s 。步驟3: 如果臨時(shí)堆棧 s 為空，返回。否則從臨時(shí)堆棧 s 中彈出頂點(diǎn)vv ，令 v = vv ，轉(zhuǎn)步驟 1 。 算法最終輸出己排好序的頂點(diǎn)序列。以上算法需進(jìn)一步細(xì)化，才能保證其實(shí)用性。（2）啟發(fā)式搜索策略由約束識(shí)別建立的 GCG 可能會(huì)包含大量冗余或矛盾的約束，并不是所有的約束都能用于推理，而且不同約束對(duì)推理過(guò)程所起的作用也不同。為此，通常遵照一般的工程常識(shí)為每個(gè)約束類(lèi)型規(guī)定相應(yīng)的優(yōu)先權(quán)值。例如尺寸約束的優(yōu)先權(quán)比結(jié)構(gòu)約束的優(yōu)先權(quán)要大，因?yàn)槌叽缂s束是顯式的，而結(jié)構(gòu)約束是隱式的。如果多個(gè)約束同時(shí)可用，則按照優(yōu)先順序觸發(fā)，亦即搜索時(shí)優(yōu)先搜索權(quán)值較大的邊，從而能較快地引導(dǎo)搜索向正確的方向進(jìn)行。（3）缺省推理 (default reasoning) 技術(shù)當(dāng)用優(yōu)先權(quán)較高的約束推理失敗 (仍有自由度不為 0 的頂點(diǎn)) 時(shí)，依次采用系統(tǒng)內(nèi)部 優(yōu)先權(quán)較低的待用約束，分步進(jìn)行推理。（4）冗余約束剔除幾何推理的過(guò)程并不是完全由自由度驅(qū)動(dòng)的，還要對(duì)矛盾的約束進(jìn)行判別，與已用約束 ( 已標(biāo)記為弧 ) 矛盾的約束不能用來(lái)減少頂點(diǎn)自由度，這樣才能建立正確的求解方式。例如，若有一個(gè)點(diǎn) P, 它在已知直線 L1 上，則該約束所代表的邊已被標(biāo)記為??；假設(shè)又存在已知直線 L2, 使得點(diǎn) P 在直線 L2 上，于是點(diǎn) P 可以通過(guò)兩直線求交進(jìn)行求解。但是如果 L1 平行于 L2( 意味著這兩條直線共線 ), 則點(diǎn) P 不能求解，因此點(diǎn) P 在直線 L2 上的約束不能使用。它是識(shí)別的冗余約束，雖未造成矛盾，但影響求解，也應(yīng)該剔除。（5）局部參數(shù)變動(dòng)處理對(duì)于已排好序的 GCG, 當(dāng)用戶只需要修改少數(shù)幾個(gè)參數(shù)值時(shí)，沒(méi)有必要從頭至尾生成整個(gè)圖形。為了提高效率，在某個(gè)局部參數(shù)變動(dòng)時(shí)，只需重新計(jì)算受到該參數(shù)直接或間接影響的元素，亦即僅受到該參數(shù)變動(dòng)影響的局部圖形元素。下面給出在某一約束值變化時(shí)，找到僅受其影響的一組元素集合的算法步驟：步驟 1：找到該約束代表的弧，取出弧頭元素階。步驟 2：對(duì)于所有vi的后繼元素vj，遞歸地向上回溯搜索其直接前驅(qū)元素。如果找到了vi，則標(biāo)記 vj 為受參數(shù)變動(dòng)影響的元素，送入待求元素隊(duì)列。步驟 3：待求元素依次出隊(duì)列，進(jìn)行求解。（6）約束一致性檢查1) 欠約束差別GCG 的拓?fù)渑判蚪Y(jié)束后，依次遍歷有向圖的逆鄰接表的表頭結(jié)點(diǎn)。如果還存在自由度大于 0 的頂點(diǎn)，則系統(tǒng)必為欠約束，表明圖中尺寸標(biāo)注不足。這些自由度大于 0 的頂點(diǎn)沒(méi)有受到尺寸的控制，系統(tǒng)會(huì)顯示出這些約束不足的頂點(diǎn)。2) 過(guò)約束差別即使圖中所有頂點(diǎn)的自由度均變?yōu)?0, 還有可能出現(xiàn)過(guò)約束，這就必須考察未用到的多余邊(冗余約束) 。如果該邊所代表的約束是由尺寸標(biāo)注引起的，那么它是多余的尺寸標(biāo)注，亦即產(chǎn)生了過(guò)約束。在上述排序算法中，每輸出一個(gè)已知元素之前，必須檢查它是否含有未用的邊，這些未用邊的約束很有可能是多余的。如果存在多余約束，系統(tǒng)會(huì)提示用戶刪除它。用戶也可以忽略該約束，算法會(huì)繼續(xù)執(zhí)行下去，多余約束將會(huì)被自動(dòng)忽略而不使其得到滿足。4幾何約束的求解計(jì)算推理結(jié)束后，幾何元素的求解順序就完全確定下來(lái)了。計(jì)算時(shí)只需依序遍歷有向圖的鄰接表的表頭結(jié)點(diǎn)，將入弧記錄的約束信息轉(zhuǎn)化為約束方程，從而計(jì)算出各頂點(diǎn)幾何元素的參數(shù)值。圖 617 顯示了排序后的依次求解過(guò)程，可見(jiàn)它等同于一種尺規(guī)作圖的方法,只需要進(jìn)行幾何解析交切運(yùn)算，因此該算法比較準(zhǔn)確高效。(a) 求解順序 1 5 (b) 求解順序 1 5 2（c）求解順序 1 5 2 8 (d) 求解順序 1 5 2 8 4 (e) 求解順序 1 5 2 8 4 3 （f） 求解順序 1 5 2 8 4 3 7 6圖 617 排序后的求解過(guò)程求解方法依據(jù)入弧的類(lèi)型和數(shù)目確定。由于約束類(lèi)型的多樣性和復(fù)雜性，求解時(shí)必須考慮到所有約束可能的排列組合，每一種求解方法對(duì)應(yīng)于一段計(jì)算程序。實(shí)際求解之前，系統(tǒng)已將其他約束類(lèi)型轉(zhuǎn)化成距離和角度類(lèi)約束，因此基于表 61 即可確定點(diǎn)和直線參數(shù)的約束組合。未注半徑的圓，其自由度是 3, 需要同時(shí)有 3 個(gè)約束才能確定，即對(duì)它的求解需要 3 個(gè)方程聯(lián)立求解。與未注半徑的困相關(guān)的約束實(shí)際上只有兩種：線圓相切約束和兩圓相切約束 (如果把點(diǎn)視為半徑為 0 的圓，那么可把點(diǎn)在圓上的約束轉(zhuǎn)化為兩圓相切約束), 因此未注半徑的圓的求解方法可有如表 62 所示的四種組合。對(duì)于一個(gè)完備約束系統(tǒng)。通?？梢源嬖谟邢迋€(gè)不同的解，但是用戶一般只能接受其中的一個(gè)。因此，多解的取舍問(wèn)題是 GCSP 中一個(gè)十分重要的問(wèn)題。事實(shí)上，對(duì)于一個(gè)完備的幾何約束系統(tǒng)來(lái)說(shuō)，解的數(shù)目一般會(huì)達(dá)到幾何元素?cái)?shù)目的指數(shù)級(jí)。表 61 點(diǎn)和直線的求解方法和對(duì)應(yīng)的約束組合幾何元素約束組合求解方法點(diǎn)D_PP + D_PP ( 點(diǎn)點(diǎn)距離 + 點(diǎn)點(diǎn)距離 )D_PP + D_PL ( 點(diǎn)點(diǎn)距離 + 點(diǎn)線距離 )求與兩已知點(diǎn)有一定距離的點(diǎn)求與一個(gè)已知點(diǎn)有一定距離且與一條已知直線有一定距離的點(diǎn)直線D_PL + D_PL ( 點(diǎn)線距離 + 點(diǎn)線距離 )D_PL + D_PL ( 點(diǎn)線距離 + 點(diǎn)線距離 )D_PL + ANG ( 點(diǎn)線距離 + 線線角度 )求與兩已知直線有一定距離的點(diǎn)求與兩巳知點(diǎn)有一定距離的直線求與一個(gè)已知點(diǎn)有一定距離且與一條己知直線有一定角度的直線表 62 未注半徑的圓的求解方法約束組合求解方法TAN_CC + TAN_CC + TAN_CCTAN_CC + TAN_CC + TAN_LCTAN_CC + TAN_LC + TAN_LCTAN_LC + TAN_LC + TAN_LC求與三個(gè)已知圓相切的圓求與兩個(gè)已知圓和一條已知直線相切的圓求與一個(gè)已知圓和兩條己知直線相切的圓與三條已知直線相切的圓首先看一個(gè)簡(jiǎn)單的例子，如圖 618 所示。圖 618(a) 的三角形是一個(gè)完備約束系統(tǒng)，圖 618的解是一致的，但顯然不是用戶所需要的。針對(duì)多解問(wèn)題，各種約束求解系統(tǒng)可能采取不同的方法。（1）數(shù)值迭代方法基于數(shù)值迭代的約束求解器的基本策略是收斂到與初始圖形最近的解，這種策略直觀且通過(guò)迭代方式很容易實(shí)現(xiàn)。然而由于解的數(shù)目呈指數(shù)式上升，約束方程組的數(shù)值迭代 t往往呈現(xiàn)出病態(tài)，因此常常會(huì)收斂到鞍點(diǎn)而非所期盼的最小點(diǎn)。用戶通常被迫將草圖畫(huà)得盡量準(zhǔn)確，以使幾何元素的數(shù)值接近所期望的解。同樣的道理，尺寸值的變化也要盡量的小。另外，由尺寸值帶來(lái)的變化并不一定是可逆的。例如把圖中某一尺寸值由 40 改為 30, 再由 30 改回 40, 得到的結(jié)果并不一定還是原來(lái)的圖，因此系統(tǒng)不得不小心地保留每一步 變化的設(shè)計(jì)歷史。 (a) 約束完備的三角形 (b) 一個(gè)一致的解圖 618 三角形的多解情況（2）通用規(guī)則判定方法這種思想的中心點(diǎn)在于根據(jù)某些特定的性質(zhì)確定多解的取舍。這通常要依賴(lài)于特定的應(yīng)用，例如可以選擇封閉的、凸的和非自交的圖形。該方法存在兩個(gè)主要問(wèn)題：(1) 通用規(guī)則的施加可能并不符合用戶的要求，特別是在用戶漸進(jìn)式地構(gòu)造草圖時(shí)。因此在構(gòu)造圖形的某些階段，不允許圖形是自交的。(2) 甚至在非常嚴(yán)格的情況下，這類(lèi)問(wèn)題的求解在計(jì)算上也是很困難的。例如，考察一個(gè)多邊形截面的頂點(diǎn)構(gòu)成的點(diǎn)集。對(duì)于某些特定應(yīng)用可能會(huì)要求草圖的結(jié)果應(yīng)該是一個(gè)簡(jiǎn)單多邊形，即非自交的多邊形。另外，也可以指定一個(gè)點(diǎn)集連接的環(huán)路方向構(gòu)造這個(gè)多邊形。這個(gè)附加要求使該問(wèn)題成為一個(gè) NP 完全問(wèn)題。（3）通過(guò)過(guò)約束方法指定正確解這是一種很自然的方法，工程師在圖中經(jīng)常使用。圖 619 給出了一個(gè)運(yùn)用這種方法得到唯一解的典型實(shí)例。假設(shè)圖中的三條平行線沒(méi)有方向，如果我們僅僅指定了兩個(gè)距離約束 dl 和 d2，則會(huì)得到兩個(gè)不同的解。由于直線不含方向，因此除了第一個(gè)距離約束外，對(duì)于其他每個(gè)距離約束都有兩個(gè)不同解的選擇。一般地，對(duì)于 n 條平行直線和 n-1 個(gè) 距離約束的完備系統(tǒng)存在 2n-2 個(gè)解。如果在本例中加入第三個(gè)距離 d3，就能得到唯一解。雖然這種方法看起來(lái)很有效，但是即使把問(wèn)題限制在一個(gè)很簡(jiǎn)單的條件下，也無(wú)法找到一個(gè)有效算法得到的問(wèn)題的解。將上述例子一般化，得到問(wèn)題的描述：給定 n 條平行線和它們之間的 n 個(gè)平行距離，是否存在滿足要求的解？可以證明這個(gè)問(wèn)題是一個(gè) NP 完全問(wèn)題，因?yàn)樗梢赞D(zhuǎn)化成一個(gè)整數(shù)劃分問(wèn)題：給定一個(gè) n 個(gè)正整數(shù)的集合 A, 是否存在 A 的一個(gè)劃分，把這 n 個(gè)整數(shù)分成兩個(gè)不相交的集 Al 和 A2, 使得 A1 中整數(shù)的和等于 A2 中整數(shù)的和? (a) 兩個(gè)距離約束得到兩個(gè)可能解 (b) 三個(gè)距離約束得到唯一解圖 619 用距離約束三條平行線三、 參數(shù)化 CAD 系統(tǒng)基于上述的算法，在傳統(tǒng) CAD 系統(tǒng)的基礎(chǔ)上，構(gòu)造一個(gè)參數(shù)化 CAD 系統(tǒng) (PCAD)對(duì)實(shí)際應(yīng)用是十分重要的。由清華大學(xué) CAD 中心開(kāi)發(fā)的 PCAD 系統(tǒng)的基本流程是：對(duì)于用戶輸入的原始草圖,通過(guò)草圖識(shí)別方法建立起圖形的 GCG 表達(dá)，這是一個(gè)無(wú)向圖的鄰接表結(jié)構(gòu)。根據(jù)幾何推理算法對(duì)原始 GCG 進(jìn)行有向化處理，拓?fù)渑判蚝笊身旤c(diǎn)輸出序列，亦即幾何元素的求解順序，它存儲(chǔ)在有向圖的逆鄰接表的表頭結(jié)點(diǎn)鏈中。順序遍歷該鏈，通過(guò)幾何解析交切求解計(jì)算和多解判定，確定出每個(gè)結(jié)點(diǎn)所包含的幾何元素的參數(shù)值，最終得到符合幾何約束的精確圖形。此流程圖如圖 620 所示。1參數(shù)化 CAD 系統(tǒng)的流程和基本功能（1） PCAD 系統(tǒng)的主要功能圖 620 系統(tǒng)的流程框圈1) 草圖設(shè)計(jì)在初始設(shè)計(jì)階段，工程師可以將注意力集中在設(shè)計(jì)上，利用鼠標(biāo)在屏幕上以草圖的形式隨手勾畫(huà)出設(shè)計(jì)圖形，表達(dá)設(shè)計(jì)思想。在給出必要的尺寸標(biāo)注之后 ,PCAD 將根據(jù)草圖形狀和尺寸大小把規(guī)整的圖形繪制出來(lái)。2) 修改設(shè)計(jì)在修改設(shè)計(jì)時(shí)只需將原有圖形調(diào)出，修改某些尺寸標(biāo)注的值，運(yùn)行 PCAD 后就可以迅速得到新的設(shè)計(jì)圖。在 PCAD 的支持下，設(shè)計(jì)師可以通過(guò)不斷調(diào)整尺寸參數(shù)值產(chǎn)生不同的設(shè)計(jì)方案。3) 支持工程設(shè)計(jì)約束PCAD 允許定義一組設(shè)計(jì)變量，通過(guò)表達(dá)式為尺寸標(biāo)注賦值，這樣根據(jù)幾個(gè)關(guān)鍵參數(shù)就可以定義一個(gè)很復(fù)雜的圖形。4）相似零件圖的生成只需要定義一張?jiān)蛨D并提供圖中設(shè)計(jì)變量的數(shù)據(jù) ,PCAD 系統(tǒng)就能自動(dòng)生成一系列結(jié)構(gòu)相同而尺寸不同的相似零件族，這使創(chuàng)建標(biāo)準(zhǔn)件和常用件庫(kù)的工作變得十分容易。 事實(shí)上，我們已利用該系統(tǒng)創(chuàng)建了全套國(guó)家標(biāo)準(zhǔn)零件庫(kù)。針對(duì)工程實(shí)際需要 ,PCAD 系統(tǒng)還增加了中心線處理、陣列處理、剖面線處理和三視圖處理等實(shí)用功能。對(duì)于中等復(fù)雜的零件圖，其處理速度和準(zhǔn)確性均能滿足工程設(shè)計(jì)的實(shí)際要求。（2）PCAD 系統(tǒng)的功能命令1) PPCREATE 命令自動(dòng)識(shí)別草圖約束，建立參數(shù)化模型，并按照識(shí)別的約束規(guī)整圖形。2）PPUPDATE 命令根據(jù)圖中的所有結(jié)構(gòu)約束和尺寸標(biāo)注值，更新全圖。3）PPDIM 命令是尺寸標(biāo)注命令，能夠進(jìn)行點(diǎn)到點(diǎn)的距離、點(diǎn)到線的距離、線到線的距離、角度、直徑和半徑的標(biāo)注。4）PPCHGDIM 命令修改尺寸標(biāo)注值，并按照新的尺寸值更新圖形。5) PPDELDIM 命令刪除尺寸標(biāo)注，并報(bào)告當(dāng)前所需的尺寸和約束數(shù)目。6）PPDSPDIM 命令顯示尺寸標(biāo)注狀態(tài)，可以是數(shù)值、變量或方程的形式。7）PPADDCON 命令對(duì)圖形施加指定約束，約束類(lèi)型包括水平、鉛垂、平行、垂直、相切、投影、共線、共點(diǎn)和固定點(diǎn)等。8) PPSHOWC