丁博++石熙++李峰

【摘 要】 由于三維CAD模型具有十分復(fù)雜的幾何形狀和拓?fù)浣Y(jié)構(gòu)，如何準(zhǔn)確的描述三維CAD模型，從而提高三維CAD模型的檢索效率，成為當(dāng)前迫切需要解決的問(wèn)題。本文提出了一種基于層次圖的三維CAD模型表征方法，層次圖中包含了特征依賴圖和屬性鄰接圖所描述的模型信息，因此，形狀特征描述符和拓?fù)潢P(guān)系描述符都可以在層次圖中提取，描述符的提取方便、準(zhǔn)確。同時(shí)，多層次的模型描述符不僅可以描述造型的總體形狀，還可以描述造型的局部細(xì)節(jié)，提高了三維CAD模型表征的準(zhǔn)確性和靈活性。

【關(guān)鍵詞】 三維CAD模型表征 層次圖 特征依賴圖 屬性鄰接圖

隨著計(jì)算機(jī)技術(shù)和計(jì)算機(jī)圖形學(xué)的不斷發(fā)展，三維CAD已經(jīng)滲透到工業(yè)生產(chǎn)中的各個(gè)方面，成為記錄和表達(dá)工程設(shè)計(jì)的主要載體[1]。有關(guān)研究表明，新產(chǎn)品開(kāi)發(fā)中重用現(xiàn)有的或供應(yīng)商提供的零部件占40%，修改后重用的零部件占40%，完全全新設(shè)計(jì)的零部件僅占20%[2]。據(jù)估計(jì)變型設(shè)計(jì)或自適應(yīng)設(shè)計(jì)約占到其中的90%，這表明大多數(shù)的設(shè)計(jì)工作可重用以前的產(chǎn)品設(shè)計(jì)知識(shí)。根據(jù)產(chǎn)品之間的相似性，最大限度地重用已有的設(shè)計(jì)資源來(lái)開(kāi)發(fā)新產(chǎn)品，不僅可以降低產(chǎn)品成本，縮短設(shè)計(jì)時(shí)間，而且還可有效的提高產(chǎn)品可靠性，保證產(chǎn)品質(zhì)量[3]。因此，準(zhǔn)確的表征三維CAD模型是實(shí)現(xiàn)三維CAD模型檢索的先決條件。

本文提出了一種基于層次圖的三維CAD模型表征方法，在層次圖中可以提取兩種模型描述符：形狀特征描述符和拓?fù)潢P(guān)系描述符。形狀特征描述可以有效描述三維CAD模型的整體形狀，拓?fù)潢P(guān)系描述符用來(lái)描述三維CAD模型的局部細(xì)節(jié)，從而實(shí)現(xiàn)了粗粒度和細(xì)粒度兩個(gè)層次的三維CAD模型檢索，提高了三維CAD模型的搜索效率。

1 相關(guān)知識(shí)介紹

目前，基于參數(shù)化的特征造型技術(shù)已經(jīng)非常成熟，大部分?jǐn)?shù)字化造型設(shè)計(jì)軟件都采用了特征造型方法。特征造型系統(tǒng)的體系結(jié)構(gòu)是一種三層結(jié)構(gòu)：底層是數(shù)據(jù)模型，由特征依賴圖（Feature Dependency Graph， FDG）表示，中間層是細(xì)胞元幾何模型，最上層是視圖模型[4]。

1.1 特征依賴圖

特征依賴圖（Feature Dependency Graph， FDG）包含了造型中的所有特征以及特征間的依賴關(guān)系，提供了造型的高層結(jié)構(gòu)[5]。特征依賴圖的形式化定義為：，其中，V={1，2，…，n}是特征依賴圖的節(jié)點(diǎn)集合；是特征依賴圖的邊集；是一個(gè)從節(jié)點(diǎn)集合到其屬性集合的映射，其中是節(jié)點(diǎn)的屬性集合；是一個(gè)從邊集合到其屬性集合的映射，其中為邊的屬性集合。圖1是一個(gè)CAD模型，圖2是它的特征依賴圖表示。

1.2 細(xì)胞元模型

在CAD系統(tǒng)中，細(xì)胞元模型表示CAD模型的幾何信息，主要采用邊界表示（Boundary Representation，B-Rep）方法。三維CAD模型的屬性鄰接圖（Property Adjacency Graph， PAG）采用CAD模型的B-Rep信息提取表示。通過(guò)提取CAD模型中的B-Rep信息，將CAD模型轉(zhuǎn)化為屬性鄰接圖。圖3為圖1的屬性鄰接圖。

