Resumen de Interacción háptica en tiempo real con modelos gráficos de alta resolución
- español
En nuestros días, la utilización de la tecnología informática se ha generalizado en muchas disciplinas, como pueden ser la medicina, los videojuegos, los dispositivos hápticos, la realización de películas, el diseño y la fabricación de objetos, la planificación de rutas para la movilidad, etc. Principalmente destacan el desarrollo de la realidad aumentada, la realidad virtual y la tecnología háptica.
Para todas estas tecnologías cada día van apareciendo nuevos dispositivos que permiten interactuar dentro de escenarios reales o virtuales por lo que se hace necesario trabajar con modelos geométricos cada vez mayores y más complejos En la actualidad los escáneres para la captura de modelos geométricos han abaratado mucho los precios y han aumentado mucho sus prestaciones, permitiendo obtener modelos geométricos en tres dimensiones con gran resolución, recogiendo de esta forma los más mínimos detalles de los objetos representados.
Además estos modelos tienen una gran resolución, y aunque los ordenadores cada vez sean más rápidos y potentes, el trabajar con ellos directamente sin utilizar ningún método de optimización se hace inviable si se espera que el tiempo de respuesta sea muy rápido o cercano al tiempo real.
En esta tesis se propone un nuevo esquema de representación que permite la descripción de sólidos formados por varias decenas de millones de triángulos: el EBP-Octree (Extended Bounding-Planes Octree). Este utiliza una estructura jerárquica de volúmenes envolventes indexados en el espacio. Dicha jerarquía se monta sobre un árbol octal. La construcción se hace recorriendo el árbol de abajo hacia arriba. Para la construcción de las envolventes, la selección de los planos relevantes en cada uno de los nodos se realiza siguiendo tres estrategias: aquellos cuyo desplazamiento ha sido menor, de manera aleatoria y mediante un algoritmo de clustering: el k-mediana.
Para validar esta estructura se han implementado algoritmos que permiten la detección de la inclusión punto en sólido, además del cálculo de la distancia y del ángulo de contacto de un punto sobre el sólido. Estos algoritmos han obteniendo unos tiempos de respuesta superior a los 1KHz que son los que se toman como referencia para poder trabajar con dispositivos hápticos. Para probar estos algoritmos se ha diseñado una aplicación de simulación háptica y se ha demostrado su validez para ser utilizada en este tipo de dispositivos.
Por último se han implementado otros algoritmos que permiten calcular la colisión entre dos modelos formados por varias decenas de millones de polígonos, obteniéndose como media de cada colisión tiempos menores a los 450 nanosegundos.
- English
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.
