17 августа 2019 года    
Суббота | 17:55    
Главная
 Новости
Базы данных
Безопасность PC
Всё о компьютерах
Графика и дизайн
Интернет-технологии
Мобильные устройства
Операционные системы
Программирование
Программы
Связь
Сети
 Документация
Статьи
Самоучители
 Общение
Форум







Разделы / Программирование / Другие

demo.design 3D programming FAQ.

Секция 6 из 6 - Предыдущая - Следующая
Все секции - 1 - 2 - 3 - 4 - 5 - 6

между какими-то точками p1, p2 используются значения r1 = p1.ra, r2 = p2.rb.
При continuity = 0 они (ra и rb) равны, при continuity = 1 ra удваивается,
а rb становится равным нулю. Таким образом, параметр continuity контролирует
"изломанность", негладкость сплайна.

Геометрический смысл всех этих параметров нагляднее всего можно показать в
случае, когда value - 2D-вектор. Тогда cur, prev, next - какие-то точки на
плоскости, сплайн - проведенная через них кривая, r - вектор-градиент
кривой в точке cur, он же является касательной (точнее, направляющим вектором
прямой, являющейся касательной) в этой точке. Параметр tension непосредственно
изменяет длину градиента; bias меняет веса g1, g2 в g3; continuity заставляет
конец градиента "ездить" вдоль g3. Все это соотвествующим образом влияет на
вид самой кривой. Для лучшего понимания посмотрите на приведенную картинку,
представьте себе гладкую линию (кривую), проведенную через точки prev, cur,
next и учтите, что r - это желаемое нами положение касательной прямой к этой
кривой в точке cur.

    value.y
       |                (aux)
       |                  @
       |                / |
       |        cur  / g1 |
       |           *      |
       |            \ \ r |
       |             \   \@
       |    *         \   |
       | prev          \  | g3
       |             g2 \ |
       |                 \|
       |                  * next
       +
    ---O--------------------------value.x
       |

В начальных и конечных точках задания функции производные ra, rb считаются
по-другому, так как для них нельзя указать предыдущую или следующую точку.
Для начальной точки

    ra = next.value - cur.value,
    rb = (1.5 * (next.value - cur.value) - 0.5 * next.ra) * (1 - tension).

Для конечной точки

    ra = (1.5 * (cur.value - prev.value) - 0.5 * prev.rb) * (1 - tension),
    rb = cur.value - prev.value.

ra для начальной точки и rb для конечной на самом деле не используются, они
приведены здесь лишь для того, чтобы формулы давали правильный результат в
случае, если есть всего две точки p0, p1; тогда

    p0.rb = p1.ra = (p1.value - p0.value) * (1 - tension).

Осталось упомянуть про параметры ease to и ease from. Они контролируют
нелинейность движения по полученной кривой в зависимости от времени - или,
если угодно, нелинейность самого времени. Не особо вникая в детали, корректно
отработать все это можно с помощью следующего куска кода:

    // ...

    float ease(float t, float a, float b) {
      float k;
      float s = a + b;

      if (s == 0.0) return t;
      if (s > 1.0) {
        a = a / s;
        b = b / s;
      }
      k = 1.0 / (2.0 - a - b);
      if (t < a)
        return ((k / a) * t * t);
      else {
        if (t < 1.0 - b){
          return (k * (2 * t - a));
        } else {
          t = 1.0 - t;
          return (1.0 - (k / b) * t * t);
        }
      }
    }

    // ...

    time = ease(time, beginKey.easeFrom, endKey.easeTo);

    // ...

Подведем итог. Для того, чтобы вычислить значение какой-то величины (скажем,
положения объекта) в какой-то момент времени, придется сделать следующее:
    - найти те два ключа, между которыми попадает этот момент времени (если
      ключ всего один, значение просто постоянно);
    - перевести глобальное время в локальное для отрезка между этими ключами;
    - скорректировать локальное время с помощью функции ease();
    - посчитать "выходящую" производную rb для начального ключа и "входящую"
      производную ra для конечного ключа;
    - по значениям величины в ключах, посчитанным производным и локальному
      времени посчитать интерполированное значение.

