一种基于GPU的三维几何图元拾取方法

摘要

一种基于GPU的三维几何图元拾取方法，意在解决现有技术中拾取效率低、拾取对象有限、拾取信息量小等各种不足。在进行拾取绘制时关闭光栅化，将鼠标位置信息和图元顶点坐标变换到规范化设备坐标系或视口坐标系，通过在几何处理器中判断投影后的二维图元与鼠标位置或选择框的关系进行命中判定，并利用变换反馈将拾取结果返回应用程序。本发明既适用于单体拾取，也适用于块拾取，拾取绘制时无需进行光栅化和片元处理，拾取过程高效快捷，可以获取到丰富的拾取信息，能够满足包含大量几何图元的图形应用中的实时交互需求，可应用到各种交互式图形应用中，例如CAD系统、游戏、UI、虚拟现实应用等。

说明书

【技术领域】

本发明涉及一种三维几何图元的快速选择与拾取方法，特别涉及一种基于图形处理单元GPU的三维几何图元拾取方法。

 

【背景技术】

图形拾取是指，根据用户使用鼠标等定位设备进行点击操作的位置或者进行框选操作的区域信息，返回选中的几何图元的ID等相关信息的过程。根据图形拾取的结果，方可进行进一步的交互操作，因此该技术是交互式图形应用的关键技术之一，在CAD软件、游戏、图形用户界面等方面有着广泛应用。

图形拾取方式分为单体拾取和块拾取两种。单体拾取使用鼠标点击选取单个图形对象；而块拾取使用鼠标键按下后拖动形成的矩形框选取位于矩形框内部的一个或多个图形对象。

现有的三维几何图元拾取方法主要有以下三种：

1、老版本OpenGL中提供的拾取方法

基于固定流水线的老版本OpenGL提供了一种基于名称堆栈和拾取矩阵的拾取方法。其主要步骤为：设置名称缓存，进入选择模式，初始化名称堆栈，设置拾取矩阵，进行拾取绘制，返回常规模式，处理命中记录。拾取的原理是利用拾取矩阵修改投影变换，将视域体限制在以鼠标位置为中心的拾取块内，绘制时，如果图形对象未被完全裁减掉，则根据当前名称堆栈中的名称信息在名称缓存中记录一次命中信息。该方法需要为不同的图形对象设置不同的ID，并在绘制相应对象前更新名称堆栈(进行名称的压入与弹出操作)。

该方法的缺点是：频繁的名称堆栈的压入与弹出操作会严重影响拾取的效率；另外对于场景中含有大量几何图元的情况，名称堆栈容易产生溢出；此外，该方法仅能得到拾取到的图形对象ID，但得不到命中该对象的具体位置信息(比如所命中的三角形的坐标)。

2、射线相交测试法

射线相交测试法将鼠标选中的点从屏幕坐标系逆变换到世界坐标系得到投影点，然后将从视点指向投影点的射线与场景中的各个几何图元在世界坐标系下进行相交测试，找出被选中的物体。

射线相交测试法的步骤如下：首先获得屏幕上鼠标点击的点，找到其对应的投影窗口上的点p；然后计算拾取射线，即一条从原点出发穿过点p的射线；将射线乘以投影矩阵和观察矩阵级联后矩阵的转置逆矩阵，变换到和模型相同的坐标系中，即将射线和模型变换到同一坐标系中；判定射线和物体是否相交，如果相交则该物体是被拾取到的物体，对于有多个物体与射线相交的情况，可根据深度信息判定拾取到的物体。

该方法能够得到更精确的拾取信息，但不适用于块拾取。进行块拾取时，拾取点有非常多个，需要用多条射线进行相交测试，计算量太大。

3、基于离屏渲染的拾取方法

此方法是将图形对象ID等信息编码为颜色，在进行拾取时进行一次额外的绘制，将不同对象以不同的颜色绘制到离屏缓存中，绘制完成后根据鼠标位置读取离屏缓存中相应位置像素的颜色值，进行解码从而获得拾取到的物体信息。