2 基于層次圖的三維CAD模型表征

本文提出了一種基于層次圖的三維CAD模型表征方法，在層次圖中可以提取兩種模型描述符：形狀特征描述符和拓?fù)潢P(guān)系描述符。多層次的模型描述符不僅可以描述造型的總體形狀，還可以描述造型的局部細(xì)節(jié)。

本文通過(guò)構(gòu)建層次圖實(shí)現(xiàn)三維CAD模型的多層次描述，層次圖中包含了特征依賴圖和屬性鄰接圖所描述的模型信息。圖4是圖1所示CAD模型的層次圖?；趯哟螆D進(jìn)行三維CAD模型檢索時(shí)，始終以粗層次信息為主導(dǎo)確定匹配的整體走勢(shì)，以細(xì)層次信息為輔助調(diào)整匹配的局部細(xì)節(jié)，這種匹配方案既符合人類的認(rèn)知過(guò)程，又能夠保證模型多個(gè)層次間匹配的一致性。

定義1層次圖（Hierarchical Graph， HG）是由五元組表示的一棵樹(shù)：

其中V為樹(shù)的特征節(jié)點(diǎn)集合；為樹(shù)的邊集合，其元素為有序節(jié)點(diǎn)對(duì)，由父節(jié)點(diǎn)指向子節(jié)點(diǎn)；是一個(gè)從節(jié)點(diǎn)集合到屬性鄰接圖集合的映射，對(duì)每一個(gè)節(jié)點(diǎn)，存在，表征節(jié)點(diǎn)v對(duì)應(yīng)的屬性鄰接圖；是一個(gè)從節(jié)點(diǎn)集合到其屬性集合的映射，Wv是節(jié)點(diǎn)的屬性集合；是一個(gè)從邊集合到其屬性集合的映射，其中WE為邊的屬性集合。

層次圖與一般的圖不同，圖中的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)屬性鄰接圖，故層次圖結(jié)構(gòu)中存在兩種類型的節(jié)點(diǎn)，即屬性圖中的節(jié)點(diǎn)和層次圖自身的節(jié)點(diǎn)。相應(yīng)地，邊也有屬于內(nèi)部屬性鄰接圖的邊和對(duì)應(yīng)層次圖的邊。在檢索的過(guò)程中，不僅僅要考慮其層次圖自身的節(jié)點(diǎn)以及邊的匹配，還要考慮其節(jié)點(diǎn)內(nèi)部屬性鄰接圖中節(jié)點(diǎn)及邊的匹配，二者間相互關(guān)聯(lián)，彼此影響。

2.1 形狀特征的提取

為了有效地支持粗粒度的三維CAD模型檢索，我們?cè)谔卣饕蕾噲D中將提取相關(guān)的屬性，包括：“特征類型”、“依賴關(guān)系”和“層次”， 特征類型指的是層次圖中特征的類型；依賴關(guān)系是指特征間必須滿足的依存關(guān)系；層次記錄了特征所屬的層次。

2.2 拓?fù)潢P(guān)系的提取

拓?fù)潢P(guān)系是指CAD模型的點(diǎn)、線、面、環(huán)之間的連接關(guān)系。三維CAD模型的拓?fù)潢P(guān)系從屬性鄰接圖中提取，屬性鄰接圖的形式化定義為：，其中，V={1，2，…，n}是屬性鄰接圖的節(jié)點(diǎn)集合，是屬性鄰接圖的邊集。B-Rep模型中的每一個(gè)面都有唯一的頂點(diǎn)Vi相對(duì)應(yīng)，因此，頂點(diǎn)Vi的屬性即為模型中面的屬性，面的屬性包括：面的幾何類型、面的凹凸性、外環(huán)邊的數(shù)量、外環(huán)邊的幾何類型和外環(huán)邊的凹凸性等信息。E為面的鄰接關(guān)系，任意兩個(gè)面都有唯一一條邊與之對(duì)應(yīng)。邊的屬性包括：邊的凹凸性和邊所連接的面類型等信息。

3 結(jié)語(yǔ)

