vtkGreedyTerrainDecimation Class Reference

#include <vtkGreedyTerrainDecimation.h>

Inheritance diagram for vtkGreedyTerrainDecimation:

[legend]Collaboration diagram for vtkGreedyTerrainDecimation:

[legend]List of all members.

---

Detailed Description

reduce height field (represented as image) to reduced TIN

vtkGreedyTerrainDecimation approximates a height field with a triangle mesh (triangulated irregular network - TIN) using a greedy insertion algorithm similar to that described by Garland and Heckbert in their paper "Fast Polygonal Approximations of Terrain and Height Fields" (Technical Report CMU-CS-95-181). The input to the filter is a height field (represented by a image whose scalar values are height) and the output of the filter is polygonal data consisting of triangles. The number of triangles in the output is reduced in number as compared to a naive tessellation of the input height field. This filter copies point data from the input to the output for those points present in the output.

An brief description of the algorithm is as follows. The algorithm uses a top-down decimation approach that initially represents the height field with two triangles (whose vertices are at the four corners of the image). These two triangles form a Delaunay triangulation. In an iterative fashion, the point in the image with the greatest error (as compared to the original height field) is injected into the triangulation. (Note that the single point with the greatest error per triangle is identified and placed into a priority queue. As the triangulation is modified, the errors from the deleted triangles are removed from the queue, error values from the new triangles are added.) The point whose error is at the top of the queue is added to the triangulaion modifying it using the standard incremental Delaunay point insertion (see vtkDelaunay2D) algorithm. Points are repeatedly inserted until the appropriate (user-specified) error criterion is met.

To use this filter, set the input and specify the error measure to be used. The error measure options are 1) the absolute number of triangles to be produced; 2) a fractional reduction of the mesh (numTris/maxTris) where maxTris is the largest possible number of triangles 2*(dims[0]-1)*(dims[1]-1); 3) an absolute measure on error (maximum difference in height field to reduced TIN); and 4) relative error (the absolute error is normalized by the diagonal of the bounding box of the height field).

Warning:

This algorithm requires the entire input dataset to be in memory, hence it may not work for extremely large images. Invoking BoundaryVertexDeletionOff will allow you to stitch together images with matching boundaries.

The input height image is assumed to be positioned in the x-y plane so the scalar value is the z-coordinate, height value.

See also:

vtkDecimatePro vtkQuadricDecimation vtkQuadricClustering

Tests:

vtkGreedyTerrainDecimation (Tests)

Definition at line 90 of file vtkGreedyTerrainDecimation.h.

virtual void	SetErrorMeasure (int)
virtual int	GetErrorMeasure ()
void	SetErrorMeasureToNumberOfTriangles ()
void	SetErrorMeasureToSpecifiedReduction ()
void	SetErrorMeasureToAbsoluteError ()
void	SetErrorMeasureToRelativeError ()
static vtkGreedyTerrainDecimation *	New ()
Public Types
typedef vtkPolyDataAlgorithm	Superclass
Public Member Functions
virtual const char *	GetClassName ()
virtual int	IsA (const char *type)
void	PrintSelf (ostream &os, vtkIndent indent)
virtual void	SetNumberOfTriangles (vtkIdType)
virtual vtkIdType	GetNumberOfTriangles ()
virtual void	SetReduction (double)
virtual double	GetReduction ()
virtual void	SetAbsoluteError (double)
virtual double	GetAbsoluteError ()
virtual void	SetRelativeError (double)
virtual double	GetRelativeError ()
virtual void	SetBoundaryVertexDeletion (int)
virtual int	GetBoundaryVertexDeletion ()
virtual void	BoundaryVertexDeletionOn ()
virtual void	BoundaryVertexDeletionOff ()
virtual void	SetComputeNormals (int)
virtual int	GetComputeNormals ()
virtual void	ComputeNormalsOn ()
virtual void	ComputeNormalsOff ()
Static Public Member Functions
static int	IsTypeOf (const char *type)
static vtkGreedyTerrainDecimation *	SafeDownCast (vtkObject *o)
Protected Member Functions
	vtkGreedyTerrainDecimation ()
	~vtkGreedyTerrainDecimation ()
