Геометрическое моделирование и компьютерная график

Общая идея

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

Рис. 4. Определение атрибутов пикселей в зависимости от положения наблюдателя.

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

Размерность массива данных, которые нам потребуются при таком подходе, составит, таким образом, 5D.

Lumigraph

В том случае, если мы знаем, что наблюдатель не может находиться за некоторой линией, можно сократить необходимый нам объем данных. А именно: сфотографировать объект вдоль этой линии (на всех уровнях по вертикали), а затем в качестве значений пикселя, соответствующего некоторому лучу зрения, будем брать значение, соответствующее ближайшему лучу камеры (см. Рис. 5).

Рис. 5. Lumigraph.

Размерность массива данных в этом случае будет составлять 4D (2D на положение камеры и 2D на изображение от каждой камеры).

Concentric mosaic

Данный метод состоит в следующем: пусть нам необходимо получить вид некоторой комнаты изнутри. Сделаем в центре комнаты набор вертикальных линейных (т.е. шириной в 1 пиксель) снимков во всех направлениях. Затем сделаем аналогичные снимки из точек концентрических окружностей по касательным направлениям (см. Рис. 6) (как по часовой стрелке, так и против; на рисунке показано только одно направление).

Рис. 6. Concentric mosaic.

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

Перенос и повороты в трех мерном пространстве

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

Определение. Преобразование плоскости называется аффинным (от англ. affinity - родство), если

оно взаимно однозначно;

образом любой прямой является прямая.

Преобразование называется взаимно однозначным, если

разные точки переходят в разные;

в каждую точку переходит какая-то точка.

Свойства аффинного преобразования в трехмерном пространстве:

отображает n-мерный объект в n-мерный: точку в точку, линию в линию, поверхность в поверхность;

сохраняет параллельность линий и плоскостей;

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

Любое аффинное преобразование задается матрицей 3x3 с ненулевым определителем и вектором переноса:

Посмотрим на это с точки зрения математики. R представляет собой матрицу линейного оператора над пространством трехмерных векторов. Вектор T требуется для осуществления параллельного переноса: если помножить ( 0 0 0 ) на любую матрицу 3x3, опять получим ( 0 0 0 ) - начало системы координат, относительно преобразования R, является неподвижно точкой. Требование, чтобы определитель был ненулевой, диктуется определением. По сути, если определитель матрицы R равен нулю, то всё пространство переходит в плоскость, прямую или точку. Тем самым не соблюдается взаимная однозначность.

На практике удобно задавать аффинное преобразование одной матрицей. При этом используются однородные координаты, введенные в предыдущей статье. Аффинное преобразование будет задаваться следующей матрицей 4x4:

Заметим, что первые три значения последней строки равны 0. Это необходимое условие того, что преобразование будет аффинным. В общем случае произвольная матрица размера 4x4 задает проективное преобразование. Такие преобразования, как можно догадаться из названия, используются для проецирования трехмерной сцены. Подробнее об этом будет рассказано в одной из последующих статей.

Рассмотрим частные случаи аффинных преобразований.

Прим. Здесь и в дальнейшем будет использоваться система координат, введенная следующим образом:

система координат правая;

ось z направлена на наблюдателя, перпендикулярно плоскости экрана;

ось y находится в плоскости экрана и направлена вверх;

ось x находится в плоскости экрана и направлена вправо.

Подробнее мы остановимся на этом при рассмотрении геометрического конвейера.

Параллельный перенос

Матрица этого преобразования выглядит следующим образом:

В данном случае матрица R = E, единичной матрице.

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

Поворот (вращение)

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

Прим. Поворот вокруг произвольного вектора не равно поворот вокруг произвольной направленной прямой.

Поворот вокруг оси y

Заметим, что при повороте вокруг оси y ординаты точек (у-координаты) не меняются. Также стоит отметить, что координаты x и z точки преобразуются независимо от y-координаты. Это означает, что любая точка p(x, y, z) перейдет в точку p'(x'(x, z), y, z'(x, y)). Теперь осталось понять, как преобразуются координаты x и z: в плоскости Oxz это будет поворот вокруг начала координат по часовой стрелке (т.к. x z y - левая тройка), т.е. в отрицательном направлении. Матрица такого преобразования известна (см. Поворот плоскости):

В итоге:

Матрица преобразования Ry(цy):

Поворот вокруг осей x и z

Аналогичными рассуждениями можно получить матрицы поворотов Rx(цx) и Rz(цz)вокруг осей x и z, соответственно.

Приведём окончательные результаты:

Несложно заметить, что определители матриц Rx, Ry, Rz равны 1. Также матрицы вращений Rrot обладают свойством ортогональности: RTR = RRT = E. Из этого, в свою очередь, следует полезное свойство, что обращение матрицы поворота можно заменить транспонированием: R-1(ц) = RT(ц).