该方法的步骤如下：首先进行初始化，创建离屏缓存对象FBO以及对图形对象ID等信息进行颜色编码；然后在拾取时进行一次额外的绘制，绘制时使用与正常模式一样的变换，保证渲染得到的图像中物体位置与正常模式下一致，但绘制时每个对象使用不同的单一颜色；绘制结束后，从离屏缓存中读取与鼠标位置对应的像素的颜色，对其解码从而获得物体的ID等信息。

此方法有以下缺点：需要进行一次额外的绘制，须耗费一定时间；再者对象信息编码容量受到离屏缓存位深的限制；此外相对于前两种方法，该方法能够获取到的拾取对象信息非常有限，例如只能拾取到位于最前方的对象，而获取不到位于拾取位置后方被遮挡的对象。

随着现代GPU的迅速发展，GPU的并行处理能力以超摩尔定律的速度发展着，在并行处理方面较CPU有着绝对优势，同时GPU的可编程能力越来越强，灵活性越来越高。Shader Model 4.0的GPU上已经可以进行Vertex Shader、Geometry Shader和Fragment Shader三个阶段的GPU编程；Shader Model 5.0中更是增加了曲面细分Shader以及用于GPU通用计算的Compute Shader等。Shader 是自定义的在GPU上运行的小程序，用于替代固定渲染管线中的部分流程。可编程能力的增强使得可以实现更多的图形特效，同时也能利用GPU进行更广泛的通用计算。

 

【发明内容】

本发明针对现有技术中拾取效率低、拾取对象有限、拾取信息量小等各种不足，通过将GPU用于通用计算目的而非渲染目的，充分利用现代GPU的并行处理能力、可编程性及灵活性，提供一种可在大量几何图元中快速拾取目标图元或图元集合，并能获取丰富拾取信息的拾取方法。

该方法的基本思想是，将鼠标位置信息和图元顶点坐标变换到规范化设备坐标系或视口坐标系，利用几何处理器(Geometry Shader)判断投影后的二维图元与鼠标位置或选择框的关系，并利用变换反馈(Transform Feedback)将拾取结果返回应用程序。

本发明的技术方案是：

一种基于GPU的三维几何图元单体拾取方法，其特征在于，包括如下步骤：

(1)     将鼠标位置由窗口设备坐标系转换到规范化设备坐标系(当拾取三角形时)或视口坐标系(当拾取线段或点时)下，并将其传入几何处理器；

(2)     关闭光栅化，使得进行拾取绘制时图元仅流经顶点处理器和几何处理器；

(3)     开启变换反馈，绘制各拾取对象，利用几何处理器判断当前图元是否会覆盖到鼠标位置，如果会覆盖到则利用变换反馈将图元信息输出到回馈缓存中，如果不会覆盖到则遗弃当前图元；应用程序端负责场景的组织、绘制顺序的控制，以及为顶点处理器和几何处理器提供拾取需要的属性参数。

(4)     关闭变换反馈，查询反馈结果，处理和获取拾取信息。

所述的基于GPU的三维几何图元单体拾取方法，其特征在于，所述步骤(3)中，绘制各拾取对象时GPU端顶点处理器主要对输入顶点进行坐标变换，变换到裁剪坐标系下，如果需要获取拾取到的图元的其他坐标系下坐标，则在顶点处理器中进行计算并传给几何处理器。

所述的基于GPU的三维几何图元单体拾取方法，其特征在于，绘制各拾取对象时GPU端几何处理器要进行以下处理：

(1)     定义输入输出图元类型，输入图元可能为三角形、线段或点，每个命中图元只产生一套属性输出，即输出图元类型设为点；

(2)     根据需要定义输出到回馈缓存的属性(例如图元所属对象的ID、父对象ID、鼠标位置深度、图元顶点世界坐标等等)；

(3)     将输入的裁剪坐标系下的图元顶点坐标通过透视相除转换到规范化设备坐标系下，如果输入图元是线段或点，则进一步转换到视口坐标系下；

(4)     通过取图元顶点的前两维坐标，得到规范化设备坐标系下投影平面上的二维图元坐标，然后判断鼠标位置是否在该二维图元内部；