virtual int	RequestData (vtkInformation *, vtkInformationVector **, vtkInformationVector *)
virtual int	FillInputPortInformation (int port, vtkInformation *info)
void	ComputePointNormal (int i, int j, float n[3])
void	EstimateOutputSize (const vtkIdType numInputPts, vtkIdType &numPts, vtkIdType &numTris)
virtual int	SatisfiesErrorMeasure (double error)
void	InsertBoundaryVertices ()
vtkIdType	AddPointToTriangulation (vtkIdType inputPtId)
vtkIdType	InsertNextPoint (vtkIdType inputPtId, double x[3])
double *	GetPoint (vtkIdType id)
void	GetPoint (vtkIdType id, double x[3])
void	GetTerrainPoint (int i, int j, double x[3])
void	ComputeImageCoordinates (vtkIdType inputPtId, int ij[2])
int	InCircle (double x[3], double x1[3], double x2[3], double x3[3])
vtkIdType	FindTriangle (double x[3], vtkIdType ptIds[3], vtkIdType tri, double tol, vtkIdType nei[3], vtkIdList *neighbors, int &status)
void	CheckEdge (vtkIdType ptId, double x[3], vtkIdType p1, vtkIdType p2, vtkIdType tri, int depth)
void	UpdateTriangles (vtkIdType meshPtId)
void	UpdateTriangle (vtkIdType triId, vtkIdType p1, vtkIdType p2, vtkIdType p3)
void	UpdateTriangle (vtkIdType triId, int ij1[2], int ij2[2], int ij3[2], double h[4])
int	CharacterizeTriangle (int ij1[2], int ij2[2], int ij[3], int *&min, int *&max, int *&midL, int *&midR, int *&mid, int mid2[2], double h[3], double &hMin, double &hMax, double &hL, double &hR)
Protected Attributes
int	ComputeNormals
vtkFloatArray *	Normals
int	ErrorMeasure
vtkIdType	NumberOfTriangles
double	Reduction
double	AbsoluteError
double	RelativeError
int	BoundaryVertexDeletion
vtkPolyData *	Mesh
vtkPointData *	InputPD
vtkPointData *	OutputPD
vtkDoubleArray *	Points
vtkDataArray *	Heights
vtkIdType	CurrentPointId
double	Tolerance
vtkIdList *	Neighbors
int	Dimensions [3]
double	Origin [3]
double	Spacing [3]
vtkIdType	MaximumNumberOfTriangles
double	Length
vtkPriorityQueue *	TerrainError
vtkGreedyTerrainDecimationTerrainInfoType *	TerrainInfo
vtkGreedyTerrainDecimationPointInfoType *	PointInfo

---

Member Typedef Documentation

typedef vtkPolyDataAlgorithm vtkGreedyTerrainDecimation::Superclass

Reimplemented from vtkPolyDataAlgorithm. Definition at line 93 of file vtkGreedyTerrainDecimation.h.

---

Constructor & Destructor Documentation

vtkGreedyTerrainDecimation::vtkGreedyTerrainDecimation (   )  [protected]

vtkGreedyTerrainDecimation::~vtkGreedyTerrainDecimation (   )  [protected]

---

Member Function Documentation

virtual const char* vtkGreedyTerrainDecimation::GetClassName (   )  [virtual]

Reimplemented from vtkPolyDataAlgorithm.

static int vtkGreedyTerrainDecimation::IsTypeOf (  const char *  type  )  [static]

Return 1 if this class type is the same type of (or a subclass of) the named class. Returns 0 otherwise. This method works in combination with vtkTypeRevisionMacro found in vtkSetGet.h. Reimplemented from vtkPolyDataAlgorithm.

virtual int vtkGreedyTerrainDecimation::IsA (  const char *  type  )  [virtual]

Return 1 if this class is the same type of (or a subclass of) the named class. Returns 0 otherwise. This method works in combination with vtkTypeRevisionMacro found in vtkSetGet.h. Reimplemented from vtkPolyDataAlgorithm.

static vtkGreedyTerrainDecimation* vtkGreedyTerrainDecimation::SafeDownCast (  vtkObject *  o  )  [static]

Reimplemented from vtkPolyDataAlgorithm.

void vtkGreedyTerrainDecimation::PrintSelf (  ostream &  os, vtkIndent  indent )  [virtual]

Methods invoked by print to print information about the object including superclasses. Typically not called by the user (use Print() instead) but used in the hierarchical print process to combine the output of several classes. Reimplemented from vtkPolyDataAlgorithm.

static vtkGreedyTerrainDecimation* vtkGreedyTerrainDecimation::New (   )  [static]

