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

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