Proximity queries with applications in computational surgery and manipulation planning
Mika Gissler · FreiDok plus (Universitätsbibliothek Freiburg) · 2011
The goal of proximity queries is to get information on the relative spatial configuration of objects. Depending on the query type, different information is returned. For example, a collision query returns whether pairs of objects overlap in space whereas a distance query might return the Euclidean distance between them. The proximity queries find application in computer-aided design and manufacturing, virtual environments, computer graphics, robotics, and computer-simulated environments. Queries for distance verification are employed in robotics and manipulation planning to search for collision-free and safe paths through the environment, whereas queries for collision detection are employed in the contact-handling approaches of simulation environments to prevent the interpenetration of solid objects. In this thesis, proximity queries are discussed in the context of computer-simulated environments. Three main aspects are addressed, notably collision or contact handling, distance computation among deformable objects and the application of proposed techniques in the areas of computational surgery and path planning. First, a framework for the physically-based animation of deformable objects is described. The description includes a summary of the collision and contact-handling methods that have already been implemented in the framework. Furthermore, contributions to the framework in the form of various types of constraints are put forward. The contact handling is the most time-critical task in the simulation loop and its computation time can vary dramatically depending on the spatial configuration of the objects in the simulation environment. Therefore, a time-critical contact handling approach is presented that assures a user-defined time constraint by trading accuracy for performance when needed. The efficiency can be further improved by carefully selecting appropriate spatial data structures depending on the application. Therefore, various spatial data structures are investigated and their application to computational-surgery scenarios is evaluated. The framework is employed as part of a geometric planner to answer various proximity queries to find collision-free or motion paths or paths that maintain a safety distance to obstacles. Thus, algorithms for distance verification are needed. An efficient distance computation algorithm is proposed that is particularly suitable for deformable objects. The most efficient proximity algorithms assume the objects to be a composition of convex parts and decompose its surface into convex patches if the objects are concave. For non-rigid objects, the decomposition might only be valid until the next simulation step. Thus, the surface is adaptively decomposed with respect to the specific query. The findings regarding the contact handling and distance computation are employed in various application scenarios. First, their application to a framework for computational surgery is described before their application in the geometric planner of a manipulation planning system is investigated.