Methods of spatial indexing of dynamic scenes based on regular octrees
Tóm tắt
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.
Tài liệu tham khảo
Cai, M. and Revesz, P., Parametric rectangles: An index structure for moving objects, Proc. of the 10th COMAD Int. Conf. on Management of Data, 2000, pp. 57–64.
Nguyen-Dinh, L.-V., Aref, W.G., and Mokbel, M.F., Spatio-Temporal Access Methods: Part2 (2003–2010), Purdue e-Pubs, 2010.
Schona, B., Mosaa, A.S.M., and Laeferb, D.F., Octree-based indexing for 3D point clouds within an Oracle spatial DBMS, Comput. Geosciences, 2013, vol. 51, pp. 430–438.
Semenov, V.A., Kazakov, K.A., Morozov, S.V., Tarlapan, O.A., Zolotov, V.A., and Dengenis, T., 4D modeling of large industrial projects using spatio-temporal decomposition, in eWork and eBusiness in Architecture, Engineering and Construction, 2010, pp. 89–95.
Zolotov, V.A. and Semenov, V.A., Modern methods of searching and indexing multidimensional data for simulation of large-scale dynamic scenes, Tr. Inst. Sistemnogo Program. Ross. Akad. Nauk, 2013, vol. 24, pp. 381–416.
Kedem, G., The quad-CIF tree: A data structure for hierarchical on-line algorithms, Proc. of the 19th Design Automation Conf., 1992, pp. 352–357.
Gottschalk, S., Lin, M.C., and Manocha, D., OBB tree: A hierarchical structure for rapid interference detection, Proc. of the SIGGRAPH'96 Conf., 1996, pp. 171–180.
Gottschalk, S., Collision Queries Using Oriented Bounding Boxes, Chapel Hill: Univ. of North Carolina, 2000.
Jimenez, P., Thomas, F., and Torras, C., 3D collision detection: A survey, Comput. Graphics, 2001, vol. 25, pp. 269–285.
Semenov, V.A., Kazakov, K.A., Zolotov, V.A., Jones, H., and Jones, S., Combined strategy for efficient collision detection in 4D Planning Applications, in Computing in Civil and Building Engineering, 2010, pp. 31–39.