View source for Proposals:New Mesh Class

This document derives the motivation and implementation of a new Mesh Class and associated Filters and IO classes for ITK


=Overview=

itkQuadEdgeMesh (itkQEMesh) is a new data structure for surface meshes. It is more efficient than the current itkMesh for surface processing. However it cannot handle N-dimensional meshes. Hence itkMesh and itkQEMesh will coexist in future releases of ITK.
This documents describes how itkQuadEdgeMesh will be integrated into ITK 3.4.

=CORE: First Implementation Subtleties=

==1: function vs filters==
Some operations on the QuadEdgeMesh are implemented in Function classes

QuadEdgeMeshFunctionBase is the base class for function objects specialised
in Mesh "small" (reduced in range) modification.
Subclasses of itk::QuadEdgeFunctionBase cannot modify their InputType since
the signature of their Evaluate( const InputType& ) method guarantees it.
Consider a method that modifies (the geometry, the connectivity or both)
a mesh.
For large modifications of this mesh we follow the classical itk Filter
schema (*), which implies duplicating the mesh which can be space consuming.
But for small modifications (think of the Euler operators) that an
algorithm needs to apply many times, this systematic duplication can
be daunting.
QuadEdgeMeshFunctionBase thus offers a leightweight alternative to itk Filter.
Subclasses of QuadEdgeMeshFunctionBase, which should override Evaluate(), are
function objects that apply reduced and localised modifications
(geometry, or connectivity) on the InputType mesh.

The main example is Euler Operators.

(*)It's up to filter's devellopers to use those functions inside the filter and enforce const-correctness.

==2: QuadEdgeMeshCells ==
an itkQuadEdgeMesh uses two types f cells: a QELineCell and a QEPolygonCell.

===Building QE layer===
Both cell types have a constructor that creates the good underlying QE structure. In fact the LineCell always creates it, and is the core cell as far as QE layer is concerned. The polygon cell has several constructors, one of which constructs the underlying QE layer. The destructor check how the cell was created and clean the QE layer if needed. It is needed when one creates a single polygon cell and want to iterate over the PointIds. The creation of the QE layer of a mesh is done elsewhere.
<br>
<br>
The cells are not, by definition, aware of the Mesh. It's thus the mesh that is in charge of creating the overall structure. It is done through the SetCell method. Each cell must be passed over to the mesh, and thus, with a QEMesh, only the dynamic way of creating cells is allowed/possible.
<br>
<br>
The SetCell method actually build the cell and its boundaries. In the case of the Polygon, it mean that the edges of the polygon are also created (as Line Cells) and added to the QEMesh. In this case, the Line Cells create the QE layer, and a polygonal face is "put" on top of it and linked with it (see the PolygonCell constructor that takes a QEType * as argument).
<br>
<br>
You can see SetCell as the conductor and AddEdge() and AddFace() as the main musicians. SetCell is going to check if containers are set, if points are valids, if edges already exist (or it creates them using AddEdge() ), if there is still space to add a face and then creates the face (using AddFace() ), wrap it in an autopointer and put it in the cell container.
<br>
<br>
SetCell( ) accept any type of itkCell / itkQEMeshCell in input. Cells whose dimension is superior to 2 are simply dropped (QEMesh is dedicated to surface meshes). Other cells are imported. Actually, only the points of the cell are used, and a new face is created. It's different from the behavior of an itkMesh where the cells are passed over and directly stored in the container. To be backward compatible, and to avoid memory leaks caused by reusing the autopointer when passing over several cells in a row, itkQuadEdgeMesh::SetCell( ) actually releases the memory of the cell after it created its own copy of it. One should be carefull then: after a SetCell( ) the pointer to the cell is valid with an itkMesh and invalid with an itkQuadEdgeMesh.

===Cell API===
Most of the Cell API (see itkCellInterface.h) has been implemented

