unity – 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:
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?

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;
        }



Source link

More To Explore

MiB: Thomas S. Gayner, Markel Corp

    This week, we speak with Thomas S. Gayner, the Chief Investment Officer and Co-Chief Executive Officer of Markel Corp. Gayner oversees public investing

Share on facebook
Share on twitter
Share on linkedin
Share on email