1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkVoxelGrid.cxx
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 #include "vtkVoxelGrid.h"
16
17 #include "vtkObjectFactory.h"
18 #include "vtkDoubleArray.h"
19 #include "vtkPointSet.h"
20 #include "vtkPointData.h"
21 #include "vtkPoints.h"
22 #include "vtkStaticPointLocator.h"
23 #include "vtkLinearKernel.h"
24 #include "vtkInformation.h"
25 #include "vtkInformationVector.h"
26 #include "vtkStreamingDemandDrivenPipeline.h"
27 #include "vtkSMPTools.h"
28 #include "vtkSMPThreadLocalObject.h"
29 #include "vtkArrayListTemplate.h" // For processing attribute data
30
31 #include <vector>
32
33
34 vtkStandardNewMacro(vtkVoxelGrid);
35 vtkCxxSetObjectMacro(vtkVoxelGrid,Kernel,vtkInterpolationKernel);
36
37 //----------------------------------------------------------------------------
38 // Helper classes to support efficient computing, and threaded execution.
39 namespace {
40
41 //----------------------------------------------------------------------------
42 // The threaded core of the algorithm (first pass)
43 template <typename T>
44 struct Subsample
45 {
46 T *InPoints;
47 vtkStaticPointLocator *Locator;
48 vtkInterpolationKernel *Kernel;
49 const vtkIdType *BinMap;
50 ArrayList Arrays;
51 T *OutPoints;
52
53 // Don't want to allocate working arrays on every thread invocation. Thread local
54 // storage prevents lots of new/delete.
55 vtkSMPThreadLocalObject<vtkIdList> PIds;
56 vtkSMPThreadLocalObject<vtkDoubleArray> Weights;
57
Subsample__anon083525c40111::Subsample58 Subsample(T* inPts, vtkPointData *inPD, vtkPointData *outPD,
59 vtkStaticPointLocator *loc, vtkInterpolationKernel *k,
60 vtkIdType numOutPts, vtkIdType *binMap, T *outPts) :
61 InPoints(inPts), Locator(loc), Kernel(k), BinMap(binMap), OutPoints(outPts)
62 {
63 this->Arrays.AddArrays(numOutPts, inPD, outPD);
64 }
65
66 // Just allocate a little bit of memory to get started.
Initialize__anon083525c40111::Subsample67 void Initialize()
68 {
69 vtkIdList*& pIds = this->PIds.Local();
70 pIds->Allocate(128); //allocate some memory
71 vtkDoubleArray*& weights = this->Weights.Local();
72 weights->Allocate(128);
73 }
74
operator ()__anon083525c40111::Subsample75 void operator() (vtkIdType pointId, vtkIdType endPointId)
76 {
77 T *px;
78 T *py = this->OutPoints + 3*pointId;
79 const vtkIdType *map = this->BinMap;
80 vtkIdList*& pIds = this->PIds.Local();
81 vtkIdType numWeights;
82 vtkDoubleArray*& weights = this->Weights.Local();
83 double y[3], count;
84 vtkIdType numIds, id;
85 vtkStaticPointLocator *loc = this->Locator;
86
87 for ( ; pointId < endPointId; ++pointId )
88 {
89 vtkIdType binId = map[pointId];
90
91 y[0] = y[1] = y[2] = 0.0;
92 loc->GetBucketIds(binId,pIds);
93 numIds = pIds->GetNumberOfIds();
94 for (id=0; id < numIds; ++id)
95 {
96 px = this->InPoints + 3*pIds->GetId(id);
97 y[0] += *px++;
98 y[1] += *px++;
99 y[2] += *px;
100 }
101 count = static_cast<double>(numIds);
102 y[0] /= count;
103 y[1] /= count;
104 y[2] /= count;
105 *py++ = y[0];
106 *py++ = y[1];
107 *py++ = y[2];
108
109 // Now interpolate attributes
110 numWeights = this->Kernel->ComputeWeights(y, pIds, weights);
111 this->Arrays.Interpolate(numWeights, pIds->GetPointer(0),
112 weights->GetPointer(0), pointId);
113 }//for all output points in this batch
114 }
115
Reduce__anon083525c40111::Subsample116 void Reduce()
117 {
118 }
119
Execute__anon083525c40111::Subsample120 static void Execute(T *inPts, vtkPointData *inPD, vtkPointData *outPD,
121 vtkStaticPointLocator *loc, vtkInterpolationKernel *k,
122 vtkIdType numOutPts, vtkIdType *binMap, T *outPts)
123 {
124 Subsample subsample(inPts, inPD, outPD, loc, k, numOutPts, binMap, outPts);
125 vtkSMPTools::For(0, numOutPts, subsample);
126 }
127
128 }; //Subsample
129
130 } //anonymous namespace
131
132
133 //================= Begin class proper =======================================
134 //----------------------------------------------------------------------------
vtkVoxelGrid()135 vtkVoxelGrid::vtkVoxelGrid()
136 {
137 this->Locator = vtkStaticPointLocator::New();
138 this->ConfigurationStyle = vtkVoxelGrid::AUTOMATIC;
139
140 this->Divisions[0] = this->Divisions[1] = this->Divisions[2] = 50;
141 this->LeafSize[0] = this->LeafSize[1] = this->LeafSize[2] = 1.0;
142 this->NumberOfPointsPerBin = 10;
143
144 this->Kernel = vtkLinearKernel::New();
145 }
146
147 //----------------------------------------------------------------------------
~vtkVoxelGrid()148 vtkVoxelGrid::~vtkVoxelGrid()
149 {
150 this->Locator->UnRegister(this);
151 this->Locator = nullptr;
152 this->SetKernel(nullptr);
153 }
154
155 //----------------------------------------------------------------------------
156 // Produce the output data
RequestData(vtkInformation * vtkNotUsed (request),vtkInformationVector ** inputVector,vtkInformationVector * outputVector)157 int vtkVoxelGrid::RequestData(
158 vtkInformation *vtkNotUsed(request),
159 vtkInformationVector **inputVector,
160 vtkInformationVector *outputVector)
161 {
162 // get the info objects
163 vtkInformation *inInfo = inputVector[0]->GetInformationObject(0);
164 vtkInformation *outInfo = outputVector->GetInformationObject(0);
165
166 // get the input and output
167 vtkPointSet *input = vtkPointSet::SafeDownCast(
168 inInfo->Get(vtkDataObject::DATA_OBJECT()));
169 vtkPolyData *output = vtkPolyData::SafeDownCast(
170 outInfo->Get(vtkDataObject::DATA_OBJECT()));
171
172 // Check the input
173 if ( !input || !output )
174 {
175 return 1;
176 }
177 vtkIdType numPts = input->GetNumberOfPoints();
178 if ( numPts < 1 )
179 {
180 return 1;
181 }
182
183 // Make sure there is a kernel
184 if ( !this->Kernel )
185 {
186 vtkErrorMacro(<<"Interpolation kernel required\n");
187 return 1;
188 }
189
190 bool valid = 1;
191 if ( this->LeafSize[0] <= 0.0 || this->LeafSize[1] <= 0.0 || this->LeafSize[2] <= 0.0 ||
192 this->Divisions[0] < 1 || this->Divisions[1] < 1 || this->Divisions[2] < 1 )
193 {
194 valid = false;
195 }
196
197 // Configure and build the locator
198 if ( valid && this->ConfigurationStyle == vtkVoxelGrid::MANUAL )
199 {
200 this->Locator->AutomaticOff();
201 this->Locator->SetDivisions(this->Divisions);
202 }
203 else if ( valid && this->ConfigurationStyle == vtkVoxelGrid::SPECIFY_LEAF_SIZE )
204 {
205 double bounds[6];
206 int divs[3];
207 this->Locator->AutomaticOff();
208 input->GetBounds(bounds);
209 divs[0] = (bounds[1]-bounds[0]) / this->LeafSize[0];
210 divs[1] = (bounds[3]-bounds[2]) / this->LeafSize[1];
211 divs[2] = (bounds[5]-bounds[4]) / this->LeafSize[2];
212 this->Locator->SetDivisions(divs);
213 }
214 else // this->ConfigurationStyle == vtkVoxelGrid::AUTOMATIC
215 {
216 this->Locator->AutomaticOn();
217 this->Locator->SetNumberOfPointsPerBucket(this->NumberOfPointsPerBin);
218 }
219 this->Locator->SetDataSet(input);
220 this->Locator->BuildLocator();
221 this->Locator->GetDivisions(this->Divisions);
222
223 // Run through the locator and compute the number of output points,
224 // and build a map of the bin number to output point. This is a prefix sum.
225 vtkIdType numOutPts=0;
226 vtkIdType binNum, numBins = this->Locator->GetNumberOfBuckets();
227 std::vector<vtkIdType> binMap;
228 for ( binNum=0; binNum < numBins; ++binNum )
229 {
230 if ( this->Locator->GetNumberOfPointsInBucket(binNum) > 0 )
231 {
232 binMap.push_back(binNum);
233 ++numOutPts;
234 }
235 }
236
237 // Grab the point data for interpolation
238 vtkPointData *inPD = input->GetPointData();
239 vtkPointData *outPD = output->GetPointData();
240 outPD->InterpolateAllocate(inPD,numOutPts);
241
242 // Finally run over all of the bins, and those that are not empty are
243 // processed. The processing consists of averaging all of the points found
244 // in the bin, and setting the average point position in the output points.
245 vtkPoints *points = input->GetPoints()->NewInstance();
246 points->SetDataType(input->GetPoints()->GetDataType());
247 points->SetNumberOfPoints(numOutPts);
248 output->SetPoints(points);
249
250 void *inPtr = input->GetPoints()->GetVoidPointer(0);
251 void *outPtr = output->GetPoints()->GetVoidPointer(0);
252 switch (output->GetPoints()->GetDataType())
253 {
254 vtkTemplateMacro(Subsample<VTK_TT>::Execute((VTK_TT *)inPtr, inPD, outPD,
255 this->Locator, this->Kernel, numOutPts, &binMap[0], (VTK_TT *)outPtr));
256 }
257
258 // Send attributes to output
259 int numPtArrays = input->GetPointData()->GetNumberOfArrays();
260 for (int i=0; i<numPtArrays; ++i)
261 {
262 output->GetPointData()->AddArray(input->GetPointData()->GetArray(i));
263 }
264
265 // Clean up. The locator needs to be reset.
266 this->Locator->Initialize();
267 points->Delete();
268
269 return 1;
270 }
271
272 //----------------------------------------------------------------------------
273 int vtkVoxelGrid::
FillInputPortInformation(int,vtkInformation * info)274 FillInputPortInformation(int, vtkInformation *info)
275 {
276 info->Set(vtkAlgorithm::INPUT_REQUIRED_DATA_TYPE(), "vtkPointSet");
277 return 1;
278 }
279
280 //----------------------------------------------------------------------------
PrintSelf(ostream & os,vtkIndent indent)281 void vtkVoxelGrid::PrintSelf(ostream& os, vtkIndent indent)
282 {
283 this->Superclass::PrintSelf(os,indent);
284
285 os << indent << "Configuration Style: " << this->ConfigurationStyle << endl;
286
287 os << indent << "Divisions: ("
288 << this->Divisions[0] << ","
289 << this->Divisions[1] << ","
290 << this->Divisions[2] << ")\n";
291
292 os << indent << "Leaf Size: ("
293 << this->LeafSize[0] << ","
294 << this->LeafSize[1] << ","
295 << this->LeafSize[2] << ")\n";
296
297 os << indent << "Number of Points Per Bin: "
298 << this->NumberOfPointsPerBin << endl;
299 }
300