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?

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

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!

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):

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:

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

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?

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 ;-)