EXPLOITING TRIANGULATED SURFACE EXTRACTION USING TETRAHEDRAL DECOMPOSITION

Beginning with digitized volumetric data, we wish to rapidly and effic iently extract and represent surfaces defined as isosurfaces in the in terpolated data, The Marching Cubes algorithm is a standard approach t o this problem, We instead perform a decomposition of each 8-cell asso ciated with a voxel into five tetrahedra, Following the ideas of Kalvi n et al, [18], Thirion and Gourdon [30], and extending the work of Doi and Koide [5], we guarantee the resulting surface representation to b e closed and oriented, defined by a valid triangulation of the surface of the body, which in turn is presented as a collection of tetrahedra , The entire surface is ''wrapped'' by a collection of triangles, whic h form a graph structure, and where each triangle is contained within a single tetrahedron, The representation is similar to the homology th eory that uses simplices embedded in a manifold to define a closed cur ve within each tetrahedron. We introduce data structures based upon a new encoding of the tetrahedra that are at least four times more compa ct than the standard data structures using vertices and triangles, For parallel computing and improved cache performance, the vertex informa tion is stored local to the tetrahedra, We can distribute the vertices in such a way that no tetrahedron ever contains more than one vertex. We give methods to evaluate surface curvatures and principal directio ns at each vertex, whenever these quantities are defined, Finally, we outline a method for simplifying the surface, that is reducing the ver tex count while preserving the geometry, We compare the characteristic s of our methods with an 8-cell based method, and show results of surf ace extractions from CT-scans and MR-scans at full resolution.