Quote:Original post by robotichrist
Probably your best bet is to use a winged edge data structure. This requires a bit more book keeping, but for the types of queries you just described it is provably optimal.

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/model/winged-e.html

Quote:Original post by snk_kid
We're already using a structure that provides similar information to winged-edge but the mapping of vertex index to a list of edge indices that a vertex is connected to is not ordered (or in an order i need) besides these structures are actually too bloated and expensive for what i'm working on at the moment (subdivision surfaces using catmull-clark with various extensions).

I've already decided earlier on I'm going to change the structures where using for something more simple yet flexible enough and more efficient like Vertex-Vertex Systems.

void traverseVerts(Vertex v){	Edge start_edge = v.edge;	Edge cur_edge = start_edge;		do	{		if(cur_edge.start == v)		{			visit(cur_edge.end);						cur_edge = cur_edge.left.next;		}		else		{			visit(cur_edge.start);					cur_edge = cur_edge.left.prev;		}		} while(cur_edge != start_edge)}

Quote:Original post by robotichrist
I've never heard of vertex-vertex systems, but they sound interesting. If you can send a link or a pointer to an article, I'd like to find out more.

Quote:Original post by robotichrist
I really don't understand why a winged-edge/half-edge structure would be so bad. The overhead is only O(1), compared to something like a vertex-array.

Quote:Original post by robotichrist
They even work well with GPUs, since the vertices can be cached within vertex buffer objects.

Quote:Original post by robotichrist
Edge-based data structures are ideal for subdivision surfaces.

Quote:Originally from Subdivision for Modeling and Animation, page 105

... A variety of representations were proposed in the past for general meshes of this type, sometimes with some of the assumptions relaxed, sometimes with more assumptions added, such as orientability of the surface represented by the mesh.

These representations include winged edge, quad edge, half edge end other data structures. The most common one is the winged edge. However, this data structure is far from being the most space efficient and convenient for subdivision.

First, most data that we need to store in a mesh, is naturally associated with vertices and polygons, not edges. Edge-based data structures are more appropriate in the context of edge-collapse-based simplification. For subdivision, it is more natural to consider data structures with explicit representations for faces and vertices, not for edges...

Quote:Original post by robotichrist
That said, they do have limitations. While winged edge data structures are generally quite fast, they are extremely painful to program. I personally try to avoid them since I find them difficult to debug, and usually more trouble than they are worth. Constructing and modifying them is especially difficult, since it is almost impossible to follow what is going inside these things half the time.

Quote:Original post by The Reindeer Effect
what is a 1-ring? i've never heard that term before

I'm just guessing you might mean a circle... if that is the case the standard topological term is 1-sphere (if you really dont feel like saying circle)

Quote:Original post by killah
Hi snk_kid, I just wanted to know which solution do you finally use for the 1-ring construction because I've got similar problems.

At first I tried to use OpenMesh library (http://www.openmesh.org) which implements a halfedge data structure, but each time I had problems with it I didn't find support anywhere... only the OpenMesh site documentation, no forums, nothing... I think that I could do this with simpler structures but I'm not sure how...

Well, can you explain me how you finally did it? is a good solution projecting the points to the best fitting plane and sort them as you said?

Thank you very much