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