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

 

Изобретение относится к вычислительной технике и может быть использовано при построении устройств отображения графической информации на экране ЭЛТ и создании специализированных графических систем для тренажеров Устройство отсечения млогоугольника для графического дисплея содержит распределитель 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 вершин в БУ 18 уменьшится на "1" по У69 и станет равным памяти. Так как содержимое счетчика не ноль, на выходе дешифратора 499 сигнал не

На выходах 333, 386 БУ 18 формируются сигналы У7, У60, Управляющий сигнал У7 сбрасывает триггер 9 вершины по входу 93, разрешает сдвиг влево на 1 разряд первого

РПР 411, поступая на управляющий вход

104 БОП 13. При атом признаки видимости вершины f0, хранящиеся в 3,6,9,12 разрядах перезапишутся соответственно в 2,5,8,11 разряды. Он же разрешает пеоезапись содержимого третьего, четвертого регистров в первый, второй с выходов 80. 81 на информационные входы 66, 67 РОН 6, По сигналу

У60, поступающему на вход 96 счетчика 10 адреса, его содержимое увеличится на "1".

Блок управления возвращается в состояние а1 и, через а2, в э3. При этом в третьем, четвертом регистрах POH 6 будут храниться координаты вершины f1, а в 1 и 3, 4 и 6, 7 и

9,10 и 12 разрядах первого РПР 411 БОП 13 признаки видимости вершины И, относительно четырех границ окна. Для ребра (f0, И) содержимое этого регистра следующее:

1р 2р 4р 5р 7р 8р 10р 11р

1 1 1 1 1 1 0 0

Наличие "00" в 10,11 разрядах указывает на невидимость ребра относительно границы ХЛ, На первом выходе дешифратора

485, являющегося выходом 263 блока 17 анализа признаков, установится сигнал, поступающий на вход режима 285 БУ 18, по которому последний перейдет в состояние а16 и затем через al, а2 и а3. аналогично описанному выше, В результате работы устройства в первый, второй регистры из третьего, четвертого регистра POH 6 перезапишутся координаты вершины f1, а в третий, четвертый регистры запишутся координаты вершины f2 с блока 3 памяти аналогично описанному выше, Для ребра (f1,f2) содержимое первого РПР 411 следующее:

1р 2р 4р 5р 7р 8р 10р 11р

1 0 1 1 1 1 .1 0

Содержимое 1 и 2, 10 и 11 разрядов указывает на пересечение ребром (И,f2) границ окна УВ, ХЛ. Содержимое первого

РПР 411 через выходы 157-164 БОП 13, шину 23 и информационные входы 255-262 БАП

17 поступает на дешифратор 485. на третьем. пятом, шестом выходах которого ус ановятся сигналы, указыва:.ощие на видимость

f2, на наличие пересечения и что их 2. Эти сигналы с выходов 267, 268, 269 блока 17 анализа признаков поступают на входы режима 289, 290, 291 БУ 18 и, в соответствии с ними, на его выходах 361, 362 формируются сигналы У35, У36. Управляющий сигнал У35 поступает на управляющий вход 244 блока

17 анализа признаков, разрешая запоминание признака видимости конечной точки ребра f2 на триггере 491, а также на входы 207, 225 блоков 15,16 вычисления пересечения, сбрасывая в "0" триггеры 481, 482 пересечений и разрешая прохождение значений координат вершин И,12, соответственно Х1, Х2, У1, У2, с выходов 78-81 РОН 6 по шине

22 и входы 212, 215 через коммутаторы 459. 462. Они записываются в регистры 467-470 по У36, поступающему на управляющий вход 208 блока 15. Блок управления переходит в состояние а4 (сигнал на пятом выходе четвертого дешифратора 651), В следующих тактах функционирования устройства производится вычисление координат точки пересечения. Эта операция выполняется относительно границ окна путем определения средней точки. В том случае. когда анализ указь,вает на одну точку пересечения или средняя точка оказывается внутри окна при наличии пересечений с четырьмя, тремя, двумя границами, элементы устройства делятся на две половины. К первой половине относятся АЛУ 403, 404 с коммутаторами 395 -398, 1-6 разряды первого

РПР 411 с коммутаторами признаков 407, 408,,1 и 2 разряды второго РПР 412 БОП 13, первый блок 15 вычисления пересечения.

На этих элементах вычисляется первое пересечение по направлению ребра. Ко второй половине относятся АЛУ 405, 406 с . коммутаторами 399-402, 7-12 разряды первого РПР 411 с коммутаторами 409, 410, 3,4 разряды второго РПР 412 БОП 13 и второй блок 16 вычисления пересечения. На этих элементах вычисляется второе пересечение.

Так как при анализе ребра (f1,f2) триггер

491 в блоке 17 анализа признаков установился в "1", зто указывает на то, что вершина

f2 находится внутри кона, и значит из двух пересечений только одно будет с границей окна, а другое вне его. Координаты точки пересечения вычисляются на первой половине элементов устройства, следовательно в 1-6 разрядах первого РПР должны будут находится признаки видимости вершин ребра (И,12) относительно границ. с которыми у него пересечение.

1777151

20 ми значениями границ, поступающих через 50 коммутаторы 396, 398 по сигналам У10, У18.

Признаки видимости со знаковых выходов эаписываюгся в 1,2 разряды второго РПР по сигналу У29. Таким образом выполняется анализ видимости t1 относительно двух границ окна. Блок управления переходит в состояние b3.

В следующем такте работы блока управления осуществляется анализ разрядов втоНа выходе 364 БУ 18 формируется сигнал У38, поступающий на вход 76 считывания/записи POH 6 и разрешающий запись со сдвигом на 1 разряд вправо s пятый, шестой регистры по входам 70, 71 результата сложения на сумматорах 475, 476 с выходов 222, 223 первого блока 15 вычисления пересечения. Т,о, вычисляются координаты средней точки (t1). Блок управления переходит в состояние а5 (сигнал на шестом выходе четвертого дешифратора 651).

Нэ выходах 354, 358, 388, 392 БУ 18 формируются управляющие сигналы У28, У32, У62, У66. Для:ребра (f1 f2) в 1,2 разрядах первого РПР 411 остаются признаки видимости для границы УВ, а в 4,5 разряды по У32, У66 перезэписываются признаки с

10,11 разрядов для границы ХЛ, прохождение которых через коммутатор признаков

408 разрешает У28.

Одновременно и (в зависимости) с У28 на выходах 336, 344 БУ 18 установятся, и будут оставаться стабильными на протяжении всего процесса вычисления пересечения; управляющие сигналы У10, У18, разрешающие прохождение через коммутаторы 396, 398 численных значений границ

