Устройство отсечения многоугольника для графического дисплея

Устройство отсечения многоугольника для графического дисплея

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано при построении устройств отображения графической информации на экране ЭЛТ и создании специализированных графических систем для тренажеров Устройство отсечения млогоугольника для графического дисплея содержит распределитель 1 сигналов, регистр2 вершин, блоки 3 4 первой и второй памяти, регистр 5 окна, блок регистров 6 общего назначения, триггер 7 флага видимости , триггер 8 конца операции, триггер 9 вершины, первый и второй счетчики 10. 11 адресов, блок 18 управления С целью повышения быстродействия устройства за счет определения видимости ребра сразу относительно всех границ окна вычисления одновременно координат точек пересечения ребра с окном и выполнения замыкания многоугольника в устройство введены дешифратор 12. блок 13 определения признаков , блок 14 формирования признаков границ, первый и второй блоки 15,16 вычисления пересечения, блок 17 анализа признаков , 10 ил. 1 табл. СО С

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

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

РЕСГ УВЛИК

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

,21) 4806001/24 (22) 26.03.90 (46) 23.11.92. Бюл. № 43 (71) Донецкий политехнический институт (72) О.А.Авксентьева и Е.А.Башков (56) Патент США N 3816726, кл. G 06 F 7/38, 1974.

Европейский патент ¹0132573,,кл. G 06

Е 15/20, 1985. (54) УСТРОЙСТВО ОТСЕЧЕНИЯ МНОГОУГОЛЬНИКА ДЛЯ ГРАФИЧЕСКОГО ДИСПЛЕЯ (57) Изобретение относится к вычислительной технике и может быть использовано при построении устройств отображения графической информации на экране ЭЛТ и создании специализированных графических систем для тренажеров. Устройство отсечения многоугольника для графического диспИзобретение относится к вычислительной технике и может быть использовано при построении устройств отображения графической информации на экране ЭЛТ и создании специализированных графических систем для тренажеров.

Известна система графического отсечения многоугольника (патент США ¹

3816726, 6 06 F 7/.г), 11.06.74), содержащий матричный умножитель, запоминающее устройство, шесть отсекателей соответственно для левой, правой, нижней, верхней. дальней и ближней плоскостей, каждый из которых включает в себя регистр координат начальной вершины ребра, регистр координат конечной вершины ребра, арифметиче„„. Ж„„17/7151 А 1 (я)э G 06 Е 15/20, G 06 G 1/08 лея содержит распределитель 1 сигналов, регистр 2 вершин, блоки 3,4 первой и второй памяти, регистр 5 окна, блок регистров 6 общего назначения. триггер 7 флага видимости, триггер 8 конца операции, триггер 9 вершины, первый и второй счетчики 10. 11 адресов. блок 18 управления. С целью повышения быстродействия устройства за счет определения видимости ребра сразу относительно всех границ окна, вычисления одновременно координат точек пересечения ребра с окном и выполнения замыкания многоугольника в устройство введены дешифратор 12. блок 13 определения признаков, блок 14 формирования признаков границ. первый и второй блоки 15,16 вычисления пересечения, блок 17 анализа признаков 10 ил 1 табл ское устройство, устройство анализа на видимость, триггер последней вершины, триггер видимости, регистр границы окна.

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

Наиболее близким техническим решением, выбранным в качестве прототипа, является отсекатель для дисплеев на электронно-лучевой трубке (европейский патент N 0132573, G 06 F 15/20, 13,02.85).

