一种基于位置关系判定的GPU三维几何图元拾取方法

邹 昆， 沃 焱， 李文生

(1. 电子科技大学中山学院计算机学院，广东 中山 528402；2. 华南理工大学计算机科学与工程学院，广东 广州 510006)

一种基于位置关系判定的GPU三维几何图元拾取方法

邹 昆1， 沃 焱2， 李文生1

(1. 电子科技大学中山学院计算机学院，广东 中山 528402；2. 华南理工大学计算机科学与工程学院，广东 广州 510006)

针对交互式图形应用对拾取在效率、适用范围和拾取信息方面的需求，提出一种新的基于GPU的三维几何图元拾取方法。在进行拾取绘制时关闭光栅化，将鼠标位置信息和图元顶点坐标变换到规范化设备坐标系，通过在几何处理器中判断投影后的二维图元与鼠标或选择框的位置关系进行命中判定，并利用变换反馈将拾取信息返回应用程序。在提出方法的基础上，介绍了单体拾取和块拾取的OpenGL实现。实验表明，该方法的单体拾取效率较基于GPU的射线相交法有约10%的提升，同时能支持高效块拾取。

计算机应用；几何图元拾取；GPU；三维交互

图形拾取技术是交互式图形应用的关键技术之一，在CAD软件、游戏、图形用户界面等方面有着广泛应用。随着图形技术和图形硬件的快速发展，交互式图形应用中三维场景的复杂度越来越高，这对拾取方法的高效性提出了更高的要求。此外，在功能方面图形应用对拾取的需求是多样化的：有的只需要单体拾取，而有的还需要支持块拾取；有的只需要获取到拾取对象的ID，而有的还需要获取拾取到的三角形的顶点坐标、拾取点的深度信息等等。这要求拾取方法适用范围广，拾取信息丰富。

随着现代GPU的迅速发展，GPU的并行处理能力以超摩尔定律的速度发展着，在并行处理方面较CPU有着绝对优势，同时GPU的可编程能力越来越强，灵活性越来越高。ShaderModel4.0的GPU上已可进行3个阶段(vertexShader、geometryShader和fragmentShader)的GPU编程。编程能力的增强使得可以实时实现更多的图形特效，同时也能利用GPU进行更广泛的通用计算。

针对交互式图形应用中对拾取在效率、适用范围和拾取信息方面的需求，通过将 GPU用于通用计算目的而非渲染目的，充分利用现代 GPU的并行处理能力、可编程性及灵活性，提出一种可在大量几何图元中快速拾取目标图元或图元集合，并能获取丰富拾取信息的方法。该方法通过在几何处理器(geometryShader)中判断投影后的二维图元与鼠标位置或选择框的关系进行命中判定，并利用变换反馈(transform feedback)将拾取结果返回应用程序。实验表明，该方法既适用于单体拾取，也适用于块拾取，并可获取到丰富的拾取信息，且过程高效。

1 相关方法

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

该方法的缺点是：①频繁的堆栈压入与弹出操作会严重影响拾取效率[3]；②当场景中含有大量几何图元时名称堆栈容易溢出[3]；③得不到命中图元的顶点坐标等信息。

(2) 射线相交测试法。射线相交测试法[2,4-7]将鼠标点从屏幕坐标系逆变换到世界坐标系得到投影点，然后将从视点指向投影点的射线与场景中的各几何图元在世界坐标系下进行相交测试，找出被选中的物体。其步骤如下[7]：①获得屏幕上鼠标点击的点，找到其对应的投影窗口上的点p；②计算拾取射线，即一条从原点出发穿过点p的射线；③将射线乘以投影矩阵和观察矩阵级联后矩阵的转置逆矩阵，变换到和模型相同的坐标系中；④判定射线和物体是否相交，如相交则该物体有被拾取到，对于有多个物体与射线相交的情况，可根据深度信息判定拾取到的物体。

当场景中含有大量图元时，逐三角形求交效率较低。王剑等[4]和郭艳霞等[5]采用将射线与包围盒求交的方法提高效率。陈煜和林玮[6]采用了分层求交的思想，先用包围盒求交实现快速拾取，再用三角形求交提高拾取精度。张嘉华等[7]则利用GPU的几何处理器对射线相交拾取进行提速。

