Tuesday, 13 January 2009

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.

No comments: