III Simposio de Postgrado 2025: Ingeniería, ciencia e innovación

02 62 *E-mail: rocarras@dcc.uchile.cl ¹ Departamento de Ciencias de la computación, Universidad de Chile ² Instituto de informática, Universidad Austral de Chile Roberto Carrasco ¹* Héctor Ferrada ² Cristóbal Navarro ² Nancy Hitscheld ¹ RTX-GPU Preprocessing for Accelerating 3D Convex Hull Computation Módulo Cs. de la Computación y Cs. de Datos e IA Resumen En un mundo cada vez más exigente, donde los videojuegos demandan repre- sentaciones más realistas, los vehículos autónomos utilizan múltiples sensores para capturar su entorno más detalladamente y las simulaciones se vuelven cada vez más complejas, son algunos ejemplos de cómo cada vez se necesitan modelos más robustos y pesados donde las tecnologías actuales enfrentan difi- cultades para procesar estos datos en tiempo real. En este contexto, el algoritmo de cerradura convexa sigue siendo una herramienta fundamental en la geome- tría computacional que se enfrenta a las mismas limitantes cuando se tratan datos a gran escala. Este trabajo presenta un filtro de preprocesamiento 3D di- señado para optimizar algoritmos de cerradura convexa con gran escalabilidad, aprovechando las capacidades de trazado de rayos (Ray Tracing) disponibles en las GPU modernas. La idea principal consiste en utilizar el trazado de rayos en combinación con téc- nicas de reducción paralelas para construir un poliedro delimitador a priori que descarta eficazmente los puntos fuera de la posible cerradura convexa. Este en- foque minimiza los datos redundantes y optimiza la carga computacional para la posterior cómputo de la cerradura convexa. Para validar el método, el filtro se prueba en tres distribuciones de puntos dife- rentes: normal, uniforme y esférica. Los resultados experimentales muestran que, especialmente para conjuntos de datos con distribución normal y uniformes, el filtro reduce sustancialmente el tiempo de procesamiento de los algoritmos de envoltura convexa. Al combinarse con una de las implementaciones de envoltura convexa 3D más rápidas conocidas, el filtro alcanza velocidades hasta 40x supe- riores a las principales soluciones en CPU multinúcleo. En resumen, este trabajo demuestra que la integración del trazado de rayos ace- lerado por GPU en el preprocesamiento geométrico ofrece una estrategia pode- rosa para mejorar el rendimiento en el campo de la geometría computacional, especialmente en aplicaciones 3D a gran escala o en tiempo real. __Referencias [1] Roberto Carrasco, Héctor Ferrada, Cristóbal A. Navarro, and Nancy Hitschfeld. An evaluation of gpu filters for accelerating the 2d convex hull, 2023. [2] Héctor Ferrada, Cristóbal A. Navarro, and Nancy Hitschfeld. A filtering technique for fast convex hull construction in r2. Journal of Computational and Applied Mathematics, 364:112298, 2020