This week I have been concentrating on writing the disertation. So far I have written the following sections

Research
Analysis (but needs reworking)
Design
Implementation

I hope to write up some of the testing tonight as well as go back to the analysis and improve it.

I think it would be best if tomorrows meeting runs as usual so that what should go in each section of the report can be discused to clarify everything in my mind and so that I can attempt to finish the first draft over the weekend.

This week I have been making slow progress with the report writing and have gotten the 64bit version of the viewer working so that I can profile it in th labs.

Geometry Instancing

Following the meeting with Tyrone this morning I have been evaluating the work required to integrate geometry instancing in to my real-time application. It currently looks like it will require a quite significant juggling of my current draw code to de-layer the way the various LODs are drawn. This is a design flaw of the original implementation and I would like to fix it as it will make the whole system far more flexable but at the moment I am not sure that time will allow for it.

I will move forward with fixing the remaining issues with automatic LOD biasing and add support for automatic distance biasing today before proceeding to the report writing.

Today I have cleaned up the last few issues with the code and made sure all the components interact correctly. I have also created a table of contents for the report along with target word counts for each section to help me focus, hopefully this will get approved in the meeting tomorrow.

I still need to create scripts for the new assets but that is just to improve the visual effectiveness of the product so will be done when I next get some spare time.

Overall im very pleased with the progress this week and I feel my product is far more complete and presentable.

Generator Complete

In another successful day I have managed to write the applet for creating the scripts used to control the offline generation of the discrete LOD levels. It also includes features for testing the model in the viewer by automatically creating a world containing the model and lauching the world as a command line parameter to the viewer.

Viewer Complete

Today marks the completion of the viewing application from a programming standpoint. All known issues have been fixed and it has been polished to a glow. All that remains to do with it is add more model variety.



Hopefully I will be able to get the generator setup app written tomorrow.

Todo List

This week I need to complete the following tasks:
Generator:
Create applet to make simplification scripts.

Viewer:
Add depth biasing.
Add target frame-rate controls.
Add resizing/full screen support.
Fix remaining bugs.
Add more models/variety to the scene.
General polish.

Report:
Contents page and general sections layout.

The wonderful world of Vertex Clustering

This week I have successfully implemented the Vertex Clustering algorithm and I am very surprised at how good the technique is in every respect. It is very fast, works on all geometry and if the grid is setup correctly very good approximations of the original mesh.

I have fixed all the bugs in the viewer that were present last week, although I have introduced another couple I'm my attempt to provide instant switching between versions of the models generated with different techniques.

Next week I will be fixing the remaining bugs in the viewer, creating a simple GUI for generating the command files to control the simplification pre-process and starting the dissertation.

Level of Details on the GPU

From research over the past couple of day s I have identified 2 methods for handling Level of Detail using the Geometry shader provided by Direct3D 10.

The first method is vertex clustering which can be implemented quite efficently and contrary to my previous knowledge on the method is capable of producing meshes of a reasonable quality if run in an incremental fashion. This method would also be applicable to implementation on the CPU.

C DeCoro, N Tatarchuk. Implementing Real-Time Mesh Simplification Using the GPU. ShaderX6.

The second method is to use triangular patchs and control vertex density as required through tessalation, detail can be added with height or displacement maps in the vertex shader.

T Boubekeur, C Schlick. Generic Adaptive Mesh Refinement. GPU Gems 3
GPU Gems 3 http://http.developer.nvidia.com/GPUGems3/gpugems3_ch05.html

I still need to check recent Siggraph proceedings so there may be more to uncover, hopefully I will get time to look into them tonight or tomorrow.

The Good, the Bad and the Iffy

Firstly, I have managed to fix some instances of missing polygons in the Delaunay triangulation which were resulting from QHull not triangulating the simplexes properly.

I have implemented my idea for removing interior polygons but have found that triangles added by the delaunay triangulation are not attaching to existing edges which comes as quite a surprise and is the final nail in the coffin for the Alpha Hulls/Shapes methods unless a revival can be performed tomorrow when talking with Tyrone.

In preparation for moving on I have followed up on the earlier suggestion of progressive meshes, reading papers about view-dependent and view-independent methods as well as the skip strip optimisations to improve performance of mesh changes at run time. While I do believe I understand the processes behind them, I'm not 100% confidant that I have enough time remaining to implement either of them.

