图形学物体拾取：CPU VS GPU

一、CPU – raycaster

射线包围盒是一种常用的方法，在 CPU 中进行拾取，性能较好，但是精度较差。当拾取频率不高时，可以考虑使用像素级精度的帧缓冲拾取Framebuffer Picker.射线投射涉及将射线投射到场景中并检查对象和射线之间的碰撞。这样做有一些缺点；如果您有多个具有许多三角形的复杂网格形状，则计算碰撞可能会很昂贵，可以使用包围盒来判断,但是因为包围盒比较简单，拾取边缘误差较大。此外，您需要编写算法或使用第三方库来遍历您的场景并计算碰撞。这为小型纯图形项目增加了不必要的工作量。

射线拾取的原理就是坐标变换，相信熟悉图形流水线的都非常清楚：

物体坐标系->(模型矩阵)世界坐标系->(视角矩阵)view/camera坐标系->(投影矩阵)裁剪坐标系->(透视除法)NDC坐标系->(窗口变换)窗口坐标系;

所以射线拾取就是反过来:窗口坐标系->NDC坐标系 ->世界坐标系.

射线数学表达: Ray = o+kv (o原点,)

/**
     * 射线拾取函数
     * 选中的网格模型变为半透明效果
     */
    function ray() {
        var Sx = event.clientX;//鼠标单击位置横坐标
        var Sy = event.clientY;//鼠标单击位置纵坐标
        //屏幕坐标转标准设备坐标
        var x = ( Sx / window.innerWidth ) * 2 - 1;//标准设备横坐标
        var y = -( Sy / window.innerHeight ) * 2 + 1;//标准设备纵坐标
        var standardVector  = new THREE.Vector3(x, y, 0.5);//标准设备坐标
        //标准设备坐标转世界坐标
        var worldVector = standardVector.unproject(camera);
        //射线投射方向单位向量(worldVector坐标减相机位置坐标)
        var ray = worldVector.sub(camera.position).normalize();
        //创建射线投射器对象
        var raycaster = new THREE.Raycaster(camera.position, ray);
        //返回射线选中的对象
        var intersects = raycaster.intersectObjects([boxMesh,sphereMesh,cylinderMesh]);
        if (intersects.length > 0) {
            intersects[0].object.material.transparent = true;
            intersects[0].object.material.opacity = 0.6;
        }
    }

拾取Mesh上的图元比如三角形或者顶点：
在这里插入图片描述

二、 GPU – Framebuffer Picker

在将场景渲染到屏幕上时，GPU已经在进行该mesh所有必要的计算，以确定每个像素应该具有什么颜色。深度测试会丢弃看不见的片元。当点击位于a（x，y）的像素，这个像素的颜色实际上是特定场景中的Object。这种技术的想法是为在渲染每个对象时通过推送常量为它们提供唯一标识符，然后在填充颜色缓冲区的同时将其渲染到额外的帧缓冲区目标 glFramebufferRenderbuffer。渲染完成后，将纹理读回主机，并使用鼠标坐标查找对象标识符。OpenGL 提供了一个 glReadPixels 函数它是利用颜色的6位16进制表示，以颜色作为ID，在后台渲染出纹理后，根据鼠标坐标下的纹理颜色，进行ID的查询进行拾取操作.。当然，你不想把它渲染到屏幕上。像素信息将在缓冲区中可用，但不会显示在屏幕上。该技术的问题在于，需要再次将场景渲染为图像（FBO的RTT）。但是，对象拾取仅在用户单击鼠标按钮时完成，因此该性能损失仅在该时间发生在绘图中，这是带有几个对象的原始场景。每个对象都将指定一种唯一的颜色。

流程如下：

准备好两份数据，一份渲染输出到屏幕，一份渲染到FBO，同时把每个物体的信息存起来。
创建一个webglRenderTarget()(FBO，不直接输出到屏幕)。
渲染FBO，通过获取到的颜色位换算回ID值，判断点击了那个物体。
通过ID值获取到点击的物体的信息，在生成一个正方体套在点击物体外面，表示高亮。
最后正常渲染场景，输出到颜色缓冲区（屏幕）。

GPU的picking优化降低显存消耗：

