CS598b Project

This project was an attempt to confront the question of surface reconstruction from a collection of points. The algorithm used works as follows:

Algorithm: A Delaunay triangulation is generated for the collection of points and the those triangles on the convex hull are defined as the boundary of the surface. Iteratively, the algorithm searches for the largest boundary triangle, finds the simplex whose face it is, removes the triangle from the boundary list and adds the three other faces, (also removing the simplex itself from the simplex list). This process halts when each data point is on some boundary triangle.
It should be noted that this algorithm does not gaurantee that the final object is a solid. (It is possible to end up with boundary triangles whose associated simplices have been removed).

This seemed to be to soon to stop and so a bit of clean up is performed afterwards:

The metric used to measure the size of a triangle face is obtained by computing the maximum of the edge lengths of the face divided through by some weight. (In my case I took the weight to be the average distance to the n-closest points, thereby allowing for greater triangles for points which have fewer neighbors.)

Possible Next Steps: I had started playing around with triangle normals, as an extra factor for the metric, but I haven't done as much as I could. Additionally, it could be useful to try to explore the ability to localize this algorithm. In other words, if only a few points are left to be revealed, then the triangles the algorithm looks through should be those closer to this collection of points.

Pictures:
Nice Torus (800 pts) Sculpted Cleaned Filled
Random Torus (1600 pts) Sculpted Cleaned Filled
Person (5844 pts) Sculpted Cleaned
I am not exactly sure what happened during the cleaning phase. (I though the code was supposed to ensure that the last triangle associated to a point would not get removed.)