Jump to content
  • Advertisement
Sign in to follow this  
broli86

question regarding half edge data structure

This topic is 3734 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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. [/QUOTE] ^^It makes me wonder if there is something wrong here in my algorithm.

Share this post


Link to post
Share on other sites
Advertisement
Well one good reason is that you cannot forward iterate around the boundary of your mesh if the outside half-edges are null. Also I expect what you are doing breaks one of the invariants listed in the cgafaq article.
Where I work we have been using an implementation of a half edge mesh based on the cga faq one, and it functions very well.
Also, I guess you are using half-edge to allow easy editing operations on the mesh. If this is the case then using integer indexing is a bad idea, as any removal of vertices, edges, or polygons means you need to update every index. Although I know quite a few operations require indices, so maybe in your case it is unavoidable. What I do is store the pointers as in the cga faq half-edge structure then suplement them with a single index in each structure representing its own index, meaning that at least there is only one index to update for each element, instead of all the references.
So your half_edge would look like:

struct half_edge
{
int eindex; // half-edge index
half_edge_vertex* start_point; //start point for half edge
half_edge_vertex* end_point; // end point for half edge
half_edge* next; // points to next edge (CCW order) which is adjacent to the current one
half_edge* prev; // points to previous edge which is adjacent to current one
};

Also there is no need for the end_point as it is easily found by next->start_point.

Share this post


Link to post
Share on other sites
You are right in saying that the algo fails if you have open mesh where you have boundary edges. Then in that case having some twin edges as null prohibits you from traversing the neighbourhood vertices. I asked around in many groups and forums and people replied that if you are having a closed mesh instead(which is what i have in my project), this algo is extremely fast and gives correct results. It might be useful in situations where one can get away with closed mesh. I do not want editing operations on mesh, I merely want to store the edge information etc because it can be used in modelling some complex effects such as diffraction.

Share this post


Link to post
Share on other sites
You answered your own question then! You aren't worried about meshes with holes, and you have been told by (several?) people that this structure works, and is fast, so you should probably try it out!
It may be that your navigation around the mesh will require a few more checks for null pair half-edges.
/edit
One problem I see with the code is that 0 is infact a valid index into a 0 based array (i.e. all C/C++/stl) arrays, so you might want a different value to indicate a null index (0xffffffff or -1?).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!