BC/NW 2008, №1 (12): 4.2

О ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ МОДУЛЯРНОЙ АРИФМЕТИКИ К ПОВЫШЕНИЮ ТОЧНОСТИ ПОЗИЦИОНИРОВАНИЯ ДВИЖУЩИХСЯ ОБЪЕКТОВ ВИРТУАЛЬНОЙ РЕАЛЬНОСТИ

Д.А. Орлов

(Москва, Московский энергетический институт(Технический университет), Россия)

orlovdmal@gmail.com

1. Введение

Системы виртуальной реальности в настоящее время приобретают всё большую актуальность. Благодаря развитию средств вычислительной техники, появилась возможность совершенствования данных систем. Совершенствование происходит по нескольким направлениям: усложняются трёхмерные модели сцены, увеличивается размер области пространства, представляемой в системе, изменяются алгоритмы визуализации, используются более точные физические модели движения объектов.

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

2. Вычислительные ошибки и их последствия

В приложениях виртуальной реальности процесс визуализации можно разделить на две части:

1) вычисление координат объектов;

2) собственно визуализация трёхмерной сцены.

Можно сказать, что на этапе 1) происходит позиционирование объекта в модельном пространстве, а на этапе 2) – позиционирование трёхмерной модели на экране. На этапе 2 активно используются методы вычислительной геометрии. На этапе 1 используются методы численного моделирования, чаще всего, методы решения дифференциальных уравнений, хотя алгоритмы вычислительной геометрии также используются (например, при определении столкновений объектов).

Таким образом, проблема позиционирования движущихся объектов виртуальной реальности приводит к подзадачам, использующим два вида алгоритмов. Численное решение дифференциальных уравнений используется для моделирования движения объектов, а алгоритмы вычислительной геометрии – для определения столкновений объектов и подготовки геометрических данных для аппаратной визуализации.

Рассмотрим подробно влияние вычислительных ошибок на результат алгоритма. Подобные ошибки в алгоритмах вычислительной геометрии могут приводить к неверным результатам алгоритмов, в том числе качественно отличающихся от истинных. В некоторых случаях алгоритм может даже войти в бесконечный цикл [1,2]. Ошибки округления при решении дифференциальных уравнений численным методом могут накапливаться от итерации к итерации (особенно при малых длинах шага). Это приводит к тому, что у конкретной реализации численного метода существует шаг, при котором погрешность минимальна. При дальнейшем уменьшении шага погрешность метода начинает возрастать. Наиболее выражен данный эффект для метода Эйлера [3, 4]. При усложнении математической модели движения вычислительные ошибки также должны возрасти, благодаря увеличению количества арифметических операций.

На практике, вычислительные ошибки приводят к следующим нежелательным эффектам. Ошибки, возникающие на этапе 1, вызывают некорректное (нереалистичное) поведение движущихся объектов виртуальной реальности. Вычислительные ошибки, возникающие на этапе 2, приводят к явным дефектам изображения (артефактам), таким, как: разрывы в полигональных сетках трёхмерных моделей и ландшафтов, исчезновение, или наоборот, появление нежелательных объектов, вследствие неправильного определения их видимости, дрожание анимации и другие [5].

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

Однако, существует ещё один способ: применение вычислений с исключением ошибок округления. Подобный тип вычислений известен в англоязычной литературе как «безошибочные» (“error-free”) [6] или «точные» (“exact”)[1]. Под вычислениями с исключением ошибок округления будем понимать вычисления, при которых результаты определённых арифметических операций могут быть представлены точно. Теоретически, при использовании вычислений подобного типа можно полностью избавиться от вычислительных ошибок. Существуют различные типы подобных вычислений, например, вычисления в рациональных числах [6] или вычисления в алгебраических числах [7].

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

3. Вычисления с исключением ошибок округления в рациональных числах

3.1 Представление рациональных чисел

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

Однако, существует другой способ представления рациональных чисел – представление чисел в одномодульной системе [6]. В этом случае рациональное число представляется целым числом из множества целых чисел от 0 до M‑1, где число M называют модулем системы. В этом случае отпадает необходимость сокращения результата после каждой арифметической операции. Однако, возникают другие недостатки: сложность преобразования чисел в обыкновенную дробь и сложность сравнения чисел. В этом случае вычислительный процесс состоит из трёх этапов [8]:

1) перевод входных данных из обыкновенных дробей в одномодульную систему;

2) выполнение вычислений в одномодульной системе;

3) перевод выходных данных из одномодульной системы в обыкновенную дробь.

В случае применения этой системы а также с малым количеством сравнений этот способ представления может обеспечить большее быстродействие, чем представление чисел обыкновенной дробью.

