Mesh Data Structures

After my meeting on Friday and following Tyrones advice, I have been looking into data structures for optimising the storage of my mesh data. My current solution of lookup tables are causing a huge bottleneck probably due to cache inconsitancy, my most recent attempt to speed up things with another lookup table actually brought it to a crawl.

So far I have found 4 structures although I have yet to get access to the papers that describe them indepth.

Winged Edge
A structure comprising of 3 double-linked lists, one each for vertices, edges and faces. It gets it name from the links to 4 adjoining edges from every edge to allow for efficent access to the set of faces surrounding an edge. It doesnt appear to be suitable for use with non-manifold meshes although it may be possible to extend it to handle them.
Bruce G. Baumgart, Winged edge polyhedron representation., Stanford University, Stanford, CA, 1972

Quad Edge
A varient of the winged edge structure, it looks to be capable of handling non-manifold meshes although I will need to examine the source paper to confirm.
Leonidas J. Guibas and Jorge Stolfi, "Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams", ACM Transactions on Graphics, 4(2), 1985, 75-123

Radial Edge
A far more complex representation, natively capable of handling non-manifold meshes. Known to have a large memory overhead.
K. Weiler, "The Radial-Edge Structure: A Topological Representation for Non-Manifold Geometric Boundary Representations", Geometric Modelling for CAD Applications, North Holland, pp. 3-36, 1988.

Partial Entity Structure
A complex storage method capable of dealing with non-manifold and malformed meshes. Improves memory usage over the radial edge method although not to a level competitive with the winged or quad edge methods.
Sang Hun Lee , Kunwoo Lee, Partial entity structure: a compact non-manifold boundary representation based on partial topological entities, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.159-170, May 2001, Ann Arbor, Michigan, United States