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.