УВ, ХЛ, поступающих на информационные входы 137, 140 блока 13 определения признаков с выходов 62. 65 регистра 5 окна.

Сигналом У62 взводится первый триггер 479 запроса в первом БВП 15, сигнал с которого (выход 220 блока) поступает на информационный вход.325 БУ 18, который переходит в состояние а18. В этом состоянии запускается первый подавтомат с состояния b2 (сигнал на третьем выходе второго распределителя сигналов 638). Блок управления перейдет в состояние а9 после окончания работы подавтомата, о чем свидетельствует сброшенное состояние первого три гера 479 запроса.

На выходах 340, 347, 355 БУ 18 формируются сигналы У14. У21, У29, На выходах

336, 344 сигналы У10, У18 были установлены раннее. По У21 íà AflY 403, 404 выполняется операция вычитания между координатами

t1, которые пропускаются через коммутаторы 395, 397 под действием У14, и численны5

45 рого РПР 412 и первого РПР 411, которые с выходов 153, 154, 157-160 БОП 13 поступают на входы 251, 252, 255-258 БАП 17.

РПР 411 1р 2р 4р 5р

1 0 1 0

РПР 412 1р 2р

0 1

На первом выходе четвертого дешифратора первой группы 488 (выход 274 блока) устанавливается сигнал, поступающий на вход режима 296 БУ 18 и указывающий, что отрезок (f1 t1) невидим. В соответствии с этим на выходах 349, 362, 391, 392 БУ 18 устанавливаются сигналы У23, У36, У65.

У66. По сигналу У23 содержимое пятого, шестого регистров РОН 6 с выходов 82, 83 по шине 22 пропускается через коммутаторы

459, 461 и записывается в регистры 467, 469

БВП 15 по УЗ6. А также по сигналу У23 содержимое 1,2 разрядов второго РПР 412

БОП 13 через элементы ИЛИ 422, 423, корректируемые по ИЛИ сигналами на выходах признаков "0" АЛУ 403, 404, пропускаются через вторые разряды коммутаторов признаков 407. 408 и записываются в 2,5 разряды первого РПР 411 по управляющим сигналам У65, У66. Блок управления переходит в состояние b1.

На выходе 364 БУ 18 установится сигнал

У38, по которому результат сложения на сумматорах 475, 476 первой 6 ВП 15, а именно координаты средней точки t2, записываются со сдвигом вправо на один разряд в пятый, шестой регистры POH 6 под информационным входам 70, 71. Блок управления переходит в состояние b2.

В этом также работы в результате вычислений на АЛУ 403, 404 в 1,2 разряды второго РПР 412 БОП 13 записываются "11", Блок управления перейдет в состояние b3, Анализ разрядов первого РПР 411 и второго РПР 412 на блоке анализа признаков

17 показывает, РПР 411 1р 2р 4р 5р

1 0 1 1

РПР 412 1р 2р

1 1 что вторая часть отрезка (t1 f2) для двух границ УВ, ХЛ имеет признаки видимости

"11", значит полностью видима и на выходе

275 блока, соответствующему второму выходу дешифратора 488 установится сигнал, поступающий на вход 297 БУ 18, Значит поиск точки пересечения с границей окна далее будет осуществляться с частью ребра (t1,с2).

В соответствии с этим нэ выходах 351, 357, 358, 362, 365 БУ 18 устанавливаются сигналы У25, У31, У32, У36, У39. По сигналу У36 в

1777151

22 регистры 468, 470 БВП 15 записываются координаты t2, поступающие íà его входы

216, 217 с выходов 82, 83 POH 6 и пропускаемые коммутаторами 460. 462 под действием У39.

Содержимое 1,2 разрядов второго РПР

412 записывается в 1,4 разряды первого

РПР 411 по управляющим сигналам У31, У32, пропускаемые через первые разряды коммутаторов признаков 407, 408 по сигналу У25. Блок управления переходит в состояние Ь1, а затем Ь2, при этом по сигналу У38 на выходе 364 БУ 18, поступающему на вход

76 считывания/записи РОН 6, координаты вновь вычисленной средней точки сЗ отрезка (t1 <2) запишутся в пятый, шестой регистры по входам 70, 71 с выходов 222, 223 первого БВП 15.

В следующем такте работы в результате определения признаков видимости точки т3 на АЛУ 403, 404 в 1,2 разряды второго РПР

412 БОП 13 записывается "1" и устанавливается сигнал на выходе признака "0" АЛУ

403, который указывает, что координата Y точки t3 совпала со значением границы УВ, значит сЗ является точкой пересечения ребра (11,12) с границей УВ,- и на выходе 276 блока 17 установится сигнал. В соответствии с этим на выходах 371, 377, 383 БУ 18 формируются сигналы У45. У51, У57. По сигналу У45 триггер 481 пересечения первого

БВП 15 взводится в "1", а по У51, У57, поступающим на управляющие входы 177, 183

БФПГ 14, в первый разряд РП 454 запишется "1". указывающая на то, что пересечение найдено с границей YB. Единица устанав ливается следующим образом: сигналы с выходов 157, 158 БОП 13 поступают на входы 185, 186 БФПГ 14, устанавливая сигнал на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ

426, поступающий через элементы ИЛИ

438, 446 на вход РП 454. Блок управления переходит в состояние Ь4.

На выходе 330 БУ 18 установится сигнал

У4, поступающий на управляющий вход 205 первого БВП 15 и сбрасывающий триггер

479 запроса в "0". Поиск пересечения окончен. Подавтомат переходит в состояние ЬО, а блок управления продолжит свое функционирование, начиная с состояния а9.

Затем выполняется запись координат точек пересечения и видимой вершины во второй блок 4 памяти. Сигнал о наличии пересечения с выхода 221 первого БВП 15 поступает на информационный вход 245

БАП 17, На его выходе 282, соответствующему третьему выходу дешифратора 490, установится сигнал, указывающий на то, что у ребра(f1 f2) имеется пересечение и видимый конец. Поэтому на выходе 380 БУ 13 формируется сигнал У54, по которому содержимое

РП 454 перезапишется для хранения в РПН

456. т,к. первой вершиной отсеченного многоугольника является точка пересечения, а следовательно, в конце работы устройства необходимо будет осуществить проверку на его замыкание, Управляющий автомат переходит в состояние а10 (сигнал на 11 выходе дешифратора 651), В соответствии с тем, что ТПП сброшен и установлен сигнал на выходе 282 БАП 17, на выходах 341, 387 БУ 18 формируются сигналы У15, У59, У61. По сигналу У15 содержимое с выходов 82, 83 РОН 6, поступая на входы 143, 144 БОП 13, проходит через коммутаторы 401, 399 и АЛУ 406, 405 без вычитания. По У59 содержимое информационного

