Статья посвящена развитию и исследованию методов пространственного индексирования и анализа сложных динамических сцен, возникающих в приложениях компьютерной графики, робототехники, анимации, виртуальной и дополненной реальности, САПР, системах nD-моделирования и планирования проектов. Подобные сцены представляются композицией большого числа протяженных геометрических объектов, проявляющих индивидуальное динамическое поведение. Главное внимание в статье уделяется алгоритмам исполнения типовых пространственных запросов с использованием регулярных динамических октодеревьев. В частности, исследуются алгоритмы определения столкновений, выборки по заданной области, поиска ближайшего соседа. Для введенных модельных наборов данных на основе вероятностного анализа выводятся оценки сложности для построения индексов и исполнения типовых запросов в среднем. Полученные оценки существенно улучшают известные пессимистические результаты и служат обоснованием целесообразности применения регулярных октодеревьев для пространственного индексирования масштабных динамических сцен. Результаты проведенных вычислительных экспериментов подтверждают полученные теоретические результаты и иллюстрируют возможности создания эффективных приложений компьютерной графики в условиях перманентно растущей сложности визуальных моделей.
展开▼
