Premium
BqR‐Tree: A Data Structure for Flights and Walkthroughs in Urban Scenes with Mobile Elements
Author(s) -
Pina J.L.,
Seron F.,
Cerezo E.
Publication year - 2010
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2010.01654.x
Subject(s) - quadtree , data structure , rendering (computer graphics) , computer science , visualization , computer graphics (images) , tree structure , computer vision , artificial intelligence , programming language
BqR‐Tree, the data structure presented in this paper is an improved R‐Tree data structure based on a quadtree spatial partitioning which improves the rendering speed of the usual R‐trees when view‐culling is implemented, especially in urban scenes. The city is split by means of a spatial quadtree partition and the block is adopted as the basic urban unit. One advantage of blocks is that they can be easily identified in any urban environment, regardless of the origins and structure of the input data. The aim of the structure is to accelerate the visualization of complex scenes containing not only static but dynamic elements. The usefulness of the structure has been tested with low structured data, which makes its application appropriate to almost all city data. The results of the tests show that when using the BqR‐Tree structure to perform walkthroughs and flights, rendering times vastly improve in comparison to the data structures which have yielded best results to date, with average improvements of around 30%.