Identifying adjacent triangles:
One approach is to loop over each vertex and to compare it with all the other vertices. This can be optimized a bit:
- A triangle may at most have 3 adjacent triangles
- All adjacent vertices will be after the current vertex (Because the previous vertices already found the current vertex!)
But, it will still be a quadratic time algorithm, which can be quite slow.
A linear time algorithm:
We will use keys to quickly find adjacent vertices. (Input: vertex, Output: an array of triangles that share the vertex)
-
Create an object that can have keys and values
Make sure that a single key can store multiple values/an array. -
For each vertex, store it in your object as a key and store the vertex’ triangle as the value. (Linear time)
object adjacencyInfo;
foreach(vertex in mesh){
if(adjacencyInfo.HasKey(vertex){
//If the keys is already present, just add the triangle to the key
adjacencyInfo["vertex"].Add(vertex.triangle);
}else{
//Otherwise, we will have to create the key and add the triangle
adjacencyInfo["vertex"] = vertex.triangle;
}
}
- Now you can simply loop over each vertex and look it up in the object (Also linear time)
foreach(vertex in mesh){
adjacencyInfo["vertex"] //All adjacent vertices
}
For finding a triangle with a common edge, a slightly modified algorithm can be used: javascript - Finding adjacent nodes - Stack Overflow