Генератор изображений Советский патент 1989 года по МПК G06T11/00 

сл го

1чЭ 1Ч5

4

W

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

Цель изобретения - повышение инфор мативности формируемого кадра изображения .

На фиг. 1 приведена структурная схема генератора; на фиг. 2 - способ задания ребер для обработки клеточным процессором на фиг. 3 - подделение клетки в клеточном процессоре; на фиг, 4 - схема селектора пересеченных клеток| на фиг, 5 - схема селектора суммы клеток| на фиг.6 - схема селектора внутренних клеток; на 1ФИГ. 7 - пример многоугольника, формирование позиционных кодов для которого приведено в таблице; на фиг. 8 - схема блока памяти масок клеточного процессора; на фиг. 9 - схема узла приоритета.

Генератор (фиг. 1) содержит геометрический процессор 1 и процессор формирования элементов изображения, со- стоящий из конвейерного вычислителя, вьтолненного на клеточных процессорах 2, каждьй из которых содержит входной регистр 3, сумматор 4, делитель на два 5, блок 6 памяти позиционных кодов, выход 7 кода внутренних клеток, селектор 8 пересеченных клеток, селектор 9 внутренних клеток, выход 10 кода суммы клеток, селектор 11 суммы клеток, выход 12 кода маски, блок 13 памяти масок, выход 14 селектора 9, выход 15 селектора 8 и узел 16 приоритета. Клеточные процессоры 2 соединены через блоки буферной памяти, выполненные в виде двух узлов 17 пере- ключаемой памяти, В клеточном процессоре -2 обозначены также выход 18 узла 16, выходы 19 и 20 первой и второй групп входного регистра 3, выход 21 селектора 11, В конвейерном вычислителе обозначены вход 22 и выходы 23 адреса клетки и признака готовно- сти маски клеточного процессора 2. . Кроме того, каждый клеточный процессор 2, начиная с второго, содержит узел 24 формирования признака готов ности маски. Процессор формирования элементов изображения содержит также фильтр 25, смеситель 26, вьшислитель

,

д20 25

д .

50

55

27 цвета и блок 28 буферной памяти элементов изображения. Генератор подключается через цифроаналоговые преобразователи 29 к отображающему устройству 30.

Селектор 8 пересеченных клеток (фиг. 4) содержит блок 31 элементов И-НЕ и регистр 32.

Селектор П суммы клеток (фиг. 5) содержит блок 33 элементов И-НЕ, регистр 34 и ключ 35.

Селектор 9 внутренних клеток (фиг. 6) содержит блок 36 элементов П-НЕ, регистр 37 и ключ 38.

Блок 13 памяти масок (фиг. 8) содержит узел 39 памяти типа первым вошел, первым вышел, дешифратор 40, регистр 41, мультиплексор 42, узел 43 оперативной памяти, узел 44 управления записью, управляемьй инвертор 45 и регистр 46.

Узел 16 приоритета (фиг. 9) содержит группы 47 и 48 регистров и схему 49 приоритета.

Генератор работает следующим образом,

В генераторе в качестве элемента разложения при преобразовании многоугольников в элемент ; изображения (ЭЙ) телевизионного раствора используется уменьшающаяся от уровня к уровню в четыре раза клетка, первона- чальньш размер которой равен площади экрана отображающего устройства 30. Количество уровней подделения определяется используемым форматом разложения в растр и точностью фильтрации изображения. Фильтрация используется дпя устранения дефектов, возникающих при квантовании изображений, и заключается в подделении ЭЙ растра на более мелкие части с последующим вычислением площади, занимаемой многоугольником в каждом ЭЙ. На каждом уровне происходит определение занятых многоугольником клеток и сравнение их с маской, сформированной от предыдущих многоугольников. Если клетка, в которой лежит текущий многоугольник оказалась полностью занята предыдущими многоугольниками, то она на следующий уровень обрс1ботки не поступает. Таким образом, процесс подделения осуществляется в виде квартернарного дерева и реализован с помощью конв ейера однотипных клеточных процессоров. Число процессоров определяется коли- ч еством уровней подделения и конечным

