Interacción háptica en tiempo real con modelos gráficos de alta resolución

Zusammenfassung

Abstract Nowadays, computer graphics technologies have become widespread in many disciplines, such as medicine, video games, haptic devices, filmmaking, design and manufacture of objects, planning of routes for mobility, etc. Mainly highlight, the development of augmented reality, virtual reality and haptic technology. For all these technologies, new devices that allow interaction within real or virtual scenarios appear daily, making it necessary to work with geometric models that are increasingly larger and more complex Currently the 3D scanners for the capture of geometric models have greatly reduced prices and have greatly increased their performance, allowing to obtain geometric models in three dimensions with high resolution, thus collecting the smallest details of the represented objects. In this thesis we propose a new representation scheme that allows the description of geometric models formed by several tens of millions of triangles: the EBP-Octree (Extended Bounding-Planes Octree). This data structure that is able to manage very large polygonal models (over 25M polygons), and we explain how this can be used in order to compute the inclusion of a point into the solid surface very efficiently, performing several thousand point-in-solid tests per second. The EBP-Octree (Extended Bounding-Planes Octree) is a very tight hierarchy of convex bounding volumes. Based on a spatial decomposition of the model using an octree, at each node it defines a bounding volume using a subset of the planes of the portion of the polygonal model contained at that node.We use the EBP-Octree in a haptic interaction environment, where distance tests and the orientation of collided triangles must be accurate and fast. Hence, we also compute the distance and the contact angle of a point on the solid. We also demonstrate that the proposed algorithm largely meets the interactive query rate demanded by a haptic interaction (1 kHz), despite being executed in a single CPU thread on a commonly available computer. In order to test these algorithms a haptic simulation application has been designed and its validity has been demonstrated to be used in this type of devices. Finally, we demonstrate that EBP-Octree facilitates the detection of collisions between two models formed by tens of millions of polygons, obtaining as average of each collision times smaller than 450 nanoseconds. This make EBP-Octree valid for real-time collision detection environments with very complex geometrical models.