Spatial Data Structures Simulation Program

This program runs simulations of real-time 3D scenes with varying numbers of static and dynamic objects in order to measure the performance of different spatial data structures. It currently includes implementations of octrees and BSP trees. It was designed to allow additional data structures to be easily implemented.

This is a Mac OS X application written in Swift. It uses OpenGL for graphics rendering.

This application was developed by Josh Beam and is distributed under the BSD-style license shown at the bottom of this file.

References

The following resources were utilized while developing this application:

1. S. Shekhar and S. Chawla, Spatial Databases: A Tour, 1st ed. Prentice Hall, 2003, ch. 1.
2. T. Akenine-Möller and E. Haines, Real-Time Rendering, 2nd ed. Wellesley, MA: A K Peters, 2002, ch. 9, pp. 345-355.
3. A. Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching,” ACM SIGMOD, vol. 14, no. 2, pp. 47-57, Jun. 1984.
4. J. T. Klosowski et al., “Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs,” IEEE Transactions on Visualization and Computer Graphics, vol. 4, no. 1, pp. 21-36, Jan.-Mar. 1998.
5. Z. Tang, “Octree Representation and Its Applications in CAD,” Journal of Computer Science & Technology, vol. 7, no. 1, pp. 29-38, 1992.
6. M. S. Paterson and F. F. Yao, “Binary Partitions with Applications to Hidden-Surface Removal and Solid Modelling,” ACM Proceedings of the fifth annual symposium on Computational geometry, pp. 23-32, 1989.
7. J. L. Bentley, “Multidimensional Divide-and-Conquer,” Communications of the ACM, vol. 23, no. 4, pp. 214-229, Apr. 1980.
8. K. Zhou et al., “Real-Time KD-Tree Construction on Graphics Hardware,” ACM Transactions on Graphics, vol. 27, no. 5, Dec. 2008.

License

Copyright (C) 2016 Josh A. Beam
All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.