Генератор изображений

Генератор изображений

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (51)4 G 06 F 15/62

ОПИСАНИЕ .ИЗОБРЕТЕНИЯ

К д ВТОРСИОМ,1/ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

t (21) 4449655/24-24 (22) 21.07.88 (46) 15.11.89. Бюл. Р 42 (71) Институт автоматики и электрометрии СО АН СССР (72) А, И. Богомяков, С. И. Вяткин, Б. С. Долговесов, Б ° С. Мазурок, А. Ф. Рожков, 10. Э..Тиссен и П. И. Унру (53) 681.325(088.8) (56) Патент США ? 4077062, кл. G 09 В 9/08, опублик. 1987..

Патент США 4570233, кл. 364/522, опублик. 1986, (54) ГЕНЕРАТОР ИЗОБРАЖЕНИЙ (57) Изобретение относится к вычислительной технике и предназначено для цифрового синтеза и воспроизведения изображений в реальном времени. Цель изобретения — повышение информативности формируемого кадра изображения. :Генератор содержит геометрический

„„Я0„„1522240 д1

2 процессор 1 и конвейерный вычислитель из . однотипных клеточных процессоров

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

4, делитель на два 5, селекторы пересеченных 8, внутренних 9, суммы 11 клеток, узел 16 приоритета и блок 13 памяти масок. Вычисление занятых многоугольником клеток по точкам пересечения его ребра с краями и серединой клетки, определение ребер, принадлежащих к клетке, с помощью узла 16, маскирование многоугольников в каждом из процессоров 2 конвейера позволяет сократить время на обработку каждого многоугольника при достаточной простоте используемого устройства, 9 ил °

1522240!

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

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

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

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

2, каждый из которых содержит входной регистр 3, сумматор 4, делитель на два 5 блок 6 памяти позиционных коЭ

35 дов, выход 7 кода внутренних клеток, селектор 8 пересеченных клеток, селектор 9 внутренних клеток, выход 10 кода суммы клеток, селектор 11 суммы клеток, выход 12 кода маски, блок 13 памяти масок, выход 14 селектора 9, выход 15 селектора 8 и узел 16 приоритета. Клеточные процессоры 2 соединены через блоки буферной памяти, выполненные в виде двух узлов 17 переключаемой памяти. В клеточном процессоре 2 обозначены также выход 18 узла 16, выходы 19 и 20 первой и второй групп входного регистра 3, выход

21 селектора 11, В конвейерном вьгчи50 слителе обозначены вход 22 и выходы

23 адреса клетки и признака готовно- . сти маски клеточного процессора 2.

Кроме того, каждый клеточный процессор 2, начиная с второго, содержит узел 24 формирования признака готов55 ности маски, Процессор формирования элементов изображения содержит также фильтр 25, сме ситель 26, вычислитель

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

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

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

Селектор 9 внутренних клеток (фиг. 6) содержит блок 36 элементов

И-НЕ, регистр 37 и ключ 38.

