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:
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 | |