Устройство для параллельной обработки трехмерных сцен

Устройство для параллельной обработки трехмерных сцен

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и предназначено для обработки трехмерных сцен и является усовершенствованием изобретения по авт.св. N 1456965. Цель изобретения - сокращение времени выполнения операции изменения масштаба обрабатываемых объектов и поворота на углы, кратные 90°, и расширение области применения за счет увеличения диапазона углов поворота и разрешающей способности обрабатываемых сцен. В устройстве каждому элементу обрабатываемой сцены соответствует свой процессор, выполняющий логическую обработку бинарных трехмерных изображений. Взаимодействие между процессорами осуществляется по непосредственным связям. Введение блоков сжатия и растяжения, увеличение количества элементов И в блоке элементов И процессора, соответствующее подключение блоков поворота к трехмерной матрице процессоров и введение блока памяти позволяют достичь упомянутых положительных эффектов. 3 з.п. ф-лы, 4 ил.

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

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

РЕСПУБЛИН (51) 5 G 06 F 15/16, 15/62

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

H A ВТОРСНОМЪ СВИДЕТЕЛЬСТВУ

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

НО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ 1РИ ГКНТ СССР! (61) 1456965 (21) 4365371/24-24 (22) 15.01 ° 33 (415) 07.12.90.Бюл. 45 (71) Ижевский механический институт (72) В.А.Бимаков (53) 681,325 (038.8) (56) Авторское свиде-ельство CCCP

¹ 1456965, кл. G 06 F 15/16, 1986. (54) УСТРОЙСТВО ДЛЯ ПАРАЛЛЕЛЬНОЙ

ОБРАБОТЕИ ТРЕХ!»ЕРНЫХ СЦЕН (57) Изобретение относится к вычислительной технике, предназначено для обработки трехмерных сцен и является усовершенствованием изобретения по авт.сз. !! - 145, 965. Цель изобретения — сокращение времени выполнения операции изменения масштаба абрабаИзобретение относится к аычислитсльнай техник», предназначено для обработки трехмерных сцен, причем каждому элементу сцены соответствует свой обрабатывающий процессор, а в,.1имодействпе между процессорами осуществляется па í посредственным связям между ними, что обуславливает. в.,»сакое быстраде1,ствие, обуславливающее ваэмажные применения для иного технического решения, и является усовершенств )ганием устройства по ,.»вт. св. 1» 456965.

Цель изобретения — сокращение времени выполие..шя опера»1,1и изменения масштаба оГ>рабатываем»1х объектов и о ис 1»врата на углы, кр.»тные 90, и расширение области;1римен:.ния з а счет

SU„„1612307 А 2 тываемых объектов и поворота на углы, о кратные 90, и расширение области применения за счет увеличения диапа— зона углов поворота и разрешающей способности обрабатываемых сцен. 8 устройстве каждому элементу абраба— тываемой сцены соответствует свой процессор, выполняющий логическую обработку бинарных трехмерных изображений. Взаимодействие между процессорами осуществляется по непосредственным связям. Введение блоков сжатия и растяжения, увеличение количества элементов И в блоке элементов И процессора, соответствующее подключению блоков поворот к трехмерной матрице процессоров, и введение блока памяти позволяют достичь упомянутых положительных эффектов. 3 з.п. ф-лы, 4 ил. увеличения диапазона углов поворота и разрешающей способности обрабатываемых сцен.

На фиг.. и 2 представлен пример реализации устройства параллельной обработки трехмерных сцен; на фиг.3 конструкция блока поворота и схемы, согласно которым в устройстве аппаратно реализуется операция поворота содержимого последнего слоя А Х А X ) матрицы вокруг центра этого слоя на о угол, не кратный 90; на фиг. 4 — кан— струкция блоков сжатия и растяжения и схемы, согласно которым в устройстве аппаратно реализуется операция сжатия содер;;имаго последнего слоя

А Х А Х матрицы на коэффициент K относительно прямой, проходящей через! 612307 ц(.нтр квадрата A X А и параллельной

:тороне этого квадрата. (Устройство (фиг.l и 2) состоит из трехмерной матрицы 1 Ь. Х А Х А процессоров, блока 2 управления, блоков 3 поворота, блоков 4 сжа.гия, блоков 5 растяжения, блока 6 памяти, первый и последний слои матрицы 1 имеют соответственно входы 7 и выходы 8. )1 свою очередь матрица 1 состоит из A процессорон 9. Каждый процессор 9 включает в себя первый регистр 10 операнда, вторзй регистр 11 рнер,.:нда, узел 12 памяти, элемент

ИЛИ 13, блок элементов И, включающий н себя элементы И 14 — 24 и элемент

ИЛИ-НЕ 25. Блок управления содержит узел 26 определения объема, узел 27 оперативной памяти, программно-адре- 20 суемые регистры 28 — 30, управляющий проЦессор 31, который состоит иэ регистра 32 команды, мультиплексора 33 адреса, арифметико-логического узла

34, дешифратора 35, элементов И 36 и 25

ИЛИ 37 выбора блоков 3 поворота, элементов ИЛИ 38 и 39 выбора блоков сжатия, элементов И 40 и ИЛИ 41 выбора блоков 5 растяжения, узла 42 микропрограммного управления. Узел

42 микропрограммного управления содержит генератор 43 синхронизирующих импульсов, дешифратор 44 команды, генератор 45 выработки адреса микро ..лова, регист): 46 адреса микрослона, узел 47 памяти микрослов, регистр