(5)     如果鼠标位置在图元内部，则设置并输出拾取信息到回馈缓存，其中拾取点的深度信息通过对图元顶点的深度进行线性插值得到；如果鼠标位置在图元外部，则遗弃当前图元，不做输出。

所述的基于GPU的三维几何图元单体拾取方法，其特征在于，在所述绘制各拾取对象时GPU端几何处理器进行处理的步骤(4)中，判断鼠标位置是否在二维图元内部的方法是：

1) 如果输入图元是三角形，则沿逆时针绕向访问图元各顶点，如果拾取点始终在各边的左边，则其在三角形内部，否则即在外部，可根据边向量与从顶点指向拾取点向量叉乘结果的z坐标符号判定拾取点是否在边的左边；

2) 如果输入图元是线段，如果拾取点到线段的距离小于等于线宽的一半，且以线段为底边、拾取点为顶部点的三角形的两个底角都不是钝角，则拾取点在线段上，否则在线段外；

3）如果输入图元是点，根据拾取点到图元的距离与点尺寸的关系决定拾取点是否在图元内部。

一种基于GPU的三维几何图元块拾取方法，其步骤包括：

(1)     将鼠标选择框坐标由窗口设备坐标系转换到规范化设备坐标系下，并将其传入几何处理器；

(2)     关闭光栅化，使得进行拾取绘制时图元仅流经顶点处理器和几何处理器；

(3)     开启变换反馈，绘制各拾取对象，利用几何处理器判断当前图元是否位于选择框内部，如果判断结果为是，则利用变换反馈将图元信息输出到回馈缓存中，否则遗弃当前图元；应用程序端负责场景的组织、绘制顺序的控制，以及为顶点处理器和几何处理器提供拾取需要的属性参数。

(4)     关闭变换反馈，查询反馈结果，处理和获取拾取信息。

所述的基于GPU的三维几何图元块拾取方法，其特征在于，在所述步骤(3)中，绘制各拾取对象时GPU端顶点处理器要对输入顶点进行坐标变换，变换到裁剪坐标系下，如果需要获取拾取到的图元的其他坐标系下坐标，则在顶点处理器中进行计算并传给几何处理器。

所述的基于GPU的三维几何图元块拾取方法，其特征在于，绘制各拾取对象时GPU端几何处理器要进行以下处理：

(1)     定义输入输出图元类型，输入图元可能为三角形、线段或点，每个命中图元只产生一套属性输出，即输出图元类型设为点；

(2)     根据需要定义输出到回馈缓存的属性(例如图元所属对象的ID、父对象ID、图元顶点世界坐标等等)；

(3)     将输入的裁剪坐标系下的图元顶点坐标通过透视相除转换到规范化设备坐标系下； 

(4)     通过取图元顶点的前两维坐标，得到规范化设备坐标系下投影平面上的二维图元坐标，然后判断图元是否在鼠标选择框内部；

(5)     如果图元在鼠标选择框内部，则设置并输出拾取信息到回馈缓存；如果鼠标位置在图元外部，则遗弃当前图元，不做输出。

所述的基于GPU的三维几何图元块拾取方法，其特征在于，在所述绘制各拾取对象时GPU端几何处理器进行处理的步骤(4)中，判断图元是否在鼠标选择框内部的方法是：不考虑线宽和点尺寸的影响，当图元全部顶点位于选择框内，即判定命中。

与现有技术相比，本发明的有益效果是：

本发明借助几何处理器在投影后的二维平面上进行拾取的命中判定，并借助回馈缓存将拾取信息返回应用程序，既适用于单体拾取，也适用于块拾取。二维的命中判定较三维的射线相交测试计算量小，因此更高效快捷；进行拾取绘制时，无需进行光栅化和片元处理，节省了处理时间；同时可以获取到丰富的拾取信息，如对象ID、父对象ID、深度信息、图元坐标信息等等；整个拾取过程在GPU上完成，满足了包含大量几何图元的图形应用中的实时交互需求。

 

【附图说明】

图1为支持Shader Model 4.0的GPU的可编程图形流水线示意图；

