石志良，陳誼，張忠全

武漢理工大學(xué)機(jī)電工程學(xué)院，武漢 430070

通用幾何約束系統(tǒng)統(tǒng)一建模研究

石志良，陳誼，張忠全

武漢理工大學(xué)機(jī)電工程學(xué)院，武漢 430070

在幾何約束和幾何實(shí)體的基本約束和歐拉參數(shù)表達(dá)的基礎(chǔ)上，研究了通用幾何約束系統(tǒng)的統(tǒng)一建模問(wèn)題。通過(guò)對(duì)三維幾何實(shí)體姿態(tài)約束和位置約束解耦性的分析，抽象出球?qū)嶓w、盒體和球盒體三種基本幾何實(shí)體表達(dá)空間幾何實(shí)體，并以基本約束的組合表達(dá)幾何約束，形成幾何約束模型特有的層次結(jié)構(gòu)；并以有向圖管理幾何約束系統(tǒng)，可以清晰地反映姿態(tài)約束和位置約束的解耦性，實(shí)現(xiàn)約束系統(tǒng)的細(xì)粒度分解，得到規(guī)模更小的求解序列，實(shí)現(xiàn)高效求解。方法實(shí)現(xiàn)于原型系統(tǒng)WhutVAS中。

幾何約束；幾何約束求解；約束處理；圖分解；歐拉參數(shù)

1 引言

在幾何約束系統(tǒng)中，幾何實(shí)體之間的約束關(guān)系是非常復(fù)雜的，如何建立有效的幾何約束系統(tǒng)模型，是幾何約束系統(tǒng)研究的基礎(chǔ)。理想的幾何約束系統(tǒng)應(yīng)該做到表達(dá)、維護(hù)和求解的一致性，幾何空間的可拓展性及幾何上的可解釋性。在幾何約束系統(tǒng)的研究中，基于變量幾何[1-3]的幾何約束系統(tǒng)建模方法，以幾何實(shí)體特征點(diǎn)的參數(shù)變量來(lái)表達(dá)幾何實(shí)體，以參數(shù)變量之間的約束方程來(lái)表達(dá)幾何約束，其局限性是顯而易見(jiàn)的。這種采用整體笛卡爾坐標(biāo)建立系統(tǒng)約束和約束方程的方法雖然從理論上來(lái)說(shuō)可以進(jìn)行任何類型的約束求解，但它需要建立一個(gè)較大的方程組，對(duì)于幾何約束的表達(dá)和求解都很不方便?；趲缀螌?shí)體和圖論[4-9]對(duì)幾何約束系統(tǒng)進(jìn)行建模，可以直接管理二、三維空間中的幾何實(shí)體及其關(guān)聯(lián)的幾何約束，具備較好的幾何空間可拓展性及幾何上的可解釋性，但是，由于幾何約束的多樣性，導(dǎo)致幾何約束的表達(dá)復(fù)雜，簡(jiǎn)潔性不夠，而且裝配約束的約束度通常大于1，不利于冗余約束的判定。為了解決這些問(wèn)題，需要研究基礎(chǔ)共性的表達(dá)問(wèn)題，彭小波[10]以運(yùn)動(dòng)學(xué)和動(dòng)力學(xué)的研究為基礎(chǔ)，提出采用歐拉參數(shù)和基本約束[11]表達(dá)幾何實(shí)體和幾何約束，結(jié)合有向圖，在幾何建模的層次上將二、三維幾何約束問(wèn)題以及多剛體系統(tǒng)動(dòng)力學(xué)問(wèn)題統(tǒng)一起來(lái)，并擴(kuò)展到多剛體系統(tǒng)的分析計(jì)算領(lǐng)域，該方法以少量的基本幾何約束表達(dá)所有的幾何約束，模型的抽象和簡(jiǎn)潔性好，然而，卻忽視了歐拉參數(shù)表達(dá)的幾何實(shí)體參數(shù)結(jié)構(gòu)上具有一定的可解耦性，對(duì)幾何實(shí)體的統(tǒng)一表達(dá)沒(méi)有作進(jìn)一步的研究和抽象，有向圖頂點(diǎn)仍然是通常的幾何實(shí)體，從而導(dǎo)致求解的規(guī)模較大。文獻(xiàn)[12]研究了三維實(shí)體之間的重合、角度和距離約束的統(tǒng)一幾何表達(dá)。本文以歐拉參數(shù)表達(dá)的幾何實(shí)體的姿態(tài)和位置約束的解耦性研究為基礎(chǔ)，抽象出球?qū)嶓w、盒體和球盒體三種基本幾何實(shí)體表達(dá)空間幾何實(shí)體，并采用基本約束的組合表達(dá)幾何約束，在有向圖上清晰地表達(dá)幾何約束系統(tǒng)的本質(zhì)特征，基于有向圖的幾何約束優(yōu)化匹配算法[13]，為二、三維幾何約束求解提供了內(nèi)在的統(tǒng)一機(jī)理，具有很強(qiáng)的理論意義。

