How to detect border vertices of an open mesh 3d model?

Question

There are two kinds of surface mesh models, closed mesh like a sphere or a cube and the second one is the open mesh model which means the surface of the model is not in a closed loop. It is open from somewhere like a hollow pipe. Sp what I want is I want to detect the border vertices of the open mesh model. there is no border in closed loop mesh but in open mesh we have to detect border vertices for some smoothing, subdivision, etc. operations. Kindly, suggest me how can I select/detect border vertices ? what is the optimal way to do this ? by comparing edges of the triangles ? Give me some idea ?

Thanks.

Solution 1

Assuming that you have a manifold mesh, then the border of the mesh are those edges which belong to only one polygon. Edges that are not on the border will belong to two polygons. The border vertices are the vertices that belong to the border edges.

A naive way to find the border vertices is to iterate through all your edges, count how many polygons they belong to, and if they only belong to one polygon, then collect the edge's vertices as border vertices. You will have to remove duplicates vertices from your collection, though.

A second approach is to have your mesh data structure examine each edge as they are added to the mesh, or as polygons are attached to particular edges. In this way, the mesh data structure can keep a list of up-to-date border edges for you, so that when you needed the edges you would not have to find them each time. This will greatly reduce the overhead of determining border edges, although inserting edges and polygons will be slightly more expensive. Your mesh data structure will also take up a bit more memory.

Solution 2

Assuming that your mesh is a 2D (or 2.5D) regular, well-constructed triangulation. You can use some of the properties listed here: http://graphics.stanford.edu/courses/cs468-10-fall/LectureSlides/02_Basics.pdf

Page 9 defines the degree (or valence) of a vertex as the number of incident edges. As shown, all boundary vertices 4 incident edges. "Internal" vertices have 5 incident edges.

Page 17 defines a boundary edge as one that is adjacent to exactly one face.

You might find the discussion on page 22 helpful (closed 2-manifold triangle meshes)