3D交互圖形應(yīng)用程序中，常常要用鼠標(biāo)去選擇圖形，其實(shí)現(xiàn)的機(jī)制基于鼠標(biāo)拾取算法。本文主要講述如何在D3D中實(shí)現(xiàn)圖元的鼠標(biāo)拾取。為了討論簡單，本文假定讀者理解D3D 坐標(biāo)變換流程和基本的圖形學(xué)知識(shí)，如果閱讀有困難請參考相關(guān)資料。
1、什么是拾取，拾取能做什么？
首先，拾取操作指當(dāng)我們在屏幕上用鼠標(biāo)點(diǎn)擊某個(gè)圖元應(yīng)用程序能返回該圖元的一個(gè)標(biāo)志和某些相關(guān)信息。有圖形程序設(shè)計(jì)經(jīng)驗(yàn)的人都知道，有這些信息就表示我們有了對(duì)該圖元的控制權(quán)，我們可以刪除，可以編輯，可以任意對(duì)待該圖元，至于你到底想干什么，就是閣下自己的事了^_^。
2、拾取操作的步驟和實(shí)現(xiàn)
拾取算法的思想很簡單：得到鼠標(biāo)點(diǎn)擊處的屏幕坐標(biāo)，通過投影矩陣和觀察矩陣把該坐標(biāo)轉(zhuǎn)換為通過視點(diǎn)和鼠標(biāo)點(diǎn)擊點(diǎn)的一條射入場景的光線，該光線如果與場景模型的三角形相交（本文只處理三角形圖元），則獲取該相交三角形的信息。本文講述的方法除可以得到三角形的一個(gè)索引號(hào)以外還可以得到相交點(diǎn)的重心坐標(biāo)。
從數(shù)學(xué)角度來看，我們只要得到射線的方向矢量和射線的出射點(diǎn)，我們就具備了判斷射線與空間一個(gè)三角面是否相交的條件，本文主要討論如何獲得這些條件，并描述了射線三角面相交判斷算法和D3D的通常實(shí)現(xiàn)方法。
根據(jù)拾取操作的處理順序，大概可以依次分為以下幾個(gè)步驟
2.1． 變換并獲得通過視點(diǎn)和屏幕上點(diǎn)擊點(diǎn)的射線矢量（Dir）
詳細(xì)介紹之前，為了大家方便理解，我們要先簡單說一下d3d坐標(biāo)轉(zhuǎn)換的大概流程，如下圖:
所以我們要通過一系列的反變換，得到我們關(guān)心的值在世界坐標(biāo)中的表示。
2.1.1 確定鼠標(biāo)選取點(diǎn)的屏幕坐標(biāo)
這一步是非常簡單的Windows給我們提供了API來完成屏幕坐標(biāo)的獲取，使用GetCursorPos獲得鼠標(biāo)指針位置，然后再利用ScreenToClient轉(zhuǎn)換坐標(biāo)到客戶區(qū)坐標(biāo)系(以窗口視區(qū)左上角為坐標(biāo)原點(diǎn)，單位為像素)，設(shè)該坐標(biāo)為（POINT screenPt）。
2.1.2 得到Dir在觀察坐標(biāo)空間內(nèi)的表示
在觀察坐標(biāo)系中，Dir是一條從觀察坐標(biāo)原點(diǎn)出發(fā)的射線，所以我們只需要再確定一個(gè)該射線經(jīng)過的點(diǎn)，就可以得到它在觀察坐標(biāo)系中的表示。假設(shè)我們要求的射線上的另外一點(diǎn)為該射線與透視投影平截頭體近剪切面的交點(diǎn)，針對(duì)最普遍的透視投影而言，透視投影平截頭體經(jīng)投影變換后，變成一個(gè)1/2立方體（請?jiān)试S我這么叫^_^，因?yàn)樗拇笮橐粋€(gè)正方體的一半，x,y方向邊長為2，z方向?yàn)?）如圖：
投影坐標(biāo)系以近剪切面中心為坐標(biāo)原點(diǎn)，該立方體從z軸負(fù)向看過去與圖形程序視區(qū)相對(duì)應(yīng)，最終近剪切面（前剪切面）上一點(diǎn)與屏幕坐標(biāo)之間的對(duì)應(yīng)關(guān)系如下圖所示：
projPt.y = (screenPt.y-screenHeight/2)/screenHeight*2; （公式2）
projPt.z =0;（實(shí)際該值可任意取，不影響最終結(jié)果。為了處理簡單，我們?nèi)「闹禐?，表示該點(diǎn)取在近剪切面上）得到projPt后，我們需要做的是把該點(diǎn)坐標(biāo)從投影空間轉(zhuǎn)換到觀察空間(view space),根據(jù)透視投影的定義，
可假設(shè)點(diǎn)(projPt.x，projPt.y，projPt.z)
對(duì)應(yīng)的其次坐標(biāo)為 (projPt.x*projPt.w，projPt.y*projPt.w，projPt.z*projPt.w，projPt.w)
我們可以通過 GetTransform( D3DTS_PROJECTION, &ProjMatrix)函數(shù)獲得投影矩陣ProjMatrix,則根據(jù)觀察空間到投影空間的變換關(guān)系則
(projPt.x*projPt.w，projPt.y*projPt.w，projPt.z*projPt.w，projPt.w)= (viewPt.x，viewPt.y，viewPt.z, 1)*pProjMatrx;
根據(jù)定義和圖形學(xué)原理
根據(jù)比例關(guān)系，screenPt與投影空間上的點(diǎn)projPt之間的關(guān)系為
假設(shè)圖形程序窗口的寬為screenWidth,高為screenHeight,
projPt.x = (screenPt.x-screenWidth/2)/screenWidth*2; （公式1）
所以,
(projPt.x*projPt.w，projPt.y*projPt.w，projPt.z*projPt.w，projPt.w)
= ( viewPt.x*ProjMatrix._m11,
viewPt.y*ProjMatrix._m22,
viewPt.z*Q-QZn,
viewPt.z)
所以
projPt.x*projPt.w = viewPt.x*ProjMatrix._m11
projPt.y*projPt.w = viewPt.y*ProjMatrix._m22
projPt.z*projPt.w = viewPt.z*Q-QZn （注意projPt.z = 0）
projPt.w = viewPt.z;
解得
viewPt.x = projPt.x*Zn/ ProjMatrix._m11;
viewPt.y = projPt.y*Zn/ ProjMatrix._m22;
viewPt.z = Zn;
好了，到這里為止我們終于求出了射線與近剪切面交點(diǎn)在觀察坐標(biāo)系中的坐標(biāo)，現(xiàn)在我們擁有了射線的出發(fā)點(diǎn)(0,0,0)和射線方向上另外一點(diǎn)(viewPt.x,viewPt.y,viewPt.z),則該射線的方向矢量在觀察空間中的表示可確定為（viewPt.x-0,viewPt.y-0,viewPt.z-0）,化簡一下三個(gè)分量同除近剪切面z坐標(biāo)Zn，該方向矢量可寫作
DIRview = (projPt.x/projMatrix._m11,projPt.y/projMatrix._m22,1)
代入公式1，公式2
DIRview.x = (2*screenPt.x/screenWidth-1)/projMatrix._m11;
DIRview.y = (2*screenPt.y/screenHeight-1)/projMatrix._m22;
DIRview.z = 1;
其中screenWidth和screenHeight可以通過圖像顯示的backBuffer的目標(biāo)表面（D3DSURFACE_DESC）來獲得，該表面在程序初始化時(shí)由用戶創(chuàng)建。
2.1.3 轉(zhuǎn)換Dir到世界坐標(biāo)空間，并得到觀察點(diǎn)在世界坐標(biāo)系中的坐標(biāo)
由于最終的運(yùn)算要在世界坐標(biāo)空間中進(jìn)行，所以我們還需要把矢量DIRview從觀察空間轉(zhuǎn)換為世界坐標(biāo)空間中的矢量DIRworld。
因?yàn)?/p>
DIRview = DIRworld*ViewMatrix;
其中ViewMatrix為觀察矩陣，在D3D中可以用函數(shù)GetTransform( D3DTS_VIEW, &ViewMatrix )得到。
所以DIRworld = DIRview * inverse_ViewMatrix,其中inverse_ViewMatrix為
ViewMatrix的逆矩陣。
觀察點(diǎn)在觀察坐標(biāo)系中坐標(biāo)為OriginView（0，0，0，1），所以其在世界坐標(biāo)系中的坐標(biāo)同樣可以利用ViewMatrix矩陣，反變換至世界坐標(biāo)系中，事實(shí)上我們可以很簡單的判斷出,其在世界坐標(biāo)系中的表示為:
OriginWorld = (inverse_ViewMatrix._41,
inverse_ViewMatrix._42,
inverse_ViewMatrix._43,
1);
到這里為止，判斷射線與三角面是否相交的條件就完全具備了。
2.2 使用射線矢量對(duì)場景中的所有三角形圖元求交，獲得三角形索引值和重心坐標(biāo)。
這一步驟地實(shí)現(xiàn)由兩種途徑:
第一種方法非常簡單，利用D3D提供的擴(kuò)展函數(shù)D3DXIntersect可以輕松搞定一切。見2.1
第二種方法就是我們根據(jù)空間解析幾何的知識(shí)，自己來完成射線三角形的求交算法。一般來講，應(yīng)用上用第一種方法就足夠了，但是我們?nèi)绻钊氲脑挘仨毨斫庀嘟粰z測的數(shù)學(xué)算法，這樣才能自由的擴(kuò)展，面對(duì)不同的需求，內(nèi)容見2.2
下面分別講解兩種實(shí)現(xiàn)途徑：
2.2.1 D3D擴(kuò)展函數(shù)實(shí)現(xiàn)求交
這種方法很簡單也很好用，對(duì)于應(yīng)用來說應(yīng)盡力是用這種方式來實(shí)現(xiàn)，畢竟效率比自己寫得要高得多。
實(shí)際上其實(shí)沒什么好講的，大概講一下函數(shù)D3DXIntersect吧
D3D SDK該函數(shù)聲明如下
HRESULT D3DXIntersect(
LPD3DXBASEMESH pMesh,
CONST D3DXVECTOR3 *pRayPos,
CONST D3DXVECTOR3 *pRayDir,
BOOL *pHit,
DWORD *pFaceIndex,
FLOAT *pU,
FLOAT *pV,
FLOAT *pDist,
LPD3DXBUFFER *ppAllHits,
DWORD *pCountOfHits
);
l pMesh指向一個(gè)ID3DXBaseMesh的對(duì)象，最簡單的方式是從.x文件獲得，描述了要進(jìn)行相交檢測的三角面元集合的信息，具體規(guī)范參閱direct9 SDK
l pRayPos 指向射線發(fā)出點(diǎn)
l pRayDir 指向前面我們辛辛苦苦求出的射線方向的向量
l pHit 當(dāng)檢測到相交圖元時(shí)，指向一個(gè)true,不與任何圖元相交則為假
l pU 用于返回重心坐標(biāo)U分量
l pV返回重心坐標(biāo)V分量
l pDist 返回射線發(fā)出點(diǎn)到相交點(diǎn)的長度
注意：以上紅色字體部分均指最近的一個(gè)返回結(jié)果（即*pDist最小）
l ppAllHits用于如果存在多個(gè)相交三角面返回相交的所有結(jié)果
l pCountOfHits 返回共有多少個(gè)三角形與該射線相交
補(bǔ)充：重心坐標(biāo)的概念
其中pU和pV用到了重心坐標(biāo)的概念，下面稍作描述
一個(gè)三角形有三個(gè)頂點(diǎn)，在迪卡爾坐標(biāo)系中假設(shè)表示為V1(x1,y1,z1),V2(x2,y2,z2),V3(x3,y3,z3),則三角形內(nèi)任意一點(diǎn)的坐標(biāo)可以表示為 pV = V1 + U(V2-V1) + V(V3-V1),所以已知三個(gè)頂點(diǎn)坐標(biāo)的情況下，任意一點(diǎn)可用坐標(biāo)(U,V)來表示，其中 參數(shù)U控制V2在結(jié)果中占多大的權(quán)值，參數(shù)V控制V3占多大權(quán)值，最終1－U－V控制V1占多大權(quán)值，這種坐標(biāo)定義方式就叫重心坐標(biāo)。
2..2.2射線三角面相交的數(shù)學(xué)算法
使用d3d擴(kuò)展函數(shù)，畢竟有時(shí)不能滿足具體需求，掌握了該方法，我們才能夠獲得最大的控制自由度，任意修改算法。
已知條件: 射線源點(diǎn)orginPoint,三角形三個(gè)頂點(diǎn) v1,v2,v3,射線方向 Dir
（均以三維坐標(biāo)向量形式表示）
算法目的: 判斷射線與三角形是否相交，如果相交求出交點(diǎn)的重心坐標(biāo)(U,V)和射線原點(diǎn)到交點(diǎn)的距離T。
我們可先假設(shè)射線與三角形相交則交點(diǎn)(注以下均為向量運(yùn)算，*數(shù)乘，dot(X,Y) X，Y 點(diǎn)乘，cross（X，Y）X，Y叉乘；U，V，T為標(biāo)量)
則：
IntersectPoint = V1 + U*(V2-V1) + V*(V3-V1) ;
IntersectPoint = originPoint + T*Dir；
所以
orginPoint + T*Dir = V1 + U*(V2-V1) + V*(V3-V1);
整理得：
這是一個(gè)簡單的線性方程組，若有解則行列式[-Dir,V2-V1,V3-V1] 不為0。
根據(jù)T,U,V的含義當(dāng)T>0, 0<U<1,0<V<1,0<U+V<1時(shí)該交點(diǎn)在三角形內(nèi)部，
解此方程組即可獲得我們關(guān)心的值,具體解法不再贅述，克萊姆法則就夠了（詳細(xì)見線性代數(shù)）:射線原點(diǎn)到相交點(diǎn)的距離T,和交點(diǎn)的中心坐標(biāo)(U,V)。
下面給出Direct 9 SDK示例程序中的實(shí)現(xiàn)代碼
IntersectTriangle( const D3DXVECTOR3& orig,
const D3DXVECTOR3& dir, D3DXVECTOR3& v0,
D3DXVECTOR3& v1, D3DXVECTOR3& v2,
FLOAT* t, FLOAT* u, FLOAT* v )
{
// 算出兩個(gè)邊的向量
D3DXVECTOR3 edge1 = v1 - v0;
D3DXVECTOR3 edge2 = v2 - v0;
D3DXVECTOR3 pvec;
D3DXVec3Cross( &pvec, &dir, &edge2 );
// 如果det為0，或接近于零則射線與三角面共面或平行，不相交
//此處det就相當(dāng)于上面的 ，
FLOAT det = D3DXVec3Dot( &edge1, &pvec );
D3DXVECTOR3 tvec;
if( det > 0 )
{
tvec = orig - v0;
}
else
{
tvec = v0 - orig;
det = -det;
}
if( det < 0.0001f )
return FALSE;
// 計(jì)算u并測試是否合法（在三角形內(nèi)）
*u = D3DXVec3Dot( &tvec, &pvec );
if( *u < 0.0f || *u > det )
return FALSE;
// Prepare to test V parameter
D3DXVECTOR3 qvec;
D3DXVec3Cross( &qvec, &tvec, &edge1 );
//計(jì)算u并測試是否合法（在三角形內(nèi)）
*v = D3DXVec3Dot( &dir, &qvec );
if( *v < 0.0f || *u + *v > det )
return FALSE;
/*計(jì)算t,并把t,u,v放縮為合法值（注意前面的t,v,u不同于算法描述中的相應(yīng)量，乘了一個(gè)系數(shù)det）,注意：由于該步運(yùn)算需要使用除法，所以放到最后來進(jìn)行，避免不必要的運(yùn)算，提高算法效率*/
*t = D3DXVec3Dot( &edge2, &qvec );
FLOAT fInvDet = 1.0f / det;
*t *= fInvDet;
*u *= fInvDet;
*v *= fInvDet;
return TRUE;
}
2.2.3 拾取完成根據(jù)獲得的中心坐標(biāo)計(jì)算我們關(guān)心的常見量。
根據(jù)重心坐標(biāo)（U,V）,我們可以很容易的算出各種相關(guān)量比如紋理坐標(biāo)和交點(diǎn)的差值顏色，假設(shè)以紋理坐標(biāo)為例設(shè)V1,V2,V3的紋理坐標(biāo)分別為T1(tu1,tv1),T2(tu2,tv2),T3(tu3,tv3)則交點(diǎn)的坐標(biāo)為
IntersectPointTexture = T1 + U(T2-T1) + V(T3-T1)
3、結(jié)束及聲明
Ok, 到這里為止關(guān)于拾取的相關(guān)知識(shí)就介紹完了，小弟第一次寫這種文章，不知道有沒有把問題說清楚，希望對(duì)大家有所幫助，有任何問題可以給我發(fā)email: jzhang1@mail.xidian.edu.cn或者到我的網(wǎng)站留言： www.heavysword.com
聲明：本文寫作的目的是為了廣大D3D學(xué)習(xí)者方便學(xué)習(xí)服務(wù)，文中算法為作者參考相關(guān)文獻(xiàn)總結(jié)，作者無意把這些據(jù)為自己的成果，所有權(quán)原算法提出者所有（參閱參考文獻(xiàn)），文中代碼為D3d SDK的示例內(nèi)容，由筆者進(jìn)行了必要的解釋，代碼版權(quán)歸microsoft所有。
4、參考文獻(xiàn)
1、Microsoft DirectX 9.0 SDK,microsoft
2、fast,Minimun Storage Ray/Triangle Intersection,Tomas Moler,Ben Trumbore