前言
本篇总结何为拾取，如何解决这一问题，实现原理,优化加速
何为拾取？
在这之前，我们通过MVP变化、视口变换将物体从局部空间变换到屏幕空间来进行渲染。现在存在一个问题：用户用鼠标点击屏幕上的物体，在这一点上物体存在先后顺序，如何确定用户点击的是哪个物体呢？
解决之道：很容易想到，我们可以将物体变回3d空间，这样物体和物体之间就可以分辨前后顺序，然后从相机沿着鼠标光标点击的方向发出一条射线，判断第一个相交的物体
应变换至哪一空间？
变换到观察空间、世界空间、局部空间都是有可能的，绝大多数是变换至局部空间。原因如下：
- 观察空间：只能处理观察空间的物体
- 世界空间：将大量顶点变换至世界空间需要的运算量太大！
- 局部空间：物体往往相对于局部空间进行定义,且变换到局部空间需要的运算量相对于变换至世界空间来说是很小的
虽然如此，我们还是需要计算从屏幕空间到局部空间，它们总共经历这些阶段：屏幕空间->NDC空间->观察空间->世界空间->局部空间
屏幕空间到NDC空间
从NDC空间到屏幕空间的变换矩阵：\(\large M = \left[\begin {array} {cc} \frac{Widt}{2} & 0 & 0 & 0 \\ 0 & -\frac{Height}{2} & 0 & 0 \\ 0 & 0 & MAXDepth - MinDepth & 0 \\ TopLeftX + \frac{Width}{2} & TopLeftY + \frac{Height}{2} & MinDepth & 1 \end {array}\right]\)
现有NDC空间下的坐标\(\large p_{ndc} = (x_{ndc}, y_{ndc}, z_{ndc})\)，将\(p_{ndc}\)变换至屏幕空间：\(\large [x_{ndc}, y_{ndc}, z_{ndc}, 1] \left[\begin{array}{cc} \frac{w}{2} & 0 & 0 & 0 \\ 0 & -\frac{h}{2} & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \frac{w}{2} & \frac{h}{2} & 0 & 1 \end {array} \right] = [\frac{x_{ndc}w + w}{2}, \frac{-y_{ndc}h + h}{2}, z_{ndc}, 1]\)，但在屏幕空间我们会忽略z维度，因此求得点\(\large p_{s} = (x_s, y_x)： x_s = \frac{x_{ndc}w + w}{2}, y_s = \frac{-y_{ndc}h + h}{2}\)
但我们想要的是这一逆变换——即屏幕空间到NDC空间，左右调整即可：\(\large x_{ndc} = \frac{2x_s}{w} - 1, y_{ndc} = -\frac{2y_s}{h}+1\)
NDC空间到投影空间
从投影空间变换到NDC空间进行x除以r(宽高比)的操作，因此进行逆变换就需要乘以r：\(\large x_{ndc} = r(\frac{2x_s}{w} - 1), y_{ndc} = -\frac{2y_s}{h}+1\)
我们还定义投影窗口位于距原点\(\large d = cot(\frac{\alpha}{2}),\alpha\)为垂直视场角，但若用此方法还需计算\(cot(\frac{\alpha}{2})\)，用相似三角形的性质能进行优化：
\(\large \frac{x_{v'}}{1} = \frac{x_v}{d} = \frac{x_v}{cot(\frac{\alpha}{2})} = x_v \times tan(\frac{\alpha}{2}) = (\frac{2x_s}{w} - 1)rtan(\frac{\alpha}{2})\)
\(\large \frac{y_{v'}}{1} = \frac{y_v}{d} = \frac{y_v}{cot(\frac{\alpha}{2})} = y_v \times tan(\frac{\alpha}{2}) = (-\frac{2y_s}{h} + 1)rtan(\frac{\alpha}{2})\)
又由于，透视投影矩阵中\(P_{00} = \frac{1}{rtan(\frac{\alpha}{2})}, P_{11} = \frac{1}{tan(\frac{\alpha}{2})}\),因此\(x'_{v}, y'_{v}\)如下：
\(\large x'_v = \frac{\frac{2x_s}{w} - 1}{P_{00}} \\ y'_v = \frac{-\frac{2y_s}{h} + 1}{P_{11}}\)
如此一来，可令射线穿过点(\(\large x'_v, y'_v, 1\))
实现：
void PickingApp::Pick(int sx, int sy)
{
XMFLOAT4X4 P = mCamera.GetProj4x4f();
// 计算观察空间中的拾取射线
float vx = (+2.0f*sx / mClientWidth - 1.0f) / P(0,0);
float vy = (-2.0f*sy / mClientHeight + 1.0f) / P(1,1);
// 观察空间中拾取射线的定义
XMVECTOR rayOrigin = XMVectorSet(0.0f, 0.0f, 0.0f,1.0f);
XMVECTOR rayDir = XMVectorSet(vx, vy, 1.0f, 0.0f);
}
从观察空间到局部空间
设拾取射线为\(r_v(t) = q + tu,V\)是观察矩阵，\(W\)为世界矩阵，则局部空间的拾取射线为\(r_L(t) = (q + tu)V^{-1}W^{-1}\)
实现：
//一开始用户没有拾取任何点，因此将该渲染项设为不可见
mPickedRitem->Visible = false;
// 检测用户是否拾取一个渲染项
for(auto ri : mRitemLayer[(int)RenderLayer::Opaque])
{
auto geo = ri->Geo;
// 跳过不可见的渲染项
if(ri->Visible == false)
{
continue;
}
XMMATRIX V = mCamera.GetView();
XMMATRIX invView = XMMatrixInverse(&XMMatrixDeterminant(V), V);
XMMATRIX W = XMLoadFloat4x4(&ri->World);
XMMATRIX invWorld = XMMatrixInverse(&XMMatrixDeterminant(W), W);
// 将拾取射线变换至对应物体的局部空间
XMMATRIX toLocal = XMMatrixMultiply(invView,invWorld);
rayOrigin = XMVector3TransformCoord(rayOrigin,toLocal);
rayDir = XMVector3TransformNormal(rayDir, toLocal);
// 计算拾取射线方向上的单位长度，用于后续相交检测
rayDir = XMVector3Normalize(rayDir);
}
射线和物体的相交检测
很直观的想法是，我们对场景中所有可见物体的三角形逐一进行遍历，并执行相交检测。值得注意的是我们只关心与射线相交且离相机最近的三角形。实现如下：
float tmin = 0.0f;
if(ri->Bounds.Intersects(rayOrigin, rayDir, tmin))
{
auto vertices = (Vertex*)geo->VertexBufferCPU->GetBufferPointer();
auto indices = (std::uint32_t*)geo->IndexBufferCPU->GetBufferPointer();
UINT triCount = ri->IndexCount / 3;
// 对找到的离相机最近的三角形执行相交检测
tmin = MathHelper::Infinity;
for(UINT i = 0; i < triCount; ++i)
{
// 三角形索引
UINT i0 = indices[i * 3 + 0];
UINT i1 = indices[i * 3 + 1];
UINT i2 = indices[i * 3 + 2];
// 三角形顶点
XMVECTOR v0 = XMLoadFloat3(&vertices[i0].Pos);
XMVECTOR v1 = XMLoadFloat3(&vertices[i1].Pos);
XMVECTOR v2 = XMLoadFloat3(&vertices[i2].Pos);
//遍历物体网格上的所有三角形
float t = 0.0f;
if(TriangleTests::Intersects(rayOrigin, rayDir,v0, v1, v2, t))
{
if(t < tmin)
{
// 记录目前离相机最近的一个被拾取的三角形
tmin = t;
UINT pickedTriangle = i;
//为被拾取的三角形设置渲染项，后续对其进行其他操作
mPickedRitem->Visible = true;
mPickedRitem->IndexCount = 3;
mPickedRitem->BaseVertexLocation = 0;
//渲染项和被拾取的物体使用相同的世界矩阵
mPickedRitem->World = ri->World;
mPickedRitem->NumFramesDirty = gNumFrameResources;
mPickedRitem->StartIndexLocation = 3 * pickedTriangle;
}
}
}
}
显然易见的是，这种方法效率太低了!接下来将介绍几种优化方法
射线与AABB的相交检测
本方法思想是运用一个接近于网格的AABB，用射线和AABB进行相交检测，若射线和AABB没有相交直接跳过；若有相交则执行射线和三角形的相交检测。对应函数如下
bool XM_CALLCONV BoundingBox::Intersects(
FXMVECTOR Origin, // ray origin
FXMVECTOR Direction, // ray direction (must be unitlength)
float& Dist //射线的相关参数t
); const
射线与球体的相交检测
射线与球体的相交检测的函数原型如下：
bool XM_CALLCONV BoundingSphere::Intersects(
FXMVECTOR Origin,
FXMVECTOR Direction,
float& Dist
); const
射线和球体相交测试的推导过程：假设射线和球体有两个交点\(t_1,t_2\),球心为\(c\)，半径为\(r\)，相交点\(p\),射线\(r(t) = q + tu\),满足条件
\(\large |p-c| = r \\
r = |r(t) - c| \\ r^2 = (r(t) - c) (r(t) - c) \\ r^2 = (q + tu - c) (q + tu - c) \\
r^2 = (q - c + tu) (q - c + tu)\),设\(\large m = q - c\)，则有\(\large (m + tu)(m + tu) = r^2 \\ mm + 2tmu + t^2uu = r^2 \\ uut^2 + 2mut + mm - r^2 = 0\)，可以看出这是一个一元二次方程：\(\large a = uu \\ b = 2mu \\ c = mm - r^2\)，利用求根公式求得u：
- 若是两个不同的正实数解，说明射线和球体有两个交点
- 若是两个负实数解，说明射线的反向延长线上和球体有两个交点
- 若都包含虚部，说明没有相交
- 若是两个相同的实数解，说明射线和球体相切
- 若是一正一负两个解，说明射线起点在球体内，其中一个交点是射线的反向延长线
其中最小的正实数解即为所求t
射线与三角形的相交检测
射线与三角形的相交检测函数原型：
bool XM_CALLCONV TriangleTests::Intersects(
FXMVECTOR Origin,
FXMVECTOR Direction,
FXMVECTOR V0, // triangle vertex v0
GXMVECTOR V1, // triangle vertex v1
HXMVECTOR V2, // triangle vertex v2
float& Dist );
设射线\(\large r(t) = q + tu\)，在满足条件\(\large u \geqslant 0, v \geqslant 0,\)且\(\large u + v \leqslant 1\)时，\(\large T(u,v) = v_0 + u(v_1 - v_0) + v(v_2 - v_0)\)是一个三角形，欲求\(\large r(t) = T(u,v)\)时成立的\(\large t,u,v\),
\(\large q + tu = v_0 + u(v_1 - v_0) + v(v_2 - v_0) \\ q - v_0 = -tu + u(v_1 - v_0) + v(v_2 - v_0)\)
推导如下：设\(\large e_1 = v_1 - v_0, e_2 = v_2 - v_0\)且\(\large m = q - v_0\),则有：\(\large -tu + ue_1 + ve_2 = m \\ \left[\begin {array} {cc} \uparrow & \uparrow & \uparrow \\ -u & e_1 & e_2 \\ \downarrow & \downarrow & \downarrow \end {array} \right] \left[\begin {array} {cc} t \\ u \\ v \end {array} \right] = \left[\begin {array} {cc} \uparrow \\ m \\ \downarrow \end {array} \right]\).根据克莱姆法则\(\large x_i = \frac{detA_i}{detA}\),以列向量m替换左矩阵中第i列的列向量，则有：\(\large t = det\left[ \begin {array} {cc} \uparrow & \uparrow & \uparrow \\ m & e_1 & e_2 \\ \downarrow & \downarrow & \downarrow \end {array} \right] / det\left[ \begin {array} {cc} \uparrow & \uparrow & \uparrow \\ -u & e_1 & e_2 \\ \downarrow & \downarrow & \downarrow \end {array} \right] \\
\large u = det\left[ \begin {array} {cc} \uparrow & \uparrow & \uparrow \\ -u & m & e_2 \\ \downarrow & \downarrow & \downarrow \end {array} \right] /det \left[ \begin {array} {cc} \uparrow & \uparrow & \uparrow \\ -u & e_1 & e_2 \\ \downarrow & \downarrow & \downarrow \end {array} \right] \\
\large v = det\left[ \begin {array} {cc} \uparrow & \uparrow & \uparrow \\ -u & e_1 & m \\ \downarrow & \downarrow & \downarrow \end {array} \right] / det\left[ \begin {array} {cc} \uparrow & \uparrow & \uparrow \\ -u & e_1 & e_2 \\ \downarrow & \downarrow & \downarrow \end {array} \right]\)，根据等式\(\large det\left[ \begin {array} {cc} \uparrow & \uparrow & \uparrow \\ a & b & c \\ \downarrow & \downarrow & \downarrow \end {array} \right] = a·(b \times c)\),可得：\(\large t = \frac{-m·(e_1 \times e_2)}{ u · (e_1 \times e_2)} \\ \large u = \frac{u·(m \times e_2)}{u·(e_1 \times e_2)} \\ \large v = \frac{u·(e_1 \times m)}{u·(e_1 \times e_2)}\),
此时即可进行叉积\(m \times e_1\)和\(u \times e_2\)
reference
[Introduction to 3D Game Programming with DirectX 12 (Frank Luna) (z-lib.org).pdf](file:///C:/Users/爱莉希雅/Desktop/ebook/Introduction to 3D Game Programming with DirectX 12 (Frank Luna) (z-lib.org).pdf)