current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 0 down vote favorite

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;
            }
        }

private static int[] GenerateAdjacency(Vector3[] positions,
            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();
            if (adjacency == null)
                throw new OutOfMemoryException("Failed to allocate memory for adjacency data");

            List<AdjEdge> edges = new List<AdjEdge>();

            for (int i = 0; i < positionIndices.Count; i+=3)
            {
                int iFace = i / 3;
                edges.Add(new AdjEdge(positions[positionIndices[i + 0]], positions[positionIndices[i + 1]], 0, iFace));
                edges.Add(new AdjEdge(positions[positionIndices[i + 1]], positions[positionIndices[i + 2]], 1, iFace));
                edges.Add(new AdjEdge(positions[positionIndices[i + 2]], positions[positionIndices[i + 0]], 2, iFace));
            }

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

                for (int j = 3 - (i % 3) + i; j < edges.Count; ++j)
                {
                    AdjEdge edgeB = edges[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;
                    }
                }
            }


            return adjacency;
        }

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?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

quadtree

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

share|improve this answer
    
If you need help with the second case ask about drawing lines in a 3d matrix and I will gladly provide the algorithm. –  zehelvion 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
up vote 1 down vote

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();
        if (adjacency == null)
            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
        Dictionary<Vector3, List<AdjEdge>> edgeMap = new Dictionary<Vector3, List<AdjEdge>>();

        // 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))
                edgeMap.Add(edgeVector, new List<AdjEdge>());                    

            // add the edge
            edgeMap[edgeVector].Add(
                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))
                edgeMap.Add(edgeVector, new List<AdjEdge>());

            // add the edge
            edgeMap[edgeVector].Add(
                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))
                edgeMap.Add(edgeVector, new List<AdjEdge>());

            // add the edge
            edgeMap[edgeVector].Add(
                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
            List<AdjEdge> edges = edgeMap[key];

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

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

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

                    // 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;
                    }
                }
            }
        }
        return adjacency;
    }
share|improve this answer
    
It may be a good idea to quantize the edge center positions when added to map. Otherwise, 2 keys will be made for edge center positions that are slightly different. –  P. Avery Oct 18 '14 at 17:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.