2.Интерполяционные кривые в машинной графике.

Одной из распространенных задач в САПР является графическое представление кривых и поверхностей. Средства компьютерной графики существенно помогают при проектировании, показывая конструктору различные варианты моделирования поверхности. При этом часто возникает задача построения кривой или поверхности, проходящей через ряд заданных точек.Интерполяция - построение кривой, проходящей через контрольные точки.

Аппроксимация - приближение кривой (не обязательно проходит точно через данные точки, но удовлетворяет некоторому заданному свойству относительно этих точек).

Интерполяция. Многочлен Лагранжа:

Пусть на плоскости задан набор точек: (x _i , y_i), i=0,...,m, причем x₀<x₁<x₂<...<x_m.

многочлен Лаганжа -

Если раскрыть данный многочлен, получим

Кривые Эрмита:

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

Даны точки, из каждой выходит вектор, являющийся касательной к куску кривой, выходящей из этой точки.

Для построения простейшей кривой достаточно двух точек. Существует параметр t, принадлежащий отрезку [0,1] и изменяющийся на нем с некоторым шагом.

, где ,и,- координаты векторов относительно точек.

Пример:

Аппроксимация. Кривая Безье

Пусть на плоскости или в пространстве задан упорядоченный набор точек, определяемый векторами V₀,V₁,V₂,...,V_m

Кривая Безье 0<t<1,

Кривая Безье обладает следующими замечательными свойствами:

1) Она является гладкой;

2) Начинается в точке V₀ и заканчивается в точке V_m, касаясь при этом отрезков (V₀ V₁ ) и (V_m-1 V_m) контрольной ломаной;

3) Функциональные коэффициенты Cⁱ_mtⁱ(1-t)^m-i при вершинах Vi, i=0,1,..,m, суть универсальные многочлены (многочлены Берштейна); они неотрицательны, и их сумма равна единице

Сплайны

Пусть отрезок [x0,xn] разбит на n частей, тогда сплайном степени m называется функция Sm(x), где m – старшая степень, обладающая следующими свойствами:

1. Sm(x) непрерывна на всем отрезке [x0,xn] вместе со своими производными до некоторого порядка p

2. на каждом отрезке [xi,xi+1] функция Sm(x) совпадает с некоторым многочленом Pm,i(x)

На каждом отрезке [xi,xi+1] таблично заданная функция заменяется на

S3(x)=ai+bi(x-xi-1)+ci(x–xi-1)*(x–xi-1)+d(x–xi-1)*(x–xi-1)*(x–xi-1)

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

B-сплайны:

В более общей форме B-сплайнов кривая в общем случае задается соотношением:

P(t) = i = 0n Pi   Nim(t)

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

Ni,1 =    1, если   xi       t       xi+1 0, в   других  случаях

Ni,k(t) = (t - xi) Ni,k-1(t) xi+k-1 - xi + (xi+k - t) Ni+1,k-1(t) xi+k - xi+1 .

Квадратичный:

Для его построения требуется минимум три точки.

Тогда

Пример:

Кубический:

Для его построения требуется минимум 4 точки.

Пример:

3. Представить алгоритм определения производительности работы ЦП по тестируемой команде

Программа измерения производительности и быстродействия компьютера.

Описание алгоритма.

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

Полный цикл * Пустой цикл

Производительность = ---------------------------

Пустой цикл - Полный цикл

1

Быстродействие = --------------------

Производительность

Алгоритм.

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

2. Получаем и сохраняем для последующего использования адрес прерывания Int 8h.

3. Устанавливаем свой вектор прерывания таймера Int 8h.

4. Проверяем некоторую переменную, которая изменяется в собственном обработчике Int 8h, означающую запуск измерений.

5. После запуска измерений начинает работу цикл, который увеличивает на 1 счетчик пустых циклов.

6. После отсчета собственным обработчиком прерываний от таймера 18 тиков (18 тиков = 1 сек.), он передает управление циклу с командой XOR, который в свою очередь увеличивает на 1 счетчик полных циклов.

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

Программа выдает результаты вычислений с точностью до сотой доли.

8. Затем восстанавливается старый адрес прерывания Int 8h и проис-

ходит выход в DOS.

///////////////ANOTHER metod

Алгоритм определения производительности по тестируемой комманде**chstota proceccorov

4. НАЧАЛО

5. Вводим частоту процессора тестируемого компьютера в МГц в переменную f

6. f := f*1000000

7. засекаем текущее время и переводим его в секунды, и сохраняем в переменной T1

8. В цикле от 1 до 1000000000 выполняем тестируемую команду.

9. засекаем время и переводим его в секунды, и сохраняем в переменной T2

10. находим TimeTest1 := T2 – T1

11. засекаем текущее время и переводим его в секунды, и сохраняем в переменной T3

12. Выполняем пустой цикл от 1 до 1000000000 (для определения времени выполнения цикла)

13. засекаем время и переводим его в секунды, и сохраняем в переменной T4

14. находим TimeTest2 := T4 – T3

15. находим число операций выполненных за 1 секунду Oper := 1000000000/(TimeTest1 – TimeTest2)

16. находим число тактов необходимое для выполнения команды: NumTakt := f/Oper

17. КОНЕЦ