1 /*========================================================================= 2 3 Program: Visualization Toolkit 4 Module: vtkHierarchicalBinningFilter.h 5 6 Copyright (c) Kitware, Inc. 7 All rights reserved. 8 See LICENSE file for details. 9 10 This software is distributed WITHOUT ANY WARRANTY; without even 11 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 12 PURPOSE. See the above copyright notice for more information. 13 14 =========================================================================*/ 15 /** 16 * @class vtkHierarchicalBinningFilter 17 * @brief uniform binning of points into 18 * a hierarchical structure 19 * 20 * 21 * vtkHierarchicalBinningFilter creates a spatial, hierarchical ordering of 22 * input points. This hierarchy is suitable for level-of-detail rendering, or 23 * multiresolution processing. Each level of the hierarchy is based on 24 * uniform binning of space, where deeper levels (and its bins) are 25 * repeatedly subdivided by a given branching factor. Points are associated 26 * with bins at different levels, with the number of points in each level 27 * proportional to the number of bins in that level. The output points are 28 * sorted according to a bin number, where the bin number is unique, 29 * monotonically increasing number representing the breadth first ordering of 30 * all of the levels and their bins. Thus all points in a bin (or even a level) 31 * are segmented into contiguous runs. 32 * 33 * Note that points are associated with different bins using a pseudo random 34 * process. No points are repeated, and no new points are created, thus the 35 * effect of executing this filter is simply to reorder the input points. 36 * 37 * The algorithm proceeds as follows: Given an initial bounding box, the 38 * space is uniformally subdivided into bins of (M x N x O) dimensions; in 39 * turn each subsequent level in the tree is further divided into (M x N x O) 40 * bins (note that level 0 is a single, root bin). Thus the number of bins at 41 * level L of the hierarchical tree is: Nbins=(M^L x N^L x O^L). Once the 42 * binning is created to a specified depth, then points are placed in the 43 * bins using a pseudo-random sampling proportional to the number of bins in each 44 * level. All input points are sorted in the order described above, with no 45 * points repeated. 46 * 47 * The output of this filter are sorted points and associated point 48 * attributes represented by a vtkPolyData. In addition, an offset integral 49 * array is associated with the field data of the output, providing offsets 50 * into the points list via a breadth-first traversal order. Metadata 51 * describing the output is provided in the field data. Convenience functions 52 * are also provided here to access the data in a particular bin or across a 53 * level. (Using the offset array directly may result in higher performance.) 54 * 55 * While any vtkPointSet type can be provided as input, the output is 56 * represented by an explicit representation of points via a 57 * vtkPolyData. This output polydata will populate its instance of vtkPoints, 58 * but no cells will be defined (i.e., no vtkVertex or vtkPolyVertex are 59 * contained in the output). 60 * 61 * @warning 62 * This class has been threaded with vtkSMPTools. Using TBB or other 63 * non-sequential type (set in the CMake variable 64 * VTK_SMP_IMPLEMENTATION_TYPE) may improve performance significantly. 65 * 66 * @sa 67 * vtkPointCloudFilter vtkQuadricClustering vtkStaticPointLocator 68 */ 69 70 #ifndef vtkHierarchicalBinningFilter_h 71 #define vtkHierarchicalBinningFilter_h 72 73 #include "vtkFiltersPointsModule.h" // For export macro 74 #include "vtkPolyDataAlgorithm.h" 75 76 #define VTK_MAX_LEVEL 12 77 78 struct vtkBinTree; 79 80 class VTKFILTERSPOINTS_EXPORT vtkHierarchicalBinningFilter : public vtkPolyDataAlgorithm 81 { 82 public: 83 //@{ 84 /** 85 * Standard methods for instantiating, obtaining type information, and 86 * printing information. 87 */ 88 static vtkHierarchicalBinningFilter *New(); 89 vtkTypeMacro(vtkHierarchicalBinningFilter,vtkPolyDataAlgorithm); 90 void PrintSelf(ostream& os, vtkIndent indent) override; 91 //@} 92 93 //@{ 94 /** 95 * Specify the number of levels in the spatial hierarchy. By default, the 96 * number of levels is three. 97 */ 98 vtkSetClampMacro(NumberOfLevels,int,1,VTK_MAX_LEVEL); 99 vtkGetMacro(NumberOfLevels,int); 100 //@} 101 102 //@{ 103 /** 104 * Specify whether to determine the determine the level divisions, and the bounding 105 * box automatically (by default this is on). If off, then the user must specify both 106 * the bounding box and bin divisions. (Computing the bounding box can be slow for 107 * large point clouds, manual specification can save time.) 108 */ 109 vtkSetMacro(Automatic,bool); 110 vtkGetMacro(Automatic,bool); 111 vtkBooleanMacro(Automatic,bool); 112 //@} 113 114 //@{ 115 /** 116 * Set the number of branching divisions in each binning direction. Each 117 * level of the tree is subdivided by this factor. The Divisions[i] must be 118 * >= 1. Note: if Automatic subdivision is specified, the Divisions are 119 * set by the filter. 120 */ 121 vtkSetVector3Macro(Divisions,int); 122 vtkGetVectorMacro(Divisions,int,3); 123 //@} 124 125 //@{ 126 /** 127 * Set the bounding box of the point cloud. If Automatic is enabled, then 128 * this is computed during filter execution. If manually specified 129 * (Automatic is off) then make sure the bounds is represented as 130 * (xmin,xmax, ymin,ymax, zmin,zmax). If the bounds specified is does not 131 * enclose the points, then points are clamped to lie in the bounding box. 132 */ 133 vtkSetVector6Macro(Bounds,double); 134 vtkGetVectorMacro(Bounds,double,6); 135 //@} 136 137 /** 138 * Convenience methods for extracting useful information about this bin 139 * tree. Return the number of total bins across all levels (i.e., the 140 * total global bins). Invoke this method after the bin tree has been 141 * built. 142 */ 143 int GetNumberOfGlobalBins(); 144 145 /** 146 * Convenience methods for extracting useful information about this bin 147 * tree. Return the number of bins in a particular level of the 148 * tree. Invoke this method after the bin tree has been built. 149 */ 150 int GetNumberOfBins(int level); 151 152 /** 153 * Convenience methods for extracting useful information about this bin 154 * tree. Given a level, return the beginning point id and number of points 155 * that level. Invoke this method after the bin tree has been built. 156 */ 157 vtkIdType GetLevelOffset(int level, vtkIdType& npts); 158 159 /** 160 * Convenience methods for extracting useful information about this bin 161 * tree. Given a global bin number, return the point id and number of 162 * points for that bin. Invoke this method after the bin tree has been 163 * built. 164 */ 165 vtkIdType GetBinOffset(int globalBin, vtkIdType& npts); 166 167 /** 168 * Convenience methods for extracting useful information about this bin 169 * tree. Given a level, and the bin number in that level, return the 170 * offset point id and number of points for that bin. Invoke this method 171 * after the bin tree has been built. 172 */ 173 vtkIdType GetLocalBinOffset(int level, int localBin, vtkIdType& npts); 174 175 /** 176 * Convenience methods for extracting useful information about a bin tree. 177 * Given a global bin number, return the bounds (xmin,xmax,ymin,ymax,zmin,zmax) 178 * for that bin. Invoke this method after the bin tree has been built. 179 */ 180 void GetBinBounds(int globalBin, double bounds[6]); 181 182 /** 183 * Convenience methods for extracting useful information about a bin tree. 184 * Given a level, and a local bin number, return the bounds 185 * (xmin,xmax,ymin,ymax,zmin,zmax) for that bin. Invoke this method after 186 * the bin tree has been built. 187 */ 188 void GetLocalBinBounds(int level, int localBin, double bounds[6]); 189 190 protected: 191 vtkHierarchicalBinningFilter(); 192 ~vtkHierarchicalBinningFilter() override; 193 194 // IVars 195 int NumberOfLevels; 196 bool Automatic; 197 int Divisions[3]; 198 double Bounds[6]; 199 200 // Handle to the underlying implementation. The representation is maintained so 201 // that the convenience functions can be invoked on the bin tree. 202 vtkBinTree *Tree; 203 204 int RequestData(vtkInformation *, vtkInformationVector **, 205 vtkInformationVector *) override; 206 int FillInputPortInformation(int port, vtkInformation *info) override; 207 208 private: 209 vtkHierarchicalBinningFilter(const vtkHierarchicalBinningFilter&) = delete; 210 void operator=(const vtkHierarchicalBinningFilter&) = delete; 211 212 }; 213 214 #endif 215