Fast Adjacent Triangle Identification

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)

  1. Create an object that can have keys and values
    Make sure that a single key can store multiple values/an array.

  2. 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;
  }
}
  1. 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: http://stackoverflow.com/a/34848669/3492994