本文提出了一種基于層次圖的三維CAD模型表征方法。層次圖中可以提取兩種模型描述符：形狀特征描述符和拓?fù)潢P(guān)系描述符。形狀特征描述可以有效描述三維CAD模型的整體形狀，拓?fù)潢P(guān)系描述符用來(lái)描述三維CAD模型的局部細(xì)節(jié)，從而實(shí)現(xiàn)了粗粒度和細(xì)粒度兩個(gè)層次的三維CAD模型表征，該方法描述三維CAD模型正確、靈活，為三維CAD模型檢索提供了有利的先決條件。

參考文獻(xiàn)：

[1]Tao S Q， Huang Z D， Zuo B Q， etal. Partial retrieval of CAD models based on the gradient flows in Lie group [J].Pattern Recognition，2012，45：1721-1738.

[2]石民，張樹(shù)生.基于特征鄰接圖的三維CAD模型檢索算法[J].機(jī)械科學(xué)與技術(shù)，2012，31（4）：583-587.

[3]潘翔，張三元，葉修梓.三維模型語(yǔ)義檢索研究進(jìn)展[J].計(jì)算機(jī)學(xué)報(bào)，2009，32（6）： 1069-1079.

[4]Sypkens Smit Matthijs， Bronsvoort Willem F.The difference between two feature models[J].Computer-Aided Design and Applications，2007，4（6）：843-81.

[5]BRONSVOORT W F，BIDARRA R， NYIRENDA P J.Developments in feature modeling[J].Computer-Aided Design and Application，2006，3（5）：655-664.endprint

【摘 要】 由于三維CAD模型具有十分復(fù)雜的幾何形狀和拓?fù)浣Y(jié)構(gòu)，如何準(zhǔn)確的描述三維CAD模型，從而提高三維CAD模型的檢索效率，成為當(dāng)前迫切需要解決的問(wèn)題。本文提出了一種基于層次圖的三維CAD模型表征方法，層次圖中包含了特征依賴圖和屬性鄰接圖所描述的模型信息，因此，形狀特征描述符和拓?fù)潢P(guān)系描述符都可以在層次圖中提取，描述符的提取方便、準(zhǔn)確。同時(shí)，多層次的模型描述符不僅可以描述造型的總體形狀，還可以描述造型的局部細(xì)節(jié)，提高了三維CAD模型表征的準(zhǔn)確性和靈活性。

【關(guān)鍵詞】 三維CAD模型表征 層次圖 特征依賴圖 屬性鄰接圖

隨著計(jì)算機(jī)技術(shù)和計(jì)算機(jī)圖形學(xué)的不斷發(fā)展，三維CAD已經(jīng)滲透到工業(yè)生產(chǎn)中的各個(gè)方面，成為記錄和表達(dá)工程設(shè)計(jì)的主要載體[1]。有關(guān)研究表明，新產(chǎn)品開(kāi)發(fā)中重用現(xiàn)有的或供應(yīng)商提供的零部件占40%，修改后重用的零部件占40%，完全全新設(shè)計(jì)的零部件僅占20%[2]。據(jù)估計(jì)變型設(shè)計(jì)或自適應(yīng)設(shè)計(jì)約占到其中的90%，這表明大多數(shù)的設(shè)計(jì)工作可重用以前的產(chǎn)品設(shè)計(jì)知識(shí)。根據(jù)產(chǎn)品之間的相似性，最大限度地重用已有的設(shè)計(jì)資源來(lái)開(kāi)發(fā)新產(chǎn)品，不僅可以降低產(chǎn)品成本，縮短設(shè)計(jì)時(shí)間，而且還可有效的提高產(chǎn)品可靠性，保證產(chǎn)品質(zhì)量[3]。因此，準(zhǔn)確的表征三維CAD模型是實(shí)現(xiàn)三維CAD模型檢索的先決條件。

本文提出了一種基于層次圖的三維CAD模型表征方法，在層次圖中可以提取兩種模型描述符：形狀特征描述符和拓?fù)潢P(guān)系描述符。形狀特征描述可以有效描述三維CAD模型的整體形狀，拓?fù)潢P(guān)系描述符用來(lái)描述三維CAD模型的局部細(xì)節(jié)，從而實(shí)現(xiàn)了粗粒度和細(xì)粒度兩個(gè)層次的三維CAD模型檢索，提高了三維CAD模型的搜索效率。

1 相關(guān)知識(shí)介紹

