Meshing
Once Image Factorization is complete, we are left with a set of unordered points (x,y,z,u,v) that we have to connect together to form a polygonal mesh. The (x,y,z) components respectively are the World Coordinates of the model and the (u,v) vector represents the vertex's location in texture space. The figure below shows the completed meshing of a set of unordered points into a polygonal mesh.
The biggest challenge in this part of the project was to find a way to connect these points. There are many ways to create meshes from unordered points, but each have their benefits and drawbacks. A list of algorithms can be ontained from http://www-users.informatik.rwth-aachen.de/~roberts/software.html . There were two methods investigated:
 | Delaunay Triangulation - it is essentially the dual of a Vornoi Diagram. [CGA 97] has a clear definition of Delaunay Triangulation: |
"The Delaunay triangulation satisfies the following property: the circumcircle of each triangle is empty. The Voronoi diagram is the closest-point map, i.e., each Voronoi cell identifies the points that are closest to an input site. The Voronoi diagram is the dual of the Delaunay triangulation. Both structures are defined for general dimension. Delaunay triangulation is an important part of mesh generation."
In the 3D case, Delaunay Triangulation returns a set of tetrahedra whose circumspheres are empty. We rejected this algorithm for our use after some consideration due to the complexity of implementation and the bother of having to deal with interior facets of tetrahedra embedded in our reconstruction.
| 3D Convex Hull - We selected this algorithm because it was easy to adapt to our requirements. We used QuickHull from the Geometry Center (http://www.geom.umn.edu/software/qhull/) to convert the points into a convex hull. The Quickhull algorithm is described in [FRA 1985]. Due to the time contraints, we didn't implement a Quickhull on our own but created a pipe from our data stream to and from the external quickhull program. We then translated the output into our own internal representation and used OpenGL to view the data. |