1
\$\begingroup\$

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: enter image description here

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?

Reference material: https://jerryyin.info/geometry-processing-algorithms/half-edge/ https://kaba.hilvi.org/homepage/blog/halfedge/halfedge.htm

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;
        }
\$\endgroup\$
1
\$\begingroup\$

This seems like it would be more robust to implement as three separate operations: First collapse the edge to fuse the two vertices, but leaving triA and triB in place as degenerate two-vertex faces. Then for each of those faces, fuse them with the neighbouring face on either side to get rid of them. Those are simpler operations that are easier to get right, and that can be then be combined to create this more complex operation.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.