Web3D引擎中三维图形对象拾取的算法与实现

陈 煜 ， 林 玮

（1.南京工业职业技术学院，江苏 南京210046；2.南京航空航天大学，江苏 南京 210016；3.南京乐游游软件科技有限公司，江苏 南京 210000）

近年来虚拟现实技术的迅猛发展，以及计算机计算能力的提高，使3D技术得到了很大的发展，已经出现了几十种之多，常见的有：cult3D，Pulse3D，ShockWave3D等[1-3]。这些引擎具有三维效果逼真的优点，然而应用于Web时，会出现下载速度慢以及需要额外下载插件等问题。idx3D，3DzzD等开源引擎采用JAVA技术，此类引擎具有不需要特殊硬件实现3D效果，用户在使用时也不需额外下载插件等优越性。由于在互联网上要实现三维图形的展示以及漫游等功能，三维图形对象的拾取功能必不可少。但是，目前这些引擎均未实现对特定对象的拾取功能，这就大大限制了人机交互的实现。

本文提出了射线分层次求交算法，首先采用包围盒算法来实现对选择对象的快速拾取，然后，为解决包围盒求交时过分拾取的问题，采用三角形算法来实现对对象的准确拾取。在提出算法的基础上，实现了用JAVA语言，在开源Web3D引擎 idx3D上对所选图形对象的拾取功能的开发。

1 图形的三维显示和拾取的基本原理

1.1 图形在屏幕上的三维显示

要将现实世界的物体以立体的视觉效果在计算机显示器上显示出来，需要进行渲染管线的处理[4-6]。通常需要先建立3D场景以及设置虚拟摄像机，根据摄像机所能看到的图形效果，将整个场景转换成2D的图像显示在显示器上，这个过程就是渲染管线。其流程如图1所示。本地空间可以方便各物体的建模，在建模后，需要将各物体的自身坐标变换成统一的世界空间下的世界坐标。将虚拟摄像机移至世界坐标的原点时，则形成了视图空间，此时各物体的坐标也需变换形成视图空间坐标，这个过程为视图空间变换。在视图空间中把3D场景转化为2D图像，这一过程被称为投影。投影可分为平行投影和透视投影[4]，而透视投影又可分为一点透视，二点透视和三点透视，在图形学中一点透视投影被广泛使用。将投影空间中通过透视形成的视锥体或称平头截体，进行规格化，也就是简化成立方体，则形成图像空间。在此，为了简化问题，将图像空间并入投影空间。视口是屏幕上一个矩形区域，视口变换就是把投影窗口变换为视口。3D物体的模型是由若干个三角形堆砌而成，将这些三角形的每个顶点转换到屏幕上就形成了2D图像，这个过程被称为光栅化。

1.2 拾取的基本原理

无论是在虚拟现实、动漫制作还是工业设计等领域，拾取的过程可以看成是渲染的逆运算。比较通用的基本原理[5-10]大多可以归纳为如下步骤：

图1 三维图形的显示过程

（1）将屏幕上鼠标点击点的二维坐标，转化为投影空间内的三维坐标。

（2）再将此三维坐标进行转换至视图空间，设这个点为P1。从虚拟摄像机的所在位置，即视图空间的原点到 P1就是视图空间下的射线，此时的P1表示有方向的向量。

（3）然后，再将视图空间中的射线，变换到世界空间中，射线可表示为P (t ) = P0+ tP1。该变换由视图变换的逆运算来完成。

（4）将各对象由包围体包围起来，射线与包围体求交，若相交则表示该图形被拾取。

2 拾取算法

在1.2节中介绍的方法基础上，本文结合Web3D引擎的特点，提出并实现了射线的分层次求交算法来提高拾取的效率。在 Web3D中三维图形的模型是用三角形网格来描述的[7]，也就是说一个三维图形的模型是由若干个三角形堆砌而成的。所谓的分层次求交算法的思想是：第一步，先以尽量少的计算量确定可能的拾取对象，本文提出射线与包围盒求交法以快速确定拾取范围。由于各三维图形的形状往往并不规则，在包围盒的范围内，有些点并不属于图形对象，作者称这种现象为过度拾取。为了解决过度拾取的问题，第二步，在包围盒的范围内，遍历三角形，将射线与三角形求交，以此来精确拾取图形。

