Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / Good way to pair half-edges? Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
z80

May 24, 2005, 01:44 PM

I am writing a small low-poly editor using the half-edge data structure (http://www.flipcode.com/articles/article_halfedge.shtml) to store meshes. I wrote a few methods for adding vertices and faces to a mesh but I am wondering how to pair edges (make them point to each other) efficiently. The naive approach is to search thru all previously creates edges when a new open edge is added to look for a neighboring edge using the same vertices. But this is slow and complex. As the number of edges increase the search time explodes in my face. I thought about having a list of open (not yet paired) edges for every vertex and search this list when a new edge is added. This seems somewhat memory consuming and unsatisfying tho. What do you guys think? Is there a better way I completely missed?

 
Angel Popov

May 25, 2005, 05:52 AM

This is what I do, the algho is very simple, short, and efficient enough for my needs.

First all half edges will have a NULL twin
Process all half-edges, for each half-edge see if e->Next->Vertex->HalfEdge is the twin, if so - assign the twins, searh the fan for a half-edge that has a NULL twin and assign it as e->Next->Vertex->HalfEdge

Repeat processing all edges while there is at least one vertex.HalfEdge with a NULL twin. This usually requires a few passes to calculate everything. There are a few ways to make it more optimal

 
Rui Martins

May 25, 2005, 09:03 AM

Two solutions:
- Spacial subdivision, to quickly find the near edges
- Include the definition of edge in the mesh files, so that any poly that share an edge, explicitly mentions which one.
A triangle for example will share 3 edges with neighbour polys.
Each shared edge will be defined only once in the file.
Every edge will have an ID, which the polys refer to.

It doesn't make sense, to lose the connection information when saving to a file format, when you already have that information in the modeller!

 
z80

May 25, 2005, 11:20 AM

Thanks for the input!

I will try your suggestion Angel and see how fast it is and otherwise go with spacial subdivision (or my original idea with a list of open edges per vertex).

Yeah, having the connection information in the file format eliminates re-pairing when loading a model, but when a new object is created with a lot of geometry (a very tesselated sphere for example) the problem is still there, unless the create-new-geometry-tool is able to supply connectivity data (which is probably a nightmare to write).

Right now my mesh class has the following construction interface (no support for supplying edge-edge connectivity data):

  1.  
  2. int InsertVert(const float x, const float y, const float z); /* Returns id of newly created vert -- use in FaceVert() */
  3. int FaceBegin(); /* Returns id of newly created face -- use in FaceVert() and FaceEnd() */
  4. int FaceVert(const int FaceID, const int VertID);
  5. void FaceEnd(const int FaceID);
  6.  

 
Angel Popov

May 26, 2005, 06:30 AM

The algho I posted ( without bothering to look at my implementation) is a bit wrong - obviously there's no way to search the fan without the Twin data.
So - instead of searching the fan and then changing e->Next->Vertex->HalfEdge, I simply assign it to NULL. When processing each edge - it checks whether it's start vert has a NULL half-edge and if so - becomes the half-edge for that vert.

so the final algho looks like this:

  1. do
  2. {
  3.   for( all edges )
  4.   {
  5.     if( edge->Vertex->HalfEdge==NULL )
  6.       edge->Vertex->HalfEdge = edge;
  7.     if( edge->Next->Vertex->HalfEdge->Next->Vertex==edge )
  8.     {
  9.        edge->Next->Vertex->HalfEdge->Twin = edge;
  10.        edge->Twin = edge->Next->Vertex->HalfEdge;
  11.        numTwins++;
  12.        edge->Next->Vertex->HalfEdge = NULL;
  13.        if( edge->Vertex->HalfEdge==edge )
  14.           edge->Vertex->HalfEdge = NULL;
  15.     }
  16.   }
  17. }
  18. while( numtwins!=numedges/2 )
  19.  
  20. for( all edges )
  21.    edge->Vertex->HalfEdge = edge;

 
Angel Popov

May 26, 2005, 07:45 AM

correction:
edge->Next->Vertex->HalfEdge->Next->Vertex==edge
should be
edge->Next->Vertex->HalfEdge->Next->Vertex==edge->Vertex

 
Angel Popov

May 26, 2005, 10:40 AM

and
if( edge->Next->Vertex->HalfEdge->Next->Vertex==edge )
should become
if( edge->Twin==NULL && edge->Next->Vertex->HalfEdge->Next->Vertex==edge )

why is the "Edit Message" link missing now?

 
z80

May 26, 2005, 11:29 AM

Thanks for the code. Haven't implemented it yet in my application but I will try out different approaches.

I think the edit-message-link goes away after a while so you cant mess with messages posted a long time ago with a lot of replies -- would allow you to make people replying look like idiots ;-)

 
This thread contains 8 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.