2 基于歐拉參數(shù)的幾何實(shí)體和幾何約束的表達(dá)

幾何實(shí)體的方位由姿態(tài)和位置確定，姿態(tài)表示幾何實(shí)體在空間中的方向，如平面的法向量，直線的方向，剛性體的方向余弦矩陣，可以由附著在幾何實(shí)體上的局部坐標(biāo)系的姿態(tài)表達(dá)；位置由附著在幾何實(shí)體上的局部坐標(biāo)系的位置表達(dá)，Haug[11]采用歐拉參數(shù)表達(dá)幾何實(shí)體的方位，以基本約束dot1、dot2、等X、等Y、等Z和距離條件[10]表達(dá)裝配約束。由于三維空間復(fù)雜于二維空間，二維空間的歐拉參數(shù)表達(dá)可以看作是三維空間的特例，因而，本文僅給出三維常見(jiàn)裝配約束的基本約束表達(dá)，如表1所示。

表1 常用裝配約束及其位置基本約束表達(dá)1）

以共軸約束為例，共軸約束限制4個(gè)自由度，如圖1 （a）所示，假定P1和P2分別是軸線L1和L2的基點(diǎn)，h1，h2分別是軸線L1，L2的方向矢量，矢量f1，g1，h1正交，假定軸線L1固定，要使L1和L2共軸，需要滿足f1⊥h2，g1⊥h2，f1⊥d12和g1⊥d12，f1⊥h2和g1⊥h2決定圓柱體2的姿態(tài)，f1⊥d12和g1⊥d12決定圓柱體2的位置，對(duì)應(yīng)的約束方程如圖1（b）。

圖1 圓柱體共軸約束實(shí)例圖

3 幾何實(shí)體姿態(tài)和位置的解耦性質(zhì)

幾何實(shí)體的姿態(tài)和位置具有一定的可解耦性質(zhì)，有利于求解。因?yàn)閺膸缀紊蟻?lái)說(shuō)，存在這樣一個(gè)事實(shí)：移動(dòng)幾何實(shí)體不破壞幾何實(shí)體的姿態(tài)，而轉(zhuǎn)動(dòng)幾何實(shí)體時(shí)卻可以破壞幾何實(shí)體的位置例如，共軸約束含有4個(gè)約束分量，約束度是4，在可解耦的情況下，共軸約束的4個(gè)約束分量可以分為軸平行的2個(gè)姿態(tài)約束和點(diǎn)在軸線上的2個(gè)位置約束，求解時(shí)可以先根據(jù)姿態(tài)約束確定姿態(tài)，然后在確定的姿態(tài)下，求解位置約束，反之則不能夠求解。當(dāng)然，也可以采用整體數(shù)值求解，需要聯(lián)立4個(gè)方程，效率顯然較低。假設(shè)以代表基本約束dot1，代表基本約束dot2是指其他的距離約束關(guān)系，存在如下性質(zhì)：

性質(zhì)1假設(shè)剛性體RB參數(shù)匹配的約束滿足條件

姿態(tài)約束和位置約束是可以解耦求解的。剛性體存在三個(gè)約束，表明姿態(tài)是完整約束的，則不論剛性體是完整約束還是欠約束，一定是可解耦求解的，如3A 3D、3A 2D和3A 1D構(gòu)型[13]。

性質(zhì)2如果與剛性體RB參數(shù)匹配的和約束滿足條件

則姿態(tài)約束和位置約束一定不可解耦求解。

