计算几何实践2.2:3D窗口的拾取操作

2018-02-25

  在三维CAD 软件和3D游戏中,都有目标的拣选操作。通常有两种方式来实现这个功能:一是通过手工计算从屏幕发出的射线与场景内的物体求交,二是使用Vulkan/OpenGL的拾取机制(Selection Mode)。 即使是自己实现三维选择操作,也有多种方式。
  简单的拾取操作分为两类:点选和框选。点选非常简单,就是求解一条射线和场景内物体的相交。框选则需要按照投影模式分一下:平行投影模式下视景体是长方体,透视投影模式下视景体是一个平截头体(frustum)。两者的计算难度则相差较大。这些计算,本质上都是碰撞检测,和游戏中子弹射出后击中物体所需要的计算原理是相同的。
  点选时,我们需要根据相机的position和近平面上被选择的点构造一条射线。我们原来的项目中,试图把这条射线构造为一个很细的长方体,以图以此解决点选时可允许误差问题。事实证明这种方式行不通。还是简单的采用第三方lib。
  框选时,我们需构造cuboid或frustum来对场景中已有的triangle、cuboid、sphere或任意形状的物体做相交检测。这里必须要对已有的物体做包围盒了,包围盒能减少一两个数量级的计算量。如果物体没有旋转,采用最简单的OBB即可。用上lib,我们很快就能完成开发任务。
  我推荐的一个C++算法lib是 Geometric Tools,其作者也是Geometric Tools for Computer Graphics一书的作者。代码接口很简单明了。
  关于OpenGL/Vulkan拾取,我想这部分应该难一些。因为如果在CAD应用中,我们一般使用3D空间物体相交测试这样纯几何的方式来做,非常清晰明了,只不过要实现几何算法比较困难,但是对于整体过程,理解起来很容易。但是在游戏中,我们不期待高精度,却很期待尽量少的使用CPU,所以会采取比较tricky、dirty的方法。原理也非常简单。我们选择时,一定会鼠标单击,此时进入选择渲染模式,渲染每一个物体的时候,可以给整个物体指定单一颜色,那么这一帧图像和正常帧就会很不同,我们读取某一个像素的颜色值,就能够知道这个颜色对应的物体了。这种算法也有限制,如物体的个数,不支持物体重叠等。链接8给出的例子代码很有代表性。而且,这种选择方式,还需要修改显示代码的逻辑,容易出错。如果我们做CAD类型项目,完全不需要这样极端的优化方式。
  还有的需求如选择是否可穿透。根据穿透的意义不同,也有对应的算法。或者自定义选择区域形状,这些是软件自身制定的规则了,需要自己特殊处理。

  1. 《Visual C++  CAD 应用程序开发技术》
  2. 《3D 游戏引擎设计》
  3. https://lwjglgamedev.gitbooks.io/3d-game-development-with-lwjgl/content/chapter23/chapter23.html
  4. http://schabby.de/picking-opengl-ray-tracing/
  5. http://www.opengl-tutorial.org/cn/miscellaneous/clicking-on-objects/picking-with-a-physics-library/
  6. http://away3d.com/tutorials/Introduction_to_Mouse_Picking
  7. http://web.cse.ohio-state.edu/~shen.94/581/Site/Slides_files/picking.pdf
  8. http://www.lighthouse3d.com/tutorials/opengl-selection-tutorial/          good example code

P.S. 最近我把我们CAD程序的三维拾取算法重构了。也算是把这篇压了两年的笔记整理发布出来了,借此罗嗦两句:

  1. 别总想着优化,搞个大事件,代码结构的可读性、清晰性,比优化重要的多。即使后来为了优化而重构,也好下手改。我们项目之前总想着加速,尝试过OpenGL拾取和投影空间选择,的确是加速了,但是,我重构时发现,三维空间纯几何算法也根本不慢,完全能够满足性能需求(还有空间划分、硬件加速的策略未使用)。
  2. 如果有算法库,就尽量使用别人的库,不要想着写一个更厉害的。出错了,我们再改错;性能不够,自行优化。
  3. 我们用C++写程序,本就是看中了native code的高效率。C++代码可优化的空间还是很大的,不要把C++用成了Java。
如果有任何意见,欢迎留言讨论。


[ 主页 ]
COMMENTS
POST A COMMENT

(optional)



(optional)