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

)5 6 06 Г 15/20, 6 06 6 1/08с ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССР1 ГОСПАТЕНТ СССР) И ИЗОБРЕТЕТЕЛ ЬСТВУ ф с СВИ К АВТОРС лея содержит распределите регистр 2 вершин, блоки 3,4 и памяти, регистр 5 окна, бл общего назначения, триггер мости, триггер 8 конца опер вершины, первый и второй адресов, блок 18 управления шения быстродействия устр определения видимости реб сительно всех границ окна, новременно координат точе ребра с окном и выполнен многоугольника в устройств шифратор 12. блок 13 опред ков, блок 14 формирован границ. первый и второй бло ления пересечения, блок 17 а ков, 10 ил, 1 табл. 1"ч. 43ехнический институти Е.А.Башков6726, кл. 0 06 Р 7/38, 1974.тент 1 ч. 0132573, кл. 6 06 ОТСЕЧЕНИЯ МНОГОРАФИЧЕСКОГО ДИСПносится к вычислитель- быть использовано при . тв отображения графина экране ЭЛТ и создаованных графических ров. Устройство отсечедля графического диспское устройство, устройство анализа на видимость, триггер последней вершины, триггер видимости, регистр границы окна, Недостатком данной системы является отсутствие схемных решений замыкания многоугольника, необходимость для отсечения многоугольника по границам окна четырех отсекателей последовательно соединенных друг с другом, при большой сложности которых вычислительные мощности используются не полностью.Наиболее близким техническим решением, выбранным в качестве прототипа, является отсекатель для дисплеев на электронно-лучевой трубке (европейский патент М 0132573, 6 06 Г 15/20, 13,02.85). Изобретение относится к вычислительной технике и может быть использовано при построении устройств отображения графической информации на экране ЭЛТ и создании специализированных графических систем для тренажеров.Известна система графического отсечения многоугольника (патент США М 3816726, 6 06 Р 7/;8, 11.06.74), содержащий матричный умножитель, запоминающее устройство, шесть отсекателей соответственно для левой, правой, нижней, верхней, дальней и ближней плоскостей, каждый из которых включает в себя регистр координат начальной вершины ребра, регистр координат конечной вершины ребра, арифметиче,21) 4806001/24(54) УСТРОЙСТВОУГОЛЬНИКА ДЛЯ ГЛЕЯ(57) Изобретение отной технике и можетпостроении устройсческой информациинии специализирсистем для тренажения многоугольника ль 1 сигналов, ервой и второй ок регистров 67 флага видиации, триггер 9 счетчики 10, 11 . С целью повыойства за счет ра сразу отновычисления одк пересечения ия замыкания о введены дееления признаия признаков ки 15,16 вычиснализа призна 20177715119ми значениями границ, поступающих через 50 коммутаторы 396, 398 по сигналам У 10, У 18, Признаки видимости со знаковых выходовзаписываюгся в 1,2 разряды второго РПР по сигналу У 29. Таким образом выполняется анализ видимости т 1 относительно двух границ окна. Блок управления переходит в состояние ЬЗ.В следующем такте работы блока управления осуществляется анализ разрядов втоНа выходе 364 БУ 18 формируется сигнал У 38, поступающий на вход 76 считывания/записи РОН б и разрешающий запись со сдвигом на 1 разряд вправо в пятый, шестой регистры по входам 70, 71 результата сложения на сумматорах 475, 476 с выходов 222, 223 первого блока 15 вычисления пересечения. Т,о, вычисляются координаты средней точки (т 1). Блок управления переходит в состояние а 5 (сигнал на шестом выходе четвертого дешифратора 651).Нэ выходах 354, 358, 388, 392 БУ 18 формируются управляющие сигналы У 28, У 32, У 62, Убб. Для:ребра (И Л 2) в 1,2 разрядах первого РПР 411 остаются признаки видимости для границы УВ, а в 4,5 разряды по У 32, Убб перезэписываются признаки с 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. В этом состоянии запускается первый подавтомат с состояния Ь 2 (сигнал на третьем выходе второго распределителя сигналов 638). Блок управления перейдет в состояние а 9 после окончания работы подавтомата, о чем свидетельствует сброшенное состояние первого тригера 479 запроса.На выходах 340, 347, 355 БУ 18 формируются сигналы У 14, У 21, У 29, На выходах 336, 344 сигналы У 10, У 18 были установлены раннее. По У 21 на АЛУ 403, 404 выполняется операция вычитания между координатами т 1, которые пропускаются через коммутаторы 395. 397 под действием У 14, и численны 5 10 15 20 25 30 35 40 45 рого РПР 412 и первого РПР 411, которые свыходов 153, 154, 151-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 и указывающий, чтоотрезок (Ид 1) невидим. В соответствии сэтим на выходах 349, 362, 391, 392 БУ 18устанавливаются сигналы У 23, У 36, У 65.Убб. По сигналу У 23 содержимое пятого, шестого регистров РОН б с выходов 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, Убб. Блок управления переходит в состояние Ь 1.На выходе 364 БУ 18 установится сигналУ 38, по которому результат сложения насумматорах 475, 476 первой БВП 15, а именно координаты средней точки т 2, записываются со сдвигом вправо на один разряд впятый, шестой регистры РОН б под информационным входам 70, 71. Блок управленияпереходит в состояние Ь 2.В этом также работы в результате вычислений на АЛУ 403, 404 в 1,2 разрядывторого РПР 412 БОП 13 записываются "11",Блок управления перейдет в состояние ЬЗ,Анализ разрядов первого РПР 411 и второго РПР 412 на блоке анализа признаков17 показывает,РПР 411 1 р 2 р 4 р 5 р1 0 1 1РПР 412 1 Р 2 р1 1что вторая часть отрезка (т 1 Л 2) для двухграниц УВ, ХЛ имеет признаки видимости"11", значит полностью видима и на выходе275 блока, соответствующему второму выходу дешифратора 488 установится сигнал, поступающий на вход 297 БУ 18, Значит поискточки пересечения с границей окна далеебудет осуществляться с частью ребра (т 1 д 2),В соответствии с этим нэ выходах 351, 357,358, 362, 365 БУ 18 устанавливаются сигналы У 25, У 31, У 32, У 36, У 39. По сигналу У 36 врегистры 468, 470 БВП 15 записываются координаты 12, поступающие на его входы 216, 217 с выходов 82, 83 РОН 6 и пропускаемые коммутаторами 460, 462 под действием У 39.Содержимое 1,2 разрядов второго РПР 412 записывается в 1,4 разряды первого РПР 411 по управляющим сигналам У 31, У 32, пропускаемые через первые разряды коммутаторов признаков 407, 408 по сигналу У 25. Блок управления переходит в состояние Ь 1, а затем Ь 2, при этом по сигналу У 38 на выходе 364 БУ 18, поступающему на вход 76 считывания/записи РОН б, координаты вновь вычисленной средней точки сЗ отрезка (11 л 2) запишутся в пятый, шестой регистры по входам 70, 71 с выходов 222, 223 первого БВП 15.В следующем такте работы в результате определения признаков видимости точки 13 на АЛУ 403, 404 в 1,2 разряды второго РПР 412 БОП 13 записывается "1" и устанавливается сигнал на выходе признака "0" АЛУ 403, который указывает, что координата У точки сЗ совпала со значением границы УВ, значит сЗ является точкой пересечения ребра (11,12) с границей УВ, и на выходе 276 блока 17 установится сигнал. В соответствии с этим на выходах 311, 377, 383 БУ 18 формируются сигналы У 45. У 51, У 57. По сигналу У 45 триггер 481 пересечения первого БВП 15 взводится в "1", а по У 51, У 57, поступающим на управляющие входы 177, 183 БФПГ 14, в первый разряд РП 454 запишется "1". указывающая на то, что пересечение найдено с границей УВ. Единица устанавливается следующим образом; сигналы с выходов 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, установится сигнал, указывающий на то, что у ребра(И Л 2) имеется пересечение и видимый конец. Поэтому на выходе 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 в блок 30 4 памяти. Эта точка соответствует первой точке отсеченного многоугольника 91, По сигналу У 61, поступающему на вход 99, содержимое счетчика 11 адреса увеличивается на "1", Блокуправления переходит в состо яние а 15.На выходах 329, 335, 385, 387 БУ 18устанавливаются сигналы УЗ, У 9, У 59, У 61, По сигналу У 9 содержимое с выходов 80, 81 РОН 6, поступая на входы 141, 142 БОП 13, 40 проходит через коммутаторы 399, 401 и АЛУ405, 406 без вычитания, А по У 59 оно записывается в блок 4 памяти аналогично описанному для точки тЗ. Эта точка соответствует второй точке 92 отсеченного 45 многоугольника, По У 61 содержимое счетчика 11 адреса увеличивается на "1". Сигнал УЗ, поступающий на вход 166 БФПГ 14, сбрасывает триггер ТПП 458. Блок управления переходит в состояние а 14, А затем пе рейдет в состояние а 16, возвратится в э 1, ичерез а 2, в аЗ аналогично описанному для (Ю,И).В результате работы устройства содержимое счетчика вершин в БУ 18 уменьшить ся на "1" и станет равным 3. Координатывершины 12 перезапишутся из третьего и четвертого в первый и второй регистры РОН б, а в третьем и четвертом регистрах будут храниться координаты вершины 3. В результате сдвига первого РПР 411 влево на 1 разряд признаки видимости вершины 12 перезапишутся в 2,5,8, 11 разряды, а в 1,4,7,10 разряды запишутся признаки видимости вершины 13, вычисленные в состоянии а 2. Содержимое первого РПР 411 для ребра (12 ЯЗ) в данном такте работы следующее;1 р 2 р 4 р 5 р 7 р 8 р 10 р 11 р1 1 .1 1 1 1 1 1Так как все признаки видимости равны "1", установится сигнал на выходе 264 БАП 17 (второй выход дешифратора 485), который указывает на полную видимость ребра 12,3) и поступает на вход 286 БУ 18, В соответствии с этим блок управления перейдет в состояние а 14, при этом в блок 4 памяти заносятся координаты вершины 13, аналогично как это было описано для вершины 12, Эта вершина соответствует третьей вершине 93 отсеченного многоугольника, Содержимое счетчика вершин в блоке управления уменьшится на "1" и станет равным 2. Блок управления формирует управляющие сигналы, проходя состояния а 1, а 2, аЗ, описанным образом.В первый. второй регистры из третьего, четвертого РОН б перезапишутся координаты вершины 13. в последние записываются координаты вершины 14. Первый РПР 411 содержит признаки видимости вершин 13 Л 4:1 р 2 р 4 р 5 р 7 р 8 р 10 р 11 р1 1 1 1 0 1 1 1Содержимое РП Р 411 поступает с выходов 157-164 БОП 13 через шину 23 и информационные входы 255-262 БАП 17 на дешифратор 485, на третьем выходе которого сигнал не устанавливается, что свидетельствует о невидимости вершины 14, и в соответствии, с этим по У 35 триггер 491 сбросится в нулевое состояние,Поиск точки пересечения по границе УН будет осуществляться на первой половине элементов аналогично описанному выше для ребра И Л 2), Отличие заключается в том, что по состоянию а 5 формируются сигналы У 27, УЗ 1. У 62, У 65 на выходах 353, 357, 388, 391 БУ 18, по которым признаки видимости по границе УН с 7,8 разрядов первого РПР 411 перезапишутся в 1,2 разряды. Точка 14 является точкой пересечения ребра (13,14) с границей УН. Блок управления переходит в состояние а 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 пересечений и записываются координаты вершин 14,Ю в регистры 467- 470 первого БВП 15, Результат с сумматоров 475, 476 записывается со сдвигом на 1 разряд вправо в пятый, шестой регистры РОН б. Таким образом вычисляются координаты точки т 5. Блок управления переходит через состояние а 4 в а 5,50 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, по которым содеркимое пятого, шестого регистров РОН б - координаты точки 14 соответствующие четвертой точке 94 отсеченного многоугольника - переэапишется в.20 блок 4 памяти аналогично как производилась эта операция для занесения координат точки пересечения тЗ. Блок управления переходит в состояние а 13.На выходе 391 БУ 18 установится сигнал 25 У 55, поступающий на вход 181 БФПГ 14,который разрешает перезапись содержимого РП 454 в РПП 455 и взводит ТПП 458, указывающий на то, что последней видимой вершиной на данном этапе отсечения будет30 точка пересечения, Блок управления переходит в состояние а 14.Устройство переходит к анализу следующего ребра (14 ЛО), Блок управления последовательно переходит в состояния: а 16, а 1, 35 а 2, аЗ. В результате работы устройства содержимое счетчика вершин в БУ 18 уменьшится на "1" и станет равным 1. В первом, втором регистрах РОН 6 хранятся координаты вершины 14, а в третьем, четвертом реги страх РОН б - координаты вершины Ю,Первый РПР 411 содержит признаки видимости вершин 14 ЛО:;а выходах 336 341. 347; 348, 355 356 Б/ 18 формируются игналы У 10-У 15, У 21, У 22, У 29, УЗО, поступающие на входы 107" 112, 126, 127 БОП 13, На первые входы АЛУ 403-406 с выходов 82, 83 РОН 6 по шине 22 через информационные входы 143, 144 и коммутаторы 395, 397. 399, 400 под воздействием сигналов У 14, У 15 поступают координаты средней точки с 5. На вторые входы АЛУ 403-406 с выходов 62-65 регистра 5 окна по шине 21 через информационные входы 137-140 и коммутаторы 396, 398, 400, 402 под воздействием сигналов У 10-У 13 поступают значения границ окна УВ, ХП, УН, ХЛ. По сигналам У 21, У 22 выполняется операция вычитания, и значения признаков видимости точки с 5 со знаковых выходов АЛУ по сигналам У 29, УЗО запишутся в 1,2 и 3,4 разряды второго РПР 412, Блок управления переходит в состояние аб. Так как точка с 5 лежит внутри окна, то во все разряды второго РПР 412 запишутся "1", и в соответствии с этим на первом выходе дешифратора 486 (выходе 270 БАП 17) установится сигнал, который поступает на вход 292 БУ 18. Это значит, что обе части ребра (14 с 5) и (с 5 ЛО) будут пересекаться с границами окна, и точки пересечения должны вычисляться на первой и второй половинах элементов параллельно. Поэтому устройством осуществляется перегруппировка признаков видимости в первом РПР 411, На выходах 353, 357, 359, 388, 389, 391, 393 блока управления 18 формируются сигналы У 27, У 31, УЗЗ, У 62, У 63, У 65, У 67. Сигнал У 27 разрешает перезапись признаков через коммутаторы признаков 407, 409, а УЗ 1, УЗЗ, У 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 БУ 18, который переходит в состоянии а 19, В этом состоя 55 нии запускаются два подавтомата, которые работают параллельно, проходя состояния ЬО,Ь 1, ЬО и б 0.0100, Блок управления переходит в состояние а 9 после окончания работы подавтоматов, о чем сигнализируют 5 10 15 20 25 30 35 40 45 50 сброшенные состояния первого и и,".н с триггеров 479, 480 эапро о.Рассмотрим работу устройства под управлением первого подавтомата. На выходах 351, 357, 358, 362, 365 БУ 18 формируются управляющие сигналы У 25, У 31, У 32, У 36, У 39, которые поступают на входы 122, 128, 129 БОП 13 и входы 208, 209 первого БВП 15. По сигналу У 36 на десятый, двенадцатый регистры 468. 470 записываются координаты точки с 5, проходящие через коммутаторы 460, 462 под воздействием сигнала У 39 и поступающие на входы 216, 217 первого БВП 15 по шине 22 с выходов 82, 83 РОН 6. Сигналы У 25 разрешает перезапись признаков видимости через первые разряды коммутаторов признаков 407, 408, а У 31, У 32 - их запись в 1.4 разряды первого РПР 411 с 1,2 разрядов второго РПР 412, Содержимое первого РПР 411 для первой части ребра (т 4 с 5) в данном такте работы следующее:1 р гр 4 р 5 р 1 0 1 1 Блок управления переходит в состояние Ь 1 (сигнал на втором выходе второго распределителя сигналов 638).На выходе 364 БУ 18 устанавливается сигнал У 38, поступающий на вход 76 считывания/записи РОН 6 и разрешающий запись со сдвигом на 1 разряд вправо в пятый, шестой регистры по входам 70, 71 через шину 24 результата сложения на сумматорах 475, 476 с выходов 222, 223 первого БВП 15. Таким образом вычисляются координаты средней точки сб. Вычисление признаков видимости, их анализ и определение, что сб является первой точкой пересечения, аналогично ребру (13,Л 4). В третий разряд РП 454 записывается "1", указывающая на пересечение ребра с границей УН. Первый триггер 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 записываются координаты точки с 5, проходящие через коммутаторы 463, 465 под воздействием сигнала У 40 и поступающие на входы28 1777151 10 7 р 8 р 10 р 11 р1 1 0 1 20 35 40 45 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 разрядов второго РП Р 412, Содержимое первого РПР 411 для второй части ребра (т 5,Ю) в данном такте работы следующее: Процесс вычисления второй точки пересечения с границей ХЛ аналогичен поиску первой точки пересечения в соответствии с приведенным алгоритмом функционирования и осуществляется на второй половине элементов. Сигнал на выходе 277 БАП 17, который соответствует первому выходу дешифратора 489, указывает на невидимость начальной части рассматриваемого отрезка, сигнал на выходе 278 указывает на невидимость конечной части. а сигнал на выходе 279 указывает, что средняя точка является точкой пересечения. Они поступают на входы режима 299-301 БУ 18, После определения точки пересечения автомат переходит в состояние б 4, при этом на выходе 372 БУ 18 устанавливается сигнал У 46, поступающий на вход 227 второй БВП 16 и устанавливающий второй триггер 482 пересечения в "1", В следующем такте на выходе 331 БУ 18 формируется сигнал У 5, поступающий на вход 224 БАП 16 и сбрасывающий второй триггер 480 запроса в "0", Координаты второй точки пересечения 17 записаны в седьмом, восьмом регистрах РОН б. Второй подавтомат переходит в начальное состояние ОО.После снятия сигналов запроса на триггерах 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 РОН бчерез коммутаторы 401,399 и АЛУ 406, 405 БОП 13 беэ вычитания записывается в блок 4 памяти. Содержимое счетчика 11 адреса увеличивается на "1". Таким образом записываются координаты первой точки пересечения 16, которая соответствует пятой вершине 95 отсеченного многоугольника, По сигналам У 52, У 57,поступающим на управляющие входы 178, 183 БФПГ 14, в 4 разряд РП 454 запишется "1", указывающая на то, что второе пересечение - с границей ХЛ. Это осуществляется следующим образом: сигналы с выходов 163, 164 БОП 13 поступают на входы 191, 192 БФПГ 14 и формируют сигнал на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 429, поступающий через элементы ИЛИ 445. 449 на ЗО вход РП 454. Блок управления переходит в состояние а 12,В этом состоянии на выходах 342, 385, 387 БУ 18 формируются управляющие сигналы У 16, У 59, У 61. По этим сигналам содержимое седьмого, восьмого регистров РОН б с выходов 84, 85 по шине 22, поступая на входы 146, 145 БОП 13, проходит через коммутаторы 399, 401 и АЛУ 405, 406 без вычитания и записывается в блок 4 памяти. Содержимое счетчика 11 адреса увеличивается на "1". Так записываются координаты второй точки пересечения 17, соответствующие шестой вершине дб отсеченного многоугольника, Блок управления переходит в состоя ние а 13.На выходе 381 БУ 18 устанавливается сигнал У 55, по которому содержимое РП 454 перезаписывается в РПП 455 и взводится ТПП 458 в БФПГ 14 аналогично как для ребра (ГЗХ 4). Блок управления переходит в состояние а 14, при этом содержимое счетчика 498 вершин станет равным "0", а затемв состояние а 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 поступают численные значения границ окна УВ, ХЛ без вычитания в качестве координат седьмой вершины 97 отсеченного многоугольника, А по У 59. У 61 они записываются в блок 4 памяти с изменением содержимого счетчика 11 адреса аналогично описанному раннее. Блок управления переходит в состояние а 11.На выходе 382 БУ 18 установится сигнал У 56, разрешающий сдвиг на 1 разряд вправо РПП 455, и "1" перезапишется из четвертого разряда в первый. Блок управления возвращается в состояние а 10.На его входах 310, 319, 320 присутствуют сигналы, указывающие на наличие информации на счетчике 11 адреса, взведенное. состояние ТПП 458, равенство содержимого РПП и РП. по которым блок управления перейдет в состояние эО. При этом на его выходе 390 установится сигнал У 64, который взводит триггер 8 конца операции и устанавливает триггер 7 флага видимости в состояние соответствующее сигналу на выходе элемента И 417 в БОП 13, поступающему с его выхода 165 по шине 23 на вход 86 триггера, На этом устройство заканчивает свою работу, В блоке 4 памяти содержатся координаты вершин отсеченного многоугольника 91.92,93,94,95,96,97, в счетчике 11 адреса - число его вершин, Триггер 7 флага видимости выдает на выходе 32 сигнал частичной видимости многоугольника, а ТКО 8 на выходе 31 - сигнал окончания работы.Рассмотрим остальные возможные варианты функционирования устройства, когда блок управления 18 находится в состоянии а 6,Ребро (1132) (фиг. 8) имеет три точки пересечения; две видимые с границами УВ,ХГ 1 и одна невидимая вне окна с границей ХЛ. Блок управления 18 перейдет в состояние аб после вычисления координа 1 средней точки кЗ, Содержимое первого РПР 411и второго РПР 412 следующее:РПР 411 1 р 2 р 4 р 5 р 7 р 8 р 10 р 11 р1 0 0 1 0 1 1 0РПР 412 0 1 1 110На выходе признака "0" (ПН 1) АЛУ 403БОП 13 установится сигнал, указывающий, что средняя точка является точкой пересечения ребра с границей УВ, На выходе 272 15 БАП 17, соответствующему первому выходудешифратора Ф 7, по сигналам, поступающим на входы 249-260 через шину 23 с выходов 153-164 БОП 13. установится сигнал.поступающий на вход 294 БУ 18, и указыва ющий, что невидима первая часть ребра,Точка кЗ является первой точкой пересечения ребра с окном, ее координаты остаются в пятом. шестом регистрах РОН 6, Блок управления переходит в состояние а 8, при 25 этом на его выходах 371, 375, 383 устанавливаются сигналы У 45, У 49, У 57, По сигналу У 45, поступающему по шине 27 на вход 210 БВП 15. взводится первый триггер 481 пересечения. По сигналам У 49, У 57, поступаю щим на входы 175, 183 БФПГ 14, в 1 разрядРП 454 запишется "1", указывающая на то, что найдено пересечение с границей УВ, Это осуществляется следующим образом: сигналы с выходов 157, 158 БОП 13 поступа ют на входы 185, 186 БФПГ 14 и формируютсигнал на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 426, поступающего через элементы ИЛИ 430, 446 на вход РП 454.В следующем такте работы блока управ ления выполняется разделение элементовустройства на две половины аналогично описанному для (14 ЛО), Блок управления переходит в состояние а 19 и запускается второй подавтомат. Блок управления перейдет 45 в состояние а 9 после завершения работыподавтомата, о чем свидетельствует сброшенное состояние второго триггера 480 запроса. Вычисление второй точки пересечения осуществляется на второй по лавине элементов, ее координаты записываются в седьмой, восьмой регистры РОН 6.Если вычисленной средней точкой окажется К 4 (фиг, 9), являющейся второй точкой пересечения, блок управления перейдет в состояние а 7. При этом сигнал о невидимости второй части ребра (М 4,Е 4) с второго выхода дешифратора 487, поступающий с выхода 273 БАП 17 нэ вход режима 295 БУ 18, формирует на его выходах 363, 366, 372,5 10 15 налам У 36, У 39 содержимое пятого, шестогорегистров РОН б перезаписывэется через коммутаторы 460, 462 в регистры 468, 470 20 25 30 35 40 45 50 55 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 РОН 6 по шине 22 через информационные входы 236, 237 и коммутаторы 463, 465 в тринадцатый, пятнадцатый регистры 471, 473. В следующем такте работы блока управления по сигналу У 44 на его выходе 370, поступающему на вход 77 считывания/записи РОН 6, содержимое регистров 471, 473 БВП 16 через сумматоры 477, 478 и выходы 242, 243 по шине 24 перезаписываются в седьмой, восьмой регистры РОН 6 по его входам 72, 73. Выполняется разделение элементов устройства. Блок управления переходит в состояние а 19 и запускает первый подавтомат. Вычисление первой точки пересечения части ребра (М 1 Л 4) с границей окна УВ осуществляется на первой половине элементов, как было описано в предыдущих вариантах,Если средняя точка анализируемого ребра (11,12) лежит вне окна, т.к. хотя бы один из разрядов второго РПР 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, корректируемые по ИЛИ сигналами на выходах признаков "0" АЛУ 403-406, пропускаются через вторые разряды коммутаторов признаков 407-410 и записываются в 2,5,8,11 разряды первого РПР 411 по управляющим сигналам У 65-У 68,Если установится сигнал на втором выходе дешифратора 487 (выход 273 БАП 17), поступающий на вход режима 295 БУ 18, то это значит, что вторая часть ребра невидима и необходимо проводить анализ его первой части, Признаки видимости вершины 12 в первом РПР 411 заменяются признаками видимости средней точки. Блок управления переходит такке; как и в предыдущем случае, в состояние а 4, При этом на его выходах 351, 352, 357-360, 362, 365 формируются сигналы У 25, У 26, У 31-У 34, У 36, УЗ 9. По сигБВП 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 БУ 18 и переводит его в состояние а 0. Г 1 ри этом на выходе 390 сформируется сигнал У 64, по которому взводится триггер 8 конца операции и устанавливается триггер 7 флага видимости в состояние соответствующее сигналу на выходе элемента И 417, т.е. он сбрасы вается - многоугольник невидим, Устройство заканчивает свою работу.В случае, когда многоугольник охватывает окно (фиг, 10) устройством выполняется занесение координат вершин окна 11, К 2, КЗ, К 4 в блок 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 численные значения пар границ окна УВ и ХП, УВ и ХП, УВ и ХЛ, УВ и ХЛ из регистра 5 окна поочередно передаются через коммутаторы 400, 402 БОП 13 и по сигналу У 47, проходя через АЛУ 405, 406 без вычитания, записываются в блок 4 памят по У 59. По сигналу У 61 содержимое счетчика 11 адреса увеличивается на "1". После записи четырех вершин блок управления переходит в состояние а 17.Считывание координат вершин отсеченного многоугольника с блока 4 памяти по первой выходной информационной шине 29 во внешнюю вычислительную систему осуществляется следующим образом, Внешняя вычислительная система устанавливает на пятом разряде шины 19 сигнал "пуск", по которому на выходе 328 БУ 18 устанавливается управляющий сигнал У 2 сбрасывающий счетчик 11 адреса в нулевое состояние. Затем на второй разряд шины 19 устанавливается сигнал ВП, а на четвертый разряд - сигналы ЧТ, по которым на выходе 43 РС 1 формируется последовательность сигналов, поступающая на вход режима 307 БУ 18 и на выходе 387 которого устанавливается сигнал У 61, увеличивающий содержимое счетчика 11 адреса на "1", Количество сигналов ЧТ должно быть равно количеству вершин отсеченного многоугольника.Блок управления может быть построен любым из известных способов в соответствии с приведенным алгоритмом функционирования устройства, Для объяснения работы устройства на фиг. 6 приведен один из вариантов построения такого блока, В качестве подавтоматов используются распределители сигналов. Список управляющих сигналов приведен в таблице. В предлагаемом устройство блоки памяти могут быть реализованы на элементах серии К 565, а остальные схемы на элементах серий К 155, К 531, К 555.Время отсечения многоугольника на устройстве - прототипе может быть оценено по формулеТ 1 = пс 1 + цт 1 + 11 т 2 +Зтбп=10где и - количество вершин отсекаемого многоугольника;ц - количество вершин многоугольникапосле отсечения двумя параллельными границами;в И - количество пересечений с границами окна;11 - время анализа одной вершины иребра на видимость;12 - время вычисления координат точкипересечения;1 бп - время перезаписи вершин в блокпамяти,Время отсечения многоугольника на заявляемом устройстве оценивается по формулеТ 2 = пт 1 + К 2 т 2+ 112,30 где Е 2 - количество одиночных пересечений(при наличии одного пересечения вектора с окном);1 - количество двойных пересечений(при пересечении вектора с двумя границами окна).Среднее время вычисления координатточки пересечения при шестнадцатиразрядном формате чисел можно оценить как 12 = 5 т 1. Как правило, отображаемый объект ап проксимируется плоскими гранями с 4,5 или6 вершинами, в среднем - пятиугольником, Тогда временные затраты на отсечение пятиугольников при различных вариантах их расположения относительно окна можно 45 оценить как:1. если невидимый пятиугольник находится над границей УВ.Т 1 = 2 кбс 1 +31 бп = 121 + Зтбп50Т 2 = бс 12. если невидимый пятиугольник находится справа от границыТ 1 = 26 т 1 + 2 хб 1 + ЗЪ = 241 ++Зтбп,Т 2 = 6113. если пятиугольник пересекает окнотаким образом, что на каждой границе будет по две точки пересеченияГ 1.= 2"611+ 2 7114124124 3 я .= ббс 131 -иТ 2 =- бт 1+ 4 т 2 - -26114. для пятиугольника на фиг. 8.Т 1 = 2,6 т 1 + 28 т 1 + 4 т 2 + 2 т 2 ++Зъ =- 58 т 1 + ЗтьТ 2 = бт 1 + Зс 2 =- 21 т 1Иэ приведенных оценок видно, что быстродействие предлагаемого устройства будет в 2-3 раза выше, чем у прототипа, за счет соответствующей организации параллельного процесса и вычисления координат только тех точек пересечения с границами окна, которые не выходят за пределы окна.Технический эффект от применения и редлагаемого устройства отсечения многоугольника для графического дисплея достигается за счет увеличения быстродействия работы устройства, и как следствие, снижение требований к производительности внешней вычислительной системы и улучшении качества воспроизведения визуальной информации о движущихся с большой скоростью телах.Формула изобретенияУстройство отсечения многоугольника для графического дисплея, содержащее первый и второй блоки памяти, блок регистров общего назначения, распределитель сигналов, регистр вершин, регистр окна, триггер флага видимости, триггер конца операции, триггер вершины, первый и второй счетчики адреса и блок управления, причем информационный вход устройства подключен к информационным входам первого блока памяти и регистра вершин, первый управляющий вход устройства подключен к первому управляющему входу распределителя сигналов и к первому входу режима блока управления, второй управляющий вход устройства подключен к второму управляющему входу распределителя сигналов, третий управляющий вход устройства подключен к третьему управляющему входу распределителя сигналов, четвертый управляющий вход устройства подключен к четвертому управляющему входу распределителя сигналов, пятый управляющий вход устройства подключен к второму входу рекима блока управления. первый и второй выходы распределителя сигналов подключены соответственно к входу считывания" записи регистра вершин и к входу считывания-записи регистра окна. третий выход распределителя сигналов подключен к входу записи первого блока памяти и к третье му входу режима блока управления,четвертый выход распределителя сигналов подключен к четвертому входу режима блока управления и к входу чтения второго блока памяти, выход регистра вершин 1 О подключен к пятому входу режима блокауправления, выходы первого и второго счетчиков адреса подключены соответственно к адресным входам первого и второго блоков памяти, первый и второй выходы первого 15 блока памяти подключены соответственно кпервому и второму информационным входам блока регистров общего назначения, первый выход блока управления подключен к входу установки в "1" триггера вершины, к 2 О входам установки в "О" первого счетчикаадреса и триггера конца операции, второй выход блока управления подключен к входу установки в "О" второго счетчика адреса, третий выход блока управления подключен 25 к первому входу считывания-записи блокарегистров общего назначения и к входу ус-.тановки в "О" триггера вершины, выход которого подключен к шестому входу режима блока управления, четвертый и пятый выхо- ЗО ды блока управления подключены соответственно к счетным входам первого и второго счетчиков адреса, шестой выход блока управления подключен к входу установки в 1"триггера конца операции и к управляющему З 5 входу триггера флага видимости, седьмойвыход блока управления подключен к входу чтения первого блока памяти и к второму входу считывания-записи блока регистров общего назначения, восьмой выход блока 4 О управления подключен к входу записи второго блока памяти, девятый и десятый выходы блока управления подключены соответственно к третьему и четвертому входам считывания-записи блока регистров общего 45 назначения, отл и ча ю щеес я тем, что,с целью повышения быстродействия, оно содержит блок определения признаков, блок формирования признаков границ, первый и второй блоки вычисления пересече О ний, блок анализа признаков и дешифратор,причем информационный вход устройства подключен к информационному входу регистра окна, выходы с первого по четвертый которого подключены соответственно к ин формационным входам с первого по четвертый первой группы блока определения признаков, первый и второй выходы которого подключены к первому и второму информационным входам второго блока памяти, стретьего по десятый вьходы блока определения признаков подключены соответственно к информационным входам с первого по восьмой блока анализа признаков, выходы с одиннадцатого по восемнадцатый блока определения признаков подключены соответственно к информационным входам с первого по восьмой блока формирования признаков границ и соответственно к информационным входам с девятого по шестнадцатый блока анализа признаков, девятнадцатый выход блока определения признаков подключен к первому информационному входу блока управления и к информационному входу триггера флага видимости, первый и второй входы блока регистров общего назначения подключены соответственно к первому и второму информационным входам первого блока вычисления пересечения, третий и четвертый :выходы блока регистров общего назначения подключены соответственно к третьему и четвертому информационным входам блока регистров общего назначения, соответственно к первому и второму информационным входам блока определения признаков и соответственно к третьему и четвертому информационным входам первого блока вычисления пересечения, пятый и шестой выходы блока регистров общего назначения подключены соответственно к третьему и четвертому информационным входам блока определения признаков соответственно к пятому и шестому информационным входам первого блока вычисления пересечения и соответственно к первому и второму информационным входам второго блока вычисления пересечения, седьмой и восьмой выходы блока регистров общего назначения подключены соответственно к пятому и шестому информационным входам блока определения признаков и соответственно к третьему и четвертому информационным входам второго блока вычисления пересечения, выход второго счетчика адреса подключен к первому информационному выходу устройства и к входу дешифратора, выход которого подключен к седьмому входу режима блока управления, с первого по четвертый выходы первого блока вычисления пересечения подключены соответственно к второму информационному входу устройства управления, к семнадцатому информационному входу блока анализа признаков, к пятому и шестому информационным входам блока регистров общего назначения, с первого по четвертый выходы второго блока вычисления пересечения подключены соответственно к третьему информационному входу блока управления, к восемэ,.,цэтсму информационному входу блока анализа признаков, к седьмому и восьмому информационным входам блока регистров общего назначения, выходы с первого по двенадцатый блока формирования признаков границ подключены соответственно к информационным входам с четвертого по пятнадцатый блока управления, выходы с первого по 1 О двадцать первый блока анализа признаковподключены соответственно к входам режима с восьмого по двадцать восьмой блока управления, пятый и шестой выходы первого блока вычисления пересечения подклю чен соответственно к пятому и шестомуинформационным входам второго блока вычисления пересечения, выход второго блока памяти подключен к второму информационному выходу устройства, выходы флага ви- О димости и конца операции которогоподключены соответственно к выходам триггера флага видимости и триггера конца операции, первый выход блока управления подключен к первому управляющему входу 25 блока определения признаков, третий выход блока управления подключен к второму управляющему входу блока определения признаков, одиннадцатый, двенадцатый и тринадцатый выходы блока управления под О ключены соответственно к первым управляющим входам формирования признакс в границ, первого и второго блоков вычисления пересечения, четырнадцатый и пятнадцатый выходы блока управления подключены 35 соответственно к третьему и четвертому управляющим входам блока определения признаков, выходы с шестнадцатого по девятнадцатый блока управления подключены соответственно к управляющим входам с 4 О пятого по восьмой блока определения признаков и соответственно к управляющим входам с второго по пятый блока формирования признаков границ, выходы с двадцатого по двадцать второй блока управления подключе ны соответственно к управляющим входам сдевятого по одиннадцатый блока определения признаков, выходы с двадцать третьего по двадцать шестой блока управления подключены соответственно к управляющим вхо дам с двенадцатого по пятнадцатый блокаопределения признаков и соответственно к управляющим входам с шестого по девятый блока формирования признаков границ, двадцать седьмой и двадцать восьмой выхо ды блока управления подключены соответственно к шестнадцатому и семнадцатому управляющим входам блока определения признаков, двадцать девятый выход блока управления подключен к восемнадцатомусодержащий процессор преобразования координат, три регистра приращений по координатам Х, У, 7, арифметико-логическое устройство, регистр общего назначения, регистр окна, первый и второй блоки памяти, 5 регистр кодов знаков, регистр признаков отсечения, схема хранения начальных условий, схема формирования признаков отображения, схема характеристик вектора, первый - пятый регистр, цифровой дифференциальный анализатор, причем вход процессора преобразования координат подключен к входу устройства, а его выход к первому регистру, выход которого соединен с входами пятого регистра, регистр окна и арифметико-логического устройства, второй вход которого соединен с первым выходом регистра общего назначения, а первый выход подключен к входам регистра общего назначения, первого и второго блоков памяти, второго и третьего регистров, второй выход арифметика-логического устройства подключен ко входам регистра признаков отсечения, регистра кодов знаков, второй выход регистра общего назначения соединен с входами трех регистров приращений по Х, У, Л, выходы которых подключены соответственно к третьему, четвертому и пятому входам арифметикологического устройства, выход регистра признаков отсечения подключен к первому выходу устройства, выход регистра кодов знаков соединен со входом схемы анализа вершин, выход которой подключен соответственно ко входам схемы хранения начальных условий, схемы формирования признаков отображения и схемы характеристик вектора, выход схемы хранения начальных условий соединен со вторым входом схемы характеристик вектора, выход схемы формирования признаков отображения соединен со вторым выходом устройства, выходы с первого по четвертый схемы характеристик вектора соединены с выходами с третьего по шестой устройства, выходы третьего регистра, первого и второго блока памяти подключены к соответствующим входам четвертого регистра, а выходы второго и четвертого регистров подключены к шестому и седьмому входам арифметикологического устройства и соответствующим входам пятого регистра. выход которого подключен ко входу цифрового дифференциального анализатора. выход которого подключен к седьмому выходу устройства,10 15 щего назначения, распределитель сигналов, регистр вершин, регистр окна, триггер 20 25 30 35 40 45 50 55 В известном устройстве операция отсечения выполняется последовательно парами параллельных границ окна, при этом вычисление пересечений в случае, когда ребро многоугольника пересекает сразу двеграницы окна. выполняется также последовательно, за счет чего снижается быстродействие устройства,Целью изобретения является повышение быстродействия устройства за счет одновременного анализа расположения ребер относительно четырех границ окна, параллельного вычисления двух точек пересечения и наличия схемных решений замыканиям ногоу гол ь ни ка. Поставленная цель достигается тем, что предложенное устройство содержит первый и второй блоки памяти, блок регистров обфлага видимости, триггер конца операции,триггер вершины, первый и второй счетчики адреса, дешифратор, блок определения признаков, блок формирования признаков границ, первый и второй блоки вычисления пересечений, блок анализа признаков и блок управления, причем информационный вход устройства подключен к информационным входам первого блока памяти и регистра вершин, первый управляющий вход устройства подключен к первому управляющему входу распределителя сигналов и к первому входу режима блока управления, второй управляющий вход устройства подключен ко второму управляющему входу распределителя сигналов, третий управляющий вход устройства подключен к третьему управляющему. входу распределителя сигналов, четвертый управляющий вход устройства подключен к четвертому управляющему входу распределителя сигналов,пятый управляющий вход устройства подключен к второму входу режима блока управления, первый и второй выходы распределителя сигналов подключены соответственно ко входу считывания/записи регистра вершин и к входусчитывания/записи регистра окна, третий выход распределителя сигналов подключен к входу записи первого блока памяти и к третьему входу режима блока управления, четвертый выход распределителя сигналов подключен к чет- вертому входу режима блока управления и к входу чтения второго блока памяти, выход регистра вершин подключен к пятому входу режима блока управления, выходы первого и второго счетчиков адреса подключены соответственно к адресным входам первого и второго блоков памяти, первый и второй выходы первого блока памяти подключены соответственно к первому и второму информационным входам блока регистров общего назначения, первый выход блока управления подключен к входу установки в единицу40 1777151 управляющему входу блока определения признаков и к второму управляющему входу первого блока вычисления пересечения. выходы с тридцатого по сороковой блока управления подключены соответственно к управляющим входам с девятнадцатого по двадцать девятый блока определения признаков, сорок первый выход блока управления подключен к третьему управляющему входу первого блока вычисления пересечения, к второму управляющему входу второго блока вычисления пересечения и к управляющему входу блока анализа признаков, выходы с сорок второго по пятьдесят второй блока управления подключены соответственно к четвертому управляющему входу первого блока вычисления пересечения, к третьему управляющему входу второго блока вычисления пересечения, к пятому управляющему входу первого блока вычисления пересечения, к управляющим входам с чет- управляющие Упр. сиг-Номер вы- нал хода УА 18 Список элементов 2501, 512501, 512501,502,539501, 544, 565501, 545, 567651503651502,540вертого по седьмой второго блока вычисления пересечения, к шестому управляющему входу первого блока вычисления пересечения, к восьмому управляющему входу второго блока вычисления пересечения, к тридцатому управляющему входу блока определения признаков, к девятому управляющему входу второго блока вычисления пересечения, выходы с пятьдесят третьего 10 по шестьдесят второй блока управленияподключены к управляющим входам с десятого по девятнадцатый блока формирования признаков границ, выходы с шестьдесят третьего по шестьдесят восьмой блока уп равления подключены соответственно кседьмому управляющему входу первого блока вычисления пересечения, к десятому управляющему входу второго блока вычисления пересечения и к управляющим вхо дам с тридцать первого по тридцатьчетвертый блока определения признаков. сигналытриггера вершиньь к ходам установки в ноль первого счетчика адреса и триггера конца операции, второй выход блока управления подключен к входу установки в ноль второго счетчика адреса, третий выход блока управления подключен к первому входу считывания/записи блока регистров общего назначения и к входу установки в ноль триггера вершины, выход которого подключен к шестому входу режима блока управления, четвертый и пятый выходы блока управления подключены соответственно к счетным входам первого и второго счетчиков адреса, шестой выход блока управления подключен к входу установки в единицу триггера конца операции и к управляющему входу. триггера флага видимости, седьмой выход блока управления подключен ко входу чтения первого блока памяти и к второму входу считывания/записи блока регистров общего назначения. восьмой выход блока управления подключен к входу записи второго блока памяти, девятый и десятый выходы блока управления подключены соответственно к третьему и четвертому входам считывания/записи блока регистров общего назначения, информационный входустройства подкл очен к информационному входу регистра окна, выходы с первого по четвертый которого подключены соответственно к информационным входам с первого по четвертый первой группы блока определения признаков, первый и второй выходы которого подключены к первому и второму информационным входам второго блока памяти, с третьего по десятый выходы блока определения признаков подключены соответственно к информационным входам с первого по восьмой блока анализа признаков, выходы с одиннадцатого по восемнадцатый блока определения признаков подключены соответственно к информационным входам с первого по восьмой блока формирования признаков границ и соответственно к информационным входам с девятого по шестнадцатый блока анализа признаков, девятнадцатый выход блока определения признаков подключен к первому информационному входу блока управления и к информационному входу триггера флага видимости, первый и второй выходы блока регистров общего назначения подключены соответственно к первому и второму информационным входам первого блока вычисления пересечения, третий и четвертый выходы блока регистров общего назначения подключены соответственно к третьему и четвертому информационным входам блока регистров общего назначения, соответственно к первому и второму информацион ным входам блска о зределения признаков и соответственно к третьему .л четвертому информационным входам первого блока вычисления пересечения, пятый и шестой выходы блока регистров общего назначения подключены соответственно к третьему и четвертому информационным входам блока определения признаков, соответственно к пятому и шестому информационным входам первого блока вычисления пересечения и 5 10 соответственно к перволу и второму информационным входам второго блока вычисления пересечения, седьмой и восьмой выходы блока регистров общего назначения подключены соответственно к пятому и шестому информационным входам блока определения признаков и соответственно к третьему и четвертому информационным входам второго блока вычисления пересечения, выход второго счетчика адреса подключен к первому информационному выходу устройства и к входу дешифратора, выход которого подключен к седьмому входу режима блока управления, с первого по четвертый выходы первого блока вычисления 30 блока регистров общего назначения, с первого по четвертый выходы второго блока вычисления пересечения подключены соответственно к третьему информационному входу блока управления, к восемнадцатому 35 информационному входу блока анализа признаков, к седьмому и восьмому информационным входам блока регистров общего назначения, выходы с первого по двенадцатый блока формирования признаков границ 40 подключены соответственно к информационным входам с четвертого по пятнадцатый блока управления. выходы с первого по двадцать первый блока анализа признаков 45 подключены соответственно к. входам режима с восьмого по двадцать восьмой блока управления, пятый и шестой выход первого блока вычисления пересечения подключен соответственно к пятому и шестому информационным входам второго блока вычисления пересечения, выход второго блока памяти подключен к второму информационному выходу устройства, выходы флага видимости и конца операции которого подключены соответственно к выходам триггера флага видимости и триггера конца операции, первый выход блока управления подключен к первомууправляющему входу блока определения признаков, третий выход блока управления подключен к второму 50 55 пересечения подключены соответственно ко второму информационному входу устройства управления, к семнадцатому информационному входу блока анализа признаков, к пятому и шестому информационным входам1777151 С)с. г, 1 ДСоставитель О,Аксентьеваедактор Н,Никольская Техред М,МоргенталКорректор С.Лисина Тираж Подписноенного комитета по изобретениям и открытиям при Г 3035, Москва, Ж, Раушская наб., 4/5 изводственно-издательский комбинат "Патент", г, Ужгород. ул.Гагарина. аказ 4123ВНИИПИ ГосударствеКНТ ССуправляющему входу блока определения признаков, одиннадцатый, двенадцатый и тринадцатый выходы блока управления подключены соответственно к первым управляющим входам формирования признаков границ, первого и второго блоков вычисления пересечения, четырнадцатый и пятнадцатый выходы блока управления подключены соответственно к третьему и четвертому управляющим входам блока определения признаков, выходы с шестнадцатого по девятнадцатый блока управления подключены соответственно к управляющим входам с пятого по восьмой блока определения признаков и соответственно к управляющим входам с второго по пятый блока формирования признаков границ, выходы с двадцатого по двадцать второй блока управления подключены соответственно к управляющим входам с девятого по одиннадцатый блока определения признаков, выходы с двадцать третьего по двадцать шестой блока управления подключены соответственно к управляющим входам с двенадцатого по пятнадцатый блока определения признаков и соответственно к управляющим входам с шестого по девятый блока формирования признаков границ, двадцать седьмой и двадцать восьмой выходы блока управления подключены соответственно к шестнадцатому и семнадцатому управляющим входам блока определения признаков, двадцать девятый выход блока управления подключен к восемнадцатому управляющему входу блока определения признаков и ко второму управляющему входу первого блока вычисления пересечения. выходы с тридцатого по сороковой блока управления подключены соответственно к управляющим входам с девятнадцатого по двадцать девятый блока определения признаков, сорок первый выход блока управления подключен к третьему управляющему входу первого блока вычисления пересечения, к второму управляющему входу второго блока вычисления пересечения и к управляющему входу блока анализа признаков, выходы с сорок второго по пятьдесят второй блока управления подключены соответственно к четвертому управляющему входу первого блока вычисления пересечения, к третьему управляющему входу второго блока вычисления пересечения, к пятомууправляющему входу первого блока определения пересечения, к управляющим входам с четвертого по седьмой второго блока вычисления пересечения, к шестому управляющему входу первого блока вычисления пересечения, к восьмому управляющему входу второго блока вычисления пересечения, кпересечения, выходы с пятьдесят третьего5по шестьдесят второй блока управления подключены к управляющим входам с деся 10 15 20 25 дельных ребер окном 30 35 50 рую выходную информационную шину 30,выход 31 конца операции и выход 32 флага видимости, первый-четвертый управляющие входы 33-36 и первый-седьмой выходы 37-43 распределителя 1 сигналов, вход счи 55 40 45 тридцатому управляющему входу блока определения признаков, к девятому управляющему входу второго блока вычисления того по девятнадцатый блока формирования признаков границ, выходы с шестьдесят третьего по шестьдесят восьмой блока управления подключены соответственно к седьмому управляющему входу первого блока вычисления пересечения, к десятому управляющему входу второго блока вычисления пересечения и к управляющим входам с тридцать первого по тридцать четвертый блока определения признаков. На фиг. 1 представлена блок-схема устройства отсечения многоугольника для графического дисплея; на фиг, 2 - блок-схема блока определения признаков; на фиг, 3 - блок-схема блока формирования признаков границ; на фиг. 4 - блок-схемы первого и второго блоков вычисления пересечений; на фиг. 5 - блок-схема блока анализа признаков; на фиг, 6. - блок-схема блока управления; на фиг. 7-10 - примеры для объяснения операции отсечения многоугольника и отУстройство (фиг, 1) содержит первый распределитель 1 сигналов (РС), регистр 2 вершин (РВ), блоки 3,4 первой и второй памяти (БП), регистр 5 окна, блок регистров 6 общего назначения (РОН), триггер 7 флага видимости (ТФВ), триггер 8 конца операции (ТКО) и триггер 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 10 15 20 25 30 35 40 45 50 55 вход 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 первого счетчика 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 подключены соответственно ко входам 141, 142 БОП 13 и к информационным входам 214, 215 БВП 15, выходы 82, 83 РОН 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, выходы 157- 164 подключены соответственно к информационным входам 185-192 БФПГ 14, а выход 165 соединен с информационным входом 284 БУ 18 и с информационным входом 86 триггера 7 флага видимости, управ1777151 10 15 20 25 30 35 40 50 ляющий вход 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 БВП 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, первый- четвертый двухразрядные коммутаторь 1 признаков 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, первый и второй триггеры запросов (ТЗП 1, ТЗП 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, первь 1 й-девятый элементы ИЛИ восьмой группы 565-573, первый-шестой элементы И десятой группы 574-579, первый-двенадцатый элементы ИЛИ девятой группы 580-591, первый-восьмой элементы И одиннадцатой группы 592-599, первый-тринадцатый элементы ИЛИ десятой группы 600-612, первый-четвертый элементы И двенадцатой группы 613-616, первый-четвертый элементы ИЛИ одиннадцатой группы 617-620, пер 55 вый-четвертый триггеоы второй группы 621-624, первый-четвертый элементы И тринадцатой группы 625-628, первый-четвертый элементы ИЛИ двенадцатой группы 629-632, первый-четвертый элементы ИЛИтринадцатой групг ы 633-636. третий дешифратор 637, второй- етвертый распределители сигналов 630-640, первый-пятый элементы ИЛИ четырнадцатой группы 641- 645, первый-пятый триггеры третьей группы 5 646-650, четвертый дешифратор 651, второй триггер 652, третий элемент ИЛИ 653, второй элемент И 654, генератор тактовых импульсов 655 и соответствующие связи между указанными элементами блока, Блок 10 управления функционально состоит из управляющего автомата с состояниями а 1 и двух подавтоматов с состоянием Ь 1 и д 1 соответственно.Первый распределитель 1 сигналов 15 предназначен для формирования сигналов, разрешающих запись исходных данных иэ внешней вычислительной системы в устройство.Регистр 2 вершин предназначен для 20 хранения числа вершин отсекаемого много- угол ьни к а.Первый и второй блоки 3.4 памяти предназначены для хранения координат вершин вводимого и отсеченного многоугольника 25 соответственно, причем первая половина слова (его младшие разряды) - координата Х, вторая половина слова (его старшие разряды) - координата У.Регистр 5 окна предназначен для хра нения численных значений границ окна; верхней - УВ, правой - ХП, нижней - УН, левой - ХЛ.Блок регистров б общего назначения включает в себя восемь регистров. Первый 35 и второй регистры предназначены для хранения значений координат начальной (или предыдущей) вершины ребра многоугольника; третий и четвертый регистры - значений координат конечной (или текущей) вершины 40 ребра многоугольника; пятый и шестой регистры - координат первой точки пересечения, седьмой и восьмой регистры координат второй точки пересечения.Триггеры 7.8 формируют сигналы, ука эывающие на полную или частичную видимость многоугольника, а также на окончание операции отсечения.Триггер 9 сигнализирует об обработке первой вершины многоугольника. 50Счетчики 10.11 предназначены для формирования адресов соответственно блоков 3,4 памяти.Блоком 13 определения признаков вычисляются признаки видимости текущей 55 вершины многоугольника относительно окна, одновременно по четырем границам. Если вершина видима. устанавливается признак "1", если нет - "0". Они хранятся на первом регистре признаков (РПР 1 411 который состоит из четырех сек.ий по три разряда в каждой. В 2,5.8,11 разрядах хранятся признаки предыдущей вершины соответственно по каждой границе УВ, ХП. УН, ХЛ. Аналогично в 1 и 3, 4 и б, 7 и 9, 10 и 12 разряды записываются признаки видимости текущей вершины. Перед анализом последующей вершины выполняется сдвиг первого РПР влево и признаки видимости текущей вершины (содержимое разрядов 3,6,9,12) займут место признаков видимости предыдущей вершины.Блок 14 формирования признаков границ предназначен для запоминания на четырехразрядных регистрах 454-456 признаков границ (ПГ), с которыми пересекается анализируемое ребро многоугольника, признаков границ предыдущего пересечения и признаков границ начального пересечения. Формирование этих признаков осуществляется на первой-четвертой группах элементов И, каждая из которых содержит по четыре элемента в соответствии с числом границ окна. На первой, второй группе элементов И формируются признаки границ соответствующих первому и второму пересечению при их поиске по четырем границам, На третьей-четвертой группе элементов И формируются признаки границ соответствующих первому и второму пересечению, при их поиске по двум границам (возможно одновременно).Блоки 15,16 предназначены для вычисления координат точки пересечения ребра с одной границей или двумя одновременно.Блок 17 анализа признаков используетсяя для анализа видимости ребра многоугольника или его части в процессе вычисления координат точек пересечения,Блок управления 18 предназначен для формирования управляющих сигналов (У) в соответствии с алгоритмом функционирования устройства отсечения многоугольника для графического дисплея. Подавтоматы блока управления предназначены для формирования управляющих сигналов при вычислении точки пересечения ребра с произвольной границей окна, В случае необходимости вычисления двух пересечений подавтоматы работают параллельно,Работа устройства задается алгоритмом его функционирования и описывается на примере отсечения пятиугольника (фиг. 7), заданного своими вершинами Ю, И, 12, 13.14, Ю с координатами ХОУО, Х 1 У 1, Х 2 У 2, ХЗУЗ. Х 4 У 4, ХОУО окном с граничными линиями УВ, ХП, УН, ХЛ. Устройством выполняется анализ каждого ребра многоугольника на видимость относительно окна, при необхо 1777151 16димости, вычисление пересечений и проверка многоугольника на замыкание,До запуска устройства производится загрузка иэ внешней вычислительной системы числа вершин в регистр 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 РС 1, на выходе 37 которого установится сигнал, разрешающий запись в регистр 2 вершин числа вершин. По второму сигналу ВП и сигналам ЗП на выходе 38 РС 1 формируется последовательность сигналов, разрешающих запись в первый блок 3 памяти координат вершин многоугольника, поступающих от внешней вычислительной системы по входной информационной шине 20. Сигнал с выхода 38 РС 1 поступает на вход ренсима 308 БУ 18 и на его выходе 386 устанавливается У 60, увеличивающий содержимое первого счетчика 10 адреса на "1". По третьему сигналу ВП и четырем сигналам ЗП на втором и третьем разрядах входной управляющей шины 19 на выходах 39-42 РС 1 устанавливаются поочередно сигналы. разрешающие запись численных значений границ окна, поступающих с входной информационной шины 20 на информационный ход 57 регистра 5 окна в порядке УВ, ХП, УН, ХЛ, Внешняя вычислительная система устанавливает на пятом разряде шины 19 сигнал "пуск", который поступает на вход режима 312 БУ 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 разряды первого РПР 41.1) по управляющим сигналам У 31- У 34. Одновременно признаки поступают на элементы ИЛИ первой группы 413-416, сиг налы на выходах которых принимаются втриггеры первой группы 418-421 по У 8, Блок управления переходит в состояние аЗ (сигнал на четвертом выходе четвертого дешифраторэ 651). 5 101520253035 равляющие сигналы У 1-У 5, У 64, по которым первый и второй счетчики 10,11 адресов, триггеры предыдущего пересечения 458 в БФПГ 14, конца операции 8, первого и второго запросов 479; 480 в БВП 15,16, первой группы 418, 421 в БОП 13 сбрасываются, а триггер 9 вершины устанавливаются в единицу, Блок управления переходит в состояние а 1 (сигнал на втором выходе четвертого дешифратора 651),В последующих тактах работы устройства вычисляются признаки видимости текущей вершины относительно четырех границ одновременно и выполняется анализ видимости ребра многоугольника относительноокна. На выходе 332 БУ 18 установится сигнал Уб, поступающий на вход чтения 49 блока 3 памяти, разрешая считывание координат первой вершины Ю с его выхода 51, и на вход считывания/записи 75 РОН 6,разрешая запись этих координат по входам 68, 69 в третий, четвертый регистры РОН б. Блок управления переходит в состояние а 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 передаются координаты вершины 10, УО, ХО, УО,ХО с выходов 81, 80 РО Н 6 по шине 22 черезвходы 142, 141 схемы. На вторые входы АЛУ 403-406 с выходов 62-65 регистра 5 окна по10 установится 15 20 25 30 35 40 45 50 55 В следующем такте анализируется состояние триггера 9 вершины, который был установлен вначале в "1", что говорит об обработке первой вершины. Блок управления переходит в состояние а 16, при этом содержимое счетчика 498 вершин в БУ 18 уменьшится на "1" по У 69 и станет равным памяти. Так как содержимое счетчика не ноль, на выходе дешифратора 499 сигнал не На выходах 333, 386 БУ 18 формируются сигналы У 7, У 60, Управляющий сигнал У 7 сбрасывает триггер 9 вершины по входу 93, разрешает сдвиг влево на 1 разряд первого РПР 411, поступая на управляющий вход 104 БОП 13. При этом признаки видимости вершины Ю, хранящиеся в 3,6,9,12 разрядах перезапишутся соответственно в 2,5,8,11 разряды. Он же разрешает пеоезапись содержимого третьего, четвертого регистров в первый, второй с выходов 80, 81 на информационные входы бб, 67 РОН б, По сигналу У 60, поступающему на вход 96 счетчика 10 адреса, его содержимое увеличится на "1". Блок управления возвращается в состояние а 1 и, через а 2, в эЗ, При этом в третьем, четвертом регистрах РОН б будут храниться координаты вершины И, а в 1 и 3, 4 и б, 7 и 9,10 и 12 разрядах первого РПР 411 БОП 13 признаки видимости вершины И, относительно четырех границ окна. Для ребра (Ю, И) содержимое этого регистра следующее: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 и затем через а 1, а 2 и аЗ, аналогично описанному выше,В результате работы устройства в первый, второй регистры из третьего, четвертого регистра РОН б перезапишутся координаты вершины И, а в третий, четвертый регистры запишутся координаты вершины 2 с блока 3 памяти аналогично описанному выше, Для ребра (И,12) содержимое первого РПР 411 следующее:1 р 2 р 4 р 5 р 7 р 8 р 10 р 11 р1 0 1 1 1 1 .1 0Содержимое 1 и 2, 10 и 11 разрядов указывает на пересечение ребром (И,12) границ окна УВ, ХЛ. Содержимое первого РПР 411 через выходы 157-164 БОП 13, шину 23 и информационные входы 255-262 БАП 17 поступает на дешифратор 485. на третьем. пятом, шестом выходах которого установятся сигналы, указыва:ощие нэ видимость 12, на наличие пересечения и что их 2. Эти сигналы с выходов 267, 268, 269 блока 17 анализа признаков поступают на входы режима 289, 290, 291 БУ 18 и, в соответствии с ними, на его выходах 361, 362 формируются сигналы У 35, У 36. Управляющий сигнал У 35 поступает на управляющий вход 244 блока 17 анализа признаков, разрешая запоминание признака видимости конечной точки ребра 12 на триггере 491, а также на входы 207, 225 блоков 15,16 вычисления пересечения, сбрасывая в "0" триггеры 481, 482 пересечений и разрешая прохождение значений координат вершин И,12, соответственно Х 1, Х 2, У 1, У 2, с выходов 78-81 РОН б по шине 22 и входы 212, 215 через коммутаторы 459- . 462. Они записываются в регистры 467-470 по УЗб, поступающему на управляющий вход 208 блока 15. Блок управления переходит в состояние а 4 (сигнал на пятом выходе четвертого дешифраторэ 651),В следующих тактах функционирования устройства производится вычисление координат точки пересечения. Эта операция выполняется относительно границ окна путем определения средней точки. В том случае, когда анализ указь:вает на одну точку пересечения или средняя точка оказывается внутри окна при наличии пересечений с четырьмя, тремя, двумя границами, элементы устройства делятся на две половины. К первой половине относятся АЛУ 403, 404 с коммутаторами 395-398, 1-6 разряды первого РПР 411 с коммутаторами признаков 407, 4081 и 2 разряды второго РПР 412 БОП 13, первый блок 15 вычисления пересечения. На этих элементах вычисляется первое пересечение по направлению ребра. Ко второй половине относятся АЛУ 405, 406 с . коммутаторами 399-402, 7-12 разряды первого РПР 411 с коммутаторами 409, 410, 3,4 разряды второго РПР 412 БОП 13 и второй блок 16 вычисления пересечения, На этих элементах вычисляется второе пересечение.Так как при анализе ребра (И,2) триггер 491 в блоке 17 анализа признаков установился в "1", это указывает на то, что вершина 12 находится внутри кона, и значит из двух пересечений только одно будет с границей окна, а другое вне его. Координаты точки пересечения вычисляются на первой половине элементов устройства, следовательно в 1-6 разрядах первого РПР должны будут находится признаки видимости вершин ребра (И,12) относительно границ, с которыми у него пересечение.