Законы существуют, чтобы их нарушать, однако тот, кто ради временного жертвует вечным, теряет и временное, и вечное.

«Атхарва Веда»

Организация законов управления и взаимодействия — вот о чем пойдет речь в этой статье.

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

Ну, а материалы наших прошлых занятий, а также руководство по двумерному пакету ЛКИ-Creator 2D и микроучебник языка Delphi вы можете найти на нашем диске в разделе «Своими руками».

Перед началом работы нам, как обычно, потребуется переустановить пакет ЛКИ-Creator 3D. Как это делается — описано в предыдущих статьях.

Управление объектами с помощью мыши (Picking)

Предположим, мы хотим щелкнуть левой клавишей по дельфинчику из примера Dolphin и в ответ получить от него некую реакцию: всплеск пузырьков, изменение положения в пространстве и т.п. Нам очевидно, что щелкаем именно по дельфину. Но как выделить нужный объект, имея на руках лишь координаты курсора мыши, тем более — в масштабе окна, а не нашего трехмерного мира? Для этого существует технология, называемая picking (выбор).

Она реализована в стандартном методе ЛКИ-Creator 3D, но, поскольку бывают жизненные ситуации, когда метод выбора объекта нужно переопределить, — разберемся, как работает picking.

Итак...

Что мы знаем

Мы знаем, что нужный нам объект спроектирован на некоторую площадь, окружающую точку, указанную мышью. А на самом деле он спроектирован на окрестность точки p, которая соответствует точке s, выделенной мышью на экране. То есть мы имеем дело с объектом в трехмерном пространстве и его проекцией.

Итак, при щелчке должен быть выбран объект, который пересекает луч, проходящий через точку p, и, соответственно, проекция этого объекта включает точку p. Для того чтобы провести луч, нужно две точки, поэтому в качестве начала луча выберем местоположение камеры — точку с проекцией в центре координат. Соответственно, нужно построить луч для выбора объектов (picking ray), а затем перебрать объекты игрового мира и проверить каждый на пересечение с лучом. Сразу следует отметить, что перебор может занять очень много времени и ресурсов, если объектов много. В этом случае можно рекомендовать разбить игровое пространство на домены, проверить, в какой домен попадает луч, и перебирать объекты только из данного домена.

В итоге получаем следующие шаги алгоритма выбора нужного объекта (picking algorithm).

Зная координаты оконной точки щелчка мыши s, вычисляем соответствующую точку p в области проекции окна. Вычисляем луч, проходящий через точку p и позицию камеры в начале координат. Трансформируем луч в игровое пространство. Находим объект, который пересекает луч. Это и будет нужный нам объект.

Пройдем этот алгоритм по шагам.

Вычисление луча

px := 0; py := 0; m_pd3dDevice.GetViewport(vp); m_pd3dDevice.GetTransform(D3DTS_PROJECTION, proj); px := ((( 2.0*x) / vp.dwWidth) – 1.0) / proj._11; py := (((-2.0*y) / vp.dwHeight) + 1.0) / proj._22; ray.dvPos.x := 0.0; ray.dvPos.y := 0.0; ray.dvPos.z := 0.0; ray.dvDir.x := px; ray.dvDir.y := py; ray.dvDir.z := 1.0;

Вычисление луча

Для вычисления луча воспользуемся параметрическим уравнением прямой p(t) = p0 + tu, где p0 — точка, откуда начинается луч, а u — вектор, указывающий направление луча. Точка начала луча совпадает с положением камеры в начале координат, поэтому p0 = (0, 0, 0). Если точка p находится на плоскости проекции и луч проходит через нее, то вектор направления u вычисляется так: u = p – p0 = (px, py, 1) – (0, 0, 0) = p. То есть тут идет чистая векторная и матричная математика в пространстве. Приходится приводить некоторые выкладки, без них никак. Вообще работа в трехмерном пространстве несколько сложнее, чем в 2D.

Таким образом можно получить нужный луч, используя координаты x и y точки щелчка мышью в пространстве окна монитора.

Трансформация луча

D3DXVec3TransformCoord(   TD3DXVector3(ray.dvPos),   TD3DXVector3(ray.dvPos),   T ); D3DXVec3TransformNormal(   TD3DXVector3(ray.dvDir),   TD3DXVector3(ray.dvDir),   T );

Трансформация луча

Луч, который мы вычислили, принадлежит пространству обзора. Однако для определения существования пересечения с объектом и объект, и луч должны находиться в одном пространстве координат. Естественно, трансформировать луч в объектное пространство намного проще и быстрее, чем тащить все объекты игрового мира в пространство луча. Чтобы трансформировать луч r(t) = p0 + tu, нужно трансформировать точку p0 и направление луча — вектор u — с помощью матрицы трансформации.

Небольшое пояснение. D3DXVec3TransformCoord — это функция для трансформации точек, а D3DXVec3TransformNormal — векторов.

Проверка пересечения луча с объектом