7.7. Кватернионы
----------------

Кватернион, он же гиперкомплексное число, представляет собой набор четырех
чисел. Иногда будет удобно представлять себе кватернион как 4D-вектор,
иногда как набор четырех чисел, иногда как число и 3D-вектор, а иногда и
как гиперкомплексное число с тремя мнимыми единицами i, j, k; таким образом,
имеем следующие представления:

    q = [x1,x2,x3,x4] = [scalar,(vector)] = [x1,(x2,x3,x4)] =
      = x1+x2*i+x3*j+x4*k.

Сложить или вычесть два кватерниона, а также умножить кватернион на число
можно, как обычно, покомпонентно; с умножением ситуация более сложная.
Умножение кватернионов должно в результате дать тоже кватернион, то есть
конструкцию, содержащую лишь слагаемые вида r и r*l, где r - действительное
число, а l - одна из мнимых единиц. Поэтому надо как-то определить операцию
умножения для любых двух мнимых единиц. Определяется она так, что умножение
получается некоммутативным, т.е. от перестановки мест множителей произведение
меняется, и x*y != y*x. Поэтому умножение двух кватернионов приходится
выполнять не по привычным правилам арифметики, а по следующим аксиомам:

    a*(b*c) = (a*b)*c,      (ассоциативность)
    (a+b)*c = a*c+b*c,      (транзитивность)
    a*(b+c) = a*b+a*c,      (транзитивность)
    a*1 = 1*a = a,          (существование единицы)
    a*0 = 0*a = 0,          (существование нуля)
    i*i = j*j = k*k = -1,   (свойство мнимых единиц)
    i*j = -j*i = k.         (связь между мнимыми единицами i, j, k)

Из этих правил, кстати, следует, что

    j*k = -k*j = i,
    k*i = -i*k = j,

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

       |  i  |  j  |  k
    ---+-----+-----+-----
     i | -1  |  k  | -j
     j | -k  | -1  |  i
     k |  j  | -i  | -1

Кроме того, из этих правил можно вывести правило для умножения кватернионов,
заданных в форме [scalar,vector]:

    q1 = [s1,v1],
    q2 = [s2,v2],
    q1*q2 = [s1*s2 - v1*v2, s1*v2 + s2*v1 + v1xv2].

Здесь v1*v2 - скалярное произведение векторов v1, v2; v1xv2 - векторное, все
остальные произведения обычные (либо число на число, либо число на вектор).

Нужны же кватернионы для представления и интерполяции поворотов. Поворот
относительно оси (x,y,z) (иными словами, поворот вокруг вектора (x,y,z),
проведенного из начала координат) на угол angle представляется кватернионом
q, лежащим на единичной 4D-сфере (то есть, 4D-вектором длины 1):

    s = cos(angle/2),
    v = (x,y,z) * sin(angle/2) / |(x,y,z)|,
    q = [s,v].

Что интересно, в такой форме поворот, соответствующий комбинации поворотов
q1 и q2, просто равен их произведению. В случае с 3D Studio это позволяет
быстро и просто перевести сохраненные в CHUNK_TRACKROTATE относительные
повороты в абсолютные: просто читаем эти самые повороты (а записаны они как
раз в форме [angle,(x,y,z)], причем длина вектора (x,y,z) уже приведена к
единичной), переводим их в кватернионную форму, получаем набор кватернионов
q0, q1, ..., q(n-1), qn. Здесь q0 и так задает абсолютный поворот, а вот все
остальные придется переводить (умножение здесь, конечно, кватернионное):

    absolute_q0 = q0,
    absolute_q1 = q1*absolute_q0,
    absolute_q2 = q2*absolute_q1,
    ...
    absolute_qn = qn*absolute_q(n-1).

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

