You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
367 lines
13 KiB
C++
367 lines
13 KiB
C++
/*=========================================================================
|
|
|
|
Program: Visualization Toolkit
|
|
Module: vtkReebGraph.h
|
|
|
|
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.
|
|
----------------------------------------------------------------------------*/
|
|
|
|
/**
|
|
* @class vtkReebGraph
|
|
* @brief Reeb graph computation for PL scalar fields.
|
|
*
|
|
*
|
|
* 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.
|
|
*
|
|
*
|
|
* @sa
|
|
* vtkReebGraphSimplificationMetric
|
|
* vtkPolyDataToReebGraphFilter
|
|
* vtkUnstructuredGridToReebGraphFilter
|
|
* vtkReebGraphSimplificationFilter
|
|
* vtkReebGraphSurfaceSkeletonFilter
|
|
* vtkReebGraphVolumeSkeletonFilter
|
|
* vtkAreaContourSpectrumFilter
|
|
* vtkVolumeContourSpectrumFilter
|
|
*
|
|
* @par Tests:
|
|
* Graphics/Testing/Cxx/TestReebGraph.cxx
|
|
*/
|
|
|
|
#ifndef vtkReebGraph_h
|
|
#define vtkReebGraph_h
|
|
|
|
#include "vtkCommonDataModelModule.h" // For export macro
|
|
#include "vtkMutableDirectedGraph.h"
|
|
|
|
class vtkDataArray;
|
|
class vtkDataSet;
|
|
class vtkIdList;
|
|
class vtkPolyData;
|
|
class vtkReebGraphSimplificationMetric;
|
|
class vtkUnstructuredGrid;
|
|
|
|
class VTKCOMMONDATAMODEL_EXPORT vtkReebGraph : public vtkMutableDirectedGraph
|
|
{
|
|
|
|
public:
|
|
static vtkReebGraph* New();
|
|
|
|
vtkTypeMacro(vtkReebGraph, vtkMutableDirectedGraph);
|
|
void PrintSelf(ostream& os, vtkIndent indent) override;
|
|
void PrintNodeData(ostream& os, vtkIndent indent);
|
|
|
|
/**
|
|
* 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
|
|
*/
|
|
int GetDataObjectType() override { return VTK_REEB_GRAPH; }
|
|
|
|
enum
|
|
{
|
|
ERR_INCORRECT_FIELD = -1,
|
|
ERR_NO_SUCH_FIELD = -2,
|
|
ERR_NOT_A_SIMPLICIAL_MESH = -3
|
|
};
|
|
|
|
/**
|
|
* 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);
|
|
|
|
/**
|
|
* 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);
|
|
|
|
/**
|
|
* 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);
|
|
|
|
/**
|
|
* 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);
|
|
|
|
/**
|
|
* 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);
|
|
|
|
/**
|
|
* 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);
|
|
|
|
/**
|
|
* 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);
|
|
|
|
/**
|
|
* 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);
|
|
|
|
/**
|
|
* 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();
|
|
|
|
// Description:
|
|
// Implements deep copy
|
|
void DeepCopy(vtkDataObject* src) override;
|
|
|
|
/**
|
|
* 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 nullptr, 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);
|
|
|
|
/**
|
|
* Use a pre-defined Reeb graph (post-processing).
|
|
* Use with caution!
|
|
*/
|
|
void Set(vtkMutableDirectedGraph* g);
|
|
|
|
protected:
|
|
vtkReebGraph();
|
|
~vtkReebGraph() override;
|
|
|
|
class Implementation;
|
|
Implementation* Storage;
|
|
|
|
private:
|
|
vtkReebGraph(const vtkReebGraph&) = delete;
|
|
void operator=(const vtkReebGraph&) = delete;
|
|
};
|
|
|
|
#endif
|