目前，基于參數(shù)化的特征造型技術(shù)已經(jīng)非常成熟，大部分?jǐn)?shù)字化造型設(shè)計(jì)軟件都采用了特征造型方法。特征造型系統(tǒng)的體系結(jié)構(gòu)是一種三層結(jié)構(gòu)：底層是數(shù)據(jù)模型，由特征依賴圖（Feature Dependency Graph， FDG）表示，中間層是細(xì)胞元幾何模型，最上層是視圖模型[4]。

1.1 特征依賴圖

特征依賴圖（Feature Dependency Graph， FDG）包含了造型中的所有特征以及特征間的依賴關(guān)系，提供了造型的高層結(jié)構(gòu)[5]。特征依賴圖的形式化定義為：，其中，V={1，2，…，n}是特征依賴圖的節(jié)點(diǎn)集合；是特征依賴圖的邊集；是一個(gè)從節(jié)點(diǎn)集合到其屬性集合的映射，其中是節(jié)點(diǎn)的屬性集合；是一個(gè)從邊集合到其屬性集合的映射，其中為邊的屬性集合。圖1是一個(gè)CAD模型，圖2是它的特征依賴圖表示。

1.2 細(xì)胞元模型

在CAD系統(tǒng)中，細(xì)胞元模型表示CAD模型的幾何信息，主要采用邊界表示（Boundary Representation，B-Rep）方法。三維CAD模型的屬性鄰接圖（Property Adjacency Graph， PAG）采用CAD模型的B-Rep信息提取表示。通過(guò)提取CAD模型中的B-Rep信息，將CAD模型轉(zhuǎn)化為屬性鄰接圖。圖3為圖1的屬性鄰接圖。

2 基于層次圖的三維CAD模型表征

本文提出了一種基于層次圖的三維CAD模型表征方法，在層次圖中可以提取兩種模型描述符：形狀特征描述符和拓?fù)潢P(guān)系描述符。多層次的模型描述符不僅可以描述造型的總體形狀，還可以描述造型的局部細(xì)節(jié)。

本文通過(guò)構(gòu)建層次圖實(shí)現(xiàn)三維CAD模型的多層次描述，層次圖中包含了特征依賴圖和屬性鄰接圖所描述的模型信息。圖4是圖1所示CAD模型的層次圖。基于層次圖進(jìn)行三維CAD模型檢索時(shí)，始終以粗層次信息為主導(dǎo)確定匹配的整體走勢(shì)，以細(xì)層次信息為輔助調(diào)整匹配的局部細(xì)節(jié)，這種匹配方案既符合人類的認(rèn)知過(guò)程，又能夠保證模型多個(gè)層次間匹配的一致性。

定義1層次圖（Hierarchical Graph， HG）是由五元組表示的一棵樹(shù)：

其中V為樹(shù)的特征節(jié)點(diǎn)集合；為樹(shù)的邊集合，其元素為有序節(jié)點(diǎn)對(duì)，由父節(jié)點(diǎn)指向子節(jié)點(diǎn)；是一個(gè)從節(jié)點(diǎn)集合到屬性鄰接圖集合的映射，對(duì)每一個(gè)節(jié)點(diǎn)，存在，表征節(jié)點(diǎn)v對(duì)應(yīng)的屬性鄰接圖；是一個(gè)從節(jié)點(diǎn)集合到其屬性集合的映射，Wv是節(jié)點(diǎn)的屬性集合；是一個(gè)從邊集合到其屬性集合的映射，其中WE為邊的屬性集合。

層次圖與一般的圖不同，圖中的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)屬性鄰接圖，故層次圖結(jié)構(gòu)中存在兩種類型的節(jié)點(diǎn)，即屬性圖中的節(jié)點(diǎn)和層次圖自身的節(jié)點(diǎn)。相應(yīng)地，邊也有屬于內(nèi)部屬性鄰接圖的邊和對(duì)應(yīng)層次圖的邊。在檢索的過(guò)程中，不僅僅要考慮其層次圖自身的節(jié)點(diǎn)以及邊的匹配，還要考慮其節(jié)點(diǎn)內(nèi)部屬性鄰接圖中節(jié)點(diǎn)及邊的匹配，二者間相互關(guān)聯(lián)，彼此影響。

2.1 形狀特征的提取

