SODA CD: A Model for Scalability-Oriented, Distributed and Anticipative Collision Detection
Résumé
In this master's thesis, we first analyze existing parallel algorithms for the problem of collision detection in virtual reality applications, as well as larger scale parallel algorithms taken from the particle simulation research field. Based on the properties we noticed to favour high scalability in these algorithms, we propose a novel approach to parallel collision detection. In order to allow the execution of interactive applications on systems made of tens of processors with an efficient solution, our parallel collision detection framework is designed to be decentralized and to exploit all available computing resources. More precisely, we improve the potential for scalability of virtual simulations primarily by loosening the synchronism constraints between processing units, moving from the current synchronize after each detection and constraint solving round scheme to several autonomous worlds that process a part of the application's simulation space at their own rhythm and synchronize with each other when an object moves from one to another. Our second contribution is a new rollback algorithm for speculative computing, that allows partial saving of the anticipated computations that get invalidated because of synchronization mechanisms. Both of these proposals are making use of a spatial subdivision uniform grid. Each processing unit is assigned a territory made of contiguous cells from this grid, and simulates the objects within this territory. The rollback algorithm makes use of the grid by integrating rollbacks cell by cell, thus saving some independant computations whenever not all cells are interconnected as a result of objects coexisting in adjacent cells. Processing units can work autonomously, using their own local clock and communicating exclusively with their direct neighbors in the grid, and making the results of their computations available via a circular buffer. This buffer is read by a rendering thread that allows users to visualize with the simulation. User input is also taken into account in the model, permitting the execution of interactive applications. We also introduce theoretical leads for load balancing in our new framework, for continuous and discrete algorithms. The proposed load balancing mechanism is distributed and does not involve global communication, in order not to hinder the scalability of the framework. It is based on the exchange of spatial subdivision grid cells that compose the area managed by each processing unit. Finally, we discuss preliminary experimentations performed with our implementation of the frame-work, despite the implementation not being complete enough to allow deterministic simulations yet. We also discuss limitations of our framework and directions for future work.
Loading...