Масштабирование (сжатие/растяжение, отражение)

Коэффициенты сжатия/растяжения, по аналогии с двухмерным пространством, определяются диагональными членами матрицы R:

Результат:

Комбинация коэффициентов sx = -1, sy = 1, sz = 1 будет задавать отражение от плоскости Oyz (x = 0). При sx = sy = sz = -1 получим центральную симметрию относительно начала координат.

Интерпретация матрицы R

Рассмотрим, что представляет собой матрица R с точки зрения линейной алгебры. Оказывается, что матрица R содержит базис новой системы координат.

Действительно, матрица

( R11 R12 R13 )

( R21 R22 R33 )

( R31 R32 R33 )

переводит вектора декартова базиса:

( 1 0 0 ) > ( R11 R21 R31 )

( 0 1 0 ) > ( R12 R22 R32 )

( 0 0 1 ) > ( R13 R23 R33 )

Скос

Теперь несложно получить преобразование скоса. Например:

Сложные аффинные преобразования

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

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

Для решения одномерных (по пространственной координате) уравнений можно использовать метод конечных разностей, однако применимость данного метода ограничена из-за его условной устойчивости. Поэтому на практике гораздо чаще используется безусловно устойчивая неявная схема Кранка-Николсона, основанная на численных приближениях для решений в промежуточной точке (x, t + t/2), где t- шаг по времени. Постановка задачи в общем виде включает уравнение

ut (x,t) = D uxx(x,t) + g(x,t) , 0 x L, 0< t < tmax, (1)

с начальным условием

u(x,0) = f (x), 0x L, t = 0 (2)

и граничными условиями, вообще говоря, являющимися функциями времени. Рассмотрим наиболее простой случай, когда g(x,t) = 0 (однородное уравнение), а в качестве граничных условий используются однородные граничные условия

u(0, t) = 0, x=0, 0t tmax,

uч(L, t) = 0, x=L, 0t tmax . (3)

Согласно схеме Кранка-Николсона, производные в уравнении (1) аппроксимируются формулами

(2)

Подставляя формулы (2) в (1) и приводя подобные, получаем уравнение

-ui-1,j+1 + s2ui,j+1 - ui+1,j+1 = s3ui,j + ui-1,j + ui+1,j , (3)

где s2 = 2/r + 2, s3 = 2/r - 2, r = D? /h2 , i = 1, 2,…, n-2, j = 1, 2, …, m-1.

Подставляя в (3) однородное граничное условие на левом конце отрезка u0,j = 0, получаем для i = 1 уравнение

s2u1,j+1 - u2,j+1 = s3u1,j + u2 j . (4)

Для аппроксимации граничного условия 2-го рода на правом конце отрезка введем фиктивную точку u(a+h) и аппроксимируем производную по формуле центральной разности

,

откуда следует, что u(a-h) = u(a+h) . Тогда из уравнения (3) при i = n -1 получаем формулу

-2un-1,j+1 + s2un,j+1 = (s3 +1)un-1,j + un-2,j . (5)

Уравнения (3)-(5) представляют собой систему линейных уравнений с трехдиагональной матрицей, которая решается методом прогонки.

Если уравнение (1) является неоднородным, значения функции g(x,t) также берутся в промежуточной точке.

Метод Хука-Дживса был разработан в 1961 году, но до сих пор является весьма эффективным и оригинальным. Поиск состоит из последовательности шагов исследующего поиска вокруг базисной точки , за которой в случае успеха следует поиск по образцу. Он применяется для решения задачи минимизирования функции без учета ограничений .ПОКООРДИНАТНЫЙ СПУСК

Описание этой процедуры представлено ниже:

А. Выбрать начальную базисную точку $b_{1}$ и шаг длиной $h_{1$} для каждой переменной $x_{j}, j = 1, 2,…, n$. В приведенной ниже программе для каждой переменной используется шаг h, однако указанная выше модификация тоже может оказаться полезной.

Б. Вычислить $f(х)$ в базисной точке $b_{1}$ с целью получения сведений о локальном поведении функции $f(x)$. Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция $f(x)$ в базисной точке $b_{1}$, находится следующим образом:

1. Вычисляется значение функции $f(b_{1})$ в базисной точке $b_{1}$.

2. Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции $f (b_{1}+h_{1}e_{1})$, где $e_{1}$ - единичный вектор в направлении оси $x_{1}$. Если это приводит к уменьшению значения функции, то $b_{1}$ заменяется на $b_{1}+h_{1}e_{1}$. В противном случае вычисляется значение функции $f (b_{1}-h_{1}e_{1})$, и если ее значение уменьшилось, то $b_{1}$ заменяем на $b_{1}-h_{1}e_{1}$. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка $b_{1 }$ остается неизменной и рассматриваются изменения в направлении оси $х_{2}$, т. е. находится значение функции $f (b_{1}+h_{2}e_{2})$ и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку $b_{2}$.