Представление рациональных чисел в многомодульной системе. В этом случае число представляется ни одним целым числом, а n числами, взятыми по модулям m₁,…,m_n. Если любая пара чисел из этих модулей – взаимно-простые, то такая многомодульная система эквивалентна одномодульной системе со значением модуля, равным произведению m₁…m_n [6, 8]. Основным преимуществом этого способа представления является возможность распараллеливания вычислений между одинаковыми вычислителями. Все вычислители выполняют одни и те же операции, но каждый вычислитель приводит результаты по своему модулю. Это позволяет легко распараллелить арифметические операции над числами очень большой разрядности. Основной недостаток этого способа – ещё больше возрастает сложность преобразования чисел в обыкновенные дроби, а также сложность сравнения чисел.

В данной работе для реализации вычислений с исключением ошибок округления в рациональных числах выбран способ представления рациональных чисел в одномодульной системе, поскольку он прост в реализации и при этом обеспечивает быстродействие, лучшее, чем представление чисел обыкновенной дробью. Более того, реализация почти всех арифметических операций в многомодульной системе аналогична реализации арифметических операций в одномодульной системе, что может облегчить дальнейшие исследования.

3.2 Вычисления с исключением ошибок округления в одномодульной арифметике

Множество дробей Фарея порядка N (обозначим как F_N) – это множество обыкновенных дробей, допускающих отображение во множество I_M числитель и знаменатель которых по абсолютной величине не больше N. Натуральное число N называют порядком дроби Фарея.

Отображение осуществляется следующим образом [6]:

,

где b^-1(mod M) – формальная обратная величина для b по модулю M.

В одномодульной системе с простым модулем M множество дробей Фарея порядка N отображается на множество I_M={0,1,2,…, M-1}, если выполняется соотношение 2N²+1≤M. Если данное соотношение не выполняется, возникает псевдопереполнение. В этом случае результат может быть неправильно интерпретирован. Псевдопереполнение имеет важное свойство: если оно имеет место в промежуточном результате, но при этом конечный результат принадлежит области F_N, то ошибки в конечном результате вычислений не возникнет [6, 8, 9].

При использовании способа представления дробей Фарея числами в одномодульной системе, операции сложения, вычитания и умножения сводятся к соответствующим операциям по модулю M над их целыми образами во множестве I_M. Операция деления сводится к умножению на обратное число.

Для обеспечения корректности полученных результатов необходимо определить модуль системы, способный гарантировать отсутствие псевдопереполнения. Исходя из свойства псевдопереполнения, указанного выше, необходимо обеспечить нахождение области F_N, лишь конечных результатов вычисления. Поэтому зная порядок дроби, представляющей результат, можно определить требуемый модуль. Для рациональных чисел, по абсолютной величине не превосходящих целое число A, при этом имеющих знаменатель не больше целого числа E, получена следующая оценка модуля [9]:

(1)

Также получен способ оценки порядка результата некоторого выражения , основанный на формуле (1):

найти диапазон величины (A);

оценить максимальный знаменатель выражения (E);

оценить модуль M≈2A²E²;

3.3. Особенности решения дифференциальных уравнений с применением вычислений в одномодульной системе

Поставим следующую задачу исследования: для вычислений с плавающей запятой и с исключением ошибок округления сравнить точность и время решения модельных уравнений, задающих движение физического объекта. Для простоты, не будем рассматривать вращательное движение. Поэтому объект можно заменить материальной точкой. Так как уравнение движения материальной точки в трёхмерном пространстве сводится к трём уравнениям движения в одномерном пространстве (по одному для каждой координаты), можно ограничиться рассмотрением одномерных случаев. Такая задача сводятся к решению дифференциального уравнения следующего вида:

(2)

где - соответственно координата, скорость и ускорение материальной точки, - масса объекта, - модельное время, - сумма сил, действующих на материальную точку.

В процессе исследования было показано, что если правая часть указанного уравнения (2) зависит от или , то вместе с номером итерации знаменатель решения возрастает как минимум экспоненциально. Это означает, что при любом значении модуля можно проделать лишь ограниченное число итераций. Так как необходимо предотвращать выход результатов из множества F_N, то в условиях ограниченности разрядной сетки единственным способом предотвращения выхода результатов из множества F_N представляется их округление [9]. Для этого зададимся максимальным количеством итераций (n_round), которое необходимо проделать без округления. Исходя из имеющихся данных, определим модуль M. После каждых n_round итераций будем производить округление значений x_i, v_i. Если производить их округление до точности, которую обеспечивают числа с плавающей запятой, можно ожидать, что ошибки округления, внесённые в результаты, полученные таким образом, будут не больше ошибок округления при вычислениях с плавающей запятой. При этом все константы, используемые в численном методе не округляются. Исходя из этого, предлагается новая схема применения вычислений в одномодульной системе для численного решения дифференциальных уравнений. Она представлена на рис. 1.

Рис. 1. Схема вычислений при решении дифференциального уравнения численным методом при использовании промежуточных округлений

4. Программная реализация и экспериментальное исследование

4.1 Программная реализация

Для выполнения вычислений в одномодульной системе реализована объектно-ориентированная библиотека со следующими возможностями:

выполнение арифметических операций в одномодульной системе;

поддержка модулей системы произвольной разрядности;

преобразования типов;

решение дифференциальных уравнений.

Библиотека реализована на языке C++ и не содержит в себе ассемблерного кода и вызовов, специфичных для какой-либо операционной системы.

С использованием данной библиотеки разработана программа, позволяющая решать модельные задачи при различных значениях начальных условий, шага и количества итераций без округления, а также обрабатывать полученные результаты.

4.2 Условия эксперимента

Для исследования возможности повышения точности решения уравнений движения с использованием вычислений в одномодульной системе проведены экспериментальные исследования. Для определения эффекта от применения вычислений в одномодульной системе, необходимо сравнить результаты решения наиболее типичных задач моделирования движения объекта в трёхмерных сценах, полученные двумя способами (с использованием вычислений с плавающей запятой и в одномодульной системе) с аналитическим решением выбранных задач. Поэтому для эксперимента необходимо выбрать модельные задачи, имеющие аналитическое решение. В качестве шага интегрирования выбираем числа вида 2^-n, где n – натуральное число. Такой шаг можно точно представить в формате с плавающей запятой, используемом в вычислительных машинах, что позволит минимизировать погрешность численного метода, использующего вычисления с плавающей запятой. В качестве показателя точности будем использовать среднеквадратичное отклонение численного решения от аналитического на всём интервале решения задачи. В качестве метода решения задач выбран метод Эйлера, так как при его использовании эффекты, вызванные вычислительными ошибками, проявляются наиболее ярко.

В качестве модельных задач рассмотрим три задачи, часто возникающие при моделировании движения физического объекта в системах виртуальной реальности. Для удобства анализа результатов ограничимся одномерными случаями. Выберем следующие задачи:

равноускоренное прямолинейное движение материальной точки (сила, действующая на материальную точку, постоянна), что соответствует следующему дифференциальному уравнению:

, где C – константа;

движение материальной точки в среде с вязким трением (сила, действующая на материальную точку, прямо пропорциональна её скорости) что соответствует следующему дифференциальному уравнению:

, где C – константа, ;

гармонические колебания материальной точки (сила, действующая на материальную точку, прямо пропорциональна её координате) что соответствует следующему дифференциальному уравнению:

, где C – константа, .

4.3 Результаты эксперимента

В ходе эксперимента были получены зависимости выбранного показателя точности решения (среднеквадратичного отклонения численного решения от аналитического) от длины шага (обозначен как h) для обоих типов вычислений. В качестве показателя ошибки мы используем среднеквадратичное отклонение численного решения от аналитического. Полученные зависимости имеют сходный характер для всех модельных задач. Поэтому приведём их графики для задачи 2 на рис. 2. По оси абсцисс отложены показатели степени числа 2 в знаменателе шага численного метода, по оси ординат – значения среднеквадратичного отклонения решений. Зависимости даны для n_round=8 и n_round=16. Проведенные эксперименты показали что, в целом вычисления в одномодульной системе обеспечивают меньшее значение среднеквадратичного отклонения, чем вычисления с плавающей запятой, особенно для малых размеров шага. Также видно, что точность решения возрастает вместе с n_round.

-log₂(h)

n_round=8

n_round=16

Рис. 2. Зависимости среднеквадратичного отклонения от значения величины шага для вычислений с плавающей запятой и в одномодульной системе для задачи 2

Также получены зависимости среднеквадратичных отклонений численных решений задач 1 и 2 от аналитического решения этих задач для вычислений с плавающей запятой (σ_F) и вычислений в одномодульной системе (σ_M) от начального значения координаты (). Эти зависимости представлены на рис. 3. По оси абсцисс отложены значения , по оси ординат – значения среднеквадратичных отклонений.

Рассмотрим эти зависимости для задачи 1. В данном случае погрешность решения с использованием чисел с плавающей запятой резко возрастает с увеличением начального значения координаты. Это связано с тем, что абсолютная точность представления числа в формате с плавающей запятой снижается по мере роста абсолютной величины числа. Однако, затем рост погрешности вычислений с плавающей запятой останавливается, т.к. разность порядков приращения координаты внутри итерации и самой координаты становится больше разрядности мантиссы на всём временном интервале решения задачи.

