计算几何实践2:几何物体及交叉判断

2017-12-10
  我们可能在程序中见到非常复杂的图形,但是,他们可以最简单的线段拼接而成。所以,线段是我们关注的重点,其次才是三角形。
  1 线段交叉判断
  线段交叉判断是最为基础的算法。最简单的场景:判断两个独立的线段是否相交。算法相当简单。把两条线段延长为直线,看直线是否相交,如果相交,判断焦点是否在一条线段上。判断直线是否相交可以转换成一个二元方程组是否有解的问题。判断一个点是否在线段上的方法:把点投影到直线上,投影点为p,判断p是否在线段AB内。此处因为交点已经在直线上了,故只需要检查是否在线段内。
    
  示例代码参见chapt2/line.py
  如果我们有两个线段的集合,需要计算他们之间有多少个交点呢?简单的做法是每两个线段之间相交检测,算法复杂度为O(n2)。有没有更好的算法呢?有的,平面扫描算法。这类算法,可称为“输出敏感的算法”,亦称为“交点敏感算法”。它的算法运行时间取决于交点的个数。这个问题很常见,如两个多边形交点个数求解,检查多边形是否边界是否自交,多边形分解(Voronoi diagramDelaunay triangulation),多边形Boolean操作。在机器人及运动规划、碰撞检测,图形学中极为常见。具体问题及算法分析,请参考链接3,4。算法复杂度为O(n log n + R), R为交点个数。链接6是一个不错的视频。因为这类算法有些复杂,我将抽出单独的一篇blog来讲讲解。
  2 半边结构(Doubly-Connected Edge List
  这个翻译有点奇怪啊,但是的确非常形象。这是图形学算法的基础,是一种图形的表示方法。链状的表示了图形的拓扑结构。使用这种数据结构重要的原因有:算法效率比较高。数据结构非常简单,一般在把planar graph按照需求变成网格(三角网格,四边形网格,多边形网格等)的过程中构建这个数据结构。可参考的Python实现有: anglyan/dcel
  3 多边形(多面体)覆盖计算
  相交测试是计算几何的基础之基础。简单的有二维平面上多边形的相交测试,复杂的有高维空间的convex hull相交测试,至于concave hull相交测试,似乎极难以处理。在这里,简单的梳理一下常见的相交测试。
  1. 三角形
  2. (凸)多边形
  3. 三面体
  4. cuboid/frustum
  5. convex hull
  说起来简单,其实连最简单的情形”三角形相交测试“都需要初学者花费一天的时间来搞明白、实现出来。更不用说后面的体相交测试。如果个人时间充足,还是尽量尝试着实现算法吧。工作了之后,再想抽出这样充足连续的时间是非常困难的。复杂物体的相交测试用到一个算法:分离轴算法。基本思路类似于平面扫描算法。在二维空间内,无论Polygon是否convex,相关的算法还是比较简单的。所以,一般也没有区分。三维,甚至高维空间内,非凸包相交检测算法极为困难,甚至凸包相交检测都非常困难,最优化课程中有讲解。高维空间的凸包(convex hull)的相交测试算法对于一般的3D应用也没有意义,不要管了。因为PyQt就自带了常见二维图形的相交测试函数。我实在不想自己搞一遍了,如果以后有时间了,就挑一些重点的函数实现一遍。所以,我现在关注的重点是三维物体。
  对于三维相交测试,一个简单的加速策略是对物体生成包围盒。因为计算量真的可能非常大。常见的包围盒是:OBB(Minimum bounding box)。AABB是OBB的一种特殊情形,不能旋转。其他类包围盒的物体有:胶囊,圆柱体,椭球,球体,三角形,convex hull。我们只需要考虑最常见的OBB即可,它能满足80%的需求。我们在软件运行过程中,很少会改变物体的包围盒,却经常需要包围盒来做相交测试,非常划得来。在常见的算法包中都应该有这些工具。在这里推荐一个简单的相交测试算法库:MathGeoLib。lib很小,功能仅限于简单的几何形状表达和几何算法。我最近在做一个CAD任务,就直接使用了这个lib。
    至于物体(mesh)与一般的包围盒相交测试,反而简单,大不了就直接遍历顶点,要么想加速,空间划分一下即可。PyQt4似乎还是只支持老的OpenGL API。PyQt5才能支持VAO,VBO等。稍后会用PyQt5写一个3D窗口程序来展示3D相交测试的例子吧。
  4 多边形boolean 操作。
   boolean操作有:union, intersection, difference。就是上面的多边形覆盖算法的一种使用。两个常见2D polygon boolean算法lib有:pyclipper, Polygon。至于convex polyhedra 的Boolean操作lib,我还没有看到成熟的lib。说明这类问题真的不好计算。至于这个难度,似乎就更大一些了。我们的CAD程序中没有这个需求。感觉游戏里类似的需求更少了。应该不需要关注。
  1. http://pyqt.sourceforge.net/Docs/PyQt4/
  2. Computational Geometry(Mark de Burg)
  3. https://github.com/ldw5258/lipt/blob/master/algorithm/flatscanning.org
  4. http://geomalgorithms.com/a09-_intersect-3.html
  5. http://pyqt.sourceforge.net/Docs/PyQt4/qpainter.html#drawConvexPolygon-2
  6. https://www.youtube.com/watch?v=dePDHVovJlE
 
如果有任何意见,欢迎留言讨论。


[ 主页 ]
COMMENTS
POST A COMMENT

(optional)



(optional)