20 выхода АЛУ 405 с выхода 147 блока 13 поступает на информационный вход 52 блока 4 памяти и записывается в первую половину слова (его младшие разряды). Одновременно содержимое информационного выхода АЛУ

406 с выхода 148 блока 13 поступает на информационный вход 52 блока 4 памяти и записывается во вторую половину слова (его старшие разряды). Таким образом записываются координаты точки пересечения 15 в блок

3р 4 памяти. Эта точка соответствует первой точке отсеченного многоугольника g1, По сигналу У61, поступающему на вход 99, содержимое счетчика 11 адреса увеличивается на "1". Блокуправления переходит в состо35 яние а15.

На выходах 329, 335, 385, 387 БУ 18 устанавливаются сигналы УЗ, У9, У59, У61, По сигналу У9 содержимое с выходов 80, 81

POH 6, поступая на входы 141, 142 БОП 13, 40 проходит через коммутаторы 399. 401 и АЛУ

405, 406 без вычитания. А по У59 оно записывается в блок 4 памяти аналогично описанному для точки t3. Эта точка соответствует второй точке g2 отсеченного

45 многоугольника, По У61 содержимое счетчика 11 адреса увеличивается на "1". Сигнал

УЗ, поступающий на вход 166 БФПГ 14, сбрасывает триггер ТПП 458. Блок управления переходит в состояние а14, А затем пе50 рейдет в состояние а16, возвратится в а1, и через а2, в аЗ аналогично описанному для (f0,И).

В результате работы устройства содержимое счетчика вершин в БУ 18 уменьшить55 ся на "1" и станет равным 3. Координаты вершины f2 перезапишутся из третьего и четвертого в первый и второй регистры POH

6, а в третьем и четвертом регистрах будут храниться координаты вершины f3. В ре23

1777151

24 зультате сдвига первого РПР 411 влево на 1 разряд признаки видимости вершины f2 перезапишутся в 2,5,8, 11 разряды, a a 1,4,7,10 разряды запишутся признаки видимости вершины f3, вычисленные в состоянии а2.

Содержимое первого РПР 411 для ребра (12ЯЗ) в данном такте работы следующее;

1р 2р 4р 5р 7р 8р 10р 11р

1 1 .1 1 1 1 1 1

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

"1", установится сигнал на выходе 264 БАП

17 (второй выход дешифратора 485), который указывает на полную видимость ребра (f2,f3) и поступает на вход 286 БУ 18, В соответствии с этим блок управления перейдет в состояние а14, при этом s блок 4 памяти заносятся координаты вершины f3, аналогично как это было описано для вершины f2, Эта вершина соответствует третьей вершине g3 отсеченного многоугольника. Содержимое счетчика вершин в блоке управления уменьшится на "1" и станет равным 2. Блок управления формирует управляющие сигналы, проходя состояния а1, а2, аЗ, описанным образом.

В первый. второй регистры из третьего, четвертого POH 6 перезапишутся координаты вершины f3. в последние записываются координаты вершины f4. Первый РПР 411 содержит признаки видимости вершин

13Л4:

1р 2р 4р 5р 7р 8р 10р 11р

1 1 1 1 .0 1 1 1

Содержимое РП P 411 поступает с выходов 157-164 БОП 13 через шину 23 и информационные входы 255-262 БАП 17 на дешифратор 485, на третьем выходе которого сигнал не устанавливается, что свидетельствует о невидимости вершины f4, и в соответствии, с этим rio У35 триггер 491 сбросится в нулевое состояние.

Поиск точки пересечения по границе YH будет осуществляться на первой половине элементов аналогична описанному выше для ребра (И f2), Отличие заключается в там, что по состоянию а5 формируются сигналы

У27, УЗ1. У62, У65 на выходах 353, 357, 388, 391 БУ 18, по которым признаки видимости по границе YH с 7,8 разрядов первого РПР

411 перезапишутся в 1,2 разряды. Точка t4 является точкой пересечения ребра (fÇ,f4) с границей YH. Блок управления переходит в состояние а9.

По состоянию триггера 491 и сигналу с первого триггера 481 пересечения БВП 15, 1р 2р 4р 5р 7р 8р 10р 11р

1 1 1 1 1 0 0 1

На выходах 267, 268 БАП 17 установятся сигналы, указывающие, что есть пересечение и их 2. Устройство переходит к вычислению пересечений. По управляющим сигналам У35, УЗ6, У38 сбрасываются триггеры 481, 482 пересечений и записываются координаты вершин f4,f0 в регистры 467470 первого БВП 15, Результат с сумматоров 475, 476 записывается со сдвигом на 1 разряд вправо в пятый, шестой регистры

РОН 6. Таким образом вычисляются координаты точки t5. Блок управления переходит через состояние а4 в а5.

55 поступающему с его выхода 221 на вход 245

БАП 17, на втором выходе дешифратора 490 вырабатывается сигнал, свидетельствующий о наличии одного пересечения, который через выход-281 поступает на вход режима 303 БУ 18. И в связи с тем, что íà его вход режима 310 не поступает сигнал с выхода 102 дешифратора 12, который устанавливается только при нулевом состоянии

10 счетчика 11 адреса. т.е. когда в блок 4 памяти не записано еще ни одной координаты, и на входе 319 отсутствует сигнал с выхода

199 БФПГ 14 соответствующему выходу

ТПП 458, на выходах 341, 385, 387 БУ 18

15 формируются сигналы У15, У59, У61, по которым содер>кимае пятого, шестого регистров POH 6 — координаты точки t4 соответствующие четвертой точке 94 отсеченного многоугольника — перезапишется в.

20 блок 4 памяти аналогично как производилась эта операция для занесения координат точки пересечения t3. Блок управления переходит в состояние а13.

На выходе 391 БУ 18 установится сигнал

25 У55, поступающий на вход 181 БФПГ 14, который разрешает перезапись содержимого РП 454 в РПП 455 и взводит ТПП 458, указывающий на то, что последней видимой вершиной на данном этапе отсечения будет

30 тачка пересечения, Блок управления переходит в состояние а14.

Устройство переходит к анализу следующего ребра (14ЛО), Блок управления последовательно переходит в состояния: а16, а1, 35 а2, аЗ. В результате работы устройства содержимое счетчика вершин в БУ 18 уменьшится на "1" и станет равным 1. В первом, втором регистрах POH 6 хранятся координаты вершины f4, à в третьем, четвертом реги40 страх POH 6 — координаты вершины f0.