размером клетки, до которой осуществляется разложение многоугольника. Из геометрического процессора 1 поступают многоугольники в прямом приоритетном порядке, что позволяет сократить время обработки закрытых частей многоугольников за счет использования многоуровневого- маскирования. Общепринятое описание многоугольников в виде набора вершин в данном устройстве заменено описанием набора линий, проходящих через ребр многоугольника и заданных их пересечениями с краями экрана: X , 2 верхней и нижней границами экрана в случае, когда ребра вертикальные (наклон больше 45°); Y

г

2С левой в случае

и правой границами экрана

горизонтальных ребер (с наклоном мен ше 45°) (фиг о 2), Такое задание позволяет сократить по сравнению с прототипом число выполняемых операций дпя определения элементов, занятых

0 писи

мировать маски клеток на каждом уровне обработки, а не только за счет накопления с нижних уровней. Это ускоряет процесс маскирования и сокращает время для коррекции масок с нижнего уровня на верхний. Из блока 6 на селекторы пересеченных клеток 8, внутренних клеток 9 и суммы (пе0 ресеченных и внутренних) клеток I1 поступают сформированные позиционные коды с выходов 7 и 10. На выходе селектора 8 образуется позиционный код пересеченных клеток дпя каждого ребра

5 путем логического вычитания позиционного кода внутренних клеток, кода суммы внутренних и пересеченных клеток и позиционного кода масок из блока 13 памяти масок на блоке 31 и зарезультата в регистр 32, В селекторах П и 9 по мере поступления ребер, относящихся к обрабатьшаемому многоугольнику, происходит накопление соответствующих позиционных кодов, а

Изобретение относится к вычислительной технике и предназначено для цифрового синтеза и воспроизведения изображений в реальном времени. Цель изобретения - повышение информативности формируемого кадра изображения. Генератор содержит геометрический процессор 1 и конвейерный вычислитель из однотипных клеточных процессоров 2, осуществляющих преобразование ребер многоугольников в элементы изображения телевизионного растра. Для преобразования в растр в устройстве использовано рекурсивное подделение экрана на клетки с помощью клеточного процессора 2, содержащего сумматор 4, делитель на два 5, селекторы пересеченных 8, внутренних 9, суммы 11 клеток, узел 16 приоритета и блок 13 памяти масок. Вычисление занятых многоугольников клеток по точкам пересечения его ребра с краями и серединой клетки, определение ребер, принадлежащих к клетке, с помощью узла 16, маскирование многоугольников в каждом из процессоров 2 конвейера позволяет сократить время на обработку каждого многоугольника при достаточной простоте используемого устройства. 9 ил.

30

обрабатьшаемым многоугольником, и ис- 25 в узлах 17 - координат трех пересече- ключить из обработки , связанные с образованием невьшуклых многоуголь- НИКОЕ Невыпуклости при задании многоугольников вершинами могут образо- вьшаться за счет неточности вычислений и округления координат, поступающих из геометрического процессора I,

На вход первого клеточного процессора 2 поступают ребра многоугольников, заданные пересечениями с краями экрана. Ребра с соответствующими признаками записьшаются во входные регистры 3 клеточного процессора 2. Заг тем вычисляется середина ребра по

ч

формулам:

35

40

НИИ ребер до тех пор, пока не поступит признак последнего ребра. При поступлении признака последнего ребра, на ключи 35 и 38 происходит маскирование многоугольника позиционным кодом, хранящимся в блоке 13 памяти масок, дпя обрабатьшаемых на текущем уровне клеток, который образовался от обработки в данных клетках предыдутцих многоугольников. Коды незамаск ирован- ных клеток записьшаются по входу разрядов данных в уз ел 17. На фиг. 7 приведен пример четьфехугольника, пересекающего клетку, в таблице показано формирование позиционного ко- да пересеченных каждым ребром этого четырехугольника клеток, а также получение окончательного позиционного кода внутренних клеток и внутренних и пересеченных клеток.

Х| + Х;

или Y

п

. Yi Y