图2为本发明拾取绘制流程示意图；

图3为用于拾取绘制的几何处理器程序流程；

图4为判断拾取点是否在三角形图元内部的示意图；

图5为判断拾取点是否在线段图元内部的示意图；

图6为判断拾取点是否在点图元内部的示意图；

图7为对三角形图元内部的拾取点进行深度插值的示意图。

 

【具体实施方式】

下面结合附图和具体实施方式对本发明作进一步详细描述：

本发明技术方案的实施需要Shader Model 4.0及以上版本GPU的支持。

图1为支持Shader Model 4.0的GPU的可编程图形流水线示意图，其中顶点处理器、几何处理器和片元处理器为可编程的。顶点处理器处理的对象是顶点，主要用于决定顶点位置等属性；几何处理器的处理对象是图元，在此处理器中可获取到顶点处理器传递过来的图元各顶点信息，由于本发明对图元进行拾取需要图元的完整信息，因此主要判定过程在此处理器中完成，变换反馈可将几何处理器输出的图元顶点属性输出到反馈缓存中，从而将拾取信息返回给应用程序；片元处理器的处理对象是片元，主要用于决定片元的颜色等属性，由于片元数远大于顶点数，其工作量通常远大于顶点处理，本发明在进行拾取绘制时禁用了无需用到的光栅化及其后的片元处理等流水线阶段，有助于提高效率。

图2为本发明拾取绘制流程示意图。下面结合图2对单体拾取的具体实施方案进行说明：

1、在拾取时禁用了光栅化(OpenGL中通过glEnable(GL_ RASTERIZER_DISCARD))，因此在图2中未出现光栅化、片元处理等流水线阶段。

2、拾取对象的顶点数据存放在GPU端的顶点缓存中，以利于绘制时能高速访问。

3、绘制各拾取对象时，应用程序端进行如下处理：

(1)     场景的组织及绘制顺序的控制：对于复杂场景，可按照深度顺序绘制各拾取对象，以简化拾取信息的处理，并可利用场景分割和提前裁剪进一步提高拾取绘制的效率；

(2)     将鼠标位置或鼠标选择框信息进行坐标转换后传入几何处理器。当进行块拾取、或者是进行单体拾取且拾取图元是三角形时，将鼠标位置由窗口设备坐标系转换到规范化设备坐标系下，方法如下：

ptX = ((x - viewportX) / viewportWidth - 0.5) * 2;

ptY = ((viewportHeight - 1 - y - viewportY) / viewportHeight - 0.5) * 2;

其中ptX和ptY是转换后的鼠标位置，x和y是窗口设备坐标系下的鼠标位置，viewportX和viewportY是窗口坐标系下视口左下角位置，viewportWidth和viewportHeight为视口的宽度和高度。而当进行单体拾取且拾取图元是点或线段时，则将鼠标位置由窗口设备坐标系转换到视口坐标系下，方法如下：

ptX = x - viewportX;

ptY = viewportHeight - 1 - y - viewportY;

如果是进行单体拾取且拾取图元是线段或者点，则还需将视口信息(将顶点坐标变换到视口坐标系下时需要)、线宽或点尺寸等拾取所需要的信息也传进几何处理器；

(3)     在绘制各拾取对象前，设置对象的变换矩阵并传进顶点处理器，这些变换矩阵与常规绘制时一致，以保证拾取绘制时各对象的位置不变；

(4)     在绘制各拾取对象前，将各对象的ID传进几何处理器，也可根据需要将其父对象ID等信息传进几何处理器。

4、绘制各拾取对象时顶点处理器主要对输入顶点进行模型变换、观察变换和投影变换，变换到裁剪坐标系下。如果需要获取拾取到的图元的世界坐标系或模型坐标系下坐标，则在顶点处理器中计算相应坐标系下顶点坐标并传给几何处理器。上述各种变换的矩阵与常规绘制时一致。

5、在进行拾取绘制时，几何处理器的程序流程如图3所示，具体阐述如下：

(1) 输入图元类型根据实际情况可设置为三角形、线段或点，绝大多数应用中为三角形；每个命中图元只产生一套拾取信息输出，即输出图元类型是点。

