Proposals:New Mesh Class: Difference between revisions

From KitwarePublic
Jump to navigationJump to search
No edit summary
 
(129 intermediate revisions by 2 users not shown)
Line 1: Line 1:
This document derives the motivation and implementation of a new Mesh Class and associated Filters and IO classes for ITK
This document derives the motivation and implementation of a new Mesh Class and associated Filters and IO classes for ITK


This page is not maintained anymore and as of 2010, the news developments are documented [http://www.itk.org/Wiki/ITK_Release_4/QuadEdgeMesh_Filter here]


=Overview=
=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.
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.2.
This documents describes how itkQuadEdgeMesh will be integrated into ITK. We are aiming at ITK 4.0, Q4 2008.  


=First Implementation Integration issues=


Here are the current issues
The development started in 2004 by Dr. Leonardo V. Florez which coded a first prototype with help from Eric Boix. By 2005 Dr. Florez prorities shifted (see commit log here:http://www.ohloh.net/projects/8458/contributors) and the project has been since kept alive by Dr. Alex. Gouaillard and Dr. Eric Boix (see same page). The project has been packaged and submitted to Insight Journal late 2006 with help from Matthieu Malaterre ( see http://hdl.handle.net/1926/306). Accepted in ITK early 2007, it is currently in the Review subdirectory. Lot of work has been done since, mainly on adding euler operators, improving the robustness (testing, coverage, ...) the speed and coding some higher level filters to test he structure (parameterization http://hdl.handle.net/1926/1315, decimation, smoothing, ...). The latest filters are mainly developed by Dr. Arnaud Gelas. All this work was initiated at CREATIS laboratory in France to which ALl the above mentioned individual were belonging at one point.
 
 
 
The main contact for this structure, filters and page is currently alex. gouaillard (agouaillard /at/ gmail.com).
 
=CORE: First Implementation Subtleties=


==1: function vs filters==
==1: function vs filters==
01/23/07 <br>
Some operations on the QuadEdgeMesh are implemented in Function classes
Operations in the QuadEdgeMesh are implemented in Function classes
 
That derive from FunctionBase. We see your point on externalizing the methods
QuadEdgeMeshFunctionBase is the base class for function objects specialised
from the QuadEdgeMesh, that's certainly compatible with the general ITK design.  
in Mesh "small" (reduced in range) modification.
In your paper you explain that you preferred to use Functions instead of Filters
Subclasses of itk::QuadEdgeFunctionBase cannot modify their InputType since
in order to save memory. That is, to make changes in-place, as opposed to
the signature of their Evaluate( const InputType& ) method guarantees it.
creating a copy of the mesh as output to a filter. That's a reasonable argument.  
Consider a method that modifies (the geometry, the connectivity or both)
I would suggest that we keep the function classes but we also offer them in the  
a mesh.
form of filters that allow to support const-correctness. Using the data-pipeline is  
For large modifications of this mesh we follow the classical itk Filter
also compatible with the VTK design.
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>
<br>
<br>
update 01/24/07: eric <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.
Providing those additional filters could be implemented as wrappers
around the function classes (with an additional copy of the mesh) which shouldn't
be too expensive to maintain. Thus support of const-correctness could thus be
cheap.
 
==2: inheritance vs link==
01/23/07 <br>
QuadEdgeMeshLineCell deriving from the GeometricQuadEdge.
This is a bit of a conceptual problem. I would suggest that we remove the  
inheritance from the QuadEdge, and replace it with the LineCell having a  
reference to the first GeometricQuadEdge of the local ring. The LineCell
may provide a method such as (for example) GetFirstQuadEdge(), that
will return a reference to the QuadEdge, and from that QuadEdge we could
continue navigating the local topology.
From the design point of view (and even the topology) it seems more
appropriate to say that : <br>
"The LineCell *has* a reference to a QuadEdge" <br>
than to say that <br>
"The LineCell *is* a QuadEdge"<br>
in particular, considering that the LineCell is the equivalent of the
"Physical Edge". 
The template parameter of the GeometricQuadEdge,
still allows you to associate data with the QuadEdge.  
<br>
<br>
<br>
<br>
update 01/24/07: kitware<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).
Trying to elaborate on the reasons for having the  
LineCell to derive from the GeometricalQuadEdge,
we are wondering if you intended the LineCell to
be oriented.  Was that part of your motivation ?
We are suggesting to remove the inheritance of
the LineCell from the GeometricalQuadEdge, and
instead have the LineCell keep a pointer to the
first of the 4  QuadEdges that will be created by
the MakeEdge() method. Similar to how the
PolygonCell is doing.<br>
<br>
<br>
Update 01/24/07:Eric <br>
The problem if you switch from inheritance to aggregation seems that you loose the coupling of the
two objects. Consider a filter (or function class) that operates at the QuadEdge
level and is written at this level (and we do this all the time). Then in order to
the have the LineCell refering to the concerned QuadEdge to be modified in the proper way
we would thus need to promote this code at the LineCell level (because a
QuadEdge wouldn't "know" of the LineCell). This would make things much harder to
write no ? You would need to navigate back and forth between the itk and QuadEdge level
in order to keep them synchronized. Wouldn't you ?
<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>
Update 01/24/07:leo<br>
When this code was written, Eric's explanation was right. It seemed very
hard to make these two data structures (QE and cell-based meshes)
compatible. As I just wrote to you, I'm working on solving this
problem, but I haven't had the time to finish it.
<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>
Update 01/24/07:leo<br>
It seemed simpler to do this to get the QE architecture working under a cell-based interface. Now, knowing
a little bit more itk's architecture, I know that we can avoid this double derivation.
I started working on this issue, but I haven't had time to finish it. Do you think it would be
interesting to continue working on this? I hope to have some time starting
next week.
<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>
<br>
Update 01/25/07:Luis<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.  
Yes, we think that it is worth to remove the double derivation.
We are heading now to have the LineCell have
a pointer to the first QuadEdge of the 4-tuple.
It will also have the MakeEdge() method, to
be called from the constructor. The MakeEdge()
in the GeometricalQuadEdge will be removed.
<br>
<br>
<br>
<br>
Update 01/25/07:leo<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.
The idea I've been developing is quite similar to Luis' suggestions.
 
In fact, I've created a new CellInterface class that "keeps track" of
==== Cell Boundary Features ====
QEs (by aggregation). I've tested this new implementation taking
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.
"native" itkMesh examples, changing just the template's instantiation
 
and running them. So far, it works fine. Right now, I'm completing
==3: QuadEdgeMesh==
this implementation in order to cope with all CellInterface methods. I
 
hope there will not be further suprises.  
=== Building QE Layer ===
The other idea I'm developing is related to dual meshes. The idea is
 
to keep track, at the same time, of the primal and dual mesh. I hope
=== Mesh API ===
to use this new representation to simplify simplex mesh-based
algorithms, but I'm sure there are more applications to this.


==3: Error management ==
==== Cell Links ====
01/23/07 <br>
There is not enough error management in the code.
For example, there are methods implemented as


              ->GetRot()->GetRot()->GetRot()
==== Cell Data ====


that rely on the assumption that none of the intermediate
==== Boundary Assignement ====
calls return a null pointer.
 
We are moving all these methods from the header file
==== Boundary Features ====
into the .cxx file, and inserting error management in them.
 
The basic principle is that no method should crash.  
==== Mesh regions ====
We can do error management by returning  null pointers
 
in the intermediate cases, or by throwing exceptions.
=== New methods ===
The unit test should be such that any method could be
 
called in any order, without making the class crash. <br>
==== FreeIndexes ====
<br>
 
Update: 01/24/07: Eric<br>
==== m_NoPoint and m_NoFace ====
Fair enough. But we have the structural guarantee that this won't happen, since the
 
edge algebra can NOT be corrupted IF you only manipulate it through Splice().
==4: Performance==
The only way (I can foresee) for your null pointer scenario to happen would
 
be some exterior corruption of the data structure.
=== Checking half of the word out there ===
Actually QuadEdge.SetRot() and it's SetOnext() counterpart shouldn't be public
For the time being, performance of QE are still being assessed. It seems that QE is still slower than itk::Mesh and than vtk. The main reason for that is that QuadEdge is double checking everything. We are currently working on making QE faster, only allowing double-checks for the Debug version.
(are they actually are) but strongly restricted. If you look closer, you should see
 
no occurence of SetRot() except for the constructor and you shouldn't
=== creating cells twice ===
find any occurence of SetOnext() except for the constructor and Splice().
when using the traditionnal way of creating cells(namely, creating the cells, wrapping them in an auto-pointer and feeding the mesh with them) QE create a new cell, and dispose the first one. The best way is to directly use the AddFace / AddEdge method to avoid that.  
How could you thus break the edge-algebra ?
 
We might also want to create a QE memory pool, where the QE would not be erased but stored. It would make sense as QE as the most numerous elements in the mesh  (4 by edge !) and will likely to be destroyed/created often, leading in a lot of memory allocations and possibly memory fragmentation (see recent work on firefox 3).  
 
In C-GAL, the 4 QE are allocated in a continuous block of memory and accessed through pointer arithmetic, as each QE is of fixed size. I think the pool allocation work would make a lot of sense for subdivision filters for example.
 
=== Secure Copying ===
We also separated AddFace and AddEdge in a "secure" and a normal one. The normal one checks everything and then call the secure one. When creating a mesh, you might want to check existence of the points (even though vtk or itk does not), orientation and a few other things. But when copying an already existing QEMesh, all those test are redundant. We achieve almost 35% improvement in copy speed.
 
We should investigate copying the entire cellContainer at a time, but right now the QE layer can not be copied directly. The QE container/pool discusssed above could make sense here too.
 
=Mesh to QuadEdgeMesh: Migration guide=
 
== types ==
 
=== Points ===
 
==== Creation of a new point ====
 
the Default PointType for an QuadEdgeMEsh is a "QuadEdgeMeshPoint" (instead of a "Point"). This PointType inheritates 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 careful about resetting this link to the correct value.
For example a subdivision 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 );
 
==== Changing geometry of an existing point ====
 
When changing the geometry of an existing point, it is important to be careful that the link to the QuadEdge remains unchanged. This can actually be done in two ways:


==4: Coding style: Method renaming==
* Direct change of coordinates
01/23/07<br>
PointID pid = 0;
We will expand the current abridged names of methods, and
PointType pointToTransfer; // here the link is set to NULL by the constructor
for reference we will leave the original name in the Doxygen
PoinType localPoint; // here the link is set to NULL by the constructor
documentation, so that users can refer to the terms used in
... 
the paper.
... // modify localPoint coordinates
...
InputMesh->GetPoint( pid, &pointToTransfer); // here pointToTransfer got the link from InputMesh point
// change the coordinates of pointToTransfer
pointToTransfer[0] = localPoint[0];
pointToTransfer[1] = localPoint[1];
pointToTransfer[2] = localPoint[2];
OutputMesh->SetPoint( pid, pointToTransfer );


==5: allocation without desallocation==
* Though the creation of a new point
01/23/07 <br>
PointID pid = 0;
The QuadEdges that are allocated in the MakeEdge() method
PoinType localPoint; // here the link is set to NULL by the constructor
in the LineCell and in the GeometricalQuadEdge (formerly QEGeom),
...
...where are they deallocated ?
... // modify localPoint coordinates
We couldn't find any calls to the "delete"s that should match
...
these "new".
  localPoint->SetEdge( InputMesh->FindEdge( pid ) ); // copy the link from InputMesh point to localPoint
We are suggesting to add the deletes to the destructor
OutputMesh->SetPoint( pid, pointToTransfer );
of the GeometricalQuadEdge<br>
<br>
update 01/24/07: eric<br>
Doing so (i.e. removing the LineCell::MakeEdge() method) makes almost all the
atomic tests of our test-suite to SegFault ! I know this looks kludgy (since LineCell::MakeEdge() seems to overload the QuadEdge::MakeEdge() while the codes are being almost the same) but is has to do with the fact that we
wanted LineCell and QuadEdges to be tigthly coupled. And we couldn't come with a cleaner way of hooking things in order to obtain the proper result in the LineCell constructor (the only time I tried, I failed poorly).
<br>
<br>
Update 01/24/07: leo<br>
Yep. Coupling QE's and cells forced a reimplementation of MakeEdge()
in order to construct edges with the right types (primal and dual).


==6: Reimplementation of MakeEdge()==
== difference after reading a writing a mesh ==
01/23/07 <br>
Why is MakeEdge() reimplemented in the LineCell ?
if it derives from the GeometricalQuadEdge and the
method already exist in that class ?
We are suggesting to remove the MakeEdge() method
from the LineCell. <br>
<br>
Update 01/24/07:eric <br>
LineCell appeared quite late in the coding process (yes, we do such things) and
were just introduced for compatibility with itk::Mesh. LineCells are not oriented.
QuadEdges are.
<br>
<br>
Update 01/24/07: leo<br>
They are not oriented. The problem comes from the
desire to make QE's and cells working together with the same syntax.
As I already wrote, I'm working on solving this.


=Second implementation=
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.


==1: Done==
* LineCell does not inherit from QuadEdgeGeom anymore
* LineCell has a pointer to a QuadEdgeGeom
* LineCell constructor creates the 4 QE
* QuadEdgeGeom keeps memory of the identifier of the LineCell in the mesh container (to be able to delete the edge)
* MakeEdge() methods removed
* two macro removed
* LineCell Destructor deletes the 4 underlying QE
* all direct creation of QuadEdgeGeom should be prohibited, and replaced in the actual code by LineCell creation
* Polygon constructor creates the needed LineCells.
* adress the iteratorMacro
It's working and the test suite passes.


==2: To be Done??==
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.
* QuadEdgeGeom constructor is made private and can only be called by LineCell ?
* QuadEdgeGeom smart initialization to prevent misuse (sym = NULL) ?
* actually delete the EdgeCell in LightWeightDeleteEdge ?


==3: Merging in ITK/review==


'''As of june 27th 2008, the Core is in ITK Review'''
The itkVTKPolyDataWriter class, currently in Review, will skip the edges and only write the triangles. It is currently the suggested filters for writing PolyData.


Changes were made in the code both in the original CVS repository ( cvs -d :pserver:anonymous@cvs.creatis.insa-lyon.fr:/cvs/public/ itkQuadEdgeMesh ) and in the version that was imported in ITK ( /Review of the CVS version of ITK ).
=CORE: Review code monitoring=


* in /Review, class and method names may have changed. Macro may have been displaced.
== 1: Code Coverage and Memory Leaks ==
* in creatis' cvs rep., the second implementation was done.


It matters now to merge everything.
Reports :
the second implementation will be first merged into the ITK/Review, then validated by several individuals, and finally merged back to the Creatis' rep. There will be a migration effort to be made for the existing filters to work (Euler Operators, recoded vtk filters and so), then everything will be ready for inclusion in a further version of ITK.
http://www.itk.org/Testing/Dashboard/MostRecentResults-Nightly/Dashboard.html




{|
{|


! ITK/Code/Review Names                     !! original CVS Names
! ITK/Code/Review Names                       !! Coverage !! # of Lines not covered !! Analyze - Comments
|-
| itkGeometricalQuadEdge.h                    || 80.00% || 9*|| iterators(9).
|-
| itkGeometricalQuadEdge.txx                  || 78.99% || 25 || IsInLnextRing(5), IsLnextSharingSameFace(1), GetNextBorderEdgeWithUnsetLeft(4), InsertAfterNextBorderEdgeWithUnsetLeft(4), ReorderOnextRingBeforeAddFace(5),IsDestinationSet(1), IsRightSet(1).
|-
|-
| itkGeometricalQuadEdge.*                  || itkQEQuadEdgeGeom.*
| ''itkQuadEdge.h''                          || 100.0% || 00 || ---- '''OK'''
|-
|-
| itkQuadEdge.*                            || itkQEQuadEdge.*
| ''itkQuadEdge.cxx''                        || 100.0% || 00 || ---- '''OK'''
|-
|-
| itkQuadEdgeMesh.*                        || itkQEMesh.*
| itkQuadEdgeMesh.h                          || 96.55% || 01 || CopyInformation(1).
|-
|-
| itkQuadEdgeMeshBaseIterator.*             || itkQEBaseIterator.*
| itkQuadEdgeMesh.txx                        || 94.77% || 22*|| degenerated cases, splice(11), deleteEdge(2), lightWeightDeleteEdge(2), DeleteFace(3), GetEdge(3), AddFace(1).
|-
|-
| itkQuadEdgeMeshBoundaryEdgesMeshFunction.*|| itkQEBoundaryRepresentativeEdgesMeshFunction.*
| itkQuadEdgeMeshBaseIterator.h              || 77.61% || 15*|| Iterators not used(15) see GeomQE.
|-
|-
| itkQuadEdgeMeshFrontIterator.*            || itkQEFrontIterator.*
| itkQuadEdgeMeshBoundaryEdgesMeshFunction.|| 66.67% || 01 || TypeMacro.
|-
|-
| itkQuadEdgeMeshLineCell.*                || itkQELineCell.*
| itkQuadEdgeMeshBoundaryEdgesMeshFunction.txx|| 88.46% || 03 || InputQE has face left case.
|-
|-
| itkQuadEdgeMeshMacro.h                   || itkQEMeshMacro.h
| itkQuadEdgeMeshFrontIterator.h             || 87.50% || 02 || Const flavor of Constructor, Destructor.
|-
|-
| itkQuadEdgeMeshPoint.*                    || itkQEPoint.*
| itkQuadEdgeMeshFrontIterator.txx            || 79.07% || 09 || Bad init fall cases, FindDefaultSeed( ).
|-
|-
| itkQuadEdgeMeshPolygonCell.*              || itkQEPolygonCell.*
| ''itkQuadEdgeMeshLineCell.h''              || 100.0% || 00 || ---- '''OK'''
|-
|-
| itkQuadEdgeMeshTopologyChecker.*          || ?
| itkQuadEdgeMeshLineCell.txx                || 98.85% || 01|| destructor's degenerated cases (1)
|-
|-
| itkQuadEdgeMeshToQuadEdgeMeshFilter.*    || /BasicFilter/itkQEMeshCopy.*
| ''itkQuadEdgeMeshMacro.h''                  || ------ || -- || ---- '''OK''' Not Covered - Macros
|-
|-
| itkQuadEdgeMeshTraits.h                   || itkQEMeshTraits.h
| ''itkQuadEdgeMeshPoint.[h/txx]''                  || 100.0% || 00 || ---- '''OK'''
|-
| ''itkQuadEdgeMeshPolygonCell.[h/txx]''            || 100.0% || 00 || ---- '''OK'''
|-
| ''itkQuadEdgeMeshTopologyChecker.h''        || 100.0% || 00 || ---- '''OK'''
|-
| itkQuadEdgeMeshTopologyChecker.txx          || 94.74% || 01 || twice genus(1).
|-
| ''itkQuadEdgeMeshToQuadEdgeMeshFilter.h''  || 33.00% || 02 || NewMacro(1), TYpeMacro(1).
|-
| ''itkQuadEdgeMeshToQuadEdgeMeshFilter.txx'' || 100.0% || 00 || ---- '''OK'''
|-
| ''itkQuadEdgeMeshTraits.h''                || ------ || -- || ---- '''OK''' Not Covered - Implicit + only types
|}


== 2 filters ==
{|
! ITK/Code/Review Names                      !! Coverage !! # of Lines not covered !! Analyze - Comments
|-
| ./itkQuadEdgeMeshBorderTransform.h ||  100.0% || 00 || -----'''OK'''
|-
| ./itkQuadEdgeMeshBorderTransform.txx ||  99.25% || 01 ||
|-
| ./itkQuadEdgeMeshCleanFilter.h || 90.48% || 06  ||
|-
| ./itkQuadEdgeMeshDecimationCriteria.h || 89.29% ||03 ||
|-
| ./itkQuadEdgeMeshDecimationFilter.h || 86.96% || 03 ||
|-
| ./itkQuadEdgeMeshDecimationQuadricElementHelper.h || 98.21% || 01 ||
|-
| ./itkQuadEdgeMeshDelaunayConformingFilter.h || 86.49% || 05 ||
|-
| ./itkQuadEdgeMeshDelaunayConformingFilter.txx || 83.33% || 12 ||
|-
| ./itkQuadEdgeMeshDiscreteCurvatureEstimator.h || 93.30% || 01 ||
|-
| ./itkQuadEdgeMeshDiscreteCurvatureTensorEstimator.h ||  ||  ||
|-
| ./itkQuadEdgeMeshDiscreteGaussianCurvatureEstimator.h ||  90.48% ||  02 ||
|-
| ./itkQuadEdgeMeshDiscreteMaxCurvatureEstimator.h || 85.71% || 01 ||
|-
| ./itkQuadEdgeMeshDiscreteMeanCurvatureEstimator.h || 96.30% || 01 ||
|-
| ./itkQuadEdgeMeshDiscreteMinCurvatureEstimator.h || 85.71% || 01 ||
|-
| ./itkQuadEdgeMeshDiscretePrincipalCurvaturesEstimator.h || 96.97% || 01 ||
|-
| ./itkQuadEdgeMeshEdgeMergeDecimationFilter.h || 52.00% || 120 ||
|-
| ./itkQuadEdgeMeshEdgeMergeDecimationFilter.txx || 58.80%  || 103 ||
|-
| ./itkQuadEdgeMeshExtendedTraits.h || || ||
|-
| ./itkQuadEdgeMeshNormalFilter.h || 25.00% || 03 ||
|-
| ./itkQuadEdgeMeshNormalFilter.txx || 92.50% || 06 ||
|-
| ./itkQuadEdgeMeshParam.h || 71.43% || 02 ||
|-
| ./itkQuadEdgeMeshParam.txx || 100.0% || 00 || -----'''OK'''
|-
| ./itkQuadEdgeMeshParamMatrixCoefficients.h  || 100.0% || 00 || -----'''OK'''
|-
| ./itkQuadEdgeMeshQuadricDecimation.h  || 97.44% || 01 ||
|-
| ./itkQuadEdgeMeshScalarDataVTKPolyDataWriter.h  || 16.65% || 05 ||
|-
| ./itkQuadEdgeMeshScalarDataVTKPolyDataWriter.txx  || 63.46% || 19 ||
|-
| ./itkQuadEdgeMeshSquaredEdgeLengthDecimation.h  || 88.89% || 01 ||
|-
| ''./itkQuadEdgeMeshSquaredEdgeLengthDecimation.txx'' || 100.0% || 00 || -----'''OK'''
|}
|}


== 4: Code Coverage and Memory Leaks ==


We used the CMake / CTest options to check code coverage and mem leaks (using gcov and valgrind).
{|
Here are the results as of '''June 28 2008'''
! ITK/Testing/Code/Review Names
|-
| *./itkQuadEdgeMeshCleanFilterTest.cxx
|-
| *./itkQuadEdgeMeshDelaunayConformingFilterTest.cxx
|-
| *./itkQuadEdgeMeshGaussianCurvatureTest.cxx
|-
| *./itkQuadEdgeMeshLinearParameterizationTest.cxx
|-
| *./itkQuadEdgeMeshMaxCurvatureTest.cxx
|-
| *./itkQuadEdgeMeshMeanCurvatureTest.cxx
|-
| *./itkQuadEdgeMeshMinCurvatureTest.cxx
|-
| *./itkQuadEdgeMeshNormalFilterTest.cxx
|-
| *./itkQuadEdgeMeshQuadricDecimationTest.cxx
|-
| *./itkQuadEdgeMeshScalarDataVTKPolyDataWriterTest1.cxx
|-
| *./itkQuadEdgeMeshSquaredEdgeLengthDecimationTest.cxx
|-
| *./itkVTKPolyDataIOQuadEdgeMeshTest.cxx
|-
| *./itkVTKPolyDataReaderQuadEdgeMeshTest.cxx
|}
 
= Euler Operators =


===4.1: Code Coverage ===
==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/txx]''|| 100.0% || 00 || ---- '''OK'''
|-
| ''*./itkQuadEdgeMeshEulerOperatorDeleteCenterVertexFunction.[h/txx]''|| 100.0% || 00 || ---- '''OK'''
|-
| ''*./itkQuadEdgeMeshEulerOperatorFlipEdgeFunction.h''          || 100.0% || 00 || ---- '''OK'''
|- 
| *./itkQuadEdgeMeshEulerOperatorFlipEdgeFunction.txx      || 69.84% || 19 ||
|-
| ''*./itkQuadEdgeMeshEulerOperatorJoinFacetFunction.[h/txx]''        || 100.0% || 00 || ---- '''OK'''
|-
| ''*./itkQuadEdgeMeshEulerOperatorJoinVertexFunction.h ''      || 100.0% || 00 || ---- '''OK'''
|-
| *./itkQuadEdgeMeshEulerOperatorJoinVertexFunction.txx          || 80.19% || 41 || wrong zipfunction return(4) failsafe cases.
|-
| ''*./itkQuadEdgeMeshEulerOperatorSplitEdgeFunction.h ''        || 100.0% || 00 || ---- '''OK'''
|-
| *./itkQuadEdgeMeshEulerOperatorSplitFacetFunction.h        || 75.00% || 01 ||
|-
| *./itkQuadEdgeMeshEulerOperatorSplitFacetFunction.txx          || 68.75% || 10 ||
|-
| ''*./itkQuadEdgeMeshEulerOperatorSplitVertexFunction.[h/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/Code/Review Names                       !! Coverage !! # of Lines not covered !! Analyze - Comments
{|
! ITK/Testing/Code/Review Names
|-
| *./itkQuadEdgeMeshEulerOperatorsTest.cxx 
|-
| *./itkQuadEdgeMeshEulerOperatorCreateCenterVertexTest.cxx
|-
| *./itkQuadEdgeMeshEulerOperatorDeleteCenterVertexTest.cxx
|-
| *./itkQuadEdgeMeshEulerOperatorFlipTest.cxx
|-
| *./itkQuadEdgeMeshEulerOperatorJoinFacetTest.cxx
|-
| *./itkQuadEdgeMeshEulerOperatorJoinVertexTest.cxx
|-
| *./itkQuadEdgeMeshEulerOperatorSplitEdgeTest.cxx
|-  
| *./itkQuadEdgeMeshEulerOperatorSplitFaceTest.cxx
|-  
|-  
| itkGeometricalQuadEdge.h                    || 62.79 - 67.44% || 16 - 14 || iterators, SetRight( ), GetRight, GetLeft, GetIdent( ).
| *./itkQuadEdgeMeshEulerOperatorSplitVertexTest.cxx
|-  
|-  
| itkGeometricalQuadEdge.txx                  || 73.53 - 75.49% || 27 - 25 || Degenerated cases (Disconnect).
| *./itkQuadEdgeMeshEulerOperatorsTestHelper.h
|}
 
Note: itkTypeMacro => GetNameOfClass( )
 
= 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 ==
 
=== ongoing work ===
{|
|-
|-
| itkQuadEdge.h                              || 07.69% || 12 || iterators.
| class name|| Existing Test || New Test || status
|-
|-
| itkQuadEdge.cxx                            || 86.15% || 36 || Degenerated Cases not tested.
|''itkAutomaticTopologyMeshSource'' || ''itkAutomaticTopologyMeshSourceTest''|| ''itkAutomaticTopology'''QuadEdge'''MeshSourceTest'' || '''OK''' (*1) ||
|-
|-
| itkQuadEdgeMesh.h                          || 25.00 - 58.33% || 09 - 05 || Requestedregion...( ), CopyInformation( ).
|itkBalloonForceFilter || || || ||
|-
|-
| itkQuadEdgeMesh.txx                        || 66.47 - 79.07% || 114- 72 || FindClosestPoint( ), DeleteFace( ), GetEdge( ), GetVector( ), LightWeightDeleteEdge( primal ), FindEdgeCell( ),
| ''itkBinaryMask3DMeshSource'' || ''itkBinaryMask3DMeshSourceTest'' || ''itkBinaryMask3D'''QuadEdge'''MeshSourceTest''|| '''OK''' ||
|-
|-
| itkQuadEdgeMeshBaseIterator.h              || 68.42% || 24 || Iterators not used.
|itkBinaryMaskToNarrowBandPointSetFilter || || || ||
|-
|-
| itkQuadEdgeMeshBoundaryEdgesMeshFunction.h  || ------ || -- || Not Covered - Not Called
|''itkConformalFlatteningMeshFilter'' || ''itkCOnformalFlatteningMeshFilterTest'' || ''itkConformalFlattening'''QuadEdgeMesh'''FilterTest'' || '''OK''' ||
 
|-  
|''itkConnectedRegionsMeshFilter'' || ''itkExtractMeshConnectedRegions'' || || '''NOT POSSIBLE''' ||
|-
|-
| itkQuadEdgeMeshBoundaryEdgesMeshFunction.txx|| ------ || -- || Not Covered - Not Called
|itkDeformableMesh3DFilter || || || ||
|-
|-
| itkQuadEdgeMeshFrontIterator.h              || 81.82% || 04 || Const flavor of Constructor, Destructor. To remove?
|itkDeformableSimplexMesh3DFilter || || || ||
|-
|-
| itkQuadEdgeMeshFrontIterator.txx            || 81.40% || 08 || Bad init fall cases, FindDefaultSeed( ).
|itkImageToParametricSpaceFilter || || || ||
|-
|-
| itkQuadEdgeMeshLineCell.h                  || 33.33% || 02 || TypeMacro( ), MakeCopy( ).
|itkInteriorExteriorMeshFilter || || || ||
|-
|-
| itkQuadEdgeMeshLineCell.txx                || 50.77% || 32 || Accept, BoundaryFeat., PointIds(+1 BUG), Ident, Type, Dimension.
|itkParametricSpaceToImageSpaceMeshFilter || || || ||
|-
|-
| itkQuadEdgeMeshMacro.h                      || ------ || -- || Not Covered - Macros
|''itkQuadEdgeMeshToQuadEdgeMeshFilter'' || ----- || ----- || '''OK''' ||
|-
|-
| itkQuadEdgeMeshPoint.h                      || 100.0% || 00 || -----
|''itkRegularSphereMeshSource''|| ''itkRegularSphereMeshSourceTest'' || ''itkRegularSphere'''QuadEdge'''MeshSourceTest'' || '''OK''' ||
|-
|-
| itkQuadEdgeMeshPoint.txx                    || 100.0% || 00 || -----
|itkSimplexMeshAdaptTopologyFilter  || || || ||
|-
|-
| itkQuadEdgeMeshPolygonCell.h                || 33.33% || 06 || TypeMacro( ), MakeCopy( ), GetType, GetDimension
|itkSimplexMeshToTriangleMeshFilter || || || ||
|-
|-
| itkQuadEdgeMeshPolygonCell.txx              || 61.54% || 25 || Accept( ), BoundaryFeat., PointsIds,
|itkSphereMeshSource || itkSphereMeshSourceTest || || in progress ||
|-
|-
| itkQuadEdgeMeshTopologyChecker.h            || 88.89% || 01 || TypeMacro( )
|itkTransformMeshFilter || || || in progress ||
|-
|-
| itkQuadEdgeMeshTopologyChecker.txx          || 33.33% || 08 || PrintSelf( )
|itkTriangleMeshToSimplexMeshFilter || || || ||
|-
|''itkVTKPolyDataReader'' || ''itkVTKPolyDataReaderTest'' || ''itkVTKPolyDataReader'''QuadEdgeMesh'''Test'' || '''OK''' ||
|-
|''itkVTKPolyDataWriter'' || ''itkVTKPolyDataWriterTest'' ||  ''itkVTKPolyDataIO'''QuadEdgeMesh'''Test'' || '''OK''' ||
|-
|itkWarpMeshFilter || itkWarpMeshFilterTest || itkWarp'''QuadEdge'''MeshFilterTest || in progress ||
|}
 
=== to include: ===
*itkMeshSpatialObject*Test*        (4)
*testMetaMesh                     
*itkDeformableSimplexMesh3D*      (3)
*itkSimplexMeshVolumeCalculator   
*itkTriangleMeshToBinaryImageFilter (2)
*itkImageToMeshFilterTest
*itkSimplexMeshTest
*itkMeshSourceGraftOutputTest
*itkMeshFstreamTest
*itkFEMGenerateMeshTest
 
=== Backward compatibility note ===
 
(*1) - Automatic topology test try to create 3 dimensional cells like tetahedron. This is not possible with an itkQEMesh. It will not fail, but the cell will not be created. Thus even if the test will not fail, there is far more less cells created than it should. Moreover, as a vector is used, and not a map, for the cell container, even if the final count is 53 cells, there is not 53 cells in the container. This two flavors of the the same test should thus not be used for benchmarking.
 
== 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 ===
{|
|-
|-
| itkQuadEdgeMeshToQuadEdgeMeshFilter.h      || ------ || -- || Not Covered - Not Used
| name || vizu to remove || file IO to remove || working remotely now?
|-
|-
| itkQuadEdgeMeshToQuadEdgeMeshFilter.txx    || ------ || -- || Not Covered - Not Used
| MeshBuildLinks || || || yes
|-
|-
| itkQuadEdgeMeshTraits.h                    || ------ || -- || Not Covered - Implicit + only types
| MeshComparativeUpdate || || || yes
|}
|}