Блок 13 памяти масок (фиг. 81 содержит узел 39 памяти типа "первым вошел, первым вышел", дешифратор 40, регистр 41 мультиплексор 42, узел

43 оперативной памяти, узел 44 ;-правления записью, управляемый инвертор

45 и регистр 46.

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

49 приоритета.

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

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

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

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

Число процессоров определяется количеством уровней подделения и конечным

5 15222 размером клетки, до которой осуществляется разложение многоугольника.

Из геометрического процессора 1 поступают многоугольники в прямом приоритетном порядке, что позволяет

S сократить время обработки закрытых частей многоугольников за счет использования многоуровневого маскирования. Общепринятое описание многоугольников в виде набора вершин в данном устройстве заменено описанием набора линий, проходящих через ребра многоугольника и заданных их пересечениями с краями экрана: Х, Х вЂ” с 15

1% верхней и нижней границами экрана в случае, когда ребра вертикальные (наклон больше 45 ); Y1,,Y — с левой и правой границами экрана в случае горизонтальных ребер (с наклоном мень-20 ше 45 ) (фиг. 2). Такое задание позволяет сократить по сравнению с прототипом число выполняемых операций для определения элементов, занятых обрабатываемым многоугольником, и ис- 25 ключить из обработки случаи, связанные с образованием невыпуклых многоуголь- ников. Невыпуклости при задании многоугольников вершинами могут образовываться за счет неточности вычислений и округления координат, поступающих из геометрического процессора 1.

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

Х1+ Х2 1 2

Х

12 2 — или Y

2 !

Эти вычисления осуществляют сумматор

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

Х1, Х,, Х или Y,, Y Yz определяется позиционный код внутренних и суммы пересеченных и внутренних клеток с помощью блока б памяти позиционных кодов. Деление клеток на внутренние и пересеченные позволяет фор40 мировать маски клеток на каждом уров— не обработки, а не только за счет накопления с нижних уровней. Эта ус1 коряет процесс маскирования и сакра" щает время для ксррекции масок с нижнего уровня на верхний. Из блока

6 на селекторы пересеченных клеток

8, внутренних клеток 9 и суммы (пересеченных и внутренних) клеток 11 поступают сформированные позиционные коды с выходов 7 и 10. На выходе селектора 8 образуется позиционный код пересеченных клеток для каждого ребра путем логического вычитания позиционного кода внутренних клеток, кода суммы внутренних и пересеченных клеток и позиционного кода масок из блока 13 памяти масок на блоке 31 и записи результата в регистр 32. В селекторах 11 и 9 па мере поступления ребер, относящихся к обрабатываемому многоугольнику, происходит накопление соответствующих позиционных кодов, а в узлах 17 — координат трех пересечений ребер до тех пор, пака не поступит признак последнего ребра. При поступлении признака последнего ребра.на ключи 35 и 38 происходит маскирование многоугольника позиционным кодом, хранящимся в блоке 13 памяти масок, для обрабатываемых на текущем уровне клеток, который образовался от обработки в данных клетках предыдущих многоугольников. Коды незамась ированных клеток записываются по входу разрядов данных в узел 17. На фиг. 7 приведен пример четырехугольника, пересекающего клетку, в таблице показана формирование позиционного кода пересеченных каждым ребром этого четырехугольника клеток, а также получение окончательного позиционного кода внутренних клеток и суммы внутренних и пересеченных клеток.

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

1522240 пуст или в данный момент не выполняе т ся цикл ч те ние — мадифик аци я — з апись узла 43 со стороны клеточного процессора 2 текущего уровня. При

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

Условием записи информации в регистр

41 служит окончание цикла чтение— модификация — запись. узла 43. Выход регистра 41 подключен к нулевому вхо- 20 ду мультиплексора 42, на другой вход которого поступает адрес клетки текущего уровня. Этот мультиплексор подключает входы адреса узла 43 и входы узла 44 управления записью либо к 25 выходу регистра 41, либо к адресу, поступающему из клеточного процессора 2 текущего уровня. Выход узла 43 подключен к управляемому инвертору 45, наличие которого позволяет не проиэво-30 дить очистку узла 43 в начале очеред. ного кадра. Управление инвертором 45 осуществляется с узла 44 управления записью. Выход управляемого инвертора

45 подключен к входу регистра 46, 35 который предназначен для хране ния считанного из узла 43 че тырехразрядного кода .маски текущего уровня и выцачи его клеточ-! ному процессору 2. Емкость четырех,разрядного узла 43 увеличивается от уровня к уровню в четыре раза.

Для повышения производительности процессоров предусмотрена параллельная запись в узлы 17 информации для четырех клеток, а также чтение только тех ребер, которые пересекают рассматриваемую (одну из четырех )клетку в случае, если нет на нее маски и если эта клетка не лежит вне многоугольни1 50 ка. Эту функцию выполняет узел 16 приоритета, который ведет эффективный поиск нужных ребер в узлах 17, Позиционный код пересеченных ребром кле— ток поступает на последовательные вхо55 ды данных групп регистров 47 и 48, каждая из которых разделена на четыре группы, соответствующие каждой из четырех образованных клеток — О, 1, 2, 3. Параллельные выходы регистров 47 и

48 групп соединены с входом схемы 49 приоритета и подключаются к ней в зависимости от обрабатываемой в данный момент клетки. В то время, как часть регистров группы 47 используется для записи позиционных кодов ребер, другая часть регистров группы 48 используется для чтения из узлов 17.

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

После выборки последнего ребра в последней клетке данного уровня чтение данного узла 17 переключаемой памяти прекращается, и он переключается на запись нового многоугольника или нового фрагмента многоугольника, а другой узел 17 переключается на чтение того, что было записано ранее.

Информация с узла 17 поступает на вход следующего клеточного процессора

2 и обрабатизается аналогичньм образом на следующем уровне. Маски, сформированные на жених уровнях, передаются на верхние вместе с их адресами через узел 24.

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

9 15222 изображения. В случае использования подделения 2х2 последний клеточный процессор 2 может быть реализован точно так же, как остальные процессоры.

Возможно использование более точнога подцеления каждого ЗИ, например, 4х4 и точнее, чта требует увеличения объема блока 6 памяти позиционных кодов и установления перед последним клеточ-10 ным процессором 2 перекодировщика для согласования входного формата.

В фильтре 25 происходит вычисление площади, занимаемой многоугольниками в каждом ЭИ. Вычисленная площадь пода15 ется на смеситель 26, туда же поступает цвет данного пиксела, который вычисляется в вычислителе 27 цвета по коэффициентам уравнений для цвета данного многоугольника и координатам 20

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

ЭИ для трех компонентов цвета с учетом занимаемой многоугольником площади в данном ЭИ. 30

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

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

Объединение этих узлов осуществляется через селектор перед цифроаналоговыми преобразователями. Таким образом осуществляется параллельная обработка нескольких ЭИ. В зависимости ат числа

40 1О обрабатываемых параллельно ЭИ изменяется и число клеточных процессоров.

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

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

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

N клеточных процессоров и M-1 блоков буферной памяти, информационный вход первого клеточного процессора является входам конвейерного вычислителя, выход а-га клеточного процессора (а — 1,...„M-1) соединен через а-й блок буферной памяти с информационным входам (а+!) -го клеточного процессора, первый и второй выходы конвейерного вычислителя соединены е соответствующими выходами М-га клеточного процессора, выходы адреса клетки и признака готовности маски Ь вЂ клеточного процессора (Ъ = 2,...М) подключены к од(Номер ребра

Позиционный код внутренних клеток с выхода 7

По з ицио нный код внутренних клеток на выходе 14

Позиционный кад суммы внутренних и п ере с еч енных клеток с выхода 10

Па з ицио нный код суммы клеток на выходе 21

Позиционный код пересеченных KJIe— ток на выходе 15

1 1110

1111 ОООО

0001

1110

2 1101

1111 ОООО 1101

3 01 I I

ОООО

I 0l 1 0Ill

0111 1111 0000 1011 0111

11 152224 ноименным входам (Ъ-1)-го клеточного процессора, причем каждый из М клеточных процессоров содержит входной регистр, сумматор, делитель на. два, блок памяти позиционных кодов, селек5 торы пересеченных и внутренних клеток и суммы клеток, узел приоритета и блок памяти масок, причем в каждом клеточном процессоре информационный вход входного регистра является инфор-мационным входам клеточного процессора, разряды первой и второй групп выхода входного регистра соединены с ,соответствующими разрядами адресного входа блока памяти позиционных кодов, выхода клеточного процессора и соответственно с разрядами входов первого и второго слагаемых сумматора, разряды выхода которого соединены через >9 делитель на два с соответствующими разрядами выхода клеточного процессора и адресного входа блока памяти позиционных кодов, выход кода внутренних клеток которого соединены с пер- 25 выми входами селекторов пересеченных и внутренних клеток, а выход каца суммы внутренних и пересеченных клеток - с первым входом селектора сум мы клеток и с вторым входом селектора

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

Ь"го клеточного процессора, а входы соединены с выходами блока памяти ма,сок и селектора внутренних клеток.!

Рри нак юесле3мне вбра фц иак оосайнке pedpe

1522240

Составитель А. Ушаков

Техред п.Сердюкова Корректор M.càìáoðñêàÿ

Редактор М, Петрова аказ 6966/48 Тираж 668 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, iK — 35, Раушская наб., д. 4/5 производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101