48 микрослова, дешифраторы 49 .;ода микрооперации„ дешифратор 50 кода режима ввода-вывода, элементы И 51

57. В состав блока 2 управления вхо- 40 дит программно-адресуемый регистр

58. Блоки поворота 3, сжатия 4 и растяжения 5 (ф(г. 3 и 4) могут быть выполнены одинаковыми по конструкции и содержат элементы ИЛИ 59 и элементы И 60.

Описание работы устройства целесообразно начать с определения ряца используемых терминов. и-мерной сценой формата Р " назовем некотос . (()) рое семейство S = 1 Е <) Г I> (где

Iz = 1,2,3,..., тпн) точечных множеств

ll-мерного эвклидово го простр:шстна К", удонлетноряющее выражению () Е,„ЕБ) t(i; () ) h (!1(() (Е,„) )(0)А (Е = ) "1 Е )), где I)((") (E ) — и мерная ме » и-мерного множества Е,„(по-. нятие и — мерной меры (1((Е ) япля(1 (N) етс,, ".тестненным обобш..нием понятий: длины p(l) (Е () ) отрезка Е (1) для R; площади p()(Е ()) плоской фигуры Š— для К; объема !1)((E ), Ф,) (31 трехмерной фигуры Е(Э) — для R . Множества Е б 8 назовем т-м объектом

1)1 и-мерной сцены $. Сцену S ГЕ б I формата F(, для которой одновремен" но выполняются выражения: F(U е „и (7 у jF 15) 1 (1 ф 1с)ф(Е1!)е1

= ф), назовем m -нарным (или m — уровненым) и-мерйым изображением формата Е(, Каждое m -нарное изображение формата F может быть представлено m — значной числовой функцией л ())1

Ф, принимающей н каждой точке à (= F такое значение (!)(а), когда справед.пиным оказывается высказывание: (МЕ„,eS) (а (; Е ) ЯЬ6Г("1) (((Ф(а)

= Ф(Ь)) =>(Ь Е „)) h((())(a)f Ф(Ь))=Ф (Ь ((„,))), Разобьем пространство R" (1) П на классы точечных множеств Р CR (где 1ELl L - =1,2,3 ... о()), для которых справедливы выражения: (l1cL) (Ya,bD )((а,()ьЯ(1, (I) где 0 (а Ь) — расстояние между точкаФ (n) ми а и Ь множества Р<, Е постоянная, ((()().) (()(")ф Ф о); (2) (Д,)еь) ((i ф j) (Р l1p

=P)) . (3)

Р() ) (4) .

E<(((l

Иножестна Р (:R одновременно удовлетворяющие всем перечисленным требованиям, назовем и-мерными пиксе,,()))» )1, лами Р -пиксельного разбиения P. а F — постоянной этого разбиения.

Точечное множество U р, сос ав (n)

Р 4)( ленное из конечного множества пикселов Р, назовем ? -дискретным объек(и) (n) том (f. 61.). Р" -дискретной моделью

)()1 р) множества E 6 R назовем P -дискретный объект Е = U P составлен (и) ный иэ всех пикселон Р (где 1Е L<, L<(. L), для которых выполняется (Ц16?.!,) (р()))(ЕДР ) /(Ь (P(1)3 8(1$, где постоянная (043()ъ1). Вычислительную процедуру по формированию

P (")-дискретной модели f)(Е)СЕ множества f(Е) из множества Г, где

/1.

f (Е) — образ множества Е С R" при и у р (ll) отображении f Å- х (Е), назовем ?в дискретизирующим отображением f,,моделирующим отображение f: Е -Ppf(Е).

1, если Р, СЕ, где z (= 1.1, ())}

1 (})1 — (nl (n}

О, если Р ° СЕ F U P

\ 1 GL }9

1., С1.; (}}1

Е»» F3E;

1 (})}