3. Если $b_{2}=b_{1}$, т. е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки $b_{1}$, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

4. Если $b_{2} \ne b_{1}$, то производится поиск по образцу.

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

1. Разумно двигаться из базисной точки $b_{2}$ в направлении $b_{2}-b_{1}$, поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца

$P_{1}=b_{1}+2(b_{2}-b_{1})$ . В общем случае $P_{i}=b_{i}+2(b_{i+1}-b_{i})$ .

2. Затем исследование следует продолжать вокруг точки $Р_{1} (Р_{i})$ .

3. Если наименьшее значение на шаге В, 2 меньше значения в базисной точке $b_{2}$ (в общем случае $b_{i+1}$), то получают новую базисную точку $b_{3 }(b_{i+2}$), после чего следует повторить шаг В, 1. В противном случае не производить поиск по образцу из точки $b_{2 }(b_{i+1}$), а продолжить исследования в точке $b_{2 }(b_{i+1}$).

Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения

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

Суть метода заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума.

Метод находит локальный экстремум и может «застрять» в одном из них. Если всё же требуется найти глобальный экстремум, можно пробовать выбирать другой начальный симплекс. Более развитый подход к исключению локальных экстремумов предлагается в генетическом методе отжига.

Алгоритм

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

Параметрами метода являются:

коэффициент отражения б > 0, обычно выбирается равным 1.

коэффициент сжатия в > 0, обычно выбирается равным 0,5.

коэффициент растяжения г > 0, обычно выбирается равным 2.

Подготовка. Вначале выбирается n + 1 точка , образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: .

Дальнейший план действий:

1. Сортировка. Из вершин симплекса выбираем три точки: xh с наибольшим (из выбранных) значением функции fh, xg со следующим по величине значением fg и xl с наименьшим значением функции fl. Целью дальнейших манипуляций будет уменьшение по крайней мере fh.

2. Найдём центр тяжести всех точек, за исключением xh: . Вычислять fc = f(xc) не обязательно.

3. Отражение. Отразим точку xh относительно xc с коэффициентом б (при б = 1 это будет центральная симметрия, в общем случае -- гомотетия), получим точку xr и вычислим в ней функцию: fr = f(xr). Координаты новой точки вычисляются по формуле:

xr = (1 + б)xc - бxh

4. Далее смотрим, насколько нам удалось уменьшить функцию, ищем место fr в ряду fh,fg,fl:

4а Если fr < fl, то направление выбрано удачное и можно попробовать увеличить шаг -- производим растяжение. Новая точка xe = (1 ? г)xc + гxr и значение функции fe = f(xe).

Если fe < fl, то можно расширить симплекс до этой точки: заменяем точку xh на xe и заканчиваем итерацию (на шаг 8).

Если fe > fl, то переместились слишком далеко: в набор берём xr (опять вместо xh) и заканчиваем итерацию (на шаг 8).

4b Если fl < fr < fg, то выбор точки уже неплохой (новая лучше двух прежних). Заменяем точку xh на xr и переходим на шаг 8.

4с Если fh > fr > fg, то меняем обозначения xr,xh (и соответствующие значения функции) местами и идём на шаг 5.

4d Если fr > fh, то просто идём на следующий шаг 5.

В результате (возможно, после переобозначения) fr > fh > fg > fl.

5. Сжатие. Строим точку xs = вxh + (1 ? в)xc и вычисляем в ней значение fs.

6 Если fs < fh, то заменяем точку xh на xs и идём на шаг 8.

7 Если fs > fh, то первоначальные точки оказались самыми маленькими. Делаем глобальное сжатие симплекса -- гомотетию к точке с наименьшим значением x0:

для всех требуемых точек xi.

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

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

Сходимость метода градиентного спуска зависит от отношения максимального и минимального собственных чисел матрицы Гессе в окрестности минимума (максимума). Чем больше это отношение, тем хуже сходимость метода.

Пусть целевая функция имеет вид:

.

И задача оптимизации задана следующим образом:

Основная идея метода заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом :

где л[j] выбирается

постоянной, в этом случае метод может расходиться;

дробным шагом, т.е. длина шага в процессе спуска делится на некое число;

наискорейшим спуском:

Алгоритм

Задают начальное приближение и точность расчёта

Рассчитывают , где

Проверяют условие остановки:

Если , то j = j + 1 и переход к шагу 2.

Иначе и останов.

Размещено на Allbest.ru