2.1 获得射线的矢量

要进行拾取，首先要获得射线的矢量。图2是相同的点在不同空间中的示意图。左图中的鼠标点击点M (x, y)，在投影空间中所对应的点为中图内的点 proj, 该点在视图空间中对应的点为view, view为在近裁剪面上的点。视图空间中的原点，和屏幕空间上鼠标点在视图空间内的对应点构成视图空间下的射线，为实现拾取功能，还需将射线变换至世界空间下。要获得射线要进行以下的一系列变换：

图2 鼠标点在各空间中的对应示意图

（1）屏幕上鼠标点的坐标转换至投影空间的坐标

具体方法为：将鼠标点的坐标转换为投影窗口也就是投影空间中近裁剪面上的坐标，再确定表示深度的Z轴的值，为计算方便取Z轴的值为0，如图2的中图所示。

屏幕的原点在左下角，而近裁剪面的原点在中心位置，又因为近裁剪面也就是投影窗口的范围为min=(-1, -1)和max=(1, 1)。根据解析几何的计算，易得变换公式为

（2）计算投影窗口上的点在视图空间的坐标。将该点与视图空间的原点相连，则可以确定视图空间内的射线。

投影窗口上的点在视图空间的坐标，是通过透视投影将平截头体转换到视图空间的逆运算。因此，需要了解透视投影以及投影空间和视图空间的变换关系。图3描述了平截头体从视图空间至投影空间的变换关系。投影空间中原点为平截头体规格化的立方体的前平面的中心。左图为视图空间，右图为投影空间。

式(2)是投影变换矩阵[11]，其中各变量的含义如式(3)所示。Zn和fov的含义如图4所示，Zn是原点至近裁剪面的距离，fov表示视图空间中原点与近裁剪面高度的夹角。screenWidth和screenHeight分别为屏幕的宽度和高度，Zf为原点至远裁剪面的距离。

图3 视图空间至投影空间的变换关系

图4 平截头体在视图空间中的投影示意图

根据投影空间和视图空间的变换，易得投影空间中的点proj和视图空间中的点view有下式的关系

其中 proj_x, proj_ y, proj_z分别为点proj在x, y和z轴上的坐标，同理view_x , view_ y, view_z分别为点view在x, y和z轴上的坐标。在此采用齐次坐标表示法来表示投影空间中的点和视图空间中的点的对应关系。所谓齐次坐标表示法[6]是指用n+1维向量来表示n维向量的方法。这种方法便于表达平移，旋转以及缩放等变换。

由式(4)可得下式

（3）计算视图空间中这条射线的方向矢量，该方向矢量用view_dir表示。

参照图4，由式(5)，易得射线方向矢量的各分量计算公式如下

（4）计算射线在世界空间下的向量。对世界空间转换到视图空间的矩阵求逆，可得视图空间转换到世界空间的矩阵

Vworldspace为世界空间下的向量，Vviewspace为视图空间下的向量，为视图空间转换到世界空间的矩阵。

根据式(6)可以分别计算射线顶点和方向在世界空间下的向量。

2.2 射线与包围盒求交的算法

包围体的类型主要有轴对齐包围盒（Axis-Aligned Bounding Box，简称AABB），包围球(Sphere)，方向包围盒（Oriented Bounding Box，简称 OBB）等[12]。作者采用了 AABB包围盒。AABB包围盒的建立以及射线与包围盒求交的算法如下：

（1）从三维图形的模型得到在x, y, z轴各方向的最大绝对值，以此来确定包围盒的8个顶点的本地空间坐标。

（2）将包围盒的本地空间坐标转换到世界空间，得到包围盒各顶点的世界坐标。

（3）将射线转换到世界坐标。

（4）射线分别对包围盒的6个面求交，射线的点落在包围盒的某一个面的范围内时，判断射线与包围盒相交。为了提高计算的速度，在6个面中，计算出任意一个面相交后就可以停止计算。