GPU的RTT Pick有一些小技巧，比如把RTT的尺寸设置为4个像素，降低渲染一帧的负担之类的，makeFrustum可以设置一下视窗的位置和尺寸，调整一下尺寸。相应的代码也得改一下，主要是像素位置要对应上。具体实现：就是调节framebuffer的尺寸，最后你要返回一个Image来解译ID。这个Image可以很小。我记得是4x4（至于为什么最小是4x4，因为在GPU中的帧缓存或者说纹理的数据结构就是平铺多维数组，就是俗称的分块，最小是4x4）；回归正题，在设置RTT的时候，要设置一下Framebuffer object的大小，这个尺寸可以通过camera的投影矩阵来设置，RTT要attach一个纹理，这个纹理尺寸就是可以是4x4。然后通过设置makeFrustrum，来设置RTT Camera的透视投影为你想要的像素位置，然后将针对该像素左下4x4这个大小区域进行绘制。当然具体makeFrustrum的参数不是4x4，而是反算到你的NDC Space下的，大概是的。你绘制的场景不变，只是绘制的投影矩阵变了，拾取只关心鼠标周围的像素ID，不关心距离很远的那些像素，这样就不用消耗过多的显存。特别注意!是渲染的场景不变，不是渲染的窗口不变。渲染的窗口通过设置投影矩阵来聚焦到鼠标周围，然后绘制的纹理要设置到一个小尺寸下,绘制出来后，图像的00点就是你鼠标位置处的那个像素。如果你设置了100x100的纹理，你就会看到从鼠标位置开始，左下100x100那么大的图像。

这个思想在分屏渲染里用的很多实际上就是假设这一个屏幕是一个4x4的窗口了，另外用的是RTT技术而已。想象一下你现在有一个10x10个屏幕，然后你想渲染1000x1000这么大的图像。那么每个图像就是100x100。你怎么去渲染这单个图像呢？其实就是你每次移动就渲染其他新的，但是永远也不可能说能看完一整张，也不用看完一整张图！本人最近也在看GAMES104游戏引擎架构，当你要实现一个小引擎或者工作实操上有很多小trick，比如可以延迟查询来降低回传同步造成的CPU卡顿，比如交互操作用不着实时渲染查询，每一秒渲染一次也就够了，这就可以降低大量的数据传输卡顿了。读到这相信你能跟我一样理解什么事工业界什么事学术界的区别~

三、拓展 – 深度值拾取

第三种方法前辈大佬说08年测绘院就有写过，看来我还是在玩泥巴哈哈哈哈~~~鼠标位置可以转换到gl_FragCoord.xy，深度值是FragCoord.z，这就是Projection后的[-1,1]区间坐标值（opengl是-1到1，而DX是0到1），然后invVP得到世界坐标的值。这就是一个普通的转换，如果是从gbuffer返回来，那就说的高级一点就是coordinate regeneration但是换汤不换药。

该方法的工作原理如下：沿鼠标射线获取整个深度范围，并将其存储为有限的固定大小。我选择 DEPTH_ARRAY_SCALE 32用于演示目的，但实际上应该在 1000 左右。在片段着色器中，我们将实体 ID 写入相应的深度桶 bucket中。为了创建存储bucket.，使用绑定到片元着色器的写到存储缓冲区。

#define DEPTH_ARRAY_SCALE 32

layout(set=0, binding = 3) buffer writeonly s_Write_t
{
    uint data[DEPTH_ARRAY_SCALE];
} s_Write;

我们通过 push_constant 以 uniform 的形式将UNIQUE_ID和MOUSE_POS传递给片段着色器

layout(push_constant) uniform PushConsts
{
    vec2 MOUSE_POS;
    uint UNIQUE_ID;
} pushC;

然后在片段着色器中，我们得到顶点着色器使用 gl_FragCoord.z 计算的当前深度值。这个值应该在 0 和 1 之间。我们通过将它乘以数组的长度 (DEPTH_ARRAY_SCALE) 来放大它。这给了我们深度桶 bucket的索引。如果我们当前着色的像素接近当前鼠标坐标，我们将唯一 ID 写入该索引位置。

// get the depth and scale it up by
// the total number of buckets in depth array
uint zIndex = uint(gl_FragCoord.z * DEPTH_ARRAY_SCALE);

if( length( pushC.MOUSE_POS - gl_FragCoord.xy) < 1)
{
    s_Write.data[zIndex] = pushC.UNIQUE_ID;
}

以上是片元着色器~
在主机端，你可以做两件事之一，要么使用 HOST_VISIBLE 存储缓冲区，并保持它的持久映射。或者，使用 DEVICE_LOCAL 存储缓冲区，并在写入片段后执行 bufferCopy。我选择了前者，因为它更容易。
您现在在主机上拥有的是一个数组，其中数组中的每个索引都代表鼠标射线上的某个深度。我们遍历数组并找到最接近的非零值。

auto * v = ... get mapped memory ...
auto u = static_cast<uint32_t*>(v);


uint32_t SELECTED_OBJECT_ID = 0;


for(size_t i=0;i<DEPTH_ARRAY_SCALE;i++)
{
    if( u[i] != 0)
    {
        SELECTED_OBJECT_ID = u[i];
        break;
    }
}
// we have to zero out the memory each frame
std::memset(v, 0, DEPTH_ARRAY_SCALE * sizeof(uint32_t));