Instantiate the class. Reimplemented from vtkPolyDataAlgorithm.

virtual void vtkGreedyTerrainDecimation::SetErrorMeasure (  int   )  [virtual]

Specify how to terminate the algorithm: either as an absolute number of triangles, a relative number of triangles (normalized by the full resolution mesh), an absolute error (in the height field), or relative error (normalized by the length of the diagonal of the image).

virtual int vtkGreedyTerrainDecimation::GetErrorMeasure (   )  [virtual]

Specify how to terminate the algorithm: either as an absolute number of triangles, a relative number of triangles (normalized by the full resolution mesh), an absolute error (in the height field), or relative error (normalized by the length of the diagonal of the image).

void vtkGreedyTerrainDecimation::SetErrorMeasureToNumberOfTriangles (   )  [inline]

Specify how to terminate the algorithm: either as an absolute number of triangles, a relative number of triangles (normalized by the full resolution mesh), an absolute error (in the height field), or relative error (normalized by the length of the diagonal of the image). Definition at line 107 of file vtkGreedyTerrainDecimation.h. References VTK_ERROR_NUMBER_OF_TRIANGLES.

void vtkGreedyTerrainDecimation::SetErrorMeasureToSpecifiedReduction (   )  [inline]

Specify how to terminate the algorithm: either as an absolute number of triangles, a relative number of triangles (normalized by the full resolution mesh), an absolute error (in the height field), or relative error (normalized by the length of the diagonal of the image). Definition at line 109 of file vtkGreedyTerrainDecimation.h. References VTK_ERROR_SPECIFIED_REDUCTION.

void vtkGreedyTerrainDecimation::SetErrorMeasureToAbsoluteError (   )  [inline]

Specify how to terminate the algorithm: either as an absolute number of triangles, a relative number of triangles (normalized by the full resolution mesh), an absolute error (in the height field), or relative error (normalized by the length of the diagonal of the image). Definition at line 111 of file vtkGreedyTerrainDecimation.h. References VTK_ERROR_ABSOLUTE.

void vtkGreedyTerrainDecimation::SetErrorMeasureToRelativeError (   )  [inline]

Specify how to terminate the algorithm: either as an absolute number of triangles, a relative number of triangles (normalized by the full resolution mesh), an absolute error (in the height field), or relative error (normalized by the length of the diagonal of the image). Definition at line 113 of file vtkGreedyTerrainDecimation.h. References VTK_ERROR_RELATIVE.

virtual void vtkGreedyTerrainDecimation::SetNumberOfTriangles (  vtkIdType   )  [virtual]

Specify the number of triangles to produce on output. (It is a good idea to make sure this is less than a tessellated mesh at full resolution.) You need to set this value only when the error measure is set to NumberOfTriangles.

virtual vtkIdType vtkGreedyTerrainDecimation::GetNumberOfTriangles (   )  [virtual]

Specify the number of triangles to produce on output. (It is a good idea to make sure this is less than a tessellated mesh at full resolution.) You need to set this value only when the error measure is set to NumberOfTriangles.

virtual void vtkGreedyTerrainDecimation::SetReduction (  double   )  [virtual]

Specify the reduction of the mesh (represented as a fraction). Note that a value of 0.10 means a 10% reduction. You need to set this value only when the error measure is set to SpecifiedReduction.

virtual double vtkGreedyTerrainDecimation::GetReduction (   )  [virtual]

Specify the reduction of the mesh (represented as a fraction). Note that a value of 0.10 means a 10% reduction. You need to set this value only when the error measure is set to SpecifiedReduction.

virtual void vtkGreedyTerrainDecimation::SetAbsoluteError (  double   )  [virtual]

Specify the absolute error of the mesh; that is, the error in height between the decimated mesh and the original height field. You need to set this value only when the error measure is set to AbsoluteError.

virtual double vtkGreedyTerrainDecimation::GetAbsoluteError (   )  [virtual]

Specify the absolute error of the mesh; that is, the error in height between the decimated mesh and the original height field. You need to set this value only when the error measure is set to AbsoluteError.

virtual void vtkGreedyTerrainDecimation::SetRelativeError (  double   )  [virtual]

Specify the relative error of the mesh; that is, the error in height between the decimated mesh and the original height field normalized by the diagonal of the image. You need to set this value only when the error measure is set to RelativeError.

virtual double vtkGreedyTerrainDecimation::GetRelativeError (   )  [virtual]