1777151 содержащий процессор преобразования координат, три регистра приращений по координатам X, Y, Z, арифметико-логическое устройство, регистр общего назначения, регистр окна, первый и второй блоки памяти, 5 регистр кодов знаков, регистр признаков отсечения, схема хранения начальных условий, схема формирования признаков отображения, схема характеристик вектора, первый — пятый регистр, цифровой дифференциальный анализатор, причем вход процессора преобразования координат подключен к входу устройства, а его выход к первому регистру, выход которого соединен с входами пятого регистра, регистр окна и арифметико-логического устройства. второй вход которого соединен с первым выходом регистра общего назначения, а первый выход подключен к входам регистра общего назначения, первого и второго блоков памяти, второго и третьего регистров, второй выход арифметика-логического устройства подключен ко входам регистра признаков отсечения, регистра кодов знаков, второй выход регистра общего назначения соединен с входами трех регистров приращений по X, Y, 2, выходы которых подключены соответственно к третьему, четвертому и пятому входам арифметикологического устройства, выход регистра признаков отсечения подключен к первому выходу устройства, выход регистра кодов знаков соединен со входом схемы анализа вершин, выход которой подключен соответственно ко входам схемы хранения начальных условий, схемы формирования признаков отображения и схемы характеристик вектора, выход схемы хранения начальных условий соединен со вторым входом схемы характеристик вектора, выход схемы формирования признаков отображения соединен со вторым выходом устройства, выходы с первого по четвертый схемы характеристик вектора соединены с выходами с третьего по шестой устройства, выходы третьего регистра, первого и второго блока памяти подключены к соответствующим входам четвертого регистра. а выходы второго и четвертого регистров подключены к шестому и седьмому входам арифметикологического устройства и соответствующим входам пятого регистра. выход которого подключен ко входу цифрового дифференциального анализатора. выход которого подключен к седьмому выходу устройства.

15 щего назначения, распределитель сигналов, регистр вершин, регистр окна, триггер

25

35

55

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

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

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

1777151

10

35

45

55 триггера вершинь!, к .ходам установки в ноль первого счетчи:d адреса и триггера конца операции, второй выход блока управления подключен к входу установки в ноль второго счетчика адреса, третий выход блока управления подключен к первому входу считывания/записи блока регистров общего назначения и к входу установки в ноль триггера вершины, выход которого подключен к шестому входу режима блока управления, четвертый и пятый выходы блока управления подклю IGHbl соответственно к счетным входам первого и второго счетчиков адреса, шестой выход блока управления подключен к входу установки в единицу триггера конца операции и к управляющему входу. триггера флага видимости, седьмой выход блока управления подключен ко входу чтения первого блока памяти и к второму входу считывания/записи блока регистров общего назначения. восьмой выход блока управления подключен к входу записи второго блока памяти, девятый и десятый выходы блока управления подключены соответственно к третьему и четвертому входам считывания/записи блока регистров общего назначения, информационный входустройства подкл Очен к информационному входу регистра окна, выходы с первого по четвертый которого подключены соответственно к информационным входам с первого по четвертый первой группы блока определения признаков, первый и второй выходы которого подключены к первому и второму информационным входам второго блока памяти, с третьего по десятый выходы блока определения признаков подключены сооТВ8ТсТВеННо к информационным входам с первого по восьмой блока анализа признаков, выходы с одиннадцатого по восемнадцатый блока определения признаков подключены соответственно к информационным входам с первого по восьмой блока формирования признаков границ и соответственно к информационным входам с девятого по шестнадцатый блока анализа признаков, девятнадцатый выход блока определения признаков подключен к первому информационному входу блока управления и к информационному входу триггера флага видимости, первый и второй выходы блока регистров общего назначения подключены соответственно к первому и второму информационным входам первого блока вычисления пересечения, третий и четвертый выходы блока регистров общего назначения подключены соответственно к третьему и четвертому информационным входам блока регистров общего назначения, соответственно к первому и второму информационным входам блска определения признако"; и соответственно к третьему и четвертому информационным входам первого блока вычисления пересечения. пятый и шестой выходы блока регистров общего назначения подключены соответственно к третьему и четвертому информационным входам блока определения признаков, соответственно к пятому и шестому информационным входам первого блока вычисления пересечения и соответственно к перво лу и второму информационным входам второго блока вычисления пересечения, седьмой и восьмой выходы блока регистров общего назначения подключены соответственно к пятому и шестому информационным входам блока определения признаков и соответственно к третьему и четвертому информационным входам второго блока вычисления пересечения, выход второго счетчика адреса подключен к первому информационному выходу устройства и к входу дешифратора, выход которого подключен к седьмому входу режима блока управления, с первого по четвертый выходы первого блока вычисления пересечения подключены соответственно ко второму информационному входу устройства управления, к семнадцатому информационному входу блока анализа признаков, к пятому и шестому информационным входам блока регистров обще о назначения. с первого по четвертый выходы второго блока вычисления пересечения пОдключены сооТ ветственно к третьему информационному входу блока управления, к восемнадцатому информационному входу блока анализа признаков, к седьмому и восьмому информационным входам блока регистров общего назначения, выходы с первого по двенадцатый блока формирования признаков границ подключены соответственно к информационным входам с четвертого по пятнадцатый блока управления. выходы с первого по двадцать первый блока анализа признаков подключены соответственно к. входам режима с восьмого по двадцать восьмой блока управления, пятый и шестой выход первого блока вычисления пересечения подключен соответственно к пятому и шестому информационным входам второго блока вычисления пересечения, выход второго блока памяти подключен к второму информационному выходу устройства, выходы флага видимости и конца операции которого подключены соответственно к выходам триггера флага видимости и триггера конца операции, первый выход блока управления подключен к первому управляющему входу блока определения признаков, третий выход блока управления подключен к второму

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