(2) 输入变量包括鼠标位置或鼠标选择框信息，根据所需拾取信息设置的输入变量(例如对象ID、父对象ID、世界坐标系顶点坐标等等)，如果是进行单体拾取且输入图元类型是线段或点，则还包括视口信息及线段宽度或点的尺寸；输出变量即输出到回馈缓存的属性，一般要有图元所属对象的ID，根据需要还可包括父对象ID、与鼠标对象位置深度(进行单体拾取时)、拾取到图元的顶点的世界坐标等等。

(3) 通过透视相除即可将顶点坐标从裁剪坐标系转换到规范化设备坐标系(坐标范围在-1到1之间)；如果是进行单体拾取且输入图元类型是线段或点，由于线宽和点尺寸是以像素为单位，命中判定最好在视口坐标系下进行，因此进一步将顶点坐标变换到视口坐标系，方法如下：

P.xy = (P.xy + 1) * viewportHalfSize;

P为顶点坐标(三维向量)，等式右边的P为规范化设备坐标系下顶点坐标，左边的P为视口坐标系下顶点坐标，viewportHalfSize为二维向量，保存有视口的宽度和高度的一半；仅对顶点坐标前两维进行变换，因为进行拾取的命中判定是二维的。

(4) 对投影平面上的二维图元进行命中判定是几何处理器程序的核心。当进行单体拾取时，目标是判断拾取点(鼠标位置)是否位于当前图元内部；当进行块拾取时，目标是判断当前图元是否位于鼠标选择框内部。

判断鼠标位置是否在二维图元内部的方法是：

1) 如果输入图元是三角形，则沿逆时针绕向访问图元各顶点，针对每一顶点计算从当前顶点指向下一顶点的边向量及从当前顶点指向拾取点的向量，通过判断此二向量的叉乘结果的z坐标符号可知拾取点在边的左边(z >= 0)还是右边(z < 0)，如果拾取点在三条边向量的左边即可判定拾取点在三角形内部，否则即在外部。图4给出了判断拾取点是否在三角形内部的示意图，对应GLSL源码如下：

/* 判断鼠标位置是否在三角形内 */

// 计算逆时针绕向的三条边向量

vec3 AB = vec3((B - A).xy, 0);

vec3 BC = vec3((C - B).xy, 0);

vec3 CA = vec3((A - C).xy, 0);

// 计算从顶点指向拾取点的向量

vec3 AM = vec3(ptMouse - A.xy, 0);

vec3 BM = vec3(ptMouse - B.xy, 0);

vec3 CM = vec3(ptMouse - C.xy, 0);

// 计算叉乘

vec3 CrossA = cross(AB, AM);

vec3 CrossB = cross(BC, BM);

vec3 CrossC = cross(CA, CM);

// 叉乘结果z值均大于等于0

if(CrossA.z >= 0 && CrossB.z >=0 && CrossC.z >= 0){

// 输出拾取信息

……

}

2) 如果输入图元是线段，需要考虑到线宽的存在，首先计算拾取点到线段的距离，如果距离小于等于线宽的一半，则进一步考察以线段为底边、拾取点为顶部点的三角形的两个底角是否都不是钝角，是则拾取点在线段上，上述条件有一个不满足则在线段外。如图5所示，拾取点M到线段AB的距离可以利用向量AM与归一化的向量AB的叉乘结果得到，而两底角是否为钝角可通过其余弦值的符号判断，余弦值可利用向量点积获得。GLSL源码如下：

/*判断鼠标位置是否在线段上*/

// 计算鼠标位置到线段的距离

vec3 NormalizedAB = vec3(normalize((B - A).xy), 0);

vec3 AM = vec3(ptMouse - A.xy, 0);

float dist = abs(cross(AM, NormalizedAB).z);

