[Insight-developers] Delete Point Problem in itk::Mesh

[Alexandre GOUAILLARD]

Hi all,

We spotted a problem in itk::Mesh and I copy the discussion on the dev. List
for archives. Luis, more for you below.

The point container in an itk::Mesh can be a map (it *is* a map if you use
the dynamicMeshTraits, or a QuadEdgeMesh trait).

If you read a mesh from a file, the points IDs are going to be consecutive.

If you then delete a Point, this point ID will be "free", i.e. There will
not be any point associated with this ID.

Let's say you then write a file from this mesh, using itkVTKPolyDataWriter.
The points will be written using an iterator on the container, without
respect to IDs. VTK (and many other formats) do(es) not accept non
consecutives IDs. The result will be a shift in the points ID in the file,
whereas the cells will still use the IDs before the shift. The visualization
using vtk will be all distorted whereas there is no problem as far as the
itk::Mesh structure is concerned.

The solution will be to "squeeze" the point container, and modify the
impacted cells before writing the file. The simplest way is to take the last
points of the container to fill the first "gap" in pointsID and modify the
cells accordingly. 

Unfortunatly, with an itk::Mesh you need to make a few traversal of the
points container to find the free ids, and then you need to go through
buildlinks and co to get to know which cells are using this point.

In QuadEdgeMesh, to keep the containers as compact as possible, we
implemented two vectors to hold the free points Id and free Cell Ids. A
delete operation put the free ID in the corresponding vector, an add
operation first check for free IDs to use instead of just adding the point
at the ned of the container.

Before writing the mesh, you can check the size of those vectors to see if
you need to reorder the point container. As the point class for QuadEdgeMesh
as a link to the local neighborhood, modifying the cells to use the new
pointID is trivial. Unfortunatly, the user need to call the appropriate
method before writing. The alternative would require to reorder all the
structure every time you delete a point or a cell which would be an
overkill.

Luis, we do not plan to implement a solution at the itk::Mesh level, but
that would be eventually needed. What I can do is adding several tests in
REVIEW to show the problem, both with itk::Mesh and itk::QuadEdgeMesh to
help whoever will want to address this issue. Would you want that?

Alex.