Methods of spatial indexing of dynamic scenes based on regular octrees

Abstract

The paper is devoted to study and development of spatial indexing methods as applied to three dimensional scenes arising in computer graphics, CAD/CAM systems, robotics, virtual and augmented reality applications, nD-modeling systems, and in project planning. Such scenes are compositions of a great number of extended geometrical objects exhibiting individual dynamic behaviors. The main focus is placed on algorithms for executing typical spatial queries with the use of regular dynamic octrees. In particular, algorithms for determining collisions, region search and nearest neighbor search are studied. For the model datasets introduced, average complexity estimates of index construction and execution of typical queries are derived based on probabilistic analysis. The estimates obtained significantly improve known pessimistic results and justify the suitability of regular octrees to spatial indexing of large-scale dynamic scenes. Results of computational experiments substantiate theoretical results and demonstrate possibilities of creating efficient computer graphics applications under the condition of permanently growing complexity of visual models.