Creating triangulations with the Ball-Pivoting Algorithm

  • Typ:Bachelorarbeit
  • Datum:2013
  • Autor(en):Rob Spoel

Overview

Goal of this bachelor thesis was to present the inner workings of the Ball-Pivoting Algorithm and to create an interactive applet that would allow it to be ran on various input data. The applet was a collaboration between multiple students. It was to facilitate an interactive environment where point clouds could be interactively created and loaded into the program. After that, each of the students would add in an algorithm or multiple algorithms for the focus of their bachelor thesis.

The algorithm that is being inspected in this thesis is the Ball-Pivoting Algorithm. It was originally conceived for surface-reconstruction of laser-scanned 3D imagery. It can take a set of vertices with estimated surface normals, and then triangulate the vertices. The triangulation that is generated is the Delaunay triangulation.

Its basic approach is to put a ball on a selected starting triangle. Each of the edges of this seed triangle represent the front of the triangulation, which will grow outward as the algorithm progresses. The ball will keep pivoting around edges of the front, thereby touching new points, and creating new triangles with the edge and the touched point. In this process, the front will keep expanding until all points have been touched by the ball and thus all the points of the given input set have been made part of the triangulation.

The algorithm has its weaknesses, which are also discussed in the paper.

Some results

Triangulation of Stanford Bunny (~36k vertices) Triangulation of Utah Teapot (480 vertices)