Bq-Rtree: una estructura de datos para la visualización de entornos urbanos en tiempo real

Abstract

El view-culling o podado de la pirámide de visión, es una técnica de aceleración habitualmente usada para conseguir movimientos de cámara en tiempo real en escenarios virtuales complejos. El rendimiento de esta técnica depende en gran manera de la estructura de datos sobre la cual se realice el podado. En este artículo se propone una estructura de datos, la BqR-Tree, la cual es una R-Tree modificada que mejora el rendimiento habitual de las R-Tree en la fase de view-culling. Para construir la estructura en tiempo de preprocesado, la ciudad se divide por medio de una partición espacial en quadtree y la manzana urbana se adopta como la unidad básica. La finalidad de esta estructura es acelerar la visualización de escenarios complejos urbanos que contengan, no sólo elementos estáticos, sino también dinámicos. La utilidad de esta estructura ha sido probada con datos poco estructurados, lo que la hace apropiada para casi cualquier conjunto de datos urbanos, y ha sido contrastada con otras estructuras de datos obteniendo resultados que suponen un promedio del 30% de mejora en la velocidad de visualización.