KDTreeTimingDemo
vtk-examples/Cxx/DataStructures/KDTreeTimingDemo
Question
If you have a question about this example, please use the VTK Discourse Forum
Code¶
KDTreeTimingDemo.cxx
#include <vtkAxis.h>
#include <vtkChartXY.h>
#include <vtkContextScene.h>
#include <vtkContextView.h>
#include <vtkFloatArray.h>
#include <vtkIdList.h>
#include <vtkKdTreePointLocator.h>
#include <vtkMath.h>
#include <vtkNamedColors.h>
#include <vtkNew.h>
#include <vtkPlot.h>
#include <vtkPoints.h>
#include <vtkPolyData.h>
#include <vtkRenderWindow.h>
#include <vtkRenderWindowInteractor.h>
#include <vtkRenderer.h>
#include <vtkSphereSource.h>
#include <vtkTable.h>
#include <vtkTimerLog.h>
#include <vtkXMLPolyDataReader.h>
#include <time.h>
#include <vector>
namespace {
void RandomPointInBounds(vtkPolyData* polydata, double p[3]);
double TimeKDTree(vtkPolyData* polydata, int maxPoints, int numberOfTrials);
} // namespace
int main(int, char*[])
{
vtkNew<vtkNamedColors> colors;
vtkNew<vtkSphereSource> reader;
reader->SetThetaResolution(30);
reader->SetPhiResolution(30);
reader->Update();
std::cout << "Timing octree..." << std::endl;
std::vector<std::pair<int, double>> results;
int numberOfTrials = 1000;
for (int i = 1; i < 20; i++)
{
double t = TimeKDTree(reader->GetOutput(), i, numberOfTrials);
std::pair<int, double> result(i, t);
results.push_back(result);
}
// Create a table with some points in it
vtkNew<vtkTable> table;
vtkNew<vtkFloatArray> maxPointsPerRegion;
maxPointsPerRegion->SetName("MaxPointsPerRegion");
table->AddColumn(maxPointsPerRegion);
vtkNew<vtkFloatArray> runtime;
runtime->SetName("Run time");
table->AddColumn(runtime);
// Fill in the table with some example values
size_t numPoints = results.size();
table->SetNumberOfRows(static_cast<vtkIdType>(numPoints));
for (size_t i = 0; i < numPoints; ++i)
{
table->SetValue(static_cast<vtkIdType>(i), 0, results[i].first);
table->SetValue(static_cast<vtkIdType>(i), 1, results[i].second);
std::cout << "Put " << results[i].first << " " << results[i].second
<< " in the table." << std::endl;
}
// Set up the view
vtkNew<vtkContextView> view;
view->GetRenderer()->SetBackground(colors->GetColor3d("White").GetData());
view->GetRenderWindow()->SetWindowName("KDTreeTimingDemo");
// Add multiple line plots, setting the colors etc
vtkNew<vtkChartXY> chart;
view->GetScene()->AddItem(chart);
vtkPlot* line = chart->AddPlot(vtkChart::LINE);
line->SetInputData(table, 0, 1);
auto lineColor = colors->HTMLColorToRGBA("Lime").GetData();
line->SetColor(lineColor[0], lineColor[1], lineColor[2], lineColor[3]);
line->SetWidth(3.0);
line->GetXAxis()->SetTitle("Max Points Per Region");
line->GetYAxis()->SetTitle("Run time");
view->GetRenderWindow()->SetMultiSamples(0);
view->GetRenderWindow()->Render();
// Start interactor
view->GetInteractor()->Initialize();
view->GetInteractor()->Start();
return EXIT_SUCCESS;
}
namespace {
void RandomPointInBounds(vtkPolyData* polydata, double p[3])
{
double bounds[6];
polydata->GetBounds(bounds);
double x = bounds[0] + (bounds[1] - bounds[0]) * vtkMath::Random(0.0, 1.0);
double y = bounds[2] + (bounds[3] - bounds[2]) * vtkMath::Random(0.0, 1.0);
double z = bounds[4] + (bounds[5] - bounds[4]) * vtkMath::Random(0.0, 1.0);
p[0] = x;
p[1] = y;
p[2] = z;
}
double TimeKDTree(vtkPolyData* polydata, int maxLevel, int numberOfTrials)
{
vtkNew<vtkTimerLog> timer;
timer->StartTimer();
vtkMath::RandomSeed(
0); // this should be changed to time(NULL) to get random behavior
// Create the tree
vtkNew<vtkKdTreePointLocator> kdtree;
kdtree->SetDataSet(polydata);
kdtree->AutomaticOff();
kdtree->SetMaxLevel(maxLevel);
kdtree->BuildLocator();
// std::cout << "With maxLevel = " << maxLevel << " there are " <<
// kdtree->GetNumberOfLeafNodes() << " leaf nodes." << std::endl;
for (int i = 0; i < numberOfTrials; i++)
{
double p[3];
RandomPointInBounds(polydata, p);
kdtree->FindClosestPoint(p);
}
timer->StopTimer();
std::cout << "KDTree took " << timer->GetElapsedTime() << std::endl;
return timer->GetElapsedTime();
}
} // namespace
CMakeLists.txt¶
cmake_minimum_required(VERSION 3.3 FATAL_ERROR)
project(KDTreeTimingDemo)
find_package(VTK COMPONENTS
vtkChartsCore
vtkCommonColor
vtkCommonCore
vtkCommonDataModel
vtkCommonSystem
vtkFiltersSources
vtkIOXML
vtkInteractionStyle
vtkRenderingContext2D
vtkRenderingContextOpenGL2
vtkRenderingCore
vtkRenderingFreeType
vtkRenderingGL2PSOpenGL2
vtkRenderingOpenGL2
vtkViewsContext2D
QUIET
)
if (NOT VTK_FOUND)
message("Skipping KDTreeTimingDemo: ${VTK_NOT_FOUND_MESSAGE}")
return ()
endif()
message (STATUS "VTK_VERSION: ${VTK_VERSION}")
if (VTK_VERSION VERSION_LESS "8.90.0")
# old system
include(${VTK_USE_FILE})
add_executable(KDTreeTimingDemo MACOSX_BUNDLE KDTreeTimingDemo.cxx )
target_link_libraries(KDTreeTimingDemo PRIVATE ${VTK_LIBRARIES})
else ()
# include all components
add_executable(KDTreeTimingDemo MACOSX_BUNDLE KDTreeTimingDemo.cxx )
target_link_libraries(KDTreeTimingDemo PRIVATE ${VTK_LIBRARIES})
# vtk_module_autoinit is needed
vtk_module_autoinit(
TARGETS KDTreeTimingDemo
MODULES ${VTK_LIBRARIES}
)
endif ()
Download and Build KDTreeTimingDemo¶
Click here to download KDTreeTimingDemo and its CMakeLists.txt file. Once the tarball KDTreeTimingDemo.tar has been downloaded and extracted,
cd KDTreeTimingDemo/build
If VTK is installed:
cmake ..
If VTK is not installed but compiled on your system, you will need to specify the path to your VTK build:
cmake -DVTK_DIR:PATH=/home/me/vtk_build ..
Build the project:
make
and run it:
./KDTreeTimingDemo
WINDOWS USERS
Be sure to add the VTK bin directory to your path. This will resolve the VTK dll's at run time.