由于剛性體存在三個(gè)移動(dòng)自由度，如果匹配的和約束數(shù)大于3，那么需要通過(guò)轉(zhuǎn)動(dòng)來(lái)滿足約束，使得姿態(tài)和位置約束求解不可解耦。如2A 4D、1A 5D和6D完整約束構(gòu)型[14]。

如果在可裝配的條件下，排除性質(zhì)1和性質(zhì)2的情況，處于欠約束情況下的姿態(tài)和位置的解耦求解不存在定性，常見(jiàn)的裝配約束都是可以解耦的，例如兩個(gè)剛性體上兩個(gè)軸線的共軸約束、平行軸相距約束、兩個(gè)平面的共面約束、面面相距約束等，姿態(tài)和位置是可以解耦求解。但是，如果兩個(gè)剛性體受到一個(gè)平行約束和兩個(gè)距離約束，剛性體初始方位的不同，可能會(huì)導(dǎo)致不可解耦求解，需要同時(shí)變換剛性體的姿態(tài)和位置來(lái)滿足距離約束。雖然欠約束情況下的姿態(tài)和位置的解耦求解不存在定性，但是能夠分離出的可解耦情況對(duì)幾何約束求解是很有意義的。對(duì)于欠約束情況下的姿態(tài)和位置非定性解耦求解，通常是先求解姿態(tài)約束，然后依據(jù)位置約束和確定的姿態(tài)，判定是否存在解，如果存在，則可解耦，否則不可解耦，采用整體數(shù)值求解。

4 幾何實(shí)體的統(tǒng)一表達(dá)

4.1 基本幾何實(shí)體認(rèn)定

由幾何實(shí)體的姿態(tài)和位置的解耦性分析，以及姿態(tài)約束和位置約束的性質(zhì)可知，僅匹配幾何實(shí)體的姿態(tài)，和約束可匹配幾何實(shí)體的姿態(tài)和位置，由此可以產(chǎn)生一個(gè)很樸素的思想：

幾何實(shí)體所受的幾何約束中，讓決定幾何實(shí)體姿態(tài)的基本約束單獨(dú)求解幾何實(shí)體的姿態(tài)，而決定幾何實(shí)體位置的基本約束單獨(dú)求解幾何實(shí)體的位置，從而將幾何實(shí)體方位的統(tǒng)一求解分為姿態(tài)和位置的獨(dú)立求解，降低求解的規(guī)模。

為了在幾何約束圖上表達(dá)這種關(guān)系，需要對(duì)幾何實(shí)體的表達(dá)作進(jìn)一步的研究和抽象，為此，引入球?qū)嶓w、盒體和球盒體三種基本幾何實(shí)體。球?qū)嶓w是一個(gè)只與空間方向相關(guān)的抽象實(shí)體，由歐拉參數(shù)組p=[e0，e1，e2，e3]表達(dá)，球?qū)嶓w僅與幾何實(shí)體的姿態(tài)相關(guān)，自由度是3；盒體是一個(gè)只與空間位置相關(guān)的抽象實(shí)體，由參數(shù)組r=[x，y，z]表達(dá)，盒體僅與幾何實(shí)體的位置相關(guān)，自由度是3；球?qū)嶓w和盒體可以表示幾何實(shí)體的方位，但是，三維空間的球面和圓柱面都存在一個(gè)形狀自由度，為清晰地表達(dá)球面和圓柱面，引入球盒體的概念，球盒體是一個(gè)與幾何實(shí)體的位置和形狀參數(shù)相關(guān)的抽象實(shí)體，由參數(shù)組r=[x，y，z]和形狀參數(shù)表達(dá)，自由度是4，表2是三種基本幾何實(shí)體的描述。

表2 三種基本幾何實(shí)體的描述

4.2 基于基本幾何實(shí)體的三維幾何實(shí)體表達(dá)

基于基本幾何實(shí)體，考察三維空間中的點(diǎn)、直線、平面、球面、圓柱面和剛性體，存在如下的表達(dá)方式：

（1）點(diǎn)

空間點(diǎn)的邊界表示為p(x，y，z)，歐拉參數(shù)表示為rp=r+Aps′p，自由度是3，因而以盒體表達(dá)。

