forked from Kitware/VTK
-
Notifications
You must be signed in to change notification settings - Fork 0
/
vtkQuadricDecimation.h
286 lines (248 loc) · 9.08 KB
/
vtkQuadricDecimation.h
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
/*=========================================================================
Program: Visualization Toolkit
Module: vtkQuadricDecimation.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.
=========================================================================*/
/**
* @class vtkQuadricDecimation
* @brief reduce the number of triangles in a mesh
*
* vtkQuadricDecimation is a filter to reduce the number of triangles in
* a triangle mesh, forming a good approximation to the original geometry.
* The input to vtkQuadricDecimation is a vtkPolyData object, and only
* triangles are treated. If you desire to decimate polygonal meshes, first
* triangulate the polygons with vtkTriangleFilter.
*
* The algorithm is based on repeated edge collapses until the requested mesh
* reduction is achieved. Edges are placed in a priority queue based on the
* "cost" to delete the edge. The cost is an approximate measure of error
* (distance to the original surface)--described by the so-called quadric
* error measure. The quadric error measure is associated with each vertex of
* the mesh and represents a matrix of planes incident on that vertex. The
* distance of the planes to the vertex is the error in the position of the
* vertex (originally the vertex error iz zero). As edges are deleted, the
* quadric error measure associated with the two end points of the edge are
* summed (this combines the plane equations) and an optimal collapse point
* can be computed. Edges connected to the collapse point are then reinserted
* into the queue after computing the new cost to delete them. The process
* continues until the desired reduction level is reached or topological
* constraints prevent further reduction. Note that this basic algorithm can
* be extended to higher dimensions by
* taking into account variation in attributes (i.e., scalars, vectors, and
* so on).
*
* This paper is based on the work of Garland and Heckbert who first
* presented the quadric error measure at Siggraph '97 "Surface
* Simplification Using Quadric Error Metrics". For details of the algorithm
* Michael Garland's Ph.D. thesis is also recommended. Hughues Hoppe's Vis
* '99 paper, "New Quadric Metric for Simplifying Meshes with Appearance
* Attributes" is also a good take on the subject especially as it pertains
* to the error metric applied to attributes.
*
* @par Thanks:
* Thanks to Bradley Lowekamp of the National Library of Medicine/NIH for
* contributing this class.
*/
#ifndef vtkQuadricDecimation_h
#define vtkQuadricDecimation_h
#include "vtkFiltersCoreModule.h" // For export macro
#include "vtkPolyDataAlgorithm.h"
class vtkEdgeTable;
class vtkIdList;
class vtkPointData;
class vtkPriorityQueue;
class vtkDoubleArray;
class VTKFILTERSCORE_EXPORT vtkQuadricDecimation : public vtkPolyDataAlgorithm
{
public:
vtkTypeMacro(vtkQuadricDecimation, vtkPolyDataAlgorithm);
void PrintSelf(ostream& os, vtkIndent indent) VTK_OVERRIDE;
static vtkQuadricDecimation *New();
//@{
/**
* Set/Get the desired reduction (expressed as a fraction of the original
* number of triangles). The actual reduction may be less depending on
* triangulation and topological constraints.
*/
vtkSetClampMacro(TargetReduction, double, 0.0, 1.0);
vtkGetMacro(TargetReduction, double);
//@}
//@{
/**
* Decide whether to include data attributes in the error metric. If off,
* then only geometric error is used to control the decimation. By default
* the attribute errors are off.
*/
vtkSetMacro(AttributeErrorMetric, int);
vtkGetMacro(AttributeErrorMetric, int);
vtkBooleanMacro(AttributeErrorMetric, int);
//@}
//@{
/**
* Decide whether to activate volume preservation which greatly reduces errors
* in triangle normal direction. If off, volume preservation is disabled and
* if AttributeErrorMetric is active, these errors can be large.
* By default VolumePreservation is off
* the attribute errors are off.
*/
vtkSetMacro(VolumePreservation, int);
vtkGetMacro(VolumePreservation, int);
vtkBooleanMacro(VolumePreservation, int);
//@}
//@{
/**
* If attribute errors are to be included in the metric (i.e.,
* AttributeErrorMetric is on), then the following flags control which
* attributes are to be included in the error calculation. By default all
* of these are on.
*/
vtkSetMacro(ScalarsAttribute, int);
vtkGetMacro(ScalarsAttribute, int);
vtkBooleanMacro(ScalarsAttribute, int);
vtkSetMacro(VectorsAttribute, int);
vtkGetMacro(VectorsAttribute, int);
vtkBooleanMacro(VectorsAttribute, int);
vtkSetMacro(NormalsAttribute, int);
vtkGetMacro(NormalsAttribute, int);
vtkBooleanMacro(NormalsAttribute, int);
vtkSetMacro(TCoordsAttribute, int);
vtkGetMacro(TCoordsAttribute, int);
vtkBooleanMacro(TCoordsAttribute, int);
vtkSetMacro(TensorsAttribute, int);
vtkGetMacro(TensorsAttribute, int);
vtkBooleanMacro(TensorsAttribute, int);
//@}
//@{
/**
* Set/Get the scaling weight contribution of the attribute. These
* values are used to weight the contribution of the attributes
* towards the error metric.
*/
vtkSetMacro(ScalarsWeight, double);
vtkSetMacro(VectorsWeight, double);
vtkSetMacro(NormalsWeight, double);
vtkSetMacro(TCoordsWeight, double);
vtkSetMacro(TensorsWeight, double);
vtkGetMacro(ScalarsWeight, double);
vtkGetMacro(VectorsWeight, double);
vtkGetMacro(NormalsWeight, double);
vtkGetMacro(TCoordsWeight, double);
vtkGetMacro(TensorsWeight, double);
//@}
//@{
/**
* Get the actual reduction. This value is only valid after the
* filter has executed.
*/
vtkGetMacro(ActualReduction, double);
//@}
protected:
vtkQuadricDecimation();
~vtkQuadricDecimation() VTK_OVERRIDE;
int RequestData(vtkInformation *, vtkInformationVector **, vtkInformationVector *) VTK_OVERRIDE;
/**
* Do the dirty work of eliminating the edge; return the number of
* triangles deleted.
*/
int CollapseEdge(vtkIdType pt0Id, vtkIdType pt1Id);
/**
* Compute quadric for all vertices
*/
void InitializeQuadrics(vtkIdType numPts);
/**
* Free boundary edges are weighted
*/
void AddBoundaryConstraints(void);
/**
* Compute quadric for this vertex.
*/
void ComputeQuadric(vtkIdType pointId);
/**
* Add the quadrics for these 2 points since the edge between them has
* been collapsed.
*/
void AddQuadric(vtkIdType oldPtId, vtkIdType newPtId);
//@{
/**
* Compute cost for contracting this edge and the point that gives us this
* cost.
*/
double ComputeCost(vtkIdType edgeId, double *x);
double ComputeCost2(vtkIdType edgeId, double *x);
//@}
/**
* Find all edges that will have an endpoint change ids because of an edge
* collapse. p1Id and p2Id are the endpoints of the edge. p2Id is the
* pointId being removed.
*/
void FindAffectedEdges(vtkIdType p1Id, vtkIdType p2Id, vtkIdList *edges);
/**
* Find a cell that uses this edge.
*/
vtkIdType GetEdgeCellId(vtkIdType p1Id, vtkIdType p2Id);
int IsGoodPlacement(vtkIdType pt0Id, vtkIdType pt1Id, const double *x);
int TrianglePlaneCheck(const double t0[3], const double t1[3],
const double t2[3], const double *x);
void ComputeNumberOfComponents(void);
void UpdateEdgeData(vtkIdType ptoId, vtkIdType pt1Id);
//@{
/**
* Helper function to set and get the point and it's attributes as an array
*/
void SetPointAttributeArray(vtkIdType ptId, const double *x);
void GetPointAttributeArray(vtkIdType ptId, double *x);
//@}
/**
* Find out how many components there are for each attribute for this
* poly data.
*/
void GetAttributeComponents();
double TargetReduction;
double ActualReduction;
int AttributeErrorMetric;
int VolumePreservation;
int ScalarsAttribute;
int VectorsAttribute;
int NormalsAttribute;
int TCoordsAttribute;
int TensorsAttribute;
double ScalarsWeight;
double VectorsWeight;
double NormalsWeight;
double TCoordsWeight;
double TensorsWeight;
int NumberOfEdgeCollapses;
vtkEdgeTable *Edges;
vtkIdList *EndPoint1List;
vtkIdList *EndPoint2List;
vtkPriorityQueue *EdgeCosts;
vtkDoubleArray *TargetPoints;
int NumberOfComponents;
vtkPolyData *Mesh;
struct ErrorQuadric
{
double *Quadric;
};
// One ErrorQuadric per point
ErrorQuadric *ErrorQuadrics;
// Contains 4 doubles per point. Length = nPoints * 4
double *VolumeConstraints;
int AttributeComponents[6];
double AttributeScale[6];
// Temporary variables for performance
vtkIdList *CollapseCellIds;
double *TempX;
double *TempQuad;
double *TempB;
double **TempA;
double *TempData;
private:
vtkQuadricDecimation(const vtkQuadricDecimation&) VTK_DELETE_FUNCTION;
void operator=(const vtkQuadricDecimation&) VTK_DELETE_FUNCTION;
};
#endif