Все кватернионы, задающие повороты, должны лежать на единичной 4D-сфере,
поэтому простейший метод (линейная интерполяция) несколько усложнится: мы
вынуждены интерполировать не по прямой между двумя векторами, а по дуге на
этой 4D-сфере, являющейся сечением сферы плоскостью, проходящей через центр
сферы и наши два вектора, то есть две точки на сфере. Все это называется
сферической линейной интерполяцией (spherical linear interpolation, если
скоращенно, slerp) и определяется следующим образом:

    slerp(q1,q2,t) = (q1*sin((1-t)*a) + q2*sin(t*a)) / sin(a),

где t - локальное время (см.п.7.6), a - угол между векторами q1, q2;

    0 <= t <= 1,
    cos(a) = (q1,q2)/(|q1|*|q2|) = (q1,q2).

То есть q1, q2 здесь уже рассматриваем как 4D-вектора. Приведенную формулу
нетрудно вывести (для лучшего понимания): нам нужна такая точка q, которая
лежит на единичной сфере, лежит в одной плоскости с q1 и q2 и центром (то
есть нулем), причем угол между векторами q и q1 меняется линейно и, таким
образом, равен t*a. Раз точка лежит в одной плоскости с 0, q1, q2, то
вектор q равен линейной комбинации векторов q1, q2:

    q = k1*q1 + k2*q2,

где k1, k2 - какие-то (пока неизвестные) коэффициенты. q лежит на сфере,
значит, длина q равна 1, отсюда имеем:

    |q| = (q,q) = 1,
    (k1*q1+k2*q2, k1*q1+k2*q2) = 1,
    k1*k1*(q1,q1) + k2*k2*(q2,q2) + 2*k1*k2*(q1,q2) = 1,
    k1*k1 + k2*k2 + 2*k1*k2*(q1,q2) = 1.

Угол между q и q1 равен t*a, отсюда:

    cos(q,q1) = cos(t*a),
    (q,q1) = cos(t*a),
    k1*(q1,q1) + k2*(q1,q2) = cos(t*a),
    k1 + k2*(q1,q2) = cos(t*a).

Получили систему уравнений для k1, k2:

    k1 + k2*(q1,q2) = cos(t*a),
    k1*k1 + k2*k2 + 2*k1*k2*(q1,q2) = 1,

или

    k1 + k2*cos(a) = cos(t*a),
    k1*k1 + k2*k2 + 2*k1*k2*cos(a) = 1.

Отсюда k1 = (cos(t*a) - k2*cos(a)), и получаем квадратное уравнение:

    cos(t*a)^2 - 2*k2*cos(a)*cos(t*a) + k2^2*cos(a)^2 + k2^2 +
      2*k2*cos(a)*cos(t*a) - 2*k2^2*cos(a)^2 = 1,

    cos(t*a)^2 + k2^2*(1 - cos(a)^2) = 1,

    k2^2 * sin(a)^2 = sin(t*a)^2,

    k2 = sin(t*a) / sin(a),

    k1 = cos(t*a) - sin(t*a)*cos(a) / sin(a) =
       = (cos(t*a)*sin(a) - sin(t*a)*cos(a)) / sin(a) =
       = sin(a - t*a) / sin(a) = sin((1 - t)*a) / sin(a).

Если a - очень маленький угол, настолько, что могут возникнуть ошибки при
делении на sin(a), можно использовать обычную линейную интерполяцию (так
как при маленьких значениях a sin(a) ~= a, sin(t*a) ~= t*a, и так далее).

Итак, мы умеем задавать повороты кватернионами, мы умеем их интерполировать
линейно по множеству их возможных значений, то есть, поверхности сферы. Но
хочется ведь интерполировать сплайнами Кочанека-Бартельса (далее везде, где
используется термин "сплайны", подразумеваются именно такие сплайны), так
как ориентация объекта должна меняться плавно, а не рывками, и желательно
по совршенно той же траектории, что и в 3D Studio. Причем строить сплайны
надо на поверхности четырехмерной сферы, иначе результаты интерполяции не
будут соответствовать поворотам; кватернион-поворот должен обязательно
лежать на единичной 4D-сфере. Естественное, возникает вопрос - как все это
сделать?

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

    g(t) = v1*(1-t)^3 + c1*3*t*(1-t)^2 + c2*3*t^2*(1-t) + v2*t^3,

