Билет 2

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

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

3. Найти кратчайшее расстояние от точки А(0; 1) до прямой y=2x+3, используя методы вариационного исчисления.

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

Для реализации этого алгоритма требуется два буфера:

1. Буфер глубины (Z - буфер).

2. Буфер регенерации.

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

1. Если глубина многоугольника Z(x, y) в текущей точке растровой развертки меньше чем соответствующая точка в Z - буфере, то точка находится ближе к наблюдателю и в буфер регенерации в точку (x, y) записываем атрибут многоугольника, Z_БУФ(x, y) <- Z(x, y).

2. Иначе {Z(x, y) > Z_БУФ(x, y)} переход к следующей точке растровой развертки многоугольника.

Главным недостатком алгоритма является большой размер Z - буфера. Сцена будет появляться в той последовательности в какой мы анализируем грани.

Достоинства: обрабатываются сцены любой сложности, прост в реализации.

(x₂, y₂, z₂)

(x₃, y₃, z₃)

(x₁, y₁, z₁)

где

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

Аналогично вычисляется Z при переходе на следующую сканирующую строку:

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

Работает в рамках одной сканирующей строки. Количество элементов в Z - строке соответствует разрешающей способности по горизонтали. Глубина Z - строки определяет величину значения Z (см. Алгоритм использующий Z - буфер).

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

Z-buffering

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

Z-sorting

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

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

X = 0 0 1 1

Y= 0 1 0 1

Функции и их обозначение:

F = 0 0 0 1 XY Конъюнкция (Логическое И)

F = 0 1 1 1 XY Дизъюнкция (Логическое ИЛИ)

F = 1 0 1 1 Y→X Импликация от Y к X

F = 1 1 0 1 X→Y Импликация от X к Y

F = 1 1 1 0 X│Y Штрих Шеффера (Отрицание конъюнкции)

F = 1 0 0 0 XY Стрелка Пирса (отрицание дизъюнкции)

F = 1 0 0 1 X~YЭквивалентность

F = 0 1 1 0 XY Сумма по модулю 2 (Исключающее ИЛИ)

F = 0 1 0 0 YΔX Запрет по X (Отрицание импликации)

Аксиомы алгебры логики.

1. - закон двойного отрицания.

2. XY=YX - коммутативный закон для умножения

3. X(YZ)=XYZ - сочетательный закон для умножения

4. XX=X - закон тождества для умножения

5. 1X=X - закон умножения на единицу

6. 0X=0 - закон умножения с нулем

7. XY=YX - коммутативный закон для сложения

8. X(YZ)=(XY)Z - сочетательный закон для сложения

9. XX=X - закон тождества для сложения

10. 1X=1 - закон сложения с единицей

11. 0X=X- закон сложения с нулем

12. X(YZ)=XYXZ - первый распределительный закон

13. XYZ=(XY)(XZ) - второй распределительный закон

14. XXY=X

15. X(XY)=X - законы поглощения

17. - законы де Моргана (инверсии)

18. X=1 - закон исключенного третьего

19. X=0 - закон противоречия.

Обозначение функциональных узлов

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

1. словесная формулировка функций логического устройства

2. составление таблицы истинности по словесной формулировке

3. запись логического уравнения устройства в виде СДНФ или СКНФ

4. минимизация логического уравнения

5. выбор одного из логических базисов

6. преобразование логического уравнения с использованием правил де Моргана

7. построение функциональной схемы логического устройства

Пример:

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

2. таблица истинности

A	B	C	Y
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

3.

4.

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

6.

3 Найти кратчайшее расстояние от точки А(0; 1) до прямой y=2x+3, используя методы вариационного исчисления

I способ. Аналитический.

y=2x+3 -> 2x-y+3=0, тогда нормальный вектор к данной прямой n={2: -1}

пусть Р – основание перпендикуляра , тогда уравнение прямой РА, перпендикулярной исходной прямой будет иметь вид

Определим координаты точки Р

т.к. Р точка пересечения двух прямых решив систему, найдем ее координаты

х/2+у=1

у=2х+3

х=-4/5

у=7/5

теперь найдем искомое расстояние АР

АР=

II способ геометрический

AP(искомое расстояние) перпендикулярно MN

тр-ик MNO подобен тр-ику MPA -> MN/MA = NO/AP -> AP=NO*MA/MN

MA=2 NO=1.5 MN=

AP=0.4

III способ. Оптимизационный

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

y=2*x+3

s=sqrt(x^2+(2x+3-1)^2)=sqrt(x^2+4*(x+1)^2)=sqrt(5*x^2+8*x+4);

s’=(10*x+8)*0.5/ sqrt(5*x^2+8*x+4)= (5*x+4)/sqrt(5*x^2+8*x+4)=0; следовательно x=-0.8;

s=sqrt(0.8)= 0.4

Уравнение Эйлера (численный)

Элементарное S расстояние между двумя точками на плоскости, координаты которых отличаются на dt и dx, равно:

Выполним некоторые преобразования:

Расстояние между двумя точками на плоскости выразится интегралом:

Задача сводится к нахождению экстремального значения интеграла при условии, что левый конец точка А(0,1), а правый прямая x=2t+3. Таким образом, в нашем случае имеем (t)=2t+3.

Для составления уравнения Эйлера запишем:

Уравнение Эйлера имеет вид x''=0. Общее решение уравнения Эйлера: x=C₁t+C₂.

Условия трансверсальности имеют вид Т.к.x'=C₁, получим: Уравнения в данном случае принимают вид С₁t₀+C₂=x₀, C₁t₁+C₂=2t₁+3. В результате имеем систему уравнений:



Из системы С₂=1. Необходимо найти t₁,C₁

.