射线相交测试法能够得到更精确的拾取信息，但用于块拾取时，需要用多条射线进行相交测试，计算量太大[3]。

(3) 基于离屏渲染的拾取方法。此类方法[3,7-8]将图形对象ID等信息编码为颜色，在进行拾取时将不同对象以不同颜色绘制到离屏缓存中，绘制完成后根据鼠标位置读取离屏缓存中相应位置像素的颜色值，进行解码从而获得拾取到的物体信息。

此方法有以下缺点：①需要额外进行一次完整的绘制，速度较GPU上实现的射线相交法要慢[7]；②信息编码容量受到离屏缓存位深的限制；③只能拾取到位于最前方的对象，获取到的拾取信息也非常有限。

除上述3种常见方法外，何健鹰等[9]提出了一种不同的拾取方法：将三角形图元变换到屏幕坐标系后，通过判断鼠标点和三角形的位置关系来进行拾取。此方法与本文提出的方法有一定相似性，但该方法面向的是三维地形图上的任意点拾取，且未讨论块拾取，也并未利用GPU实现。

2 基于GPU的拾取框架

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

图1 支持ShaderModel4.0的GPU图形流水线示意图

拾取方法的基本思想是，在拾取时进行一次额外的绘制，将鼠标位置信息和图元顶点坐标变换到规范化设备坐标系，利用几何处理器判断投影后的二维图元与鼠标位置或选择框的关系，并利用变换反馈将拾取信息返回应用程序。

图2 拾取绘制流程示意图

图2给出了拾取绘制流程的示意图。在拾取时禁用了光栅化，因此在图中未出现光栅化、片元处理等流水线阶段。拾取对象的顶点数据存放在GPU端的顶点缓存中，以利于绘制时能高速访问。顶点处理器负责对输入顶点进行模型变换、观察变换和投影变换，变换到裁剪坐标系下，如果需要获取所拾取到图元的世界坐标系或模型坐标系下坐标，则在顶点处理器中计算相应坐标系下顶点坐标并传给几何处理器。几何处理器主要负责判断当前图元是否被拾取到，是则输出拾取信息到回馈缓存，否则遗弃当前图元，具体步骤见图3。应用程序端负责场景的组织、绘制顺序的控制以及为顶点处理器和几何处理器提供拾取需要的属性参数。

下面分别针对单体拾取和块拾取对拾取方法进行详细描述，并介绍其OpenGL实现。

3 拾取方法及实现

3.1 单体拾取

在进行单体拾取时，应用程序端的步骤如下：

(1) 将鼠标位置由窗口设备坐标系转换到规范化设备坐标系并传入几何处理器，方法如下：

其中，ptX和ptY是转换后的鼠标位置，x和y是窗口设备坐标系下的鼠标位置，viewportX和viewportY是窗口坐标系下视口左下角位置，viewportWidth和 viewportHeight为视口的宽度和高度。

(2) 关闭光栅化(OpenGL中通过 glEnable (GL_RASTERIZER_DISCARD))，开启变换反馈。

(3) 绘制各拾取对象。对于复杂场景，可按照深度顺序绘制各拾取对象，以简化拾取信息的处理，并可利用场景分割和提前裁剪进一步提高拾取绘制的效率。在绘制各拾取对象前：①设置对象的变换矩阵并传进顶点处理器，这些变换矩阵与常规绘制时一致，以保证拾取绘制时各对象的位置不变；②将各对象的ID传进几何处理器，也可根据需要将其父对象ID等信息传进几何处理器。

(4) 关闭变换反馈，查询反馈结果，处理和获取拾取信息。处理工作比如从回馈缓存中搜索深度值最小的图元从而拾取到最前方的图元，如果在绘制时已经是按照深度顺序进行绘制的，则无需此处理。

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

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

(1) 绝大多数应用中图元为三角形，因此输入图元类型设置为三角形；每个命中图元只产生一套拾取信息输出，因此输出图元类型设为点。

