- 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
Follow this Question
Related Questions
Color triangle on mesh 3 Answers
Procedural mesh creation issue 1 Answer
Draw multiple triangles from a 2d vector of dots C# 0 Answers