為了有效地支持粗粒度的三維CAD模型檢索，我們?cè)谔卣饕蕾噲D中將提取相關(guān)的屬性，包括：“特征類型”、“依賴關(guān)系”和“層次”， 特征類型指的是層次圖中特征的類型；依賴關(guān)系是指特征間必須滿足的依存關(guān)系；層次記錄了特征所屬的層次。

2.2 拓?fù)潢P(guān)系的提取

拓?fù)潢P(guān)系是指CAD模型的點(diǎn)、線、面、環(huán)之間的連接關(guān)系。三維CAD模型的拓?fù)潢P(guān)系從屬性鄰接圖中提取，屬性鄰接圖的形式化定義為：，其中，V={1，2，…，n}是屬性鄰接圖的節(jié)點(diǎn)集合，是屬性鄰接圖的邊集。B-Rep模型中的每一個(gè)面都有唯一的頂點(diǎn)Vi相對(duì)應(yīng)，因此，頂點(diǎn)Vi的屬性即為模型中面的屬性，面的屬性包括：面的幾何類型、面的凹凸性、外環(huán)邊的數(shù)量、外環(huán)邊的幾何類型和外環(huán)邊的凹凸性等信息。E為面的鄰接關(guān)系，任意兩個(gè)面都有唯一一條邊與之對(duì)應(yīng)。邊的屬性包括：邊的凹凸性和邊所連接的面類型等信息。

3 結(jié)語(yǔ)

本文提出了一種基于層次圖的三維CAD模型表征方法。層次圖中可以提取兩種模型描述符：形狀特征描述符和拓?fù)潢P(guān)系描述符。形狀特征描述可以有效描述三維CAD模型的整體形狀，拓?fù)潢P(guān)系描述符用來(lái)描述三維CAD模型的局部細(xì)節(jié)，從而實(shí)現(xiàn)了粗粒度和細(xì)粒度兩個(gè)層次的三維CAD模型表征，該方法描述三維CAD模型正確、靈活，為三維CAD模型檢索提供了有利的先決條件。

參考文獻(xiàn)：

[1]Tao S Q， Huang Z D， Zuo B Q， etal. Partial retrieval of CAD models based on the gradient flows in Lie group [J].Pattern Recognition，2012，45：1721-1738.

[2]石民，張樹(shù)生.基于特征鄰接圖的三維CAD模型檢索算法[J].機(jī)械科學(xué)與技術(shù)，2012，31（4）：583-587.

[3]潘翔，張三元，葉修梓.三維模型語(yǔ)義檢索研究進(jìn)展[J].計(jì)算機(jī)學(xué)報(bào)，2009，32（6）： 1069-1079.

[4]Sypkens Smit Matthijs， Bronsvoort Willem F.The difference between two feature models[J].Computer-Aided Design and Applications，2007，4（6）：843-81.

[5]BRONSVOORT W F，BIDARRA R， NYIRENDA P J.Developments in feature modeling[J].Computer-Aided Design and Application，2006，3（5）：655-664.endprint

【摘 要】 由于三維CAD模型具有十分復(fù)雜的幾何形狀和拓?fù)浣Y(jié)構(gòu)，如何準(zhǔn)確的描述三維CAD模型，從而提高三維CAD模型的檢索效率，成為當(dāng)前迫切需要解決的問(wèn)題。本文提出了一種基于層次圖的三維CAD模型表征方法，層次圖中包含了特征依賴圖和屬性鄰接圖所描述的模型信息，因此，形狀特征描述符和拓?fù)潢P(guān)系描述符都可以在層次圖中提取，描述符的提取方便、準(zhǔn)確。同時(shí)，多層次的模型描述符不僅可以描述造型的總體形狀，還可以描述造型的局部細(xì)節(jié)，提高了三維CAD模型表征的準(zhǔn)確性和靈活性。

【關(guān)鍵詞】 三維CAD模型表征 層次圖 特征依賴圖 屬性鄰接圖