==== Local Points container and PointId API ====
Note that for the QECells, the underlying GeometricalQuadEdge is the pointIdContainer. Each QEGeom contains one PointId (it's origin), and all the QEGeom of a given face are linked. An iterator (given by GetGeomLnext( )) allows you to go around. In native QuadEdgeMesh code, this is used in place of the usual unsigned long* as definition of the PointIdsIterator.
<br>
<br>
Unfortunatly, this is not backward compatible with the usual Cell API. If you try to create a cell using the celltraits defined in the itkQuadEdgeMeshTraits, this would fail as the PointIdsIterator would be defined as an iterator on QuadEdges, whereas usual itk Cells do not have a QuadEdge Layer. This case happen everytime you want to use an existing filter that produce a Mesh (let's say, itkVTKPolyDataReader) and use an itkQuadEdgeMesh as OutputType.
<br>
We then splitted the PointIds API into 2 versions: the usual version, which basically returns null pointers, or pointers to something empty (check with the itkQuadEdgeMeshCellInterfaceTest.cxx code), and the QuadEdgeIterator based one, which is prefixed by "Internal" and used an additional type defined in the default QuadEdgeMesh traits as PointIdsInternal Iterator. The first one is used by default and enforce total backward compatibility with existing filters. The later is used within itkQuadEdgeMesh, and should be used by default by any code using only QuadEdgeMesh. 
<br>
<br>
To be fully compliant with the cell API, as far as Points Id iterator are concerned, we implemented a local point container, and thus duplicated the information. This point container is only used for backward compatibility with existing code and is only built when a call to the GetPointIds() method is made. We encourage users that are writing new code to use the Internal*() Methods instead for better memory usage.

==== Cell Boundary Features ====
Right now, the polygon cell Boundary features, type and dimension API are implemented but could be made better. Specifically, the GetType could return different values depending on the number of point, as in a QuadEdgeMesh, all cells but edges are polygons. For the time being, it returns POLYGON_CELL. Get Boundary features returns the number of points, and the number of edges deduced from ... the number of points :). The other Boundary feature interface is not yet implemented.

==3: QuadEdgeMesh==

=== Building QE Layer ===

=== Mesh API ===

==== Cell Links ====

==== Cell Data ====

==== Boundary Assignement ====

==== Boundary Features ====

==== Mesh regions ====

=== New methods ===

==== FreeIndexes ====

==== m_NoPoint and m_NoFace ====

=Mesh to QuadEdgeMesh: Migration guide=

== types ==

=== Points ===
the Default PointType for an QuadEdgeMEsh is a "QuadEdgeMeshPoint" (instead of a "Point"). This pointype inheritate from "Point" and adds a link to the QuadEdge ring and accessors (see the paper for details on edge ring). When you pass a point from an existing mesh to another one, you should be carefull about reseting this link to the correct value.
For exemple a subdivion filter takes a coarse mesh in input and outputs a finer mesh by subdividing the cells. In the triangular case, the output mesh has 4 times more triangles than the input mesh. In such filters, the first step is to copy the input point into the output, without the cells (none of the input cell will be present in the output mesh). During this process the link to the QuadEdge ring should be reset to null.
Existing code:
  PointID pid = 0;
  PointType pointToTransfer;
  InputMesh->GetPoint( pid, &pointToTransfer);
  OutputMesh->SetPoint( pid, pointToTransfer );

Need to be changed into this (for new code):
Existing code:
  PointID pid = 0;
  PointType pointToTransfer;
  InputMesh->GetPoint( pid, &pointToTransfer);
  '''pointToTransfer.SetEdge( NULL );''' // explicitly set the link to NULL
  OutputMesh->SetPoint( pid, pointToTransfer );

or this (backward compatible with "itk::Point"):
  PointID pid = 0;
  PointType pointToTransfer;
  InputMesh->GetPoint( pid, &pointToTransfer);
  '''PoinType localPoint;''' // here the link is set to NULL by the constructor
  '''localPoint[0] = pointToTransfer[0];'''
  '''localPoint[1] = pointToTransfer[1];'''
  '''localPoint[2] = pointToTransfer[2];'''
  OutputMesh->SetPoint( pid, localPoint );

== difference after reading a writing a mesh ==

When importing a mesh, QE creates the edges when missing. For example if you read a triangular mesh from a file, you will then have a mesh made of triangles and edges. It will have more cells. If only one surface of one component, each triangle has 3 edges, each edge is shared between 2 triangles, thus if the original mesh was made of n triangles, the QE mesh will be made of n triangles + 3n/2 edges = 5n/2 cells in the container (and much more Quad Edges in the underlying structure). If you write that mesh directly, you will end up with a different mesh than the one you read.

In the very simple case where you just read then write a mesh from one file, the two files will be different. We plan to come up with a   writer that would only write the edges if they are meaningfull, i.e. if they are "wire" edges, edges that do not have face on the right or on the the left.

=CORE: Review code monitoring=

== 1: Code Coverage and Memory Leaks ==

Reports :
http://www.itk.org/Testing/Dashboard/MostRecentResults-Nightly/Dashboard.html


{|

! ITK/Code/Review Names                       !! Coverage !! # of Lines not covered !! Analyze - Comments
|- 
| itkGeometricalQuadEdge.h                    || 72.22% || 10*|| iterators(9), SetRight(2).
|- 
| itkGeometricalQuadEdge.txx                  || 82.79% || 21 || IsInLnextRing(5), IsLnextSharingSameFace(1), GetNextBorderEdgeWithUnsetLeft(4), InsertAfterNextBorderEdgeWithUnsetLeft(4), ReorderOnextRingBeforeAddFace(5),IsDestinationSet(1), IsRightSet(1).
|-
| ''itkQuadEdge.h''                           || 100.0% || 00 || ---- '''OK'''
|-
| ''itkQuadEdge.cxx''                         || 100.0% || 00 || ---- '''OK'''
|-
| itkQuadEdgeMesh.h                           || 96.55% || 01 || CopyInformation(1).
|-
| itkQuadEdgeMesh.txx                         || 94.77% || 22*|| degenerated cases, splice(11), deleteEdge(2), lightWeightDeleteEdge(2), DeleteFace(3), GetEdge(3), AddFace(1).
|-
| itkQuadEdgeMeshBaseIterator.h               || 77.61% || 15*|| Iterators not used(15) see GeomQE.
|-
| itkQuadEdgeMeshBoundaryEdgesMeshFunction.h  || 66.67% || 01 || TypeMacro.
|-
| itkQuadEdgeMeshBoundaryEdgesMeshFunction.txx|| 88.46% || 03 || InputQE has face left case.
|-
| itkQuadEdgeMeshFrontIterator.h              || 87.50% || 02 || Const flavor of Constructor, Destructor.
|-
| itkQuadEdgeMeshFrontIterator.txx            || 79.07% || 09 || Bad init fall cases, FindDefaultSeed( ).
|-
| ''itkQuadEdgeMeshLineCell.h''               || 100.0% || 00 || ---- '''OK'''
|-
| itkQuadEdgeMeshLineCell.txx                 || 98.85% || 01|| destructor's degenerated cases (1)
|-
| ''itkQuadEdgeMeshMacro.h''                  || ------ || -- || ---- '''OK''' Not Covered - Macros
|-
| ''itkQuadEdgeMeshPoint.h''                  || 100.0% || 00 || ---- '''OK'''
|-
| ''itkQuadEdgeMeshPoint.txx''                || 100.0% || 00 || ---- '''OK'''
|-
| ''itkQuadEdgeMeshPolygonCell.h''            || 100.0% || 00 || ---- '''OK'''
|-
| ''itkQuadEdgeMeshPolygonCell.txx''          || 100.0% || 00 || ---- '''OK'''
|-
| ''itkQuadEdgeMeshTopologyChecker.h''        || 100.0% || 00 || ---- '''OK'''
|-
| itkQuadEdgeMeshTopologyChecker.txx          || 94.74% || 01 || twice genus(1).
|-
| ''itkQuadEdgeMeshToQuadEdgeMeshFilter.h''   || ------ || -- || ---- '''OK''' Not Covered - Not Used yet - tested in creatis
|-
| ''itkQuadEdgeMeshToQuadEdgeMeshFilter.txx'' || ------ || -- || ---- '''OK''' Not Covered - Not Used yet - tested in creatis
|-
| ''itkQuadEdgeMeshTraits.h''                 || ------ || -- || ---- '''OK''' Not Covered - Implicit + only types
|}

= Euler Operators =

==1: Introduction and implementation choices==
The advantage of the QE datastructure is to have only two operators to modify itself. Unfortunatly, the splice operator is not very intuitive (to say the less). Moreover a lot of topology/connectivity/geometry processing filters in the publications are based on the so-called euler operators (operators that do not modify the Euler number of the mesh). Smooth is one example of a geometry filter that does NOT require those operators as it does not modify the connectivity of the mesh, but subdivision, remeshing, simplifying (decimate =>  with a metric, reversible = Progressive Mesh, ...) and many other filters can be moe easily written above Euler Ops.
<br>
<br>
We mimic'ed the API on C-GAL's even though the underlying code is completly different:
http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Polyhedron/Chapter_main.html
Only combinatorial operateors are coded. Genus modifying method or hole/facet handling are not.
<br>
<br>
as for the implementation, we choosed factorization over performance: when an euler operator can be written using other(s), we did it this way, even if we knew it would lead to suboptimal performances (like creating a face to remove it just after). We prefered to keep the code easy to maintain. Good example of this is the SplitEdge function that uses the SPlitVertex function, or the JoinVertex function that uses the (non-trivial) ZipMesh function.

==2: code coverage ==
{|
! ITK/Code/Review Names                       !! Coverage !! # of LNC !! Analyze - Comments
|- 
| ''*./itkQuadEdgeMeshEulerOperatorCreateCenterVertexFunction.h''|| 100.0% || 00 || ---- '''OK'''
|-
|''*./itkQuadEdgeMeshEulerOperatorCreateCenterVertexFunction.txx''|| 100.0% || 00 || ---- '''OK'''
|- 
| ''*./itkQuadEdgeMeshEulerOperatorDeleteCenterVertexFunction.h''|| 100.0% || 00 || ---- '''OK'''
|- 
| ''*./itkQuadEdgeMeshEulerOperatorDeleteCenterVertexFunction.txx''|| 100.0% || 00 || ---- '''OK'''
|- 
| ''*./itkQuadEdgeMeshEulerOperatorFlipEdgeFunction.h''          || 100.0% || 00 || ---- '''OK'''
|-  
| ''*./itkQuadEdgeMeshEulerOperatorFlipEdgeFunction.txx''        || 100.0% || 00 || ---- '''OK'''
|- 
| ''*./itkQuadEdgeMeshEulerOperatorJoinFacetFunction.h''         || 100.0% || 00 || ---- '''OK'''
|- 
| ''*./itkQuadEdgeMeshEulerOperatorJoinFacetFunction.txx''       || 100.0% || 00 || ---- '''OK'''
|- 
| ''*./itkQuadEdgeMeshEulerOperatorJoinVertexFunction.h ''       || 100.0% || 00 || ---- '''OK'''
|- 
| *./itkQuadEdgeMeshEulerOperatorJoinVertexFunction.txx          || 92.16% || 04 || wrong zipfunction return(4) failsafe cases.
|- 
| ''*./itkQuadEdgeMeshEulerOperatorSplitEdgeFunction.h ''        || 100.0% || 00 || ---- '''OK'''
|- 
| ''*./itkQuadEdgeMeshEulerOperatorSplitFacetFunction.h''        || 100.0% || 00 || ---- '''OK'''
|- 
| *./itkQuadEdgeMeshEulerOperatorSplitFacetFunction.txx          || 100.0% || 00 || ---- '''OK'''
|- 
| ''*./itkQuadEdgeMeshEulerOperatorSplitVertexFunction.h''       || 100.0% || 00 || ---- '''OK'''
|- 
| ''*./itkQuadEdgeMeshEulerOperatorSplitVertexFunction.txx''     || 100.0% || 00 || ---- '''OK'''
|- 
| *./itkQuadEdgeMeshFunctionBase.h                               || 66.67% || 03 || TypeMacro, virtual Evaluate
|- 
| *./itkQuadEdgeMeshZipMeshFunction.h                            || 75.00% || 01 || TypeMacro
|- 
| *./itkQuadEdgeMeshZipMeshFunction.txx                          || 77.27% || 05 || No InputMesh, LeftSet, Eric's super special case cases.
|}

{|
! ITK/Testing/Code/Review Names
|- 
| *./itkQuadEdgeMeshEulerOperatorsTest.cxx  
|}

Note: itkTypeMacro => GetNameOfClass( )

==3: Synchronize ITK/Code/Review with Original rep ==
[http://cegs-dart-server.caltech.edu/itkQuadEdgeMesh/Dashboard/ Dedicated Dashboard]

=== KWStyle ===

08/15/07 Now updated at least daily !

- [http://www.creatis.insa-lyon.fr/~agouaillard/itkQE/KWSMatrix.html Matrix]

=== Coverage === 

08/15/07 Now updated every other hour, see dedicated dashboard link above.


=== Mem. Leaks ===

08/15/07 Now both the QuadEdge Code in Review and the Original QE repository at creatis are monitored at least daily. Please see the ITK dashboard and the dedicated dashboard for both results.

= Backward Compatibility, Benchmarks and Examples=

'''IN PROGRESS'''

One should be able to use an itkQuadEdgeMesh anywhere an itkMesh was used for a surface mesh. We wanted the transition to be as easy as just modifying the MeshType. It had two goals: not rewriting existing code (even if it could/should be rewritten to beneficiate of the full power of QuadEdgeMesh) and (we hopped) fasten the filters as buildlinks where not required anymore.

It required the implementation of the (almost) complete Mesh and cell API and thus had an impact on the memory footprint and on the speed. Some features could not and should not be implemented though, like the buildlinks() method (which now does nothing) and the 
CellLinks / PointCellLinks feature that has no longer reason to exist. Thi slast part is not fully implemented right now (august 3rd, 2007).

To test the implementation, and also to benchmark the eventual gains in speed, the best way is  to try every itkMeshSourceFilter that is expected a mesh of dimension equal or inferior to 2 (surface). To help this in progress work, we are going to list here all the filters that are involved and notify everyone when they are included in the test suite / benchmark and successfully using QuadEdgeMesh.

Note: same problem appear in all the tests I am porting: the bool GetPoint( pointinditenfier id& PointType*) that should be imherited from itk::PointSet (through itk::Mesh) is not found.

== Backward compatibility ==

{|
|-
| class name|| Existing Test || New Test || status
|-
|''itkAutomaticTopologyMeshSource'' || ''itkAutomaticTopologyMeshSourceTest''|| ''itkAutomaticTopology'''QuadEdge'''MeshSourceTest'' || '''OK''' ||
|-
| itkBinaryMask3DMeshSource || || || ||
|-
|itkBinaryMaskToNarrowBandPointSetFilter || || || ||
|-
|itkImageToParametricSpaceFilter || || || ||
|-
|-> itkBalloonForceFilter || || || ||
|- 
|''itkConnectedRegionsMeshFilter'' || ''itkExtractMeshConnectedRegions'' || || '''NOT POSSIBLE''' ||
|-
|itkDeformableMesh3DFilter || || || ||
|-
|itkDeformableSimplexMesh3DFilter || || || ||
|-
|itkInteriorExteriorMeshFilter || || || ||
|-
|itkParametricSpaceToImageSpaceMeshFilter || || || ||
|-
|''itkQuadEdgeMeshToQuadEdgeMeshFilter'' || ----- || ----- || '''OK''' ||
|-
|itkSimplexMeshAdaptTopologyFilter   || || || ||
|-
|itkSimplexMeshToTriangleMeshFilter || || || ||
|-
|itkTransformMeshFilter || || || ||
|-
|itkTriangleMeshToSimplexMeshFilter || || || ||
|-
|itkWarpMeshFilter || itkWarpMeshFilterTest || itkWarp'''QuadEdge'''MeshFilterTest || in progress ||
|-
|''itkRegularSphereMeshSource''|| ''itkRegularSphereMeshSourceTest'' || ''itkRegularSphere'''QuadEdge'''MeshSourceTest'' || '''OK''' ||
|-
|itkSphereMeshSource || itkSphereMeshSourceTest || || ||
|-
|-> ''itkVTKPolyDataReader'' || ''itkVTKPolyDataReaderTest'' || ''itkVTKPolyDataReader'''QuadEdgeMesh'''Test'' || '''OK''' ||

|}

to include:
*itkConformalFlatteningMeshFilter  (2)
*itkMeshSpatialObject*Test*        (4)
*testMetaMesh                      
*itkDeformableSimplexMesh3D*       (3)
*itkSimplexMeshVolumeCalculator    
*itkTriangleMeshToBinaryImageFilter (2)
*itkImageToMeshFilterTest
*itkSimplexMeshTest
*itkMeshSourceGraftOutputTest
*itkMeshFstreamTest
*itkFEMGenerateMeshTest

== Benchmarks ==

=== introduction ===
* Some benchmarks were written for the paper and need to be ported. The most important being the speed comparison between atomic operations on the mesh (like deleting an edge). 
* Other benchmarks and comparison were requested by the reviewers and are of interest:
- the time needed to import a mesh in an itk::QuadEdgeMesh compared to an itk::Mesh (we can use itkVTKPolyDataReader for that).<br>
- the respective memory footprint of a cell, a mesh, ...
* Wherever the backward compatibility is achieved, we should compare speed and memory footprint depending on the MeshType.
* Whenever a filter has been rewritten to take advantage of QE (MeshRegion for example) we should provide a comparison.

=== filters to port ===
{|
|-
| name || vizu to remove || file IO to remove || working remotely now?
|-
| MeshBuildLinks || || || yes
|-
| MeshComparativeUpdate || || || yes
|}

=== filters to write ===

== Examples ==

=== filters to port ===

{|
|-
| name || vizu to remove || file IO to remove || working remotely now?
|-
| BackAndForth || || || no - segmentation fault
|-
| CutGraphUsingFront || || || no - DISPLAY error
|-
| CutGraphUsingIterator || || || no - segmentation fault
|-
| DijkstraPrimal || || || no - DISPLAY error
|-
| DiscreteCurvature || || || no - DISPLAY error
|-
| ExtractComponent || || || no - DISPLAY error
|-
| itkQECurvatureFilters || || || no - DISPLAY error
|-
| itkQEDecimateFilters || || || no - segmentation fault
|-
| itkQEGradientField || || || yes no arg case - no -c case - segmentation fault
|-
| itkQEHarmonicField || || || yes no arg case - no -c case - DISPLAY error
|-
| itkQENormalFilters || || || no - segmentation fault
|-
| itkQETest || || || no - DISPLAY error
|-
| itkQETestTraits || || || no - DISPLAY error
|-
| MeshSmooth || || || no - DISPLAY error
|-
| QEMeshToVTKUnstructuredGrid || || || no - DISPLAY error
|-
| TorusSimple || || || no - DISPLAY error
|-
| UniversalCoveringSpace || || || no - segmentation fault
|-
| vtkToItkQEImport || || || no - DISPLAY error
|-
| ivtkUGToItkQEImport|| || || no - DISPLAY error
|}