if(dist <= halfLineWidth){

// 判断以AB为底M为顶的三角形的两底角的余弦值是否不小于0

float cosBAM = dot(NormalizedAB.xy, AM.xy);

vec2 BM = ptMouse - B.xy;

float cosABM = dot(BM, -NormalizedAB.xy);

if(cosBAM >= 0 && cosABM >= 0){

// 输出拾取信息

……

}

3）如果输入图元是点，如图6所示，对于默认的方形点，根据拾取点到点图元顶点的横向和纵向距离与点尺寸的关系判定，对应GLSL源码：

/*判断鼠标位置是否在方形点上*/

// 计算鼠标位置到点的水平和垂直距离

float distX = abs(ptMouse.x - A.x);

float distY = abs(ptMouse.y - A.y);

if(distX <= halfSize && distY <= halfSize){

// 输出拾取信息

……

}

而对于反走样的圆形点，直接根据拾取点到点图元顶点的距离与点尺寸的关系判定，对应GLSL源码：

/*判断鼠标位置是否在圆形点上*/

// 计算鼠标位置到点的距离

float dist = distance(ptMouse, A.xy);

if(dist <= halfSize){

// 输出拾取信息

……

}

当进行块拾取时，图元位于选择框内部有两种情况：一种是图元全部位于选择框内部；另一种是图元有部分位于选择框内部。全部位于内部时判定命中更适合拾取目标是图元的情况，而部分位于内部时即判定命中更适合拾取目标是图元所属对象的情况。本发明采用的是前者，这样拾取更简单高效，由于图元都是凸的，仅需判定图元顶点是否都在选择框内即可，此判定不考虑线宽、点尺寸因素，全部在规范化设备坐标系下完成。此种方法也可用于拾取图元所属对象，只是可能丧失一些精度。

(5) 在为输出属性赋值时，所属对象ID及其父对象ID、图元顶点世界坐标等直接由输入变量得到，而对于单体拾取，拾取点的深度属性根据图元顶点的深度线性插值得到：

1) 对于三角形图元，如图7所示，拾取点M的深度可根据三个顶点A、B、C的深度值进行线性插值得到，插值系数分别为三角形MBC、MCA、MAB的面积占三角形ABC面积的比重，三角形的面积可以利用叉乘得到，相应的GLSL源码如下：

// 计算深度插值并输出

float AreaMBC = abs(CrossB.z);

float AreaMCA = abs(CrossC.z);

float AreaMAB = abs(CrossA.z);

depth = dot(vec3(A.z, B.z, C.z), 

    vec3(AreaMBC, AreaMCA, AreaMAB)) 

    / (AreaMBC + AreaMCA + AreaMAB);

其中CrossA、CrossB、CrossC的计算可参见前面图4对应的GLSL源码；

2) 对于线段图元，由拾取点做关于线段的垂线，将拾取点的深度等同于垂足的深度，根据两线段端点的深度线性插值得到；

3) 对于点图元，拾取点深度直接等同于点的深度。

6、在拾取绘制完成后，拾取结果已位于回馈缓存中，将其映射到应用程序内存中，即可处理和获取到拾取信息。处理拾取信息时，主要做的工作如下：

1) 合并：将缓存中属于同一个对象(ID相同)的图元产生的命中记录进行合并，由于在绘制时是逐个对象绘制的，属于相同对象的命中记录在缓存中是连续的。如果拾取目标是图元，则无需进行合并；

2) 排序：根据深度从小到大顺序对不同对象的记录进行排序。如果在绘制时已经是按照深度顺序进行绘制的，则可不必进行排序。

对于块拾取，本发明的方案框架也可实现当图元有部分位于选择框内部时即判定命中，需要在判定时引入二维裁剪算法，复杂度有一定增加。

在进行块拾取且拾取目标是三角形图元时，如果需要只拾取正面朝向屏幕的图元，可在几何处理器中加上正反面判定：通过三角形法线的z值符号判断其朝向。

此外，三维几何图元的拾取方法也可用于拾取二维几何图元。

本发明中的拾取方法高效快捷、能获取多种信息、灵活性强，具有良好的应用前景，可应用到各种交互式图形应用中，例如CAD系统、游戏、UI、虚拟现实应用等。本发明中的单体拾取方法适用面广，而块拾取方法尤其适合需要对拾取图元进行交互操作的几何模型造型系统中。