Зависимости тех же величин, построенные для задачи 2 также представлены на рис 3. Зависимость среднеквадратичного отклонения от начального значения для задачи 2, полученная при использовании вычислений с плавающей запятой, аналогична зависимости, полученной при исследовании задачи 1. В то же время зависимость σ_M от для задачи 2 имеет иной характер, чем соответствующая зависимость для задачи 1. Это связано с тем, что в данном случае выполняется округление промежуточных результатов. Поэтому, при увеличении достигается то же максимальное значение среднеквадратичного отклонения, что и для вычислений, использующих числа с плавающей запятой. Тем не менее, существует область в которой вычисления с исключением ошибок округления обеспечивают меньшую погрешность. Также отметим, что при увеличении n_round вычислительная погрешность снижается.

log2(x0) σF σM

σF σM nround=8 σM nround=16 log2(x0)

Рис. 3. Зависимости ошибки решения от начальной координаты для задачи 1 (слева) и задачи 2 (справа) для обоих типов вычислений

В ходе эксперимента также исследована зависимость скорости вычислений в одномодульной системе от разрядности модуля. В качестве тестовой задачи выбрана задача 1. Количество итераций 2¹⁶=65536. В качестве модулей системы использовались простые числа Мерсенна. Длина модуля изменялась от 520 до 11200 бит. Эксперимент проводился на компьютере со следующими характеристиками:

процессор Intel Pentium 4A 2,26 GHz;

512 МБ оперативной памяти PC2700;

операционная система Microsoft WindowsXP ServicePack 2.

Из полученных результатов видно, что скорость решения убывает с увеличением разрядности модуля. При этом наибольшая полученная скорость решения задачи с применением вычислений с исключением ошибок округления составила 3775 итераций в секунду, что меньше скорости решения с применением вычислений с плавающей запятой примерно в 1000 раз (одна из причин такого падения в производительности состоит в том, что вычисления с исключением ошибок округления реализованы программно, в отличие от вычислений с плавающей запятой).

5. Заключение

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

В результате проведённого исследования разработана библиотека, реализующая вычисления с исключением ошибок округления в одномодульной системе, методика оценки модуля системы, необходимого для представления результатов вычислений, также показано, что применение вычислений с исключением ошибок округления для решения задач моделирования движения приводят к резкому росту знаменателя, следовательно, решение затруднено. Экспериментальное исследование показало, что существуют области резкого повышения точности решения указанной задачи при использовании вычислений с исключением ошибок округления. Однако, увеличение точности вычислений достигается ценой потери скорости (на данный момент разрыв составляет примерно 1000 раз). Однако, скорость вычислений можно повысить, перейдя к многомодульной системе представления чисел. Также можно сказать, что эффективное применение рассматриваемого типа вычислений возможно для задач, в которых на каждой итерации вносится существенная погрешность вычисления.

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

6. Литература

[1] L. Kettner, K. Mehlhorn, S. Pion, S. Schirra, and C. Yap. “Classroom Examples of Robustness Problems in Geometric Computations”, ESA, volume 3221 of LNCS, pp. 702-713, 2004

http://www.mpi-inf.mpg.de/~kettner/pub/nonrobust_cgta_06.pdf

[2] C. Yap. “White Paper on Exact Computation and Reliable Geometric Software”, Courant Institute of Mathematical Sciences, 1996

[3] David M. Bourg. “Physics for Game Developers”, O’Reilly’s Associates, Inc., 2002

[4] Амосов А.А., Дубинский Ю.А., Копченова Н.В. “Вычислительные методы для инженеров: Учебное пособие” – 2-е изд., доп. – М.: Издательство МЭИ, 2003. – 596 с., ил

[5] Peter Freese. “Solving Accuracy Problems in Large World Coordinates”, “Game Programming Gems 4”, Charles River Media, 2004, pp. 157-170

[6] R.T. Грегори Р., Кришнамурти Е. Безошибочные вычисления. Методы и приложения: Пер. с англ. – М.: Мир,1998 – 208 с., ил.

[7] K.A. Wahid, V.S. Dimitrov and G.A. Jullien. “Error-Free Arithmetic for Discrete Wavelet Transforms using Algebraic Integers”, Proceedings of the 16th IEEE Symposium on Computer Arithmetic p. 238, 2003

[8] Дзегелёнок И.И., Оцоков Ш.А. “Экспериментальное исследование модели безошибочных вычислений на ПМК-сети КУРС 2000”, “Сб. трудов международной научной конференции "Информационные средства и технологии", М.:МЭИ (ТУ), 2003.- C.103-106

[9] Орлов Д.А. “ Повышение точности позиционирования движущихся объектов виртуальной реальности ” Труды международной научно-технической конференции «Информационные средства и технологии». 16-18 октября 2007 г. В трёх томах Т2. – М.: Полиграфический центр МЭИ (ТУ) С. 199-203