Skip to content

Instantly share code, notes, and snippets.

@dwilliamson
Last active February 26, 2023 10:34
Show Gist options
  • Save dwilliamson/e6250dcb280cecc976d11ac12fc11a59 to your computer and use it in GitHub Desktop.
Save dwilliamson/e6250dcb280cecc976d11ac12fc11a59 to your computer and use it in GitHub Desktop.
Simple, fast adjacency builder
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;
}
};
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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment