Устройство отсечения многоугольника для графического дисплея Советский патент 1992 года по МПК G06F15/20 G06G1/08 

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

Известна система графического отсечения многоугольника (патент США № 3816726. G 06 Р7/ГЛ 11 0674) содержащий матричный умножитель, запоминающее устройство, шесть отсекателей соответственно для левой, правой, нижней, верхней, дальней и ближней плоскостей, каждый из которых включает в себя регистр координат начальной вершины ребра регистр координат конечной вершины ребра, арифметическое устройство, устройство анализа на видимость, триггер последней вершины, триггер видимости, регистр границы окна Недостатком данной системы является отсутствие схемных решений замыкания многоугольника, необходимость для отсечения многоугольника по границам окна четырех отсекателей последовательно соединенных друг с другом, при большой сложности которых вычислительные мощности используются не полностью.

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

XI

Xf

xi

-«,ъ

JI

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

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

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

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

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

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

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

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

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

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

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

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

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

подключены соответственно к информаци. онным входам с четвертого по пятнадцатый

блока управления, выходы с первого по

двадцать первый блока анализа признаков

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

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

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

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

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

На фиг. 1 представлена блок-схема устройства отсечения многоугольника для графического дисплея: на фиг, 2 - блок-схема

0 блока определения признаков; на фиг. 3 - блок-схема блока формирования признаков границ; на фиг. 4 - блок-схемы первого и второго блоков вычисления пересечений; на фиг. 5 - блок-схема блока анализа призна5 ков; на фиг. 6 - блок-схема блока управления; на фиг. 7-10 - примеры для объяснения операции отсечения многоугольника и отдельных ребер окном.

Устройство (фиг. 1) содержит первый

0 распределитель 1 сигналов (PC), регистр 2 вершин (РВ), блоки 3,4 первой и второй памяти (БП), регистр 5 окна, блок регистров 6 общего назначения (РОЫ), триггер 7 флага видимости (ТФВ), триггер 8 конца операции

5 (ТКО) и триггер 9 вершины (ТВ), первый и второй счетчики 10, 11 адресов, дешифратор 12, блок 13 определения признаков (БОЛ), блок 14 формирования признаков границ (БФПГ), первый блок 15 вычисления

0 пересечения (ВВП), второй блок 16 вычисления пересечения, блок 17 анализа признаков (БАП), блок управления 18(БУ), входную управляющую шину 19, входную информационному шину 20, шину 21 окна, шину 22

5 блока регистров общего назначения, шину 23 признаков, шину 24 информации, шину 25 условии, шину 26, шину 27 управления, шину 28 распределителя сигналов, первую выходную информационную шину 29, вто0 рую выходную информационную шину 30, выход 31 конца операции и выход 32 флага видимости, первый-четвертый управляющие входы 33-36 и первый-седьмой выходы 37-43 распределителя 1 сигналов, вход счи5 тывания/записи 44, информационный вход 45 и выход 46 регистра 2 вершин, информационный вход 47, вход записи 48, вход чтения 49, адресный вход 50 и выход 51 первого блока 3 памяти, информационный вход 52, вход чтения 53, вход записи 54, адресный

вход 55 и выход 56 второю блока 4 памяти, информационный вход 57. входы считывания/записи 58-61 и первый-четвергый выходы 62-65 регистра 5 окна, первый-восьмой информационные входы 66-73. первый-чет- вертый входы считывания/записи 74-77 и первый-восьмой выходы 78-85 блока регистров 6 общего назначения, информационный и управляющий входы 86. 87 и выход 88 триггера 7 флага видимости, входы установки в ноль и единицу 89. 90 и выход 91 триггера 8 конца операции, входы установки в единицу и ноль 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 вычисления пересечения, первый-десятый управляющие входы 224- 233. первый-шестой информационные входы 234-239 и первый-четвертый выходы 240-243 второго блока 16 вычисления пересечения, управляющий вход 244. первый-восемнадцать и информационные входы 245-262 и первый-двадцать первый выходы 263-283 блока 17 анализа признаков, первый-двадцать восьмой входы режима 285-312, первый-пятнадцатый информационные входы 284. 313-326 и первый-шестьдесят восьмой выходы 327- 394 блока управления 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 второго блока 4 пя- м я т и и к входу режима 307 Б У 18, оыход 46 регистра 2 вершин п о д - ключен к входу режима 309 БУ 18, выход 97 5 первого счетчика 10 адреса соединен с адресным входом 50 блока 3 памяти а его входы 95, 96 установки в ноль и счетный - с выходами 327, 386 БУ 18. выход 332 которого соединен со входом чтения 49 блока 3

0 памяти, выходы 62-65 регистра 5 окна соединены с информационными входами первой группы 137-140 блока 13 определения признаков, информационные входы 66, 67 блока регистров 6 общего назначения сое5 динены с его выходами 80, 81, а также его информационные входы 68, 69 соединены с выходом 51 блока 3 памяти, соответственно с n-младшими и n-старшими разрядами, информационные входы 70-73 РОН 6 подклю0 чены соответственно к выходам 222, 223 блока 15 вычисления пересечения и выходам 242, 243 блока 16 вычисления пересечения, а входы считывания/записи 74-77 соединены соответственно с выходами 333,

5 332. 364, 370 БУ 18, выходы 78. 79 РОН 6 подключены соответственно к информационным входам 212,213 ВВП 15, а его выходы 80, 81 подключены соответственно ко входам 141, 142 БОП 13 и к информационным

0 входам 214, 215 БВП 15, выходы 82, 83 РОН 6 подключены соответственно к информационным входам 143, 144 БОП 13, к информационным входам 216. 217 БВП 15 и к информационным входам 236. 237 БВП 16,

5 а его выходы 84, 85 подключены соответственно ко входам 145, 146 БОП 13 и к информационным входам 238, 239 БВП 16, выход 100 второго счетчика 11 адреса соединен с адресным входом 55 блока 4 памяти и вхо0 дом 101 дешифратора 12. а его входы 98, 99 установки в ноль и счетный соединены с выходами 328. 387 БУ 18, выход 385 которого соединен с входом 54 чтения блока 4 памяти, выход 102 дешифратора 12 соеди5 нен с входом режима 31 БУ 18, управляющий вход БОП 13 соединен с выходом 327 БУ 18, управляющие входы 104-131 соедине- - ны соответственно с выходами 333-360 БУ 18, управляющий вход 132 соединен с выходом

0 373 БУ 18. а управляющие входы 133-136 с выходами 391-394 БУ 18, выходы 147, 148 БОП 13 подключены к информационному входу 52 блока 4 памяти, ее выходы 149-164 подключены соответственно к информаци5 онным входам 245-260 БАП 17, выходы 157- 164 подключены соответственно к информационным входам 185-192 БФПГ 14, а выход 165 соединен с информационным входом 284 БУ 18 и с информационным входом 86 триггера 7 флага видимости, управпяющий вход 87 которого и вход 89 установки в единицу триггера 8 конца операции подключены к выходу 390 БУ 18, выход 327 которого соединен с входом 90 установки в ноль ТКО 8 и входом 92 установки в единицу триггера 9 вершины, вход 93 установки в ноль которого подключен к выходу 333 БУ

18,а выход 94 соединен с входом режима 306 БУ 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 5ВП 15, выходы 220, 221 которого соединены соответственно с информационным входом 325 БУ 18 и с информационным входом 261 БАП 17, а выходы 218, 219 подключены соответственно к информационным входам 234, 235 БВП 16, выходы 241, 240 которого соединены соответственно с информационным входом 262 БАП 17 и информационным входом 326 БУ 18, выходы 331,361, 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)содержит первый четвертый элементы ИСКЛЮЧАЩЕЕ ИЛИ 426-429. первые-четвертые элементы И первой,второй,третьей, четвертой групп элементов 430-433, 434- 437, 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, первый-четвертый элементы И двенадцатой группы 613-616, первый-четвертый элементы ИЛИ одиннадцатой группы 617-620, первый-четвертый триггеры второй группы 621-624, первый-четвертый элементы И три- надцзтой группы 625-628. первый-четвертый элементы ИЛИ двенадцатой группы 629-632. первый-четвертый элементы ИЛИ

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

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

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

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

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

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

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

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

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

Блоком 13 определения признаков вычисляются признаки видимости текущей вершины многоугольника относительно окна, одновременно по четырем границам. Если вершина видима, устанавливается признак 1, если нет - О. Они хранятся на

первом регистре признаков (РПР1) 411 который состоит из четырех секеий по три разряда в каждой. В 2,5.8.11 разрядах хранятся признаки предыдущей вершины соответственно по каждой границе YB, ХП, YH, ХЛ. Аналогично в 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. f4, TO с координатами XOYO, X1Y1, X2Y2, X3Y3. X4Y4, XOYO окном с граничными линиями YB, ХП. YH, ХЛ. Устройством выполняется анализ каждого ребра многоугольника на видимость относительно окна, при необходимости, вычисление пересечений и проверка многоугольника на замыкание.

До запуска устройства производится загрузка из внешней вычислительной системы числа вершин в регистр 2 вершин, их координат в первый блок 3 памяти и значений границ окна в регистр 5 окна по входной информационной шине 20, сопровождаемые сигналами на входной управляющей шине 19: исходное состояние, выполнить (ВП), запись (ЗП), чтение (ЧТ), пуск, которые поступают в распределитель 1 сигналов и в БУ 18. Вначале появляется сигнал исходное состояние на первом разряде шины, который по входу 33 устанавливает распределитель 1 сигналов в нулевое состояние, по входу режима 311 блока управления устанавливает его в состояние аО, причем этим же сигналом второй и третий распределители 655, 656 сигналов БУ 18 также устанавливаются в нулевое состояние, а сигналы У1, У2 на его выходах 327, 328 сбрасывают счетчики 10, 11 адресов и триггеры 646-650 БУ 18. Затем внешняя вычислительная система устанавливает первый сигнал ВП на втором разряде и сигнал ЗП на третьем разряде входной управляющей шины 19, а также число вершин многоугольника на входную информационную шину 20. Сигналы поступают на входы 34,35 PC 1, на выходе 37 которого установится сигнал, разрешающий запись в регистр 2 вершин числа вершин. По второму сигналу ВП и сигналам ЗП на выходе 38 PC 1 формируется последовательность сигналов, разрешающих запись в первый блок 3 памяти координат вершин многоугольника. поступающих от внешней вычислительной системы по входной информационной шине 20. Сигнал с выхода 38 PC 1 поступает на вход режима 308 БУ 18 и на его выходе 386 устанавливается У60, увеличивающий содержимое первого счетчика 10 адреса на 1. По третьему сигналу ВП и четырем сигналам ЗП на втором и третьем разрядах входной управляющей шины 19 на выходах 39-42 PC 1 устанавливаются поочередно сигналы, разрешающие запись численных значений границ окна, поступающих с входной информационной шины 20 на информационный ход 57 регистра 5 окна в порядке YB, ХП, YH, ХЛ. Внешняя вычислительная система устанавливает на пятом разряде шины 19 сигнал пуск, который поступает на вход режима 312 БУ 18 и разрешает перезапись содержимого регистра 2 вершин, равное шести (для условий рассматриваемого примера), в счетчик 499 вершин, а также формирует на его выходах 327-331, 390 управляющие сигналы У1-У5, У64, по которым первый и второй счетчики 10,11 адресов, триггеры предыдущего пересечения 458 в БФПГ 14, конца операции 8, первого и второго запросов 479-, 480 в БВП 15,16, первой группы 418, 421 в БОП 13 сбрасываются, а триггер 9 вершины устанавливаются в единицу. Блок управления переходит в состояние а1 (сигнал на втором выходе четвертого

дешифратора 651).

В последующих тактах работы устройства вычисляются признаки видимости текущей вершины относительно четырех границ одновременно и выполняется анализ видимости ребра многоугольника относительно окна. На выходе 332 БУ 18 установится сигнал У6, поступающий на вход чтения 49 блока 3 памяти, разрешая считывание координат первой вершины Ю с его выхода

51, и на вход считывания/записи 75 РОН6,

разрешая запись этих координат по входам

68, 69 в третий, четвертый регистры РОН 6.

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

(сигнал на третьем выходе четвертого дешифратора 651).

На выходах 334-339, 347, 348. 357-360 БУ 18 установятся сигналы У8-У13, У21, У22. У31-У34, поступающие соответственно на входы 105-110, 118, 119. 128-131 блока 13

определения признаков. На первые входы четырех арифметико-логических устройств через коммутаторы 395, 397, 399, 401 по управляющим сигналам У8, У9 передаются координаты вершины fO, YO, ХО, YO,

ХО с выходов 81, 80 РОН 6 по шине 22 через входы 142,141 схемы. На вторые входы АЛУ 403-406 с выходов 62-65 регистра 5 окна по шине 21 через информационные входы 137-. 140 и коммутаторы 396. 398, 400, 402 под

воздействием сигналов У10, У13 поступают значения границ окна YB, ХП. YH, ХЛ. Сигналы У21,У22 разрешают операцию вычитания на АЛУ/ 403-406, которые имеют три выхода: первый - знаковый (ЗП),.второй информационный, третий - признак О - (ПН). Значения признаков со знаковых выходов запи ываются соответственно в 3,6,9, 12 разряды-первого РПР 411 по управляющему сип-Ралу У8 и по этому же сигналу,

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

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

На выходах 333, 386 БУ 18 формируются сигналы У7, У60. Управляющий сигнал У7 сбрасывает триггер 9 вершины по входу 93. разрешает сдвиг влево на 1 разряд первого РПР 411, поступая на управляющий вход 104 БОП 13. При этом признаки видимости вершины fO, хранящиеся в 3,6,9,12 разрядах перезапишутся соответственно в 2,5,8,11 разряды. Он же разрешает пеоезапись содержимого третьего, четвертого регистров в первый, второй с выходов 80 81 на информационные входы 66, 67 РОН 6, По сигналу У60, поступающему на вход 96 счетчика 10 адреса, его содержимое увеличится на 1. Блок управления возвращается в состояние а1 и, через а2, в аЗ. При этом в третьем, четвертом регистрах РОН 6 будут храниться координаты вершины f1, а в 1 и 3, 4 и 6, 7 и 9,10 и 12 разрядах первого РПР 411 БОП 13 признаки видимости вершины f1, относи- тельно четырех границ окна. Для ребра (fO, f 1) содержимое этого регистра следующее:

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

11111 10 О

Наличие 00 в 10,11 разрядах указыва- ет на невидимость ребра относительно границы ХЛ. На первом выходе дешифратора 485, являющегося выходом 263 блока 17 анализа признаков, установится сигнал, поступающий на вход режима 285 БУ 18, по которому последний перейдет в состояние а16 и затем через а1, а2 и аЗ аналогично описанному выше.

В результате работы устройства в первый, второй регистры из третьего, четверто- го регистра РОН 6 перезапишутся координаты вершины f1, а в третий, четвертый регистры запишутся координаты вершины f2 с блока 3 памяти аналогично описанному выше. Для ребра (f1,f2) содер- жимое первого РПР 411 следующее

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

10111110

Содержимое 1 и 2. 10 и 11 разрядов указывает на пересечение ребром (f1,f2) границ окна YB, ХЛ. Содержимое первого РПР 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 вычисления пересечения, сбрасывая в О триггеры 481, 482 пересечений и разрешая прохождение значений координат вершин f1,f2, соответственно Х1. Х2, Y1, Y2, с выходов 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 вычисления пересечения. На этих элементах вычисляется второе пересечение.

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

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

На выходах 354, 358, 388. 392 БУ 18 формируются управляющие сигналы У28, У32, У62, У66. Для ребра (f1,f2) в 1.2 разрядах первого РПР 411 остаются признаки видимости для границы YB, а в 4,5 разряды по У32, У66 перезаписываются признаки с 10,11 разрядов для границы ХЛ, прохождение которых через коммутатор признаков 408 разрешает У28.

Одновременно и (в зависимости) с У28 на выходах 336. 344 БУ 18 установятся, и будут оставаться стабильными на протяжении всего процесса вычисления пересечения, управляющие сигналы У10, У18, разрешающие прохождение через коммутаторы 396, 398 численных значений границ YB, ХЛ, поступающих на информационные входы 137, 140 блока 13 определения признаков с выходов 62, 65 регистра 5 окна. Сигналом У62 взводится первый триггер 479 запроса в первом БВП 15, сигнал с которого (выход 220 блока) поступает на информационный вход 325 БУ 18, который переходит в состояние а18. В этом состоянии запускается первый подавтомат с состояния Ь2 (сигнал на третьем выходе второго распределителя сигналов 638). Блок управления перейдет в состояние а9 после окончания работы подавтомата, о чем свидетельствует сброшенное состояние первого триггера 479 запроса.

На выходах 340, 347, 355 БУ 18 формируются сигналы У14. У21, У29/На выходах 336,344 сигналы У10, У18 были установлены раннее. ПоУ21 на АЛ У 403,404 выполняется операция вычитания между координатами t1, которые пропускаются через коммутаторы 395, 397 под действием У14, и численными значениями границ, поступающих через коммутаторы 396, 398 по сигналам У10, У18. Признаки видимости со знаковых выходов записываются в 1,2 разряды второго РПР по сигналу У29. Таким образом выполняется анализ видимости т1 относительно двух границ окна. Блок управления переходит в состояние ЬЗ.

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

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

1010 РПР412 1р2р

01

На первом выходе четвертого дешифратора первой группы 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 по У36. А также по сигналу У23 содержимое 1,2 разрядов второго РПР 412 БОП 13 через элементы ИЛИ 422, 423, корректируемые по ИЛИ сигналами на выходах признаков О АЛУ 403, 404, пропускаются

через вторые разряды коммутаторов признаков 407, 408 и записываются в 2,5 разряды первого РПР 411 по управляющим сигналам У65, У66. Блок управления переходит в состояние Ы.

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

У38, по которому результат сложения на сумматорах 475, 476 первой БВП 15, а именно координаты средней точки т.2, записываются со сдвигом вправо на один разряд в

пятый, шестой регистры РОН 6 под информационным входам 70, 71. Блок управления переходит в состояние Ь2.

В этом также работы в результате вычислений на АЛУ 403, 404 в 1,2 разряды

второго РПР 412 БОП 13 записываются 11. Блок управления перейдет в состояние ЬЗ. Анализ разрядов первого РПР 411 и второго РПР 412 на блоке анализа признаков 17 показывает,

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

1011 РПР412 1р2р

11

что вторая часть отрезка (t1,f2) для двух границ YB, ХЛ имеет признаки видимости 11, значит полностью видима и на выходе 275 блока, соответствующему второму выходу дешифратора 488 установится сигнал, поступающий на вход 297 БУ 18. Значит поиск точки пересечения с границей окна далее будет осуществляться с частью ребра (t1 ,t2). В соответствии с этим на выходах 351, 357. 358, 362, 365 БУ 18 устанавливаются сигналы У25, У31, У32, У36. У39. По сигналу У36 в

регистры 468, 470 ВВП 15 записываются координаты t2, поступающие на его входы 216, 217 с выходов 82, 83 РОН 6 и пропускаемые коммутаторами 460. 462 под действием У39.

Содержимое 1,2 разрядов второго РПР 412 записывается в 1,4 разряды первого РПР 411 по управляющим сигналам У31, У32, пропускаемые через первые разряды коммутаторов признаков 407, 408 по сигналу У25. Блок управления переходит в состояние Ы, а затем Ь2, при этом по сигналу У38 на выходе 364 БУ 18, поступающему на вход 76 считывания/записи РОН 6, координаты вновь вычисленной средней точки t3 отрезка (t1 ,t2) запишутся в пятый, шестой регистры по входам 70, 71 с выходов 222, 223 первого БВП 15.

В следующем такте работы в результате определения признаков видимости точки t3 на АЛУ 403, 404 в 1,2 разряды второго РПР 412 БОП 13 записывается 1 и устанавливается сигнал на выходе признака О АЛУ 403, который указывает, что координата Y точки t3 совпала со значением границы YB, значит t3 является точкой пересечения ребра (f1,f2) с границей YB, и на выходе 276 блока 17 установится сигнал. В соответствии с этим на выходах 371, 377, 383 БУ 18 формируются сигналы У45. У51, У57. По сигналу У45 триггер 481 пересечения первого БВП 15 взводится ,а по У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 запроса в О. Поиск пересечения окончен. Подавтомат переходит в состояние ЬО, а блок управления продолжит свое функционирование, начиная с состояния а9.

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

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

