Трансформации

30.01.2000 — 21.04.2000

Внимание

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

Определения

Система координат (СК): — способ задания координат. Кроме количества и обозначения величин, задающих координаты (например, x, y, z), системы координат различаются и точками, из которых ведутся отсчеты систем координат.
Поворот точки: — изменение координат точки так, чтобы не изменялось расстояние между этой точкой и центром координат. Обычно повороты производятся вокруг точки центра координат — в двухмерном мире, или вокруг оси, проведенной через центр координат — в трехмерном пространстве.
Поворот вектора: — изменение направление вектора без изменения его длины. Выполняется аналогично повороту точки.
Перенос: — изменение координат всех точек объекта на одинаковую величину. Это движение без вращения. Обращаю внимание, что перенос делается только для точек, но не для вектора.
Трансформация: — здесь: нахождение координат точки в заданной системе координат, используя координаты точки в другой системе. В Elfish трансформация может включать в себя переносы и/или вращения. При трансформации положение точки не изменяется.
Единичная трансформация: — трансформация, не изменяющая координат точки (вектора).
Нормальный вектор: — вектор, имеющий длину 1. Таким вектором принято указывать направление.
Нормализация вектора: — приведение длины вектора к 1, без изменения его направления.
Мировая система координат: — система координат, считающаяся неподвижной. Обычно относительно такой системы координат задается положение объектов и камеры.
Пространство просмотра: — система координат, в которой камера находится в центре. В Elfish ось координат Z направлена по направлению камеры, Y — вверх, X — вправо.
Примитив: — здесь: основная единица, из которой строится изображение. Это могут быть точки, линии, треугольники или что-нибудь в этом роде.

Небольшое предисловие

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

Выражаю благодарность Epic Games, Inc. (отдельное спасибо to Tim Sweeney) за предоставленные исходники игры Unreal Tournament, в которых использовались исключительно векторные трансформации, которые и подтолкнули меня к написанию этого руководства. :-)

Зачем трансформации?

Все просто: монстры должны поворачиваться и перемещаться. Большинство предметов в трехмерном мире делают это, и будет очень странно, если в Elfish такого не будет. ;-) Так что вот: трансформации нужны для того, чтобы перемещать и поворачивать предметы. Сейчас я кое-что о них расскажу...

Многопространственность

Трехмерные движки устроены так, что каждый объект "варится в своем собственном пространстве" — в своей собственной системе координат. Например, вершины треугольников, из которых состоит ракета, могут быть определены относительно центра этой ракеты. Центр ракеты можно переместить или повернуть — и тогда можно будет переместить и повернуть все вершины ракеты в одно действие.

объекты в разных пространствах

Также, обычно в движках существует неподвижная система координат, относительно которой задаются пространства объектов и камеры — "мировая" система координат. Если смотреть на рисунок, то можно представить, что положения красного и зеленого объектов и камеры заданы относительно черной системы OXYZ. Чтобы выполнять рисование в такой системе координат, координаты объектов должны быть преобразованы сначала в неподвижное пространство, а затем — в пространство камеры.

Устройство пространств

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

В Elfish используются декартовы пространства — когда оси координат заданы взаимно перпендикулярными единичными векторами.

Положение начала системы координат задается одним вектором, и еще тремя векторами задается ориентация (поворот) этой системы координат:

// Так, как это сделано в Unreal Tournament
class cCoords // Coordinate system
{
private:
    cVector Origin; // положение центра координат
    cVector XAxis, YAxis, ZAxis; // направления осей координат
                                 // (всегда единичные вектора)

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

Все системы координат заданы относительны друг друга; фактически, нет неподвижной системы координат — мировая система только считается неподвижной.

Если задать систему координат Origin = (0, 0, 0), XAxis = (1, 0, 0), YAxis = (0, 1, 0), ZAxis = (0, 0, 1), то она будет совпадать с той координатной системой, относительно которой она задана. Трансформация в такую систему координат называется единичной, т.к. при трансформации в нее координат, они (координаты) не изменяются.

Функция трансформации

Для начала я напомню о скалярном умножении векторов. Это операция, когда координаты векторов попарно умножаются, а затем складываются, таким образом образуя одно число. Заодно опишу вектор...

class cVector
{
public:
    float x, y, z;

public:
    // scalar product - скалярное произведение
    float operator | (const cVector &V) const
    {
        return x*V.x + y*V.y + z*V.z;
    }

Все другие векторные операции можно найти в файле cVector.h примера.

Из курса школьной геометрии известно, что скалярное произведение векторов равняется произведению их длин, умноженному на косинус угла между ними. А также есть следствие, гласящее: результатом скалярного произведения является длина проекции вектора A на B, умноженная на длину вектора B.

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

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

cVector cCoords::TransformVector(const cVector &Src) const
{
    // Без переноса - только поворот.
    // Создается вектор, координаты
    // которого - длины проекций на оси координат.
    return cVector(Src | XAxis, Src | YAxis, Src | ZAxis);
}

cVector cCoords::TransformPoint(const cVector &Src) const
{
    // вначале - перенос точки в желаемое пространство,
    // а затем точка поворачивается в этом пространстве
    return TransformVector(Src - Origin);
}

Собственно, вот и все. Если вам это понятно, то можете считать себя крутым профессионалом. ;)

Движение систем координат

Elfish использует трансформации следующим образом. Точки моделей определены относительно своих систем координат. Эти системы координат движутся относительно мировой системы координат. Система координат камеры также движется относительно мировой системы координат.

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

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

перенос ракеты

Допустим, в мировой координатной системе M есть ракета, которую нужно перенести. Начальное положение ракеты — координатная система O, конечная — система O'. Как передвинуть координатную систему? Простой способ — это просто прибавить к Origin нужную величину. Но мы не ищем легких путей, ибо этот способ неприемлем для поворотов.

В этом месте я напомню, что трансформация — это нахождение координат точки в заданном пространстве. А также напомню, что я задал пространства векторами. Отсюда следствие: можно находить координаты пространств относительно других пространств.

Итак, строится координатная система M' такая, что трансформация M => M' обратна трансформации O => O'. Короче говоря, координаты ракеты O в системе M' будут такие же, как и координаты ракеты O' в системе M.

Нелегкий способ принуждает нас находить координаты O в M', чтобы найти координаты O' в M.

движение — это трансформация

То, что справедливо для переноса, справедливо и для любой трансформации.

Как осуществляется движение систем координат? Вот так: строится система координат, обратная величине перемещения исходной системы. Затем производится трансформация векторов координатной системы в созданную систему. Таким образом — производя трансформации в пространства, противоположные движению, получается движение.

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

Создание систем кординат

Объединение трансформаций

Трансформация производится пространством. Следовательно, если несколько раз перенести и повернуть систему координат, то можно выполнить все эти трансформации за один раз — всего лишь трансформировав точку в это пространство.

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

Выглядит объединение трансформаций так: A_to_C = B_to_C * A_to_B. Почему так перевернуто? Для совместимости с операцией *=. Если записывается A *= B, то это означает, что A трансформируется в B. Можно было бы и наоборот, только я не хочу отклоняться от линии, заложенной в UT.

// Вначале перегружу немного конструкторов...

cCoords::cCoords(): Origin(0, 0, 0), 
    XAxis(1, 0, 0), YAxis(0, 1, 0), ZAxis(0, 0, 1) {}
// Пространство единичной трансформации

cCoords::cCoords(const cCoords &T) // Конструктор копирования
{
    *this = T;
}

// Перегруженный оператор копирования... 
cCoords &cCoords::operator = (const cCoords &T)
{
    Origin = T.Origin;
    XAxis = T.XAxis;
    YAxis = T.YAxis;
    ZAxis = T.ZAxis;
    return *this;
}

cCoords &cCoords::operator *= (const cCoords &B)
{
    Origin = B.TransformPoint(Origin);
    XAxis = B.TransformVector(XAxis);
    YAxis = B.TransformVector(YAxis);
    ZAxis = B.TransformVector(ZAxis);
    return *this;
}
cCoords cCoords::operator * (const cCoords &T) const
{
    return cCoords::cCoords(*this) *= T;
}

А теперь — об обратной трансформации. Она делается так: Back = cCoords() * Source. Т.е. координаты центра координат в неком пространстве обратны координатам этого пространства.

cCoords cCoords::Back()
{
    return cCoords() * *this;
}

Теперь можно объединить системы координат объекта и камеры. Чтобы сделать координатную систему преобразования из пространства объекта в пространство камеры, нужно узнать координаты камеры в пространстве объекта: ObjectToCamera = WorldToCamera * ObjectToWorld. Или, поскольку положение объектов задается относительно мировой системы, а не наоборот: ObjectToCamera = WorldToCamera * WorldToObject.Back().

Перенос

Перенос — это круто!

void cCoords::AddTranslation(const cVector &Translation)
{
    Origin += Translation;
}

Вот и все. :-)

