Here is my implementation for halfedge data structure, very different from the one on flipcode and cgafaq -
struct half_edge
{
int eindex; // half-edge index
int start_point; //start point for half edge
int end_point; // end point for half edge
int next; // points to next edge (CCW order) which is adjacent to
the current one
int prev; // points to previous edge which is adjacent to current
one
};
typedef struct half_edge he;
struct half_edge_vertex
{
he *edge; //One of the half edges emanating from this vertex
};
typedef struct half_edge_vertex he_vertex;
struct half_edge_face
{
he *edge; // One of the half edges bordering this face
};
typedef half_edge_face he_face;
edgeno - just an index
start_point, end_point - vertex indices basically
next, prev - for adjacent edges in a triangle
face - the triangle to which the half edge belongs.
Initialize all the twin entries as 0 first, then after the other entries are filled up, run a simple loop like this -
he edge_record[SIZE_OF_LIST];
...............................
.................................
for(i = 0; i < SIZE_OF_LIST;i++)
for(j = i+1; j < SIZE_OF_LIST; j++)
{
if(edge_record[j].twin == 0 && edge_record == 0)
{
if(edge_record.end_point == edge_record[j].start_point && edge_record.start_point == edge_record[j].end_point)
edge_record.twin = j;
edge_record[j].twin = i;
}
}
Those half edges for which twin remains 0, they are considered to be boundary half edges.
However, the cgafaq seems to have a different approach -
Boundary half-edges are marked with a null 'left' polygon.
In particular, a null half-edge pointer in the half-edge 'pair' field should not be used to mark the boundary.
^^It makes me wonder if there is something wrong here in my algorithm.