0 в состояние аЮ (сигнал на 11 выходе дешифратора 651).

В соответствии с тем, что ТПП сброшен и установлен сигнал на выходе 282 БАП 17, на выходах 341, 387 БУ 18 формируются

5 сигналы У15,У59,У61. По сигналу У 15содер- жимое с выходов 82, 83 РОН 6, поступая на входы 143, 144 БОП 13, проходит через коммутаторы 401, 399 и АЛУ 406, 405 без вычитания. По У59 содержимое информационного

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

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

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

На выходах 329, 335, 385, 387 БУ 18 устанавливаются сигналы УЗ, У9;У59, У61. По сигналу У9 содержимое с выходов 80, 81 РОН 6, поступая на входы 141, 142 БОП 13,

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

5 многоугольника. По У61 содержимое счетчика 11 адреса увеличивается на 1. Сигнал УЗ, поступающий на вход 166 БФПГ 14, сбрасывает триггер ТПП 458. Блок управления переходит в состояние а 14. А затем пе0 рейдет в состояние а 16, возвратится в а1,и через а2, в аЗ аналогично описанному для (fO,f1).

В результате работы устройства содержимое счетчика вершин в БУ 18 уменьшить5 ся на 1 и станет равным 3. Координаты вершины f2 перезапишутся из третьего и четвертого в первый и второй регистры РОН 6, а в третьем и четвертом регистрах будут храниться координаты вершины f3. В результате сдвига первого РПР 411 влево на 1 разряд признаки видимости вершины f2 перезапишутся в 2,5,8, 11 разряды, а в 1.4,7,10 разряды запишутся признаки видимости вершины f3, вычисленные в состоянии а2. Содержимое первого РПР 411 для ребра (f2,f3) в данном такте работы следующее:

1р 2р 4р 5р 7р 8р Юр 11р 1111111 1

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

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

1р 2р 4р 5р 7р 8р Юр 11р 1111011 1

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

Поиск точки пересечения по границе YH будет осуществляться на первой половине элементов аналогично описанному выше для ребра (f 1 ,f2). Отличие заключается в том, что по состоянию а5 формируются сигналы У27, У31. У62, У65 на выходах 353, 357, 388. 391 БУ 18, по которым признаки видимости по границе YH с 7,8 разрядов первого РПР 411 перезапишутся в 1,2 разряды. Точка т.4 является точкой пересечения ребра (f3,f4) с границей YH. Блок управления переходит е состояние а9.

По состоянию триггера 491 и сигналу с первого триггера 481 пересечения БВП 15,

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

счетчика 11 адреса, т.е. когда в блок 4 памяти не записано еще ни одной координаты, и на входе 319 отсутствует сигнал с выхода 199 БФПГ 14 соответствующему выходу ТПП458, на выходах 341, 385, 387 БУ 18

формируются сигналы У15, У59, У61, по которым содержимое пятого, шестого регистров РОН 6 - координаты точки t4 соответствующие четвертой точке д4 отсеченного многоугольника - перезапишется в

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

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

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

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

Устройство переходит к анализу следующего ребра (f4,fO). Блок управления последовательно переходит в состояния : а16, а1.

з2, аЗ. В результате работы устройства содержимое счетчика вершин в БУ 18 уменьшится на 1 и станет равным 1. В первом, втором регистрах РОН 6 хранятся координаты вершины f4, а в третьем, четвертом регистрах РОН 6 - координаты вершины Ю. Первый РПР 411 содержит признаки видимости вершин f4,fO:

45

1р 2р 4р 5р 7р 8р Юр 11р 111110 01

На выходах 267, 268 БАП 17 установятся сигналы, указывающие, что есть пересечение и их 2. Устройство переходит к вычислению пересечений. По управляющим сигналам У35, У36, У38 сбрасываются триггеры 481, 482 пересечений и записываются координаты вершин f4,fO в регистры 467- 470 первого БВП 15. Результат с сумматоров 475, 476 записывается со сдвигом на 1 разряд вправо в пятый, шестой регистры РОН 6. Таким образом вычисляются координаты точки t5. Блок управления переходит через состояние а4 в а5.

