derivadas.dev

Pablo Díaz Viñambres

MSc Informatics @ TUM

Estudio y mejora del rendimiento de modelos Octree para búsqueda de vecinos en nubes de puntos 3D

C++OpenMPLiDARTrabajos


Para mi TFG de Ingeniería Informática, desarrollé algoritmos rápidos para consultas espaciales en nubes de puntos 3D PR3\mathcal{P} \subset \mathbb{R}^3. El problema que abarqué es sencillo: dado un centro pPp \in \mathcal{P}, o bien buscamos todos los puntos a menos de una distancia dada r>0r > 0 (fixed-radius queries), o bien buscamos los kk puntos más cercanos (kNN queries) de la nube. Estas dos operaciones de búsqueda de vecindad son extremadamente comunes, y suelen convertirse en un cuello de botella computacional en el procesado de nubes grandes para teledetección y fotogrametría. Para resolver este problema, desarrollamos dos enfoques para acelerar las búsquedas:

  • Reordenación de la nube de puntos mediante Space Filling Curves (SFCs), alterando el orden en memoria para reducir fallos de caché y mejorar el rendimiento hasta un 75%.
  • Una estructura de datos en forma de octree linear, equipada con un algoritmo novedoso para recuperación rápida de puntos en búsquedas de radio fijo, y una adaptación a esta estructura de un algoritmo conocido para búsquedas kNN. Ambos algoritmos destacan en rendimiento y superan incluso bibliotecas SoTA en términos de velocidad de las búsquedas (hasta 10x más rápido, mejor escalabilidad en rr y kk), uso de memoria (70% menos, layout compacto) y tiempo de construcción (paralelizable, hasta 30x más rápida).

El trabajo obtuvo la nota máxima (10/10) y fue reconocido con Matrícula de Honor como uno de los mejores de la promoción. Tras mi graduación, mis tutores y yo seguimos trabajando en el proyecto y lo ampliamos primero a un artículo corto para las Jornadas SARTECO 2025. Más adelante, redactamos un artículo completo, ya enviado y disponible como preprint en arXiv. Consulta la entrada del proyecto de investigación para más información!.