Surface Extraction from a Linked Simplex Mesh

Intro

The marching methods extract a surface however the surface is not connected and is used for display purposes.

When we want to extract a connected surface the linked simplex mesh seems ideal because it is already connected so the problem becomes much simpler. I am going to talk about this in more depth and explore a couple of algorithms.

Surfaces

For generality lets call any such contour a surface in that dimension. For example in 2D a surface is a curve, in 3D it is a 2D surface and in 4D its a 3D object.

Note however that although the object is one dimension less it is still imbedded in that space. For example while in 3D the surface is 2D the triangles are all in 3D space. From the data structures perspective what is unique is that for any simplex on the surface there is one less link.

Consider a continuous contour of triangles in 3D space. There correspond one-one with the 3D simplex having the contour pass through it, with the exception when the contour intersects one of the simplexes faces. Here logic needs to be implemented to ensure continuity with the surface representation.

Assuming one-one for simplicity then a 2D triangle with three 3D points is used to build the surface.

From an implementational point of view d3tri can represent the mesh. d3tess can hold the tessellation but its methods of drawing are for 2D objects so it would project to the x-y plane by ignoring z. d3tess draws in 3D but uses a 4D object so one of its dimensions would be wasted. Perhaps it is time to look at whats common and separate the display out from the tessellation, or create a new tessellation. The drawing tessellation would then be templated so the tessellation is pluged in.

Algorithm Discussion

Linked simplex produce meshes without holes, so transversing a tessellation is much easier as you do not have to worry about these artifacts.

Constructing a surface can involve iterating over a simplex mesh. Assuming that each point in the mesh has a function value f(X) where X is the point then for a constant value of f(x)=c a contour in 2D or a surface in 3D is produces. Firstly not that this is an object one dimension less than the space it is in.

Then the algorithm I am proposing should have the following spec. Given a contour value and an initial simplex containing the contour point in its bounds (ie Min( f(p[i]) <= c &tl;= Max( f(p[i]) for the initial simplex and its points, iterate from the simplex to any other connected simplex which shares this property, outputing the new mesh as a linked simplex mesh one dimension less than the linked simplex mesh space.

Practical applications of this algorithm are for extracting surfaces from marching simplex algorithms. For example marching cubes is really a special case of marching simplexes. Building a marching simplex mesh then using this algorithm to extract various surfaces from the mesh. The surfaces could be of any shape as they are contours in their dimension. In 3D this could be used to look at skin tissue or bone in a body. The contour is extracted and looked at.

Another Approach

The other way to reconstruct the surface is from the output of a marching method. Assuming that the tessellation has no holes then the problem becomes given this set of triangles (in 3D from a 2D surface), construct the mesh.

Conclusion

Implement both algorithms, this is going to be really interesting.