Building a Half-Edge Mesh from a Triangle List

The problem is to build a polygonal mesh from a triangle list efficiently. A solution is important specially when building or testing physics engines. The method below shows a possible solution. This can be done without needing the additional storage and processing cost of keeping a list of half-edges for a given face during its addition which would be linked at the end of the addition in that case.


#define NULL_FEATURE 255

void Hull::AddFaces(u8 V, const Vec3* vs, u8 F, const Face* fs)
{
	// Hull statistics
	// E ~ 3V - 6, F ~ 2V - 4 
	// Mesh statistics
	// E ~ 3V, F ~ 2V, HE = 2 * E 
	u32 HE = 2 * 3 * V;
	ASSERT(V < 256);
	ASSERT(HE < 256);
	ASSERT(F < 256);

	memcpy(vertices, vs, V * sizeof(Vec3));
	vertexCount = V;

	edgeCount = 0;

	for (u8 i = 0; i < F; ++i) 
	{
		faces[i].edge = NULL_FEATURE;
	}
	faceCount = F;

	struct Edge
	{
		u8 v1, v2;
		u8 e12, e21;
	};

	const u32 edgePairCapacity = 256;
	Edge edgePairs[edgePairCapacity];
	u32 edgePairCount = 0;

	// Loop over all faces.
	for (u8 i = 0; i < faceCount; ++i) 
	{
		// Add face
		const Face* face = fs + i;
		u8 faceVertexCount = face->vertexCount;
		const u8* indices = face->indices;
		
		// Loop over all edges if the current face.
		for (u8 j = 0; j < faceVertexCount; ++j) 
		{
			// Add edge
			u8 v1 = indices[j];
			u8 v2 = j + 1 < faceVertexCount ? indices[j + 1] : indices[0];

			// Check if two half edges for this edge were created before.
			i32 edgeIndex = -1;
			bool flip = false;
			for (u32 k = 0; k < edgePairCount; ++k)
			{
				Edge* e = edgePairs + k;
				if (e->v1 == v1 && e->v2 == v2)
				{
					edgeIndex = k;
					break;
				}
				if (e->v1 == v2 && e->v2 == v1)
				{
					edgeIndex = k;
					flip = true;
					break;
				}
			}

			if (edgeIndex >= 0)
			{
				ASSERT(flip);
				u8 e12 = edgePairs[edgeIndex].e21;
				u8 e21 = edgePairs[edgeIndex].e12;

				HalfEdge* edge12 = edges + e12;
				HalfEdge* edge21 = edges + edge12->twin;
				
				ASSERT(e12 == edge21->twin);
				ASSERT(e21 == edge12->twin);

				// The mesh is probably a non-manifold one.
				ASSERT(edge12->face == NULL_FEATURE);

				// Add the half-edge to this face circular list of half-edges
				edge12->face = i;
				
				if (faces[i].edge == NULL_FEATURE)
				{
					faces[i].edge = e12;
					edges[e12].prev = e12;
					edges[e12].next = e12;
				}
				else
				{
					u8 tail = faces[i].edge;
					u8 head = edges[tail].next;

					edges[head].prev = e12;
					edges[tail].next = e12;

					edges[e12].prev = tail;
					edges[e12].next = head;

					faces[i].edge = e12;
				}
			}
			else 
			{
				// Add two half-edges
				u8 e12 = edgeCount++;
				u8 e21 = edgeCount++;

				edges[e12].origin = v1;
				edges[e12].twin = e21;
				edges[e12].face = i;
				edges[e12].prev = NULL_FEATURE;
				edges[e12].next = NULL_FEATURE;

				edges[e21].origin = v2;
				edges[e21].twin = e12;
				edges[e21].face = NULL_FEATURE;
				edges[e21].prev = NULL_FEATURE;
				edges[e21].next = NULL_FEATURE;

				// Add half-edge to this face circular list of half-edges
				if (faces[i].edge == NULL_FEATURE)
				{
					faces[i].edge = e12;
					edges[e12].prev = e12;
					edges[e12].next = e12;
				}
				else
				{
					u8 tail = faces[i].edge;
					u8 head = edges[tail].next;

					edges[head].prev = e12;
					edges[tail].next = e12;
					
					edges[e12].prev = tail;
					edges[e12].next = head;
					
					faces[i].edge = e12;
				}
				// Add half-edges to map
				ASSERT(edgePairCount < edgePairCapacity);
				edgePairs[edgePairCount++] = { v1, v2, e12, e21 };
			}
		}
	}

	Validate();
}

The method above works because the final face edge index is used as a “tail pointer” for the face’s circular list of half-edges. It is not necessary to have the face at this index pointing to a particular edge unless required. It can point to any half-edge as long as the edge envolves the face.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s