Вращение вокруг оси Z

Вращение в трехмерном пространстве происходит вокруг каких-нибудь осей. Для начала я сделаю поворот вокруг оси Z — эта самый простой поворот. Правда, придется вспомнить самую трудно запоминающуюся формулу тригонометрии... ;-)

Если поворачивать точки/вектора вокруг оси Z, то у этих точек/векторов будут изменяться только координаты X, Y. А значит, поворот в трехмерном пространстве вокруг оси координат — это поворот в двухмерном пространстве.

Итак, приступим. Пусть нужно повернуть точку 1 (смотрите рисунок) на угол a, и получить таким образом точку 2.

поворот двухмерной точки

Вот перед вами вывод формулы поворота точки вокруг центра координат.

o1 = o2 = R; // расстояние от центра координат до точки

// косинус угла равен отношению прилежащего катета к гипотенузе
Cos(b) = x1 / R;
// с синусом что-то похожее...
Sin(b) = y1 / R;

// вот эти самые формулы изучались в восьмом классе...
Cos(a+b) = Cos(a) * Cos(b) - Sin(a) * Sin(b) = x2 / R;
Sin(a+b) = Sin(a) * Cos(b) + Cos(a) * Sin(b) = y2 / R;

// Заменим Sin и Cos a на R...
x1/R * Cos(a) - y1/R * Sin(a) = x2/R;
x1/R * Sin(a) + y1/R * Cos(a) = y2/R;

// А теперь сократим на R
x2 = x1 * Cos(a) - y1 * Sin(a);
y2 = x1 * Sin(a) + y1 * Cos(a);

Как видите, все просто!

поворот осей координат

Из курса тригонометрии восьмого класса известно, что единичные вектора в качестве (x, y) имеют, соответственно, (cos, sin) своего поворота. А это значит — синусы/косинусы являются координатами векторов, задающих пространство! Допишу небольшую функцию к cCoords... Главное — не забыть, что прибавлять к системе координат нужно систему обратной трансформации (смотрите предыдущую главу "Движение систем координат").

// Немного удобства...
cCoords::cCoords(const cVector &O,
    const cVector &X, const cVector &Y, const cVector &Z)
    : Origin(O), XAxis(X), YAxis(Y), ZAxis(Z) {}

// Повернуть систему координат на некоторый угол...
void cCoords::AddRotationZ(const float Z)
{
    *this *= cCoords(
        cVector(0.0, 0.0, 0.0),

        cVector( cosf(Z), -sinf(Z), 0.0 ),
        cVector( sinf(Z),  cosf(Z), 0.0 ),
        cVector(   0.0,      0.0,   1.0 )
        ).Back();
}

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

Немного подробнее...

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

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

Обратите внимание на операцию поворота, которая будет применяться в данном случае: ObjectCoordinateSystem *= RotationCoordinateSystem.Back();