===4.2: Memory Leak ===
=== filters to write ===

Latest revision as of 12:42, 27 October 2010

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

This page is not maintained anymore and as of 2010, the news developments are documented here

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. We are aiming at ITK 4.0, Q4 2008.


The development started in 2004 by Dr. Leonardo V. Florez which coded a first prototype with help from Eric Boix. By 2005 Dr. Florez prorities shifted (see commit log here:http://www.ohloh.net/projects/8458/contributors) and the project has been since kept alive by Dr. Alex. Gouaillard and Dr. Eric Boix (see same page). The project has been packaged and submitted to Insight Journal late 2006 with help from Matthieu Malaterre ( see http://hdl.handle.net/1926/306). Accepted in ITK early 2007, it is currently in the Review subdirectory. Lot of work has been done since, mainly on adding euler operators, improving the robustness (testing, coverage, ...) the speed and coding some higher level filters to test he structure (parameterization http://hdl.handle.net/1926/1315, decimation, smoothing, ...). The latest filters are mainly developed by Dr. Arnaud Gelas. All this work was initiated at CREATIS laboratory in France to which ALl the above mentioned individual were belonging at one point.


The main contact for this structure, filters and page is currently alex. gouaillard (agouaillard /at/ gmail.com).

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.

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.

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).

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.

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.

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.
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.

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

4: Performance

Checking half of the word out there

For the time being, performance of QE are still being assessed. It seems that QE is still slower than itk::Mesh and than vtk. The main reason for that is that QuadEdge is double checking everything. We are currently working on making QE faster, only allowing double-checks for the Debug version.

creating cells twice

when using the traditionnal way of creating cells(namely, creating the cells, wrapping them in an auto-pointer and feeding the mesh with them) QE create a new cell, and dispose the first one. The best way is to directly use the AddFace / AddEdge method to avoid that.

We might also want to create a QE memory pool, where the QE would not be erased but stored. It would make sense as QE as the most numerous elements in the mesh (4 by edge !) and will likely to be destroyed/created often, leading in a lot of memory allocations and possibly memory fragmentation (see recent work on firefox 3).

In C-GAL, the 4 QE are allocated in a continuous block of memory and accessed through pointer arithmetic, as each QE is of fixed size. I think the pool allocation work would make a lot of sense for subdivision filters for example.

Secure Copying

We also separated AddFace and AddEdge in a "secure" and a normal one. The normal one checks everything and then call the secure one. When creating a mesh, you might want to check existence of the points (even though vtk or itk does not), orientation and a few other things. But when copying an already existing QEMesh, all those test are redundant. We achieve almost 35% improvement in copy speed.

We should investigate copying the entire cellContainer at a time, but right now the QE layer can not be copied directly. The QE container/pool discusssed above could make sense here too.

Mesh to QuadEdgeMesh: Migration guide

types

Points

Creation of a new point

the Default PointType for an QuadEdgeMEsh is a "QuadEdgeMeshPoint" (instead of a "Point"). This PointType inheritates 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 careful about resetting this link to the correct value. For example a subdivision 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 );

Changing geometry of an existing point

When changing the geometry of an existing point, it is important to be careful that the link to the QuadEdge remains unchanged. This can actually be done in two ways:

  • Direct change of coordinates
PointID pid = 0;
PointType pointToTransfer; // here the link is set to NULL by the constructor
PoinType localPoint; // here the link is set to NULL by the constructor
...  
... // modify localPoint coordinates
...
InputMesh->GetPoint( pid, &pointToTransfer); // here pointToTransfer got the link from InputMesh point
// change the coordinates of pointToTransfer
pointToTransfer[0] = localPoint[0];
pointToTransfer[1] = localPoint[1];
pointToTransfer[2] = localPoint[2];
OutputMesh->SetPoint( pid, pointToTransfer );
  • Though the creation of a new point
PointID pid = 0;
PoinType localPoint; // here the link is set to NULL by the constructor
...
... // modify localPoint coordinates
...
localPoint->SetEdge( InputMesh->FindEdge( pid ) ); // copy the link from InputMesh point to localPoint
OutputMesh->SetPoint( pid, pointToTransfer );

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.