и считаем ее значение в произвольно взятой точке t, используя только
линейную интерполяцию (linear interpolation, lerp): пусть

    lerp(a, b, t) = a*(1-t) + b*t,

тогда g(t) можно посчитать вот так:

    tmp1 = lerp(v1, c1, t),
    tmp2 = lerp(c1, c2, t),
    tmp3 = lerp(c2, v2, t),
    tmp4 = lerp(tmp1, tmp2, t),
    tmp5 = lerp(tmp2, tmp3, t),
    g(t) = lerp(tmp4, tmp5, t).

Нам же надо интерполяцию сплайнами по поверхности сферы, это можно получить,
всего-навсего заменив в приведенных выше формулах линейную интерполяцию lerp
на наш сферический вариант, slerp. Далее, сравнивая g(t) с полученной в
п.7.6. интерполяционной функцией f(t) можно заметить, что, если

    p1 = v1              <=>   v1 = p1,
    r1 = (c1 - v1) * 3   <=>   c1 = (p1 + r1) / 3,
    r2 = (v2 - c2) * 3   <=>   c2 = (p2 - r2) / 3,
    p2 = v2              <=>   v2 = p2,

то g(t) совпадает с f(t). Длинный и нудный вывод для v1, v2, c1, c2 через
функции lerp()/slerp() делать, пожалуй, смысле нет, так что ограничимся
конечными результатами. А именно, для каждой точки-ключа cur имеем

    g1 = slerp(cur, prev, -(1+bias)/3.0);
    g2 = slerp(cur, next,  (1-bias)/3.0);
    g3 = slerp(g1, g2, 0.5 + 0.5*continuity);
    g4 = slerp(g1, g2, 0.5 - 0.5*continuity);
    cur.ra = slerp(cur, g3,  (tension-1));
    cur.rb = slerp(cur, g3, -(tension-1));

Для начальной и конечной точки, соответственно, имеем следующее:

    q0.rb = slerp(p0, p1, (1-tension)*(1+continuity*bias)/3.0);
    qn.ra = slerp(pn, p(n-1), (1-tension)*(1-continuity*bias)/3.0);

При интерполяции между какими-то точками a и b просто полагаем

    v1 = a,
    c1 = a.rb,
    c2 = b.ra,
    v2 = b,

и считаем g(t) по приведенному выше алгоритму. Здесь мы до сих пор не учли
параметры ease to и ease from, но это дело одной строки кода - посчитать на
самом деле надо не g(t), а g(ease(t)). Впрочем, обычно ease(t) = t. Что это
за функция ease(), откуда она берется, для чего нужна и как рассчитывается,
написано в п.7.6.

Таким образом, получаем кватернион, соответствующий повороту, задающий
ориентацию объекта. Осталось выяснить, как из этого кватерниона получить
что-нибудь более привычное - скажем, матрицу поворота. С одной стороны,
вспомнив, как делается перевод в кватернионную форму для поворота на угол
angle относительно оси (x,y,z), можно написать, что

    q = [s,v],
    angle = 2 * arccos(angle),
    (x,y,z) = v / sin(angle/2),

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

    q = [w,(x,y,z)],

        [ 1-2*(y*y+z*z)   2*(x*y-w*z)     2*(x*z+w*y)   ]
    A = [ 2*(x*y+w*z)     1-2*(x*x-z*z)   2*(y*z-w*x)   ]
        [ 2*(x*z-w*y)     2*(y*z+w*x)     1-2*(x*x-y*y) ].

Подведем итог. Для интерполяции ориентации объекта в какой-то момент времени
с помощью кватернионов и сплайнов придется сделать почти то же самое, что и
в случае "обычной" интерполяции чего-нибудь сплайнами (п.7.6). Различия же
заключаются в следующем:

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

Все остальное совпадает с планом действий при "обычной" сплайновой
интерполяциии и изложено в пункте 7.6.

7.8. Обратная трассировка лучей
-------------------------------

