Proposals:New Mesh Class: Difference between revisions

From KitwarePublic
Jump to navigationJump to search
Line 7: Line 7:
This documents describes how itkQuadEdgeMesh will be integrated into ITK 3.2.
This documents describes how itkQuadEdgeMesh will be integrated into ITK 3.2.


=CORE: First Implementation Integration issues=
=CORE: First Implementation Subtleties=
 
Here are the current issues


==1: function vs filters==
==1: function vs filters==
01/23/07 <br>
Operations in 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
That derive from FunctionBase. The idea is to "externalize" what would otherwise be a class method
from the QuadEdgeMesh, that's certainly compatible with the general ITK design.
to be able to extend he class at posteriori. Some modifications of the mesh are
In your paper you explain that you preferred to use Functions instead of Filters
so local that you do not want to use a itkMeshToMeshFilter that would copy
in order to save memory. That is, to make changes in-place, as opposed to
the entire input mesh to the output. Euler Operators are a perfect exemple of this.
creating a copy of the mesh as output to a filter. That's a reasonable argument.  
 
I would suggest that we keep the function classes but we also offer them in the
It's up to filter's devellopers to use those functions inside the filter and enforce const-corectness.
form of filters that allow to support const-correctness. Using the data-pipeline is
 
also compatible with the VTK design.
==2: QuadEdgeMeshCells ==
<br>
an itkQuadEdgeMesh uses two types f cells: a QELineCell and a QEPolygonCell.
<br>
update 01/24/07: eric <br>
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==
===Building QE layer===
01/23/07 <br>
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.
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>
update 01/24/07: kitware<br>
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>
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>
<br>
<br>
Update 01/24/07:leo<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.
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>
<br>
<br>
Update 01/24/07:leo<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).
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>
<br>
<br>
Update 01/25/07:Luis<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.
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>
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.
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
QEs (by aggregation). I've tested this new implementation taking
"native" itkMesh examples, changing just the template's instantiation
and running them. So far, it works fine. Right now, I'm completing
this implementation in order to cope with all CellInterface methods. I
hope there will not be further suprises.
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
to use this new representation to simplify simplex mesh-based
algorithms, but I'm sure there are more applications to this.
 
==3: Error management ==
01/23/07 <br>
There is not enough error management in the code.
For example, there are methods implemented as
 
              ->GetRot()->GetRot()->GetRot()


