Cette page appartient aux archives web de l'EPFL et n'est plus tenue à jour.
This page belongs to EPFL's web archive and is no longer updated.

YPZhou

semester project journal #1

这段时间主要花在3D曲面的voronoi分割上了,由于没有什么现成的代码可以用,所以基本上只能借助一些几何库自己来写。

我们使用了cgal库,大致的方法是:
1 为曲面构造一个以三角形为基本元素的AABB树;
2 在曲面的bounding box里面随即取点,然后利用AABB树找到这些sample在曲面上的最近点;
3 以第二步中的点为基点,构造delaunay triangulation;
4 通过triangulation的对偶来获得voronoi diagram。

以上方法的最大问题是,由于我们不仅需要得到一个对3D空间的voronoi分割,而且要用它去分割一个曲面,也就是说我们要计算voronoi分割和曲面的相交,而cgal中并没有任何数据结构适用于这种情况。
对于这个问题,我们需要做的是设计一种数据结构。它既要能存储voronoi分割和曲面的相交,还要能够记录voronoi分割的各种性质。比方说,我们会需要知道voronoi分割和曲面相交得到的每一条曲线,同时也要知道这些曲线中,哪几条围成了一个patch。
目前我们的数据结构还不够完善,改进和完成数据结构是下一阶段的主要目标。只要这个数据结构设计得合理,实现ruled surface逼近应该并不困难。

剩下的问题集中在对cgal的学习上,cgal的官方tutorial和documentation相当糟糕(真的!)。可能这个库比较小众,使用者基本都是research向的人吧,在网上基本找不到什么通俗易懂的教程。
我觉得cgal最难习惯的一点就是数据基本上都是类似范型的东西,比如point,vector,segment等,在定义这些数据的时候还需要指定它们的kernel,而kernel的作用大致是指定了数据的具体表现形式。如果数据的kernel不同,它们之间基本是不能进行任何操作的,而相同kernel的数据则基本都有互相转换的函数。比如segment有point函数可以获得端点,也有to_vertex函数来获得方向向量。

嗯,大概就是这些了。


We have spent these weeks on Voronoi Segmentation of a given 3D surface. We implemented it with the help of the cgal library.

Steps :
1 Build an AABB tree for the surface(primitives are the triangles);
2 Random sample the bounding box of the surface, then take the nearest points of the samples on the surface as site points;
3 Build Delaunay Triangulation with those site points;
4 The dual of the triangulation will be a Voronoi Diagram.

Then we intersect the Voronoi Diagram with the surface to get a Voronoi Segmentation of the surface. The problem here is that cgal has no data structure available for such case.
We need to come up with a data structure which can store information of intersections, and information about the Voronoi structure.

We also got some problems in using cgal. We did not find any easy tutorial and the online manual of cgal is terrible.

Posted by Yunpeng Zhou at 23:27