4d моделирование, пространственная индексация, бинарные деревья поиска, октальные деревья, вычислительная сложность, Electronic computers. Computer science, QA75.5-76.95

As opposed to traditional project planning and scheduling methods, 4D modeling technologies allow performing more comprehensive analysis taking into account both spatial and temporal factors. Such analysis enables to identify critical issues in early design and planning stages and to save significantly on the total project implementation costs. Unsurprisingly that there is a large interest to these emerging technologies and both free and commercial systems have been recently developed and applied in different industrial domains. However, being applied to large industrial projects and programs, most systems face significant problems relating to performance degradation and limited interactive capabilities what ultimately neglects the key benefits of visual 4D modeling technologies. In this paper a promising approach to rising up the performance and scalability of 4D modeling applications by means of indexing project data has been discussed. Three alternative indexing schemes have been proposed and described in conformity to the features of spatio-temporal coherence of arising dynamic scenes. These schemes have been investigated against the efficiency criteria to resolve typical requests connected with deployment and updates of indexes, reconstruction of scenes, analysis of visible objects, and animation of dynamic scenes. Conducted computational complexity analysis and obtained asymptotic estimates confirm the efficiency of the proposed indexing schemes and cause their introduction in industrial practice. Recommendations on their practical use have been also provided.