【文章內(nèi)容簡介】 dWnd 所指向的像素格式描述子結(jié)構(gòu)，利用該函數(shù)可以枚舉像素格式。 c） SetupGetPixelFormat(HDC hdc) 該函數(shù)用于獲取 hdc 的格式索引。 d） SetPixelFormat(m_hDC, pixelformat, amp。pfdWnd) 該函數(shù)用格式索引 pixelformat 來設(shè)置 hdc 的像素格式。在使用該函數(shù)之前應(yīng)該調(diào)用 ChoosePixelFormat 來獲取像素格式索引。另外， OpenGL 窗口風(fēng)格必須包含 WS_CLIPCHILDREN 和 WS_CLIPSIBLINGS 類型，否則設(shè)置失敗。 OpenGL 通常支持 24 種不同的像素格式，如果系統(tǒng)安裝了 OpenGL 硬件加速器，它會支持其他的像素格式。設(shè)置 DC 的像素格式的 邏輯圖 如圖 24 所示。 圖 24 設(shè)置像素格式 邏輯圖 碰撞檢測技術(shù) 碰撞檢測是構(gòu)造可視化系統(tǒng)的不可缺少的一個重要部分，它可以使用戶以更自然的方式與可視化系統(tǒng)中的場景對象進行交互。如果沒有碰撞檢測，當(dāng)一個對象碰到另一個對象時，往往會 ―穿墻而過 ‖，而不會產(chǎn)生碰撞的效果，這在現(xiàn)實中是不存在的。因此，構(gòu)造可視化系統(tǒng)時，必須能夠?qū)崟r、精確地判斷場景中物體之間是否發(fā)生碰撞?？梢暬到y(tǒng)中動態(tài)物體與靜態(tài)物體之間或動態(tài)物體之間的交互基礎(chǔ)就是碰撞檢測。 碰撞檢測 基本 原理 碰撞檢測（ Collision Detection）即檢測虛擬場景中不同對象之間是否發(fā)生了碰撞。從幾何上講，碰撞檢測表現(xiàn)為兩個多面體的求交測試問題。按照是否考慮時間參數(shù)，碰撞檢測又可分為 CCD（ Continouslly Collision Detection，連續(xù)碰撞檢測）和 DCD（ Discrete Collision Detection，離散碰撞檢測）。 CCD的定義如下： 設(shè)三維空間 R用三維幾何坐標系統(tǒng) wF 表示，其中有 N個運動模型， 其狀態(tài) 隨著時間而改變， iF 表示第 i個模型所占的空間。 wF 隨著時間的變化形成四維坐標系統(tǒng) wC ，模型 iF 沿 著 一定 的軌 跡運 動 形成 四維 坐標 系統(tǒng) iC ， 碰 撞 檢測 就是 判 斷???????? nCCCC 321 是否成立。 上述定義給出了碰撞檢測的精確的理論描述，但其計算 復(fù)雜度太高。在實際運用枚舉或選擇像素格式 DescribePixelFormat ChoosePixelFormat 期望的像素格式描述子結(jié)構(gòu) PIXELFORMATDESCRIPTOR 設(shè)置像素格式 匹配 NO YES 時 通常采用犧牲計算精度提高計算時間的方法，不考慮連續(xù)的四維空間，僅僅 在離散的點上考慮問題，以簡化碰撞檢測的計算 量 。具體方法 是在 計算出環(huán)境中所有物體在下一時刻的位置、方向等運動狀態(tài)后 ，檢測是否有對象在新的狀態(tài)下與其它物體重疊若有物體重疊，則發(fā)生碰撞，反之則不會發(fā)生碰撞 。這種方法稱為 DCD，由名稱可知，該方法 只檢測離散時間點上可能發(fā)生的碰撞，若對象運動速度很快或時間點間隔太長時， 則可能會 出現(xiàn) ―穿 墻而過 ‖的 現(xiàn)象。通常解決 的 方法有三種：一是 對物體的運動速度加以 限制；二是 盡可能地 減小離散點的 采樣間隔 ；三是對物體的運動狀態(tài)加以限制 。 碰撞檢測算法分析 考慮圍繞物體運動的整 個空間，所謂的碰撞檢測就是檢測物體由當(dāng)前狀態(tài)運動到下一狀態(tài)所經(jīng)過的四維空間與其它物體經(jīng)過的四維空間是否發(fā)生重疊，即檢測物體的運動軌跡。由此理論基礎(chǔ)，可以給出離散碰撞檢測算法，其偽代碼如下： Bool Collision Detection ( iA , jA )。 { Input iA 和 jA 。 for t←0到 T,采樣間隔 為 ? t for iA ∈ { 1A , 2A ,..., NA } 移動 iA 到 t時刻的位置 。 for jA ∈ { 1?iA , 2?iA ,… , NA } 移 動 jA 到 t時刻的位置 。 for對象的 iA 中的每一個多邊形 kP for對象的 jA 中的每一個多邊形 lP if( iP 與 jP 相交 ) return (true)。 //發(fā)生碰撞 else( iP 與 jP 沒有 相交 ) return (false)。 //沒有發(fā)生碰撞 } 由上面的偽 代碼可以看出， 程序中 含 三層循環(huán) 。 最外層的 for循環(huán) ， 時間 t以 采樣 間隔 ? t遞增。 步長 ? t越大 ， 檢測速度越快 ， 但檢測精度卻會下降 （嚴重時可能 出現(xiàn)漏檢 ）， 且這種 固定步長的檢測算法不能根據(jù)具體情況調(diào)整步長和精度。 第 二、三 層的 for循環(huán) ， 對所有 物體（ iA 和 jA ） 進行檢測 ， 使問題的時間復(fù)雜度變?yōu)?O( 2N )。最內(nèi)層的 for循環(huán) ， 即對組成多面體的基本幾何元素 （ 通常是三角形 ） 進行相交測試。 若場景中有 N個多面體 ， 每個多面體有 M個頂點 ， 則碰撞檢測的時間復(fù)雜度為 O( 2N 2M )。 上 述的碰撞檢測算法要遍歷所有的基本幾何元素 ， 是最基本的碰撞檢測算法 ，但是速度很慢 。 在實際運用中， 為了提高檢測速度 ，常常簡化 算法，簡化算法大 體上 可以 分為空間分解法和包圍盒層次法兩大類?？臻g分解法是將虛擬空間分解為體積相等的小單元格 ， 只對占據(jù)同一單元格或相臨單元格的幾何對象進行相交測試。典型的空間分解法有八叉樹法和二叉空間剖分法。包圍盒層次法是利用體積略大而形狀簡單的包圍盒把復(fù)雜的幾何對象包裹起來 ， 碰撞檢測時 在包圍盒之間進行 相交測試 。 如果包圍盒相交 ， 再進行幾何對象之間精確的碰撞檢測。顯然 ， 包圍盒法對于判斷兩個幾何對象不相交是十分有效的。包圍盒相交 ， 并不意味著兩個幾何對象一定相交 ， 所以包圍盒的選擇應(yīng)該滿足既簡單又緊密的要求。 經(jīng)典算法研究 在碰撞 檢測 中， 包圍盒 層次法 是比較成熟的算法，其 基本思想是通過建立對象的包圍盒層次來逐漸逼近對象的幾何模型 ， 從而用體積略大而形狀簡單的包圍盒代替復(fù)雜的幾何對象參加碰撞檢測 ， 通過包圍盒 之 間的相交測試 快速地 排列成 不相交的基本幾何元素對 ， 以減少相交測試的次數(shù)。 典型的 包圍盒碰撞檢測法包括球形包圍盒檢測法、 AABB（ Axis–Aligned Bounding Boxes，坐標軸的軸向包圍盒） 檢測法、 OBB（ Oriented Bounding Boxes， 方向 包圍盒 ） 檢測法、 kDOP（ Discrete Orientation Polytopes，離散方向多面體） 檢測法、 FDH（ Fixed Directions Hulls，固定方向凸包）檢測法等 。 a） 球形包圍盒檢測法 球形包圍盒 檢測 法是一種最簡單的碰撞檢測法 ，顧名思義 是用球形來 逼近 物體或物體的 某 一部分 ，再判斷近似的 包圍球是否相交。 這種檢測法 僅需要測試兩個球體中心的距離是否小于它們的半徑和 ，若小于，則發(fā)生 碰撞。如果用中心點距離的平方和半徑和的平方進行比較 ， 效果更好 。 由于 去除拙劣的開方運算， 運算量大大減少 。但是 ， 簡單的運算也導(dǎo)致了精確度的降低。 b） AABB檢測法 所謂 AABB，即 包含該碰撞體且邊平行于坐標軸的最小六面體。描述一個 AABB，僅需六個標量。在構(gòu)造 AABB時 ，僅 需沿著物體局部坐標系的軸向 （ x,y,z） 來構(gòu)造 。因此 ， 所有的 AABB具有一致的方向。 AABB樹是基于 AABB的二叉樹 ， 按照從上到下的遞歸細分方式構(gòu)造生成。在每一次遞歸過程中 ， 要求取最小的 AABB， 需沿所選的剖面分別將物體分為正負兩半 ，并將所對應(yīng)的原始幾何元素分別歸屬正、負兩邊 ， 整個遞歸過程類似于空間二叉剖分 ，只是每次剖分的對象是 AABB， 而不是空間區(qū)域。遞歸細分一直要進行到每一個葉子節(jié)點只包含一個原始幾何元素為止 ， 所以具有 n個原始幾何元素的 AABB樹具有 n1個非葉子節(jié)點和 n個葉子節(jié)點。 AABB樹之間的碰撞檢測是一個雙重遞歸遍歷的過程。對 于 AABB樹 A和 B，若 樹A的根節(jié)點的 AABB與樹 B內(nèi)部節(jié)點的 AABB不相交 ， 則停止向下遍歷。如果遍歷能達到樹 B的葉節(jié)點 ， 再用該葉節(jié)點遍歷樹 A；如果能到達樹 A的葉節(jié)點 ， 則進一步進行基本幾何元素之間的相交測試。 c） OBB檢測法 所謂 OBB，即 包含該對象且相對于坐標軸方向任意的正六面體。與 AABB樹相比 ，OBB的最大特點是其方向的任意性 ， 這使得它可以根據(jù) 被包裹對象的形狀特點盡可能緊密地包裹對象。該算法利用頂點坐標的一階和二階統(tǒng)計特性 ， 包圍盒層次的劃分依據(jù)是 ： ?? ??? ni iii rqpn 0 )(31? 式 （ ） 31)(31 0 ????? ?? kjrrqqppnC ni kjkjkjjk ，?????? 式 （ ） 其中 n構(gòu)成模型的三角形的數(shù)目； ??? ipp? ， ??? iqq? ， ??? irr? 是 31向量；T321 )( pppp ???? ，? 和 jkC 是 33協(xié)方差矩陣； ? ：均值； C ：協(xié)方差 ??ip ；第 i個三角形的三個頂點是 )( iii rqp ， 。 OBB的計算相對于 AABB和包圍球而言復(fù)雜一些 ， 其關(guān)鍵是尋找最佳方向 ， 并確定在該方向上包圍對象的包圍盒的最小尺寸。 OBB踫撞檢測算法 能有效提高系統(tǒng)的檢測效率，但在解決系統(tǒng)的實時性檢測問題時還稍 嫌不足。 d） kDOP檢測法 kDOP的概念最早 是 由 Kay和 Kajiya提出 的 ， 旨在將 各層次包圍盒盡可能緊密地包裹其中所含的景物。作為葉節(jié)點 ， 景物自身即是最緊的包圍盒 ， 但由于包圍盒的選取還要求光線與包圍盒的求交測試盡可能簡單 ， 因此 通常 選取形狀比較簡單的球體、圓柱體、長方體等作為包圍盒。但 是 這些形狀簡單的包圍盒具有包裹景物不緊的缺點 ，Kay和 Kajiya提出了根據(jù)景物的實際形態(tài)選取若干組不同方向的平行平面對 （ Slab） 包裹一個景物或一組景物的層次包圍盒技術(shù)。這些平行平面對組成一個凸體 ， 稱之為平行 2k面體 ， 如圖 25所示。 由圖可以看出每個物體需要用超過 3對平行平面對來逼近，所有的平行平面對都是由方向相反的兩個法向量所定義的半空間相交得到的，而這些平行平面對的法向量是固定不變的。在實際應(yīng)用中，可以合理地選擇法向量的方向，例如取集合 {1， 0，1}中的整數(shù)，以簡化平行平面對的計算。由此可以看出， AABB是 k=6時 kDOP的情形，即 6DOP。當(dāng) k足夠大時， kDOP就發(fā)展為物體的凸包 （ Convex Hull） 。對于平面圖形而言凸包是包圍一組控制點的凸多邊形的邊界；對于立體圖形而言凸包是用面片連接各頂點的多面體的包絡(luò)。 圖 25 用 平行平面對包裹對象示意圖 圖 26 平行平面對 與 對象交點 運算圖 對于 k值和平行平面對方向的選取 ， 考察 k=6， k=14， k=18， k=24時的情形。如前面所述 ，當(dāng) k=6時 ， kDOP就是 AABB， 可以看作是與坐標軸正交的 3對平行平面對的交集 ， 即平行平面對的法矢量由矢量 （ 1， 0， 0），（ 0， 1， 0） 和 （ 0， 0， 1）， 如圖 26所示。 當(dāng) k=14時就有 7對 （ K/2） 平行平面對來包裹物體 ， 選平行平面對的法矢量為 （ 1，0， 0），（ 0， 1， 0），（ 0， 0， 1），（ 1， 1， 1），（ 1， 1， 1），（ 1， 1， 1） 和（ 1， 1， 1） 。前面的 3個法矢量所決定的平行平面對的交集就是 AABB。后面 4個矢 量 決定的 8個斜半平面 切 了 AABB的 8個角。 k=18和 k=26時情形 ， 依此類推。因此 ， 只要合理地選取 k的大小以及平行平面對的方向 ， 就可以在碰撞檢測的簡單性和包裹物體的緊密性之間取得較好的折中。 e） FDH檢測法 FDH是一種特殊的凸包 ， 它 具 有 凸包緊密性好的優(yōu)點。 FDH可以看作是 AABB的擴展 。 AABB可以看作是與坐標軸正交的 3對平行的平面對的交集。兩個 AABB相交當(dāng)且僅當(dāng)所有的 3對平行平面對都分別相交 ,這個條件很容易檢測。 擴展 AABB的思想 ， 用超過 3對的平行平面對來逼近對象 ，這些平行平面對的法向量 固定不變。 FDH檢測 算法首先求一般物體的凸殼 ， 然后將物體的特征面分為一系列凸特征面子集和凹特征面子集 ， 分別對這些子集建立基于 FDH的包容體層次。對于凸特征面子集設(shè)定 一個界限值 ， 當(dāng)包容體中的特征面數(shù)小于這個值時 ， 細分終止。對于凹特征面子集則剖分到每個 葉節(jié)點只含一個基本幾何體。 FDH碰撞檢測的基本思想是利用幾何特性簡單的包圍盒代替復(fù)雜的幾何對象進行相交測試 ， 如果兩個結(jié)點上的包圍盒不相交 ， 則它們所包圍的對象的基本幾何元素的子集不相交 ， 從而不需要對子集中的元素作進一步的相交測試。 表 五種包圍盒方法的比較表 包圍盒方法 緊密性 檢測速度 檢測難度 檢測精度 應(yīng)用范圍 球形法 AABB OBB kDOP FDH 差 較差 中等 較好 好 快