（2）直線

在三維空間中，設(shè)固結(jié)在直線上的局部坐標(biāo)系為o′x′y′z′，直線的位置由局部坐標(biāo)系原點(diǎn)o′確定，歐拉參數(shù)表示為ro=r′+Aos′o；直線的空間姿態(tài)由x′y′z′的姿態(tài)確定，直線的方向由向量v′表示，歐拉參數(shù)表示為v=Avv′，與方向向量正交的向量為h和g，v′、h和g表示局部坐標(biāo)系o′x′y′z′的姿態(tài)，由此可知，直線的姿態(tài)可以表示為球?qū)嶓w，直線的位置可以表示為盒體。在三維空間中，直線的自由度是4，球?qū)嶓w和盒體的自由度之和是6，則需要在球?qū)嶓w和盒體之間添加內(nèi)部約束，以保證直線表達(dá)的正確性。取直線上的任意一點(diǎn)rp（不同于原點(diǎn)o′，該點(diǎn)相當(dāng)于待確定直線上的點(diǎn)），則有rp和o′連線的方向與v′一致的條件成立，由基本約束可知，需添加2個(gè)dot2約束

其中dij=rp-ro約束度是2，與三維空間直線的幾何意義吻合。

（3）平面

在三維空間中，設(shè)固結(jié)在平面上的局部坐標(biāo)系為o′x′y′z′，平面的位置由局部坐標(biāo)系原點(diǎn)o′確定，歐拉參數(shù)表示為ro=r′+Aos′o；平面的空間姿態(tài)由x′y′z′的姿態(tài)確定，平面的法向由向量v′表示，歐拉參數(shù)表示為v=Avv′，與法向量正交的向量為h和g，v′、h和g表示局部坐標(biāo)系o′x′y′z′的姿態(tài)，由此可知，平面的姿態(tài)可以表示為球?qū)嶓w，平面的位置可以表示為盒體。在三維空間中，平面的自由度是3，球?qū)嶓w和盒體的自由度之和是6，則需要在球?qū)嶓w和盒體之間添加三個(gè)內(nèi)部約束，以保證平面表達(dá)的正確性。取全局坐標(biāo)原點(diǎn)到平面上的垂足為R，則有R和o′連線的矢量與v′滿足垂直約束，由基本約束可知，需添加1個(gè)dot2和2個(gè)dot1約束：

其中dij=R-ro。

（4）球面

在三維空間中，球面的位置由球心的坐標(biāo)p(x，y，z)確定，由于球面具有空間對(duì)稱的性質(zhì)，不具備方向，球面的半徑是形狀自由度，具有4個(gè)自由度，這些性質(zhì)決定球面可以采用球盒體表達(dá)，球面的位置由歐拉參數(shù)表示為rp=r+Apsp。

（5）圓柱面

在三維空間中，圓柱面具有4個(gè)方位自由度和1個(gè)形狀自由度，方位自由度由圓柱面的軸線決定，形狀自由度表示圓柱面的半徑，根據(jù)直線的表達(dá)可知，圓柱面可以采用球?qū)嶓w和球盒體表達(dá)，同樣需要對(duì)球?qū)嶓w和球盒體添加兩個(gè)內(nèi)部dot2約束，約束度為2。

（6）剛性體

三維空間剛性體的自由度是6，3個(gè)轉(zhuǎn)動(dòng)自由度和3個(gè)移動(dòng)自由度，由歐拉參數(shù)表達(dá)的3個(gè)轉(zhuǎn)動(dòng)自由度由球?qū)嶓w表達(dá)，3個(gè)移動(dòng)自由度由球盒體表達(dá)，球?qū)嶓w和球盒體之間不存在內(nèi)部的約束關(guān)系。

通過(guò)對(duì)基本幾何約束和基本幾何實(shí)體的研究可知，裝配約束可以由基本約束的組合來(lái)表達(dá)，幾何實(shí)體可以由基本幾何實(shí)體和基本幾何約束的組合表達(dá)，這使得幾何約束模型的表達(dá)呈現(xiàn)出其特有的層次結(jié)構(gòu)，如圖2所示。

圖2 幾何約束模型層次結(jié)構(gòu)圖

5 幾何約束系統(tǒng)建模

