If you are interested by the half-edge or curious about sophisticated data structures, this post is for you. I know it is very difficult for people new in the field of computational geometry to find relevant informations about implementation of half-edge structure, so I will try to explain the concepts very carefully.
When you understand the basic principles of navigation, then maybe you want to expose a compliant API in order to iterate more easily through your mesh. So it can be done very easily by implementing a collection of iterators on top of the half-edge structure. For example, some ideas of iterators you can add to your library:
public class IteratorFromVertexToNeighbourVertices
public class IteratorFromFaceToNeighbourFaces
Now come back to low level half-edge implementation. We saw that the list of 11 getter methods exposed by the Edge class is quite useful to use. But at first look, it will imply a lot of datas to maintain and in consequence a nightmare to implement. But don't worry, because in reality almost of the adjacency relations between the objects can be deduced from the very small core of datas showed in this illustration:
public class Edge
// core datas:
// public interface:
This proves that only 4 datas need to be maintained in order to implement a complete half-edge structure.
So now that we have a descent core API, we need some additionnal tools to comfortably build concrete structures. For example, we could code a parser that generates a complete half-edge structured Mesh from a .3ds file (3D Studio Max native export format). An other possibility is to code some simple primitives and tools allowing us to expand them. We choose this second approach and it is the subject of the next articles:
First, what is the motivation behind the use of half-edge ? Maybe you already know data structures like linked-list, tree, or graph, but what is half-edge and why you would need to implement it ?
One answer I would give is the following: you need a half-edge structure when you need to navigate very quickly and easily inside a polygon mesh. Remember that you need polygon mesh not only for 3D, but also for some 2D complex datas representation like Delaunay triangulation (note that in this article we will deal only with 3 sides polygon mesh).
Now the problem is that in many libraries or softwares, the polygon mesh datas are stored inside 2 arrays: one that explicitly stores the vertices positions and one that stores vertices indexes for each triangle. For example, it is the case in Unity3D Mesh class. We can illustrate this by the following diagram:
Now the problem is that in many libraries or softwares, the polygon mesh datas are stored inside 2 arrays: one that explicitly stores the vertices positions and one that stores vertices indexes for each triangle. For example, it is the case in Unity3D Mesh class. We can illustrate this by the following diagram:
This data structure is quite simple to understand and to implement, but it is a performance disaster when you need to write an algorithm that needs to navigate and search efficiently inside the mesh. One obvious example of navigation is pathfinding. But why is it not efficient ? Because the adjacency access is not. For example, if you want to find all the vertices connected by an edge to a given vertex, you need to scan the entire triangle array to find the relevant indexes ; so the time you spend to do it increases by the size of your mesh.
But with half-edge you can access adjacency in constant time, because in this structure it becomes the explicit way to keep the datas. For this purpose, the main object you will implement will be not a vertex or a face, but an oriented edge. Think oriented edge as the core node of your data, as we can see in this illustration:
Given an Edge object current edge, a descent half-edge API should give you access to the complete adjacency: Vertex, Edge and Face objects adjacent to current edge. For example, my own interface for half-edge structure as a library contains 4 core classes: Vertex, Edge, Face and Mesh with the following public methods :
public class Vertex
public class Edge
public class Face
Equiped with that, you must be able to iterate efficiently in order to navigate through the whole mesh. For example, from any Vertex v, you can iterate to any direct adjacent Vertex by calling a sequence like:
v.edge.destinationVertex // 1st adjacent vertex
v.edge.rotLeftEdge.destinationVertex // 2nd adjacent vertex at left
v.edge.rotLeftEdge.rotLeftEdge.destinationVertex // 3rd adjacent vertex at left
But with half-edge you can access adjacency in constant time, because in this structure it becomes the explicit way to keep the datas. For this purpose, the main object you will implement will be not a vertex or a face, but an oriented edge. Think oriented edge as the core node of your data, as we can see in this illustration:
Given an Edge object current edge, a descent half-edge API should give you access to the complete adjacency: Vertex, Edge and Face objects adjacent to current edge. For example, my own interface for half-edge structure as a library contains 4 core classes: Vertex, Edge, Face and Mesh with the following public methods :
public class Vertex
- public get position : Vector // (can be any 2D or 3D coordinates data)
- public get edge : Edge // (any Edge with this Vertex as origin)
public class Edge
- public get originVertex : Vertex
- public get destinationVertex : Vertex
- public get oppositeEdge : Edge
- public get nextLeftEdge : Edge
- public get prevLeftEdge : Edge
- public get nextRightEdge : Edge
- public get prevRightEdge : Edge
- public get rotLeftEdge : Edge
- public get rotRightEdge : Edge
- public get leftFace : Face
- public get rightFace : Face
public class Face
- public get edge : Edge // (any Edge with this face adjacent at left)
public class Mesh
- public get vertices : Vertex []
- public get edges : Edge []
- public get faces : Face []
Equiped with that, you must be able to iterate efficiently in order to navigate through the whole mesh. For example, from any Vertex v, you can iterate to any direct adjacent Vertex by calling a sequence like:
v.edge.destinationVertex // 1st adjacent vertex
v.edge.rotLeftEdge.destinationVertex // 2nd adjacent vertex at left
v.edge.rotLeftEdge.rotLeftEdge.destinationVertex // 3rd adjacent vertex at left
v.edge.rotLeftEdge. ... .rotLeftEdge.destinationVertex // n-th adjacent vertex at left
The same idea works for faces. From any Face f, you can reach the 3 direct adjacent Face just by:
f.edge.rightFace // 1st adjacent face at left
f.edge.nextLeftEdge.rightFace // 2nd adjacent face at left
f.edge.nextLeftEdge.nextLeftEdge.rightFace // 3rd adjacent face at left
The same idea works for faces. From any Face f, you can reach the 3 direct adjacent Face just by:
f.edge.rightFace // 1st adjacent face at left
f.edge.nextLeftEdge.rightFace // 2nd adjacent face at left
f.edge.nextLeftEdge.nextLeftEdge.rightFace // 3rd adjacent face at left
When you understand the basic principles of navigation, then maybe you want to expose a compliant API in order to iterate more easily through your mesh. So it can be done very easily by implementing a collection of iterators on top of the half-edge structure. For example, some ideas of iterators you can add to your library:
public class IteratorFromVertexToNeighbourVertices
- public function set fromVertex(value:Vertex)
- public function get next : Vertex
public class IteratorFromFaceToNeighbourFaces
- public function set fromFace(value:Face)
- public function get next : Face
public class IteratorFromEdgeToRotatedEdges
- public function set fromEdge(value:Edge)
- public function get next : Edge
public class IteratorFromVertexToHoldingFaces
- public function set fromVertex(value:Vertex)
- public function get next : Face
You can see here that given an Edge object current edge, only 4 datas are required: origin vertex opposite edge, next left edge and left face. As a justification, I will simply give you a possible implementation of the Edge class with the complete deduced adjacency relations:
// core datas:
- private var _originVertex : Vertex
- private var _oppositeEdge : Edge
- private var _nextLeftEdge : Edge
- private var _leftFace : Face
// public interface:
- public get originVertex : Vertex { return _originVertex }
- public get destinationVertex : Vertex { return _oppositeEdge.originVertex }
- public get oppositeEdge : Edge { return _oppositeEdge }
- public get nextLeftEdge : Edge { return _nextLeftEdge }
- public get prevLeftEdge : Edge { return _nextLeftEdge.nextLeftEdge }
- public get nextRightEdge : Edge { return _oppositeEdge.nextLeftEdge.nextLeftEdge.oppositeEdge }
- public get prevRightEdge : Edge { return _oppositeEdge.nextLeftEdge.oppositeEdge }
- public get rotLeftEdge : Edge { return _nextLeftEdge.nextLeftEdge.oppositeEdge }
- public get rotRightEdge : Edge { return _oppositeEdge.nextLeftEdge }
- public get leftFace : Face { return _leftFace }
- public get rightFace : Face { return _oppositeEdge.leftFace }
This proves that only 4 datas need to be maintained in order to implement a complete half-edge structure.
So now that we have a descent core API, we need some additionnal tools to comfortably build concrete structures. For example, we could code a parser that generates a complete half-edge structured Mesh from a .3ds file (3D Studio Max native export format). An other possibility is to code some simple primitives and tools allowing us to expand them. We choose this second approach and it is the subject of the next articles:
No comments:
Post a Comment