Первый РПР 411 садер>кит признаки видимости вершин f4,f0:

1777151

1р гр 4р 5р

1 0 1 1

I;v выходах 336-341. 347; 348, 355 356

hv 18 формируются игналы У1О-У15, У21, У22, У29, УЗО, поступающие на входы 107-112, 126, 127 БОП 13, На первые входы АЛУ

403-406 с выходов 82, 83 POH 6 по шине 22 через информационные входы 143, 144 и коммутаторы 395, 397. 399, 400 под воздействием сигналов У14, У15 поступают координаты средней точки t5. На вторые входы

АЛУ 403-406 с выходов 62-65 регистра 5 окна по шине 21 через информационные входы 137-140 и коммутаторы 396, 398, 400, 402 под воздействием сигналов У10-У13 поступают значения границ окна УВ, ХП, УН, ХЛ. По сигналам У21, У22 выполняется операция вычитания, и значения признаков видимости точки t5 со знаковых выходов АЛУ по сигналам У29. УЗО запишутся в 1,2 и 3,4 разряды второго РПР 412. Блок управления переходит в состояние аб. Так как точка t5 лежит внутри окна, то во все разряды второго РПР 412 запишутся "1", и в соответствии с этим на первом выходе дешифратора 486 (выходе 270 БАП 17) установится сигнал, который поступает на вход 292 БУ 18. Это значит, что обе части ребра (14л5) и (5ЛО) будут пересекаться с границами окна, и точки пересечения должны вычисляться на первой и второй половинах элементов параллельно. Поэтому устройством осуществляется перегруппировка признаков видимости в первом РПР 411, На выходах 353, 357, 359, 388, 389, 391, 393 блока управления 18 формируются сигналы У27, У31, YÇÇ, У62, У63, У65, У67. Сигнал У27 разрешает перезапись признаков через коммутаторы признаков 407, 409, а У31, YÇÇ, У65, У67 их запись в 1,2 и 7,8 разряды первого РПР 411.

Одновременно на выходах 343, 337, 345, 339

БУ 18 установятся управляющие сигналы

У17, У11, У19, У13 для коммутаторов 396, 398, 400, 402, разрешающие прохождение значений границ УН, ХП, УВ, ХЛ на АЛУ

403-406 на протяжении всего процесса поиска пересечения. Таким образом на первой половине элементов будет выполняться поиск пересечения с границей УН, а на второй — с границей ХЛ, По сигналам У62, У63, поступающим на вход 211 первого БВП 15 и вход 228 второго БВП 16, взводятся первый и второй триггеры 479, 480 запросов. сигналы которых с выходов 220, 240 блока поступают на входы 325, 326 bY 18, который переходит в состоянии а19, В этом состоянии запускаются два подавтомата, которые работают параллельно, проходя состояния

bO,Ь1,...,ЬО и d0.01,...АО. Блок управления переходит в состояние а9 после окончания работы подавтоматов, о чем сигнализируют

50 сброшенные состояния первого и .;:;;".н . с триггеров 479. 480 эапро о».

Рассмотрим работу устройства под управлением первого подавтомата. На выходах 351, 357, 358, 362. 365 БУ 18 формируются управляющие сигнальi У25, У31, У32, У36, У39, которые поступают на входы 122, 128. 129 БОП 13 и входы 208, 209 первого БВП 15. По сигналу У36 на десятый, двенадцатый регистры 468. 470 записываются координаты точки t5, проходящие через коммутаторы 460, 462 под воздействием сигнала У39 и поступающие на входы 216, 217 первого БВП 15 по шине 22 с выходов

82, 83 POH 6. Сигналы У25 разрешает перезапись признаков видимости через первые разряды коммутаторов признаков 407, 408, а У31, У32 — их запись в 1.4 разряды первого

РПР 411 с 1,2 разрядов второго РПР 412.

Содержимое первого РПР 411 для первой части ребра (т4 т5) в данном такте работы следующее:

Блок управления переходит в состояние

b1 (сигнал на втором выходе второго распределителя сигналов 638).

На выходе 364 БУ 18 устанавливается сигнал У38, поступающий на вход 76 считывания/записи POH 6 и разрешающий запись со сдвигом на 1 разряд вправо в пятый, шестой регистры по входам 70, 71 через шину 24 результата сложения на сумматорах 475, 476 с выходов 222, 223 первого БВП

15. Таким образом вычисляются координаты средней точки тб. Вычисление признаков видимости, их анализ и определение, что tá является первой точкой пересечения, аналогично ребру (fÇ,f4). В третий разряд РП 454 записывается "1", указывающая на пересечение ребра с границей YH. Первый триггер 481 пересечения в БАП 15 взводится, первый триггер 479 запроса сбрасывается. Подавтомат переходит в начальное состояние bo.

Рассмотрим работу устройства под управлением второго подавтомата. На выходах 350, 363, 366, 367, 393, 394 БУ 18 формируются управляющие сигналы У24, У67, У68, У37. У40, У41, которые поступают на входы 121, 135, 136 БОП 13 и входы 226, 229, 230 БВП 16. По сигналу У37 на тринадцатый, пятнадцатый регистры 471. 473 записываются координаты точки t5, проходящие через коммутаторы 463, 465 под воздействием сигнала У40 и поступающие на входы

27

1777151

7р 8р 10р 11р

1 1 0 1

25

50

236, 237 второго БВП 16 по шине 22 с выходов 82, 83 РОН 6, а на регистры 472, 474 перезаписывается содержимое регистров

468, 470, проходящее через коммутаторы

464, 466 под воздействием сигнала У41, поступающее на информационные входы 234;

235 второго БВП 16 с выходов 218, 219 первого БВП 15, Сигнал У24 разрешает перезапись признаков видимости через вторые разряды коммутаторов признаков 409, 410, а У67, У68 их запись разряды первого РПР

411 с 3, 4 разрядов второго РПP 412. Содержимое первого РПР 411 для второй части ребра (т5ЛО) в данном такте работы следующее:

Процесс вычисления второй точки пересечения с границей ХЛ аналогичен поиску первой точки пересечения в соответствии с приведенным алгоритмом функционирования и осуществляется на второй половине элементов. Сигнал на выходе 277 БАП 17, который соответствует первому выходу дешифратора 489, указывает на невидимость начальной части рассматриваемого отрезка, сигнал на выходе 278 указывает на невидимость конечной части. а сигнал на выходе

