PDA

View Full Version : Fast Adjacent Triangle Identification



stefnotch
05-07-2016, 03:23 AM
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;
}
}

3) 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