Задачный практикум

Часть 1 

В задачном практикуме приведенные примеры решения типовых задач.  

1.   Определить минимальное количество интерполяционных тактов, необходимое для формирования вектора ортогональными шаговыми приращениями.  

Формирование вектора осуществляется вертикальными и горизонтальными шаговыми приращениями (рис.9.1).    

       Рис. 9.1.    

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

Аналогично, количество интерполяционных тактов в направлении оси ординат равно DY. Общее количество интерполяционных тактов DX+DY.  

2.   Выполнить интерполирование отрезка прямой с  приращениями DХ=5, DY=2 по алгоритму Петуха А.М., Ободника Д.Т.  

Интерполирование по алгоритму Петуха А.М., Ободника Д.Т. осуществляется согласно следующих формул:    

где БП и МП соответственно больше и меньшее значение приращений DХ, DY.  

БП = 5,      МП = 2,      D = 3.  

ОФ₀ = ë5/2û = 2          ОФ₃ = –2 + 3 = 1  

ОФ₁ = 2 – 2 = 0         ОФ₄ = 1 – 2 = –1  

ОФ₂ = 0 – 2 =  -2        ОФ₅ = –1 + 3 = 2  

При ОФ_i³0 выполняется горизонтальный шаг, а при ОФ_i<0 – диагональный.

Сформированная траектория представлена на рис. 9.2.    

    Рис. 9.2.  

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

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

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

Поскольку диагональный шаг включает перемещение по оси Y, то можно утверждать, что на каждое перемещение по оси Х приходиться два перемещения по оси Y, то есть ∆Y=2∆Х.  

Поскольку адреса пикселов при формировании вектора уменьшаются, то это означает, что он формируется по направлению к начальной точке экрана.  

           Рис.9.3.  

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

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

          Рис. 9.4.    

Отрезок прямой имеет по отношению к самым близким точкам решетки дискретного пространства две погрешности: d⁺ и d^– (рис. 9.4). Из двух возможных точек решетки, одна из которых находится выше, а другая – ниже отрезка прямой, целесообразно выбрать ту, для которой погрешность d⁺ или d^– меньшая по модулю.  

В случае (а), когда идеальный отрезок прямой проходит через середину дискреты, то d⁺=|d^–|=0.5, поэтому самая близкая точка решетки отдалена от вектора на 0.5 шага дискретизации. В этом случае имеем два идентичных варианта выбора самых близких точек решетки, которые наиболее близко находятся к отрезку прямой. Каждая из этих точек отдаленна от отрезка на половину шага дискретизации.  

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

5.   Определить значение оценочной функции в точке (6,2) при формировании отрезка прямой согласно алгоритма Петуха-Ободника при условии, что ∆х=8, ∆y=3, х_н=0, у_н=0. 

Согласно условия выполнено 4 горизонтальных и 2 диагональных координатных приращения. При формировании горизонтального шага значение оценочной функции определяется по формуле:  

ОФ_i+1 = ОФ_i – МП,  

где МП – меньшее из приращений. В данном случае МП=3.  

При выполнении диагонального шага:  

ОФ_i+1 = ОФ_i + D, где D=БП–МП,   D=5. 

Подитоживая приведенное, находим      ОФ₆ = ОФ₀ – 4МП + 2D.  

Для алгоритма Петуха, Ободника ОФ₀=ëБП/2û=4. Учитывая начальное значение оценочной функции, находим   

ОФ₆ = 4 – 12 + 10 = 2.  

6.   Определите тип вектора, который согласно алгоритма Петуха А.М., Ободника Д.Т, линейной интерполяции имеет все значения последней, равной начальному значению.

Оценочная функция вычисляется по следующим формулам:    

где МП и БП – соответственно меньшее и большее приращения отрезка прямой.  

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

ОФ₁ = ОФ₀ – МП.  

При   МП = 0, ОФ₁ = ОФ₀ = ОФ_і,   i = 1,БП.  

7.   Доказать, что начальное и конечное значения оценочной функции при формировании вектора по алгоритму линейной интерполяции Петуха–Ободника равны.  

Оценочная функция рассчитывается согласно формул:    

где МП, БП – соответственно меньшее и большее приращения.  

При ОФ_і³0 формируется горизонтальный (вертикальный) шаг, а при ОФ_і<0 диагональный. Количество диагональных шагов равно МП, а количество горизонтальных (вертикальных) БП–МП. Поскольку выполняется БП интерполяционных тактов, то конечное значение оцениваемой функции равно:  