基于幾何約束模型層次結(jié)構(gòu)，采用有向圖G=(V，A)描述幾何約束系統(tǒng)，其中V是表達(dá)幾何約束系統(tǒng)中所有幾何實(shí)體的頂點(diǎn)集合，以基本幾何實(shí)體表達(dá)幾何實(shí)體，則V僅由球?qū)嶓w、盒體和球盒體組成的集合。有向弧集合A={a}，一條有向弧表示一個(gè)基本約束，具有1個(gè)約束度，如果以有向弧直接表示裝配約束，而裝配約束的約束度通常大于1，則有向弧的權(quán)值大于1，導(dǎo)致在有向圖上無(wú)法清晰地表示冗余約束。

如果與頂點(diǎn)v匹配的約束數(shù)m小于其自由度DOF(v)，則稱頂點(diǎn)v是自由頂點(diǎn)；如果m等于DOF(v)，則稱v是固定頂點(diǎn)。在有向圖中，如果頂點(diǎn)v1到v2存在一條路徑P，且v1是自由頂點(diǎn)，則稱P是從v2到v1的逆向可逆路徑，簡(jiǎn)稱可逆路徑。路徑P所包含的有向弧的條數(shù)稱為P的長(zhǎng)度。如果G為有向無(wú)環(huán)圖，則從頂點(diǎn)v∈V出發(fā)的所有路徑上的頂點(diǎn)集稱為v的傳播域，從v出發(fā)所有逆向路徑上的頂點(diǎn)集稱為v的先決域。

構(gòu)造幾何約束有向圖G的算法關(guān)鍵在于：在有向圖上為新增約束c尋找匹配頂點(diǎn)v，其實(shí)質(zhì)是有向圖上的＜c，v＞二部圖匹配。簡(jiǎn)單地說(shuō)，構(gòu)造幾何約束有向圖的過(guò)程實(shí)際上就是為每條有向弧確定匹配頂點(diǎn)的過(guò)程。

構(gòu)造規(guī)則1如果兩個(gè)相關(guān)頂點(diǎn)中有一個(gè)頂點(diǎn)為固定頂點(diǎn)，另外一個(gè)為自由頂點(diǎn)，則約束與自由頂點(diǎn)匹配。

構(gòu)造規(guī)則2如果不屬于同一個(gè)強(qiáng)連通分量的兩個(gè)相關(guān)頂點(diǎn)的均為自由頂點(diǎn)，則約束匹配于傳播域體積較小的頂點(diǎn)。

構(gòu)造規(guī)則3如果兩個(gè)相關(guān)頂點(diǎn)的剩余自由度都為0，則從兩個(gè)相關(guān)頂點(diǎn)開始，找出一條最短的可逆路徑，將這條路徑反向，相應(yīng)頂點(diǎn)的剩余自由度增加，新增約束與之匹配。

以上的三個(gè)構(gòu)造規(guī)則是幾何約束與頂點(diǎn)匹配的通用規(guī)則，在以基本幾何實(shí)體表達(dá)的有向圖中，頂點(diǎn)僅由三種基本幾何實(shí)體組成，添加的裝配約束由dot1、dot2和距離等基本幾何約束組成，由于基本幾何約束的特定的性質(zhì)，與基本幾何實(shí)體的匹配具有特殊的特性。

性質(zhì)3dot1基本幾何約束只能夠在球?qū)嶓w之間依據(jù)構(gòu)造規(guī)則匹配，如果不滿足匹配的條件，則該約束冗余。

性質(zhì)4dot2基本幾何約束可以在球?qū)嶓w、盒體和球盒體之間依據(jù)構(gòu)造規(guī)則進(jìn)行匹配；如果待匹配的盒體或球盒體的剩余自由度為0，而該盒體或球盒體對(duì)應(yīng)的球?qū)嶓w是自由頂點(diǎn)，dot2可與球?qū)嶓w匹配，否則，依據(jù)構(gòu)造規(guī)則進(jìn)行匹配。

性質(zhì)5距離約束在盒體或球盒體之間依據(jù)構(gòu)造規(guī)則進(jìn)行匹配，如果待匹配的盒體或球盒體的剩余自由度為0，而該盒體或球盒體對(duì)應(yīng)的球?qū)嶓w是自由頂點(diǎn)，距離可與球?qū)嶓w匹配，否則，依據(jù)構(gòu)造規(guī)則進(jìn)行匹配。