Чтобы найти объект, который пересекает луч, нужно последовательно перебрать все полигоны, из которых состоит поверхность объекта, и проверить, есть ли точка пересечения какого-либо полигона и луча. Этот метод дает правильный результат, но он требует много ресурсов, особенно если полигонов много. На практике применяют другие методы: построение ограничивающих объемов (Bounding Volume). Самые распространенные ограничивающие объемы — это сфера (Bounding Sphere) и коробка (Bounding Box), которая бывает следующих видов: коробка со сторонами, параллельными осям координат в мировой системе (Axis-Aligned Bounding Box (AABB)), и произвольно ориентированная коробка (Oriented Bounding Box (OBB)). К сожалению, приходится вводить много новых понятий, но без этого практически никак. Ничего, скоро все закончится.

Так вот, методы, которые применяются для picking, практически без изменений могут быть применены и к определению правил взаимодействия объектов в игровом пространстве (Collision Detection).

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

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

Построение ограничивающего объема (сферы) для объекта

p := World.Objects.Mesh.Vertices; D3DX8.D3DXComputeBoundingSphere( p, World.Objects.Mesh.NumVertices, D3DFVF_RESERVED0, BSphere._center, BSphere._radius);

Найдем объект, который пересекает луч. Это и будет нужный нам объект.

Для этого проверим, существует ли точка пересечения сферы и луча. Радиус r и центр сферы c заданы, поэтому используем следующее уравнение: длина вектора p – c должна быть равна радиусу сферы r, если точка p принадлежит сфере.

Чтобы определить, как и где луч p(t) = p0 + tu пересекает сферу, мы подставим уравнение луча в уравнение сферы и найдем решение и параметр t, который определит точки пересечения.

Подставим p(t) = p0 + tu в |p(t) – c| – r = 0, получим |p0 + tu – c| – r = 0 и в итоге

Ax2 + Bx + C = 0,

где

A = u · u, B = 2(u · (p0 – c)) è C = (p0 – c) · (p0 – c) – r2.

Проверка пересечения луча с объектом

// v := ray.dvPos – sphere._center; D3DXVec3Subtract(v, TD3DXVector3(sphere._center), TD3DXVector3(ray.dvPos) ); // вычисляем параметры квадратичного уравнения b := 2.0 * D3DXVec3Dot(TD3DXVector3(ray.dvDir), v); c := D3DXVec3Dot(v, v) – (sphere._radius * sphere._radius); // находим дискриминант discriminant := (b * b) – (4.0 * c); if discriminant < 0.0 then Result := false; discriminant := sqrt(discriminant); // находим два корня уравнения s0 := (-b + discriminant) / 2.0; s1 := (-b – discriminant) / 2.0; // нас интересует только случай, когда оба корня больше или равны 0, тогда наш луч пересекает ограничивающую сферу if (s0 >= 0.0) and (s1 >= 0.0) then Result := true; Result := false;

Если качественно оценивать решения t1 и t0 этого уравнения, то можно выделить несколько общих случаев.

Луч не пересекает сферу; и t0, и t1 — мнимые корни уравнения. Луч находится перед сферой; и t0, и t1 меньше 0. Луч внутри сферы; один из корней больше 0, а другой — меньше. Положительный по знаку корень дает точку пересечения луча и сферы. Луч пересекает сферу; и t0, и t1 больше 0. Луч касается сферы, t0 = t1 и больше 0.

Выбор объекта по щелчку мыши

// пробегаем по всем объектам игрового мира for i:=0 to World.NObj-1 do begin p := World.Objects.Mesh.Vertices; // вычисляем ограничивающую сферу D3DX8.D3DXComputeBoundingSphere( p, World.Objects.Mesh.NumVertices, D3DFVF_RESERVED0, BSphere._center, BSphere._radius); // проводим проверку на пересечение луча и сферы if raySphereIntersectionTest(ray, BSphere) then begin World.IntersectActionExecute(World.Objects.Id); break; end; end;

Для того чтобы привязать picking к щелчку мыши, мы вставим процедуру проверки пересечения в обработчик щелчков мыши TLKI3dForm.MouseProcess.

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

Реализация метода в ЛКИ-Creator

У всех игровых объектов есть свойство IsPickingEnabled, определяющее, можно ли выбирать объект мышью. Например, если у вас в игре есть звезды, планеты, ракеты и вражеские корабли, но стрелять можно только по последним — у всех остальных это свойство надо установить в false, а у кораблей — в true. Рекомендуется всегда отключать picking у «лишних» объектов во избежание неточностей и траты лишних ресурсов.

То же свойство есть и у формы: оно должно быть установлено в true, если вы хотите, чтобы picking в принципе работал.

Далее, чтобы ввести у себя поддержку picking’а, вам осталось сделать только одно: переопределить метод TLKI3dGameWorld.IntersectActionExecute(ObjId : integer). Этот метод отвечает за действия, которые совершает игровой мир в момент щелчка мышью по какому-то объекту. Параметр — идентификационный номер этого объекта.

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

Для того чтобы организовать свой метод picking, необходимо переопределить методы CalcPickingRay, TransformRay, raySphereIntersectionTest, LKI3dPicking для TLKI3dForm и ComputeBoundingSphere для TLKI3dGameObject.