Эти вычисления осуществляют сумматор 4 и делитель на два 5, реализованньй монтажным сдвигом. Все клетки, образованные при обработке многоугольников, делятся на внутренние, полностью лежащие внутри многоугольника, и пересеченные одним или несколькими ребрами. По трем координатам (фиг. 3) X ,, Х или Y,, Y ,, Y определя М

ется позиционный код внутренних и

суммы пересеченных и внутренних клеток с помощью блока 6 памяти позиционных кодов. Деление клеток на внутренние и пересеченные позволяет фор0

5 в узлах 17 - координат трех пересече-

5

0

5

0

5

НИИ ребер до тех пор, пока не поступит признак последнего ребра. При поступлении признака последнего ребра, на ключи 35 и 38 происходит маскирование многоугольника позиционным кодом, хранящимся в блоке 13 памяти масок, дпя обрабатьшаемых на текущем уровне клеток, который образовался от обработки в данных клетках предыдутцих многоугольников. Коды незамаск ирован- ных клеток записьшаются по входу разрядов данных в уз ел 17. На фиг. 7 приведен пример четьфехугольника, пересекающего клетку, в таблице показано формирование позиционного ко- да пересеченных каждым ребром этого четырехугольника клеток, а также получение окончательного позиционного кода внутренних клеток и внутренних и пересеченных клеток.