The itkVTKPolyDataWriter class, currently in Review, will skip the edges and only write the triangles. It is currently the suggested filters for writing PolyData.

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 80.00% 9* iterators(9).
itkGeometricalQuadEdge.txx 78.99% 25 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/txx] 100.0% 00 ---- OK
itkQuadEdgeMeshPolygonCell.[h/txx] 100.0% 00 ---- OK
itkQuadEdgeMeshTopologyChecker.h 100.0% 00 ---- OK
itkQuadEdgeMeshTopologyChecker.txx 94.74% 01 twice genus(1).
itkQuadEdgeMeshToQuadEdgeMeshFilter.h 33.00% 02 NewMacro(1), TYpeMacro(1).
itkQuadEdgeMeshToQuadEdgeMeshFilter.txx 100.0% 00 ---- OK
itkQuadEdgeMeshTraits.h ------ -- ---- OK Not Covered - Implicit + only types

2 filters

ITK/Code/Review Names Coverage # of Lines not covered Analyze - Comments
./itkQuadEdgeMeshBorderTransform.h 100.0% 00 -----OK
./itkQuadEdgeMeshBorderTransform.txx 99.25% 01
./itkQuadEdgeMeshCleanFilter.h 90.48% 06
./itkQuadEdgeMeshDecimationCriteria.h 89.29% 03
./itkQuadEdgeMeshDecimationFilter.h 86.96% 03
./itkQuadEdgeMeshDecimationQuadricElementHelper.h 98.21% 01
./itkQuadEdgeMeshDelaunayConformingFilter.h 86.49% 05
./itkQuadEdgeMeshDelaunayConformingFilter.txx 83.33% 12
./itkQuadEdgeMeshDiscreteCurvatureEstimator.h 93.30% 01
./itkQuadEdgeMeshDiscreteCurvatureTensorEstimator.h
./itkQuadEdgeMeshDiscreteGaussianCurvatureEstimator.h 90.48% 02
./itkQuadEdgeMeshDiscreteMaxCurvatureEstimator.h 85.71% 01
./itkQuadEdgeMeshDiscreteMeanCurvatureEstimator.h 96.30% 01
./itkQuadEdgeMeshDiscreteMinCurvatureEstimator.h 85.71% 01
./itkQuadEdgeMeshDiscretePrincipalCurvaturesEstimator.h 96.97% 01
./itkQuadEdgeMeshEdgeMergeDecimationFilter.h 52.00% 120
./itkQuadEdgeMeshEdgeMergeDecimationFilter.txx 58.80% 103
./itkQuadEdgeMeshExtendedTraits.h
./itkQuadEdgeMeshNormalFilter.h 25.00% 03
./itkQuadEdgeMeshNormalFilter.txx 92.50% 06
./itkQuadEdgeMeshParam.h 71.43% 02
./itkQuadEdgeMeshParam.txx 100.0% 00 -----OK
./itkQuadEdgeMeshParamMatrixCoefficients.h 100.0% 00 -----OK
./itkQuadEdgeMeshQuadricDecimation.h 97.44% 01
./itkQuadEdgeMeshScalarDataVTKPolyDataWriter.h 16.65% 05
./itkQuadEdgeMeshScalarDataVTKPolyDataWriter.txx 63.46% 19
./itkQuadEdgeMeshSquaredEdgeLengthDecimation.h 88.89% 01
./itkQuadEdgeMeshSquaredEdgeLengthDecimation.txx 100.0% 00 -----OK