Specify the relative error of the mesh; that is, the error in height between the decimated mesh and the original height field normalized by the diagonal of the image. You need to set this value only when the error measure is set to RelativeError.

virtual void vtkGreedyTerrainDecimation::SetBoundaryVertexDeletion (  int   )  [virtual]

Turn on/off the deletion of vertices on the boundary of a mesh. This may limit the maximum reduction that may be achieved.

virtual int vtkGreedyTerrainDecimation::GetBoundaryVertexDeletion (   )  [virtual]

Turn on/off the deletion of vertices on the boundary of a mesh. This may limit the maximum reduction that may be achieved.

virtual void vtkGreedyTerrainDecimation::BoundaryVertexDeletionOn (   )  [virtual]

Turn on/off the deletion of vertices on the boundary of a mesh. This may limit the maximum reduction that may be achieved.

virtual void vtkGreedyTerrainDecimation::BoundaryVertexDeletionOff (   )  [virtual]

Turn on/off the deletion of vertices on the boundary of a mesh. This may limit the maximum reduction that may be achieved.

virtual void vtkGreedyTerrainDecimation::SetComputeNormals (  int   )  [virtual]

Compute normals based on the input image. Off by default.

virtual int vtkGreedyTerrainDecimation::GetComputeNormals (   )  [virtual]

Compute normals based on the input image. Off by default.

virtual void vtkGreedyTerrainDecimation::ComputeNormalsOn (   )  [virtual]

Compute normals based on the input image. Off by default.

virtual void vtkGreedyTerrainDecimation::ComputeNormalsOff (   )  [virtual]

Compute normals based on the input image. Off by default.

virtual int vtkGreedyTerrainDecimation::RequestData (  vtkInformation *  , vtkInformationVector **  , vtkInformationVector *  )  [protected, virtual]

This is called by the superclass. This is the method you should override. Reimplemented from vtkPolyDataAlgorithm.

virtual int vtkGreedyTerrainDecimation::FillInputPortInformation (  int  port, vtkInformation *  info )  [protected, virtual]

Fill the input port information objects for this algorithm. This is invoked by the first call to GetInputPortInformation for each port so subclasses can specify what they can handle. Reimplemented from vtkPolyDataAlgorithm.

void vtkGreedyTerrainDecimation::ComputePointNormal (  int  i, int  j, float  n[3] )  [protected]

void vtkGreedyTerrainDecimation::EstimateOutputSize (  const vtkIdType  numInputPts, vtkIdType &  numPts, vtkIdType &  numTris )  [protected]

virtual int vtkGreedyTerrainDecimation::SatisfiesErrorMeasure (  double  error  )  [protected, virtual]

void vtkGreedyTerrainDecimation::InsertBoundaryVertices (   )  [protected]

vtkIdType vtkGreedyTerrainDecimation::AddPointToTriangulation (  vtkIdType  inputPtId  )  [protected]

vtkIdType vtkGreedyTerrainDecimation::InsertNextPoint (  vtkIdType  inputPtId, double  x[3] )  [protected]

double* vtkGreedyTerrainDecimation::GetPoint (  vtkIdType  id  )  [protected]

void vtkGreedyTerrainDecimation::GetPoint (  vtkIdType  id, double  x[3] )  [protected]

void vtkGreedyTerrainDecimation::GetTerrainPoint (  int  i, int  j, double  x[3] )  [protected]

void vtkGreedyTerrainDecimation::ComputeImageCoordinates (  vtkIdType  inputPtId, int  ij[2] )  [protected]

int vtkGreedyTerrainDecimation::InCircle (  double  x[3], double  x1[3], double  x2[3], double  x3[3] )  [protected]

vtkIdType vtkGreedyTerrainDecimation::FindTriangle (  double  x[3], vtkIdType  ptIds[3], vtkIdType  tri, double  tol, vtkIdType  nei[3], vtkIdList *  neighbors, int &  status )  [protected]

void vtkGreedyTerrainDecimation::CheckEdge (  vtkIdType  ptId, double  x[3], vtkIdType  p1, vtkIdType  p2, vtkIdType  tri, int  depth )  [protected]

void vtkGreedyTerrainDecimation::UpdateTriangles (  vtkIdType  meshPtId  )  [protected]

void vtkGreedyTerrainDecimation::UpdateTriangle (  vtkIdType  triId, vtkIdType  p1, vtkIdType  p2, vtkIdType  p3 )  [protected]