ОФ_к = ОФ_БП = ОФ₀–МП×(БП–МП)+D×МП = ОФ₀–МП×D+МП×D = ОФ₀.  

8.   Определить минимальное количество интерполяционных тактов алгоритмов линейной интерполяции с восьмивекторним направлением шаговых приростов.  

Формирование шаговой траектории согласно указанных алгоритмов осуществляется горизонтальными (вертикальными) и диагональными шагами. Диагональный шаг включает в себя одновременное перемещение по обеим координатам. При ∆х>∆y шаговая траектория состоит из горизонтальных и диагональных приращений. Учитывая, что диагональный шаг включает перемещение в горизонтальном направлении, делаем вывод, что количество шагов для достижения конечной точки равно ∆x.   

         Рис.9.5.    

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

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

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

где БП, МП – соответственно большее и меньшее приращения.  

Цикл интерполирования заканчивается через БП такты.  

В регистр БП и МП с входной шины D заносятся соответственно большее (БП) и меньшее (МП) приращения. Регистр накапливающего сумматора обнуляют. Значение БП заносится в RG накапливающего сумматора (образован комбинационным сумматором Sm и регистром RG). Через мультиплексор МХ на вход накапливающего сумматора подается значение МП в инверсном коде (поскольку операция вычитания для данного случая выполняется в дополнительном коде, то при ее реализации на вход переноса накапливающего сумматора подается уровень логической единицы). Значение БП–МП с выхода сумматора Sm заносится в регистр D. В счетчик СТ2 с выхода регистра БП подается значение большего приращения, которое под действием сигнала Y₄ записывается в счетчик. В регистр RG накапливающего сумматора подается значение ëБП/2û, которое получаем монтажным путем на выходе счетчика СТ2. На этом заканчивается цикл подготовки.  

В цикле интерполяции в каждом такте находится значение оценочной функции. Для этого на вход накапливающего сумматора с выхода мультиплексора подается значение D или МП.  

Знак оценочной функции определяет сигнал переноса Р_вых сумматора. С каждым интерполяционным тактом значения счетчика уменьшается на 1. При достижении счетчиком нулевого состояния процесс интерполяции заканчивают.    

   Рис. 9.6.

10.    Определить значения интенсивностей цвета точек для обеспечения антиалиазинга векторной границы с приращениями DХ=5, DВ=2 при условии, что интенсивность цвета I=10

Коэффициент наклона вектора равен DY/DX. Зададим угол наклона отношением I/I_X, то есть DY/DX=I/I_X.    

Таким образом, І_Х=4, I=10.  

Выполним интерполирования с параметрами I, І_Х при количестве интерполяционных тактов DХ=5. При положительном знаке оценочной функции значение интенсивности цвета определяется как разность между параметром I и текущим значением оценочной функции, а при отрицательном – как модуль ОФ.  

БП = 10,   МП = 4  

ОФ₀ = ëБП/2û = 5;         D = БП – МП = 6  

ОФ₁ = ОФ₀ – МП = 5 – 4 = 1,     I₁ = I – ОФ₁ = 9  

ОФ₂ = ОФ₁ – МП = 1 – 4 = –3,   I₂ = 3  

ОФ₃ = ОФ₂ + D = –3 + 6 = 3,      I₃ = 10 – 3 = 7  

ОФ₄ = ОФ₃ – МП = 3 – 4 = –1,   I₄ = 1  

ОФ₅ = ОФ₄ + D = –1 + 6 = 5,     I₅ = 5  

Установлением І₀=5, І₁=9, І₂=3, І₃=7, І₄=1, І₅=5 обеспечивается сглаживание ступенчатой формы вектора.  

11.   Определить количество интерполяционных тактов для формирования траектории окружности ортогональными шаговыми приращениями.  

Рассмотрим первый квадрант (рис.9.7). Шаговая траектория формируется горизонтальными и вертикальными элементарными перемещениями.    

          Рис. 9.7.    

Количество шаговых приращений в направлении координат Х равно радиусу R, поскольку вертикальные шаги не обеспечивают перемещения по оси абсцисс. Аналогичная ситуация имеет место и для ординатного направления. Таким образом, количество шаговых приращений для формирования траектории в первом квадранте равно 2R, а для всей окружности: 2R×4=8R.  

     Содержание