5 по шестьдесят второй блока управления подключены к управляющим входам с деся10

20

25 дельных ребер окном

35

50 рую выходную информационную шину 30, выход 31 конца операции и выход 32 флага видимости, перзый-четвертый управляющие входы 33-36 и первый-седьмой выходы

37-43 распределителя 1 сигналов, вход счи55

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

На фиг. 1 представлена блок-схема устройства отсечения многоугольника для графического дисплея; на фиг, 2 — блок-схема блока определения признаков; на фиг. 3— блок-схема блока формирования признаков границ; на фиг. 4 — блок-схемы первого и второго блоков вычисления пересечений; на фиг. 5 — блок-схема блока анализа признаков; на фиг, 6 -- блок-схема блока управления; на фиг. 7-10 — примеры для объяснения операции отсечения многоугольника и отУстройство (фиг. 1) содержит первый распределитель 1 сигналов (PC), регистр 2 вершин (РВ), блоки 3,4 первой и второй памяти (БП), регистр 5 окна, блок регистров 6 общего назначения (POH), триггер 7 флага видимости (ТФВ), триггер 8 конца операции (TKQ) и триггер 9 вершины (ТВ), первый и второй счетчики 10, 11 адресов, дешифратор 12, блок 13 определения признаков (БОП), блок 14 формирования признаков границ (БФПГ), первый блок 15 вычисления пересечения (БВП), второй блок 16 вычисления пересечения, блок 17 анализа признаков (БАП), блок управления 18 (БУ), входную управляющую шину 19, входную информационному шину 20, шину 21 окна, шину 22 блока регистров общего назначения, шину

23 признаков, шину 24 информации, шину

25 условий, шину 26, шину 27 управления, шину 28 распределителя сигналов, первую выходную информационную шину 29, втотывания/записи 44, информационный вход

45 и выход 46 регистра 2 вершин, информационный вход 47, вход записи 48, вход чтения 49, адресный вход 50 и выход 51 первого блока 3 памяти, информационный вход 52, вход чтения 53, вход записи 54, адресный

1777151

10

20

35

45

