Login
Thread-Safe Spatial Subdivision
By: Erik Sunderland
Supervisor: Gary Brubaker
Masters of Interactive Technology degree conferred December 15, 2008
Thesis / Project completed: February 1, 2009
The current generation of console hardware contains very powerful processor architectures. However, to utilize this to its maximum potential, the game development industry needs to be familiar with concurrency and threading concepts. This new paradigm of programming requires that engineers understand more about what the hardware is doing and how they can design systems that use multiple threads to process work simultaneously.At the heart of many systems are containers that house the data usesd by the system. Linked-lists, quadtrees, octrees, and BSP trees are some of the containers that are looked at. All of these containers have unique ways to store spatial data and each have their benefits depending on whether the data is points or bounding boxes, static or dynamic, or even multi-dimensional going beyond two and three dimensions of games today.
The project was initially to discover a way to create a thread-safe quadtree that does not just restrict access to the entire tree with a mutex. After many attempts to create a very fine-grained tree, the problem was re-assessed and a spatial grid was created. The constant changing of data in the simulation caused unique problems for the dynamic quadtree approach and required that the data contention of this tree be removed to solve the problem at hand.
The final implementation held up fairly well against testing. Testing showed that as the number of cores increased, the overall time to update a given number of units dropped. This shows that the container and the simulation were utilizing the additional cores and is the kind of utilization the industry needs to do with current systems on today’s hardware.
The project overall was very ambitious and taught me a lot about concurrency and design. Even though the quadtree attempt was not successful, I think that it taught me a great deal about atomic functions, design decisions in a concurrent system, and gave me an example of how to think about a solution when any thread can interrupt and change what another thread is about to do.
Print This Page