that rely on the assumption that none of the intermediate
===Cell API===
calls return a null pointer.
Most of the Cell API (see itkCellInterface.h) has been implemented
We are moving all these methods from the header file
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.
into the .cxx file, and inserting error management in them.
The basic principle is that no method should crash.
We can do error management by returning  null pointers
in the intermediate cases, or by throwing exceptions.
The unit test should be such that any method could be
called in any order, without making the class crash. <br>
<br>
<br>
Update: 01/24/07: Eric<br>
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().
The only way (I can foresee) for your null pointer scenario to happen would
be some exterior corruption of the data structure.
Actually QuadEdge.SetRot() and it's SetOnext() counterpart shouldn't be public
(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
find any occurence of SetOnext() except for the constructor and Splice().
How could you thus break the edge-algebra ?
==4: Coding style: Method renaming==
01/23/07<br>
We will expand the current abridged names of methods, and
for reference we will leave the original name in the Doxygen
documentation, so that users can refer to the terms used in
the paper.
==5: allocation without desallocation==
01/23/07 <br>
The QuadEdges that are allocated in the MakeEdge() method
in the LineCell and in the GeometricalQuadEdge (formerly QEGeom),
...where are they deallocated ?
We couldn't find any calls to the "delete"s that should match
these "new".
We are suggesting to add the deletes to the destructor
of the GeometricalQuadEdge<br>
<br>
<br>
update 01/24/07: eric<br>
Unfortunatly, this is not backward compatible with the usual Cell API. 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. This one is used within itkQuadEdgeMesh, and should be used by default by any code using only QuadEdgeMesh.
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>
<br>
<br>
Update 01/24/07: leo<br>
To be fully compliant with the cell API, as far as Points Id iterator are concerned, would mean implementing a local (in the cell) point container, and thus duplicate the information. It would also require building an Edge container in the polygoncell. That can be done, but would duplicate information and take more memory. We supposed that nobody would try to use a QuadEdgeCell without a QuadEdgeMesh, and made the minimum implementation for the API to be complete. If there was a need for a complete API, we could easily implement the complete solution.
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()==
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>
<br>
<br>
Update 01/24/07: leo<br>
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.
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.


=CORE: Second implementation=
=CORE: Second implementation=

Revision as of 17:55, 27 July 2007

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

CORE: First Implementation Subtleties

1: function vs filters

Operations in the QuadEdgeMesh are implemented in Function classes That derive from FunctionBase. The idea is to "externalize" what would otherwise be a class method to be able to extend he class at posteriori. Some modifications of the mesh are so local that you do not want to use a itkMeshToMeshFilter that would copy the entire input mesh to the output. Euler Operators are a perfect exemple of this.

It's up to filter's devellopers to use those functions inside the filter and enforce const-corectness.

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 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. 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. This one 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, would mean implementing a local (in the cell) point container, and thus duplicate the information. It would also require building an Edge container in the polygoncell. That can be done, but would duplicate information and take more memory. We supposed that nobody would try to use a QuadEdgeCell without a QuadEdgeMesh, and made the minimum implementation for the API to be complete. If there was a need for a complete API, we could easily implement the complete solution.

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.

CORE: Second implementation

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

  • QuadEdgeGeom constructor is made private and can only be called by LineCell ?
  • QuadEdgeGeom smart initialization to prevent misuse (sym = NULL) ?

3: Merging in ITK/review

As of june 27th 2008, the Core is in ITK Review

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

  • in /Review, class and method names may have changed. Macro may have been displaced.
  • in creatis' cvs rep., the second implementation was done.

It matters now to merge everything. 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.


ITK/Code/Review Names original CVS Names
itkGeometricalQuadEdge.* itkQEQuadEdgeGeom.*
itkQuadEdge.* itkQEQuadEdge.*
itkQuadEdgeMesh.* itkQEMesh.*
itkQuadEdgeMeshBaseIterator.* itkQEBaseIterator.*
itkQuadEdgeMeshBoundaryEdgesMeshFunction.* itkQEBoundaryRepresentativeEdgesMeshFunction.*
itkQuadEdgeMeshFrontIterator.* itkQEFrontIterator.*
itkQuadEdgeMeshLineCell.* itkQELineCell.*
itkQuadEdgeMeshMacro.h itkQEMeshMacro.h
itkQuadEdgeMeshPoint.* itkQEPoint.*
itkQuadEdgeMeshPolygonCell.* itkQEPolygonCell.*
itkQuadEdgeMeshTopologyChecker.* ?
itkQuadEdgeMeshToQuadEdgeMeshFilter.* /BasicFilter/itkQEMeshCopy.*
itkQuadEdgeMeshTraits.h itkQEMeshTraits.h

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 July 12 2008

4.1: Code Coverage

Reportrs : http://www.itk.org/Testing/Sites/buildhost.creatis.insa-lyon.fr/Linux-c++/20070712-2040-Experimental/CoverageByName.html


ITK/Code/Review Names Coverage # of Lines not covered Analyze - Comments
itkGeometricalQuadEdge.h 75.56% 11 iterators, SetRight( ).
itkGeometricalQuadEdge.txx 81.97% 23 Degenerated cases (Disconnect).
itkQuadEdge.h 07.69% 12* iterators.
itkQuadEdge.cxx 86.05% 36 Degenerated Cases not tested.
itkQuadEdgeMesh.h 75.00% 03 Requestedregion...( ), CopyInformation( ).
itkQuadEdgeMesh.txx 85.11% 60* GetEdge( cellId ), SetCell with a native itkCell.
itkQuadEdgeMeshBaseIterator.h 65.79% 26 Iterators not used.
itkQuadEdgeMeshBoundaryEdgesMeshFunction.h 75.00% 01 -----
itkQuadEdgeMeshBoundaryEdgesMeshFunction.txx 88.46% 03 -----
itkQuadEdgeMeshFrontIterator.h 81.82% 04 Const flavor of Constructor, Destructor. To remove?
itkQuadEdgeMeshFrontIterator.txx 81.40% 08 Bad init fall cases, FindDefaultSeed( ).
itkQuadEdgeMeshLineCell.h 72.73% 03 const versions of Get/Set Id API.
itkQuadEdgeMeshLineCell.txx 67.82% 28* Accept( ), "Internal" versions of PointIds( 8 fct. )
itkQuadEdgeMeshMacro.h ------ -- Not Covered - Macros
itkQuadEdgeMeshPoint.h 100.0% 00 -----
itkQuadEdgeMeshPoint.txx 100.0% 00 -----
itkQuadEdgeMeshPolygonCell.h 83.33% 03* MakeCopy( )
itkQuadEdgeMeshPolygonCell.txx 66.22% 25* Accept( ), BoundaryFeat., PointsIds,
itkQuadEdgeMeshTopologyChecker.h 100.0% 00
itkQuadEdgeMeshTopologyChecker.txx 88.89% 04
itkQuadEdgeMeshToQuadEdgeMeshFilter.h ------ -- Not Covered - Not Used - OK tested in creatis
itkQuadEdgeMeshToQuadEdgeMeshFilter.txx ------ -- Not Covered - Not Used - OK tested in creatis
itkQuadEdgeMeshTraits.h ------ -- Not Covered - Implicit + only types

4.2: Memory Leak, warnings and KWStyle

Euler Operators

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.

1: list of files

  • ./itkQEEulerOperatorCreateCenterVertexFunction.h
  • ./itkQEEulerOperatorCreateCenterVertexFunction.txx
  • ./itkQEEulerOperatorDeleteCenterVertexFunction.h
  • ./itkQEEulerOperatorDeleteCenterVertexFunction.txx
  • ./itkQEEulerOperatorFlipEdgeFunction.h
  • ./itkQEEulerOperatorFlipEdgeFunction.txx
  • ./itkQEEulerOperatorJoinFacetFunction.h
  • ./itkQEEulerOperatorJoinFacetFunction.txx
  • ./itkQEEulerOperatorJoinVertexFunction.h
  • ./itkQEEulerOperatorJoinVertexFunction.txx
  • ./itkQEEulerOperatorSplitEdgeFunction.h
  • ./itkQEEulerOperatorSplitFacetFunction.h
  • ./itkQEEulerOperatorSplitFacetFunction.txx
  • ./itkQEEulerOperatorSplitVertexFunction.h
  • ./itkQEEulerOperatorSplitVertexFunction.txx
  • ./EulerOperatorsTest.cxx

2: Synchronize ITK/Code/Review with Original rep

Dedicated Dashboard

KWStyle

- Matrix

Coverage

Subtest Percentage Lines covered Lines not covered Files covered Files not covered Coverage metric
. 78.68 1709 463 56 0 0.79
Examples 66.67 22 11 1 0 0.74
Testing 76.80 1112 336 17 0 0.77
Code 83.21 575 116 38 0 0.83


Mem. Leaks

Names Whatever Memory Leak Potential Memory Leak Uninitialized Memory Read
EulerOperatorsTest Report 0 2 0
vtkUnstructuredGridImportTest Report 0 1 0
  1. write an IJ paper?
  2. code in Review
  3. release 3.4 ?
Retrieved from "https://public.kitware.com/Wiki/index.php?title=Proposals:New_Mesh_Class&oldid=9964"