55 вход 55 ll «ыход 56 второ о блока 4 памяти. информационный вход 57. входы считывания/записи 58-61 и первыи-четвертый выходы 62-65 регистра 5 окна. первый-восьмой информационные входы 66-73. гервый-четвертый входы считывэния/записи 74-77 и первый-восьмой выходы 78-85 блока регистров 6 общего назначения, информационный и управляющий входы 86. 87 и выход 88 триггера 7 флага видимости, входы установки в ноль и единицу 89. 90 и выход 91 триггера 8 конца операции. входы установки B единицу и ноль 92. 93 и выход 94 триггера 9 вершины, входы установки в ноль и счетный

95, 96 и выход 97 первого счетчика 10 адреса, входы установки в ноль и счетный 98, 99 и выход 100 второго счетчика 11 адреса, вход 101 и выход 102 дешифратора 12, первый-тридцать четвертый управляющие входы

103-136, первый-четвертый инфо рмаци онн ые входы первой группы 137-140, первый-шестой информационные входы 141-146 и первый-девятнадцатый выходы 147-165 блока 13 определения признаков, первый-девятнадцатый управляющие входы 166-184, первыйвосьмой информационные входы 185-192 и первый-двенадцатый выходы 193-204 блока

14 формирования признаков границ, первый-седьмой управляющие .входы 205-211, первый-шестой информационные входы

212-217 и первый-шестой выходы 218-223 первого блока 15 вычисления пересечения, первый-десятый управляющие входы 224233. первый-шестой информационные входы 234-239 и первый-четвертый выходы

240-243 второго блока 16 вычисления пересечения, управляющий вход 244. первый-восемнадцатый информационные входы 245-262 и первый-двадцать первый выходы 263-283 блока 17 анализа признаков. первый-двадцать восьмой входы режима 285-312, первый-пятнадцатый информационные входы 284. 313-326 и первый-шестьдесят восьмой выходы 327394 блока управления 18.

Информационные входы 45,47,57 соответственно регистра 2 вершин. первого блока 3 памяти, регистра 5 окна подключены к информационному входу устройства 20, управляющие входы 33-36 распределителя 1 сигналов соединены с первым-четвертым разрядами пятиразрядной входной управляющей шины 19, а его выход 37 подключен к входу считывания/записи 44 регистра 2 вершин, выход 38 подключен к входу записи

48 первого блока 3 памяти и входу режима

308 БУ 18, выходы 39-42 подключены соответственно к входам 58-61 считывания/записи регистра 5 окна. выход 43 подключен ко входу считывания 53 BTop0f 0 блГ)ксз 4 il3мяти и к входу режима 307 BY 18. выход 46 регистра 2 вершин подключен к входу режима 309 bY 18, выход 97 первого счетчика 10 адреса соединен с адресным входом 50 блока 3 памяти. а его входы 95, 96 установки в ноль и счетный — с выходами 327, 386 БУ 18. выход 332 которого соединен со входом чтения 49 блока 3 памяти, выходы 62-65 регистра 5 окна соединены с информационными входами первой группы 137-140 блока 13 определения признаков, информационные входы 66, 67 блока регистров 6 общего назначения соединены с его выходами 80, 81, а также его информационные входы 68, 69 соединены с выходом 51 блока 3 памяти. соответственно с и-младшими и и-старшими разрядами, информационные входы 70-73 РОН 6 подключены соответственно к выходам 222. 223 блока 15 вычисления пересечения и выходам 242, 243 блока 16 вычисления пересечения, а входы считывания/записи 74-77 соединены соответственно с выходами 333, 332, 364, 370 БУ 18, выходы 78. 79 РОН 6 подключены соответственно к информационным входам 212, 213 БВП 15, а его выходы

80, 81 подключены cooTBBTGTBBHHQ ко входам 141. 142 БОП 13 и к информационным входам 214, 215 БВП 15, выходы 82, 83 Р0Н

6 подключены соответственно к информационным входам 143, 144 БОП 13, к информационным входам 216, 217 БВП 15 и к информационным входам 236, 237 БВП 16, а его выходы 84, 85 подключены соответствен но ко входам 145, 146 БОП 13 и к информационным входам 238, 239 БВП 16, выход

