Генерация и построение изображений ландшафта в реальном времени (стр. 6 из 8)
Откуда получим
t = – (Ax1 + By1 + Cz1 + D) / (Aa + Bb + Cc) (2.2.5.5)
Если знаменатель этой дроби равен нулю, значит луч параллелен плоскости, в которой лежит треугольник. Точки пересечения нет.
Для нахождения координат точки пересечения надо подставить найденное значение параметра t в уравнения луча (2). Назовем точку пересечения D. Мы получим координаты xD, yD, zD.
Теперь необходимо определить, попала ли точка D внутрь треугольника. Найдем координаты векторов AB, BC, CA (A, B, C – вершины треугольника) и координаты векторов AD, BD, CD. Затем найдем три векторных произведения:
nA = ABxAD,
nB = BCxBD, (2.2.5.6)
nC = CAxCD.
Эти вектора будут коллинеарные. Если все три вектора сонаправлены, то точка D лежит внутри треугольника. Сонаправленность определяется равенству знаков соответствующих координат всех трех векторов.
Операцию проверки принадлежности точки D треугольнику ABC можно ускорить. Если ортогонально спроецировать треугольник ABC и точку D на одну из плоскостей xOy, yOz или xOz, то попадание проекции точки в проекцию треугольника будет означить попадание самой точки в треугольник (конечно же, если уже известно, что точка D лежит в плоскости, содержащей треугольник ABC). При этом число операций заметно сокращается. Так для поиска координат всех векторов нужно искать по две координаты на каждый вектор, а при поиске векторных произведений нужно искать только одну координату (остальные равны нулю).
Для проверки сонаправленности векторов, полученных при вычислении векторного произведения нужно проверить знаки этой единственной координаты для всех трех векторов. Если все знаки больше нуля, или меньше нуля, то вектора сонаправлены. Равенство нулю одного из векторных произведений соответствует случаю, когда точка D попадает на прямую, содержащую одну из сторон треугольника.
Кроме того, перед вычислениями векторов и векторных произведений можно провести простой габаритный тест. Если проекция точки D лежит правее, левее, выше или ниже каждой из проекций вершин треугольника, то она не может лежать внутри.
Остается добавить, что для проецирования лучше выбирать ту из плоскостей, площадь проекции треугольника на которую больше. При таком условии исключается случай проецирования треугольника в отрезок (при условии, что проверяемый треугольник не вырожден в отрезок). Кроме того, при увеличении площади проекции уменьшается вероятность ошибки. Для определения такой плоскости проецирования достаточно проверить три координаты нормали треугольника. Если z-координата нормали больше (по абсолютному значению) x и y, то проецировать надо на плоскость xOy. Если y больше чем x и z, то проецируем на xOz. В оставшемся случае – на yOz.
bool RayTriangleIntersect(Vector RayPos, Vector RayDir, Vector P1, Vector P2, Vector P3,
outVector ResultPoint, outVector ResultNormal)
{
constdouble EPSILON2 = 0.00001;
Vector v1 = P2 - P1;
Vector v2 = P3 - P1;
Vector pvec = RayDir ^ v2;
double det = v1 * pvec;
ResultPoint = newVector();
ResultNormal = newVector();
if ((det < EPSILON2) && (det > -EPSILON2))
{
returnfalse;
}
double invDet = 1 / det;
Vector tvec = RayPos - P1;
double u = (tvec * pvec) * invDet;
if ((u < 0) || (u > 1))
returnfalse;
else
{
Vector qvec = tvec ^ v1;
double v = (RayDir * qvec) * invDet;
if ((v < 0) || (u+v > 1))
returnfalse;
double t = (v2 * qvec) * invDet;
if (t > 0)
{
ResultPoint = RayPos + RayDir * t;
ResultNormal = v1 ^ v2;
returntrue;
}
else
returnfalse;
}
}
Перемещение и вращение камеры
Представление камеры с помощью векторов:
Матрица вращения вокруг единичного вектора vна угол омега:
Вычисление матрицы камеры:
// вектор бинормали
Vector sideVec(viewMat.p[0], viewMat.p[1], viewMat.p[2]);
//вектор нормали (указывает "верх" камеры)
Vector upVec(viewMat.p[3], viewMat.p[4], viewMat.p[5]);
// векторнаправления
Vector dirVec(viewMat.p[6], viewMat.p[7], viewMat.p[8]);
// построение матрицы поворота (по формуле выше на рисунке)
Matrix Rot(camAng.y, (dirVec ^ upVec).Normalize());
// добавление вращения по оси Y (он указывает верх камеры), которое зависит от смещение мыши по х
Rot.AddRotationY(-camAng.x);
// обновление векторов камеры (домножение на матрицу поворота)
upVec = Rot * upVec;
dirVec = Rot * dirVec;
sideVec = Rot * sideVec;
// обновление матрицы камеры
viewMat.p[0] = sideVec.x; viewMat.p[1] = sideVec.y; viewMat.p[2] = sideVec.z;
viewMat.p[3] = upVec.x; viewMat.p[4] = upVec.y; viewMat.p[5] = upVec.z;
viewMat.p[6] = dirVec.x; viewMat.p[7] = dirVec.y; viewMat.p[8] = dirVec.z;
// обновление матрицы камеры с учетом ее позиции
float m[16] = {
viewMat.p[0], viewMat.p[3], -viewMat.p[6], 0,
viewMat.p[1], viewMat.p[4], -viewMat.p[7], 0,
viewMat.p[2], viewMat.p[5], -viewMat.p[8], 0,
-(viewMat.p[0]*camSrc.x + viewMat.p[1]*camSrc.y + viewMat.p[2]*camSrc.z),
-(viewMat.p[3]*camSrc.x + viewMat.p[4]*camSrc.y + viewMat.p[5]*camSrc.z),
(viewMat.p[6]*camSrc.x + viewMat.p[7]*camSrc.y + viewMat.p[8]*camSrc.z),
1
};
Технологический раздел
Выбор среды разработки и технологии программирования
После подготовки и изучения алгоритмов встал еще ряд вопросов:
-под какую операционную систему реализовывать программный продукт;
-какой язык программирования и среду разработки использовать;
-какую технологию программирования положить в основу проекта.
В качестве операционной системы была выбрана система WidowsXP и более новые Vista и 7. Это обусловлено тем, что WindowsXP — самая распространенная на сегодняшний день ОС. И для нее написано больше всего IDE и программного обеспечения для разработки.
Программный комплекс состоит из двух модулей: редактора и просмотра ландшафта.
Языком программирования для написания программы «Редактор» был выбран язык C#. С помощью C# можно быстро писать программы под Windows или интернет-приложения, благодаря удобному синтаксису, интеллектуальным подсказкам и управляемому коду. Используя управляемый код, не нужно заботится о сборке мусора, об указателях и о некоторых базовых структурах и алгоритмах – все это уже реализовано. Минусом разработки на C# .Net является низкая производительность программ. Но это уже компенсируется современным аппаратным обеспечением. Кроме того, в редакторе нам и не требуется высокая производительность, потому что там рассчитываются только карты (изображение) и нет интерактивных элементов, в отличие от программы просмотра.
Языком программирования для написания программы просмотра ландшафтов был выбран язык С++. Язык С++ сочетает в себе удобство с точки зрения структуры кода (объекты, перегрузка функций, операторов, обработка исключений и др.) и программирование на низком уровне (арифметика указателей, ассемблерные вставки, выравнивание памяти, директивы компилятора). Кроме того, среда разработки VisualStudio 2008 может сильно оптимизировать код, используя раскрытие циклов, встраивание функций, использование суперскалярных команд процессора SSE и др., тем самым увеличив производительность.
Минусы языка С++ тоже имеются: ручная сборка мусора (возможные утечки памяти из-за этого).
В качестве технологического подхода к разработке проекта был выбран объектно-ориентированный подход. Этот выбор обуславливается легкостью и быстротой разработки программы, хотя взамен ее скорости.
Так же встал вопрос о том, как можно использовать аппаратные возможности современных вычислительных систем. Дело в том, что выполнение данной задачи без использования аппаратно-реализованных алгоритмов (например, алгоритм, использующий Z-буфер) не дало бы требуемых результатов. Можно было бы говорить об изображении ландшафта, но не в реальном времени, т.к. даже современные процессоры не в состоянии одновременно обрабатывать и выводить такое количество информации. При том, в настоящее время, когда большинство стандартных алгоритмов реализовано аппаратно, было бы глупо не использовать эти возможности. Это заведомо определяло бы несостоятельность программного продукта в свете современных тенденций. К тому же мне было интереснее сосредоточиться на алгоритме изображения ландшафтов, чем реализовывать стандартные алгоритмы, пройденные в прошлом семестре.
Выбор библиотек, поддерживающих аппаратные возможности современных компьютеров, был не велик: Direct3D или OpenGL. Я выбрал OpenGL, как более распространенную и простую для понимания. OpenGL является открытым графическим стандартом, разработанным и утвержденным несколькими ведущими фирмами, такими как Nvidiacorporation, AMD, Intel, и др. В число ее достоинств входят стабильность, надежность, переносимость, простота использования. Хотя следует отметить, что Direct3D немного выигрывает в скорости и в возможностях.
Структура программы
Программа «Просмотр ландшафта»
Main – модуль, в котором происходит связывание всех компонентов программы. В не содержатся следующие функции:
// загрузка настроек, таких как путь к карте высот, карте освещенности и текстуре ландшафта и неба, из файла
voidLoadSettings(char *FileName)
// В этом событии указываются действии, совершаемые в момент старта программы
boolappPreInit()
// В этом событии указывается последовательность действий при визуализации каждого кадра (несколько раз в секунду)
boolappRender()
// В этом событии указываются действия, совершаемые при закрытии программы (освобождение ресурсов)
voidappShutdown()
// Обработчик нажатий клавиш
boolProcessKey(HWNDhWnd,WPARAMwParam)
Terrain – Описывает непосредственно геометрию ландшафта (вершины, индексы, нормали), текстуры ландшафта, неба, воды.
Также этот класс отвечает за визуализацию всех этих объектов.
DynamicCamera – Реализация камеры, ее передвижения, вращения, а также связь с ландшафтом (передвижение по нему).
Font – модуль для инициализации и вывода текста на экран
Render– модуль для реализации визуализации в 3-мерном и 2-мерном режимах
Image – модуль для загрузки и обработки изображений
Texture – модуль для загрузки изображений и инициализаций структур
Vector – модуль для работы с векторами (сложение, вычитание, скалярное произведение, векторное произведение)
Matrix – модуль для работы с матрицами (умножение, транспонирование, нахождение обратной). Матрицы используются для реализации композиции трансформаций (перемещение, вращение, поворот), для реализации геометрических алгоритмов