robust and flexible 3d data structure

Question

I'm looking for a concept to store (in 3 dimensional euclidian space) faces, edges and vertex such that

• information (about relation) isn't duplicated
• queries for adjecent and neighboring faces/edges/vertex are fast
• the mesh is not limited to connected faces of the same winding

definitions

• neighbor of a face: the face that shares an edge with this face
• neighbor of a vertex: the vertex that is on the other end of an edge sharing that vertex
• adjecent edge: an edge that shares the same vertex of an endpoint with this edge

I have considered the Half-Edge data structure, but queries on it only really work when all connected faces have the same winding.

For instance, consider this pseudo code to access such related entities:

face.neighbors #the neighboring faces
face.edges #the edges shared by this face (in the right winding order)
face.verts #the vertex of that face (in the right winding order)
edge.v1, edge.v2 #the two vertex making up an edge
vertex.edges #the edges this vertex shares
vertex.neighbors # the neighbors of this vertex along each shared edge

Answer 1

I would take a look at CGAL, the Computational Geometry Algorithms Library. You might be able to use something directly, or at least get some good ideas. Half-edge sounds like a good idea; in my opinion, you should enforce uniform winding as much as possible. It sounds like you're not interested in that, however.

One idea could be to retain a pair (one element for each winding) in the data structure for a face; this might give you enough flexibility to implement some kind of half-edge-like data structure on top of it, with good efficiency.

Answer 2

I think X3D might be the standard you are looking for.

From wikipedia:

X3D is the ISO standard XML-based file format for representing 3D computer graphics, the successor to the Virtual Reality Modeling Language (VRML) X3D features extensions to VRML (e.g. Humanoid Animation, NURBS, GeoVRML etc.), the ability to encode the scene using an XML syntax as well as the Open Inventor-like syntax of VRML97, and enhanced application programming interfaces (APIs).

There are several free/open source libraries out there to use for it.

Answer 3

Not so much a recommended structure but rather a 3D library used by a pro for computational task that can be built upon.

Michael Garland, a research scientist with NVIDIA Research, have release his graphics library he uses for computational tasks on 3D models and meshes.

• libgfx
• qslim a mesh simplification app based on libgfx (I have personally used it and ported qvis to MacOSX)

Answer 4

If you don't want to be limited to manifold surfaces, winged-edge is it these days. If "data about relation" is really your top priority then I guess you're out of luck.