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...