РАЗДЕЛ II
АЛГОРИТМИЧЕСКИЕ И ПРОГРАММНО-АППАРАТНЫЕ МЕТОДЫ ОРГАНИЗАЦИИ ДИНАМИЧЕСКИХ СЦЕН В ИГК ОВ
Существовавшие методы не позволяли осуществлять вывод нескольких символов (свыше пяти) на картографическом фоне, при условии, что матрица, описывающая их конфигурацию, достигала значения 24 х 24 [4-7, 50, 51, 82, 88]. Организация таких вычислений усложнялась тем, что следует успевать пошагово осуществлять одновременно перекодировку точек, в нашем случае 5-ти массивов, каждый из которых состоял из более чем 500 точек, и запоминать массив, состоящий из множества данных, определяемых числом слоев, составляющих картографический фон, находящийся под каждым символом, а затем, после очередного шага перемещения символа, воспроизводить "освободившуюся" от символа его часть.
Рассмотрим задачу отображения динамики единичного видеосимвола в реальном времени.
2.1. Аналитическое описание динамики единичного видеосимвола и оценка вычислительных ресурсов
2.1.1. Матричный метод.
Движение объекта отображается на экране как перемещение видеосимвола S, представленного некоторым подмножеством множества точек квадратной n x n матрицы пикселов [4, 82, 88]. В равноотстоящие дискретные моменты времени tk (k = 1, 2, ...) на вход программы управления движением символа поступают координаты точки Р2 (х2, у2), в которую символ S должен быть перемещен из предыдущей точки Р1 (х1, у1). Задача состоит в том, что необходимо переместить символ S из точки Р1 в точку Р2 и повернуть продольную ось символа на новое направление движения вдоль вектора с минимально возможным использованием вычислительных ресурсов. При этом движение должно происходить без деформации символа S (требование константности формы).
Введем две системы координат: основную ОХY, ось ОХ которой свяжем с нижней, а ось ОY - с левой границами экрана и О'Х'Y' - систему для задания новых координат точек символа, изменившего ориентацию своего движения на определенный угол (рис.2.1, а и рис.2.1, б).
Обе координатные системы - декартовы прямоугольные с одинаковыми масштабами по всем четырем осям. Расположим квадратную n x n матрицу-носитель символа так, что точка пересечения ее диагоналей находится в центре О' дополнительной системы координат О'Х'Y'. Тогда положение и конфигурация символа определяются заранее заданными координатами некоторых точек матрицы в системе X'O'Y'. Конфигурацию символа предполагаем симметричной относительно его продольной оси, а центром изображения S считаем точку О'. Обозначим точками Р1(х1, у1) и Р2(х2, у2) предыдущее и последующее положения центра символа. Символ считаем расположенным в точке Рi(хi, уi), если его центр О' находится в точке Рi(хi, уi).
Перенести символ S в точку Р2(х2, у2) означает воспроизвести его в этой точке так, чтобы центр О' имел координаты (х2, у2), а продольная ось символа совпала с направлением вектора . Такое движение достигается параллельным переносом системы координат Х'О'Y' в точку Р2(х2, у2)
х = х' + х2 ; у = у' + у2 (2.1)
и поворотом ее на угол ?:
х = х'соs? - у'sin? ,
y = х'sin? + у'соs?.
(2.2)
Здесь
? = arctg (y2 - y1)/(x2 - x1) (2.3)
- угол наклона прямой к горизонтали.
Одновременный перенос и поворот описывается преобразованием:
х = х'соs? - у'sin? + x2;
y = х'sin? + у'соs? + y2.
(2.4)
В (2.4)х2, у2 - координаты нового начала, х, у - координаты точки М (образа), х', у' - координаты точки М' (прообраза точки М). Координаты (х', у') являются постоянными и задаются при исходном положении символа.
Чтобы найти новые координаты одной точки символа надо выполнить 8 арифметических операций (2.4) и 3 операции (2.3) - 11 операций (предполагаем, что тригонометрические функции sin?, cos?, arctg? не вычисляются, а считываются из таблиц).
Для размера матрицы n x n, равному 10 х 10, т.е. 100-точечного символа это потребует 1100 операций. При быстродействии видеоконтроллера 40 МГц на воспроизведение такого символа на очередном шаге будет затрачено около 3 миллисекунд: 2,5 х 10-6 х 1,1 х 103 = 3 мс, что недопустимо в подавляющем числе применений. Это объясняется тем, что размер матрицы достигает, как правило, больших размеров, поворот осуществляется пошагово, чтобы обеспечить плавность, последовательно на несколько углов, составляющих этот поворот, а количество символов может составлять десяток и более.
Очевидно, что затраты памяти на хранение одного символа существенно сокращаются тогда, когда он определен только точками, задающими его конфигурацию. Причем число матриц с "записанными" его конфигурациями должно быть столько, сколько предусмотрено угловых шагов при отображении его вращения. При этом, в соответствии с курсом, надо успевать рассчитывать, согласно (2.1) на каждом шаге новые координаты центра матрицы.
2.1.2. Векторный метод.
Нами предложен метод, когда описание символа представляется не всеми точками в векторной форме, а лишь точками, составляющими его контур. Контур S образуют прямые, проведенные через эти точки. Тогда на каждом шаге новые координаты угловых точек вычисляются аналогично (2.4), а контур образуется построением отрезков прямых. Быстродействие и размер необходимых вычислительных ресурсов зависят от сложности конфигурации конкретного символа, которая определяется числом исключаемых из построения внутренних точек, составляющих контур S. При этом можно получить значительную экономию вычислительных ресурсов, необходимых для реализации поворота символов и их поступательного перемещения. Описанный метод имеет ограничения, связанные с тем, что для представления и анализа динамических сцен в реальном времени требуется отображать сложные символы, содержащие различные атрибуты, которые необходимы для однозначного распознавания их оператором, см. Приложение А. Кроме того, время построения таких символов составляет значительную величину.
2.1.3. Инварианты преобразования вращения.