Simple, fast adjacency builder

Adjacency.cpp

struct Adjacency
{
  struct Vertex
  {
    // Vertices are shared by a variable number of edges. This indexes the global EdgeRef array.
    uint32_t edgeStartRef;
    uint32_t nbEdges;
  };

  union EdgeRef
  {
    static const uint32_t TriangleBits = 2;
    static const uint32_t MaxSharedTriangles = 1 << TriangleBits;

    struct
    {
      // Indexes the global edge array
      uint32_t edgeIndex : 32 - TriangleBits;

      // Indexes the Edge-local triangle array. This index only makes sense in an EdgeRef that
      // belongs to a Triangle.
      uint32_t sharedTriangleIndex : TriangleBits;
    };

    uint32_t value;
  };

  struct Edge
  {
    // Vertex code is an ORing of the vertex indices defining the edge. LSB contains the vertex with
    // the lowest index.
    uint32_t vertexCode;

    // Shared triangles, indexing the global triangle list
    uint32_t triangleIndices[EdgeRef::MaxSharedTriangles];
    uint32_t nbTriangles;
  };

  struct Triangle
  {
    uint32_t vertexIndices[3];

    EdgeRef edgeRefs[3];

    bool visited;
  };

  static const uint32_t InvalidVertex = 0xFFFFFFFF;

  // Fixed budget for vertices and triangles
  static const uint32_t MaxNbVertices = 50000;
  Vertex vertices[MaxNbVertices];
  static const uint32_t MaxNbTriangles = 50000;
  Triangle triangles[MaxNbTriangles];

  // Less 1 because 0xFFFF is an invalid vertex
  static_assert(MaxNbVertices < 65535, "Too many vertices to encode in an edge");

  // Worst case scenario is where all vertices are unwelded and each triangle adds its own unique edge
  // to list.
  static const uint32_t MaxNbEdges = MaxNbTriangles * 3 * 2;
  Edge edges[MaxNbEdges];

  EdgeRef vertexEdgeRefs[MaxNbEdges];

  uint32_t nbVertices;
  uint32_t nbTriangles;
  uint32_t nbEdges;

  void Reset(uint32_t nb_vertices)
  {
    assert(nb_vertices < MaxNbVertices);
    nbVertices = nb_vertices;
    nbTriangles = 0;
    nbEdges = 0;

    // Clear edge arrays
    for (uint32_t i = 0; i < nb_vertices; i++)
    {
      Vertex& vertex = vertices[i];
      vertex.edgeStartRef = 0;
      vertex.nbEdges = 0;
    }
  }

  void AddTriangle(uint32_t i0, uint32_t i1, uint32_t i2)
  {
    assert(nbTriangles < MaxNbTriangles);

    assert(i0 < nbVertices);
    assert(i1 < nbVertices);
    assert(i2 < nbVertices);

    Triangle& triangle = triangles[nbTriangles++];
    triangle.vertexIndices[0] = i0;
    triangle.vertexIndices[1] = i1;
    triangle.vertexIndices[2] = i2;
    triangle.visited = false;

    // Keep count of max number edges required per vertex
    // Each triangle adds 2 edges to a vertex. If triangles share an edge with a vertex then they will
    // both share the added edge, adding only 3 edges between them. So this max will only be hit if
    // each triangle is unwelded.
    vertices[i0].nbEdges += 2;
    vertices[i1].nbEdges += 2;
    vertices[i2].nbEdges += 2;
  }

  void Build()
  {
    // Count total number of edges required
    uint32_t edge_start_index = 0;
    for (uint32_t i = 0; i < nbVertices; i++)
    {
      Vertex& vertex = vertices[i];
      vertex.edgeStartRef = edge_start_index;
      edge_start_index += vertex.nbEdges;

      // Currently stores the MAX edge count. Reset to zero so that the actual edge count can be
      // figured out.
      vertex.nbEdges = 0;
    }

    assert(edge_start_index < MaxNbEdges);

    // Identify shared edges and triangles
    for (uint32_t i = 0; i < nbTriangles; i++)
    {
      Triangle& triangle = triangles[i];

      uint32_t vi0 = triangle.vertexIndices[0];
      uint32_t vi1 = triangle.vertexIndices[1];
      uint32_t vi2 = triangle.vertexIndices[2];

      triangle.edgeRefs[0] = AddEdgeToVertices(vi0, vi1);
      triangle.edgeRefs[1] = AddEdgeToVertices(vi1, vi2);
      triangle.edgeRefs[2] = AddEdgeToVertices(vi2, vi0);

      AddTriangleToEdge(i, triangle.edgeRefs[0]);
      AddTriangleToEdge(i, triangle.edgeRefs[1]);
      AddTriangleToEdge(i, triangle.edgeRefs[2]);
    }
  }

