After reinvestigating the meaning of manifold meshes, I have found my interpretation to be incorrect. My previous concept of a manifold mesh was a mesh which had no boundary edges (edges which are only attached to a face from one side). This however appears to be incorrect, A mesh is manifold if an edge is shared by either 1 or two faces. This means that I no longer have to worry about my mesh representation being able to support non-manifold meshs since while there inlusion would be nice, it is generally considered bad practice to create non-manifold meshes in the first place. Also various methods for LOD generation are only designed to work with manifold meshes.

As a result of this I intend on starting to implement the Half-Edge mesh representation today as it seems a nice balance between the complexity of implemenation and the connectivity performance benefits it can provide.

Mesh Representation Pt2

Following more research into mesh representations I have come across the Half-Edge format, (Not to be confused with the Half Edge collapse method). It works by considering each edge in the model to actually be composed of two directed edges. For every half edge it then stores links to 1 of the vertices, the face, the next edge and the adjoining half-edge. This allows for very easy access to the local neighbourhood of a vertex, which is very important for operations such as the edge collapse.

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

Progress

This week I have got the max-supporting-plane-distance error metric running, although its very slow and I suspect some flaws as its producing output which is a little to close to that produced by simple distance methods. I have also started on error quadrics but am a bit stumped by the equations.

Long Overdue Update

Last week a succeeded in getting the half-edge collapse operator working, I think I need to put more time into the error metrics now so that I can get it to produce higher quality output and hopefully extend it to perform full-edge collapses. I am currently looking into the maximum supporting plane distance, introduced by Ronfard and Rossignac in 1996, and error-quadrics which is an extension of maximum supporting plane distance developed by Garland and Heckbert in 1997. I hope to have at least one of these methods implemented this week.

I have integrated Nvidia PerfHUD into my viewing application so that I can get profiling data, I decided to use it instead of the Direct3D9 query functionallity do to the simplicity of integration and the automatic visualisation. Because both my home computer and the university computers run on Nvidia graphics cards I felt that being platform dependent wasnt an important factor in my desision.

Tests on my home computer using a scene comprising of 25 very high polygon models have resulted in a frame rate of approximatly 28fps. Substituting the output from my half-edge collapse increased the frame rate to 39fps with only marginal visable loss of detail in the nearest model, this will because I have yet to implement any switching methods so it was just using the lower resolution model.