Mesh data structures: Finding neighbouring edges of a vertex

snoken · 2023-12-29T21:25:38

Hi, I am working with a directed edge data structure which is like the half-edge but more memory efficient. I am trying to determine the neighbouring edges given a vertex id. This is almost like finding the degree of a vertex. I am finding myself in an issue where if I try to find neighbouring edges of a vertex id which is part of a boundary edge, it ends up in an infinite loop. For example, when passing vertex id 2, it goes through edges 2 -> 26 -> 1 -> 17 -> 1 -> 17 -> and keeps looping between 1 and 17. My Current thought process is to traverse the structure using next(halfedge[edge]) until we hit a boundary edge. This traversal is counterclockwise, once we hit a boundary edge we know we have explored the left side. We now need to flip to explore the right side so I trigger to boolean so we now start exploring clockwise to get the edges on that side until we once again hit a boundary edge. I am quite confused on how you could find neighbouring edges given a vertex id and would appreciate any insight. This is what I am currently doing. std::vector<int> Mesh::NeighbourEdges(int vertex_id) { std::vector<int> neighbours; long startingEdge = firstDirectedEdge[vertex_id]; // fde for current vertex long currentEdge = startingEdge; bool otherside = false; do { // 2 -> 26 -> 1 -> 17 -> 1 -> 17 -> 1 neighbours.push_back(currentEdge); if(halfedge[currentEdge] == -1) { currentEdge = prev(startingEdge); otherside = true; } else { if(!otherside) { currentEdge = next(halfedge[currentEdge]); } else { currentEdge = prev(halfedge[currentEdge]); } } } while (currentEdge != startingEdge); return neighbours; }

Graphics and GPU Programming Programming OpenGL MeshDataStructures HalfEdge mesh BoundaryEdges

Started by snoken December 28, 2023 08:05 PM

11 comments, last by JoeJ 11 months, 2 weeks ago

snoken

Author

December 29, 2023 08:46 PM

@JoeJ Thanks for the reply!

JoeJ said:
V should become u in the next step.

Currently U becomes V on the next step for me. Made some other changes you mentioned too. I'm curious, what does the GetEdgePoly function return for you? Not seen a function name like this before