I am quite certain this is a commonly asked question but no matter how I rephrase it I simply can't find any answer on the internet.
I am making an user interface for user to select a region within a mesh by selecting multiple vertices.
To be more precise, given a triangular mesh, and a set of vertex (which is a subset of the vertices of the mesh), I would like to get all faces that are surrounded by the vertex subset.
I looked up a few algorithms, like points in polygon, Dijkstra's algorithm etc but they don't seems to help.
Many thanks.
At first you need a closed polyline embedded on the mesh that represents the contour. Once you have this contour, you can fill its inside to get the corresponding faces.
There are multiple ways to get the contour line. One way is to use a path finding algorithm like A* to find the shortest path between two consecutive vertices in your selection set (i.e. (v0 -> v1), (v1 -> v2) ... (vn -> v0)). This will give you a polyline represented as directed edges of the mesh.
Depending on how nicely the user selection behaves, you might want to clean the contour a bit. For example if the contour contains an edge that is traversed in both directions (e.g. v1 -> v2 -> v3 -> v2 -> v4 -> ...), you can just kill this edge pair. A similar cleanup is necessary if you have self intersections.
Once you have the directed contour line, filling its interior can be achieved with a breadth-first traversal. The idea is to start at the contour edges and then to iteratively add incident faces. A basic algorithm could be outlined as follows:
Input:
E: directed edges of the contour
O <- empty list of faces to examine
V <- empty list of visited faces
// Initialization
for every e in E:
calculate the face left of e (-> f)
add f to O
add f to V
// Do BFS
while O is not empty:
take the first element out of O (-> f)
for all faces g adjacent to f and not in V:
add g to O
add g to V
After this procedure, the selected faces will be in V. There is a critical part, however:
calculate the face left of e
First, the notion of left of and right of should be clear from the mesh itself. The vertices of faces are usually ordered in counter-clockwise or clockwise order (face winding order). Therefore, every non-boundary edge {v1, v2} is present in two faces: Once as (v1 -> v2) and once as (v2 -> v1). Depending on the winding order, you can choose the face that contains the edge in the correct direction. Then, if you know the winding order of your contour, this is all you need to do. I.e. if your contour is always clockwise and your mesh faces are always in clockwise order, you are done.
Things get a bit more complicated if the contour can be in either direction. Then, it is not clear what part the user wanted to mark (consider a sphere where the contour is the equator). There are two simple options:
For both options, you need to do the BFS in both directions from the contour (they are two separate BFSs to be precise). For performance reason, it is a good idea to do both at the same time. Then, you can abort whenever either one of the region runs out of open faces in O (option 1, this region will be the smaller one) or if you encounter the additional point (option 2, continue BFS only for this region).
To do this BFS efficiently, you need a way of mapping edges to their according faces and/or a neighborhood data structure on the mesh. If you want to use the latter, you might want to consider a halfedge data structure