M.Sc Student | Tropp Oren |
---|---|

Subject | Temporal Coherence in Collision Detection for Bounding Volume Hierarchies |

Department | Department of Electrical Engineering |

Supervisors | Professor Ayellet Tal |

Professor Ilan Shimshoni | |

Full Thesis text |

Collision detection is a fundamental problem in computer graphics, as well as in computational geometry, solid modeling, robotics and molecular modeling. For most of these applications, real-time performance is required. Dynamic scenarios are those in which multiple collision queries (frames) describe a physical movement of an object in space.

The basic premise of this work is that in a dynamic
environment, collision queries are typically similar and therefore dependant on
queries made in previous frames. This *temporal coherence* implies that
information from past collision queries can be used to accelerate future
queries.

We present a framework for using temporal coherence within bounding
volume hierarchies. First, we note that many of the tests performed in the
previous frame will also be performed in the next. This allows us to start from
a middle point (a *front*) of the previous query rather than from scratch.
We explore and analyze different strategies for determining and maintaining an
optimal front. Second, we note that some of the information acquired in the
previous frame can be stored to speed up a similar collision test in the
future.

We present an implementation for the popular OBB and AABB data structures and show an improvement of up to 70% in query time using temporal coherence, compared to the original version of the algorithm. When temporal coherence is absent, it is identified by the algorithm and a non-coherence version is called. This allows for stable performance for a variety of movement types.

We proceed to discuss the triangle-triangle intersection test, which is performed at the leaves of any collision detection data structure. We present a fast method for finding whether two triangles embedded in three dimensions intersect. While previous work has focused on geometrical solutions, we propose an algebraic approach. Our technique solves the basic linear equations sets associated with the problem and exploits the strong relations between these sets to accelerate their solution. Moreover, unlike previous techniques, with minimal additional cost, the exact intersection coordinates can be determined. Finally, our technique uses general principles that can be applied to any problem where several equations are strongly related, such as a rectangle-rectangle intersection test. We show that our algorithm saves about 20% of the mathematical operations used by the best previous triangle-to-triangle intersection algorithm. Our experiments also show that it runs 18.9% faster than the fastest previous algorithm on average for typical scenarios of collision detection.