  uint32_t GetSharedTriangle(EdgeRef edge_ref) const
  {
    const Edge& edge = edges[edge_ref.edgeIndex];
    return edge.triangleIndices[edge_ref.sharedTriangleIndex];
  }

private:
  EdgeRef AddEdgeToVertices(uint32_t vi0, uint32_t vi1)
  {
    Vertex& v0 = vertices[vi0];
    Vertex& v1 = vertices[vi1];

    // Construct ordered vertex code for edge
    uint32_t vertex_code = vi0 < vi1 ? vi0 | (vi1 << 16) : vi1 | (vi0 << 16);

    // Search for a matching edge already in the first vertex.
    EdgeRef* vertex_edge_refs = vertexEdgeRefs + v0.edgeStartRef;
    for (uint32_t i = 0; i < v0.nbEdges; i++)
    {
      EdgeRef edge_ref = vertex_edge_refs[i];
      Edge& edge = edges[edge_ref.edgeIndex];
      if (edge.vertexCode == vertex_code)
      {
        // If the edge was found in the first vertex, it's assumed to also be in the second vertex
        // and so nothing further needs to be done.
        return edge_ref;
      }
    }

    // Add a new edge if one wasn't found
    EdgeRef edge_ref;
    edge_ref.edgeIndex = nbEdges++;
    Edge& edge = edges[edge_ref.edgeIndex];
    edge.vertexCode = vertex_code;
    edge.nbTriangles = 0;

    // Initially when there are zero or one triangles attached to an edge, ensure retrieving a
    // shared triangle returns an invalid index, without the user having to check the edge triangle
    // count first.
    edge_ref.sharedTriangleIndex = 1;
    edge.triangleIndices[1] = InvalidVertex;

    // Add the edge to both vertices
    vertexEdgeRefs[v0.edgeStartRef + v0.nbEdges++] = edge_ref;
    vertexEdgeRefs[v1.edgeStartRef + v1.nbEdges++] = edge_ref;

    return edge_ref;
  }

  void AddTriangleToEdge(uint32_t triangle_index, EdgeRef& edge_ref)
  {
    Edge& edge = edges[edge_ref.edgeIndex];
    assert(edge.nbTriangles < EdgeRef::MaxSharedTriangles);

    // When edges share more than 2 triangles, this will always index one of the first two
    edge_ref.sharedTriangleIndex = (edge.nbTriangles ^ 1) & 1;

    edge.triangleIndices[edge.nbTriangles++] = triangle_index;
  }
};

BFS.cpp

uint32_t* TriangleQueue;
uint32_t nb_triangles = 0;
uint32_t triangle_read_index = 0;

for (uint32_t i = 0; i < adjacency->nbTriangles; i++)
{
  if (adjacency->triangles[i].visited)
  {
    continue;
  }

  TriangleQueue[0] = i;
  nb_triangles = 1;
  adjacency->triangles[i].visited = true;

  while (triangle_read_index < nb_triangles)
  {
    uint32_t triangle_index = TriangleQueue[triangle_read_index++];

    Adjacency::Triangle& triangle = adjacency->triangles[triangle_index];

    // visit triangle here

    // visit neighbours

    uint32_t ti0 = adjacency->GetSharedTriangle(triangle.edgeRefs[0]);
    uint32_t ti1 = adjacency->GetSharedTriangle(triangle.edgeRefs[1]);
    uint32_t ti2 = adjacency->GetSharedTriangle(triangle.edgeRefs[2]);

    if (ti0 != Adjacency::InvalidVertex && adjacency->triangles[ti0].visited == false)
    {
      TriangleQueue[nb_triangles++] = ti0;
      adjacency->triangles[ti0].visited = true;
    }
    if (ti1 != Adjacency::InvalidVertex && adjacency->triangles[ti1].visited == false)
    {
      TriangleQueue[nb_triangles++] = ti1;
      adjacency->triangles[ti1].visited = true;
    }
    if (ti2 != Adjacency::InvalidVertex && adjacency->triangles[ti2].visited == false)
    {
      TriangleQueue[nb_triangles++] = ti2;
      adjacency->triangles[ti2].visited = true;
    }
  }
}