计算几何实践3:三角化

2017-12-10

  想写一篇三角化的总结,竟然拖了三年时间。这是我拖的最久的一篇总结了。再不写,没准以后不做这方面内容了,就没有机会了。刚开始进入项目组的时候,项目刚进入初始阶段,我们人手不够,紧迫性也不是那么高,所以,我也被允许有一些时间来阅读网格化相关的材料,一份70页的paper,一个小册子Polygon Mesh Processing。那时候还是很痛苦的,完全没有这方面的经验。
  在CAD程序中,一个很基础、重要的功能就是对Planar Graphic进行网格化。而各种网格之中,三角形网格尤为重要。所以,三角化是必须要掌握的算法。而在游戏中,程序员一般只需要把美术制作的3D模型(基本上三角形mesh)导入场景即可,也有一些情况下需要在游戏引擎中对网格做再次处理。所以,最好是对于三角化过程熟悉一些。想要把一个Planar Graphic拆分为多个三角形,拆分的方式非常多。更不用说新增定点或其他参数的情况,那拆分的方式就更多了。我们最常使用的是Delaunay三角化算法。C/C++的算法lib有很多。若使用Python,scipy包就提供了Delaunay 三角化算法,这是使用最广的一种三角化算法,所以scipy也只提供了这一种。使用起来很简单,但是,如果要自己来第一次实现这个算法,估计没有一周时间完成不了。
  使用算法库,我们倒是可以很快的实现功能,但是业务层对于数据结构肯定是有独特要求的。我们在项目中大部分时间估计就是处理和业务相关的部分了。至于算法,我现在是没有时间去实现了。只能了解个大概,学会使用。scipy.spatial.Delaunay只提供了最简单的功能,没有见到控制三角行角度、边长度、整体均匀程度、是否新增控制点等等功能,但是C/C++ lib,如CGAL、triangle等都有实现。triangle 当然也有 Python Wrapper,可在此处下载。接下来的程序使用这个lib。参考chapt3/triangulation.py程序,就可以很快的实现三角化程序。

    

    三角化过程中,我们一般有几个常见的需求:

  1. 图形中有洞
  2. 图形中有一条线段或者曲线,生成的三角形顶点必须要落在此线段上。
  3. 图形中某些区域要求三角形密度高一些,有些区域要求密度低一些。
  4. 对生成的三角形的角度,边长度,均匀程度、是否新增控制点等有要求。

  当然,真实的需求可能比这个复杂多了。在planar grpahic 中间扣几个洞 这个需求实在太常见了,如一面墙上有窗户、门,衣服上有镂空。既然是洞,那肯定是不能参与三角化的。三角化的算法接受的最重要的参数就是一系列的离散的顶点。如果想要在图形中扣一个洞,这个洞也只能用顶点信息来描述。

  例如上图,中间镂空的四边形,需要使用四条边及四边形内部任意点来指定,而四条边可以通过顶点对来描述。下面示例的红叉就是镂空部分内某一点。其实这个过程也很简单,算法首先对整个图形进行三角化,然后把镂空的部分吃掉就可以了。python版本的triangle lib输入的数据结构在文档中讲解太少了,让人不知所云。只要输出一下 triangle.get_data('face.1') ,就能照着例子来做了。triangle lib的算法控制主要依靠传入函数的一个字符串, 如 B = triangle.triangulate(A, 'pqa0.015c'),这个字符串的各个字符的意义,只能参看文档了,只要看懂了,还是非常好使用的。 如下是一个计算带孔的图形的三角化例子。请参考chapt3/complicateTriangulation.py 

  三角形顶点比三角形面片上的位置更容易确定,更好用。比如我们希望在布料上一条直线段上排布纽扣。又如如布料上一条直线段与另一布料缝合并参加物理模拟,只有缝合处的线段上都是三角形的边才能保证模拟后比较平整。同样,线段也只能通过两个顶点表示,如果限制了三角形最大面积和最小锐角,那么也可以限制三角形的边长,那么线段就会按照这个限制来分割。如下图

  对于渲染和模拟来说,我们都希望mesh有的地方密集一些,有的地方稀疏一些,主要是为减少计算量和资源使用量。处理得当,减少一两个数量级不是难事。所以,必要性显而易见。一种方法直接增加输入的顶点,第二种方法是在给出区域的条件约束,在算法内部实现。很显然,第一种简单多了。

  我们现在研发的程序的技术重点是布料模拟,其实布料模拟可以算作有限元分析的一种。我们对于网格有一些要求:如不能有很小的锐角(要尽量像正三角形),要均匀大小。估计其他的有限元分析对于网格可能有更严格的限制。或者需要三维空间的网格,那问题的难度就上升一个级别了。一般的开发工作中也接触不到的。
  我们的项目一直在使用C语言版本的triangle 这个lib来做三角化。非常小巧,简单,只有一个入口函数,一个函数就可以完成三角化的工作。
