The Advancing Fronts Algorithm
The kind of algorithm we'll be palying with is an advancing front algorithm, Early version of such algorithms include Ball pivoting algorithm (BPA). Some related algorithms require the surface to be defined implicitly. YouTube videos exist depicting the triangulation process and its utility for visualization. You can get a sense for what the value of triangulation is and how it represents an improvement over visualizing just the point cloud.
Since this course does not have the pre-requisites required to implement the algorithm from scratch (a good algorithms course), I have written a primitive version of the algorithm then removed some of the key code. Your task is to flesh it out, then to apply it to several point clouds with different processing parameters, and communicate your findings. All of the necessary scripts and code stubs can be found here. The zip-file contains the mesh generation code stub, a script stub for testing out the code, and a Matlab file with some sample surfaces as point clouds. You should test out the code on one of the objects in the point cloud from earlier activities (that you've been working with). Presumably, you've segmented out each individual object in an earlier activity.
Other References
- C.E. Scheidegger, S. Fleishman, C.T. Silva. “Triangulating Point Set Surfaces with Bounded Error.” Eurographics Symposium on Geometry Processing, 2005. pdf, open source code
- Z.C. Marton, R.B. Rusu, M. Beetz. “On Fast Surface Reconstruction Methods for Large and Noisy Point Clouds.” ICRA, 2009. paper, code in PCL
- D.J. Mavrilipis. “An Advancing Front Delaunay Triangulation Algorithm Designed for Robustness.” Journal of Computational Physics, 117(1):90-101, 1995. presentation slides , paper
- Lots more by just googling: advancing fronts algorithm.
- There are other triangulation methods, but one should be careful regarding their underlying assumptions. For example, there is a class of triangulation or mesh generation schemes that depend on having the desired surface implicitly modeled using a signed distance or equivalent function.