Enhancing CGAL's Alpha Wrap

The goal of this project was to enhance the Alpha Wrap algorithm, in particular its implementation in CGAL. I worked on two tasks:

• In the beginning of the coding period, I implemented and benchmarked several sphere marching algorithms to enhance the performance of the offset intersection (Rule 1 in the paper).
• In the end of the coding period, I implemented the Alpha Wrap algorithm with a varying alpha value.

The Alpha Wrap algorithm takes as input a soup of primitives (points, edges and triangles) and returns a watertight oriented surface triangle mesh that encloses the input with a given offset. The algorithm has two parameter:

• the offset around the input and
• a parameter alpha that controls how fine the output mesh will be (the higher the alpha the coarser the output mesh).

The idea of the algorithm is to carve out a tetrahedral Delaunay triangulation until it encloses the input. Intuitively it is like sculpting a block of stone containing the input soup, with the garantie to never carve out an element of the input.

The outline of the algorithm is as follows: The algorithm starts with a Delaunay triangulation of the whole space and incrementally refines this triangulation by adding points on the offset of the input. The triangulation is divided between inside and outside cells (in 3D these are tetrahedra) and the final output is the interface between inside and outside. When the algorithm is initialized, all cells are tagged as inside. The carving step consists in tagging an inside cell as outside. When the algorithm would carve out a cell that actually contains part of the input, this triggers the addition of a new point on the offset of the input in the triangulation and refines the mesh. Carving always happens at a facet that is at the interface between inside and outside, this facet is called a gate. The alpha parameter controls how small such a gate can be and thus prevents the carving from happening once the output is fine enough. To compute a new point to insert in the triangulation, the algorithm takes the circumcenter of the outside cell (the dual of this cell in the Delaunay triangulation) and projects it onto the offset of the input. In some cases (rule 1 in the paper), this projection is done using sphere marching.

During a refinement of the triangulation, the circumcenter of the outside cell is projected onto the surface to get a new refinement point. When the dual edge between the outside and inside cells intersects the input offset (rule 1 in the paper), then sphere marching is used to compute an intersection point. (cyan dots in 1)

My goal in this project was to improve the existing dichotomic search algorithm used so far by replacing it with a faster sphere marching algorithm.

I implemented and benchmarked the following algorithms:

• Lipschitz dichotomic search (already implemented when I started),
• sphere marching,
• enhanced sphere marching.

Two main results came out of this investigation:

• sphere marching is in general the fastest algorithm,
• conventional sphere marching enhancement techniques do not yield a performance in the Alpha Wrap algorithm.

The first result is to be expected. In particular, it was expected that sphere marching is more efficient than a dichotomy, even if the implemented dichotomy relies on Lipschitz bounds and is thus more efficient that a regular binary search.

The second result is more surprising and has two main reasons.

The first reason has to do with the sequential nature of the Alpha Wrap algorithm. Most of the literature on improved sphere marching algorithms are thought for its implementation in a rendering pipeline, which runs in parallel. However Alpha Wrap computes its projections in a sequential manner, one gate at a time. For this reason most of the performance gains experienced in the context of rendering do not transfer to the context of Alpha Wrap and can even decrease the performance.

The second reason for the low performance gain is due to the fact that projection rays are in general aligned with the normal direction of the input surface, making vanilla sphere marching already close to optimal. Again, literature on sphere marching improvements is focused on rendering. In this context, the main performance bottleneck of vanilla sphere marching are rays that are tangent to the surface and most of the performance gain comes from making these rays faster. In our case, there are almost no such rays. The difference is due to the fact that in rendering, all rays are shot from the same point: the camera origin. In our case however, each ray is shot from a different point, in a direction that is always roughly towards the closest point of the input. Thus rays in Alpha Wrap are almost parallel to the normal direction of the surface. For this reason the steps taken in the sphere marching algorithm are already close to optimal.

I implemented the Alpha Wrap algorithm with a varying alpha value. In particular I wrote a field generator that depends on the curvature of the input.

In the vanilla implementation of Alpha Wrap, the value of alpha is a fixed number for the whole duration of the algorithm.

Recall that the alpha value determines how fine the triangulation can be refined. Having a fixed alpha value results in an output mesh with a relatively homogeneous refinement. By allowing the alpha to vary, we can have an output mesh that is coarser in some places and finer in some others.

We decided make alpha depend on the point in space (and alternative would be to make it depend on the number of iterations in the algorithm). A space dependent alpha can be modelled a positive scalar field \(\alpha : \mathbb R ^3 \to \mathbb R{>0}\).

Two design decision have to be taken:

• Where should the field be evaluated at ?
• What field to use ?

For the first question, I simply used the refinement point when it exists or take the circumcenter of the current gate.

For the second question, I experimented with different fields. The simplest fields do not depend on the input. I implemented a few based on signed distance functions. These field already yield interesting results.

Things get really interesting when then field starts depending on the input. I implemented a field that depends on the curvature of the input. For that I used CGAL's Corrected Curvature Computation to compute and store the value of the curvature at the input points. The field at a point \(p \in \mathbb R^3\) is then computed as follows: we first look for the closest point to to \(p\) in the input and call it \(v\). For this I used CGAL's AABB Tree. We then query the curvature at \(v\) to get the principal components \(k_1, k_2\) and compute the maximum curvature \(\max(|k_1|, |k_2|)\) at \(v\). The alpha value of the field at \(p\) is then the inverse of the maximum curvature at \(v\).

During this summer I was able to explore many ideas, implement them and put them to the test. The code I contributed is part of a branch in CGAL's development repository and will be used for further integration in the main codebase by my mentor.

What's left to do?

• Final Benchmark of the sphere tracing algorithms. The sphere marching algorithms should be tested against the bigger benchmarks in the CGAL suite before getting merged. This will be done by my mentor after the project.
• Implementing the offset as a field as well. Due to the current implementation, it would make sense to also implement the offset as a field before merging the code for varying alpha. This would make the interface cleaner.

Overall this Google Summer of Code has been a great experience! I learned a lot of things about CGAL, C++ and geometry processing. I am happy I could contribute to a very popular geometry processing library like CGAL. I am very grateful to Mael, my mentor during the summer, his support and reactivity has been flawless during the whole duration of the program. I would also like to mention that Geometry Factory, the organization behind CGAL, has also been very welcoming and remarkably well organised.