隨著計(jì)算機(jī)技術(shù)和計(jì)算機(jī)圖形學(xué)的不斷發(fā)展，三維CAD已經(jīng)滲透到工業(yè)生產(chǎn)中的各個(gè)方面，成為記錄和表達(dá)工程設(shè)計(jì)的主要載體[1]。有關(guān)研究表明，新產(chǎn)品開(kāi)發(fā)中重用現(xiàn)有的或供應(yīng)商提供的零部件占40%，修改后重用的零部件占40%，完全全新設(shè)計(jì)的零部件僅占20%[2]。據(jù)估計(jì)變型設(shè)計(jì)或自適應(yīng)設(shè)計(jì)約占到其中的90%，這表明大多數(shù)的設(shè)計(jì)工作可重用以前的產(chǎn)品設(shè)計(jì)知識(shí)。根據(jù)產(chǎn)品之間的相似性，最大限度地重用已有的設(shè)計(jì)資源來(lái)開(kāi)發(fā)新產(chǎn)品，不僅可以降低產(chǎn)品成本，縮短設(shè)計(jì)時(shí)間，而且還可有效的提高產(chǎn)品可靠性，保證產(chǎn)品質(zhì)量[3]。因此，準(zhǔn)確的表征三維CAD模型是實(shí)現(xiàn)三維CAD模型檢索的先決條件。

本文提出了一種基于層次圖的三維CAD模型表征方法，在層次圖中可以提取兩種模型描述符：形狀特征描述符和拓?fù)潢P(guān)系描述符。形狀特征描述可以有效描述三維CAD模型的整體形狀，拓?fù)潢P(guān)系描述符用來(lái)描述三維CAD模型的局部細(xì)節(jié)，從而實(shí)現(xiàn)了粗粒度和細(xì)粒度兩個(gè)層次的三維CAD模型檢索，提高了三維CAD模型的搜索效率。

1 相關(guān)知識(shí)介紹

目前，基于參數(shù)化的特征造型技術(shù)已經(jīng)非常成熟，大部分?jǐn)?shù)字化造型設(shè)計(jì)軟件都采用了特征造型方法。特征造型系統(tǒng)的體系結(jié)構(gòu)是一種三層結(jié)構(gòu)：底層是數(shù)據(jù)模型，由特征依賴圖（Feature Dependency Graph， FDG）表示，中間層是細(xì)胞元幾何模型，最上層是視圖模型[4]。

1.1 特征依賴圖

特征依賴圖（Feature Dependency Graph， FDG）包含了造型中的所有特征以及特征間的依賴關(guān)系，提供了造型的高層結(jié)構(gòu)[5]。特征依賴圖的形式化定義為：，其中，V={1，2，…，n}是特征依賴圖的節(jié)點(diǎn)集合；是特征依賴圖的邊集；是一個(gè)從節(jié)點(diǎn)集合到其屬性集合的映射，其中是節(jié)點(diǎn)的屬性集合；是一個(gè)從邊集合到其屬性集合的映射，其中為邊的屬性集合。圖1是一個(gè)CAD模型，圖2是它的特征依賴圖表示。

1.2 細(xì)胞元模型

在CAD系統(tǒng)中，細(xì)胞元模型表示CAD模型的幾何信息，主要采用邊界表示（Boundary Representation，B-Rep）方法。三維CAD模型的屬性鄰接圖（Property Adjacency Graph， PAG）采用CAD模型的B-Rep信息提取表示。通過(guò)提取CAD模型中的B-Rep信息，將CAD模型轉(zhuǎn)化為屬性鄰接圖。圖3為圖1的屬性鄰接圖。

2 基于層次圖的三維CAD模型表征

本文提出了一種基于層次圖的三維CAD模型表征方法，在層次圖中可以提取兩種模型描述符：形狀特征描述符和拓?fù)潢P(guān)系描述符。多層次的模型描述符不僅可以描述造型的總體形狀，還可以描述造型的局部細(xì)節(jié)。

本文通過(guò)構(gòu)建層次圖實(shí)現(xiàn)三維CAD模型的多層次描述，層次圖中包含了特征依賴圖和屬性鄰接圖所描述的模型信息。圖4是圖1所示CAD模型的層次圖?；趯哟螆D進(jìn)行三維CAD模型檢索時(shí)，始終以粗層次信息為主導(dǎo)確定匹配的整體走勢(shì)，以細(xì)層次信息為輔助調(diào)整匹配的局部細(xì)節(jié)，這種匹配方案既符合人類的認(rèn)知過(guò)程，又能夠保證模型多個(gè)層次間匹配的一致性。

定義1層次圖（Hierarchical Graph， HG）是由五元組表示的一棵樹(shù)：

