1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: TestPointLocators.cxx
5
6 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7 All rights reserved.
8 See Copyright.txt or http://www.kitware.com/Copyright.htm 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 "vtkKdTree.h"
16 #include "vtkKdTreePointLocator.h"
17 #include "vtkMath.h"
18 #include "vtkOctreePointLocator.h"
19 #include "vtkPointLocator.h"
20 #include "vtkPoints.h"
21 #include "vtkPolyData.h"
22 #include "vtkStaticPointLocator.h"
23 #include "vtkTimerLog.h"
24
TimePointLocators(int,char * [])25 int TimePointLocators(int, char*[])
26 {
27 int nPts = 100000;
28 int nQ = nPts / 10;
29 int N = 10;
30 double R = 0.01;
31
32 vtkTimerLog* timer = vtkTimerLog::New();
33 double buildTime[4], cpTime[4], cnpTime[4], crpTime[4];
34 for (int i = 0; i < 4; ++i)
35 {
36 buildTime[i] = cpTime[i] = cnpTime[i] = crpTime[i] = 0.0;
37 }
38
39 cout << "\nTiming for " << nPts << " points, " << nQ << " queries\n";
40
41 // Populate a list of points and query locations
42 vtkPoints* points = vtkPoints::New();
43 points->SetDataTypeToDouble();
44 points->SetNumberOfPoints(nPts);
45 for (int i = 0; i < nPts; ++i)
46 {
47 points->SetPoint(i, vtkMath::Random(-1, 1), vtkMath::Random(-1, 1), vtkMath::Random(-1, 1));
48 }
49
50 vtkPolyData* polydata = vtkPolyData::New();
51 polydata->SetPoints(points);
52 points->ComputeBounds();
53
54 // Create points array which are positions to probe data with FindClosestPoint().
55 vtkPoints* qPoints = vtkPoints::New();
56 qPoints->SetDataTypeToDouble();
57 qPoints->SetNumberOfPoints(nQ);
58 vtkMath::RandomSeed(314159);
59 for (int i = 0; i < nQ; ++i)
60 {
61 qPoints->SetPoint(i, vtkMath::Random(-1, 1), vtkMath::Random(-1, 1), vtkMath::Random(-1, 1));
62 }
63
64 vtkIdList* closest = vtkIdList::New();
65
66 //---------------------------------------------------------------------------
67 // The simple uniform binning point locator
68 vtkPointLocator* uniformLocator = vtkPointLocator::New();
69 timer->StartTimer();
70 uniformLocator->SetDataSet(polydata);
71 uniformLocator->BuildLocator();
72 timer->StopTimer();
73 uniformLocator->Delete();
74 buildTime[0] = timer->GetElapsedTime();
75
76 uniformLocator = vtkPointLocator::New();
77 uniformLocator->SetDataSet(polydata);
78 uniformLocator->BuildLocator();
79 timer->StartTimer();
80 for (int i = 0; i < nQ; ++i)
81 {
82 uniformLocator->FindClosestPoint(qPoints->GetPoint(i));
83 }
84 timer->StopTimer();
85 cpTime[0] = timer->GetElapsedTime();
86
87 timer->StartTimer();
88 for (int i = 0; i < nQ; ++i)
89 {
90 uniformLocator->FindClosestNPoints(N, qPoints->GetPoint(i), closest);
91 }
92 timer->StopTimer();
93 cnpTime[0] = timer->GetElapsedTime();
94
95 timer->StartTimer();
96 for (int i = 0; i < nQ; ++i)
97 {
98 uniformLocator->FindPointsWithinRadius(R, qPoints->GetPoint(i), closest);
99 }
100 timer->StopTimer();
101 crpTime[0] = timer->GetElapsedTime();
102 uniformLocator->Delete();
103
104 //---------------------------------------------------------------------------
105 // The simple uniform binning point locator, this time built
106 // statically and threaded (may be much faster on threaded machine).
107 vtkStaticPointLocator* staticLocator = vtkStaticPointLocator::New();
108 timer->StartTimer();
109 staticLocator->SetDataSet(polydata);
110 staticLocator->BuildLocator();
111 timer->StopTimer();
112 staticLocator->Delete();
113 buildTime[1] = timer->GetElapsedTime();
114
115 staticLocator = vtkStaticPointLocator::New();
116 staticLocator->SetDataSet(polydata);
117 staticLocator->BuildLocator();
118 timer->StartTimer();
119 for (int i = 0; i < nQ; ++i)
120 {
121 staticLocator->FindClosestPoint(qPoints->GetPoint(i));
122 }
123 timer->StopTimer();
124 cpTime[1] = timer->GetElapsedTime();
125
126 timer->StartTimer();
127 for (int i = 0; i < nQ; ++i)
128 {
129 staticLocator->FindClosestNPoints(N, qPoints->GetPoint(i), closest);
130 }
131 timer->StopTimer();
132 cnpTime[1] = timer->GetElapsedTime();
133
134 timer->StartTimer();
135 for (int i = 0; i < nQ; ++i)
136 {
137 staticLocator->FindPointsWithinRadius(R, qPoints->GetPoint(i), closest);
138 }
139 timer->StopTimer();
140 crpTime[1] = timer->GetElapsedTime();
141 staticLocator->Delete();
142
143 //---------------------------------------------------------------------------
144 // The KD Tree point locator
145 vtkKdTreePointLocator* kdTreeLocator = vtkKdTreePointLocator::New();
146 timer->StartTimer();
147 kdTreeLocator->SetDataSet(polydata);
148 kdTreeLocator->BuildLocator();
149 kdTreeLocator->Delete();
150 timer->StopTimer();
151 buildTime[2] = timer->GetElapsedTime();
152
153 kdTreeLocator = vtkKdTreePointLocator::New();
154 kdTreeLocator->SetDataSet(polydata);
155 kdTreeLocator->BuildLocator();
156 timer->StartTimer();
157 for (int i = 0; i < nQ; ++i)
158 {
159 kdTreeLocator->FindClosestPoint(qPoints->GetPoint(i));
160 }
161 timer->StopTimer();
162 cpTime[2] = timer->GetElapsedTime();
163
164 timer->StartTimer();
165 for (int i = 0; i < nQ; ++i)
166 {
167 kdTreeLocator->FindClosestNPoints(N, qPoints->GetPoint(i), closest);
168 }
169 timer->StopTimer();
170 cnpTime[2] = timer->GetElapsedTime();
171
172 timer->StartTimer();
173 for (int i = 0; i < nQ; ++i)
174 {
175 kdTreeLocator->FindPointsWithinRadius(R, qPoints->GetPoint(i), closest);
176 }
177 timer->StopTimer();
178 crpTime[2] = timer->GetElapsedTime();
179 kdTreeLocator->Delete();
180
181 //---------------------------------------------------------------------------
182 // Octree point locator
183 vtkOctreePointLocator* octreeLocator = vtkOctreePointLocator::New();
184 timer->StartTimer();
185 octreeLocator->SetDataSet(polydata);
186 octreeLocator->BuildLocator();
187 octreeLocator->Delete();
188 timer->StopTimer();
189 buildTime[3] = timer->GetElapsedTime();
190
191 octreeLocator = vtkOctreePointLocator::New();
192 octreeLocator->SetDataSet(polydata);
193 octreeLocator->BuildLocator();
194 timer->StartTimer();
195 for (int i = 0; i < nQ; ++i)
196 {
197 octreeLocator->FindClosestPoint(qPoints->GetPoint(i));
198 }
199 timer->StopTimer();
200 cpTime[3] = timer->GetElapsedTime();
201
202 timer->StartTimer();
203 for (int i = 0; i < nQ; ++i)
204 {
205 octreeLocator->FindClosestNPoints(N, qPoints->GetPoint(i), closest);
206 }
207 timer->StopTimer();
208 cnpTime[3] = timer->GetElapsedTime();
209
210 timer->StartTimer();
211 for (int i = 0; i < nQ; ++i)
212 {
213 octreeLocator->FindPointsWithinRadius(R, qPoints->GetPoint(i), closest);
214 }
215 timer->StopTimer();
216 crpTime[3] = timer->GetElapsedTime();
217 octreeLocator->Delete();
218
219 //---------------------------------------------------------------------------
220 // Print out the statistics
221 cout << "Build and delete tree\n";
222 cout << "\tUniform: " << buildTime[0] << "\n";
223 cout << "\tStatic: " << buildTime[1] << "\n";
224 cout << "\tOctree: " << buildTime[2] << "\n";
225 cout << "\tKD Tree: " << buildTime[3] << "\n";
226
227 cout << "Closest point queries\n";
228 cout << "\tUniform: " << cpTime[0] << "\n";
229 cout << "\tStatic: " << cpTime[1] << "\n";
230 cout << "\tOctree: " << cpTime[2] << "\n";
231 cout << "\tKD Tree: " << cpTime[3] << "\n";
232
233 cout << "Closest N points queries\n";
234 cout << "\tUniform: " << cnpTime[0] << "\n";
235 cout << "\tStatic: " << cnpTime[1] << "\n";
236 cout << "\tOctree: " << cnpTime[2] << "\n";
237 cout << "\tKD Tree: " << cnpTime[3] << "\n";
238
239 cout << "Closest points within radius queries\n";
240 cout << "\tUniform: " << crpTime[0] << "\n";
241 cout << "\tStatic: " << crpTime[1] << "\n";
242 cout << "\tOctree: " << crpTime[2] << "\n";
243 cout << "\tKD Tree: " << crpTime[3] << "\n";
244
245 cout << "Total time\n";
246 cout << "\tUniform: " << (buildTime[0] + cpTime[0] + cnpTime[0] + crpTime[0]) << "\n";
247 cout << "\tStatic: " << (buildTime[1] + cpTime[1] + cnpTime[1] + crpTime[1]) << "\n";
248 cout << "\tOctree: " << (buildTime[2] + cpTime[2] + cnpTime[2] + crpTime[2]) << "\n";
249 cout << "\tKD Tree: " << (buildTime[3] + cpTime[3] + cnpTime[3] + crpTime[3]) << "\n";
250
251 timer->Delete();
252 points->Delete();
253 qPoints->Delete();
254 polydata->Delete();
255 closest->Delete();
256
257 // Always return success, although the test infrastructure should catch
258 // excessive execution times.
259 return 0;
260 }
261