void vtkGreedyTerrainDecimation::UpdateTriangle (  vtkIdType  triId, int  ij1[2], int  ij2[2], int  ij3[2], double  h[4] )  [protected]

int vtkGreedyTerrainDecimation::CharacterizeTriangle (  int  ij1[2], int  ij2[2], int  ij[3], int *&  min, int *&  max, int *&  midL, int *&  midR, int *&  mid, int  mid2[2], double  h[3], double &  hMin, double &  hMax, double &  hL, double &  hR )  [protected]

---

Member Data Documentation

int vtkGreedyTerrainDecimation::ComputeNormals [protected]

Definition at line 174 of file vtkGreedyTerrainDecimation.h.

vtkFloatArray* vtkGreedyTerrainDecimation::Normals [protected]

Definition at line 175 of file vtkGreedyTerrainDecimation.h.

int vtkGreedyTerrainDecimation::ErrorMeasure [protected]

Definition at line 179 of file vtkGreedyTerrainDecimation.h.

vtkIdType vtkGreedyTerrainDecimation::NumberOfTriangles [protected]

Definition at line 180 of file vtkGreedyTerrainDecimation.h.

double vtkGreedyTerrainDecimation::Reduction [protected]

Definition at line 181 of file vtkGreedyTerrainDecimation.h.

double vtkGreedyTerrainDecimation::AbsoluteError [protected]

Definition at line 182 of file vtkGreedyTerrainDecimation.h.

double vtkGreedyTerrainDecimation::RelativeError [protected]

Definition at line 183 of file vtkGreedyTerrainDecimation.h.

int vtkGreedyTerrainDecimation::BoundaryVertexDeletion [protected]

Definition at line 184 of file vtkGreedyTerrainDecimation.h.

vtkPolyData* vtkGreedyTerrainDecimation::Mesh [protected]

Definition at line 187 of file vtkGreedyTerrainDecimation.h.

vtkPointData* vtkGreedyTerrainDecimation::InputPD [protected]

Definition at line 188 of file vtkGreedyTerrainDecimation.h.

vtkPointData* vtkGreedyTerrainDecimation::OutputPD [protected]

Definition at line 189 of file vtkGreedyTerrainDecimation.h.

vtkDoubleArray* vtkGreedyTerrainDecimation::Points [protected]

Definition at line 190 of file vtkGreedyTerrainDecimation.h.

vtkDataArray* vtkGreedyTerrainDecimation::Heights [protected]

Definition at line 191 of file vtkGreedyTerrainDecimation.h.

vtkIdType vtkGreedyTerrainDecimation::CurrentPointId [protected]

Definition at line 192 of file vtkGreedyTerrainDecimation.h.

double vtkGreedyTerrainDecimation::Tolerance [protected]

Definition at line 193 of file vtkGreedyTerrainDecimation.h.

vtkIdList* vtkGreedyTerrainDecimation::Neighbors [protected]

Definition at line 194 of file vtkGreedyTerrainDecimation.h.

int vtkGreedyTerrainDecimation::Dimensions[3] [protected]

Definition at line 195 of file vtkGreedyTerrainDecimation.h.

double vtkGreedyTerrainDecimation::Origin[3] [protected]

Definition at line 196 of file vtkGreedyTerrainDecimation.h.

double vtkGreedyTerrainDecimation::Spacing[3] [protected]

Definition at line 197 of file vtkGreedyTerrainDecimation.h.

vtkIdType vtkGreedyTerrainDecimation::MaximumNumberOfTriangles [protected]

Definition at line 198 of file vtkGreedyTerrainDecimation.h.

double vtkGreedyTerrainDecimation::Length [protected]

Definition at line 199 of file vtkGreedyTerrainDecimation.h.

vtkPriorityQueue* vtkGreedyTerrainDecimation::TerrainError [protected]

Definition at line 202 of file vtkGreedyTerrainDecimation.h.

vtkGreedyTerrainDecimationTerrainInfoType* vtkGreedyTerrainDecimation::TerrainInfo [protected]

Definition at line 203 of file vtkGreedyTerrainDecimation.h.

vtkGreedyTerrainDecimationPointInfoType* vtkGreedyTerrainDecimation::PointInfo [protected]

Definition at line 204 of file vtkGreedyTerrainDecimation.h.

---

The documentation for this class was generated from the following file:

• dox/Hybrid/vtkGreedyTerrainDecimation.h

---