變分層次包圍體的構(gòu)建及其在碰撞檢測(cè)中的應(yīng)用.pdf

1、實(shí)時(shí)碰撞檢測(cè)是機(jī)器人、動(dòng)畫仿真、虛擬現(xiàn)實(shí)等領(lǐng)域中一個(gè)非常關(guān)鍵的問(wèn)題，其基本任務(wù)是確定兩個(gè)或多個(gè)物體彼此之間是否發(fā)生接觸或穿透。盡管針對(duì)碰撞檢測(cè)已有了大量有價(jià)值的研究成果，但隨著諸如虛擬現(xiàn)實(shí)等新興領(lǐng)域的涌現(xiàn)及隨之而來(lái)的人們對(duì)交互實(shí)時(shí)性、場(chǎng)景真實(shí)性要求的不斷提高，碰撞檢測(cè)技術(shù)所面臨的問(wèn)題也日益突出，其中最核心的問(wèn)題是如何有效地提高碰撞檢測(cè)的速度。 層次包圍體法是解決碰撞檢測(cè)問(wèn)題固有時(shí)間復(fù)雜性的一種有效的方法，它是用體積略大而幾何特性

2、簡(jiǎn)單的包圍體來(lái)近似地描述復(fù)雜的幾何對(duì)象。通過(guò)構(gòu)造樹(shù)狀層次結(jié)構(gòu)來(lái)逼近對(duì)象的幾何模型，在對(duì)包圍體層次樹(shù)進(jìn)行遍歷的過(guò)程中，通過(guò)包圍體間的快速相交測(cè)試來(lái)及早地排除明顯不可能相交的基本幾何元素對(duì)，而只對(duì)包圍體重疊的部分元素進(jìn)行進(jìn)一步的相交測(cè)試，以提高碰撞檢測(cè)的速度。 本文提出了一種基于迭代的Lloyd分簇方法的變分逼近構(gòu)建層次包圍體方法，為解決構(gòu)建層次包圍體問(wèn)題提供了一種新的方法，我們的方法所構(gòu)建的層次包圍樹(shù)以包圍體的外部體積為代價(jià)函數(shù)，