Wayback Machinekoobas.hobune.stream
May JUN Jul
Previous capture 13 Next capture
2021 2022 2023
2 captures
13 Jun 22 - 14 Jun 22
sparklines
Close Help
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
  • Asset Store
  • Get Unity

UNITY ACCOUNT

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account
  • Blog
  • Forums
  • Answers
  • Evangelists
  • User Groups
  • Beta Program
  • Advisory Panel

Navigation

  • Home
  • Products
  • Solutions
  • Made with Unity
  • Learning
  • Support & Services
  • Community
    • Blog
    • Forums
    • Answers
    • Evangelists
    • User Groups
    • Beta Program
    • Advisory Panel

Unity account

You need a Unity Account to shop in the Online and Asset Stores, participate in the Unity Community and manage your license portfolio. Login Create account

Language

  • Chinese
  • Spanish
  • Japanese
  • Korean
  • Portuguese
  • Ask a question
  • Spaces
    • Default
    • Help Room
    • META
    • Moderators
    • Topics
    • Questions
    • Users
    • Badges
  • Home /
avatar image
0
Question by nikofamily873284788753 · Nov 18, 2021 at 04:36 PM · 2dmeshvertextriangles

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:

alt text

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

Comment
Add comment
10 |3000 characters needed characters left characters exceeded
▼
  • Viewable by all users
  • Viewable by moderators
  • Viewable by moderators and the original poster
  • Advanced visibility
Viewable by all users

0 Replies

· Add your reply
  • Sort: 

Your answer

Hint: You can notify a user about this post by typing @username

Up to 2 attachments (including images) can be used with a maximum of 524.3 kB each and 1.0 MB total.

Follow this Question

Answers Answers and Comments

303 People are following this question.

avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image avatar image

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

Mesh triangles don't match wireframe view? 0 Answers

Understanding verts and triangles in Unity 1 Answer


Enterprise
Social Q&A

Social
Subscribe on YouTube social-youtube Follow on LinkedIn social-linkedin Follow on Twitter social-twitter Follow on Facebook social-facebook Follow on Instagram social-instagram

Footer

  • Purchase
    • Products
    • Subscription
    • Asset Store
    • Unity Gear
    • Resellers
  • Education
    • Students
    • Educators
    • Certification
    • Learn
    • Center of Excellence
  • Download
    • Unity
    • Beta Program
  • Unity Labs
    • Labs
    • Publications
  • Resources
    • Learn platform
    • Community
    • Documentation
    • Unity QA
    • FAQ
    • Services Status
    • Connect
  • About Unity
    • About Us
    • Blog
    • Events
    • Careers
    • Contact
    • Press
    • Partners
    • Affiliates
    • Security
Copyright © 2020 Unity Technologies
  • Legal
  • Privacy Policy
  • Cookies
  • Do Not Sell My Personal Information
  • Cookies Settings
"Unity", Unity logos, and other Unity trademarks are trademarks or registered trademarks of Unity Technologies or its affiliates in the U.S. and elsewhere (more info here). Other names or brands are trademarks of their respective owners.
  • Anonymous
  • Sign in
  • Create
  • Ask a question
  • Spaces
  • Default
  • Help Room
  • META
  • Moderators
  • Explore
  • Topics
  • Questions
  • Users
  • Badges