void triangulate(char *, struct triangulateio *, struct triangulateio *, struct triangulateio *);
  算法本身可能很复杂,但是lib的使用还算比较简单。第一个参数是字符串,控制了“三角形内角大小,边长,均匀程度”等参数,第二个参数是输入,第三个参数是三角化输出,第四个参数是voronoi输出,一般置为NULL即可。这里要提一下,为什么有voronoi这个参数呢?是因为voronoi tessellation和 delaunay triangulation是对偶的,相当于同一个计算结果换了一种描述而已。但是,每一个参数本身是非常复杂的,定义如下:

struct triangulateio {
  REAL *pointlist;                                               /* In / out */
  REAL *pointattributelist;                                      /* In / out */
  int *pointmarkerlist;                                          /* In / out */
  int numberofpoints;                                            /* In / out */
  int numberofpointattributes;                                   /* In / out */

  int *trianglelist;                                             /* In / out */
  REAL *triangleattributelist;                                   /* In / out */
  REAL *trianglearealist;                                         /* In only */
  int *neighborlist;                                             /* Out only */
  int numberoftriangles;                                         /* In / out */
  int numberofcorners;                                           /* In / out */
  int numberoftriangleattributes;                                /* In / out */

  int *segmentlist;                                              /* In / out */
  int *segmentmarkerlist;                                        /* In / out */
  int numberofsegments;                                          /* In / out */

  REAL *holelist;                        /* In / pointer to array copied out */
  int numberofholes;                                      /* In / copied out */

  REAL *regionlist;                      /* In / pointer to array copied out */
  int numberofregions;                                    /* In / copied out */

  int *edgelist;                                                 /* Out only */
  int *edgemarkerlist;            /* Not used with Voronoi diagram; out only */
  REAL *normlist;                /* Used only with Voronoi diagram; out only */
  int numberofedges;                                             /* Out only */
};


  其实,总结一下,也只有:三角化的顶点(及个数),顶点属性,三角形(输出),线段,洞,区域属性,三角形边(输出),只有四五个是有效的。其中,只有pointlist才是必需的,不用担心很复杂。上面几个图例对应的python调用函数的参数为:A = dict(vertices=vertices, segments=segments, holes=holeMarkerPos),三个二维数组罢了。  
  Youtube上有视频对算法的过程做了动画讲解,看起来就直观多了。

  1. http://dzhelil.info/triangle/index.html  triangle python wrapper 
  2. https://people.eecs.berkeley.edu/~jrs/papers/imrtalk.pdf
  3. https://people.eecs.berkeley.edu/~jrs/papers/triangle.pdf

2017-12-22  P.S. 这两周忙起来了,这篇文章拖了很久了,也不在乎这两周了,不过,终于算是完成。。

 

 

 

如果有任何意见,欢迎留言讨论。


[ 主页 ]
COMMENTS
POST A COMMENT

(optional)



(optional)