Поиск ближайших соседей в сложных трехмерных сценах.


Поиск ближайших соседей в сложных трехмерных сценах.

Авторы

Петрищев К.С., Золотов В.А., Семенов В.А.

Аннотация

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

Издание

Труды XIX Байкальской Всероссийской конференции «Информационные и Математические Технологии в Науке и Управлении» в 3 т. Том 3. Издательство: ИСЭМ СО РАН, 2014. Стр. 56-62.

Научная группа

Системная интеграция и прикладные программные комплексы

Все публикации за 2014 год Все публикации