pearswj/Plankton — pull request #2 by pearswj (2013-07-31 14:42:40+00:00)
Title: Handle non-manifold vertices when adding faces

To quote myself from a recent email conversation...

> First off, I'm defining non-manifold vertices as vertices which have two or more outgoing boundary edges. My reasoning behind exploring non-manifold vertices (but not non-manifold meshes in general) was that when faces are created from a list of vertex indices there is no reason why a non-manifold vertex condition could not arise during construction. The attached image shows a vertex which is incident to four faces, none of which share an edge. Let's say we've created this mesh from an OBJ file... There may be more faces still to come (which fill in the gaps between faces) but, because of the order that the faces have been added so far, the halfedges will not be linked correctly*. With non-manifold vertices it is impossible to be sure that their halfedges are correctly linked without interrogating the geometry of the mesh. Instead we can "handle" the non-manifold vertex by re-linking the halfedges when new faces are added. For example, the addition of face {1, 0, 8} would provide some much needed information about the adjacency of the halfedges around vertex #0 – in this case halfedges {0, 8} and {1, 0} will need to be made adjacent to each other and the other halfedges adjusted to maintain a valid loop of halfedges around vertex #0.
>
> ![make_adjacent](https://f.cloud.github.com/assets/121068/886602/a9c30694-f9ec-11e2-9de7-d42bc54fe2f8.png)

The blog at http://www.pointclouds.org/blog/nvcs/ (from which the above image was adapted) provides some useful insight into the handling of halfedges around a non-manifold vertex.

With the changes below it has been possible to create large halfedge meshes from face-vertex data stored in OBJ files.