Построение собственных математических моделей

2.5       Построение собственных математических моделей

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

Интерполяция.

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

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

f_i=y_i

f’(x_i-0)=f’(x_i+0)

f’’(x_i-0)=f’’(x_i+0)

Кроме того, на границе, при x=x₀ и x=x_n ставятся условия:

f'’(x₀)=0 и f``(x_n)=0 (1)

 Будем искать кубический полином в виде:

f(x)=a_i+b_i(x -–x_i-1)+c_i(x-x_i-1)²+d_i(x-x_i-1)³, (2)

Из условия f_i=y_iимеем:

f(x_i-1)=a_i=y_i-1

f(x_i)=a_i+b_ih_i+c_iI_i²+d_ih_i³=y_i. (3)

h_i=x_i-x_i-1, i=1,2,…,n-1

Вычислим производные:

f’(x)=b_i+2c_i(x-x_i-1)+3d_i(x-x_i-1),

f’’(x)=2c_i+6d_i(x-x_i-1),

И потребуем их непрерывности при x=x_i:

b_i+1=b_i+2c_ih_i+3d_ih_i²,

c_i+1=c_i+3d_ih_i, i=1,2,…,n-1 (4)

Общее число неизвестных коэффициентов, очевидно, равно 4n, число уравнений (3) и (4) равно 4n-2. Недостающие два уравнения получаем из условий (1) при x=x₀ и x=x_n;

c_i=0, c_n+3d_nh_n=0.

Выражая из (4) d_i=(c_i+1-c_i)/3h_i, подставляя это значение в (3) и исключая

a_i=y_i-1, получим:

i=1,2,…,n-1,

Подставив теперь выражения для b_i, b_i+1 и d_i в первую формулу (4),

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

i=1,2,…,n-1. (5)

C краевыми условиями:

c₁=0, c_n+1=0. (6)

Условие c_n+1=0 эквивалентно условию c_n+3d_nh_n=0 и уравнению c_i+1=c_i+d_ih_i. Разностное уравнение (5) с условиями (6) решается методом прогонки.

 Можно ввести понятие сплайна порядка m как функции, которая является полиномом степени m на каждом их отрезков сетки и во всех внутренних узлах сетки удовлетворяет условиям непрерывности функции и производной порядка m-1 включительно. Обычно для интерполяции используются случаи m=3 (рассмотренный выше кубический сплайн) и m=1 (линейный сплайн, соответствующий аппроксимации графика функции y(x) ломаной, проходящей через точки (x_i,y_i)).

Работа с трехмерными изображениями.

После проведения интерполяции уже можно построить графики для одномерных случаев. Но двумерные случаи (поверхности) требуют дополнительных математических и алгоритмических методов.

 Изображение пространственных объектов на экранной плоскости не возможно без операции проектирования. Видов такого проектирования существует довольно много. Мы остановимся на описании проектирования пучком прямолинейных лучей. Различают два типа таких пучков: пучок лучей, исходящих из одной точки и пучок лучей, параллельный заданному направлению. Для получения проекции заданного объекта на плоскость необходимо провести через каждую его точку прямую из проектирующего пучка и затем найти координаты точек пересечения этих прямых с плоскостью изображения.

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

Для описания преобразований проектирования также удобно пользоваться матрицами. Например, матрица проектирования на плоскость

0yz вдоль оси 0x имеет следующий вид:

Если M(x,y,z) – заданная точка, то соответствующая ей точка на плоскости изображения находится так:v

Таким образом, точка M проектируется в точку M^*(0,y,z).

В случае, если плоскость проектирования параллельна координатной

плоскости 0yz, матрица несколько изменяется:

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

Матрицы, соответствующие другим случаям взаимного расположения проектирующего пучка параллельных лучей и координатной системы, разумеется, также существуют. Рассмотрим, например, случай косоугольного проектирования, при котором пучок прямых пересекает координатную плоскость 0xy по углом 45^o (кабинетная проекция). Тогда соответствующая матрица будет иметь следующий вид:

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

x^*=a₁x+b₁y+c₁z+d₁,

y^*=a₂x+b₂y+c₂z+d₂,

z^*=a₃x+b₃y+c₃z+d₃.

Любое изменение координат, описываемое этими формулами, можно представить посредством комбинации (последовательного выполнения) простейших операций: параллельного переноса, поворота, зеркального отражения и растяжения (сжатия).

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

Рассмотрим частный случай для вращения:

-           матрица поворота вокруг оси 0x.

-           матрица поворота вокруг оси 0y.

-          

матрица поворота вокруг оси 0z
Операцию параллельного переноса нельзя записать при помощи матрицы используемого размера 3 на 3. Тем не менее, единая матричная запись всех упомянутых преобразований возможно, если формально ввести еще одну дополнительную координату:

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

Это один из простейших алгоритмов удаления невидимых поверхностей. Работает этот алгоритм в пространстве изображения. Идея z-буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания атрибутов (интенсивности) каждого пиксела в пространстве изображения, z-буфер - это отдельный буфер глубины, используемый для запоминания координаты z или глубины каждого видимого пиксела в пространстве изображения. В процессе работы глубина или значение z каждого нового пиксела, который нужно занести в буфер кадра, сравнивается с глубиной того пиксела, который уже занесен в z-буфер. Если это сравнение показывает, что новый пиксел расположен впереди пиксела, находящегося в буфере кадра, то новый пиксел заносится в этот буфер и, кроме того, производится корректировка z-буфера новым значением z. Если же сравнение дает противоположный результат, то никаких действий не производится. По сути, алгоритм является поиском по х и у наибольшего значения функции z (х, у).

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

 Основной недостаток алгоритма - большой объем требуемой памяти. Если сцена подвергается видовому преобразованию и отсекается до фиксированного диапазона координат z значений, то можно использовать z-буфер с фиксированной точностью. Информацию о глубине нужно обрабатывать с большей точностью, чем координатную информацию на плоскости (х, y); обычно бывает достаточно 20 бит. Буфер кадра размером 512х512х24 бит в комбинации с z-буфером размером 512х512х20 бит требует почти 1.5 мегабайт памяти. Однако снижение цен на память делает экономически оправданным создание специализированных запоминающих устройств для z-буфера и связанной с ним аппаратуры.

Альтернативой созданию специальной памяти для z-буфера является использование для этой цели оперативной или массовой памяти. Уменьшение требуемой памяти достигается разбиением пространства изображения на 4, 16 или больше квадратов или полос. В предельном варианте можно использовать г-буфер размером в одну строку развертки. Для последнего случая имеется интересный алгоритм построчного сканирования. Поскольку каждый элемент сцены обрабатывается много раз, то сегментирование z-буфера, вообще говоря, приводит к увеличению времени, необходимого для обработки сцены. Однако сортировка на плоскости, позволяющая не обрабатывать все многоугольники в каждом из квадратов или полос, может значительно сократить этот рост.

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

 Хотя реализация методов устранения лестничного эффекта, основывающихся на префильтрации, в принципе возможна, практически это сделать трудно. Однако относительно легко реализуются методы постфильтрации (усреднение подпикселов). Напомним, что в методах устранения лестничного эффекта, основывающихся на постфильтрации, сцена вычисляется в таком пространстве изображения, разрешающая способность которого выше, чем разрешающая способность экрана. Поэтому возможны два подхода к устранению лестничного эффекта на основе постфильтрации. В первом используется буфер кадра, заданный в пространстве изображения, разрешение которого выше, чем у экрана, и z-буфер, разрешение которого совпадает с разрешением экрана. Глубина изображения вычисляется только в центре той группы подпикселов, которая усредняется. Если для имитации расстояния от наблюдателя используется масштабирование интенсивности, то этот метод может оказаться неадекватным.

Во втором методе оба буфера, заданные в пространстве изображения, имеют повышенную разрешающую способность. При визуализации изображения.

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