(2) 输入变量包括鼠标位置信息、远近裁剪面到视点的距离(判断图元是否在视域体外时用到)、表示当前投影类型的布尔变量，以及根据所需拾取信息设置的输入变量(例如对象ID、父对象ID、模型坐标系顶点坐标等等)；输出变量即输出到回馈缓存的属性，一般要有图元所属对象的ID，根据需要还可包括父对象ID、鼠标对应位置深度、拾取到图元的顶点坐标等等。

(3) 判断图元是否在视域体内可以快速排除一些图元，避免进行后续计算，在透视投影情况下也可保证后续的透视除法不会除以0或接近0的数而产生较大误差。如果当前图元至少有一个顶点在视域体内，则进行后续处理。

对于透视投影，判断顶点是否在视域体内方法如下：

其中，near和far分别是近、远裁剪面到视点的距离，abs为求绝对值函数，A是一图元顶点在裁剪坐标系下的坐标，而A.w实际上等于观察坐标系下的–A.z，即A.w代表的是A所在的与观察坐标系z轴垂直的平面到视点的距离。如果AIn为true，则A在视域体内，否则在视域体外。

对于正交投影，视域体的6个面正好是裁剪坐标系下的x = ±1，y = ±1和z = ±1，而顶点的w坐标为1，因此判断方法更加简单：

(4) 通过透视除法即可将顶点坐标从裁剪坐标系转换到规范化设备坐标系(坐标范围在–1到1之间)：A = A / A.w。

(5) 对投影平面上的二维图元进行命中判定是几何处理器程序的核心。对于单体拾取，目标是判断拾取点(鼠标位置)是否位于当前图元内部，此时只用到图元顶点的x、y坐标。具体方法是：沿逆时针绕向访问图元各顶点，针对每一顶点计算从当前顶点指向下一顶点的边向量及从当前顶点指向拾取点的向量，通过判断此二向量的叉乘结果的z坐标符号可知拾取点在边的左边(z≥0)还是右边(z < 0)，如果拾取点在3条边向量的左边即可判定拾取点在三角形内部，否则即在外部。对应GLSL源码如下(图4给出了三角形顶点、拾取点及相关向量的示意图)：

图4 三角形图元、拾取点及相关向量示意图

(6) 在为输出属性赋值时，所属对象ID及其父对象ID、图元顶点坐标等直接由输入变量得到，而拾取点M的深度可根据三个顶点A、B、C的深度值进行线性插值得到，插值系数分别为三角形MBC、MCA、MAB的面积占三角形ABC面积的比重，三角形的面积可以利用叉乘得到，相应的GLSL源码如下：

其中，CrossA、CrossB、CrossC的值之前进行命中判定时已得到，dot为求点积函数，深度值depth为规范化坐标系下的深度值。

(7) 在输出拾取属性到回馈缓存(使用EmitVertex())前，为了确保拾取点在视域体内，还需对拾取点的深度值depth进行一次判定：如果其值在–1到1之间则进行输出。这是因为前面只确保了有一个图元顶点在视域体内，而命中判定只确保了拾取点的投影在视域体内，有可能出现拾取点在深度方向上偏离出视域体的情况。

如果在拾取绘制时不是按照深度顺序进行绘制的，绘制完后在应用程序端还需从回馈缓存中搜索深度值最小的图元从而拾取到最前方的图元。如果拾取绘制和常规绘制的场景完全一样，也可在拾取绘制前读取鼠标位置的深度值，并传入几何处理器，在算出拾取点M的深度后，与传入的深度值进行比较来判定M是否被遮挡，这样对于复杂场景的拾取，可降低后期拾取信息处理的复杂度。

3.2 块拾取

在进行块拾取时，使用鼠标等定位设备确定一个选择框，投影后位于该选择框内的图元判定为命中。最常见的是矩形选择框，但也有应用需要任意形状选择框。而命中判定通常有2种方式：①整个图元位于选择框内则判定为命中；②图元有部分位于选择框内则判定为命中。本文方法可为采用第①种命中判定方式的块拾取提供方便高效的实现，下面对其进行详细介绍，而对于采用第②种命中判定方式的块拾取在后面给出拓展思路。