Сначала создается система координат, обратная тому, куда должна переместиться система координат объекта, а затем в ней находятся координаты системы этого объекта. Все так, как писалось в главе Движение систем координат. Не поленитесь — прочитайте ее еще раз, и все сразу станет понятнее. :-)

Поворот вокруг произвольной оси

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

поворот вокруг произвольной оси

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

void cCoords::AddAxisRotation(const cVector &Axis, float Angle)
{
    // requires Axis to be normalized
    float AngleCos = cosf(Angle * 0.5f);
    float AngleSin = sinf(Angle * 0.5f);

    float x = Axis.x * AngleSin;
    float y = Axis.y * AngleSin;
    float z = Axis.z * AngleSin;
    float w = AngleCos;

    float xx = x*x; float xy = x*y; float xz = x*z; float xw=x*w;
    float yy = y*y; float yz = y*z; float yw = y*w;
    float zz = z*z; float zw = z*w;

    *this *= cCoords(
        cVector(0, 0, 0),
        
        cVector(1 - 2*(yy+zz),     2*(xy-zw),     2*(xz+yw)),
        cVector(    2*(xy+zw), 1 - 2*(xx+zz),     2*(yz-xw)),
        cVector(    2*(xz-yw),     2*(yz+xw), 1 - 2*(xx+yy))
        ).Back();
}

У меня есть мысль, как получить это пространство, используя последовательные повороты вокруг осей координат. Можно повернуть желаемую ось так, чтобы она совпадала с какой-нибудь осью координат, например с OZ. Затем — повернуть вокруг оси OZ на нужный угол, а потом вернуть желаемую ось "на родину". Вполне возможно, что поле всех этих поворотов получится описанная в функции трансформация.

На этом все, курс трехмерных трансформаций можно считать пройденным. Большее в Elfish не используется.

Стек трансформаций

Хотя в Elfish и не применяется стек трансформаций, эта информация пригодится Вам, чтобы лучше понимать устройство трехмерного мира. К тому же Direct3D и OpenGL используют такие стеки, и, вполне возможно, Elfish в будущем будет их использовать.

Рассмотрим стек на примере скелетной модели:

скелетная модель

Здесь есть следующие пространства: 0 — пространство камеры, 1 — мировое пространство, 2 — пространство туловища модели, 3 — пространство плеча, 4 — пространство руки. Причем каждое следующее пространство задано относительно предыдущего. Сделано так, чтобы можно было, например, свободно вращать всей рукой, изменяя всего лишь координатную систему плеча 3.

Чтобы нарисовать такую модель, для каждой части модели выполняются несколько трансформаций. Например, чтобы нарисовать плечо, придется делать 3 трансформации: плечо => туловище, туловище => мировая система, мировая система => камера. Конечно, не обязательно делать всю эту последовательность трансформаций для каждой точки плеча — можно объединить последовательность трансформаций в одну.

А для скорости и удобства, чтобы не объединять трансформации 0, 1, 2 несколько раз — для 3 и 3', для координатных систем используется стек. Работает это так:

Координатная система, делающая трансформацию 1 => 0 кладется на вершину стека.
В стек копируется верхняя трансформация, и к ней добавляется координатная система 2 => 1. Теперь верхняя координатная система способна переводить координаты точек туловища в пространство камеры (2 => 0).
В стек копируется верхняя трансформация.
Трансформация 3 => 2 добавляется к верхней. Теперь можно делать преобразование плечо => камера.
Аналогично в стек складываются все остальные трансформации.
После работы с каждым пространством, его трансформация изымается из стека — все происходит в обратном направлении.
Когда трансформация 3 => 0 изымается из стека, оставшуюся трансформацию можно использовать для пространства 3', запустив в стек трансформацию 3' => 2.

В Elfish пока не используется скелетных моделей.

Пример

В примере показаны оси мировой системы координат, и относительно мировой системы координат крутится треугольник.

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

