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.

Following todays meeting I have the following targets for this week

• Create a test scene to ensure my models are of high enough detail to cause noticable frame-rate issues.
• To analyse available profiling tools and intergrate whichever is most suitable into my viewer
• Finish implementation of the half-edge collapse algorithm.

So far I have looked at the support in Direct3D9 and Nvidia PerfHUD for getting profiling data but I am unsure which will provide the most suitable data. To remove the platform specific aspect it would be nice to use Direct3D but the statistics are not as indepth as those provided by PerfHUD so I suspect I may chose the PurfHUD route, This will hopefully allow me to avoid crossover with RTG.

Round up

This week has been far more productive than last week, I have made a start with both the report and the programming. I am just writing overviews for each algorithm at the moment so that I can plan which to implement. I have however decided to press on with some implementation, singling out the half-edge collapse due to its simplisity and the ease which it will allow me to test/debug the error metrics and varying support code.
I have no questions in mind at present for tomorrows meeting.

Follow up

Over the past few days I have been starting to write my report which at the moment mainly consists of overviews of the various methods for generating the level of detail meshs. I have unearthed more algorithms for simplification by the names of Superfaces and geometric optimisation

Kalvin, A and Taylor R. (1996) Superfaces: Polygonal Mesh Simplification with Bounding Error. Proceedings of Computer Graphics and Applications '96, Los Alamitos, California: IEEE Computer Society Press.

Hinker P and Hansen C. (1993) Geometric Optimisation. Proceedings of Visualization '93, Los Alamitos, California: IEEE Computer Society Press.

Tomorrow I hope to begin with the implementation of the Half-Edge collapse. I have decided that it is the logical place to start even if for no other reason than benchmark purposes. While I feel that it isnt going to as suitable as the full edge collapse in the long term, it is very suitable for extending into a full edge collapse at a later point. This will allow me to get over any hurdles with connectivity information and implement some error metrics, before worrying about optimal vertex placement.

Its finally time to start writing the report, Today I hope to have a draft writeup of the techniques I have found so far well underway so that I can use it to compose my thoughts and form a valid argument as to which techniques I should attempt to implement and I what order it will be sensible to do so in. In my head I had just assumed that the Half-Edge Collapse was the correct place to start, just because of its relative simplisity and for helping test error metrics code, however after meeting with Tyrone on thursday I feel that I need to form a stronger argument before I can begin implementation.
The FYP is going to be my focus for the week so I still hope to have some implementation underway by the end of the week but I cannot say which method it will be at the present time.

In other news, yet another technique has popped up from the woodwork by the name of Vertex Remapping (Greg Turk, Re-Tiling Polygonal Surfaces, Siggraph 1992 Conference Proceedings) which works by placing new vertices over the surface of the model and then working out how to link them so that topology is preserved. Points are placed randomly and then are refined with elastic functions to give an even spread, elacticity factors can be set locally for user control of high density regions.

Having spent most of the night looking at papers and working out how to block out the project I dont really have any pertainant questions so tomorrows meeting is going to be very quick indeed, probably focusing on time management skills which I appear to be lacking.

Tonights Plan

My final year project has been taking a back seat recently while i get work done on the group project and my AGS however tonight is dedicated to it and i would like to get started on the offline generation process, This will initially be blocked out with modules for swapping algorithms and error metrics. I will probably need to do some more research into generation of things like adjacency data.

At present I have no questions or anything to really show but hopefully over then next few hours that will change.

Following todays presentations it has been decided that in response to my worries about the usefulness of progressive level of detail in the project area, that my project will be refocused.
Now the progressive LOD aspect of the project has been removed to make way for a fuller evaluation of discrete LOD generation and usage techniques.

In terms of changes to the schedule, I will now be looking to implement 2 more generation techniques (for a total of 3) and to create a simple UI to allow the various parameters to be tweeked without needing to use the command line interface of the generation app directly.

Progress

I have spent most of today finishing off my renderer and camera, its now in a working state ready to demonstrate output from a simplification algorithm. I have also managed to find a good source for what initially appear to be suitable models.

On the research side I have been reading about Cell Collapse and Alpha Hulls as well as how Edge Collapse can be extended for use with progressive level of detail.

I am becoming concerned that it is generally unsuitable to use progressive level of detail for the problem that this project is aimed at, as while I can see a place for it with terrain and building geometry, I fear that the depth of objects will be insufficent to successfully utilise the technique.

I may have to attempt to change my specification to either include the world geometry for a more complete solution to the urban environment LOD problem, or remove progressive meshes so that I can focus on the offline generation of discrete meshes and runtime switching.

Over the weekend I have written a large portion of the renderer and basic support code, I have also managed to source some models from http://archive3d.net which may be suitable for using the finished product.

Meeting Overview 07/11/2008

During the first meeting with Tyrone it has become clear that my specification did not fully describe the target problem which I hope to investigate. I had envisaged only dealing with items in the scene which are supposed to be instanced such as vehicles, pedestrians and generic street furniture, as opposed to the terrain and buildings which I viewed as not being reusable.

Next week I will have to give a short presentation of my initial research. I will be giving a genral overview of some of the offline techiniques for generating the low resolution meshs.

Required Prop List

• Car
• Lorry
• Bench
• Railing
• Lamp post
• Pedestrian
• Low resolution terrain (just to put it all in)
  

Target for next week

• Basic world rendering
• User controlled camera
• Source 3D assets
  

Blog Usage

• Provide full references for everything.
• Record all progress and achievements (with pictures if relevant).
• Post agenda's before and summaries after every meeting.

It Begins

Now that my specification has been finalised and submitted, I have begun to review some of the level of detail(LOD) techniques in use. For this I have been reading Level of Detail for 3D Graphics, ISBN: 1-55860-838-9. The book is providing a very high level overview but most importantly, it has provided me with references to what sound like very promising papers on some techniques for offline LOD generation such as a paper titled Mesh Optimization by Hoppe H, T DeRose, T Duchamp, J McDonald and W Stuetzle from the 1993 SIGGRAPH conference. Over the next week I will try and get copies of these papers and begin reading them.