1 /*=========================================================================
3 Program: Visualization Toolkit
4 Module: $RCSfile: vtkQuadricClustering.h,v $
6 Date: $Date: 2003/11/07 16:07:10 $
7 Version: $Revision: 1.33.2.1 $
9 Copyright (c) 1993-2002 Ken Martin, Will Schroeder, Bill Lorensen
11 See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
13 This software is distributed WITHOUT ANY WARRANTY; without even
14 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 PURPOSE. See the above copyright notice for more information.
17 =========================================================================*/
18 // .NAME vtkQuadricClustering - reduce the number of triangles in a mesh
19 // .SECTION Description
20 // vtkQuadricClustering is a filter to reduce the number of triangles in a
21 // triangle mesh, forming a good approximation to the original geometry. The
22 // input to vtkQuadricClustering is a vtkPolyData object, and all types of
23 // polygonal data are handled.
25 // The algorithm used is the one described by Peter Lindstrom in his Siggraph
26 // 2000 paper, "Out-of-Core Simplification of Large Polygonal Models." The
27 // general approach of the algorithm is to cluster vertices in a uniform
28 // binning of space, accumulating the quadric of each triangle (pushed out to
29 // the triangles vertices) within each bin, and then determining an optimal
30 // position for a single vertex in a bin by using the accumulated quadric. In
31 // more detail, the algorithm first gets the bounds of the input poly data.
32 // It then breaks this bounding volume into a user-specified number of
33 // spatial bins. It then reads each triangle from the input and hashes its
34 // vertices into these bins. (If this is the first time a bin has been
35 // visited, initialize its quadric to the 0 matrix.) The algorithm computes
36 // the error quadric for this triangle and adds it to the existing quadric of
37 // the bin in which each vertex is contained. Then, if 2 or more vertices of
38 // the triangle fall in the same bin, the triangle is dicarded. If the
39 // triangle is not discarded, it adds the triangle to the list of output
40 // triangles as a list of vertex identifiers. (There is one vertex id per
41 // bin.) After all the triangles have been read, the representative vertex
42 // for each bin is computed (an optimal location is found) using the quadric
43 // for that bin. This determines the spatial location of the vertices of
44 // each of the triangles in the output.
46 // To use this filter, specify the divisions defining the spatial subdivision
47 // in the x, y, and z directions. You must also specify an input vtkPolyData.
48 // Then choose to either 1) use the original points that minimize the quadric
49 // error to produce the output triangles or 2) compute an optimal position in
50 // each bin to produce the output triangles (recommended and default behavior).
52 // This filter can take multiple inputs. To do this, the user must explicity
53 // call StartAppend, Append (once for each input), and EndAppend. StartAppend
54 // sets up the data structure to hold the quadric matrices. Append processes
55 // each triangle in the input poly data it was called on, hashes its vertices
56 // to the appropriate bins, determines whether to keep this triangle, and
57 // updates the appropriate quadric matrices. EndAppend determines the spatial
58 // location of each of the representative vertices for the visited bins. While
59 // this approach does not fit into the visualization architecture and requires
60 // manual control, it has the advantage that extremely large data can be
61 // processed in pieces and appended to the filter piece-by-piece.
65 // This filter can drastically affect topology, i.e., topology is not
68 // The filter handles input triangle strips and arbitrary polygons. Arbitrary
69 // polygons are assumed convex: during insertion they are triangulated using
70 // a fan of triangles from the first point in the polygons. If the polygon is
71 // concave, this can produce bad results. In this case, use vtkTriangleFilter
72 // to triangulate the polygons first.
75 // vtkQuadricDecimation vtkDecimatePro vtkDecimate
77 #ifndef __vtkQuadricClustering_h
78 #define __vtkQuadricClustering_h
80 #include "vtkPolyDataToPolyDataFilter.h"
83 class vtkFeatureEdges;
86 class VTK_GRAPHICS_EXPORT vtkQuadricClustering : public vtkPolyDataToPolyDataFilter
89 vtkTypeRevisionMacro(vtkQuadricClustering, vtkPolyDataToPolyDataFilter);
90 void PrintSelf(ostream& os, vtkIndent indent);
91 static vtkQuadricClustering *New();
94 // Set/Get the number of divisions along each axis for the spatial bins.
95 // The number of spatial bins is NumberOfXDivisions*NumberOfYDivisions*
96 // NumberOfZDivisions. The filter may choose to ignore large numbers of
97 // divisions if the input has few points and AutoAdjustNumberOfDivisions
99 void SetNumberOfXDivisions(int num);
100 void SetNumberOfYDivisions(int num);
101 void SetNumberOfZDivisions(int num);
102 vtkGetMacro(NumberOfXDivisions, int);
103 vtkGetMacro(NumberOfYDivisions, int);
104 vtkGetMacro(NumberOfZDivisions, int);
105 void SetNumberOfDivisions(int div[3]);
106 int *GetNumberOfDivisions();
107 void GetNumberOfDivisions(int div[3]);
110 // Enable automatic adjustment of number of divisions. If off, the number
111 // of divisions specified by the user is always used (as long as it is valid).
112 vtkSetMacro(AutoAdjustNumberOfDivisions,int);
113 vtkGetMacro(AutoAdjustNumberOfDivisions,int);
114 vtkBooleanMacro(AutoAdjustNumberOfDivisions,int);
117 // This is an alternative way to set up the bins. If you are trying to match
118 // boundaries between pieces, then you should use these methods rather than
119 // SetNumberOfDivisions. To use these methods, specify the origin and spacing
120 // of the spatial binning.
121 void SetDivisionOrigin(float x, float y, float z);
122 void SetDivisionOrigin(float o[3])
123 {this->SetDivisionOrigin(o[0],o[1],o[2]);}
124 vtkGetVector3Macro(DivisionOrigin, float);
125 void SetDivisionSpacing(float x, float y, float z);
126 void SetDivisionSpacing(float s[3])
127 {this->SetDivisionSpacing(s[0],s[1],s[2]);}
128 vtkGetVector3Macro(DivisionSpacing, float);
131 // Normally the point that minimizes the quadric error function is used as
132 // the output of the bin. When this flag is on, the bin point is forced to
133 // be one of the points from the input (the one with the smallest
134 // error). This option does not work (i.e., input points cannot be used)
135 // when the append methods (StartAppend(), Append(), EndAppend()) are being
137 vtkSetMacro(UseInputPoints, int);
138 vtkGetMacro(UseInputPoints, int);
139 vtkBooleanMacro(UseInputPoints, int);
142 // By default, this flag is off. When "UseFeatureEdges" is on, then
143 // quadrics are computed for boundary edges/feature edges. They influence
144 // the quadrics (position of points), but not the mesh. Which features to
145 // use can be controlled by the filter "FeatureEdges".
146 vtkSetMacro(UseFeatureEdges, int);
147 vtkGetMacro(UseFeatureEdges, int);
148 vtkBooleanMacro(UseFeatureEdges, int);
149 vtkFeatureEdges *GetFeatureEdges() {return this->FeatureEdges;}
152 // By default, this flag is off. It only has an effect when
153 // "UseFeatureEdges" is also on. When "UseFeaturePoints" is on, then
154 // quadrics are computed for boundary / feature points used in the boundary
155 // / feature edges. They influence the quadrics (position of points), but
157 vtkSetMacro(UseFeaturePoints, int);
158 vtkGetMacro(UseFeaturePoints, int);
159 vtkBooleanMacro(UseFeaturePoints, int);
162 // Set/Get the angle to use in determining whether a point on a boundary /
163 // feature edge is a feature point.
164 vtkSetClampMacro(FeaturePointsAngle, float, 0.0, 180.0);
165 vtkGetMacro(FeaturePointsAngle, float);
168 // When this flag is on (and it is on by default), then triangles that are
169 // completely contained in a bin are added to the bin quadrics. When the
170 // the flag is off the filter operates faster, but the surface may not be
172 vtkSetMacro(UseInternalTriangles, int);
173 vtkGetMacro(UseInternalTriangles, int);
174 vtkBooleanMacro(UseInternalTriangles, int);
177 // These methods provide an alternative way of executing the filter.
178 // PolyData can be added to the result in pieces (append).
179 // In this mode, the user must specify the bounds of the entire model
180 // as an argument to the "StartAppend" method.
181 void StartAppend(float *bounds);
182 void StartAppend(float x0,float x1,float y0,float y1,float z0,float z1)
183 {float b[6]; b[0]=x0; b[1]=x1; b[2]=y0; b[3]=y1; b[4]=z0; b[5]=z1;
184 this->StartAppend(b);}
185 void Append(vtkPolyData *piece);
189 // This flag makes the filter copy cell data from input to output
190 // (the best it can). It uses input cells that trigger the addition
191 // of output cells (no averaging). This is off by default, and does
192 // not work when append is being called explicitely (non-pipeline usage).
193 vtkSetMacro(CopyCellData, int);
194 vtkGetMacro(CopyCellData, int);
195 vtkBooleanMacro(CopyCellData, int);
198 vtkQuadricClustering();
199 ~vtkQuadricClustering();
204 // Given a point, determine what bin it falls into.
205 vtkIdType HashPoint(float point[3]);
208 // Determine the representative point for this bin.
209 void ComputeRepresentativePoint(float quadric[9], vtkIdType binId,
213 // Add triangles to the quadric array. If geometry flag is on then
214 // triangles are added to the output.
215 void AddPolygons(vtkCellArray *polys, vtkPoints *points, int geometryFlag);
216 void AddStrips(vtkCellArray *strips, vtkPoints *points, int geometryFlag);
217 void AddTriangle(vtkIdType *binIds, float *pt0, float *pt1, float *pt2,
221 // Add edges to the quadric array. If geometry flag is on then
222 // edges are added to the output.
223 void AddEdges(vtkCellArray *edges, vtkPoints *points,
225 void AddEdge(vtkIdType *binIds, float *pt0, float *pt1, int geometeryFlag);
228 // Add vertices to the quadric array. If geometry flag is on then
229 // vertices are added to the output.
230 void AddVertices(vtkCellArray *verts, vtkPoints *points, int geometryFlag);
231 void AddVertex(vtkIdType binId, float *pt, int geometryFlag);
234 // Initialize the quadric matrix to 0's.
235 void InitializeQuadric(float quadric[9]);
238 // Add this quadric to the quadric already associated with this bin.
239 void AddQuadric(vtkIdType binId, float quadric[9]);
242 // Find the feature points of a given set of edges.
243 // The points returned are (1) those used by only one edge, (2) those
244 // used by > 2 edges, and (3) those where the angle between 2 edges
245 // using this point is < angle.
246 void FindFeaturePoints(vtkCellArray *edges, vtkPoints *edgePts, float angle);
249 // This method will rep[lace the quadric generated points with the
250 // input points with the lowest error.
251 void EndAppendUsingPoints(vtkPolyData *input);
255 // This method sets the verticies of the output.
256 // It duplicates the structure of the input cells (but decimiated).
257 void EndAppendVertexGeometry(vtkPolyData *input);
259 // Unfinished option to handle boundary edges differently.
260 void AppendFeatureQuadrics(vtkPolyData *pd);
262 int UseFeaturePoints;
263 int UseInternalTriangles;
265 int NumberOfXDivisions;
266 int NumberOfYDivisions;
267 int NumberOfZDivisions;
270 // can be smaller than user values when input numb er of points is small.
271 int NumberOfDivisions[3];
273 // Since there are two was of specifing the grid, we have this flag
274 // to indicate which the user has set. When this flag is on,
275 // the bin sizes are computed from the DivisionOrigin and DivisionSpacing.
276 int ComputeNumberOfDivisions;
278 float DivisionOrigin[3];
279 float DivisionSpacing[3];
280 int AutoAdjustNumberOfDivisions;
286 vtkIdType SliceSize; //eliminate one multiplication
291 PointQuadric():VertexId(-1),Dimension(255) {}
294 // Dimension is supposed to be a flag representing the dimension of the
295 // cells contributing to the quadric. Lines: 1, Triangles: 2 (and points
297 unsigned char Dimension;
302 PointQuadric* QuadricArray;
303 vtkIdType NumberOfBinsUsed;
305 // Have to make these instance variables if we are going to allow
306 // the algorithm to be driven by the Append methods.
307 vtkCellArray *OutputTriangleArray;
308 vtkCellArray *OutputLines;
310 vtkFeatureEdges *FeatureEdges;
311 vtkPoints *FeaturePoints;
312 float FeaturePointsAngle;
319 vtkQuadricClustering(const vtkQuadricClustering&); // Not implemented.
320 void operator=(const vtkQuadricClustering&); // Not implemented.