Я сделал объект Graphics частью именного пространства Globals — для удобства. Еще в этот объект добавлена функция, принимающая массив вершин, и выводящая список треугольников, список линий или просто список точек — в зависимости от параметра:

struct cColor
{
    float r, g, b;
    cColor(float r_, float g_, float b_): r(r_), g(g_), b(b_) {}
    cColor(): r(0.5f), g(0.5f), b(0.5f) {}
    cColor(const cColor &C): r(C.r), g(C.g), b(C.b) {}
};

struct cVertex
{
    cVector V;
    cColor C;
    cVertex(cVector &V_, cColor &C_): V(V_), C(C_) {}
    cVertex() {}
};

class oGraphics
{
public:
    enum PrimitiveType { Points, Lines, Triangles };
    void virtual Draw(PrimitiveType Type, 
        int Count, const cVertex *Vertices);
};

///////////////////////////////////////////////////////////
//  "Универсальная" функция вывода примитивов.
///////////////////////////////////////////////////////////

void oGraphics::Draw(PrimitiveType Type, 
        int Count, const cVertex *Vertices)
{
    switch (Type)
    {
    case Points:
        glBegin(GL_POINTS);
        break;
    case Lines:
        glBegin(GL_LINES);
        break;
    case Triangles:
        glBegin(GL_TRIANGLES);
        break;
    }
    for (int i = 0; i < Count; i++)
    {
        glColor3f(Vertices->C.r, Vertices->C.g, Vertices->C.b);
        glVertex3f(Vertices->V.x, Vertices->V.y, Vertices->V.z);
        Vertices++;
    }
    glEnd();
}

///////////////////////////////////////////////////////////
//  Немного рисования...
///////////////////////////////////////////////////////////

#define Pif 3.14159265358979323846f

void oGraphics::DrawTestTriangle()
{
    static float Angle = 0;
    Angle += Pif/3200;

    //------- Camera
    cTransf WorldToCamera;
    WorldToCamera.AddAxisRotation
        (cVector(1, 1, 1).Normalize(), Angle / 4);

    //------- Triangle
    cTransf TriToWorld;
    TriToWorld.AddAxisRotation
        (cVector(0, 0, 1).Normalize(), Angle);
    TriToWorld.AddTranslation
        (cVector(0.5f, 0, 0));
    TriToWorld.AddAxisRotation
        (cVector(0, 0, 1).Normalize(), Angle * 7);

    cTransf TriToCamera = WorldToCamera * TriToWorld.Back();
 
    cVertex Tri[3] = {
        cVertex(cVector(0.5f, 0.5f, 0) *= 0.5f, cColor(1, 0, 0)),
        cVertex(cVector(-0.7f, 0, 0) *= 0.5f, cColor(0, 1, 0)),
        cVertex(cVector(0, -0.7f, 0) *= 0.5f, cColor(0.3f, 0.3f, 1))
    };
    for (int i = 0; i < 3; i++)
        Tri[i].V = TriToCamera.TransformPoint(Tri[i].V);
    Draw(Triangles, 3, Tri);

    //------- Axises
    cTransf AxToCamera = WorldToCamera;

    cVertex Axis[6] = {
        cVertex(cVector(0, 0, 0), cColor(0.5f, 0.5f, 0.5f)),
        cVertex(cVector(1, 0, 0), cColor(1, 0, 0)),
        cVertex(cVector(0, 0, 0), cColor(0.5f, 0.5f, 0.5f)),
        cVertex(cVector(0, 1, 0), cColor(0, 1, 0)),
        cVertex(cVector(0, 0, 0), cColor(0.5f, 0.5f, 0.5f)),
        cVertex(cVector(0, 0, 1), cColor(0, 0, 1))
    };
    for (i = 0; i < 6; i++)
        Axis[i].V = AxToCamera.TransformPoint(Axis[i].V);
    Draw(Lines, 6, Axis);
}

Как говорится, Enjoy.

Следующая страница: Область просмотра