欠約束情形下的匹配多樣性會(huì)產(chǎn)生不良的強(qiáng)連通分量，增加求解時(shí)間花費(fèi)。為此采用優(yōu)化處理方法，文獻(xiàn)[13]對(duì)此作了詳細(xì)的闡述，最終得到一個(gè)強(qiáng)連通分量體積較優(yōu)的求解序列。在求解序列中，對(duì)于每個(gè)幾何實(shí)體對(duì)應(yīng)的基本幾何實(shí)體，如果是可解藕的，則先求解姿態(tài)和位置約束，然后求解內(nèi)部約束。

6 實(shí)例分析

為驗(yàn)證本文方法的正確性，采用一個(gè)回轉(zhuǎn)窯托輪軸裝配的實(shí)例進(jìn)行驗(yàn)證。圖3（a）為托輪軸裝配模型，其中裝配部件有中心軸1、托輪2、內(nèi)擋圈3、軸承4、套筒5、軸承6和外擋圈7，爆炸圖如圖3（b）所示；裝配約束有共軸約束CoLL(1，2)、CoLL(1，3)、CoLL(1，4)、CoLL(1，5)、CoLL(5，6) 和CoLL(6，7)，共面約束有CoFF(1，2)、CoFF(1，3)，CoFF(3，4)、CoFF(4，5)、CoFF(5，6)和CoFF(6，7)。由于裝配部件為空間剛體，采用球體Si和盒體Bi分別表示部件i的姿態(tài)參數(shù)和位置參數(shù)，以分別表示部件i的轉(zhuǎn)動(dòng)和移動(dòng)，球體Si和盒體Bi分別具有3個(gè)轉(zhuǎn)動(dòng)自由度和3個(gè)移動(dòng)自由度。假設(shè)中心軸1的位姿固定，采用基本約束分量表達(dá)裝配約束，在剔除冗余約束分量后，可得到如圖3（c）所示的約束有向圖。該約束有向圖可采用并行求解，其求解序列如圖3（d）所示為{Sq0，Sq1，Sq2，Sq3，Sq4，Sq5，Sq6，Sq7，Sq8，Sq9}，其中Sq1和Sq5內(nèi)的頂點(diǎn)可并行求解。

圖3 托輪軸裝配模型及其約束圖

7 結(jié)論

本文借鑒多體系統(tǒng)分析中的歐拉參數(shù)方法，以幾何實(shí)體和幾何約束的歐拉參數(shù)表達(dá)為基礎(chǔ)，通過(guò)對(duì)歐拉參數(shù)表達(dá)姿態(tài)約束和位置約束的解耦性分析，抽象出球?qū)嶓w、盒體和球盒體三種三維空間的基本幾何實(shí)體，并以球?qū)嶓w、盒體和球盒體對(duì)三維空間中的點(diǎn)、直線、平面、球面、圓柱面和剛性體進(jìn)行統(tǒng)一表達(dá)，以簡(jiǎn)潔的基本幾何實(shí)體和基本幾何約束，結(jié)合有向圖對(duì)幾何約束系統(tǒng)進(jìn)行建模，描述了幾何約束求解的本質(zhì)特征，可以清晰地表達(dá)姿態(tài)約束和位置約束的解耦性；本文的方法解決了二維與三維的幾何實(shí)體和幾何約束統(tǒng)一模型問(wèn)題，為二、三維幾何約束求解提供了內(nèi)在的統(tǒng)一機(jī)理，具有很強(qiáng)的理論意義，同時(shí)，為后續(xù)對(duì)姿態(tài)約束和位置約束分別采用解析求解，進(jìn)一步提高求解效率奠定了基礎(chǔ)。但本文的表達(dá)模型適用于三維空間中的點(diǎn)、直線、平面、球面、圓柱面和剛性體之間的裝配關(guān)系，是否適用于除圓柱和球以外的二次曲面的表達(dá)需要做進(jìn)一步的研究和完善。

[1]Lin V C，Gossard D C，Light R A.Variational geometry in computer-aided design[J].Compute Graphics，1981，15（3）：171-177.