Кз выходах 336 341 3-17.348,355 35G Б/ 18 формируются „i/лналы У10-У15. У21, У22, У29, УЗО, поступающие на входы 107- 112, 126, 127 БОП 13. На первые входы АЛУ 403-406 с выходов 82. 83 РОН 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 поступают значения границ окна YB. ХП, YH, ХЛ. По сигналам У2 i, У22 выполняется операция вычитания, и значения признаков видимости точки t5 со знаковых выходов АЛУ по сигналам У29, УЗО запишутся в 1,2 и 3,4 разряды второго РПР 412. Блок управления переходит в состояние аб. Так как точка т5 лежит внутри окна, го во все разряды второго РПР 412 запишутся 1. и в соответствии с этим на первом выходе дешифратора 486 (выходе 270 БАП 17) установится сигнал, который поступает на вход 292 БУ 18. Это значит, что обе части ребра (f4,t5) и (tS.fO) будут пересекаться с границами окна, и точки пересечения должны вычисляться на первой и второй половинах элементов параллельно. Поэтому устройством осуществляется перегруппировка признаков видимости в первом РПР 411. На выходах 353, 357, 359, 388, 389, 391, 393 блока управления 18 формируются сигналы У27. У31, УЗЗ, У62, У63, У65, У67. Сигнал У27 разрешает перезапись признаков через коммутаторы признаков 407, 409, а У31, УЗЗ, У65, У67 их запись в 1,2 и 7,8 разряды первого РПР 411. Одновременно на выходах 343, 337,345,339 БУ 18 установятся управляющие сигналы У17, У11, У19, У13 для коммутаторов 396, 398, 400, 402, разрешающие прохождение значений границ YH, ХП. YB, ХЛ на АЛУ 403-406 на протяжении всего процесса поиска пересечения. Таким образом на первой половине элементов будет выполняться поиск пересечения с границей YH, а на второй - с границей ХЛ. По сигналам У62, У63, поступающим на вход 211 первого БВП 15 и вход 228 второго БВП 16, взводятся первый и второй триггеры 479. 480 запросов, сигналы которых с выходов 220, 240 блока поступают на входы 325. 326 БУ 18, который переходит в состоянии а19. В этом состоянии запускаются два подавтомата, которые работают параллельно, проходя состояния

ЬО,ЫЬО и dO.dl, ...dO. Блок управления

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

сброшенные состояния первою и iorc триггеров 479. 480 .запросов

Рассмотрим работу устройства под управлением первого подавтомата. На выхо- дах 351, 357, 358, 362. 365 БУ 18 формируются управляющие сигналы У25, У31. У32, У36, У39, которые поступают на входы 122, 128. 129 БОП 13 и входы 208, 209 первого БВП 15. По сигналу У36 на десятый,

0 двенадцатый регистры 468, 470 записываются координаты точки т.5. проходящие через коммутаторы 460. 462 под воздействием сигнала У39 и поступающие на входы 216, 217 первого БВП 15 по шине 22 с выходов

5 82, 83 РОН 6. Сигналы У25 разрешает перезапись признаков видимости через первые разряды коммутаторов признаков 407, 408, а У31, У32 -их запись в 1.4 разряды первого РПР 411 с 1,2 разрядов второго РПР 412.

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

25

1р 2р 4р 5р 1011

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

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

сигнал У38. поступающий на вход 76 считывания/записи РОН 6 и разрешающий запись со сдвигом на 1 разряд вправо в пятый, шестой регистры по входам 70, 71 через

шину 24 результата сложения на сумматорах 475.476 с выходов 222. 223 первого БВП 15. Таким образом вычисляются координаты средней точки t6 Вычисление признаков видимости, их анализ и определение, что t6

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

Рассмотрим работу устройства под уп- равлением второго подавтомата. На выходах 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 и поступающие на входы

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 сЗ, 4 разрядов второго РПР 412. Содержимое первого РПР 411 для второй части ребра (t5,fO) в данном такте работы следующее:

7р 8р Юр 11р 1101

Процесс вычисления второй точки пере- сечения с границей ХЛ аналогичен поиску первой точки пересечения в соответствии с приведенным алгоритмом функционирования и осуществляется на второй половине элементов. Сигнал на выходе 277 БАП 17, который соответствует первому выходу дешифратора 489, указывает на невидимость начальной части рассматриваемого отрезка, сигнал на выходе 278 указывает на невидимость конечной части а сигнал на выходе 279 указывает, что средняя точка является точкой пересечения. Они поступают на входы режима 299-301 БУ 18 После определения точки пересечения автомат переходит в состояние d4, при этом на выходе 372 БУ 18 устанавливается сигнал У46, поступающий на вход 227 второй ВВП 16 и устанавливающий второй триггер 482 пересечения в 1. В следующем такте на выходе 331 БУ 18 формируется сигнал У5, поступающий на вход 224 БАП 16 и сбрасывающий второй триггер 480 запроса в О Координаты второй точки пересечения t7 записаны в седьмом, восьмом регистрах РОН 6. Второй подавтомат переходит в начальное состоя- ние dO.

После снятия сигналов запроса на триггерах 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, которая соответствует пятой вершине д5 отсеченного многоугольника. По сигналам У52, У57, поступающим на управляющие входы 178, 183 БФПГ 14, в 4 разряд РП 454 запишется 1, указывающая на то, что второе пересечение - с границей ХЛ. Это осуществляется следующим образом: сигналы с выходов 163, I64 БОП 13 поступают на входы 191, 192 БФПГ 14 и формируют сигнал на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 429, поступающий через элементы ИЛИ 445.449 на вход РП 454. Блок управления переходит в состояние а12.

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

На выходе 381 БУ 18 устанавливается сигнал У55, по которому содержимое РП 454 перезаписывается в РПП 455 и взводится ТПП 458 в БФПГ 14 аналогично как для ребра (f3,f4). Блок управления переходит в состояние а14, при этом содержимое счетчика 498 вершин станет равным О, а затем в состояние а16.

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