100 второго счетчика 11 адреса соединен с адресным входом 55 блока 4 памяти и входом 101 дешифратора 12. а его входы 98. 99 установки в ноль и счетный соединены с выходами 328. 387 БУ 18, выход 385 которого соединен с входом 54 чтения блока 4 памяти. выход 102 дешифратора 12 соединен с входом режима 31 БУ 18, управляющий вход БОП 13 соединен с выходом 327

БУ 18, управляющие входы 104-131 соедине-ны соответственно с выходами 333-360 БУ 18, управляющий вход 132 соединен с выходом

373 БУ 18, э управляющие входы 133-136 с выходами 391-394 БУ 18, выходы 147, 148

БОП 13 подключены к информационному входу 52 блока 4 памяти. ее выходы 149-164 подключены соответственно: к информационным входам 245-260 БАП 17, выходы 157164 подключены соответственно к информационным входам 185-192 БФПГ 14, а выход 165 соединен с информационным входом 284 БУ 18 и с информационным входом 86 триггера 7 флага видимости, управ1777151

35

50 ляющий вход 87 которого и вход 89 установки в единицу триггера 8 конца операции подключены к выходу 390 БУ 18, выход 327 которого соединен с входом 90 установки в ноль TKO 8 и входом 92 установки в единицу триггера 9 вершины, вход 93 установки s ноль которого подключен к выходу 333 BY

18. а выход 94 соединен с входом режима

306 BY 18, выходы 329, 336-339, 343-346, 375-384 которого соединены соответственно с управляющими входами 166-184 БФПГ

14, выходы 193-204 которого подключены ко входам 313-324 БУ 18, выходы 330, 349, 361, 362, 365, 371, 388 последнего соединены соответственно с управляющими входами

205-211 БВП 15, выходы 220, 221 которого соединены соответственно с информационным входом 325 БУ 18 и с информационным входом 261 БАП 17, а выходы 218, 219 подключены соответственно к информационным входам 234, 235 БВП 16, выходы 241.

240 которого соединены соответственно с информационным входом 262 БАП 17 и информационным входом 326 БУ 18, выходы

331, 36", 363, 372, 389, 366-369, 374 которого соединены соответственно с управляющими входами 224-233 БВП 16; а выход 361 — с управляющим входом 244 БАП 17, выходы

263-283 последнего соединены с входами режима 285-305 БУ 18, входы режима 311, 312 которого подключены к первому и пятому разрядам входной управляющей шины

19, поичем выход 56 блока 4 памяти подключен к информационному выходу 29 устройства, выход второго счетчик" 11 адреса подключен к информационному выхоцу 30 устройства, выход 91 триггера 8 подключен к выходу 31 конца операции устройства, а выход 88 триггера 7 подключен к выходу 32 флага видимости устройства.

Блок регистров 6 общего назначения содержит первый-восьмой регистры.

Блок 13 определения признаков (фиг, 2) содержит первый-восьмой коммутаторы

395-402, первое-четвертое арифметико-логические устройства (АЛУ) 403-406, первыйчетвертый двухразрядные коммутаторы признаков 407-410, первый регистр признаков 411 (РПР), второй регистр признаков

412, первый-четвертый элементы ИЛИ первой группы 413-416, элемент И 417. первыйчетвертый триггеры первой группы 418-421, первый-четвертый элементы ИЛИ второй группы 422-425 и соответствующие связи между указанными элементами блока.

Блок 14 формирования признаков границ (фиг. 3) содержит первый-четвертый элеме ITbl

ИСКЛ КЗЧАЩЕ Е ИЛИ 426-429. первые-четвертые элементы И первой, второй, третьей, четвертой групп элементов 430-433, 434437, 438-441, 442-445, первый-четвертый элементы ИЛИ третьей группы 446-449, первый-четвертый элементы И пятой группы