在确定了相交的包围盒后，进入到下一个阶段：射线与包围盒中三维图形模型的各三角形求交的计算。如果没有与射线相交的包围盒，则没有要拾取的对象。

2.3 射线与三角形求交的算法

Web3D中的各三维图形的模型都是由三角形堆砌而成的，对射线与三角形求交可以精准地拾取目标图形。如果射线落在某一个三角形内则可以确定该三角形所在的图形为拾取的对象，示意图如图5所示。这是一个三角形线性插值的问题，具体的演算如下：

设射线原点为P0，射线方向为Dir；三角形三个顶点为 V0，V1，V2；t ，u ，v分别为标量。假设射线与三角形相交，则交点为

这是一个齐次线性方程组，若有解则行列式[-Dir，V1-V0，V2-V0]不为0。根据t，u，v的含义，易得，当t >0, 0< u <1, 0< v <1, 0< u +v <1时该交点在三角形内部，根据线性代数中的克莱姆法则，可知：射线原点到相交点的距离 t，以及交点的坐标( u，v)。

图5 射线与三角形相交的示意图

3 拾取的实现

3.1 idx3D引擎简介

idx3D是一款开源的Web3D引擎，基本实现了渲染管线，也就是将3D模型转换成屏幕上的有立体视觉的2D图形的基本流程。由于该引擎是由JAVA语言编写的，利用其开发的系统有如下优点：

（1）在Web浏览器上运行时，用户不需下载特殊插件；

（2）不依赖于硬件也就是显卡可以实现3D效果。

由于这种基于JAVA开发的Web3D引擎对于Web3D技术的实用化和普及化具有积极的意义，有必要探讨其功能的扩展。idx3D具有简单的3D渲染框架，有利于将精力集中在拾取功能的实现上，非常适合于将所研究的算法在此引擎上实现。

3.2 具体实现

3.2.1 拾取的流程

拾取算法的流程图如图6所示，实现拾取的过程如下：首先，在图形程序窗口，设鼠标点击点为 posMouse(x, y)，该点为平面上的点。得到该点的坐标后，将该鼠标点逐步转换为投影空间中的三维坐标，再转换为视图空间坐标，至此可以得到视图空间中的射线，然后将射线转换至世界空间中。接下来进入对拾取目标的判断。一个三维图形对应一个包围盒，此处为一个循环结构，boxCnt为包围盒的个数。射线对包围盒逐个求交，直至得到相交的包围盒，或者找不到相交包围盒而结束循环。对包围盒求交的方法是，计算射线与一个包围盒的各个面是否相交，也就是计算射线是否在包围盒的某一个面的范围内，SURCNT为包围盒的面的个数即6。当确定了与射线相交的包围盒后，由于包围盒的范围内有一部分是不属于对象图形的，也就是产生了过度拾取的问题。这时，需要对包围盒内图元的各个三角形与射线求交，此处也是一个循环结构，如果计算出与射线相交的三角形，则可以确定该三角形所属的图形即为所要拾取的图形，否则对任何图形不做拾取处理，triCnt为三角形的个数。

3.2.2 代码的实现

为实现拾取功能，在idx3D引擎的基础上，主要建立了以下各类，并在相应类中定义了实现算法的属性和方法。实现拾取的类图见图7。

（1）拾取器Picker类的建立主要定义了以下各拾取方法：

1）定义了拾取对象的方法：ObjectPicking-Result类型的 pickObject (Scene scene, Vector mousePos, Object model, boolean returnAt1stTime)方法。

2）定义了拾取对象包围盒的方法：AABBPickingResult 类型的 pickAABB(Camera camera, Vector mousePos, Vector min, Vector max)方法。

3）定义了拾取对象三角形的方法：TrianglePickingResult 类 型 的 pickTriangle(Camera camera, Vector mousePos, Vector v0,Vector v1, Vector v2)方法。

（2）计算屏幕上的点到视图空间中的点的转换过程，并由此生成射线，再将射线转换至世界空间坐标下。

