/usr/include/vtk-5.8/vtkDecimatePro.h is in libvtk5-dev 5.8.0-5.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 | /*=========================================================================
Program: Visualization Toolkit
Module: vtkDecimatePro.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.
=========================================================================*/
// .NAME vtkDecimatePro - reduce the number of triangles in a mesh
// .SECTION Description
// vtkDecimatePro is a filter to reduce the number of triangles in a triangle
// mesh, forming a good approximation to the original geometry. The input to
// vtkDecimatePro is a vtkPolyData object, and only triangles are treated. If
// you desire to decimate polygonal meshes, first triangulate the polygons
// with vtkTriangleFilter object.
//
// The implementation of vtkDecimatePro is similar to the algorithm
// originally described in "Decimation of Triangle Meshes", Proc Siggraph
// `92, with three major differences. First, this algorithm does not
// necessarily preserve the topology of the mesh. Second, it is guaranteed to
// give the a mesh reduction factor specified by the user (as long as certain
// constraints are not set - see Caveats). Third, it is set up generate
// progressive meshes, that is a stream of operations that can be easily
// transmitted and incrementally updated (see Hugues Hoppe's Siggraph '96
// paper on progressive meshes).
//
// The algorithm proceeds as follows. Each vertex in the mesh is classified
// and inserted into a priority queue. The priority is based on the error to
// delete the vertex and retriangulate the hole. Vertices that cannot be
// deleted or triangulated (at this point in the algorithm) are
// skipped. Then, each vertex in the priority queue is processed (i.e.,
// deleted followed by hole triangulation using edge collapse). This
// continues until the priority queue is empty. Next, all remaining vertices
// are processed, and the mesh is split into separate pieces along sharp
// edges or at non-manifold attachment points and reinserted into the
// priority queue. Again, the priority queue is processed until empty. If
// the desired reduction is still not achieved, the remaining vertices are
// split as necessary (in a recursive fashion) so that it is possible to
// eliminate every triangle as necessary.
//
// To use this object, at a minimum you need to specify the ivar
// TargetReduction. The algorithm is guaranteed to generate a reduced mesh
// at this level as long as the following four conditions are met: 1)
// topology modification is allowed (i.e., the ivar PreserveTopology is off);
// 2) mesh splitting is enabled (i.e., the ivar Splitting is on); 3) the
// algorithm is allowed to modify the boundary of the mesh (i.e., the ivar
// BoundaryVertexDeletion is on); and 4) the maximum allowable error (i.e.,
// the ivar MaximumError) is set to VTK_DOUBLE_MAX. Other important
// parameters to adjust include the FeatureAngle and SplitAngle ivars, since
// these can impact the quality of the final mesh. Also, you can set the
// ivar AccumulateError to force incremental error update and distribution
// to surrounding vertices as each vertex is deleted. The accumulated error
// is a conservative global error bounds and decimation error, but requires
// additional memory and time to compute.
// .SECTION Caveats
// To guarantee a given level of reduction, the ivar PreserveTopology must
// be off; the ivar Splitting is on; the ivar BoundaryVertexDeletion is on;
// and the ivar MaximumError is set to VTK_DOUBLE_MAX.
//
// If PreserveTopology is off, and SplitEdges is off; the mesh topology may
// be modified by closing holes.
//
// Once mesh splitting begins, the feature angle is set to the split angle.
// .SECTION See Also
// vtkDecimate vtkQuadricClustering vtkQuadricDecimation
#ifndef __vtkDecimatePro_h
#define __vtkDecimatePro_h
#include "vtkPolyDataAlgorithm.h"
#include "vtkCell.h" // Needed for VTK_CELL_SIZE
class vtkDoubleArray;
class vtkPriorityQueue;
class VTK_GRAPHICS_EXPORT vtkDecimatePro : public vtkPolyDataAlgorithm
{
public:
vtkTypeMacro(vtkDecimatePro,vtkPolyDataAlgorithm);
void PrintSelf(ostream& os, vtkIndent indent);
// Description:
// Create object with specified reduction of 90% and feature angle of
// 15 degrees. Edge splitting is on, defer splitting is on, and the
// split angle is 75 degrees. Topology preservation is off, delete
// boundary vertices is on, and the maximum error is set to
// VTK_DOUBLE_MAX. The inflection point ratio is 10 and the vertex
// degree is 25. Error accumulation is turned off.
static vtkDecimatePro *New();
// Description:
// Specify the desired reduction in the total number of polygons (e.g., if
// TargetReduction is set to 0.9, this filter will try to reduce the data set
// to 10% of its original size). Because of various constraints, this level of
// reduction may not be realized. If you want to guarantee a particular
// reduction, you must turn off PreserveTopology, turn on SplitEdges and
// BoundaryVertexDeletion, and set the MaximumError to VTK_DOUBLE_MAX (these
// ivars are initialized this way when the object is instantiated).
vtkSetClampMacro(TargetReduction,double,0.0,1.0);
vtkGetMacro(TargetReduction,double);
// Description:
// Turn on/off whether to preserve the topology of the original mesh. If
// on, mesh splitting and hole elimination will not occur. This may limit
// the maximum reduction that may be achieved.
vtkSetMacro(PreserveTopology,int);
vtkGetMacro(PreserveTopology,int);
vtkBooleanMacro(PreserveTopology,int);
// Description:
// Specify the mesh feature angle. This angle is used to define what
// an edge is (i.e., if the surface normal between two adjacent triangles
// is >= FeatureAngle, an edge exists).
vtkSetClampMacro(FeatureAngle,double,0.0,180.0);
vtkGetMacro(FeatureAngle,double);
// Description:
// Turn on/off the splitting of the mesh at corners, along edges, at
// non-manifold points, or anywhere else a split is required. Turning
// splitting off will better preserve the original topology of the
// mesh, but you may not obtain the requested reduction.
vtkSetMacro(Splitting,int);
vtkGetMacro(Splitting,int);
vtkBooleanMacro(Splitting,int);
// Description:
// Specify the mesh split angle. This angle is used to control the splitting
// of the mesh. A split line exists when the surface normals between
// two edge connected triangles are >= SplitAngle.
vtkSetClampMacro(SplitAngle,double,0.0,180.0);
vtkGetMacro(SplitAngle,double);
// Description:
// In some cases you may wish to split the mesh prior to algorithm
// execution. This separates the mesh into semi-planar patches, which are
// disconnected from each other. This can give superior results in some
// cases. If the ivar PreSplitMesh ivar is enabled, the mesh is split with
// the specified SplitAngle. Otherwise mesh splitting is deferred as long
// as possible.
vtkSetMacro(PreSplitMesh,int);
vtkGetMacro(PreSplitMesh,int);
vtkBooleanMacro(PreSplitMesh,int);
// Description:
// Set the largest decimation error that is allowed during the decimation
// process. This may limit the maximum reduction that may be achieved. The
// maximum error is specified as a fraction of the maximum length of
// the input data bounding box.
vtkSetClampMacro(MaximumError,double,0.0,VTK_DOUBLE_MAX);
vtkGetMacro(MaximumError,double);
// Description:
// The computed error can either be computed directly from the mesh
// or the error may be accumulated as the mesh is modified. If the error
// is accumulated, then it represents a global error bounds, and the ivar
// MaximumError becomes a global bounds on mesh error. Accumulating the
// error requires extra memory proportional to the number of vertices in
// the mesh. If AccumulateError is off, then the error is not accumulated.
vtkSetMacro(AccumulateError,int);
vtkGetMacro(AccumulateError,int);
vtkBooleanMacro(AccumulateError,int);
// Description:
// The MaximumError is normally defined as a fraction of the dataset bounding
// diagonal. By setting ErrorIsAbsolute to 1, the error is instead defined
// as that specified by AbsoluteError. By default ErrorIsAbsolute=0.
vtkSetMacro(ErrorIsAbsolute,int);
vtkGetMacro(ErrorIsAbsolute,int);
// Description:
// Same as MaximumError, but to be used when ErrorIsAbsolute is 1
vtkSetClampMacro(AbsoluteError,double,0.0,VTK_DOUBLE_MAX);
vtkGetMacro(AbsoluteError,double);
// Description:
// Turn on/off the deletion of vertices on the boundary of a mesh. This
// may limit the maximum reduction that may be achieved.
vtkSetMacro(BoundaryVertexDeletion,int);
vtkGetMacro(BoundaryVertexDeletion,int);
vtkBooleanMacro(BoundaryVertexDeletion,int);
// Description:
// If the number of triangles connected to a vertex exceeds "Degree", then
// the vertex will be split. (NOTE: the complexity of the triangulation
// algorithm is proportional to Degree^2. Setting degree small can improve
// the performance of the algorithm.)
vtkSetClampMacro(Degree,int,25,VTK_CELL_SIZE);
vtkGetMacro(Degree,int);
// Description:
// Specify the inflection point ratio. An inflection point occurs
// when the ratio of reduction error between two iterations is greater
// than or equal to the InflectionPointRatio.
vtkSetClampMacro(InflectionPointRatio,double,1.001,VTK_DOUBLE_MAX);
vtkGetMacro(InflectionPointRatio,double);
// Description:
// Get the number of inflection points. Only returns a valid value after
// the filter has executed. The values in the list are mesh reduction
// values at each inflection point. Note: the first inflection point always
// occurs right before non-planar triangles are decimated (i.e., as the
// error becomes non-zero).
vtkIdType GetNumberOfInflectionPoints();
// Description:
// Get a list of inflection points. These are double values 0 < r <= 1.0
// corresponding to reduction level, and there are a total of
// NumberOfInflectionPoints() values. You must provide an array (of
// the correct size) into which the inflection points are written.
void GetInflectionPoints(double *inflectionPoints);
// Description:
// Get a list of inflection points. These are double values 0 < r <= 1.0
// corresponding to reduction level, and there are a total of
// NumberOfInflectionPoints() values. You must provide an array (of
// the correct size) into which the inflection points are written.
// This method returns a pointer to a list of inflection points.
double *GetInflectionPoints();
protected:
vtkDecimatePro();
~vtkDecimatePro();
int RequestData(vtkInformation *, vtkInformationVector **, vtkInformationVector *);
double TargetReduction;
double FeatureAngle;
double MaximumError;
double AbsoluteError;
int ErrorIsAbsolute;
int AccumulateError;
double SplitAngle;
int Splitting;
int PreSplitMesh;
int BoundaryVertexDeletion;
int PreserveTopology;
int Degree;
double InflectionPointRatio;
vtkDoubleArray *InflectionPoints;
// to replace a static object
vtkIdList *Neighbors;
vtkPriorityQueue *EdgeLengths;
void SplitMesh();
int EvaluateVertex(vtkIdType ptId, unsigned short int numTris,
vtkIdType *tris, vtkIdType fedges[2]);
vtkIdType FindSplit(int type, vtkIdType fedges[2], vtkIdType& pt1,
vtkIdType& pt2, vtkIdList *CollapseTris);
int IsValidSplit(int index);
void SplitLoop(vtkIdType fedges[2], vtkIdType& n1, vtkIdType *l1,
vtkIdType& n2, vtkIdType *l2);
void SplitVertex(vtkIdType ptId,int type, unsigned short int numTris,
vtkIdType *tris, int insert);
int CollapseEdge(int type, vtkIdType ptId, vtkIdType collapseId,
vtkIdType pt1, vtkIdType pt2, vtkIdList *CollapseTris);
void DistributeError(double error);
//
// Special classes for manipulating data
//
//BTX - begin tcl exclude
//
// Special structures for building loops
class LocalVertex
{
public:
vtkIdType id;
double x[3];
double FAngle;
};
typedef LocalVertex *LocalVertexPtr;
class LocalTri
{
public:
vtkIdType id;
double area;
double n[3];
vtkIdType verts[3];
};
typedef LocalTri *LocalTriPtr;
class VertexArray;
friend class VertexArray;
class VertexArray { //;prevent man page generation
public:
VertexArray(const vtkIdType sz)
{this->MaxId = -1; this->Array = new LocalVertex[sz];};
~VertexArray()
{
if (this->Array)
{
delete [] this->Array;
}
};
vtkIdType GetNumberOfVertices() {return this->MaxId + 1;};
void InsertNextVertex(LocalVertex& v)
{this->MaxId++; this->Array[this->MaxId] = v;};
LocalVertex& GetVertex(vtkIdType i) {return this->Array[i];};
void Reset() {this->MaxId = -1;};
LocalVertex *Array; // pointer to data
vtkIdType MaxId; // maximum index inserted thus far
};
class TriArray;
friend class TriArray;
class TriArray { //;prevent man page generation
public:
TriArray(const vtkIdType sz)
{this->MaxId = -1; this->Array = new LocalTri[sz];};
~TriArray()
{
if (this->Array)
{
delete [] this->Array;
}
};
vtkIdType GetNumberOfTriangles() {return this->MaxId + 1;};
void InsertNextTriangle(LocalTri& t)
{this->MaxId++; this->Array[this->MaxId] = t;};
LocalTri& GetTriangle(vtkIdType i) {return this->Array[i];};
void Reset() {this->MaxId = -1;};
LocalTri *Array; // pointer to data
vtkIdType MaxId; // maximum index inserted thus far
};
//ETX - end tcl exclude
//
private:
void InitializeQueue(vtkIdType numPts);
void DeleteQueue();
void Insert(vtkIdType id, double error= -1.0);
int Pop(double &error);
double DeleteId(vtkIdType id);
void Reset();
vtkPriorityQueue *Queue;
vtkDoubleArray *VertexError;
VertexArray *V;
TriArray *T;
// Use to be static variables used by object
vtkPolyData *Mesh; //operate on this data structure
double Pt[3]; //least squares plane point
double Normal[3]; //least squares plane normal
double LoopArea; //the total area of all triangles in a loop
double CosAngle; //Cosine of dihedral angle
double Tolerance; //Intersection tolerance
double X[3]; //coordinates of current point
int NumCollapses; //Number of times edge collapses occur
int NumMerges; //Number of times vertex merges occur
int Split; //Controls whether and when vertex splitting occurs
int VertexDegree; //Maximum number of triangles that can use a vertex
vtkIdType NumberOfRemainingTris; //Number of triangles left in the mesh
double TheSplitAngle; //Split angle
int SplitState; //State of the splitting process
double Error; //Maximum allowable surface error
private:
vtkDecimatePro(const vtkDecimatePro&); // Not implemented.
void operator=(const vtkDecimatePro&); // Not implemented.
};
#endif
|