Обратная трассировка лучей (она же рэйкастинг, raycasting) - простой, хотя
и довольно медленный, метод получения высокореалистичных изображений. Этот
метод часто путают с прямой трассировкой лучей (рэйтрэйсинг, raytracing),
которая, на самом деле, практически никогда и никем не используется из-за
своей редкостной неэффективности. Впрочем, эти два термина уже практически
и не различают.

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

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

Непосредственное освещение от источника света считаем, например, по уравнению
Фонга (см. п.5.1). На самом деле, компоненты diffuse и specular в этом
уравнении для большей реалистичности с точки зрения физики надо разделить
на квадрат расстояния до источника света, но обычно этим пренебрегают.

Ослабление света в прозрачной среде учитывается делением на коэффициент

    k = exp(beta * l),

где

    k    - коэффициент ослабления,
    beta - коэффициент прозрачности среды,
    l    - длина пути внутри среды.

Наконец, преломляется луч света по следующему закону:

     sin(b) = n1 * sin(a) / n2,

где

    a - угол между падающим лучом L и нормалью N,
    b - угол между преломленным лучом L' и нормалью N,
    n1 - коэффициент преломления среды, в которой проходит луч L,
    n2 - коэффициент преломления среды, в которой проходит луч L'.

Вот иллюстрация.

                 N
                 |
         L       |
           \   a |
             \ ,-|
               \ |      среда 1
    -------------P----------------
                 |\     среда 2
                 | \
                 |-'\
                 | b \
                 |    L'

Для воздуха считают beta = 0, n = 1; для всех остальных сред обычно beta > 0,
n > 1. Надо отметить, что все эти коэффициенты (отражения, преломления,
прозрачности) различны для каждой из трех цветовых компонент R, G, B. Еще
надо отметить, что обычно объекты непрозрачны и поэтому преломлением
пренебрегают.

Алгоритм работы функции трассировки луча с началом o = (ox,oy,oz) и
направлением d = (dx,dy,dz), возвращающей, кстати, освещенность по всем трем
цветовым компонентам, будет, таким образом, выглядеть примерно так:

    - ищем ближайшее пересечение луча со сценой (определяем точку p, где
      произошло пересечение, выясняем, с каким конкретно объектом оно
      произошло)
        - если не нашли, возвращаем 0
        - если пересечение есть, текущую освещенность полагаем равной
          фоновой освещенности (ambient)
    - определяем вектор n, нормаль к объекту в точке пересечения
    - для кажого (точечного) источника света
        - считаем вектор l, соединяющий источник и точку p (начало в p)
        - ищем пересечение луча с началом в точке p и направлением d со сценой
            - если нашли, прекращаем обработку этого источника, так как
              его не видно
        - считаем симметричный l относительно n вектор r
        - считаем по уравнению Фонга (оно использует n, l, r, d) освещенность
          в точке за счет этого источника света, добавляем ее к текущей
    - считаем симметричный d относительно n вектор refl, то есть отраженный
      вектор
    - трассируем отраженный луч (с началом p и направлением refl), добавляем
      полученную освещенность к текущей
    - считаем направление преломленного луча (вектор refr) по d, n и
      коэффициентам преломления
    - трассируем преломленный луч (с началом p и направлением refr), добавляем
      полученную освещенность к текущей
    - покомпонентно умножаем текущую освещенность на цвет объекта
    - если для материала, заполняющего пройденную лучом от o до p трассу
      beta != 0, умножаем текущую освещенность на коэффициент ослабления
    - возвращаем текущую освещенность

При стандартной камере, которая находится в (0,0,-dist), и ориентирована так,
что пикселу экрана (sx,sy) соотвествует 3D-точка (sx-xSize/2, ySize/2-sy, 0),
для получения цвета пиксела (sx,sy), очевидно, достаточно оттрассировать луч,
положив при этом

    ox = oy = dz = 0,
    oz = -dist,
    dx = sx - xSize / 2,
    dy = ySize / 2 - sy.

Секция 6 из 6 - Предыдущая - Следующая

 demo.design 3D programming FAQ.
Лента новостей


2006 (c) Copyright Hardline.ru