This repository has been archived by the owner. It is now read-only.
Benchmark of various spatial data structures for collision detection.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
.gitignore Updating .gitignore. Apr 1, 2015
Base.h Adding source files and Makefile. Nov 7, 2010
BruteForce.cpp cmake unix fix Mar 5, 2018
BruteForce.h Adding source files and Makefile. Nov 7, 2010
CMakeLists.txt Updating CMake to link against freeglut on Windows. Apr 1, 2015
Core.cpp cmake unix fix Mar 5, 2018
HierarchicalGrid.cpp cmake unix fix Mar 5, 2018
HierarchicalGrid.h Adding source files and Makefile. Nov 7, 2010
ISpatialCell.h Adding source files and Makefile. Nov 7, 2010
ISpatialObject.h Adding source files and Makefile. Nov 7, 2010
ISpatialStructure.h
Kdtree.cpp cmake unix fix Mar 5, 2018
Kdtree.h
LICENSE Adding MS-RL license. Nov 7, 2010
LooseOctree.cpp
LooseOctree.h Adding source files and Makefile. Nov 7, 2010
Octree.cpp cmake unix fix Mar 5, 2018
Octree.h
README.md Fixing 7 year old typo in readme. Apr 1, 2015
SortAndSweep.cpp cmake unix fix Mar 5, 2018
SortAndSweep.h Adding source files and Makefile. Nov 7, 2010
SphereObject.cpp cmake unix fix Mar 5, 2018
SphereObject.h Adding source files and Makefile. Nov 7, 2010
UniformGrid.cpp cmake unix fix Mar 5, 2018
UniformGrid.h Adding source files and Makefile. Nov 7, 2010
Vector3.h Adding source files and Makefile. Nov 7, 2010

README.md

Spatial Collision Test Image

This project is a benchmark tool used to assess performance of different collision detection data structures.

Most of these data structures were taken Christer Ericson's Real-Time collision detection (Morgan Kaufmann Publishers 2004) book.

The Kd-Tree SAH idea was taken from Maxim Shevtsov, Alexei Soupikov, Alexander 
Kapustin, Intel
 Corporation, 2007, "Highly Parallel Fast KD‐tree Construction for Interactive Ray Tracing of Dynamic Scenes" paper.

The implemented data structures are:

  • Bruteforce (for reference)
  • Sort and Sweep (Sweep and Prune)
  • Uniform Grid
  • Hierarchical Grid
  • Octree
  • Loose Octree
  • Kd-Tree (using SAH)

A small demo application was written (using GLUT and FF OpenGL) to help visualize and compare the tested data structures.

Please see LICENSE file for License information.
All code is (c) Mykola Konyk, 2008.