采用矩形选择框和第①种命中判定方式的块拾取方法与前面的点拾取非常相似。应用程序端的工作与单体拾取基本一致，只是传入几何处理器的不再是鼠标位置，而是选择框的坐标信息，同样是转换到规范化设备坐标系。几何处理器的程序流程同样如图3所示，但有以下不同：

(1) 判断图元是否在视域体外时，判断顶点是否在视域体内的方法与单体拾取相同，但只有当图元所有顶点都在视域体内时，才进行后续处理。

(2) 在对投影平面上的二维图元进行命中判定时更加简单，如果图元的所有顶点都在矩形框内则判定为命中。

(3) 在为输出属性赋值时，深度值可输出3个顶点的深度值，或是输出顶点平均深度值，不再需要进行插值。

(4) 在输出拾取属性到回馈缓存前，不再需要对深度值进行判定，因为前面已确保整个图元在视域体内。

如果需要仅拾取未被遮挡的图元，可以在进行拾取绘制前读取矩形选择框区域的深度值，保存为深度纹理，然后在进行拾取绘制时，在几何处理器中，在判定顶点均位于选择框内后，根据顶点相对于选择框的x、y坐标确定纹理坐标，从深度纹理采样，将采样得到的深度值与顶点深度值进行比较，如果全部顶点均被遮挡则判定为未命中，否则判定为命中。

此外，也可对命中判定进行修改，使能够支持任意形状选择框下的块拾取，其思想与单体拾取时的命中判定相似：如果沿逆时针方向访问任意形状选择框的各边，顶点A始终在各边的左边，则该顶点在选择框内，如果3个顶点都在选择框内，则该图元判定为命中。

对于第②种命中判定方式：图元有部分位于选择框内则判定为命中，可利用多边形裁剪算法(例如Sutherland-Hodgman多边形裁剪算法[10])判定图元与选择框是否相交，但由于目标是相交判断而不是获得裁剪后的多边形，可以对算法进行相应的优化，具体实现留待后续工作完成。

4 实验结果及分析

在Microsoft VisualStudio 2010环境下使用OpenGL4.3和FreeGLUT库实现了上述拾取方法，块拾取采用了矩形选择框和第①种命中判定方式：整个图元位于选择框内则判定为命中。实验使用了一个3D场景漫游程序，场景中包含地面、天空球、圆环及多个随机分布的球。实验硬件为 CPU i5-2430M(2.40 GHz双核)、4 G内存、显卡NVIDIA GeForce GT 550M(2 G显存)的笔记本。

图5给出了单体拾取的示例，在鼠标点击进行单体拾取操作后将拾取到的对象用红色线框包裹显示，并在控制台输出拾取信息，包括拾取到的三角形数量、三角形顶点模型坐标系坐标、拾取对象ID(这里拾取到第140号小球)以及鼠标拾取位置的深度值(规范化设备坐标系)。块拾取时使用鼠标按下拖动形成的矩形框来框选图元，图6给出了块拾取的示例，其中拾取到的8个地面三角形用红色线框突出显示。

图5 单体拾取示例

图6 块拾取示例

效率测试仍然使用上述场景，通过控制球的数量来调节场景的图元总数。在测试块拾取时，使用随机位置和大小的选择框。此外用OpenGL实现了在拾取速度方面具有代表性的文献[7]中基于 GPU的射线相交测试方法，进行单体拾取的对比。实验中拾取绘制时均未采取场景分割、提前裁剪等措施，也未按照深度顺序进行绘制。拾取时间取 10次拾取用时的平均值。

表1给出了实验的时间数据，从中可以看到相对于基于 GPU的射线相交法，本文单体拾取方法有约10%的性能提升，这得益于其更高效的判定过程(在几何处理器中判定一个三角形是否命中仅需3次透视除法和3次叉乘，如需计算拾取点深度再加上1次点乘和1次除法)。对于块拾取本文方法同样可以高效地完成，而射线相交法无法为块拾取提供有效的支持，如果从选择框内每一像素引发一条射线，一方面效率低，另一方面有限的射线数量会降低拾取精度，有可能造成漏拾取的情况。相对于单体拾取，本文块拾取的速度稍慢，这是因为块拾取时命中的图元数要更多，实验发现，选择框越大，拾取时间越长。本文方法拾取时间主要耗时不在拾取时的绘制，而在从回馈缓存获取拾取结果，例如对于 6 755 700个图元的情况，单体拾取平均耗时102.44Ms，其中拾取绘制平均耗时才6.69Ms。