279 указывает, что средняя точка является точкой пересечения. Они поступают на входы режима 299-301 БУ 18. После определения точки пересечения автомат переходит в состояние d4, при этом на выходе 372 БУ 18 устанавливается сигнал У46, поступающий . на вход 227 второй БВП 16 и устанавливающий второй триггер 482 пересечения в "1".

В следующем такте на выходе 331 БУ 18 формируется сигнал У5, поступающий на вход 224 БАП 16 и сбрасывающий второй триггер 480 запроса в "0". Координаты второй точки пересечения t7 записаны в седьмом, восьмом регистрах РОН б. Второй подавтомат переходит B начальное состояние d0.

После снятия сигналов запроса на триггерах 479, 480 первого, второго БВП 15,16 блок управления продолжит свое функционирование, начиная с состояния а9. На вход

302 БУ 18 поступает сигнал, указывающий на наличие двух пересечений. с выхода 280

БАП 17, который формируется на первом выходе дешифратора 490 по сигналам, поступающим на информационные входы 261, 262 этой схемы с выходов 221, 241 первого, второго БВП 15,16. На вход 319 БУ 18 поступает сигнал с выхода 199 БФПГ 14, сформированный триггером 458 предыдущего пересечения. На вход 320 БУ 18 поступает сигнал с выхода 200 БФПГ 14, который устанавливается схемой совпадения 457, указывая на равенство содержимого РП 454 и

РПП 455 (наличие единиц в их третьих разрядах). т.е. расположение точек предыдущего и первого вычисленного пересечения на одной границе. Так как устройством не закончен анализ вершин, то на выходах 341, 378, 383, 385, 387 БУ 18 формируются управляющие сигналы У15, У52. У57, У59, У61, По сигналам У15, У59, У61 содержимое с выходов 82, 83 РОН 6 через коммутаторы 401, 399 и АЛУ 406, 405 БОП 13 беэ вычитания записывается в блок 4 памяти. Содержимое счетчика 11 адреса увеличивается на "1". Таким образом записываются координаты первой точки пересечения t6, которая соответствует пятой вершине 95 отсеченного многоугольника, По сигналам У52, У57, поступающим на управляющие входы 178, 183 БФПГ 14, в 4 разряд РП 454 запишется

"1", указывающая на то, что второе пересечение — с границей ХЛ. Это осуществляется следующим образом: сигналы с выходов

163, l64 БОП 13 поступают на входы 191, 192 БФПГ 14 и формируют сигнал на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 429, поступающий через элементы ИЛИ 445. 449 на

30 вход РП 454. Блок управления переходит в состояние а12, В этом состоянии на выходах 342, 385, 387 БУ 18 формируются управляющие сигналы У16, У59, У61. По этим сигналам содержимое седьмого, восьмого регистров POH 6 с выходов 84, 85 по шине 22, поступая на входы 146, 145 БОП 13, проходит через коммутаторы 399, 401 и АЛУ 405, 406 без вычитания и записывается в блок 4 памяти.

Содержимое счетчика 11 адреса увеличивается на "1". Так записываются координаты второй точки пересечения t7, соответствующие шестой вершине g6 отсеченного многоугольника, Блок управления переходит в состояние а13.

На выходе 381 БУ 18 устанавливается сигнал У55, по которому содержимое РП 454 перезэписывается в РПП 455 и взводится

ТПП 458 в БФПГ 14 аналогично как для ребра (ГЗХ4). Блок управления переходит в состояние а14, при этом содержимое счетчика 498 вершин станет равным "0", а затем в состояние а16.

Нэ информационный вход 319 поступает сигнал с выхода 199 БФПГ 14, сформированный триггером 458 предыдущего пересечения. В этом случае проверяется замкнутость. отсечен ного многоугольника.

На выходе 379 БУ 18 установится сигнал

1777151

У53, который разрешает перезапись содержимого РПН 456 (с признаком границы, на которой находится первая вершина отсеченного многоугольника) в РП 454. Блок управления переходит в состояние а10.

На информационный вход 319 БУ 18 поступает сигнал сформирован н ы и ТПП 458.

На информационный вход 320 БУ 18 не поступает сигнал с выхода 200 БФПГ 14, что говорит о неравенстве содержимого РП 454 и РПП 455, так как установлены первый разряд РП и четвертый разряд РПП. По содержимому РП, поступающему с выходов

201-204 БФПГ 14 на входы 321-324 БУ 18, на

его выходах 339, 345, 385, 387 формируются сигналы У13, У19, У59, У61. По сигналам У13, У19, поступающим на входы 110. 116 БОП

13, на вторые входы АЛУ 405. 406 с выходов о2, 65 регистра 5 окна по шине 21 через информационные входы 137, 140 и коммутаторы 400, 402 поступают численные значения границ окна УВ, ХЛ без вычитания в качестве координат седьмой вершины g7 отсеченного многоугольника. А по У59. У61 они записываются в блок 4 памяти с изменением содержимого счетчика 11 адреса аналогично описанному раннее. Блок управления переходит в состояние а11.

На выходе 382 BY 18 установится сигнал

У56, разрешающий сдвиг на 1 разряд вправо РПП 455, и "1" перезапишется из четвертого разряда в первый. Блок управления возвращается в состояние а10.

На его входах 310, 319, 320 присутствуют сигналы, указывающие на наличие информации на счетчике 11 адреса. взведенное. состояние ТПП 458, равенство содержимого РПП и РП. по которым блок управления перейдет в состояние э0. При этом на его выходе 390 установится сигнал

У64, который взводит триггер 8 конца операции и устанавливает триггер 7 флага видимости в состояние соответствующее сигналу на выходе элемента И 417 в БОП 13, поступающему с его выхода 165 по шине 23 на вход 86 триггера. На этом устройство заканчивает свою работу. В блоке 4 памяти содержатся координаты вершин отсеченного многоугольника g1.g2,gÇ.g4,g5,g6,g7, в счетчике 11 адреса — число его вершин.

Триггер 7 флага видимости выдает на выходе 32 сигнал частичной видимости многоугольника, а ТКО 8 на выходе 31 — сигнал окончания работы.

Рассмотрим остальные возможные варианты функционирования устройства, когда блок управления 18 находится в состоянии а6.

Ребро (k1.k2) (фиг. 8) имеет три точки пересечения: две видимые с границами УВ, ХГ1 и одна невидимая вне окна с границей

ХЛ. Блок управления 18 перейдет в состояние аб после вычисления координэ средней точки k3, Содержимое первого РПР 411 и второго РПР 412 следующее:

РПР 411 1р 2р 4р 5р 7р 8р 10р 11р