Проверка столкновений объектов

Что такое Collision Detection и зачем оно нужно?

Перед человеком, решившим заняться трехмерной графикой, очень скоро (обычно сразу же после появления на экране первой созданной самостоятельно сцены) встает вопрос, похожий на эти: «А как сделать так, чтобы машинки сталкивались?», или «Как сделать, чтобы человек не проходил сквозь стены и мебель?», или «Как сделать, чтобы мячик скакал по комнате?».

Вот как раз определением факта столкновения объектов (а в идеале еще и определением точек контакта объектов при столкновении) и занимается Collision Detection. Для двумерного игрового мира мы уже умеем это делать. В 3D все похоже, но несколько сложнее. Предположим, у нас есть два объекта — корабль и ракета. Их поверхности в 3D мире состоят из связанных полигонов. Наиболее распространенный класс полигонов — треугольник, но есть и другие. Нужно перебрать все полигоны одного объекта и проверить, существует ли пересечение их с полигонами другого объекта. Хотя на самом деле довольно часто для уменьшения расчетов вместо самих объектов используют так называемые Bounding Volumes, такие как Bounding Sphere, Bounding Box или объект с минимальным уровнем детализации (в виде выпуклого многогранника). Это нам известно из предыдущей главы про picking.

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

Есть и такая возможность: сперва определить столкновение Bounding Volumes, а если оно имело место — то проверить более точно уже по граням, было ли столкновение. Это быстрее, чем сразу проверять грани: тогда детальная обработка понадобится только для тех объектов, которые достаточно близко друг к другу.

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

Что такое Bounding Volume?

Bounding Volume — это ограниченная область в пространстве. Для целей Collision Detection подразумевается, что эта область «твердая», т.е. сквозь нее не могут проходить другие объекты.

Bounding Volume может иметь любую форму (чаще всего выпуклую), но поскольку определение столкновения сложных объектов — процесс достаточно непростой, который к тому же может занимать довольно много времени, часто сложные объекты заменяются на более простые Bounding Volumes — сферы (Bounding Sphere), параллелепипеды (Bounding Box) или выпуклые многогранники (Convex Polyhedron).

При этом получается, что объект как бы окружен непроницаемой оболочкой, которая более или менее повторяет его контуры.

Bounding Sphere	Bounding Sphere — это Bounding Volume в виде сферы. Использование Bounding Sphere — это простой, быстрый и самый грубый (если, конечно, объект сам по себе не является сферой) способ узнать, столкнулись объекты или нет.	Bounding Box	Bounding Box — это Bounding Volume в виде прямоугольного параллелепипеда. Обычно параллелепипед более точно, чем сфера, повторяет форму объектов, к тому же проверка на столкновения с помощью Bounding Box-ов все еще достаточно простая и быстрая, поэтому они наиболее часто используются для проверки на столкновения. Существует два варианта Bounding Box-ов: AABB и OBB.
Axis-Aligned BBox	AABB (Axis-Aligned Bounding Box) — это Bounding Box со сторонами, параллельными осям координат в мировой системе. Как можно видеть, при вращении объекта AABB изменяет свои размеры, но всегда остается ориентированным по осям координат. Проверка на столкновения с помощью AABB выполняется очень просто и быстро.	Oriented BBox	OBB (Oriented Bounding Box) — это произвольно ориентированный Bounding Box. В отличие от AABB, OBB вращается вместе с объектом и не меняет своих размеров. Проверка на столкновения с помощью OBB несколько сложнее и медленнее, чем с помощью AABB, но чаще она более предпочтительна.

Как определить факт столкновения поверхностей объектов?

Мы выберем сферу в качестве ограничивающего объема для объектов нашего игрового мира. Тогда проверка столкновения объектов переходит в проверку пересечения двух сфер.

Проверка столкновения двух ограничивающих объемов (сфер)

function TLKI3dForm.CheckSphereIntersect( XCenter1 : single; YCenter1 : single; ZCenter1 : single; Radius1 : single; XCenter2 : single; YCenter2 : single; ZCenter2 : single; Radius2 : single ) : boolean; var XDiff, YDiff, ZDiff, Distance : single; begin // вычисляем расстояние между центрами сфер XDiff := abs(XCenter2-XCenter1); YDiff := abs(YCenter2-YCenter1); ZDiff := abs(ZCenter2-ZCenter1); Distance := sqrt(XDiff*XDiff+YDiff*YDiff+ZDiff*ZDiff); // если сферы пересекаются… if(Distance <= (Radius1+Radius2)) then Result := true // а нет – так нет else Result := false; end;

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

Это интересно: для оптимизации выполнения проверки на столкновение сфер можно исключить использование функции вычисления квадратного корня sqrt.

Оптимизация

Distance := XDiff*XDiff+YDiff*YDiff+ZDiff*ZDiff; RadiusDistance := (Radius1+Radius2)*(Radius1+Radius2)*3;   // Пересекаются If (Distance <= RadiusDistance) then result := true ; Result := FALSE; // Не пересекаются

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

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