ITK/Testing/Code/Review Names
*./itkQuadEdgeMeshCleanFilterTest.cxx
*./itkQuadEdgeMeshDelaunayConformingFilterTest.cxx
*./itkQuadEdgeMeshGaussianCurvatureTest.cxx
*./itkQuadEdgeMeshLinearParameterizationTest.cxx
*./itkQuadEdgeMeshMaxCurvatureTest.cxx
*./itkQuadEdgeMeshMeanCurvatureTest.cxx
*./itkQuadEdgeMeshMinCurvatureTest.cxx
*./itkQuadEdgeMeshNormalFilterTest.cxx
*./itkQuadEdgeMeshQuadricDecimationTest.cxx
*./itkQuadEdgeMeshScalarDataVTKPolyDataWriterTest1.cxx
*./itkQuadEdgeMeshSquaredEdgeLengthDecimationTest.cxx
*./itkVTKPolyDataIOQuadEdgeMeshTest.cxx
*./itkVTKPolyDataReaderQuadEdgeMeshTest.cxx

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.

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.

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/txx] 100.0% 00 ---- OK
*./itkQuadEdgeMeshEulerOperatorDeleteCenterVertexFunction.[h/txx] 100.0% 00 ---- OK
*./itkQuadEdgeMeshEulerOperatorFlipEdgeFunction.h 100.0% 00 ---- OK
*./itkQuadEdgeMeshEulerOperatorFlipEdgeFunction.txx 69.84% 19
*./itkQuadEdgeMeshEulerOperatorJoinFacetFunction.[h/txx] 100.0% 00 ---- OK
*./itkQuadEdgeMeshEulerOperatorJoinVertexFunction.h 100.0% 00 ---- OK
*./itkQuadEdgeMeshEulerOperatorJoinVertexFunction.txx 80.19% 41 wrong zipfunction return(4) failsafe cases.
*./itkQuadEdgeMeshEulerOperatorSplitEdgeFunction.h 100.0% 00 ---- OK
*./itkQuadEdgeMeshEulerOperatorSplitFacetFunction.h 75.00% 01
*./itkQuadEdgeMeshEulerOperatorSplitFacetFunction.txx 68.75% 10
*./itkQuadEdgeMeshEulerOperatorSplitVertexFunction.[h/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
*./itkQuadEdgeMeshEulerOperatorCreateCenterVertexTest.cxx
*./itkQuadEdgeMeshEulerOperatorDeleteCenterVertexTest.cxx
*./itkQuadEdgeMeshEulerOperatorFlipTest.cxx
*./itkQuadEdgeMeshEulerOperatorJoinFacetTest.cxx
*./itkQuadEdgeMeshEulerOperatorJoinVertexTest.cxx
*./itkQuadEdgeMeshEulerOperatorSplitEdgeTest.cxx
*./itkQuadEdgeMeshEulerOperatorSplitFaceTest.cxx
*./itkQuadEdgeMeshEulerOperatorSplitVertexTest.cxx
*./itkQuadEdgeMeshEulerOperatorsTestHelper.h

Note: itkTypeMacro => GetNameOfClass( )

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

ongoing work

class name Existing Test New Test status
itkAutomaticTopologyMeshSource itkAutomaticTopologyMeshSourceTest itkAutomaticTopologyQuadEdgeMeshSourceTest OK (*1)
itkBalloonForceFilter
itkBinaryMask3DMeshSource itkBinaryMask3DMeshSourceTest itkBinaryMask3DQuadEdgeMeshSourceTest OK
itkBinaryMaskToNarrowBandPointSetFilter
itkConformalFlatteningMeshFilter itkCOnformalFlatteningMeshFilterTest itkConformalFlatteningQuadEdgeMeshFilterTest OK
itkConnectedRegionsMeshFilter itkExtractMeshConnectedRegions NOT POSSIBLE
itkDeformableMesh3DFilter
itkDeformableSimplexMesh3DFilter
itkImageToParametricSpaceFilter
itkInteriorExteriorMeshFilter
itkParametricSpaceToImageSpaceMeshFilter
itkQuadEdgeMeshToQuadEdgeMeshFilter ----- ----- OK
itkRegularSphereMeshSource itkRegularSphereMeshSourceTest itkRegularSphereQuadEdgeMeshSourceTest OK
itkSimplexMeshAdaptTopologyFilter
itkSimplexMeshToTriangleMeshFilter
itkSphereMeshSource itkSphereMeshSourceTest in progress
itkTransformMeshFilter in progress
itkTriangleMeshToSimplexMeshFilter
itkVTKPolyDataReader itkVTKPolyDataReaderTest itkVTKPolyDataReaderQuadEdgeMeshTest OK
itkVTKPolyDataWriter itkVTKPolyDataWriterTest itkVTKPolyDataIOQuadEdgeMeshTest OK
itkWarpMeshFilter itkWarpMeshFilterTest itkWarpQuadEdgeMeshFilterTest in progress

to include:

  • itkMeshSpatialObject*Test* (4)
  • testMetaMesh
  • itkDeformableSimplexMesh3D* (3)
  • itkSimplexMeshVolumeCalculator
  • itkTriangleMeshToBinaryImageFilter (2)
  • itkImageToMeshFilterTest
  • itkSimplexMeshTest
  • itkMeshSourceGraftOutputTest
  • itkMeshFstreamTest
  • itkFEMGenerateMeshTest

Backward compatibility note

(*1) - Automatic topology test try to create 3 dimensional cells like tetahedron. This is not possible with an itkQEMesh. It will not fail, but the cell will not be created. Thus even if the test will not fail, there is far more less cells created than it should. Moreover, as a vector is used, and not a map, for the cell container, even if the final count is 53 cells, there is not 53 cells in the container. This two flavors of the the same test should thus not be used for benchmarking.

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).
- 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