# How to write an adjacency algorithm that compares position data?

I have a list of indexed triangles for which I need to generate adjacency data. I've already written a brute force algorithm that creates 3 edge data structures for each triangle and then compares the edge structures with those of other triangles like so:

public struct AdjEdge
{
public Vector3 _ref0;
public Vector3 _ref1;
public int _edge;
public int _face;
public bool _parsed;

public AdjEdge(Vector3 ref0, Vector3 ref1, int edge, int face)
{
_ref0 = ref0;
_ref1 = ref1;
_edge = edge;
_face = face;
_parsed = false;
}
}

List<int> positionIndices)
{
int ncFaces = positionIndices.Count / 3;
int ncVertices = positions.Length;

// inst. adjacency array and set all values to -1
int[] adjacency = Enumerable.Repeat(-1, 3 * ncFaces).ToArray();
throw new OutOfMemoryException("Failed to allocate memory for adjacency data");

for (int i = 0; i < positionIndices.Count; i+=3)
{
int iFace = i / 3;
}

for (int i = 0; i < edges.Count - 1; ++i)
{
if (edgeA._parsed)
continue;

for (int j = 3 - (i % 3) + i; j < edges.Count; ++j)
{
if (edgeB._parsed)
continue;
// CompareVectors() returns true if the vectors are separated by a distance less than 1e-6f
if (CompareVectors(edgeA._ref0, edgeB._ref1)
&& CompareVectors(edgeA._ref1, edgeB._ref0))
{
adjacency[3 * edgeA._face + edgeA._edge] = edgeB._face;
adjacency[3 * edgeB._face + edgeB._edge] = edgeA._face;
edgeA._parsed = true;
edgeB._parsed = true;
break;
}
}
}

}


Needless to say, time complexity is an issue here. What is the most efficient method for generating adjacency when comparing position data using an epsilon?

Disclaimer: this is not the academic approach to reduce complexity but it will work in this case.

1. Build a 3d uniform grid or an Octree (depending on data distribution) of Edge arrays around the scene.
2. Add each edge to the appropriate slot (based on the edge's center) in the grid / Octree.
3. If the edge's center is epsilon away from the inner border of the grid, compare that edge with neighboring edges that are on the other side of that inner border.

This should reduce computation time from O(n^2) to something that often completes in linear time.

This is a 2d representation but the idea is that you only need to compare edges that exist in the same slot in the Octree or grid. If I misunderstood and the edges don't need to be similar in length but only nearly parallel and a small distance away from one another than you need to use something akin to Bresenham's line algorithm and add the edges to multiple slots of the grid (in that case definitely use a grid and not an Octree).

• If you need help with the second case ask about drawing lines in a 3d matrix and I will gladly provide the algorithm. – AturSams Oct 18 '14 at 8:56
• That worked very well thanks! When first reading your suggestion I had not considered that creating an octree was a sorting method. I implemented your suggestion with a 2D map, the key for which is the edge center position. For each edge in the mesh I compute the edge center and place the edge in the map. After all edges have been collected, I iterate over the edges that share an edge center and do comparisons for each edge. I will add an answer below to show how I implemented your method of sorting. Thanks again. – P. Avery Oct 18 '14 at 17:48

Here is my implementation of Zehelvion's suggestion. An octree wasn't necessary but his suggestion helped to formulate the following method:

private static int[] GenerateAdjacency(Vector3[] positions,
List<int> positionIndices)
{
// faces within mesh
int ncFaces = positionIndices.Count / 3;

// vertex count
int ncVertices = positions.Length;

// inst. adjacency array and set all values to -1
int[] adjacency = Enumerable.Repeat(-1, 3 * ncFaces).ToArray();
throw new OutOfMemoryException("Failed to allocate memory for adjacency data");

// the edge map will hold an edge center position as key and a list of edges that share the edge center position

// edge center position
Vector3 edgeVector = new Vector3();

// iterate over list of position indices
// there are 3 indices per face
for (int i = 0; i < positionIndices.Count; i+=3)
{
// face index
int iFace = i / 3;

// compute edge center position
edgeVector = Quantize((positions[positionIndices[i + 0]] + positions[positionIndices[i + 1]]) / 2);

// if the edge center doesn't exist in the map then add a new entry
if (!edgeMap.ContainsKey(edgeVector))

new AdjEdge(positions[positionIndices[i + 0]], positions[positionIndices[i + 1]], edgeVector, 0, iFace));

// compute edge center position
edgeVector = Quantize((positions[positionIndices[i + 1]] + positions[positionIndices[i + 2]]) / 2);

// if the edge center doesn't exist in the map then add a new entry
if (!edgeMap.ContainsKey(edgeVector))

new AdjEdge(positions[positionIndices[i + 1]], positions[positionIndices[i + 2]], edgeVector, 1, iFace));

// compute edge center position
edgeVector = Quantize((positions[positionIndices[i + 2]] + positions[positionIndices[i + 0]]) / 2);

// if the edge center doesn't exist in the map then add a new entry
if (!edgeMap.ContainsKey(edgeVector))

new AdjEdge(positions[positionIndices[i + 2]], positions[positionIndices[i + 0]], edgeVector, 2, iFace));
}

// iterate over the edge map
foreach (Vector3 key in edgeMap.Keys)
{
// list of edges sharing the same center position

// iterate over source edges
for (int i = 0; i < edges.Count - 1; ++i)
{
// source edge

// do not parse edge twice
if (edgeA._parsed)
continue;

// iterate over comparison edges
for (int j = i + 1; j < edges.Count; ++j)
{
// comparison edge

// do not parse edge twice
if (edgeB._parsed)
continue;

// compare the edges
if (CompareVectors(edgeA._ref0, edgeB._ref1)
&& CompareVectors(edgeA._ref1, edgeB._ref0))
{
// the edges were similar so set adjacency for both edges
adjacency[3 * edgeA._face + edgeA._edge] = edgeB._face;
adjacency[3 * edgeB._face + edgeB._edge] = edgeA._face;

// set parsed state true
edgeA._parsed = true;
edgeB._parsed = true;

// break out of comparison loop
break;
}
}
}
}