[2]Serrano D，Gossard D.Constraint management in conceptual design[J].A rtificial Intelligence in Engineering Design，Computational Mechanics Publications，1988.

[3]A it-Aoudia S，Jegou R，Michelucci D.Reduction of constraint systems[C]//Combined Proceedings of EDUGRAPHICS’93 and COMPUGRAPHICS’93，1993：31-40.

[4]Owen J C.Algebraic solution for geometry from dimensional constraints[C]//Proceedings of ACM Symposium on Solid Modeling Foundation，Austin，TX，1991：397-407.

[5]K ramer G.Solving geometric constraints systems：a case study in kinematics[M].Cambridge，MA：M IT Press，1992.

[6]Hoffmann C M，Lomonosov A，Sitharam M.Decomposition plans for geometric constraint systems II new algorithms[J]. Journal of Symbolic Computation，2001，31（4）：408-428.

[7]Gao X S，Lin Q，Zhang G.A C-tree decomposition algorithm for 2D and 3D geometric constraint solving[J].Computer-Aided Design，2006，38（1）：1-13.

[8]董金祥，葛建新，高屹，等.變參繪圖系統(tǒng)中約束求解的新思路[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，1997，9（6）：513-519.

[9]李彥濤，胡事民，孫家廣.一個(gè)幾何約束系統(tǒng)分解的新算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2000，12（12）：926-930.

[10]彭小波.二、三維幾何約束統(tǒng)一求解器原理與方法研究[D].武漢：華中科技大學(xué)，2002.

[11]Haug E J.機(jī)械系統(tǒng)的計(jì)算機(jī)輔助運(yùn)動(dòng)學(xué)和動(dòng)力學(xué)[M].劉興祥，譯.北京：高等教育出版社，1996.

[12]Haller K，John A L，Sitharam M，et al.Body-and-cad geometric constraint system s[J].Computational Geometry：Theory and Applications，2012，45（8）：385-405.

[14]Gao X S，Lei D L，Liao Q Z，et al.Generalized Stewart-Gough platforms and their direct kinematics[J].IEEE Trans on Robotics，2005，21（2）：141-151.

[13]陳立平，王波興，彭小波.一種面向欠約束幾何系統(tǒng)求解的二部圖匹配優(yōu)化處理方法[J].計(jì)算機(jī)學(xué)報(bào)，2000，23（5）：523-530.

SHI Zhiliang,CHEN Yi,ZHANG Zhongquan

School of M echanical and Electronic Engineering,Wuhan University of Technology,Wuhan 430070,China

A united modeling method of generalized geometric constraint system is investigated on the basis of expressing geometric constraints and geometric elements by basic geometric constraints and Euler parameter,respectively.After analyzing the decoupled property of orientation and position constraints related with spatial geometric elements,the basic bodies are summarized into ball,box and ball-box body to express spatial geometric elements,together with assembly constraints expressed by a combination of basic constraints,which forms a particular hierarchy structure of geometric constraint model.The geometric constraint system is coded as a directed geometric constraint graph which describes the relation among the basic geometric elements.The model method can reflect the decoupled property of orientation and position constraints clearly.The smaller solving units and the efficient solving sequence can be obtained.This method has been implemented in prototype system WhutVAS.

geometric constraint;geometric constraint solving;constraint handling;graph decomposition;Euler parameter

A

TP391

10.3778/j.issn.1002-8331.1209-0191

SH I Zhiliang,CHEN Yi,ZHANG Zhongquan.Research on united modeling method of generalized geometric constraint system.Computer Engineering and Applications,2014,50（16）：159-163.

國(guó)家自然科學(xué)基金（No.50905132）。

石志良（1974—），男，博士，副教授，主要研究方向?yàn)榧s束求解、參數(shù)化設(shè)計(jì)及智能CAD系統(tǒng)；陳誼（1988—），男，碩士研究生，主要研究方向?yàn)閿?shù)字化設(shè)計(jì)。E-mail：shizhil998@yahoo.com.cn

2012-09-19

2013-01-05

1002-8331（2014）16-0159-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-01-18,http://www.cnki.net/kcms/detail/11.2127.TP.20130118.1024.010.htm l