У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 с выходов 62, 65 регистра 5 окна по шине 21 через информационные входы 137, 140икоммута- торы 400, 402 поступают численные значения границ окна YB, ХЛ без вычитания в качестве координат седьмой вершины д7 отсеченного многоугольника. А по У59. У61 они записываются в блок 4 памяти с изме- нением содержимого счетчика 11 адреса аналогично описанному раннее. Блок управления переходит в состояние а11.

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

На его входах 310, 319. 320 присутствуют сигналы, указывающие на наличие ин- формации на счетчике 1 1 адреса, взведенное состояние ТПП 458, равенство содержимого РПП и РП, по которым блок управления перейдет в состояние аО. При этом на его выходе 390 установится сигнал У64, который взводит триггер 8 конца операции и устанавливает триггер 7 флага видимости в состояние соответствующее сигналу на выходе элемента И 417 в БОП 13, поступающему с его выхода 165 по шине 23 на вход 86 триггера. На этом устройство заканчивает свою работу. В блоке 4 памяти содержатся координаты вершин отсеченного многоугольника g1.g2,g3.g4.g5,g6,g7, в счетчике 11 адреса - число его вершин. Триггер 7 флага видимости выдает на выходе 32 сигнал частичной видимости многоугольника, а ТКО 8 на выходе 31 - сигнал окончания работы.

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

Ребро (к1.к2) (фиг. 8) имеет три точки пересечения: две видимые с границами YB,

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

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

100101 1 О РПР 412 0111

На выходе признака О (ПН1) АЛУ 403 БОП 13 установится сигнал, указывающий, что средняя точка является точкой пересечения ребра с границей YB. На выходе 272 БАП 17, соответствующему первому выходу дешифратора , по сигналам, поступающим на входы 249-260 через шину 23 с выходов 153-164 БОП 13. установится сигнал, поступающий на вход 294 БУ 18. и указывающий, что невидима первая часть ребра. Точка k3 является первой точкой пересечения ребра с окном, ее координаты остаются в пятом, шестом регистрах РОН 6. Блок управления переходит в состояние э8, при этом на его выходах 371, 375, 383 устанавливаются сигналы У45, У49, У57. По сигналу У45, поступающему по шине 27 на вход 210 ВВП 15, взводится первый триггер 481 пересечения. По сигналам У49, У57, поступающим на входы 175, 183 БФПГ 14, в 1 разряд РП 454 запишется 1, указывающая на то, что найдено пересечение с границей YB. Это осуществляется следующим образом: сигналы с выходов 157. 158 БОП 13 поступают на входы 185. 186 БФПГ 14 и формируют сигнал на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 426, поступающего через элементы ИЛИ 430, 446 на вход РП 454.

В следующем такте работы блока управления выполняется разделение элементов устройства на две половины аналогично описанному для (f4,fO). Блок управления переходит в состояние а19 и запускается второй подавтомат. Блок управления перейдет в состояние а9 после завершения работы подавтомата, о чем свидетельствует сброшенное состояние второго триггера 480 за- проса. Вычисление второй точки пересечения осуществляется на второй половине элементов, ее координаты записываются в седьмой, восьмой регистры РОН 6.

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

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 выполняется запись координат точки k4 с выходов 82, 83 РОН 6 по шине 22 через информационные входы 236, 237 и коммутаторы 463, 465 в тринадцатый, пятнадцатый регистры 471, 473. В следующем такте работы блока управления по сигналу У44 на его выходе 370, поступающему на вход 77 считывания/записи РОН 6, содержимое регистров 471, 473 БВП 16 через сумматоры 477, 478 и выходы 242, 243 по шине 24 перезаписываются в седьмой, восьмой регистры РОН 6 по его входам 72, 73. Выполняется разделение элементов устройства. Блок управления переходит в состояние а19 и запускает первый подавтомат. Вычисление первой точки пересечения части ребра (k1,k4) с границей окна YB осуществляется на первой половине элементов, как было описано в предыдущих вариантах.

Если средняя точка анализируемого ребра (k1 ,k2) лежит вне окна, т.к. хотя бы один из разрядов второго РПР 412 БОП 13 сброшен, и следовательно, установлен сигнал на первом выходе дешифратора 487, (выход 272 БАП 17), поступающий на вход 294 БУ 18, то это значит, что первая часть ребра невидимая и необходимо проводить анализ его второй части. Признаки видимости вершины к1 в первом РПР 411 заменяются признаками видимости средней точки. Блок управления переходит в состояние а4. При этом на его выходах 349, 350, 362, 391-394 формируются сигналы У23. У24, У36, У65- У68. По сигналам У23, У36 содержимое пятого, шестого регистров РОН 6 перезаписывается по шине 22 через коммутаторы 459, 461 в регистры 467, 469 БВП 15. По сигналам У23, У24 признаки с второго РПР 412 БОП 13 через элементы ИЛИ 422- 425, корректируемые по ИЛИ сигналами на выходах признаков О АЛУ 403-406, пропускаются через вторые разряды коммутаторов признаков 407-410 и записываются в

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

