- Home /

# Having trouble implementing edge collapse operation with half-edge data structure

I'm trying to make a half-edge data structure to interact with meshes in 2D space in Unity but I'm having trouble with implementing an edge collapse operation that merges one vertex into its twin half-edge vertex.

The diagram below shows how the edge collapse code is supposed to work:

After using it in Unity with a basic mesh, it seems to work for a bit until it gives a null reference exception because a triangle I'm pointing to doesn't exist in this region:

```
do
{
//merge the index of the specific triangle by overwriting vertB with vertA in the triangle mesh indices
currentHE.SourceVert = sourceVertA;
if (triangleMeshIndices[TriangleIndex * 3] == vertIndexB)
{
triangleMeshIndices[TriangleIndex * 3] = vertIndexA;
}
else if (triangleMeshIndices[TriangleIndex * 3 + 1] == vertIndexB)
{
triangleMeshIndices[TriangleIndex * 3 + 1] = vertIndexA;
}
else if (triangleMeshIndices[TriangleIndex * 3 + 2] == vertIndexB)
{
triangleMeshIndices[TriangleIndex * 3 + 2] = vertIndexA;
}
currentHE = currentHE.Twin.Next;
} while (currentHE != startHE);
```

Here's an example of how it works in Unity: https://i.imgur.com/rQymkBh.mp4

I really want to know what special cases I'm missing and as to why this happens on occasion. Could there be a more fool-proof way to implement it?

Here's the function in question:

```
public void Collapse(HalfEdge targetEdge)
{
//don't proceed with the collapse if triangle is by any chance located on the bounds of the mesh
if (targetEdge.SourceTF == null || IsBoundaryTriangle(targetEdge.SourceTF) ||
IsBoundaryTriangle(targetEdge.Twin.SourceTF)) return;
//reference necessary mesh info for the collapse
//first triangle
TriangleFace triA = targetEdge.SourceTF;
HalfEdge halfEdgeA1 = targetEdge;
HalfEdge halfEdgeA2 = halfEdgeA1.Next;
HalfEdge halfEdgeA3 = halfEdgeA2.Next;
HalfEdge halfEdgeTwinA2 = halfEdgeA2.Twin;
HalfEdge halfEdgeTwinA3 = halfEdgeA3.Twin;
Vertex sourceVertA = halfEdgeA1.SourceVert;
//second triangle
TriangleFace triB = targetEdge.Twin.SourceTF;
HalfEdge halfEdgeB1 = targetEdge.Twin;
HalfEdge halfEdgeB2 = halfEdgeB1.Next;
HalfEdge halfEdgeB3 = halfEdgeB2.Next;
HalfEdge halfEdgeTwinB2 = halfEdgeB2.Twin;
HalfEdge halfEdgeTwinB3 = halfEdgeB3.Twin;
Vertex sourceVertB = halfEdgeB1.SourceVert;
//Set all of the surrounding edges of the twin's vertex to use target edge's vertex as a source instead for the merge
HalfEdge startHE = sourceVertB.SourceHE;
HalfEdge currentHE = startHE;
//side verts
Vertex sourceVertA3 = halfEdgeA3.SourceVert;
Vertex sourceVertB3 = halfEdgeB3.SourceVert;
int vertIndexA = sourceVertA.VertIndex;
int vertIndexB = sourceVertB.VertIndex;
do
{
//merge the index of the specific triangle by overwriting vertB with vertA in the triangle mesh indices
currentHE.SourceVert = sourceVertA;
if (triangleMeshIndices[TriangleIndex * 3] == vertIndexB)
{
triangleMeshIndices[TriangleIndex * 3] = vertIndexA;
}
else if (triangleMeshIndices[TriangleIndex * 3 + 1] == vertIndexB)
{
triangleMeshIndices[TriangleIndex * 3 + 1] = vertIndexA;
}
else if (triangleMeshIndices[TriangleIndex * 3 + 2] == vertIndexB)
{
triangleMeshIndices[TriangleIndex * 3 + 2] = vertIndexA;
}
currentHE = currentHE.Twin.Next;
} while (currentHE != startHE);
//attach the twins and set the side verts
halfEdgeTwinA2.SetTwin(halfEdgeTwinA3);
halfEdgeTwinB2.SetTwin(halfEdgeTwinB3);
sourceVertA3.SourceHE = halfEdgeTwinA2;
sourceVertB3.SourceHE = halfEdgeTwinB2;
//removal
RemoveThisTriangle(triA);
RemoveThisTriangle(triB);
HalfEdges.Remove(halfEdgeA1.GetHashCode());
HalfEdges.Remove(halfEdgeA2.GetHashCode());
HalfEdges.Remove(halfEdgeA3.GetHashCode());
HalfEdges.Remove(halfEdgeB1.GetHashCode());
HalfEdges.Remove(halfEdgeB2.GetHashCode());
HalfEdges.Remove(halfEdgeB3.GetHashCode());
//remove vertex
sourceVertB.RemoveThisVertex();
//set the merged vertex's source edge to its twin
sourceVertA.SourceHE = halfEdgeTwinA3;
}
public void RemoveThisTriangle(TriangleFace targetTriangle)
{
HalfEdge startHE = targetTriangle.SourceHE;
HalfEdge currentHE = startHE;
int triangleIndex = targetTriangle.TriangleIndex;
do
{
currentHE.SourceTF = null;
currentHE = currentHE.Next;
} while (currentHE != startHE);
//remove triangle object from list
triangleFaces.RemoveAt(triangleIndex);
//remove mesh indices using the triangle obj's index from the mesh list of triangle indices
triangleMeshIndices.RemoveAt(triangleIndex * 3);
triangleMeshIndices.RemoveAt(triangleIndex * 3);
triangleMeshIndices.RemoveAt(triangleIndex * 3);
//readjust indices for triangle obj list
for (int i = 0; i < triangleFaces.Count; i++)
{
if (triangleIndex < triangleFaces[i].TriangleIndex)
{
triangleFaces[i].TriangleIndex -= 1;
}
}
}
public bool IsBoundaryTriangle(TriangleFace triangle)
{
HalfEdge startHE = triangle.SourceHE;
HalfEdge currentHE = startHE;
do
{
if (currentHE.Twin.SourceTF == null) return true;
currentHE = currentHE.Next;
} while (currentHE != startHE);
return false;
}
```

### Your answer

### Welcome to Unity Answers

If you’re new to Unity Answers, please check our User Guide to help you navigate through our website and refer to our FAQ for more information.

Before posting, make sure to check out our Knowledge Base for commonly asked Unity questions.

Check our Moderator Guidelines if you’re a new moderator and want to work together in an effort to improve Unity Answers and support our users.

### Follow this Question

### Related Questions

Mesh triangles don't match wireframe view? 0 Answers

Understanding verts and triangles in Unity 1 Answer

2d custom mesh triangulator problem 1 Answer

Optimized vertex manipulation 1 Answer

Mesh Vertex 0 Answers