其中V為樹(shù)的特征節(jié)點(diǎn)集合；為樹(shù)的邊集合，其元素為有序節(jié)點(diǎn)對(duì)，由父節(jié)點(diǎn)指向子節(jié)點(diǎn)；是一個(gè)從節(jié)點(diǎn)集合到屬性鄰接圖集合的映射，對(duì)每一個(gè)節(jié)點(diǎn)，存在，表征節(jié)點(diǎn)v對(duì)應(yīng)的屬性鄰接圖；是一個(gè)從節(jié)點(diǎn)集合到其屬性集合的映射，Wv是節(jié)點(diǎn)的屬性集合；是一個(gè)從邊集合到其屬性集合的映射，其中WE為邊的屬性集合。

層次圖與一般的圖不同，圖中的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)屬性鄰接圖，故層次圖結(jié)構(gòu)中存在兩種類型的節(jié)點(diǎn)，即屬性圖中的節(jié)點(diǎn)和層次圖自身的節(jié)點(diǎn)。相應(yīng)地，邊也有屬于內(nèi)部屬性鄰接圖的邊和對(duì)應(yīng)層次圖的邊。在檢索的過(guò)程中，不僅僅要考慮其層次圖自身的節(jié)點(diǎn)以及邊的匹配，還要考慮其節(jié)點(diǎn)內(nèi)部屬性鄰接圖中節(jié)點(diǎn)及邊的匹配，二者間相互關(guān)聯(lián)，彼此影響。

2.1 形狀特征的提取

為了有效地支持粗粒度的三維CAD模型檢索，我們?cè)谔卣饕蕾噲D中將提取相關(guān)的屬性，包括：“特征類型”、“依賴關(guān)系”和“層次”， 特征類型指的是層次圖中特征的類型；依賴關(guān)系是指特征間必須滿足的依存關(guān)系；層次記錄了特征所屬的層次。

2.2 拓?fù)潢P(guān)系的提取

拓?fù)潢P(guān)系是指CAD模型的點(diǎn)、線、面、環(huán)之間的連接關(guān)系。三維CAD模型的拓?fù)潢P(guān)系從屬性鄰接圖中提取，屬性鄰接圖的形式化定義為：，其中，V={1，2，…，n}是屬性鄰接圖的節(jié)點(diǎn)集合，是屬性鄰接圖的邊集。B-Rep模型中的每一個(gè)面都有唯一的頂點(diǎn)Vi相對(duì)應(yīng)，因此，頂點(diǎn)Vi的屬性即為模型中面的屬性，面的屬性包括：面的幾何類型、面的凹凸性、外環(huán)邊的數(shù)量、外環(huán)邊的幾何類型和外環(huán)邊的凹凸性等信息。E為面的鄰接關(guān)系，任意兩個(gè)面都有唯一一條邊與之對(duì)應(yīng)。邊的屬性包括：邊的凹凸性和邊所連接的面類型等信息。

3 結(jié)語(yǔ)

本文提出了一種基于層次圖的三維CAD模型表征方法。層次圖中可以提取兩種模型描述符：形狀特征描述符和拓?fù)潢P(guān)系描述符。形狀特征描述可以有效描述三維CAD模型的整體形狀，拓?fù)潢P(guān)系描述符用來(lái)描述三維CAD模型的局部細(xì)節(jié)，從而實(shí)現(xiàn)了粗粒度和細(xì)粒度兩個(gè)層次的三維CAD模型表征，該方法描述三維CAD模型正確、靈活，為三維CAD模型檢索提供了有利的先決條件。

參考文獻(xiàn)：

[1]Tao S Q， Huang Z D， Zuo B Q， etal. Partial retrieval of CAD models based on the gradient flows in Lie group [J].Pattern Recognition，2012，45：1721-1738.

[2]石民，張樹(shù)生.基于特征鄰接圖的三維CAD模型檢索算法[J].機(jī)械科學(xué)與技術(shù)，2012，31（4）：583-587.

[3]潘翔，張三元，葉修梓.三維模型語(yǔ)義檢索研究進(jìn)展[J].計(jì)算機(jī)學(xué)報(bào)，2009，32（6）： 1069-1079.

[4]Sypkens Smit Matthijs， Bronsvoort Willem F.The difference between two feature models[J].Computer-Aided Design and Applications，2007，4（6）：843-81.

[5]BRONSVOORT W F，BIDARRA R， NYIRENDA P J.Developments in feature modeling[J].Computer-Aided Design and Application，2006，3（5）：655-664.endprint