450-453, регистр текущих признаков границ (РП) 454, регистр предыдущих признаков границ (РПП) 455, регистр начальных при- знаков границ(РПН) 456, схему совпадения

457, триггер предыдущего пересечения (ТПП) 458 и соответствующие связи между указанными элементами блока.

Блоки 15,16 вычисления пересечений (фиг. 4) содержат девятый-шестнадцатый коммутаторы 459-466, девятый-шестнадцатый регистры 467-474, первый-четвертый сумматоры 475-478, первый и второй триггеры запросов (ТЗП I, ТЗП2) 479, 480, первый и второй триггеры пересечений (ТП1, ТП2)

481, 482 и соответствующие связи между указанными элементами блока.

Блок 17 анализа признаков (фиг. 5) содержит первый и второй элементы ИЛИ 483, 484, первый-шестой дешифраторы первой группы 485-490, первый триггер 491 и соответствующие связи между указанными элементами блока.

Блок управления 18 (фиг. 6) содержит входную шину 492, шину 493 состояний автомата и шину 494 состояний третьего и четвертого распределителей сигналов, шины 495-498 информации, счетчик 499 вершин, второй дешифратор 500, первый-одиннадцатый элементы И шестой группы 501-511, первый-шестой элементы

ИЛИ четвертой группы 512-517, первыйсемнадцатый элементы И седьмой группы

518-534, первый-четвертый элементы ИЛИ пятой группы 535-538, первый-пятый элементы ИЛИ шестой группы 539-543, первыйдевятый элементы И восьмой группы

544-552, первый-восьмой элементы И девятой группы 553-560, первый-четвертый элементы ИЛИ седьмой группы 561-564, первый-девятый элементы ИЛИ восьмой группы 565-573, первый-шестой элементы И десятой группы 574-579, первый-двенадцатый элементы ИЛИ девятой группы 580-591, первый-восьмой элементы И одиннадцатой группы 592-599, первый-тринадцатый элементы ИЛИ десятой группы 600-612, первый-четBåðòûé элеменTû И двенадцатой группы 613-616, первый-четвертый элементы ИЛИ одиннадцатой группы 617-620, пер55 вый-четвертый триггеры второй группы

621-624, первый-четвертый элементы И тринадцатой группы 625-628, первый-четвертый элементы ИЛИ двенадцатой группы

629-632, первый-четвертый элементы ИЛИ

1777151 тринадцатой rpynr ы 633-636. третий дешифратор 637, второй- етвертый распределители сигналов 630-640, первый-пятый элементы ИЛИ четырнадцатой группы 641645, первый-пятый триггеры третьей группы 5

646-650, четвертый дешифратор 651, второй триггер 652, третий элемент ИЛИ 653, второй элемент И 654, генератор тактовых импульсов 655 и соответствующие связи между указанными элементами блока, Блок 10 управления функционально состоит из управляющего автомата с состояниями ai u двух подавтоматов с состоянием bi u di соответст вен но.

Первый распределитель 1 сигналов 15 предназначен для формирования сигналов, разрешающих запись исходных данных иэ внешней вычислительной системы в устройство.

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

Первый и второй блоки 3.4 памяти предназначены для хранения координат вершин вводимого и отсеченного многоугольника 25 соответственно, причем первая половина слова (его младшие разряды) — координата

Х, вторая половина слова (его старшие разряды) — координата Y.

Регистр 5 окна предназначен для хра- 30 нения численных значений границ окна; верхней — YB, правой — ХП, нижней — YH, левой — ХЛ.

Блок регистров 6 общего назначения включает в себя восемь регистров. Первый 35 и второй регистры предназначены для хранения значений координат начальной (или предыдущей) вершины ребра многоугольника; третий и четвертый регистры — значений координат конечной (или текущей) вершины 40 ребра многоугольника; пятый и шестой регистры — координат первой точки пересечения, седьмой и восьмой регистры координат второй точки пересечения.

