Пристрій для обчислення швидких геометричних перетворень

Пристрій для обчислення швидких геометричних перетворень містить блок завдання вхідних параметрів, блок керування, перший, другий, третій блоки перетворення координат, перший, другий, третій логарифмічні перетворювачі, перший, др угий функціональні перетворювачі, перший, др угий адресні формувачі, блок формування лінії нескінченно віддалених точок, ви хід якого є першим виходом пристрою, блок пам'яті, перший інформаційний вихід блока завдання вхідних параметрів з'єднаний із дев'ятими входами першого, другого, третього блоків перетворення координат, другий інформаційний вихід з'єднаний з одинадцятими входами першого і другого адресних формувачів, від першого до четвертого керуючі виходи з'єднані з відповідними входами першого, другого і третього блоків перетворення координат, і четвертий також зв'язаний із дев'ятими входами першого і другого адресних формувачів, п'ятий і шостий виходи відповідно з третіми і четвертими їхніми входами, а перший вхід з'єднаний із п'ятим виходом блока керування, від другого до четвертого виходи якого з'єднані відповідно із шостими, сьомими і восьмими входами першого, другого, третього блоків перетворення координат, третіми входами першого, другого і третього логарифмічних перетворювачів, сьомими і десятими входами першого і другого адресних формувачів, шостими входами першого і другого функціональних перетворювачів і третього входу блока формування лінії нескінченно віддалених точок, перші і другі ви ходи першого логарифмічного перетворювача через перший функціональний перетворювач з'єднані з першим і другим входом першого адресного формувача, перший вихід другого блока перетворення координат з'єднаний із першими входами другого логарифмічного перетворювача і блока формування лінії нескінченно віддалених точок, перший і другий виходи третього логарифмічного перетворювача через другий функціо A (54) ПРИСТРІЙ ДЛЯ ОБЧИСЛЕННЯ ШВИДКИХ ГЕОМЕТРИЧНИХ П ЕРЕТВОРЕНЬ 36792 із другим входом першого підсумовувача і другого входу другого підсумовувача, ви хід якого через сьомий регістр з'єднаний із першим входом третього віднімача, другий вхід якого є дев'ятим входом, а вихід з'єднаний через одинадцятий регістр із другим входом другого блока порівняння, вихід якого через шостий тригер з'єднаний із третім входом елемента І, вихід якого з'єднаний із першим входом сьомого тригера, вихід якого є третім виходом пристрою, десятий вхід з'єднаний із третіми входами першого, третього і четвертого елементів затримки, другим входом другого елемента затримки, другими входами регістрів і другими входами тригерів, при цьому третій і четвертий інформаційні виходи блока завдання вхідних параметрів з'єднані відповідно з восьмим і дев'ятим входами блока відображення крапкових об'єктів, перший вихід першого блока перетворення координат з'єднаний із першим входом першого логарифмічного перетворювача і з четвертим входом блока відображення, перший вихід третього блока перетворення координат з'єднаний із першим вхо дом третього логарифмічного перетворювача і п'ятого входу блока відображення, перший і другий виходи друго го логарифмічного перетворювача з'єднані, відповідно, з п'ятими і четвертими входами першого і другого функціональних перетворювачів і шостим і сьомим входами блока відображення, виходи першого і другого адресних формувачів з'єднані, відповідно, із другим і третім входами блока відображення і з першим і другим входами блока пам'яті, вихід якого з'єднаний із першим входом блока відображення крапкових об'єктів і є другим виходом пристрою, перший вихід блока керування з'єднаний із другими входами першого, другого, третього логарифмічних перетворювачів і блока формування лінії нескінченно віддалених точок, п'ятими входами першого, другого і третього блоків перетворення координат, третіми входами першого і другого функціональних перетворювачів, шостими входами першого і другого адресних формувачів і десятого входу блока відображення крапкових об'єктів. Винахід відноситься до обчислювальної техніки, систем технічного зору, тренажерів різноманітного призначення, а також може бути використаний в телевізійній техніці. Відомо пристрій для формування динамічних зображень (див. а.с. СРСР №1109785 за МПК G09G 1/08, бюл. №31, 1984), що містить блок завдання вхідних параметрів і синхронізації, два блоки перетворення координат, формувач керуючих імпульсів, шини керуючого і вихідного сигналів. Найбільш близьким за сукупністю ознак є пристрій для обчислення швидких геометричних перетворень (див. пат. РФ №2020557 за МПК5 G06F 7/548, бюл. №18, 1994). Пристрій містить блок завдання вхідних параметрів, перший, другий, третій блоки перетворення координат, блок пам'яті, блок керування, перший, другий, третій логарифмічні перетворювачі, перший, другий функціональні перетворювачі, перший, другий адресні формувачі, блок формування лінії нескінченно віддалених точок. Описані аналог і прототип не забезпечують високу якість відображення крапкових світних об'єктів (КСО) через відсутність безупинного відображення крапкових об'єктів. В основу винаходу поставлено завдання створення пристрою для обчислення швидких геометричних перетворень, що за рахунок уведення блока відображення крапкових об'єктів і нових зв'язків забезпечив би постійне високоякісне відображення будь-якої кількості ТСО сцени на екрані. Такий технічний результат може бути досягнутий, якщо в пристрій для обчислення швидких геометричних перетворень, що містить блок завдання вхідних параметрів, блок керування, перший, другий, третій блоки перетворення координат, перший, другий, третій логарифмічні перетворювачі, перший, другий функціональні перетворювачі, перший, другий адресні формувачі, блок формування лінії нескінченно віддалених точок, вихід якого є першим виходом пристрою, блок пам'яті, перший інформаційний вихід блока зав дання вхідних параметрів з'єднаний із дев'ятими входами першого, другого, третього блоків перетворення координат, другий інформаційний вихід з'єднаний з одинадцятими входами першого і другого адресних формувачів, від першого до четвертого керуючі виходи з'єднані з відповідними входами першого, другого і третього блоків перетворення координат, і четвертий також з¢єднаний із дев'ятими входами першого і другого адресних формувачів, п'ятий і шостий ви ходи відповідно з третіми і четвертими їхніми входами, а перший вхід з'єднаний із п'ятим виходом блока керування, від другого до четвертого ви ходи якого з'єднані відповідно із шостими, сьомими і восьмими входами першого, другого, третього блоків перетворення координат, третіми входами першого, другого і третього логарифмічних перетворювачів, сьомими і десятими входами першого і другого адресних формувачів, шостими входами першого і другого функціональних перетворювачів і третього входу блока формування лінії нескінченно віддалених точок, перші і другі виходи першого логарифмічного перетворювача через перший функціональний перетворювач з'єднані з першим і другим входом першого адресного формувача, перший вихід др угого блока перетворення координат з'єднаний із першими входами другого логарифмічного перетворювача і блока формування лінії нескінченно віддалених точок, перший і другий виходи третього логарифмічного перетворювача через другий функціональний перетворювач з'єднані з першим і другим входами другого адресного формувача, другі виходи першого і третього блоків перетворення координат з'єднані з п'ятими входами відповідно першого і другого адресних формувачів, другий вихід другого блока перетворення координат з'єднаний із восьмими входами першого і другого адресних формувачів, відповідно до винаходу, введений блок відображення крапкових об'єктів, що містить блок обчислення полярного кута, блок обчислення полярних координат, перший віднімач, перший і другий 2 36792 підсумовувачі, блок обчислення логарифма синуса і косинуса, др угий і третій віднімачі, перший і другий блоки порівняння, елемент І, перший з'єднаний із четвертим і п'ятим входами, другий з'єднаний із першим входом, третій з'єднаний із другим і третім, четвертий з'єднаний із шостим і сьомим входами елементи затримки, одинадцять регістрів, послідовно з'єднані дешифратор відсутності об'єктів, перший, другий, третій і четвертий тригери, вихід останнього з'єднаний із першим входом елемента І, перший і другий виходи першого елемента затримки з'єднані відповідно з входами блока обчислення полярного кута, ви хід якого через перший регістр з'єднаний із першим входом першого віднімача, вихід якого через п'ятий регістр з'єднаний із входом блока обчислення логарифма синуса і косинуса, перший вихід якого з'єднаний через восьмий регістр із першим входом першого блока порівняння, а другий вихід з'єднаний через дев'ятий регістр із першим входом другого блока порівняння, вихід другого елемента затримки з'єднаний із входом дешифратора відсутності об'єктів і з першим входом блока обчислення полярних координат, другий і третій входи якого з'єднані із першим і другим виходами третього елемента затримки, перший вихід з'єднаний через другий регістр із другим входом першого віднімача, а другий – через третій регістр із першим входом другого підсумовувача і першого входу першого підсумовувача, ви хід якого через шостий регістр з'єднаний із першим входом другого віднімача, другий вхід якого являється восьмим , а вихід з'єднаний через десятий регістр із другим входом першого блока порівняння, вихід якого через п'ятий тригер з'єднаний із другим входом елемента І, перший і другий ви ходи четвертого елемента затримки з'єднані відповідно з першим і третім входами четвертого регістра, вихід якого з'єднаний із другим входом першою підсумовувача і другого входу другого підсумовуванч, ви хід якого через сьомий регістр з'єднаний із першим входом третього віднімача, другий вхід якого є дев'ятим входом, а вихід з'єднаний через одинадцятий регістр із другим входом другого блока порівняння, вихід якого через шостий тригер з'єдний із третім входом елемента І, вихід якого з'єднаний із першим входом сьомого тригера, вихід якого є третім виходом пристрою, десятий вхід з'єднаний із третіми входами першого, третього і четвертого елементів затримки, другим входом другого елемента затримки, другими входами регістрів і другими входами тригерів, при цьому третій і четвертий інформаційні виходи блока завдання вхідних параметрів з'єднані відповідно з восьмим і дев'ятим входами блока відображення крапкових об'єктів, перший вихід першого блока перетворення координат з'єднаний із першим входом першого логарифмічого перетворювача і з четвертим входом блока відображення, перший вихід третього блока перетворення координат з'єднаний із першим входом третього логарифмічного перетворювача і п'ятим входом блока відображення, перший і другий ви ходи др угого логарифмічного перетворювача з'єднані, відповідно, з п'ятим і четвертими входами першого і другого функціональних перетворювачів і шостим і сьомим входами блока відображення, виходи першого і другого адресних формувачів з'єднані, відповідно, із другим і третім входами блока відображення і з першим і другим входами блока пам'яті, вихід якого з’єднаний із першим входом блока відображення крапкових об’єктів і є другим виходом пристрою, перший вихід блока керування з'єднаний із другим входами першого, другого, третього логарифмічних перетворювачів і блока формування лінії нескінченно віддалених точок, п'ятими входами першого, другою і третього блоків перетворення координат, третіми входами першого і другого функціональних перетворювачів, шостими входами першого і другого адресних формувачів і десятого входу блока відображення крапкових об’єктів. Таким чином, введення блока відображення крапкових об'єктів, перший вхід якого є ви ходом блока пам'яті, другий і третій входи є виходами відповідно першого і другого адресних формувачів, че твертий і п'ятий входи є ви ходами відповідно першого і третього блоків перетворення координат, забезпечує постійне високоякісне відображення будь-якого числа крапкових об'єктів сцени на екрані. На фіг. 1 зображена структурна схема пристрою для обчислення швидких геометричних перетворень; па фіг. 2 зображена структурна схема блока відображення крапкових об'єктів; на фіг. 3 зображені геометричні елементи задачі для знаходження зони охоплення; на фіг. 4 зображені геометричні елементи задачі для визначення координат КСО. Пристрій для обчислення швидких геометричних перетворень містить блок 1 завдання вхідних параметрів, блок 2 керування, перший 3, другий 4, третій 5 блоки перетворення координат, перший 6, другий 7, третій 8 логарифмічні перетворювачі, перший 9, другий 10 функціональні перетворювачі, перший 11, другий 12 адресні формувачі, блок 13 формування лінії нескінченно віддалених точок, блок пам'яті 14, блок 15 відображення крапкових об'єктів. Блок 15 відображення крапкових об'єктів містить блок 16 обчислення полярного кута, блок 17 обчислення полярних координат, перший віднімач 18, перший 19 і другий 20 підсумовувачі, блок 21 обчислення логарифма синуса і косинуса, др угий 22 і третій 23 віднімачі, перший 24 і другий 25 блоки порівняння, елемент 26 І, перший 27, другий 28, третій 29 і четвертий 30 елементи затримки, одинадцять регістрів 31-41, дешифратор 42 відсутності об'єктів, перший 43, другий 44, третій 45 і четвертий 46 тригери, також тригери 47, 48, 49. Вхід 1 є входом коду графічного примітива (ГП), вхід 2 є входом координати Х усередині комірки, вхід 3 є входом координати Z усередині комірки, вхід 4 є входом Х-складової вектора спостереження, вхід 5 є входом Z-складової вектора спостереження, входи 6 і 7 є входами дробової і цілої частин відповідно логарифма Y-складового вектора спостереження, вхід 8 є входом константи LC1, вхід 9 є входом константи LC2, вхід 10 – входом синхронізації. Пристрій працює таким чином. Роботу пристрою розглянемо з моменту появи на другому і третьому виходах блока 2 керування імпульсів "Скидання рядкового імпульсу, що гасить, (РІГ)" і "Скидання кадрового імпульсу, що 3 36792 гасить (СІГ)", що встановлюють пристрій у вихідний стан, а також "Обмін", що ініціює передачу параметрів із блока 1 завдання вхідних параметрів (БЗВП). Кожний параметр, що виставляється БЗВП 1 на інформаційних вихода х 1 і 2, супроводжується парою керуючих сигналів по керуючи х ви ходах: перший установлює відповідний регістр у режимі "Прийом", другий синхросигнал "Запис" надходить на синхровходи усіх регістрів, призначених для зберігання параметрів, забезпечуючи їхній запис у регістри. По закінченні дії сигналу "Скидання КІГ" блок 2 керування починає видавати на одному із своїх ви ходів серію синхроімпульсів, що управляють обчислювальним конвеєром у пристрої. Часто та цих синхроімпульсів відповідає темпу промальовування пікселів на екрані телевізійного приймача. На кожний синхроімпульс на виході блока 14 пам'яті з'являється інформація, що відповідає пікселу екрана, у тому числі і інформація про розташування крапкових об'єктів. Після відображення чергового рядка блок 2 керування виробляє сигнал "Скидання РІГ", що установлює вузли пристрою в стан, що відповідає початку рядка, а потім формування кадру закінчується появою на виходах 2 і 3 блока 2 керування сигналів відповідно "Скидання РІГ" і "Скидання КІГ". Кожний із трьох блоків перетворення координат (БПК) 3, 4, 5 обчисляє координату проекційного променя. Логарифмічні перетворювачі 6, 7, 8 здійснюють апаратну реалізацію функції' двійкового логарифма. Призначення функціональних перетворювачів 9, 10 полягає у формуванні на першому ви ході значення функції 2k, а на другому виході d. Адресні формувачі (АФ) 11, 12 призначені для обчислення координат проекції елемента екрана на предметну площину. Блок формування лінії нескінченно віддалених точок (БФЛТ) 13 призначений для формування на екрані телевізійного приймача лінії обрію. Блок 2 керування призначений для синхронізації функціонування усього пристрою: ініціює передачу вхідних параметрів БЗВП, коли з'являється КІГ, і виробляє серію синхроімпульсів С1, що керують конвеєром протягом часу формування кадру. Блок відображення крапкових об'єктів призначений для визначення наявності в даному пікселі КСО сцени. æ1 ö L^ ÷ è2 ø LL ^ = log 2 ç В основу даного блока покладений алгоритм, у якому кожному пікселу екрана поставимо у відповідність так звану зону охоплення, розташовану на предметній площині. Зона охоплення є деякою апроксимацією проекції даного піксела. Алгоритм при такому підході складається з двох етапів: 1) визначення розмірів і положення зони охоплення, 2) вибір КСО, найближчого до центру зони і перевірка, чи потрапив він в зону. Визначимо зону охоплення (фіг. 3) як прямокутну область із центром у точці Р (точка перетинання проекційного променя для даного піксела з предметною площиною), орієнтовану так, що дві сторони прямокутника будуть перпендикулярні до проекційного променя даного піксела. Знайдемо сторони прямокутника. Зі співвідношень подоби: L ^ = L ^Z = де L^ H × DZ E Vy , L ^Y = H × DY E Vy ; (1) – поперечний розмір зони охоплення, DYE , D Z E – розміри піксела, Н – у-складова проек-ційного променя в g-системі, Vy – у-складова вектора спостереження в g системі. Подовжній розмір зони захоплення буде складати: L ^Y HV × D YE LP = = , (2) 2 sin q Vy r де V = n – модуль вектора спостереження, q – кут між проекційним променем і предметною площиною, sin q = V y V . При інших орієнтаціях екрана й інших напрямках вектора спостереження, використовуємо ті ж співвідношення (1) і (2). У них параметри V i V y беруться для кожного піксела. Знайдемо логарифм половини складової L^ : = log 2 (H × D Z E ) - 1 - log 2 V y = LC1 - LV y , У випадку, якщо параметр V протягом кадру змінюється незначно, він може бути визначений як де LC1 = log 2 ( H × DZ E ) - 1 – константа для кадру, LV y = log 2 V y – значения, одержуване для кожноконстанта. Тоді логарифм половини складової L p : го піксела в ході виконання центропроективного перетворення. æ1 ö LL p = log 2 ç L p ÷ = log 2 (HV × DYE ) - 1 - 2 log 2 Vy = LC2 - 2LVy , è2 ø позначається тією ж літерою, що і точка в її початде LC 2 = log 2 ( HV × D YE ) - 1 – константа для кадку. Використовуються системи координат: X,Z – ру. прямокутні координати, R, j – полярні координати. Вибір КСО, найближчого до центру зони охопТочки, що розглядаються: О – початок координат лення і перевірка його знаходження у зоні охопg-системи, Р – точка перетинання проекційного лення, проведемо таким чином. Прийнято такі угопроменя з предметною площиною, F – КСО на C предметній площині, К – лівий нижній ріг комірки, ди (фіг. 4): позначення A B позначає координату А яка містить точку Р. Введемо прямокутн у систему точки В у системі координат С. Система координат 4 36792 p¢ p¢ p¢ координат X PZ , вісь PZ якої є продовженr ням проекції вектора спостереження n на площину XZ, і яка повернена проти годинної стрілки на p p кут b відносно системи координат X PZ . Хр і Zp є порядковими номерами комірки уздовж осей Х і K K Z, а X p i Z p – координатами усередині комірки. Кількість і розташування КСО усередині комірки визначається кодом ГП NГП. Код ГП виби Його координати K K K X F = f 2 ( X p , Z p , N ГП ); K K K Z F = f 3 ( X p , Z p , N ГП ); У системі Р точка F має координати: P K K K K K XF = X -X = f 2 ( X p , Z p , N ГП ) - X ; F P P P K K K K K ZF = Z -Z = f 3 ( X p , Z p , N ГП ) - Z . F P P P P Знайдемо полярні координати R F , j F тієї ж точки в системі Р. рається за адресою: N ГП = f1 ( X p , Z p ) K K Знаючи X p й Z p і розташування КСО в даній комірці по NГП, з усіх КСО даної комірки вибираємо найближчий до точки Р. Позначимо його через F. P RF = ( X ) + (Z ) P 2 F P 2 F ( 2 = æ f 2 ( X K , Z K , N ГП ) - X K ö + æ ç ÷ ç p p P ø è è K K K f 3 ( X p , Z p , N ГП ) - Z P 2 ö , ÷ ø ) P P P K K K K K K j F = f 4 X F , Z F = f 4 æ f 2 ( X p , Z p , N ГП ) - X P , f 3 ( X p , Z p , N ГП ) - Z ö , ç ÷ P ø è Логарифм відстані точки F до координатних осей системи Р': P¢ P P¢ log 2 X F = log 2 R F + log 2 sin j F ; де f 4 ( ) – функція, що обчислює полярний кут по прямокутних координатах. ( ) P¢ P P¢ log 2 Z F = log 2 R F + log 2 cos(j F ); Знайдемо кут b : b = f 4 (V X , V Z ), де VX, VZ – x- і z – складові вектора спостереження. Полярні координати точки F y системі P¢ P P¢ P P¢ : R F = R F , j F = j F - b . Прямокутні координати тієї ж точки в системі P¢ P P¢ P¢ P P¢ P¢ : X F = R F × sin j F , Z F = R F × cos j F , ( ) Якщо задовольняється така система нерівностей, то КСО потрапляє в проекцію піксела: ( ) ì1 ï 2 Lp í1 ï L^ î2 P¢ ³ ZF , P¢ ³ XF , що еквівалентно P¢ ZF , P¢ XF , P (LVy + log 2 RF ) , у другому підсумовувачі – P (2LVy + log 2 RF ) . Після приходу наступного cин Перетворимо цю нерівність в еквівалентну ì LC - LV y + log R P ³ log sin j P¢ , ï 1 2 F 2 F (3). í P P¢ ï LC 2 - 2 LV y + log 2 R F ³ log 2 cos j F . î ( ( ì æ1 ö ï log 2 ç 2 L p ÷ ³ log 2 è ø í æ 1 L ö ³ log ïlog ç ÷ 2 î 2è 2 ^ø ) ) хроімпульсу Блок 15 відображення крапкових об'єктів працює таким чином. На початку кадру на входи 8 і 9 блока надходять константи LC1 і LC2 і утримуються протягом усього кадру. З приходом на вхід 10 першого синхроімпульсу в блоки 27-30 затримки по входах 1-7 надходять вхідні дані. Після приходу n-го синхроімпульсу (де n – тривалість найбільшої затримки) вхідні дані, відповідні до першого піксела кадра, з'являються на виходах блоків 2730. У блоці 16 формується значення кута b ,у блоці P P 17 – значення log 2 R F i j F , у блоці 42 – ознака наявності КСО в комірці. Після приходу наступного P P синхроімпульсу значення b , log 2 R F i j F ознака наявності КСО і Lvy з'являються на виходах регістрів і тригера першого щабля конвеєра. У першому P¢ віднімачі відбувається обчислення j F , у першому підсумовувачі обчислюється сума значення P¢ jF , P log 2 R F + LV y , P log 2 R F + 2 LV y і ознака наявності КСО з'являються на виходах регістрів і тригера другого щабля конвеєра. У блоці 21 обчислюються значення логарифмів синуса і косинуса, на виході 1 блока 21 P¢ з'являється значення log 2 sin j F , на виході 2 – P¢ значення log 2 cos j F . На виході друго го відніма ( ) ча 22 формується значення LC1 - LV y + log 2 R , на виході третього віднімана 23 формується зна ( ) чення LC 2 - 2 LV y + log 2 R . Після приходу наP¢ ступного синхроімпульсу значення log 2 sin j F , P¢ log 2 cos j F , 5 ( ) LC1 - LV y + log 2 R , 36792 ( LC 2 - 2 LV y + log 2 R ) тригерів четвертого щабля конвеєра. Елемент 26 І формує ознаку "підсвічування піксела" що після приходу наступного синхроімпульсу з'являється на виході тригера 49 п'ятого щабля конвеєра, що є виходом блока 15 відображення крапкових об'єктів. і ознака наявності КСО з'являються на виходах регістрів і тригера третього щабля конвеєра. Перший 24 і другий 25 блоки порівняння формують ознаки виконання відповідно першого і другого нерівностей (3). Ці ознаки, а також ознака наявності КСО після приходу наступного синхроімпульсу з'являються на виходах Фіг. 1 6 36792 Фіг. 2 Фіг. 3 7 36792 Фіг. 4 __________________________________________________________ ДП "Український інститут промислової власності" (Укрпатент) Україна, 01133, Київ-133, бульв. Лесі Українки, 26 (044) 295-81-42, 295-61-97 __________________________________________________________ Підписано до друку ________ 2001 р. Формат 60х84 1/8. Обсяг ______ обл.-вид. арк. Тираж 50 прим. Зам._______ ____________________________________________________________ УкрІНТЕІ, 03680, Київ-39 МСП, вул. Горького, 180. (044) 268-25-22 ___________________________________________________________ 8