BC/NW 2007, №2, (11) :7.1
ПОВЫШЕНИЕ ТОЧНОСТИ ПОЗИЦИОНИРОВАНИЯ ДВИЖУЩИХСЯ ОБЪЕКТОВ ВИРТУАЛЬНОЙ РЕАЛЬНОСТИ
Орлов Д.А.
(Москва, Московский энергетический институт (ТУ), Российская Федерация)
Актуальность использования систем виртуальной реальности приводит к постоянному повышению требований, предъявляемых к ним. Помимо улучшения качества изображения, основные требования следующие:
– увеличение размеров области, представляемой в виртуальной среде;
– повышение точности позиционирования объектов трёхмерных сцен.
Задачу позиционирования объекта в виртуальной среде можно разделить на две подзадачи: моделирование движения объекта и позиционирование трёхмерной модели. Задача моделирования движения физического объекта состоит в вычислении его координат в модельном пространстве. Движение объекта чаще всего задаётся дифференциальными уравнениями.
Однако, подобные системы используют вычисления с плавающей запятой, в процессе которых возникают ошибки округления. Это приводит к нежелательным эффектам, таким как искажение трёхмерных моделей объектов и траекторий их движения [1]. Для борьбы с ними существуют различные способы, например: увеличение разрядной сетки чисел, изменение порядка арифметических операций. Однако, они не позволяют полностью исключить ошибки округления, поэтому интересным представляется применение вычислений с исключением ошибок округления, то есть такого типа вычислений, при использовании которого результаты основных арифметических операций вычисляются точно [2,3,4].
Поскольку требуется точное представление результата деления, для реализации данного типа вычислений необходимо работать с рациональными числами. Для представления рациональных чисел целесообразно выбрать представление в модулярной арифметике, так как оно обеспечивает более высокое быстродействие, чем вычисления в обыкновенных дробях. Вычисления в модулярной арифметике могут быть реализованы в одномодульной или многомодульной системе. Так как обе эти системы эквивалентны [2], для исследований применим вычисления в одномодульной системе, как более простые в реализации.
Областью представления чисел в одномодульной системе является множество дробей Фарея – обыкновенных дробей, числитель и знаменатель которых по абсолютной величине не больше натурального числа N (порядка дроби). Для корректного преобразования числа из одномодульной системы с модулем M в дробь Фарея порядка N необходимо выполнение соотношения M≥2N2+1. Если результат вычислений выходит из области представления, то такая ситуация называется псевдопереполнением. Для его предотвращения надо выбрать модуль системы, достаточный для представления результатов. Предлагается следующая методика оценки такого модуля:
1) найти диапазон величины (A);
2) оценить максимальный знаменатель выражения (E);
3) оценить порядок дроби Фарея N=AE-1;
4) оценить модуль M≈2A2E2;
В ходе исследований также выявлено, что при решении численным методом большинства дифференциальных уравнений движения, наблюдается резкий (как минимум, экспоненциальный) рост порядка дроби, представляющей результат, с номером итерации. Поэтому при любом модуле можно проделать лишь ограниченное число итераций. Для предотвращения роста порядка дроби предлагается через равное количество итераций ввести промежуточные округления. Исходя из этого разработана технология вычислений в одномодульной системе применительно к задачам моделирования движения физического объекта. Ключевыми её составляющие – это оценка модуля системы и решение задачи численным методом в одномодульной системе с промежуточными округлениями.
Для выполнения вычислений в одномодульной системе реализована объектно-ориентированная библиотека со следующими возможностями:
• выполнение арифметических операций в одномодульной системе
• поддержка модулей системы произвольной разрядности
• преобразования типов
• решение дифференциальных уравнений
Экспериментальное исследование проводилось следующим образом: модельные задачи решались с использованием обоих типов вычислений, затем численные решения сравнивались с аналитическим. В качестве модельных задач выбраны задачи, наиболее часто возникающие при моделировании движения тел в системах виртуальной реальности: равноускоренное движение материальной точки (задача 1), движение в среде с вязким трением (задача 2), гармонические колебания груза (задача 3).
В ходе эксперимента исследованы зависимости точности решения задач от шага численного метода. Зависимости для задачи 1 представлены на рисунке 1. Как видно из графиков, при малых значениях шага погрешность вычислений с плавающей запятой начинает возрастать, для вычислений в одномодульной системе такой рост не наблюдается.
Рисунок 1 – Зависимости погрешностей от шага метода
Рисунок 2 – Зависимости погрешностей от начального значения координаты
Также проведены исследования зависимости погрешности решения от начального значения координаты x0 (рисунок 2). Особенность задачи 1 состоит в том, что при её решении численным методом не происходит резкого роста порядка дроби, поэтому она решается без промежуточных округлений. Для вычислений с плавающей запятой при увеличении x0 наблюдается резкий рост погрешности. Для вычислений в одномодульной системе такого роста не происходит. Задача 2 решается с промежуточными округлениями. Зависимость для вычислений с плавающей запятой аналогична зависимости для задачи 1. Зависимость для вычислений в одномодульной системе с промежуточными округлениями аналогична зависимости для вычислений с плавающей запятой, однако наблюдается меньший рост погрешности.
Скорость решения задачи 1 в одномодульной системе составила 3775 итераций/сек (скорость вычислений с плавающей запятой – 4∙106 итераций/сек). При такой скорости вычислений, минимальный шаг для решения задачи в реальном времени составит 1/3775 с. Это означает, что скорость вычислений в одномодульной системе достаточна для решения данной задачи в реальном времени, но для их эффективного применения необходимо нуждается в повышении.
В процессе работы были получены следующие результаты и сделаны следующие выводы:
• разработана методика оценки модуля системы, необходимого для представления результатов вычислений;
• разработана технология вычислений в одномодульной системе для решения задач позиционирования;
• существуют области резкого повышения точности решения задачи позиционирования при вычислениях в модулярной арифметике;
• скорость вычислений в одномодульной системе достаточна для решения модельных задач в реальном времени, но для эффективного применения нуждается в повышении.
Основным направлением дальнейших исследований является переход к многомодульной системе, что позволит ускорить вычисления путём параллельного выполнения действий по разным модулям.
ЛИТЕРАТУРА
1. Peter Freese Solving Accuracy Problems in Large World Coordinates // «Game Programming Gems 4», Charles River Media, 2004, с. 157 – 170
2. Грегори Р., Кришнамурти Е. Безошибочные вычисления. Методы и приложения: Пер. с англ. – М.: Мир,1998 – 208 с., ил.
3.Дзегелёнок И.И. , Оцоков Ш.А. Экспериментальное исследование модели безошибочных вычислений на ПМК-сети КУРС 2000 // Сб. трудов международной научной конференции "Информационные средства и технологии" М.:МЭИ (ТУ), 2003.- C.103-106.
4. Орлов Д.А., Оцоков Ш.А. О возможности применения «безошибочных» вычислений для решения задачи Коши // Сб. трудов Междунар. Науч-техн. Конф. «Информационные средства и технологии» Том 2, М.:МЭИ (ТУ), 2006г. – с. 207-210