טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentOren Tropp
SubjectTemporal Coherence in Collision Detection for Bounding
Volume Hierarchies
DepartmentDepartment of Electrical Engineering
Supervisors Full Professor Tal Ayellet
Full Professor Shimshoni Ilan
Full Thesis textFull thesis text - English Version


Abstract

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.