1 0 0 1 0 1 1 0

РПР 412 0 1 1 1

На выходе признака "0" (ПН1) АЛУ 403

БОП 13 установится сигнал. указывающий, что средняя точка является точкой пересечения ребра с границей YB. На выходе 272

15 БАП 17, соответствующему первому выходу дешифратора 487, по сигналам, поступающим на входы 249-260 через шину 23 с выходов 153-164 БОП 13. установится сигнал. поступающий на вход 294 БУ 18, и указыва20 ющий, что невидима первая часть ребра.

Точка кЗ является первой точкой пересечения ребра с окном, ее координаты остаются в пятом. шестом регистрах POH 6, Блок управления переходит в состояние а8, при

25 этом на его выходах 371, 375, 383 устанавливаются сигналы У45, У49, У57. По сигналу

У45, поступающему по шине 27 на вход 210

БВП 15. взводится первый триггер 481 пересечения. По сигналам У49, У57, поступаю3Q щим на входы 175, 183 БФПГ 14, в 1 разряд

РП 454 запишется "1", указывающая на то, что найдено пересечение с границей УВ, Это осуществляется следующим образом: сигналы с выходов 157, 158 БОП 13 поступа35 ют на входы 185, 186 БФПГ 14 и формируют сигнал на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 426, поступающего через элементы ИЛИ 430, 446 на вход РП 454.

В следующем такте работы блока управ40 ления выполняется разделение элементов устройства на две половины аналогично описанному для (14ЛО), Блок управления переходит в состояние а19 и запускается второй подавтомат. Блок управления перейдет

45 в состояние а9 после завершения работы подавтомата, о чем свидетельствует сброшенное состояние второго триггера 480 запроса. Вычисление второй точки пересечения осуществляется на второй половине элементов, ее координаты записываются в седьмой, восьмой регистры POH 6.

Если вычисленной средней точкой окажется k4 (фиг. 9), являющейся второй точкой пересечения, блок управления перейдет в состояние а7. При этом сигнал о невидимости второй части ребра (1<4,k4) с второго выхода дешифратора 487, поступающий с выхода 273 БАП 17 на вход режима 295 БУ

18, формирует на его выходах 363, 366, 372, 31

1777151

376, 383 управляющие сигналы У37, У40, У46, У50, У57, По сигналы У46, поступающему по шине 27 на вход 227 БВП 16, взводится второй триггер 482 пересечения. По сигналам У50, У57, поступающим на входы

176, 183 БФПГ 14, 2 разряд РП 454 установится в "1", указывая на то, что найдено пересечение с границей ХП. Это осуществляется следующим образом: сигналы с выходов 159, 160 БОП 13 поступают на входы

187, 188 БФПГ 14 и формируют сигнал на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ

427, поступающий через элементы ИЛИ 435, 447 на вход РП 454. По управляющим сигналам У37, У40 на входах 226. 229 БВП 16 выполняется запись координат точки И с выходов 82, 83 POH 6 по шине 22 через информационные входы 236, 237 и коммутаторы 463, 465 в тринадцатый, пятнадцатый регистры 471, 473. В следующем такте работы блока управления по сигналу У44 на его выходе 370, поступающему на вход 77 считывания/записи POH 6, содержимое регистров 471, 473 БВП 16 через сумматоры 477, 478 и выходы 242, 243 по шине 24 перезаписываются в седьмой, восьмой регистры РОН

6 по его входам 72, 73. Выполняется разделение элементов устройства. Блок управления переходит в состояние а19 и запускает первый подавтомат. Вычисление первой точки пересечения части ребра (k1,k4) с границей окна YB осуществляется на первой половине элементов, как было описано в предыдущих вариантах.

Если средняя точка анализируемого ребра (1,k2) лежит вне окна, т.к. хотя бы один из разрядов второго РПР 412 БОП 13 сброшен, и следовательно, установлен сигнал на первом выходе дешифратора 487, (выход

272 БАП 17), поступающий на вход 294 БУ

18, то это значит, что первая часть ребра невидимая и необходимо проводить анализ его второй части, Призйаки видимости вершины k1 в первом РПР 411 заменяются признаками видимости средней точки. Блок управления переходит в состояние а4, При этом на его выходах 349, 350, 362, 391-394 формируются сигналы У23, У24, У36, У65У68. По сигналам У23, У36 содержимое пятого, шестого регистров P OH 6 перезаписывается по шине 22 через коммутаторы 459, 461 в регистры 467, 469 БВП 15.

По сигналам У23, У24 признаки с второго

РПР 412 БОП 13 через элементы ИЛИ 422425, корректируемые по ИЛИ сигналами на выходах признаков "0" АЛУ 403-406, пропускаются через вторые разряды коммутаторов признаков 407-410 и записываются в

10

15 налам У36, У39 содержимое пятого, шестого регистров POH 6 перезаписывается через коммутаторы 460, 462 в регистры 468, 470

25

2,5,8,11 разряды первого РПР 411 по управляющим сигналам У65-У68.

Если установится сигнал на втором выходе дешифратора 487 (выход 273 БАП 17), поступающий на вход режима 295 БУ 18, то это значит, что вторая часть ребра невидима и необходимо проводить анализ его первой части, Признаки видимости вершины k2 в первом РПР 411 заменяются признаками видимости средней точки. Блок управления переходит так>ке; как и в предыдущем случае, в состояние а4, При этом íà его выходах 351, 352, 357-360, 362, 365 формируются сигналы У25, У26, У31-У34, У36, У39. По сигБВП 15. По сигналам У25, У26 признаки с второго РПР412 БОП 13 через элементы ИЛИ

422-425 пропускаются через первые разряды коммутаторов признаков 407-410 и записываются в 1,4,7,10 разряды первого РПР 411 по управляющим сигналам У31-У34, Если установится сигналы на первом и втором выходах дешифратора 487, то это значит, что ребро или анализируемая его часть полностью невидимы или оно проходит через вершину окна. В первом случае(на выходах признака нуля (ПН1-ПН4) всех АЛУ

403-406 отсутствуют сигналы) блок управления переходит в состояние а16, изменяя содержимое счетчика вершин. Во втором случае (хотя бы на одном выходе признака нуля АЛУ 403-406 есть сигнал) на выходах

371, 375, 383 БУ 18 формируются сигналы

У45, У49, У57, по которым взводится триггер

481 пересечения в БВП 15 и устанавливается соответствующий разряд РП 454 БФПГ