表1 拾取时间数据

5 结 论

本文提出了一种基于 GPU的三维几何图元拾取方法，通过在 GPU几何处理器中判断投影后的二维图元与鼠标或选择框的位置关系进行命中判定。该方法既适用于单体拾取，也适用于块拾取，单体拾取相对基于GPU的射线相交法有约10%的效率提升，并且可获取到丰富的拾取信息，能较好地满足各种三维交互式图形应用的需要。

[1]SegalM, Akeley K. The OpenGL graphicsSystem: aSpecification (version 1.0) [S]. USA：Silicon Graphics Inc, 1994.

[2] 姚继权, 李晓豁. 计算机图形学人机交互中三维拾取方法的研究[J]. 工程设计学报, 2006, 13(2): 116-120.

[3] 李 胜, 汪国平. 一种在图形处理器上拾取三维几何图元的方法[P]. 中国, 200810103054.5. 2008-09-24.

[4] 王 剑, 陆国栋, 谭建荣. 三维场景中图形对象的拾取方法[J]. 机械, 2004, 31(7): 29-32.

[5] 郭艳霞, 侯彤璞, 杜园园. 基于DirectX的三维场景实体的拾取[J]. 辽宁石油化工大学学报, 2009, 29(3): 77-84.

[6] 陈 煜, 林 玮. Web3D引擎中三维图形对象拾取的算法与实现[J]. 工程图学学报, 2011, 32(6): 82-88.

[7] 张嘉华, 梁 成, 李桂清. GPU三维图元拾取[J]. 工程图学学报, 2009, 30(1):46-52.

[8] 王亚平, 余 柯, 罗 堃. 在OpenGL中一种新的拾取方法及其应用—基于对象缓冲区的选择拾取方法[J].工程图学学报, 2003, 24(2): 60-65.

[9] 何健鹰, 徐强华, 游 佳. 基于OpenGL的一种三维拾取方法[J]. 计算机工程与科学, 2006, 28(1):45-46, 70.

[10]Sutherland I E, Hodgman G W. Reentrant polygon clipping [J]. Communications of the ACM, 1974, 17(1): 32-42.

A 3D Geometric Primitive PickingMethod on GPU by Positional Relation Judgment

Zou Kun1, Wo Yan2, Li Wensheng1
(1.School of Computer Engineering, Zhongshan Institute, University of ElectronicScience and Technology of China, Zhongshan Guangdong 528402, China; 2.School of ComputerScience and Technology,South China University of Technology, Guangzhou Guangdong 510006, China)

3D geometry primitive picking is a key technique for 3D interactive graphics applications which is required to be highly efficient, widely applicable and able to obtain rich information. In order toSatisfy these requirements, a novel GPU-based 3D geometric primitive pickingMethod is proposed. The drawing for picking is conducted as follows: rasterization is first turned off, then theMouse position and coordinates of primitive vertexes are transformed to the normalized equipment coordinateSystem, and hit test isMade on the geometry processor by judging the positional relation between the 2D projected primitive and theMouse position orSelection box, at last picking results are returned to the application by utilization of transform feedback. Based on thisMethod, the OpenGL implementation ofSingle-object picking and block picking are both discussed. ExperimentsShow that the proposedMethod is about 10% faster than GPU-based ray intersectionMethod in terms ofSingle-object picking, and it canSupport efficient block picking.

computer application; geometric primitive picking; GPU; 3D interaction

TP 391.41

A

2095-302X(2015)02-0262-06

2014-07-03；定稿日期：2014-10-04

国家自然科学基金资助项目(61300095)；广东省自然科学基金资助项目(S2013010012307，S2012010010508)；广东省高等学校优秀青年教师培养计划资助项目(Yq2013206)；电子科技大学中山学院科研团队培育资助项目(412YT01)

邹 昆(1980–)，男，湖北郧西人，副教授，博士。主要研究方向为图形图像处理。E-mail：cszoukun@foxmail.com