[Insight-users] Polygonization algorithms, Marching Triangles

[Dan Mueller]

Hi Insight-users,

Our group is interested in comparing polygonziation algorithms. By
polygonization I mean algorithms which convert an implicit surface
embedded in a scalar volume to a mesh. We are specifically interested
in so-called "adaptive" algorithms, which produce a mesh consisting of
variable-size polygons based on some criteria (such as curvature).

Obviously ITK already includes the Marching Cubes [1] algorithm within
Algorithms/itkBinaryMask3DMeshSource. Together with
Review/itkQuadEdgeMeshDecimationFilter I understand it is possible to
generate adaptive polygonizations. But surely it would be more
efficient/faster to go straight from the volume to an adaptive mesh,
without the intermediate decimation step?

Anyhow, to investigate such matters we obviously need to
source/implement other polygonization algorithms. The first algorithm
we wish to focus on is Marching Triangles [2] (or at least one of its
more recent/improved derivations [3]).

Question 1: Is there an existing ITK Marching Triangles implementation
out there? From my understanding there is not one in the existing code
archive, or submitted to the Insight Journal. Perhaps there is one
hidden in the NAMIC Sandbox? Or some discarded student project
collecting the digital equivalent of dust on someone's hard drive?

Question 2: I am surprised Marching Triangles has not been previously
included in the toolkit. Is this because of lack of
time/motivation/interest? Or perhaps some other more frustrating
issue, such as "intellectual property" (ie. patent)? I did a cursory
patent search, but did not turn up anything...

Thanks for any advice/pointers.

Cheers, Dan

[1] Lorensen and Cline, Marching cubes: A high resolution 3D surface
construction algorithm, Proceedings of the 14th annual conference on
Computer graphics and interactive techniques, pp 163 - 169, 1987

[2] Hilton, Stoddart, Illingworth and Windeatt, Marching triangles:
range image fusion for complex object modelling, Proceedings.of the
International Conference on Image Processing, pp. 381-384, 1996
http://personal.ee.surrey.ac.uk/Personal/A.Hilton/research/mt/hilton-mt-97.pdf

[3] Akkouche andc Galin, Adaptive Implicit Surface Polygonization
Using Marching Triangles, Computer Graphics Forum Volume 20 Issue 2,
pp. 67-80, 2002
http://www.ann.jussieu.fr/~frey/papers/scivi/Akkouche%20S.,%20Adaptive%20implicit%20surface%20polygonization%20using%20marching%20triangles.pdf