Если установится сигнал на втором выходе дешифратора 487 (выход 273 БАП 17),

поступающий на вход режима 295 БУ 18, то это значит, что вторая часть ребра невидима и необходимо проводить анализ его первой части. Признаки видимости вершины к2 в первом РПР 411 заменяются признаками

видимости средней точки. Блок управления переходит также, как и в предыдущем случае, в состояние а4. При этом на его выходах 351,352, 357-360, 362, 365 формируются сигналы У25, У26, У31-У34, У36, У39. По сигналам У36, У39 содержимое пятого, шестого регистров РОН 6 перезаписывается через коммутаторы 460, 462 в регистры 468, 470 БВП 15. По сигналам У25, У26 признаки с второго РПР 412 БОП 13 через элементы ИЛИ

422-425 пропускаются через первые разряды коммутаторов признаков 407-410 и записываются в 1,4,7,10 разряды первого РПР 411 по управляющим сигналам У31-У34.

Если установится сигналы на первом и

втором выходах дешифратора 487, то это значит, что ребро или анализируемая его часть полностью невидимы или оно проходит через вершину окна. В первом случае (на выходах признака нуля (ПН1-Г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 БУ 18 и переводит его в состояние аО. При этом на выходе 390 сформируется сигнал У64, по которому взводится триггер 8 конца операции и устанавливается триггер 7 флага видимости в состояние соответствующее сигналу на выходе элемента И 417, т е. он сбрасы вается - многоугольник невидим Устройство заканчивает свою работу.

В случае, когда многоугольник охватывает окно (фиг. 10) устройством выполняется занесение координат вершин окна И, 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 приведен один из вариантов построения такого блока. В качестве подавтоматов используются распределители сигналов. Список управляющих сигналов приведен в таблице

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

Т1 nt1 +qt1 +k1t2 +3ten

где п - количество вершин отсекаемого многоугольника;

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

k1 - количество пересечений с границами окна;

t1 - время анализа одной вершины и ребра на видимость;

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

пересечения;

ten время перезаписи вершин в блок памяти.

Время отсечения многоугольника на за- являемом устройстве оценивается по формуле

Т2 nt1 + k2t2 + It2.

где k2 - количество одиночных пересечений (при наличии одного пересечения вектора с окном);

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

Среднее время вычисления координат точки пересечения при шестнадцатиразрядном формате чисел можно оценить как t2 5t1. Как правило, отображаемый объект аппроксимируется плоскими гранями с 4,5 или 6 вершинами, в среднем - пятиугольником. Тогда временные затраты на отсечение пятиугольников при различных вариантах их расположения относительно окна можно

оценить как:

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

50

Т1 +3t6n 12t1 +3t6n T2 6t1

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

T1 + + 3t6n 24t1 + +3t6n;T2 6t1

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

П --2 6t1 -i 2«7t1 - 4t2 4x2

I3tftn - 66t1 1- 3Un

T2 - 6t1 + 4t2 -26t1

4. для пятиугольника на фиг 8 Т1 2-6t1 + 2/8x1 + 4t2 + 2t2 +

-t3t6n 58x1 ЗХбп

T2 6x1 +3x2 21x1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

сигналы

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

IIГ

|Упр. сиг-(Номер вы-| |нал (хода УА18|

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

У22 У23 У24 У25 У26 У27 У28 У29 УЗО У31

У32 УЗЗ

У34 У35 УЗб У37 У38 У39 У40 У41 У42 У43 У44 У45 У46 У47 У48 У49 У50 У51 У52 У53 У54 У55 У56 У57

У58

У59

У60

348 349 350 351 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

|516

1505,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

1504,513,541,569,570

1504,513,541,585

1505,506,510,511,517,518,526,527,542,550,551

1562,583,584,586,596,598,610

|502,505,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,506,509,517,535,550,551,553,586,587

|505,507,508,549,552,554,588

(536

(505,506,509,517,550,551,586

1505,508,555,589

|508

1507,549

(507,552

|537

(505,520,556,557,590

505,530,554,591

|514,522,546,571,576,577,606,607

|639

|505,510,511,518,542,556,557,583,584,601

1505,510,511,518,542,554,583,584,602

|520

(514,531-534,546,571,572,574,575,595

|521

1514,559

1651

1651

1505,514,520,531-534,546,554,556,557,571,5721

1574,575,590,595,603|

(514,522,546,571,576 |

|502,514,522,531-534,546,571,572,574-577,592|

|604,609I

(503,561I

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

I У613871514,522,523,531-534,546,571,572,574-577,592

604-606

У623881510,511,518,542,583

У633891518,543

У643901514,524,525,531-534,546,511,578,579,608

У653911506,510,511,518,526,527,542,548,562,583,584

1596,597,609 У66 | 392 1505,506,510,511,518,528,529,542,547,563,583

j 1584,613,614,617 У67 | 393 1505,506,510,511,518,526,527,542,543,547,562

j 1583,584,596,599,611

У68 | 394 1505,506,510,511,518,528,529,542,543,547,5631 | 1583,584,613,616,619I

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

S

9Ь 3

Г

ffo

ш

ш,

0,

hего,

| 4-«iM M- U-l«г -

(

Ъ/гбо

/5

/3