14 аналогично описанному раннее. Блок управления переходит в состояние а9, Рассмотрим случай, когда многоугольник располо>кен полностью вне окна. В состоянии управляющего автомата а16, когда все вершины и ребра проанализированы, ТПП 458 в БФПГ 14 сброшен, на выходе хотя бы одного из триггеров 418-421 БОП 13 установится нулевой сигнал, свидетельствующий, что все вершины невидимы относительно соответствующей границы окна, который через элемент И 417 и выход 165 поступает на вход 284 BY 18 и переводит его в состояние а0. При этом на выходе 390 сформируется сигнал У64, по которому взводится триггер 8 конца операции и устанавливается триггер 7 флага видимости в состояние соответствующее сигналу на выходе элемента И 417, т.е. он сбрасывается— многоугольник невидим. Устройство заканчивает свою работу.

1777151

В случае, когда многоугольник охватывает окно (фиг. 10) устройством выполняется занесение координат вершин окна k1, k2, k3, k4 в блок 4 памяти. Блок управления находится в состоянии а16, все вершины проанализированы, ТПП 458 в БФПГ 14 сброшен, о чем свидетельствует сигнал на выходе 319

БУ 18, счетчик 11 адресэ находится в нулевом состоянии и соответствующий сигнал с дешифратора 12 через выход .102 по шине

26 поступает на вход режима 310 БУ 18, на вход 284 которого не поступает нулевой сигнал с элемента И 417 БОП 13. Блок управления формирует четыре серии управляющих сигналов У19, У20, У47, У58, У59. У61: У12.

У20, У47, У58, У59, У61; У12, У13, У47, У58, У59, У61; У13, У19, У47, У58, У59, У61 нэ .-ыходах 338, 339, 345, 346, 373. 384. 385, 387. По сигналам У19 и У20. У12 и У20, У12 и У13, У13 и У19 численные значения пар границ окна YB и ХП. YB и ХП, YB и ХЛ, YB и ХЛ из регистра 5 окна поочередно передаются через коммутаторы 400, 402 БОП 13 и по сигналу У47, проходя через АЛУ 405, 406 без вычитания, записываются в блок 4 памят по У59. По сигналу У61 содержимое счетчика 11 адреса увеличивается на "1". После записи четырех вершин блок управления переходит в состояние а17.

Считывание координат вершин отсеченного многоугольника с блока 4 памяти по первой выходной информационной шине 29 во внешнюю вычислительную систему осуществляется следующим образом. Внешняя вычислительная система устанавливает на пятом разряде шины 19 сигнал "пуск", по которому на выходе 328 БУ 18 устанавливается управляющий сигнал У2 сбрасывающий счетчик 11 адреса в нулевое состояние.

Затем на второй разряд шины 19 устанавливается сигнал ВП, а на четвертый разряд— сигналы ЧТ, по которым на выходе 43 PC 1 формируется последовательность сигналов, поступающая на вход режима 307 БУ 18 и на выходе 387 которого устанавливается сигнал У61, увеличивающий содержимое счетчика 11 адреса на "1". Количество сигналов

ЧТ должно быть равно количеству вершин отсеченного многоугольника.

Блок управления может быть построен любым из известных способов в соответствии с приведенным алгоритмом функционирования устройства, Для объяснения работы устройства на фиг. 6 приведен один из вариантов построения такого блока. B качестве подавтоматов используются распределители сигналов. Список управляющих сигналов приведен в таблице.

В предлагаемом устройство блоки памяти могут быть реализованы на элементах серии К565, а остальные схемы на элементах серий К155, К531, К555.

Время отсечения многоугольника на устройстве — прототипе может быть оценено по формуле

Т1 = nt1 + qt1 + k1t2 +Зсбп=

10 где n — количество вершин отсекаемого многоугольника;

q — количество вершин многоугольника после отсечения двумя параллельными границами;

k1 — количество пересечений с границами окна; с1 — время анализа одной вершины и ребра на видимость;

t2 — время вычисления координат точки пересечения;

tbn — время перезаписи вершин в блок памяти, Время отсечения многоугольника на заявляемом устройстве оценивается по формуле

Т2 = nt1 + k2t2+ lt2, где k2 — количество одиночных пересечений (при наличии одного пересечения вектора с окном);

1 — количество двойных пересечений (при пересечении вектора с двумя границами окна).

Среднее время вычисления координат точки пересечения при шестнадцатиразрядном формате чисел можно оценить как t2 =

5t1. Как правило, отображаемый объект ап4р проксимируется плоскими гранями с 4,5 или

6 вершинами, в среднем — пятиугольником, Тогда временные затраты на отсечение пятиугольников при различных вариантах их расположения относительно окна можно

45 оценить KaK:

1. если невидимый пятиугольник находится над границей YB.

Т1 = 2кбс1 +Зсбп = 12t1 + Зс п

Т2 = бс1

2. если невидимый пятиугольник находится справа от границы

Т1 = 2 бс1 + 2хбс1 + Зсв = 24t1 +

+Зьп,Т2 = бс1

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

1777151

Г1 = 2 "áti + 2 "7t! 4t2 -- 4t2 З г, = ббс1 > 3 ;

Т2 =- át1+ 4t2 =-26t1

4. для пятиугольника на фиг. 8.

T1 = 2.6t1 + 2 8т1 + 4t2 + 2t2 +

+Зь,=- 58т1 + Зьп

Т2 = бт1 + Зс2 =- 21t1

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

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

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

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

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

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

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

25 к первому входу считывания-записи блока регистров общего назначения и к входу ус-. тановки в "0" триггера вершины, выход которого подключен к шестому входу режима блока управления, четвертый и пятый выхо30 ды блока управления подключены соответственно к счетным входам первого и второго счетчиков адреса, шестой выход блока управления подключен к входу установки в 1" триггера конца операции и к управляющему

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

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

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

37

38

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

"..îTâåòñòâåíно к первому и второму информационным входам первого блока вычисления пересечения, третий и четвертый

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

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

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

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

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

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

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

