Skip to content

Latest commit

 

History

History
76 lines (65 loc) · 2.92 KB

README.md

File metadata and controls

76 lines (65 loc) · 2.92 KB
Raw

Binary Space Partitioning (BSP)

Recursively divides the space into two parts until the leaf nodes satisfy the constraints such as minimum number of spatial objects in a partition.

  • BSP tree is a heirarchical subdivisions of n dimensional space into convex subspaces. The space is subdivided using hyperplanes passing through node.
  • Kd-trees and quad-trees have hyperplanes aligned with the coordinate axis while BSP tree has hyperplanes with any orientation.

How to run Binary Space Partitioning algorithm

  • You can change the parition parameters in extract_params_partitioning method of partition_params.hpp.
  • Paramters are volume of space (min_x, min_y, min_z, max_x, max_y, max_z) and bucket_size. You choose the volume of space based on the input spatial objects so that all the spatial objects are covered.
  • In the code, space volume is hard-coded as 0,0,0,50,50,50 for testObj.mbb as input and bucket_size as 4.
g++ -std=c++0x bsp_3d.cpp -o bsp
./bsp testObj.mbb

Sort Tile Recursive Partitioning (STR)

Sort Tile Recursive Partitioning : Partitioning using RTree from libSpatialIndex.

Hello World of libSpatialIndex C++ library

https://github.com/libspatialindex/libspatialindex/wiki/1.-Getting-Started

g++ -std=c++0x helloLibSpatial.cpp -lspatialindex_c -lspatialindex -o helloLibSpatial
./helloLibSpatial

How to run Sort Tile Partitioning algorithm

g++ -std=c++0x str_3d.cpp -lspatialindex_c -lspatialindex -o str
./str testObj.mbb

Visualizations with OpenGL (trials)

Hello World of OpenGL C++ library with installation instructions

http://www.linuxjournal.com/content/introduction-opengl-programming

  • Installation
apt-cache search opengl
sudo apt-get install freeglut3 freeglut3-dev libglew-dev
sudo apt-get install mesa-utils
  • Check your OpenGL installation
glxinfo | grep OpenGL
  • Draw Triangle and Circle as a HelloWorld program.
    • Opens Triangle and Circle in two openGL windows.
g++ openGLHelloWorld.cpp -lglut -lGL -o hello
./hello
  • Draw Rotated Cube using OpenGL.
g++ openGLCube.cpp -lglut -lGL -lGLU -o cube
./cube

Visualizations in Matlab

After trying several things in OpenGL, I found stackoverflow links directing to Matlab. The APIs were simpler and easy to implement. So, I implemented the partitioning algorithm visualizations in Matlab and not in OpenGL.

Run simplecube.m

The visualizations are for both BSP and STR partitioning algorithms.

  1. BSP
    Input for BSP visualization is

    • testObj.dat containing spatial MBBs
    • boundingBoxBSP.dat has output partitioned MBBs. Output is a bounding box visualization. Check project report or bsp.png for the visualization.

  2. STR
    Input for STR visualization is

    • testObj.dat containing spatial MBBs
    • boundingBoxSTR.dat has output partitioned MBBs. Output is a bounding box visualization. Check project report or str.png for the visualization.