Триггеры 7.8 формируют сигналы, ука- 45 эывающие на полную или частичную видимость многоугольника, а также на окончание операции отсечения.

Триггер 9 сигнализирует об обработке первой вершины многоугольника. 50

Счетчики 10.11 предназначены для формирования адресов соответственно блоков

3,4 памяти.

Блоком 13 определения признаков вычисляются признаки видимости текущей 55 вершины многоугольника относительно окна, одновременно по четырем границам. Если вершина видима. устанавливается признак "1", если нет — "0". Они хранятся на первом регистре признаков (РПР1 41! который состоит из четырех сек .ий о три разряда в каждой. В 2,5.8,11 разрядах хранятся признаки предыдущей вершины соответственно по каждой границе УВ, ХП. УН, ХЛ. Аналогично в 1 и 3, 4 и 6, 7 и 9, 10 и 12 разряды записываются признаки видимости текущей вершины. Перед анализом последующей вершины выполняется сдвиг первого РПР влево и признаки видимости текущей вершины (содержимое разрядов

3,6,9,12) займут место признаков видимости предыдущей вершины.

Блок 14 формирования признаков границ предназначен для запоминания на четырехразрядных регистрах 454-456 признаков границ (ПГ), с которыми пересекается анализируемое ребро многоугольника, признаков границ предыдущего пересечения и признаков границ начального пересечения.

Формирование этих признаков осуществляется на первой-четвертой группах элементов

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

Блоки 15,16 предназначены для вычисления координат точки пересечения ребра с одной границей или двумя одновременно.

Блок 17 анализа признаков используется для анализа видимости ребра многоугольника или его части в процессе вычисления координат точек пересечения.

Блок управления 18 предназначен для формирования управляющих сигналов (Y) в соответствии с алгоритмом функционирования устройства отсечения многоугольника для графического дисплея. Подавтоматы блока управления предназначены для формирования управляющих сигналов при вычислении точки пересечения ребра с произвольной границей окна. В случае необходимости вычисления двух пересечений подавтоматы работают параллельно.

Работа устройства задается алгоритмом его функционирования и описывается на примере отсечения пятиугольника (фиг. 7), заданного своими вершинами fO, f1, f2, f3.

14, 10 с координатами ХОУО, Х1У1, Х2У2, Х3У3. Х4У4, ХОУО окном с граничными линиями УВ, ХП, YH. ХЛ. Устройством выполняется анализ каждого ребра многоугольника на видимость относительно окна, при необхо1777151

16 димости, вычисление пересечений и проверка многоугольника на замыкание, До запуска устройства производится загрузка иэ внешней вычислительной системы числа вершин в регистр 2 вершин, их координат в первый блок 3 памяти и значений границ окна в регистр 5 окна по входной информационной шине 20, сопровождаемые сигналами на входной управляющей шине 19: "исходное состояние", "выполнить" (ВП), "запись" (ЗП). "чтение" (ЧТ), "пуск", которые поступают в распределитель 1 сигналов и в БУ 18. Вначале появляется сигнал "исходное .состояние" на первом разряде шины, который по входу 33 устанавливает распределитель 1 сигналов в нулевое состояние, по входу режима 311 блока управления устанавливает его в состояние а0, причем этим же сигналом второй и третий распределители 655, 656 сигналов БУ 18 также устанавливаются в нулевое состояние, а сигналы У1, У2 íà его выходах 327, 328 сбрасывают счетчики 10, 11 адресов и триггеры 646-650 БУ 18. Затем внешняя вычислительная система устанавливает первый сигнал ВП на втором разряде и сигнал ЗП на третьем разряде входной управляющей шины 19, а также число вершин многоугольника на входную информационную шину 20. Сигналы поступают на входы 34.35 PC 1, на выходе 37 которого установится сигнал, разрешающий запись в . регистр 2 вершин числа вершин. По второму сигналу ВП и сигналам ЗП на выходе 38 РС

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

20. Сигнал с выхода 38 РС 1 поступает на вход режима 308 БУ 18 и íà его выходе 386 устанавливается У60, увеличивающий содержимое первого счетчика 10 адреса на

"1". По третьему сигналу ВП и четырем сигналам ЗП на втором и третьем разрядах входной управляющей шины 19 на выходах

39-42 PC 1 устанавливаются поочередно сигналы. разрешающие запись численных значений границ окна, поступающих с входной информационной шины 20 на информационный ход 57 регистра 5 окна в порядке

УВ, ХП, УН, ХЛ, Внешняя вычислительная система устанавливает на пятом разряде шины 19 сигнал "пуск", который поступает на вход режима 312 BY 18 и разрешает перезапись содержимого регистра 2 вершин, равное шести (для условий рассматриваемого примера), в счетчик 499 вершин, а также формирует на его выходах 327-331, 390 упшине 21 через информационные входы 137-.

140 и коммутаторы 396, 398, 400, 402 под

40 воздействием сигналов У10, У13 поступают значения границ окна УВ, ХП. УН, ХЛ. Сигналы У21, У22 разрешают операцию вычитания на АЛУ. 403-406, которые имеют три выхода; первый — знаковый (ЗП),.второй—

45 информацйонный, третий — признак "0"

Ф. . (ПН). Значения признаков со знаковых вы% . ходов записываются соответственно в 3,6,9, 12 рэзряд ь!:.первого РПР 411 по управляющему сигйалу У8 и по этому же сигналу, 50 через первые разряды коммутаторов признаков 407-410 в 1,4,7,10 разряды первого

РПР 411> по управляющим сигналам У31У34. Одновременно признаки поступают на элементы ИЛИ первой группы 413-416, сиг55 налы на выходах которых принимаются в триггеры первой группы 418-421 по У8. Блок управления переходит в состояние аЗ (сигнал на четвертом выходе четвертого дешифраторэ 651).

35 равляющие сигналы У1-У5, У64, по которым первый и второй счетчики 10,11 адресов, триггеры предыдущего пересечения 458 в

БФПГ 14, конца операции 8, первого и второго запросов 479; 480 в БВП 15,16, первой группы 418, 421 в БОП 13 сбрасываются, а триггер 9 вершины устанавливаются в единицу, Блок управления переходит в состояние а1 (сигнал на втором выходе четвертого дешифратора 651), В последующих тактах работы устройства вычисляются признаки видимости текущей вершины относительно четырех границ одновременно и выполняется анализ видимости ребра многоугольника относительно окна. На выходе 332 БУ 18 установится сигнал У6, поступающий на вход чтения 49 блока 3 памяти, разрешая считывание координат первой вершины fO c его выхода

51, и на вход считывания/записи 75 РОН6, разрешая запись этих координат по входам

68, 69 в третий, четвертый регистры POH 6.

Блок управления переходит в состояние а2 (сигнал на третьем выходе четвертого дешифратора 651).

На выходах 334-339, 347, 348. 357-360

БУ 18 установятся сигналы У8-У13, У21, У22, У31-У34, поступающие соответственно нэ входы 105-110, 118, 119, 128-131 блока 13 определения признаков, На первые входы четырех арифметико-логических устройств

403-406 через коммутаторы 395, 397, 399, 401 по управляющим сигналам У8, У9 передаются координаты вершины f0, УО, ХО, УО, ХО с выходов 81, 80 РО Н 6 по шине 22 через входы 142, 141 схемы. На вторые входы АЛУ

403-406 с выходов 62-65 регистра 5 окна по

1777151

10 установится

20

40

В следующем такте анализируется состояние триггера 9 вершины, который был установлен вначале в "1", что говорит об обработке первой вершины. Блок управления переходит в состояние а16, при этом содержимое счетчика 498