1777151 управляющему входу блока определения признаков и к второму управляющему входу первого блока вычисления пересечения. выходы с тридцатого по сороковой блока управления подключены соответственно к управляющим входам с девятнадцатого по двадцать девятый блока определения признаков, сорок первый выход блока управления подключен к третьему управляющему входу первого блока вычисления пересечения, к второму управляющему входу второго блока вычисления пересечения и к управляющему входу блока анализа признаков, выходы с сорок второго по пятьдесят второй блока управления подключены соответственно к четвертому управляющему входу первого блока вычисления пересечения, к третьему управляющему входу второго блока вычисления пересечения, к пятому управляющему входу первого блока вычисления пересечения, к управляющим входам с четуправляющие (Упр. сиг-(HoMep вы-! (нал (хода УА18!

) ——

Список элементов

2! 501, 512 l ! 501, 512 ! 501, 502, 539 ! 501, 544, 565 ! 501, 545, 567 I ! 651 l (503 ! 651 l (502,540 l

I 510, 511, 518, 526, 527, 542, 562, 583, 584, 596, 621 I (510,511,518,528,529,542,563,583,584,613,622! (510,511,514,518,522,526,527,542,546,562,571( (576,583,584,596,606,623,625,633,636,637,640! !

510>511>514>518>522>528>529>542>54á>563>571! (576,583,584,606,613,624,627,633-636,637,640! (504,513,541,569 (504,513,514,531-534,541,546,571,572,574,575! !

592>600 ! 515 l те же, что и для У10 те же, что и для У11 те же, что и для У12 те же, что и для У13

5 1 9 564 l

У1 > r)r) 7! У2 l 328

УЗ . l 329

l У4 330! У5 331

Уб l 332

У7 333

У8 334! У9 335

У10 (336

У11 337

У12 338! !

У13 339! l

У14 340

У15 341!

У16 342! У17 343

У18 l 344

У19 345

У20 l 346! У21 347 вертого по седьмой второго блока вычисления пересечения, к шестому управляющему входу первого блока вычисления пересечения, к восьмому управляющему входу второго блока вычисления пересечения, к тридцатому управляющему входу блока определения признаков, к девятому управляющему входу второго блока вычисления пересечения, выходы с пятьдесят третьего ð по шестьдесят второй блока управления подключены к управляющим входам с десятого по девятнадцатый блока формирования признаков границ, выходы с шестьдесят третьего по шестьдесят восьмой блока уп15 равления подключены соответственно к седьмому управляющему входу первого блока вычисления. пересечения, к десятому управляющему входу второго блока вычисления пересечения и к управляющим вхощ дам с тридцать первого по тридцать четвертый блока определения признаков. сигналы

1777151

Продолжение таблкць! — - — — 348

349! 350

Æ1 (352 (353! 354

355

356

357!! 358 (359!

360

361! 362 (363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378! 379

380

381

382 (383!

384

385

386

У22

У23

У24

У25

У26

У27

У28

У29

УЗО ! У31 !

У32 (УЗЗ (! У34 (УЗ5 (У36

У37

У38

У39

У40

У41

У42

У43 (У44 ! У45

У46

У47

У48 ! У49 ! У50

У51

У52

У53

У54

У55

У56 ! У57 !

У58

У59 !

У60!

I 3 l (516 (505, 506, 547, 548, 573 (505-508, 547, 549, 580 (505, 506, 509, 517, 550, 551, 581 (505, 507, 517, 550, 552, 582 (510, 511, 518, 526, 527, 542, 562, 583, 584, 596 ! 510, 511, 518, 528, 529, 542, 563, 583, 584, 613 (504, 513, 541, 569, 570 (504, 513, 541, 585 ! 505, 506, 510, 511, 517, 518, 526, 527, 542, 550, 551 (562,583,584, 586,596,598, 610 (502,596,506,509,510,511,517,518,528,529,542! (550,551 563,583,584,586,613,615,618 (505,507,508,510,511,517,518,526,527,542,543! (549,550,552,562,583,584,596,599,612 (505,507,508,517,549,550,552,620 ( (535,553 !

505,50б,509,517,5З5,550,551,553,586,587 (505,507,508,549,552,554,588 (536 (! 505 э 506 э 509 э 51 7э 550 э 551 э 586

1505 > 508, 555, 589 ( (508 (! 507, 549 (507,552 (537 (505,520,556,557,590 j ! 505, 530, 554, 591 (j 514, 522, 546, 571, 576, 577, 606, 607 ( (б39 (505, 510, 511, 518, 542, 556, 557, 583, 584, 601 (505, 510, 511, 518,542, 554, 583, 584, 602

I 520 ( (514,531-5З4,546,571,572,574,575,595 (521 (514, 559 (651 ( (651 (505, 514, 520, 531-534, 546, 554, 556, 557, 571, 572 ( (574, 575, 590, 595, 603 (514, 522, 546, 571, 576 (! 502, 51 4, 522, 531-534, 546, 571, 572, 574-577, 592 (604,609 ( (503,561 !

1777151

Продолжение таблицы !

1!

У61 ! ! У62

У63

) У64 ! У65 !

У66 l

У67 !

У68 !!

387 !

388 ! 389

391 ! ! 392 !

393

l ! 394 !

l 514, 522, 523, 531- 534, 546, 571, 572, 574-577, 592 I ! 604- 606 I ! 510, 511, 518, 542, 583

l 518, 543 (514,524,525,531-534,546 511,578,579,608 !

506,510, 511,518, 526, 527, 542, 548, 562, 583,584! !

596,597,609 !

505,506,510,511,518,528,529,542,547 ° 563,583! !

584,613,614,617 (505,506,510,511,518,526,527,542,543,.547,562! !

583 584 596 599 611

l505 506,510,511,518,528,529,542,543,547,563! ! 583, 584, 613, 616, 619

1777151

1777151

%иг 3

1777151

1777151

17771 1

1777151

1777151

1777151

17. 715 !

1777151 crг, 7Р

Составитель О,Аксентьева

Редактор H,Hèêoëüñêàÿ Техред М,Моргентал

Корректор С.Лисина

Заказ 4123 Тираж Подписное

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

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород. ул.Гагарина. 101

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

 

Похожие патенты:

Изобретение относится к вычислительным устройствам с ручным управлением и может быть использовано для обучения детей счету

Изобретение относится к вычислительным устройствам с ручным управлением и может быть использовано в металлообработке

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

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

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

Изобретение относится к вычислительным устройствам с ручным управлением и предназначено для решения штурманских задач

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

Изобретение относится к вычислительной технике, может быть использовано при определении уровня качества монтажных объектов и является усовершенствованием изобретения по авт

Изобретение относится к вычислительным устройствам с ручньм управлением и может быть использовано для кинематического анализа сферических механизмов

Изобретение относится к автоматике и вычислительной технике, в частности к устройстаам синхронизации работы объектов в сложной АСУ, и может быть использовано для организации совместной работы совокупности территориально разнесенных объектов управления

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

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

Изобретение относится к вычислительной технике и может быть использовано при моделировании процессов функционирования сложных систем

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

Изобретение относится к вычислительной технике и может быть использовано для анализа связности вершин графа

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

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

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

Изобретение относится к вычислительной технике и может быть использовано в электронной цифровой вычислительной машине
Наверх