在Camera.java中定义了getScreenToWorldRay(Vector screenPos)方法进行如下计算：

1）计算屏幕上鼠标点在标准投影空间中近裁剪面上的坐标；

2）调用getProjectionMatrix( )方法获得投影变换矩阵，计算投影点在视图空间下的坐标；

3）计算视图空间下射线的方向；

4）调用getViewMatrix( )方法获得世界空间至视图空间的转换矩阵，再求逆矩阵。计算世界空间中的射线。

（3）射线Ray类的建立

1）定义射线是一个有起点和方向的三维空间中的向量；

2）定义了拾取对象包围盒的方法：IntersectionResult类型的 intersects(AABB box )方法。由于包围盒在碰撞，场景管理以及特效等方面都需要用到，因此与射线求交的方法定义在Ray类中，以方便后续功能的扩展。

（4）包围盒AABB类的建立

用min和max两个三维向量来表示图形对象包围盒的范围。这两个点分别是在本地空间中的左下前点和右上后点，前者的x, y, z轴的坐标均为最小值，后者的x, y, z轴的坐标均为最大值。其他各顶点的坐标值均可以通过min和max两点坐标值的正负计算而获得。

定义了对该包围盒进行变换的方法。包围盒是对象图形在本地空间中建立起来的，需要对其进行相应的至其他空间的变换。

图6 拾取算法流程图

图7 实现拾取的类图

3.3 案 例

采用实现了图形拾取功能的 Web3D引擎，开发出如图8和图9所示的演示案例。图中的茶壶为可旋转、缩放的三维图形，当光标在茶壶以外的位置时，如图8所示，鼠标的标记为小箭头，茶壶的颜色不变，也就是图形没有被拾取。当光标移至茶壶上时，如图9所示，鼠标的标记变为小手形状，茶壶变为红色，表明该对象被拾取。

该案例开发的流程如下：

（1）采用3DSMax为茶壶建模；

（2）构造场景；

（3）加入材质和灯光；

（4）将模型文件导入程序中；

（5）重构场景，以及场景规格化；

（6）初始化渲染状态；

（7）设置旋转矩阵，实现整体平移，缩放和旋转，以及单体平移，缩放和旋转；

（8）进行渲染得到有三维效果的图形；

（9）在MouseMove（）中调用拾取功能实现图9所显示的拾取全过程。

图8 未拾取的运行结果

图9 拾取的运行结果

4 结 论

本文根据 Web3D引擎的特点在射线拾取的基础上，提出了分层次射线求交算法，并在实际的 Web3D引擎上实现了该算法。通过实际案例验证了可以高效地实现对三维图形的拾取功能。在程序中实现的射线，AABB包围盒以及三角形等部分，为后续的碰撞检测算法的实现奠定了基础。

[1]罗立宏, 谭夏梅. 几种 Web3D技术及比较[J]. 甘肃科技, 2007, (5): 60-63.

[2]朱珊虹, 李 彦. 几种 Web3D 技术的比较研究[J].内江科技, 2010, (4): 117.

[3]罗立宏, 谭夏梅. 基于ShockWave3D的Web虚拟现实技术研究[J]. 科技资讯, 2007, (4): 101-102.

[4]李春雨, 等. 计算机图形学及实用编程技术[M]. 北京: 北京航空航天大学出版社, 2009: 73-94.

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

[6]孙家广, 等. 计算机图形学(第3版)[M]. 北京: 清华大学出版社, 1998: 358-390.

[7][美]Steve Cunningham. 计算机图形学[M]. 石教英,潘志庚译. 北京: 机械工业出版社, 2008: 83-85.

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

[9]张嘉华, 等. GPU 三维图元拾取[J]. 工程图学学报,2009, 30(1): 46-52.

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

[11]Transforms变换[Z]. http://www.gesoftfactory.com/developer/Transform.htm#_世界变换

[12]王晓荣, 王 萌, 李春贵. 基于AABB包围盒的碰撞检测算法的研究[J]. 计算机工程与科学, 2010,32(4): 59-61.