Блок 13 памяти масок (фиг. 8) включает собственно узел 43 оперативной памяти (масок текущего уровняД а также узел 39 памяти типа первым вошел, первым вьшшл, который служит дпя приема заполненной маски с последующего уровня. Адрес в память масок поступает как с текущего уровня обработки клетки (на фиг. 1 не показаны), так и со следующего уровня. Запись в узел 39 происходит при наличии сигнала переполнения памяти масок с узла 24. Чтение узла 39 разрешено, если он не

пуст или в данный момент не вьтолня- ется цикл чтение - модификация ,- запись узла 43 со стороны клеточного процессора 2 текущего уровня. При чтении узла 39 младшие биты адреса поступают на дешифратор 40, формирующий четьфехразрядньй позиционный код маски текущего уровня с единственным установленным битом, соответ- ствующим полностью заполненной маске последующего уровня. Этот код и оставшиеся разряды адреса маски записываются в регистр 41. Если узел 39 пуст, то ни одного бита маски стар- шего уровня сформировано не будет. Условием записи информап ии в регистр 41 спужкт окончание цикла чтение - модификация - запись- узла 43, Выход регистра 41 подключен к нулевому входу мультиплексора 42s на другой вход которого поступает адрес клетки текущего уровня. Этот мультиплексор подключает входы адреса узла 43 и входы узла 44 управления записью либо к выходу регистра 41, либо к адресу, поступающему из клеточного процессора 2 текущего уровня. Выход узла -43 подключен к управляемому инверт ору 45, наличие которого позволяет не произво дить очистку узла 43 в начале очередного кадра,, Управление инвертором 45 осуществляется с узла 44 управления записью. Выход управляемого инвертора 45 подключен к входу регистра 46, который предназначен дня хранения считанного из узла 43 четырехразрядного кода маски текущего уровня и выдачи его клеточному процессору 2. Емкость четырех- разрядного узла 43 увеличивается от уровня к уровню в четыре раза.

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

ток поступает на последовательные входы даннЕ,гх: групц регистров 47 и 48, каждая из которых разделена на четыре группы, соответствующие каждой из четырех образованных клеток - О, 1, 2,

д

0

5

3, Параллельные выходы регистров 47 и 48 групп соединены с входом схемы 49 приоритета и подключаются к ней в зависимости от обрабатьтаемой в дан- ньй момент клетки. В то время, как часть регистров группы 47 используется для записи позиционных кодов ребер, другая часть регистров группы 48 используется для чтения из узлов 17. С каждым новым ребром записывается позиционньй код пересечения в эти регистры. На выход е каждого из регистров, соответствующего одной из четырех выбранных клеток, образуется по- зшщонньй код всех ребер, пересекших эту клетку. Те ребра, которые пересекали данную выбранную клетку, отметятся нулями, а которые не пересекали - единицами. Этот код поступает на вход схемы 49, на выходе 8 которой формируется адрес первого ребра, пересекающего выбранную клетку, и поступает на узел 17, Если нет больше ребер, которые пересекали эту клетку, выбирается следующая, пока не выберутся все клетки и ребра, пересекающие их. Выбор незамаскированных клеток, обрабатываемых, на данном уровне, осуществляется при- оритетной схемой (не.показана), аналогичной схеме 49, а также рядом схем (не показаны), осуществляющих управление работой клеточного процессора 2.

После выборки последнего ребра в последней клетке данного уровня чтение данного узла 17 переключаемой памяти прекращается, и он переключается на запись нового многоугольника или нового фрагмента многоугольника, а .. другой узел 17 переклю-чается на чтение того, что было записано ранее. Информация с узла 17 поступает на вход следующего клеточного процессора 2 и обрабатьшается аналогичньЕМ образом на следующем уровне„ Маски, сформированные на 1-ШЖШ-1Х УРОВНЯХ; передаются на верхние вместе с их адреса- Mji через узел 24,

Последний клеточный процессор 2 в конвейерном вычи(шителе формирует описание ЭЙ, которое поступает на . фильтр 25. Координаты пересечения ребра с клеткой на выводе этого клеточного процессора 2 1гж& не использзгются, а выходной-инЛорма1даей является ЭЙ высокого разрешения с селектора 9 внутренних клеток. Количество элементов разложения, на которое подделяет- ся ЭЙ, зависит от требуемого качества

изображения. В cjry4ae использования подделения 2x2 последний клеточный процессор 2 может быть реализован точно так же, как остальные процессоры. Возможно использование более точного подцеления каждого ЭЙ, напригчер, 4x4 и точнее, что требует увеличения объема блока 6 памяти позиционных кодов и установления перед последним клеточным процессором 2 перекодировщика для согласования входного формата.

В фильтре 25 происходит вычисление площади, занимаемой многоугольниками

в каждом ЭН. Вычисленная площадь пода- з выход геометрического процессора соеется на смеситель 26, туда же поступает цвет данного пиксела, которьм вычисляется в вычислителе 27 цвета по коэффициентам уравнений для цвета данного многоугольника и координатам 20 ЭЙ, поступающих из конвейерного вычислителя. Вычислитель 27 цвета позволяет осуществить линейную интерполяцию цвета для создания округлых объектов, а тшсже вычислить туман в каждой точ- 25 ке изображения. В смесителе 26 происходит окончательное вычисление цвета ЭЙ для трех компонентов цвета с учетом занимаемой многоугольником площади в данном ЭЙ.30

Окончательньй цвет ЭЙ записывается в блок 28, представляющий память для трех компонент цвета всех ЭЙ кадра с сумматором на входе. Если ЭЙ занят текущим многоугольником не полностью, то значение цвета суммируется с цветом других многоугольников, лежащих в этом же ЭЙ. Одна часть блока 28 используется клеточными процессорами 2 для формирования изображения, а другая в это время считьюается синхронно с телевизионной разве рткой и через цифроаналоговые преобразователи 29 три компоненты цвета в аналоговом ви- .де подаются на отображающее устройство 30.

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

35

40

45

55

динен с входом процессора формирования элементов изображегшя, выход которого является Бьпгодом генератора, прргчем процессор формирования элементов изображения содержит блок буферной памяти элементов изображения, выход которого является выходом процессора формирования элементов изображения s смеситель, выход которого соединен с информационным входом блока буферной памяти элементов изображения, фильтр и вычислитель иззета, выходы которых соединены с первым и вторым входами смесителя соответственно, входы задания коэффициентов вычислителя цвета соединены с соответствующими разрядами выхода геометрического процессора, о тли чающийся тем, что, с целью повышения информативности формируемого кадра изображения, в процессор форкшрования элементов изображения введен конвейерньй вычислитель, разряды входа которого соединены с входами соответствующих разрядов процессора формирования элементов изображения, а первый и второй выходы - с входом фильтра и с входом координат элементов изображения вычислителя цвета соответственно, причем конвейерньй вычислитель содержит М клеточных процессоров и М-1 блоков буферной памяти, информационньй вход первого клеточного процессора является входом конвейерного вычислителя, выход а-го клеточного процессора (а l50 « M-l) соединен через а-й блок буферной памяти с информационным входом (а+1)-го клеточного процессора, первый и второй выходы -конвейерного вычислителя соединены с соответствующими выходами М-го клеточного процессора, выходы адреса клетки и признака готовности маски Ь-го клеточного процессора (Ь 25.,.М) подключены к одобрабатьгоаемых параллельно ЭЙ изменяется и число клеточных процессоров.

К генератор; псд -глючается ЭВМ универсального типа, осушествляющая управление работой всех узлов и используемая для подкачки баз данных и тестового контроля.

Формула изобретения

Генератор изображений, содержащий геометрический процесс ор и процессор формирования элементов изображе.ния.

20530

п

5

0

5

5

динен с входом процессора формирования элементов изображегшя, выход которого является Бьпгодом генератора, прргчем процессор формирования элементов изображения содержит блок буферной памяти элементов изображения, выход которого является выходом процессора формирования элементов изображения s смеситель, выход которого соединен с информационным входом блока буферной памяти элементов изображения, фильтр и вычислитель иззета, выходы которых соединены с первым и вторым входами смесителя соответственно, входы задания коэффициентов вычислителя цвета соединены с соответствующими разрядами выхода геометрического процессора, о тли чающийся тем, что, с целью повышения информативности формируемого кадра изображения, в процессор форкшрования элементов изображения введен конвейерньй вычислитель, разряды входа которого соединены с входами соответствующих разрядов процессора формирования элементов изображения, а первый и второй выходы - с входом фильтра и с входом координат элементов изображения вычислителя цвета соответственно, причем конвейерньй вычислитель содержит М клеточных процессоров и М-1 блоков буферной памяти, информационньй вход первого клеточного процессора является входом конвейерного вычислителя, выход а-го клеточного процессора (а l50 « M-l) соединен через а-й блок буферной памяти с информационным входом (а+1)-го клеточного процессора, первый и второй выходы -конвейерного вычислителя соединены с соответствующими выходами М-го клеточного процессора, выходы адреса клетки и признака готовности маски Ь-го клеточного процессора (Ь 25.,.М) подключены к одноименным входам (b-l)-ro клеточного процессора, причем каждьй из М клеточных процессоров содержит входной регистр, сумматор, делитель на два, блок памяти позиционньпс кодов, селе1с торы пересеченных и внутренних клеток и суммы клеток, узел приоритета и блок памяти масок, причем в каждом клеточном процессоре информационньй вход входного регистра является информационным входом клеточного процессора, разряды первой и второй групп выхода входного регистра соединены с соответствующими разрядами адресного входа блока памяти позиционных кодов, выхода клеточного процессора и соот ветственно с разрядами входов первого и второго слагаемых сут матора, разряды выхода которого соединены через делитель на два с соответствующими разрядами выхода клеточного процессора и адресйого входа блока памяти позиционных кодов, выход кода внутренних клеток которого соединены с первыми входами селекторов пересеченных и внутренних клеток, а выход кода суммы внутренних и пересеченных кле- |ток - с первым входом селектора суммы клеток и с вторым входом селектора

U

1110

1 1

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

признака готовности маски и адреса

клетки а-го клеточного процессора соединены с одноименными выходами (а+1)- го клеточного процессора, вход адреса клетки текущего уровня блока па0 -мяти масок каждого клеточного процессора соединен с разрядами адреса его информационного входа, а каждьй Ь-й клеточный процессор содержит узел формирования признака готовности маски,

5 выход признака готовности маски которого является одноименным.выходом Ь-го клеточного процессора, а входы соединены с выходш« И блока памяти ма- ,сок и селектора внутренних клеток.

0000

0001

11 10

вмм оамм

it w

л

n

йг

прижал mctfSHtto ffip&

10

л

J

f

Фаг 5

fug.3

Признак тсл(3негв ptfpa

#a/. 7

Aiffti клетки, т&кущёю уровне

Adpfc каетки ( уровни

Фа.ё

15

Фрщ.

«&Ф

7

15

Зрврр

J J.

Of

Lb

«

9

IS