I have modified the viewing application to give the user more control over the environment but I have yet to populate the scene sufficently.

On second thoughts

The mesh created by the alpha hull has many holes in the outermost layer, naively removing faces based on surface normals would lead to holes propagating into the model. It is going to be necessary to do something which either seals the holes in the outer layer or remove exposed edges (that arent present in the original model) if I am going to be able to obtain a manifold surface from the mesh.

Alpha Hull?

Following on from last time I have now implemented removal of all edges in the alpha shape which are longer than σ. I have then merged the shape with the previous mesh resulting in:

Im not really sure if this is just an expected result and simply because of a bad value of σ or if there is a bug.

Next I need to find a way of removing the interior polygons, Im thinking that I will need to do something like:

1) build a list of edges from the list of faces (only storing connectivity information to the face that uses it)
2) check for edges with more than two instances
3) use the face normals of all the attached faces to determine the outermost pair

This should leave me with multiple disconnected sets of polygons which I can probably pick between using the bounding boxes, the alpha hull being the largest.

Reversal of fortunes?

I have finally started moving again with what I beleive to be the delauney triangluation of a model computed with the help of QHull.

Next up is to remove edges which are longer than the specified value of σ to form the alpha shape of the set.

Following up on the using an existing library I have found

Qhull, Copyright (c) 1993-2003

The National Science and Technology Research Center for
Computation and Visualization of Geometric Structures
(The Geometry Center)
University of Minnesota

which is available without any requirement to publish source code, unlike CGAL which has the required areas under a Q-Public Licence, requiring all software using it to be published as open-source under the same licence.

More bad news

Things just get worse today with the findings that the lifting map method is pretty much out of the running as a result of accuracy issues when calculating the matrix determinant.

Yuanxin Liu and Jack Snoeyink "A Comparison of Five Implementations of 3D
Delaunay Tessellation"

Its looking likely that the only way any of this is ever going to work is if I make use of an existing library such as CGAL to do all the work.

The Worst Day

Alpha hulls and the material available on them are rapidly defeating me, Looking back on today I have gone round and round in circles trying to understand a standard (rather than my homebrew adhoc) method for creating them. Two general methods I have come across are Alpha Prisms by Jihad El-Sana and Amitabh Varshney, which have stumped me on the computation of the union of their alpha prism representation, and Alpha Shapes by Herbert Edelsbrunner and Ernst P Mucke which makes use of Delaunay Triangulation.

I have looked into 2 methods for computing the Delaunay triangulation of a surface.
Firstly using edge flipping which I understand in 2D but goes to hell in 3D although is posible according to Barry Joe "Constuction of Three-Dimensional Improved-Quality Triangulations using local transformations".
Secondly lifting maps which takes advantage of the knowledge that the convex hull of the 4D representation is when brought back down to 3D equal to the delaunay triangulation. This causes problems with the need to compute the determinant of a 5x5 matrix as well as with the mapping back into 3D space.

I suspect my best chance is the lifting maps route as there should be plenty of information of the matrix computations required and then i just need to find a way of determining the bottom faces of a 4D object for the mapping back to 3D.

I have another day to look at it tomorrow but I cant help but feel it would take a miracle for this stuff to click. Fun Times...

I have now got something working, unfortunatly its currently tending to merge points inside the mesh resulting in nasty errors. I dont expect it to be too hard to test the surface curvature to establish if the merge is occuring outside the model but I havent looked into available methods.

Over the past couple of days I have been trying to understand how Alpha Shapes work over point sets but I have been unable to understand the Delaunley Triangulation theory.

As a result I have set off on my own root implementing it using the Half Edge Mesh structure as a corner stone. Its not currently working due to a bug breaking down the data structure validity however I am confident that with that fixed the method I have devised should be as good as any other method for creating the alpha shape of an object. My theory goes along the lines of

for every vertex
for every other vertex
if in range and not directly connected
Add Edge


however simply adding an edge would break the half edge data structure so when adding an edge it first determines which pair of edges it should join between for each vertex and then proceeds to fold down the triangle bounded by them on each vertex.

these triangles are then joined together to form a base of a prism that is then constructed by adding the edge joining the 2 vertices's and another to edges to triangulate the sides of the prism.

now the mesh is valid again and the algorithm can move on to the next pair.