Ф((Р. ) (nl P !

, если Р,, С f (Е ) р

О, если РЕ Сf (Е) (n} p ()}l

Ф (Р ) = (1, если tU (f(E)QP())/{(l (Р ) Ур (()! (n1 Ы

Ф (Р() ) ® ())} („1 (}}!

О, еслиI(l (Й(Е)()РЕ)/Р4 (Р(I) с О Е -. (6) 5 161

Особенностью обработки трехмерных сцен в предлагаемом устройстве является то, что все обрабатываемые трехмерные объекты представлены в (э} устройстве их P --дискретными моделя(Ъ} ми, роль пикселов Ре выполняют куби.ки 1. Х 1 Х 1, а выполнение геометрических преобразований пространства

R, к числу которых относятся преобразования поворота, перекоса, сжатия и растяжения„ заменено в устрой(М стве выполнением P -дискретизирующих отображений (модулирующих соответствующие геометрические преобразования с заданной степенью точности)

Р -дискретных объектов. Рассмотрим, (Я} х

Построение Р -дискретной модели образа f (E) прецполагает определение меры {}((1(Р х () ) (Е));для каждого

Р(" сцены S.. Из равенства Е

= Ц Р," следует f(E) 0 f(P;), где LpCL, отсюда P((}f(E)

- Р, " (1(,О f(PI" )) =,U (Р,(" ОЕ(Р,,))

}с() 6 (s

Так „(° ) (° () ()) ())}

Ф)), а f — биективное отображенйе

f: R - К, то f (Ð(" ) ((f (Р(")) = ф, }

Таким образом из (1) и свойства аддитивности меры вытекает

Выражения (5) и (6) полностью определяют зависимость значений Ф от значений Ф на области определения Г = Р } ) f (7())}) Так как f (Е

Э

< и (Е}-) то Е (Е) { «} = ф (где Г = (1

= Г $P) поэтому значения Ф (Р < ), соответствующие пикселам Р(1СF, рав-. (()} няются О. Р -дискретизирующее отображение допускает возможность одновременного выполнения над всеми пикселями Р сцены Б выражении (}}} . (5) и (6) . простейший способ осуществления такого распараллеливания, 2307 общий принцип построения P -дискрет())) ной модели f ((E) множества f (E) (где

Е = U Р " — некоторый произвольный е

Р(" -дискретный объект; f — биек- и н тивное отображение f: R -+К ) из объекта Е, входящего в состав бинарного п-мерного изображения S} неп}

10 которого формата F . Результатом

1 такого построения должно стать бинар. ное и-мерное изображение S формата

Р,, содержашее объект fP (E). Поскольку. S и S являются бинарными и15 мерными изображениями, они могут быть представлены следующими двухзначными функциями: где 1 Q ? С1 s (и} ()1 р (Й

FZ — — Ц Р; Р (Е) F (f (E) °

Еа(. ! _#_(х"() ((х)) - p "Ь ;)() (Р,)).

30 )SLY

Используя введенную ФУнкцию @, (Р, ) i можно записать

}) (Р (Г(х)) -, {Х (Р(()х{Р, ) х

Ф (P )j (5) где Gl C L<, причем Qi g L ) { (Р(" р ((„f (P(") Ф {! $A(igG1)g. Из определения

Р -дискретной модели множества f(E) следует ( непосредственно вытекающий из выражений (5) и (б), состоит в примене, нии для каждого пиксела Р { { пары (n} многовходовой аналоговой сумматор— пороговый элемент (вход 1-ro порого-. вого элемента соединен с выходом

1-го аналогового сумматора). Каждый

1-й сумматор служит для реализации выражения (5), каждый 1-й пороговый элемент — для реализации выражения (6). Варьируя значением, можно, упростить данный способ айпаратной реализации P -дискретизируюшего (Ю»

1612307 отображения путем замены аналоговьгх элементов на простейшие цифровые элементы. Действителрно„ если для выбранного значения 5) высказывание ($, EL)(yt (P(Af (Р ) ) )))li <) EP J истинно, то для формирования значения Ф (P() нет необходимости вычис6 лять 5) а достаточно реализовать булевую функцию (7)

9 (»1 где Ф, (Г; ) и Ф (Р ) выполняют уже роль булевых переменных (1 — истинно, 0 — ложно), В зависимости от того, какое из значений Ф„(Р ) (О (»l или 1) пикселов Р k-ro n-мерного (»!

Ю» бинарного изобр .ения образует P дискретную модель объекта Е, можно говорить о позитивном или негативном представлениг ооьекта Е в изображении. Переход от позитивного представления объекта Е к ега негативному представлению равнозначен замене функции Ф„(Р »1) на функцию

Ф„{Р " : (n1

0, если P С Е

Р " СЕ

Выражение (7) в случае негативного представления объектов Е и

f" (Е) имеет вид

Ф(Р ) = Л Ф,(Р, ). (8) Ega

Зависимость (8) является ма-. ематической основой для реализации в и) предлагаемом устройстве Р -дискретизирующих отображений, моделирующих перенос, поворот, сжатие P -дискрет э) ных объектов, Применительно к P (»)

1) дискретизирующим отображениям f,, моделирующим перенос, повороты, сжатия сбъекта Е, негативное представление отличается от позитивного тем, что образующие при выполнении этих отобг)ажений "пустые" области

= Г(" )),fо(Е) в случае негагивного представления f (E) заполняются еди,1

50 ницами. В устройстве содержимое регистров 10 гли 11 одноименного операнда всех процессоров 9 матрицы 1 или слов узла 12 памяти, имеющих одинаковый адрес, образует трехмерное поле значений Ф„(Р() некоторого k-ro би(Я 55 нарного тре;;мерного изображения фор- мата F . Формат F представляет со)э) бой куо А Х А :: А и со ст он т иэ А

35 (э1 трехмерных пикселов P(— кубиков

1 Х 1 Х 1 (фиг.!), где 1 = 1,2,...,А

Каждому кубику Р э куба F взаимно(й однозначно соответствует процессор

9 матрицы 1, Особенностью модели(э1 рования Р -дискретизирующим отображением Q)r (Q) поворота P -дискретг (эЪ ного объекта Q Q F на произвольный (Ъ) угол является невозможность сохранения в Р(дискретном объекте f г(Я) числа кубиков Р Cf () и их относи(э)

Р тельного положения, характерных для кубиков Р gQ. Важным исключением из (М этого правила является повсг)от

Q)f (Q) на углы, кратные 90, вокруг взаимно-ортогональных осей Ох, Оу, 0z проходящих через центр куба F ®) и параллельных его ребрам (фиг.1).

Необходимым требованием к устройству обработки трехмерных сцен является требование обеспечения возможности поворота объектов сцен на большой диапазон пространственньгх углов.Данная проблема решается в предлагаемом устройстве путем частичной депараллелизации процедуры поворота, при этом моделирование поворота P Läèñêðåòíî"o объекта на заданный угол осуществляется при помощи последовательного выполнения следующих аппаратно-реализованных дискретиэирующих отображений: отображений, моделирующих поворот произвольного бинарного иэображения формата F 1 вокруг осей Ох, Оу, 02 на углы, кра ные 90 (90, 180, 270О); отображений, моделирующих поворот произвольных плоских (г бинарных изображений формата Fq (где „ — октант квадрата А Х A) на углы из диапазона 0 4()(+45О,при этом октант Ftl состоит из квадратов (г1

I Х 1 (ïèêñåëîâ РЯ, входящих в состав квадрата F (размером А Х А); поворот вокруг центра F>I на углы, о. кр атные 90; симметрии от но сит ел ьно взаимно-ортогональньгх прямых проходящих через цен р квадрата F u параллельных сторонам Ф ; преобразованиях, выражающихся через композицию двух первых видов преобразова" ний; не отображаются друг на друга, Между пикселами Р сР (Ж = 1,2,... и (э) . „А ) и пикселами Р CF(э1 последнего { о тно сительно направления В) слоя А Х А Х 1 матрицы 1 существует взаимно-однозначное соответствие. ю

Способ аппаратной реализации Р -дискретиэирующего отображения Рз, + f (PQ

Ол д Вэ

1612307

{где f °: R 2 Rz — поворот плоскос(К ти на угол М, вокруг центра Р )) в блоках 3 предлагаемого устройства не отличается ат способа реализации

Р - 2 (Р )) в блоках поворота прототиЖ М ж па и заключается в использовании многовходовых элементов И. В та же время, если в прототипе число многовходавых элементов И, используемых при моделировании поворота плоского фрагмента изображения на один единственный угол, соответствует числу р) -(2) „(Z) пикселов Р -"Р«1 «где ."«, — квадрант г ),то в предлагаемом устройстве 15 (2) число многовхадавых элементов И,использует(х для тех же целей,соот@) (2) ветствует числу пикселов Р> С Р т. е. в предлагаемом устройстве это число примерно в два раза меньше.

Кроме того, часть указанных многовходовых элементов И в предлагаемом устройстве используется для моделирова- . ния поворота бинарного изображения. формата F.I не на один угол, а на не- 25 (2.)

«/8 сколько углов поворота. Сущность данного приема состоит в следующем.

Из-за погрешности дискретизации каждый P дискретный объект f (Е) явФ ляется Р -дискретной моделью образа

f {Е) не одного преобразования f

1«,"-> Р", а целого множества П (fP,Е) преобразований f, образы Й(Е) котоpbrx имеют одну ту же Р -дискретную (1 моцель f (Е) . Среци преобразований

Я«: fl(f ",Å) есть однотипные преобразования (павороты вокруг одной точки, сжатия относительно одной прямой и т.п.). Отсюда образу f(Р 2 пиксела

-P {2)

P (. F(можно дать в соответствие мно(2)

Ж 40 жество 11(2 (f, Рф преобразований поворо". à fg . R 2R вокруг центра Р

2 углы поворота в которых отличаются, а образы К (Pô имеют одну и ту же

-дискретную модель fg (P ), Поэтому ф), мо)22елирование поворота Рф- и (Рф

Р -дискретизирующим отображением (г

Р - Х (Р р осуществляется с точностью (2) (р (21, да УГЛОВ()2 {)(ж

Nna мсек с

Пусть задано конечное множее гво

К =(Ol;) (ие диапааона 0 — 45 I б значений углов„поворот на которые (2) бинарного изображения формата Р«2< предполагается реализовать в блоках

3 устройства. Пусть F.> — участок (2) (2.

Р«{8, образованный времй пикселами

Р ) СРД, расстояние r (P } которых до центра F удовлетворяет неравен-! ству Г(Р 2"- r» где r> — постоянная величина, P 1-дискретизирующее

«2 отображение Fö() - f< (F«8} вызывает (2) P (2) отображение Р -т ба (ф . Точность моделирования поворота произвольного (2« (2.)

P -дискретного .объекта Q C F y на угол {)а (т.е. диапазон {)(„„i ((6ФМ2,„ не превышает точности моделирования (2) (2) поворота пиксела Р С F> располо (2) женного на расстоянии т Р ) мии макс (т.е.(„2,,« 0 «) = Х д„дкс }, где удкс М) ",,««q«(g« 0i . (2);, урке, ««их, Поскольку с уменьшением значения

Мин мс(кс г (к, диапазон g — ф становйтся )2«ире, возможно сущестзавание

Й) таких участков Р, в которых диапазон Ф вЂ («(перекрывает не один, чин мс«к- а нес1 алько углов («(И поворота (3 образуя множество И > С М перекрываемых углов.

3 случае выполнения этога условия мнаговхадовые элементы И блоков 3; используемые при моделировании поворота бинарного изображения формата (7 )

Р « (« (для реализации поворота участ(2) к а Р т этого изображения) н а угол с( (1!, могут быть использованы и при моделировании поворотов изображения

2. р 92 формата Р« 8. на другие (ш{11 -)- 1) углы «)((="И. вокруг центра Р(2) (m/!4 ) число углов множества 1. ) .Разобъем

Ф (г) (2 \ r (2 (2 актан- Р«/8 на зо ь r У = Рт" 1 т- %где (2) (z)

Р, — названные участки Р п

Т „(D

К удовлетворяющие условию тп(Лг)

= щ(11" ) — 1. Каждый j-é блок 3 предлагаемого устройства, управляемый собственным сигналам погорота (СП3), включает в себя только те многовхадовые элементы И, катар, е соответствуют пикселам Р Cf,(Ð >, (2) Р (2)

Ф

Ж с У где (){, Е 1". . Отсюда параллельный поворот бинарного изображения формата

F на угол М O М вокруг центра Р

МЯ моделируется в устройстве путем одновременной подачи управляющих сигналов СП на те блоки 3, чьп саответP,ë(2) ствующие образы f<(F>) при объединении дают (с допустимой степенью точности) образ fP(F(2)), a «{8

На фиг.3 показано, как абъединеР е((2). ние 1 (Р ) i-га блока 3, f (F ) j — гр блока 3 <у(шJ 1 га алака 3 (Р{«{р

Ъ-r o блока 3 дает образ повернутого октанта Р,1 (2)

Достал)2ством предлагаемого устройства является возможность осуществления с его помощью высокоскоростного изменения масштаба P -дискрет(р) ных объектов н а большой диапазон мас161280

12 штабных коэффициентов ° Значительное расширение диапазона масштабных коэффициентов достигнуто в устройстве благодаря частичной депараллелиза5 ции процедуры изменения масштаба, (Ч когдса изменение масштаба P -дискретного объекта на заданный коэффициент

k осуществляется при помощи последовательного выполнения P -дискретизи(а1 рующих отображений, выполняемых над (21 прямоугольными участками F бинарного иэображения формата Р() и моделирующих преобразования сжатия (растяж(ния) плоскости к прямой PR 15 проходящей через центр квадрата

F и параллельной стороне Р . Мной (г) жество F „C F представляет в об(v (е) щем случае прямоугольник, две параллельные стороны которого перпендикулярны прямой РР и имеют длину х F/2 {или А), две другие стороны параллельны PR, причем как минимум одна из них лежит на стороне квадрата F 1. Длины сторон F „ име- 25 (21 ют целые значения. Возможные варианты F (сжатые в k раз), отличающие(х) ся степенью распараллеливания операции сжатия, а также объемом используемого оборудования, приведены на З() фиге4 в„г,д. При.сжатии плоскости в раз к прямой РК (т.е. при выполнении преобразования f ". R R )

2" образ i <(a) точки а Е R и сама точка а лежат н общем перпендикуляре к прямой PR принадлежат одной и той же полуплоскости с грани(,ай

PR, расстояние Р (i к(а), PR) (от точки f к (а) до PR) и Р (а, PR) {от точки а до PR) связ аны з ависимостью:

P(f(((а), РК) = k P(a, РК). Если

0 1 — растяжением. Час гньй случаи F показан на фиг.4е и (2) пр ед. т авля ет собой прямоугольник раз- 4g мером А/2 Х 1 (где А — четное),состоящий из А/2 квадратиков-пикселов (г) 0.1. О)

Р СР; образ f„(F< > показан на фиг,4з; образ f < (F+) — на фиг.4и. р)

Аппаратная реалчз ация г — дискретизируищего отображения Рм-) Й (Р 1, моде(11 P .-Фр к лирующего сжатие бинарного изображеи) ния формата Р... состоит в применении многовходовых элементов ИЛИ 59,входы которых соединяются с входами 8 уст55 ройства в соответствии с выражением (8) (или в соответствии с (7) ), При малых значениях k (примерно в пределах Ос k - 0,3) использование цифро-. вых элементов 59 для моделирования сжатия F> в k раз требует значир) тельного снижения порогового значения ((® (аналога ()g в (6)), что приводит к существенному снижению точности моделирования преобразования сжатия.

Для предотвращения этого при малых значениях k целесообразна замена m-входовых элементов 59 на пары

m-входовой аналоговый сумматор— пороговый элемент, реализующие непосредственно выражения (S) и (6) и моделирующие сжатие с большей точностью. В этом случае выход порогового элемента соединяется с входом элемента И 60. Образу f„(Р ) пиксела Р С F по аналогии с Л g(f<,P®)

Р1 -,(gl " р -Ю. можно да..ь в соответствие множество

Ц (r,Ð у преобразований сжатия у- р (ее

iк . R - К к прямой PR коэффициенты k сжатия в которых отличаются, а образы К(,(Р ) имеют одну и ту же

121 л й,.

P -дискретную модель f (P Поэтому моделирование сжатия Р )- х (Рф осуществляется с точностью до коэффици.„мян „макс ентов K < 1 К, . Пусть задано конечное множество D = (К; % (не днапаэона 0 — 1) значений коэффициентов сжатия к PR. (21

1 Пусть F — участок прямоугольника

F образованный всеми пикселами

Р (-F» расстояние G(P ) которых до р1 (n прямой PR удовлетворяет неравенству

С (Р у - Су,, где G — постоянная ве(z личина Р -дискретизирующее отображение Гм -ъ Г„(Р„,) вьпывает отображение (21 p (z)

Г),- х к (Р„ . Точность моделирования (г1 .-р Ф поеобразования сжатия произвольного

Й (Ц

P. -дискретного объекта Н СР на коэффициент k к прямой PR (т.е. диапазон Км"„д6К Кма,к„.) не превышает точности моделирования сжатия к прямой PR пиксела Р(C F, расположен(М Р) ного на расстоянии. С(Рф = Сщ (т. е. мин макс N

Кмис- К g (, — Кмакс) ° Пусть

G> < G+ + I . Поскольку с уменьшеми((ма (с

Кием значения GW диапазон К вЂ” К становится шире, возможно существова(2) ние таких участков F„„, в которых диапазон К вЂ” К перекрывает не мин макс аУ

1 од(н, а несколько коэффициентов kCD сжатия к прямой PR, образуя множество О,, „ С D перекрываемых коэффициентов. 3 случае выполнения этого условия элементы 59 и 60 блоков 4, используемые при сжатии бинарного (D изображения формата F ® (для сжатия

1612307

50 участка F,„ýòoãî изображения) на (21 коэффициент k е Г„,, могут быть иск пользоваьы и при моделировании сжатия из об р ажения формат а Р на дру(И к гие ш(Э, )-1 коэффициенты k E 0> к прямой PR (m(D ) — исло коэффициенк тов множества и ). Разобьем F1(на к O (21 (21 (z> (n (г зоны Р = Р (Г ",, где Г Г,((— названнь1е участки прямоугольника

Г„„, удовлетворяющие условию m(D<) к

= m(D ) — 1, Каждый j-й блок 4 предлагаемого устройства, управляегый собс гв енным сигналом сжатия (CCj), включает в себя только те элементы 59 и 60 которые соответствуют пикселам Р С Е„(Г ), где МЭ .(г.) .- Р (З к

Отсюда параллельпое сжатче бинарного изображения формата F,- на коэффи(г1 циент k (; D к прямой PR моделируется в устройстве путем одновременной подачи управляющих сигналов СС на те

Р л(,) блоки 4, чьи образы i (F, ) при объединении дают образ f (РМВ) . Аналогичным образом в блоках 5 устройства 25 реализуется растяжение бинарного (21 изображения формата Р на коэффиМ циент kp l î" прямой PR, Роль управляющих сигналов выполняют в этом случае сигналы р-"стяжения (CP(, поступающие на управляющие входы элементов 60 блоков 5. Конструкция и работа блока 2 управления предлагаемого устройства в основном совпадает с конструкцией и работой блока уграв35 ленин прототипа. Однако команда

ПВЗ Аl в предлагаемом устройстве имеет иной смысл: Сформировать сцену Al из сцены Al путем сдвига исходного содержимого этой сцены на шаг вдоль Б с поворотом октанта последнего слоя А Х А Х 1 сцены вокруг Ох на угол, номер которого хранится в регистре 30, и записью результата поворота в первый слой результирующей сцены", Кроме того, в систему команд устройства дополнительно введена команда OK Аl "Сформировать сцену A) из сцены Аl путем сдвига исходного содержимого этой сцены на шаг вдоль Б со сжатием прямоугольного участка А Х 1 последнего слоя

А Х А Х 1 сцены к прямой, проходящей через центр квадрата А Х А этого слоя, и параллельной стороне квадрата на коэффициент, номер которого хранится в регистре 30, и записью результата сжатия в первый слой результирующей сцены1. В управляющем процессоре 31 реализуется принцип микропрограммного управления. Согласно этого принципа высшим уровнем внутреннего языка управления являетется язык команд программы. Управление на этом уровне осуществляется последовательным извлечением команд из узла 27 памяти и их выполнением, Каждой команде соответствует своя микропрограмма — последовательность микрокоманд, выполнение которых приводит к выполнению операции, заданной в команде.

Регистр 32 команды предназначен для хранения выполняемой команды. В процессе ее выполнения сигналы с выходов разрядов адресной части регистра 32 группами, соответствующими отдельным адресам Al, А2 сцен-операндов, через выходы АЛП мультиплексора 33 подключаются к адресным входам узлов 12 памяти процессоров 9.

Управление мультиплексором 33 производится разрядом РУАВ регистра 48 микрослова. Если этот разряд равен

"О", то к адресным входам узлов 12 подключается код А1, если "1" — подключается код А2.

Узел 42 микропрограммного управления служит для генерации управляющих сигналов. Для каждого состояния управляющего процессора 31 существует отдельное микрослово. Узел 47 памяти хранит эти микрослова, содержащие копии управляющих сигналов (сигналов микрооперации), требующихся для каждого состояния управляющего процессора 31. С целью выработки последовательности управляющих сигналов содержимое регистра 46 адреса микрослова с помощью генератора 45 изменяется по каждому импульсу Сl, вырабатываемому генератором 43. Последовательность микрослов образует микропрограмму. 1(икрослово содержит управляющее поле, разряды которого используются для генерации сигналов требуемых микроопераций, а также поле следующего микроадреса и .поле кода микроветвления ° Часть управляющего поля микрослова образует поле управления матрицей 1, в это поле входят разряд управления адресными входами матрицы (РУАБ), разряды кода микрооперации (КИО), разряд разрешения записи в узел 12 (ЗЛП), разряд управления считыванием содержимого узла 12 памяти в регистры 10 (СР8), разряд управле16

1612307 ния считыванием содержимого узла 12 в регистры 11 (СР9), три разряда кода режима ввода-вывода (РВВ), разряд запуска операции определения объема

{фБ). Содержимое разрядов РВВ регист" ра 48 соответствует следующим режимам работы устройства: 001 — "Поворот на угол, некратный 90 "; 010—

"ввод информации в матрицу 1 из регИстра 28"; 011 — "Вывод информации ив матрицы 1 в регистр 29"; 100—

"Сжатие/растяжение .

Для повышения скорости выполнения поворотов содержимого матрицы

1 на углы, кратные 90, вокруг осей

Ох, Оу, Oz, увеличения скорости выполнения межпроцессорных передач вдоль осей Ох, Оу, Oz блок элементов

И каждого процессора 9 может дополнительно содержать двухвходовые элементы И 18 — 24, предназначенные для реализации поворота содержимого матрицы на углы 180 и 270о вокруг Ох, 25

I80 и 270 вокруг Оу, 90, 180 и 270

Вокруг Oz соответственно. Управляющие входы этих элементов И соединены

С соответствующими выходами дешифра-! гора 49 кода микроопераций.Информа- 30

1 ионные входы соединяются с выхода.N ми процессора 9, чьи кубики Р 1 при повороте на соответствующий угол, о кратный 90 вокруг одной из трех названных осей отображаются на кубиOI ки Г, в процессорах 9 которых находятся указанные входы. В случае построения матрицы 1 из типовых интегральных модулей, каждый из которых содержит внутри себя 24 процессора 4

9, образующих относительно поворотов на углы, кратные 90, вокруг Ох, Оу, ф

Oz замкнутую систему, возможно многократное повышение скорости обработки сцен без существенного понижения надежности и габаритов устройства (поскольку все ортогонально-кольцевые межпроцессорные связи располагались бы внутри модуля), При включении в состав процессоров 9 элементов

И 18 - 24 поле KNO регистра 48 содержит четыре разряда, содержимое которых соответствует следующим микрооперациям и командам (включаемых в этом случае в систему команд устрой55 ства) ". 1) 0000 — "01 (1 02", ИНЕ Аl, А2; 2) 0001 — "Поворот на 90 вокруг

Рх", ПВI Аl, AZ- 3) 0010 — "Поворот на 90 вокруг Оу",i ПВ2 А1э А2;

4) 0011 — "Сдвиг на шаг вдоль 3",СДВ

А1 А2; 5) 0100 — "Поворот на 180О вокруг Ох", ПВ4 AI,A2; 6) 0101 — "Поворот на 270 вокруг Ох",, ПВ5 Аl,А2;

7) 0110 — "Поворот на 180 вокруг

Oy", ПВ6 АI,AZ; 8) 0111 — "Поворот на 270 вокруг Оу", ПВ7 Al A2

9) 1000 — "Поворот на. 90 вокруг Oz"

ПВ8 Al А2; 10) 1001 — "Поворот на !

80 вокруг Oz", ПВ9 Аl, А2;

11) 1010 — "Поворот на 270 вокруг

Oz" ПВIО Аl, А2.

В устройстве имеется возможность обработки m -нарных (где ш 2) и дискретных йзображений формата (где п 3),отличающихся высоким разрешением. Обработка таких изображений осуществляется в устройстве трех" мерными бинарными фрагментами (формата F ), обрабатываемыми в устройстве с предельной стененью параллелизации, последовательно фрагмент за фрагментом, функцию хранения фрагментов ш -нарных изображений может выл полнять в этом случае память на узлах

12, Однако максимально достижимьп объем этои памяти сильно ограничен из-за небольших размеров кристалла типового модуля матрицы 1, поэтому устройство может дополнительно содержать блок 6 памяти (фиг. 1), связанный с матрицей 1 посредством двух маО 2 гистралеи ввода-вывода по А проводных связей (7 или 8) каждая. При наличии в составе устройства блока

6 в блок 2 управления дополнительно вводится программно-адресуемый регистр 58, в регистр 48 вводятся разряды ЗП (запись в память 6) и .ЧП (чтение памяти 6), система команд устройства дополняется командаьи:

BBbIB AI — "Записать содержимое последнего (относительно В) слоя

А Х А Х 1 сцены Al в память 6 по адресу, хранящемуся в регистре 58";

ВВВ Аl " "Записать бинарное изображение формата F (А Х А), хранящееся в памяти 6 по адресу, код которого расположен в регистре 58, в первый (относительно В) .слой Л Х А Х 1 сцены с адресом Al .

Рассмотрим выполнение каждой из введенных команд. При этом будем считать, что объекты сцен-операндов

А1, А2 представлены в негативном виде.

Команда ПВЗ Al. Иикрослово этой команды содержит: РУАВ = О, СР8 = 1, !

612307

KN0 = 0011, ЗЛП = i PBB = 001. При.; выполнении микрокаманды по импульсу

Ci на адресных входах узлов 12 установится код А), будут подготовлены элементы 17, 52 и 53, а также элемен (B. ты И 36, чьи образы Е (Р при объединении дают f<(F, ) (g - угол, Р -(г) номер которого расположен в регнсгре

30), будут подготовлены двухвходо- fO вые элементы И выбранных блоков 3.

С приходам С2 производится запись содержимого Al в регистры 10, при этом информация с выходов 8 поступа ет на многавходавые элементы И выб- !5 ранных блоков 3 и через двухвходовые элементы И выбранных блоков 3 поступает на входы 7. В момент прихода СЗ содержимое регистров 10 со сдвигом на шаг записывается в узел 20

l2 памяти по адресу Ai, в первый слой Л Х А Х 1 сцены Ai записывается изображение повернутого октанта (21

F последнего слоя А Х. А Х ) предыН8 дущего содержимого Al Далее осу- ществляется переход к микропрограмме извлечения следующей команды прог-. раммы. Поворот всего квадрата Г( осуществляется программно за восемь этапов (соатветственно числу октан- 30 тов Р),, входящих в F ),, (2) (2) !

Команда СЖ Лl . !)икрослово этой команды содержит: РУАВ = О, СР8 = 1, KN0 - =0011, ЗЛП = 1, PBB = 100. При выполнении микракаманды по импульсу

Cl на адресных входах узлов )2 установится код Al будут подготовлены элементы 17, 52 и 53 и элементы р "ФЛ

38 (или 40), чьи образы f„(F+r при объединении дают „(, (где k — - ка,р ю эффициент, номер которого хранится

Ф в регистре 30; F — крайний верхнии

l2l прямоугольник А Х 1 квадрата F .), будут подготовлены элементы И 60 4 . выбранных блоков 4 (или 5). С приходом С2 производится запись содержимого Al в регистры 10, при этом информация с выходов 8 поступает на элементы 59 выбранных блоков 4 (или

5) и через элементы 60 этих блоков поступает на входы 7. В момент прихода CÇ содержимое регистров 10 со сдвигом на шаг записывается в узлы

12 по адресу Al, в первый слой

А Х А Х 1 сцены А! записывается сжа55 (z) тое изображение прямоугольника Г„ .

Сжатие (растяжение) всей сцены

А Х А Х А осуществляется программно с использованием допалнительньгх (рабочих) сцен и применением команд

ИНЕ Аl, А2 и СДБ Ai, А2.

Команда ББЫВ Аl, 1)икрослово этой команды содержит: РУАБ = О, СР8 = 1, ЗЛП = 1, KNO = 001), ЗП = 1, ЧП = О.

При выполнении микрокоманды по импульсу С! на адресных входах узлов

12 установится код Л), будут подготовлены элементы 17,52, 53 и 55,. С приходом С2 производится запись содержимого Al в регистры iO при этом информация с выходов 8 поступает на входы данных блока 6. В момент при;ада CÇ содержимое регистров 10 со сдвигQM на шаг записывается в узел

12 по адресу Ai, а сигнал с выхода элемента 55 инициирует в памяти 6 операцию Запись", Команда ВВВ Лl. 1)икраслова этой команды содержит: РУАВ = О, СР8

1, ЗЛП = 1, КМО = 0011, ЗП = О, ЧП вЂ” — i. Перед выполнением команды на выходных регистрах памяти 6 находится информация, извлеченная иэ памяти 6 па адресу, хранящемуся в регистре 58, однако связь выходов этих регистров с входами 7 блокирована.

Блокировка может быть осуществлена при помощи А ключей И, управляемых триггером, который сбрасывается С! а устанавливается СЧП (ключи и триг гер включаются в этом случае в состав блока 6), При выполнении микрокоманды по импульсу С) на адресных входах узлов 12 установится кад Лl, будут подготовлены элементы 17,52, 53 и 56. С приходом С2 производится запись содержимого Al в регистры 10 и ссуществляется разблокирование связей выходных регистров памяти 6 с входами 7 матрицы. В момент прихода

C3 содержимое регистров 10 со сдвигом на шаг записывается в узел 12 по адресу Al а в первый слой

Л Х А Х 1 сцены Аl записывается информация, извлеченная из памяти 6. С приходом следующего импульса Cl производится блокирование выходов памяти 6. Команда ПБ4 Аl, А2. Микропрограмма этой команды включает микрослова. 1) — РУАБ = О, CP8=1; 2)

РУЛВ = 1, КИО = 0100, ЗЛП = 1. Б результате выполнения первого микрослова содержимое A) располагается в регистрах 10. Па Сl в регистр микрослава вызывается второе микро— слово микропрограммы, С приходам СЗ

19 !

612307 производится запись содержимого регистров 10 в память 12 через подготовленные элементы И 18 с поворотом на 180 вокруг Ох. Аналогичным о ,образом выполняются и другие команды вида ПЗ Н А1,А2 (отличающиеся кодом

КМО), Повороты на углы ф = + Д(; + о

+ 1 90 выполняются программно. Сжатие

P -дискретных изображений формата Р ф) (2) к прямой РК на коэффициенты K = K, К выполняется программно. Изменение масштаба P -дискретных изображений (з) формата F на коэффициент. k относиЮ тельно оси Ох (т.е, операция одновременного сжатия в k раз к плоскости

z0x и в k раз к плоскости уОх) выполняется программно. формула изобретения

1, Устройство для параллельной обработки трехмерных сцен по атв.св.: р 145б9 5, о т л и ч а ю щ e e с я тем, что, с целью сокращения времени выполнения операции изменения масштаба обрабатываемых объектов, в него введены блоки сжатия и блоки растяжения, информационные входы которых соединены с выходами первых регистров операнда соответствукипдх процессоров последнего относительно направления Б слоя трехмерной матрицы, а выходы соединены с входами блоков элементов И соответствующих процессоров первого относительно направления 3 слоя трехмерной матрицы, управляющие входы блоков сжатия и растяжения соединенъ с выходами второй группы блока управления.

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

5 соответствующих процессоров матрицы последнего относительно направления

«Ф

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

-Ф направления В слоя т