text: /*=========================================================================
  
    Program:   Visualization Toolkit
    Module:    $RCSfile: vtkReebGraph.h,v $
  
    Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
    All rights reserved.
    See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
  
       This software is distributed WITHOUT ANY WARRANTY; without even
       the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
       PURPOSE.  See the above copyright notice for more information.
  
  =========================================================================*/
  /*----------------------------------------------------------------------------
   Copyright (c) Sandia Corporation
   See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details.
  ----------------------------------------------------------------------------*/
  
  // .NAME vtkReebGraph - Reeb graph computation for PL scalar fields.
  //
  // .SECTION Description
  // vtkReebGraph is a class that computes a Reeb graph given a PL scalar
  // field (vtkDataArray) defined on a simplicial mesh.
  // A Reeb graph is a concise representation of the connectivity evolution of
  // the level sets of a scalar function.
  //
  // It is particularly useful in visualization (optimal seed set computation,
  // fast flexible isosurface extraction, automated transfer function design,
  // feature-driven visualization, etc.) and computer graphics (shape
  // deformation, shape matching, shape compression, etc.).
  //
  // Reference:
  // "Sur les points singuliers d'une forme de Pfaff completement integrable ou
  // d'une fonction numerique",
  // G. Reeb,
  // Comptes-rendus de l'Academie des Sciences, 222:847-849, 1946.
  //
  // vtkReebGraph implements one of the latest and most robust Reeb graph
  // computation algorithms.
  //
  // Reference:
  // "Robust on-line computation of Reeb graphs: simplicity and speed",
  // V. Pascucci, G. Scorzelli, P.-T. Bremer, and A. Mascarenhas,
  // ACM Transactions on Graphics, Proc. of SIGGRAPH 2007.
  //
  // vtkReebGraph provides methods for computing multi-resolution topological
  // hierarchies through topological simplification.
  // Topoligical simplification can be either driven by persistence homology
  // concepts (default behavior) or by application specific metrics (see
  // vtkReebGraphSimplificationMetric).
  // In the latter case, designing customized simplification metric evaluation
  // algorithms enables the user to control the definition of what should be
  // considered as noise or signal in the topological filtering process.
  //
  // References:
  // "Topological persistence and simplification",
  // H. Edelsbrunner, D. Letscher, and A. Zomorodian,
  // Discrete Computational Geometry, 28:511-533, 2002.
  //
  // "Extreme elevation on a 2-manifold",
  // P.K. Agarwal, H. Edelsbrunner, J. Harer, and Y. Wang,
  // ACM Symposium on Computational Geometry, pp. 357-365, 2004.
  //
  // "Simplifying flexible isosurfaces using local geometric measures",
  // H. Carr, J. Snoeyink, M van de Panne,
  // IEEE Visualization, 497-504, 2004
  //
  // "Loop surgery for volumetric meshes: Reeb graphs reduced to contour trees",
  // J. Tierny, A. Gyulassy, E. Simon, V. Pascucci,
  // IEEE Trans. on Vis. and Comp. Graph. (Proc of IEEE VIS), 15:1177-1184, 2009.
  //
  //
  //
  // Reeb graphs can be computed from 2D data (vtkPolyData, with triangles only)
  // or 3D data (vtkUnstructuredGrid, with tetrahedra only), sequentially (see
  // the "Build" calls) or in streaming (see the "StreamTriangle" and
  // "StreamTetrahedron" calls).
  //
  // vtkReebGraph inherits from vtkMutableDirectedGraph.
  //
  // Each vertex of a vtkReebGraph object represents a critical point of the
  // scalar field where the connectivity of the related level set changes
  // (creation, deletion, split or merge of connected components).
  // A vtkIdTypeArray (called "Vertex Ids") is associated with the VertexData of
  // a vtkReebGraph object, in order to retrieve if necessary the exact Ids of
  // the corresponding vertices in the input mesh.
  //
  // The edges of a vtkReebGraph object represent the regions of the input mesh
  // separated by the critical contours of the field, and where the connectivity
  // of the input field does not change.
  // A vtkVariantArray is associated with the EdgeDta of a vtkReebGraph object and
  // each entry of this array is a vtkAbstractArray containing the Ids of the
  // vertices of those regions, sorted by function value (useful for flexible
  // isosurface extraction or level set signature computation, for instance).
  //
  // See Graphics/Testing/Cxx/TestReebGraph.cxx for examples of traversals and
  // typical usages (customized simplification, skeletonization, contour spectra,
  //  etc.) of a vtkReebGraph object.
  //
  //
  // .SECTION See Also
  //      vtkReebGraphSimplificationMetric
  //      vtkPolyDataToReebGraphFilter
  //      vtkUnstructuredGridToReebGraphFilter
  //      vtkReebGraphSimplificationFilter
  //      vtkReebGraphSurfaceSkeletonFilter
  //      vtkReebGraphVolumeSkeletonFilter
  //      vtkAreaContourSpectrumFilter
  //      vtkVolumeContourSpectrumFilter
  //
  // .SECTION Tests
  //      Graphics/Testing/Cxx/TestReebGraph.cxx
  
  #ifndef __vtkReebGraph_h
  #define __vtkReebGraph_h
  
  #include  "vtkMutableDirectedGraph.h"
  
  class vtkDataArray;
  class vtkDataSet;
  class vtkIdList;
  class vtkPolyData;
  class vtkReebGraphSimplificationMetric;
  class vtkUnstructuredGrid;
  
  class VTK_FILTERING_EXPORT vtkReebGraph : public vtkMutableDirectedGraph
  {
  
  public:
  
    static vtkReebGraph *New();
  
    vtkTypeMacro(vtkReebGraph, vtkMutableDirectedGraph);
    void PrintSelf(ostream& os, vtkIndent indent);
    void PrintNodeData(ostream& os, vtkIndent indent);
  
    // Description:
    // Return class name of data type. This is one of VTK_STRUCTURED_GRID, 
    // VTK_STRUCTURED_POINTS, VTK_UNSTRUCTURED_GRID, VTK_POLY_DATA, or
    // VTK_RECTILINEAR_GRID (see vtkSetGet.h for definitions).
    // THIS METHOD IS THREAD SAFE
    virtual int GetDataObjectType() {return VTK_REEB_GRAPH;}
  
  
    enum
    {
      ERR_INCORRECT_FIELD = -1,
      ERR_NO_SUCH_FIELD = -2,
      ERR_NOT_A_SIMPLICIAL_MESH = -3
    };
  
    // Description:
    // Build the Reeb graph of the field 'scalarField' defined on the surface
    // mesh 'mesh'.
    //
    // Returned values:
    //
    // vtkReebGraph::ERR_INCORRECT_FIELD: 'scalarField' does not have as many
    // tuples as 'mesh' has vertices.
    //
    // vtkReebGraph::ERR_NOT_A_SIMPLICIAL_MESH: the input mesh 'mesh' is not a
    // simplicial mesh (for example, the surface mesh contains quads instead of
    // triangles).
    //
    int Build(vtkPolyData *mesh, vtkDataArray *scalarField);
  
    // Description:
    // Build the Reeb graph of the field 'scalarField' defined on the volume
    // mesh 'mesh'.
    //
    // Returned values:
    //
    // vtkReebGraph::ERR_INCORRECT_FIELD: 'scalarField' does not have as many
    // tuples as 'mesh' has vertices.
    //
    // vtkReebGraph::ERR_NOT_A_SIMPLICIAL_MESH: the input mesh 'mesh' is not a
    // simplicial mesh.
    //
    int Build(vtkUnstructuredGrid *mesh, vtkDataArray *scalarField);
  
  
    // Description:
    // Build the Reeb graph of the field given by the Id 'scalarFieldId',
    // defined on the surface mesh 'mesh'.
    //
    // Returned values:
    //
    // vtkReebGraph::ERR_INCORRECT_FIELD: 'scalarField' does not have as many
    // tuples as 'mesh' as vertices.
    //
    // vtkReebGraph::ERR_NOT_A_SIMPLICIAL_MESH: the input mesh 'mesh' is not a
    // simplicial mesh (for example, the surface mesh contains quads instead of
    // triangles).
    //
    // vtkReebGraph::ERR_NO_SUCH_FIELD: the scalar field given by the Id
    // 'scalarFieldId' does not exist.
    //
    int Build(vtkPolyData *mesh, vtkIdType scalarFieldId);
  
    // Description:
    // Build the Reeb graph of the field given by the Id 'scalarFieldId',
    // defined on the volume mesh 'mesh'.
    //
    // Returned values:
    //
    // vtkReebGraph::ERR_INCORRECT_FIELD: 'scalarField' does not have as many
    // tuples as 'mesh' as vertices.
    //
    // vtkReebGraph::ERR_NOT_A_SIMPLICIAL_MESH: the input mesh 'mesh' is not a
    // simplicial mesh.
    //
    // vtkReebGraph::ERR_NO_SUCH_FIELD: the scalar field given by the Id
    // 'scalarFieldId' does not exist.
    //
    int Build(vtkUnstructuredGrid *mesh, vtkIdType scalarFieldId);
  
  
    // Description:
    // Build the Reeb graph of the field given by the name 'scalarFieldName',
    // defined on the surface mesh 'mesh'.
    //
    // Returned values:
    //
    // vtkReebGraph::ERR_INCORRECT_FIELD: 'scalarField' does not have as many
    // tuples as 'mesh' as vertices.
    //
    // vtkReebGraph::ERR_NOT_A_SIMPLICIAL_MESH: the input mesh 'mesh' is not a
    // simplicial mesh (for example, the surface mesh contains quads instead of
    // triangles).
    //
    // vtkReebGraph::ERR_NO_SUCH_FIELD: the scalar field given by the name
    // 'scalarFieldName' does not exist.
    //
    int Build(vtkPolyData *mesh, const char* scalarFieldName);
  
    // Description:
    // Build the Reeb graph of the field given by the name 'scalarFieldName',
    // defined on the volume mesh 'mesh'.
    //
    // Returned values:
    //
    // vtkReebGraph::ERR_INCORRECT_FIELD: 'scalarField' does not have as many
    // tuples as 'mesh' as vertices.
    //
    // vtkReebGraph::ERR_NOT_A_SIMPLICIAL_MESH: the input mesh 'mesh' is not a
    // simplicial mesh.
    //
    // vtkReebGraph::ERR_NO_SUCH_FIELD: the scalar field given by the name
    // 'scalarFieldName' does not exist.
    //
    int Build(vtkUnstructuredGrid *mesh, const char* scalarFieldName);
  
    // Description:
    // Streaming Reeb graph computation.
    // Add to the streaming computation the triangle of the vtkPolyData surface
    // mesh described by
    // 	vertex0Id, scalar0
    // 	vertex1Id, scalar1
    // 	vertex2Id, scalar2
    //
    // 	where vertex<i>Id is the Id of the vertex in the vtkPolyData structure
    // 	and scalar<i> is the corresponding scalar field value.
    //
    // IMPORTANT: The stream _must_ be finalized with the "CloseStream" call.
    int StreamTriangle(	vtkIdType vertex0Id, double scalar0,
                        vtkIdType vertex1Id, double scalar1,
                        vtkIdType vertex2Id, double scalar2);
  
    // Description:
    // Streaming Reeb graph computation.
    // Add to the streaming computation the tetrahedra of the vtkUnstructuredGrid
    // volume mesh described by
    // 	vertex0Id, scalar0
    // 	vertex1Id, scalar1
    // 	vertex2Id, scalar2
    // 	vertex3Id, scalar3
    //
    // 	where vertex<i>Id is the Id of the vertex in the vtkUnstructuredGrid
    // 	structure and scalar<i> is the corresponding scalar field value.
    //
    // IMPORTANT: The stream _must_ be finalized with the "CloseStream" call.
    int StreamTetrahedron( vtkIdType vertex0Id, double scalar0,
                           vtkIdType vertex1Id, double scalar1,
                           vtkIdType vertex2Id, double scalar2,
                           vtkIdType vertex3Id, double scalar3);
  
    // Description:
    // Finalize internal data structures, in the case of streaming computations
    // (with StreamTriangle or StreamTetrahedron).
    // After this call, no more triangle or tetrahedron can be inserted via
    // StreamTriangle or StreamTetrahedron.
    // IMPORTANT: This method _must_ be called when the input stream is finished.
    // If you need to get a snapshot of the Reeb graph during the streaming
    // process (to parse or simplify it), do a DeepCopy followed by a
    // CloseStream on the copy.
    void CloseStream();
  
    // Descrition:
    // Implements deep copy
    void DeepCopy(vtkDataObject *src);
  
    // Description:
    // Simplify the Reeb graph given a threshold 'simplificationThreshold'
    // (between 0 and 1).
    //
    // This method is the core feature for Reeb graph multi-resolution hierarchy
    // construction.
    //
    // Return the number of arcs that have been removed through the simplification
    // process.
    //
    // 'simplificationThreshold' represents a "scale", under which each Reeb graph
    // feature is considered as noise. 'simplificationThreshold' is expressed as a
    // fraction of the scalar field overall span. It can vary from 0
    // (no simplification) to 1 (maximal simplification).
    //
    // 'simplificationMetric' is an object in charge of evaluating the importance
    // of a Reeb graph arc at each step of the simplification process.
    // if 'simplificationMetric' is NULL, the default strategy (persitence of the
    // scalar field) is used.
    // Customized simplification metric evaluation algorithm can be designed (see
    // vtkReebGraphSimplificationMetric), enabling the user to control the
    // definition of what should be considered as noise or signal.
    //
    // References:
    //
    // "Topological persistence and simplification",
    // H. Edelsbrunner, D. Letscher, and A. Zomorodian,
    // Discrete Computational Geometry, 28:511-533, 2002.
    //
    // "Extreme elevation on a 2-manifold",
    // P.K. Agarwal, H. Edelsbrunner, J. Harer, and Y. Wang,
    // ACM Symposium on Computational Geometry, pp. 357-365, 2004.
    //
    // "Simplifying flexible isosurfaces using local geometric measures",
    // H. Carr, J. Snoeyink, M van de Panne,
    // IEEE Visualization, 497-504, 2004
    //
    // "Loop surgery for volumetric meshes: Reeb graphs reduced to contour trees",
    // J. Tierny, A. Gyulassy, E. Simon, V. Pascucci,
    // IEEE Trans. on Vis. and Comp. Graph. (Proc of IEEE VIS), 15:1177-1184,2009.
    int Simplify(double simplificationThreshold,
      vtkReebGraphSimplificationMetric *simplificationMetric);
  
    // Description:
    // Use a pre-defined Reeb graph (post-processing).
    // Use with caution!
    void Set(vtkMutableDirectedGraph *g);
  
  protected:
  
    vtkReebGraph();
    ~vtkReebGraph();
  
    class Implementation;
    Implementation* Storage;
  
  private:
    vtkReebGraph(const vtkReebGraph&); // Not implemented.
    void operator=(const vtkReebGraph&); // Not implemented.
  
  };
  
  #endif
  