there is a special case when the vertices's at the bottom of the fold are shared between the vertices's which we wish to join. In that case either the collapse could be ignored, leaving any further passes to deal with it or the shared edge can be moved up to the two vertices's which we want to join, effectively rotating the trough. Processing it may be undesirable if no further passes are going to be run as it may change the silhouette in an undesirable manner.

While I'm not currently handling the special case, I hope to have the validation bug fixed tonight so it can be seen in action and a decision on what to do next can be made tomorrow.

Todays task is to restart implementing Alpha Hulls. After thinking about it, the only difference between Alpha Shapes in a point set (where there is no prior knowledge of connectivity) are the links which are seperated by a distance greater than alpha. As a result it should be possible to treat the data as a point set and then pass over the dataset afterwards reinstating links that are larger than alpha. This may result in an increased number of internal faces but analysis of surface curvature should allow for relativly simple removal of these cases.

New paper.
Three-dimensional Alpha Shapes (1994)

Herbert Edelsbrunner, Ernst P. Mücke
ACM Transactions on Graphics

A week in review

This week I have been working on the model switching in the real time component. It is currently working based on distance from the camera which it evaluates just before drawing, this also provides data for if the object is behind the viewer under which circumstances I dont even attempt to draw it.

A file is automatically generated when the various LOD meshes are computed so that everything can be handled automatically behind the renderer interface. Ultimatly it would be nice to integrate an image metric into the generation stage so that switching distances can be computed automatically instead of relying on user input. It may be a suitable alternative to work it out as a function of triangle reduction against size however I have yet to try this.

On the Alpha Hulls front I have found only a single paper which might provide an insight into implementation of the technique, it is however an algorithm designed to working on 2D raster sets.
Tightening: Curvature-Limiting Morphological Simplification.
Jason Williams and Jarek Rossignac.
Sketch in the ACM Symposium on Solid and Physical Modeling (SPM). pp. 107-112, June 2005.

Update

Just a quick post to say that currently my attempt at implementing Alpha Hulls is a long way from running. I have also located a backup of my old mesh/adjacency although I have yet to gather any statistics on its run time.

So I guess I need to just keep plugging along with my implementation, currently blocked out as

1. Look for hard edges (connected face normals seperated by > 70 degrees)
2. Compute the alpha prisms
3. Create a lookup for vertices sorted by position into a grid with cells (2*m_alpha) x (2*m_alpha) x (2*m_alpha) This is really just an optimisation to reduce searches to a subset
4. Sort edges into sets of directed strips
5. Check for contacts
6. Add and remove edges identified by contacts.

Im still not sure that I fully understand how to check for contacts such that it resolves to the correct point so maybe you have some thoughts on it Tyrone, either way it could be something to discuss.

Alpha Hull Simplification

Having spent many hours reading various versions of "Topology Simplification for Polygonal Virtual Environments" by Jihad El-Sana and Amitabh Varshney, I have to say I'm completely stumped by how to implement this.

In general I understand the technique as running a sphere of a specified radius over the surface and anywhere that the sphere cannot reach is removed, reconnecting the mesh at the vertices's which prevented the sphere getting to the point.

I also understand that the sphere can be reduced to a point by extending the faces along there normals by the a length equal to the sphere radius, this reduces the computational complexity.

By using the bit field method proposed in the aforementioned paper it is possible to compute the union of a collection of extended faces (referred to as alpha-prisms), and that's where I get stuck.

How should faces be selected for adding to the union to create meaningful simplification?
For CAD geometry used in the samples they used the expectation of hard edges to generate edge lists that could be checked, however I would expect the more subtle changes in a sufficiently hi-resolution model of most objects.

*edit*
I guess I'm looking at my idea of usage wrongly, I had always thought of alpha-hull being a complete simplification algorithm but really its just for removing holes or defined pits (as opposed to shallow details) so that another algorithm can work more effectively. While it generally does remove faces when closing holes it will usually be minimal in comparison to proper geometry simplification methods.

Today I have been implementing Error Quadrics for Full Edge collapse support, I was originally intending on having it done before Christmas so that I could begin looking at Alpha Hulls but that plan fell to pieces due to many problems with implementing the Half Edge mesh data structure.

Everything appears to be working when using relatively small reductions (11000 -> 4000 triangles) but when I tested on a larger model many errors started creeping in. This is probably due to how im accumulating error but I havent had time to look into it yet.

No doubt this mornings meeting will be short as im not currently stuck with anything and I have targets left over from christmas to keep working towards.