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

u = s + td + ag при a = 0 значение u задает сам отрезок. Далее, если a = 0, при t = 0 и t = 1 получаются концевые точки отрезка. Также известно, что hj = u *[VT] = pj + qjt+ wja и заметим, что при t = 0 pj является скалярным произведением концевой точки отрезка и j-й плоскости, ограничивающей тело. Аналогично pj + qj является скалярным произведением другой концевой точки отрезка и j-й плоскости, ограничивающей тело. Наконец, напомним, что j-я плоскость, ограничивающая тело, видима, если wj = 0. Поэтому, если wj  О и pj  0, то один конец отрезка лежит или на видимой плоскости или между видимой плоскостью и точкой наблюдения. Если же pj + qj  0, то другой конец отрезка также лежит либо на видимой плоскости, либо между этой плоскостью и точкой наблюдения. Следовательно, отрезок полностью видим, если для любого j wj  О и pj  0 и pj + qj  0. Эти условия гарантируют, что неравенства hj  0 не могут быть выполнены ни при каких a  0 и 0  t  1. Поэтому никакая часть отрезка не может быть невидимой, т. е. Отрезок полностью видим. Ниже приводится эффективная реализация алгоритма Робертса. В Этом алгоритме можно выделить три основных этапа. На первом этапе каждое тело анализируется индивидуально с целью удаления нелицевых плоскостей. На втором этапе проверяется экранирование оставшихся в каждом теле ребер всеми другими телами с целью обнаружения их невидимых отрезков. На третьем этапе вычисляются отрезки, которые образуют новые ребра при протыкании телами друг друга. В данном алгоритме предполагается, что тела состоят из плоских полигональных граней, которые в свою очередь состоят из рёбер, а ребра – из отдельных вершин. Все вершины, ребра и грани связа­ны с конкретным телом. Алгоритм Робертса: 1. Удаление нелицевых плоскостей: Для каждого тела в сцене: 1.1. Сформировать многоугольники граней и ребра, исходя из списка вершин тела. 1.2. Вычислить уравнение плоскости для каждой полигональной грани тела. 1.3. Проверить знак уравнения плоскости: 1.4. Взять любую точку внутри тела, например усреднив координаты его вершин. 1.5. Вычислить скалярное произведение уравнения плоскости и точки внутри тела. 1.6. Если это скалярное произведение < О, то изменить знак уравнения этой плоскости. 1.7. Сформировать матрицу тела. 1.8. Умножить ее слева на матрицу, обратную матрице видового преобразования, включающего перспективу. 1.9. Вычислить и запомнить габариты прямоугольной объемлющей оболочки преобразованного объема: xmin, xmax, ymin, ymax. 1.10. Определить нелицевые плоскости: 1.10.1. Вычислить скалярное произведение пробной точки, лежащей в бесконечности, на преобразованную матрицу тела. 1.10.2. Если это скалярное произведение < О, то плоскость невидима. 1.10.3. Удалить весь многоугольник, лежащий в этой плоскости. Это избавляет от необходимости отдельно рассматривать, невидимые линии, образуемые пересечением пар невидимых плоскостей. 2. Удаление из каждого тела тех ребер, которые экранируются всеми остальными телами в сцене: 2.1. Если задано только одно тело, то алгоритм завершается. 2.2. Сформировать приоритетный список этих тел: 2.2.1. Провести сортировку по z. Сортировка производится по максимальным значениям координаты z вершин преобразованных тел. Первым в упорядоченном списке и обладающим наиболь­шим приоритетом будет то тело, у которого минимальное среди максимальных значений z. В используемой правой системе координат это тело будет самым удаленным от точки наблюдения, расположенной в бесконечности на оси z. 2.3. Для каждого тела из приоритетного списка: 2.3.1. Проверить экранирование всех лицевых ребер всеми другими телами сцены. Тело, ребра которого проверяются, называется пробным объектом, а тело, относительно которого в настоящий момент производится проверка, называется пробным телом. Естественно, что нужно проверять экранирование пробного объекта только теми пробными телами, у которых ниже приоритеты. 3. Провести проверки экранирования для прямоугольных объ­емлющих оболочек пробного объекта и пробного тела: 3.1. Если xmin (пробное тело) > xmax (пробный объект) или xmax (пробное тело) < xmin (пробный объект) или ymin (пробное тело) > ymax (пробный объект) или ymax (пробное тело) < ymin (пробный объект), то пробное тело не может экранировать ни одного ребра пробного объекта. Перейти к следующему пробному телу. В противном случае: Провести предварительные проверки протыкания, чтобы увидеть, не протыкается ли пробное тело пробным объек­том и существует ли возможность частичного экранирова­ния первого последним. 3.2. Сравнить максимальное значение z у пробного объекта с минимальным значением z у пробного тела. 3.2.1. Если zmax (пробный объект) < zmin (пробное тело), то протыкание невозможно. Перейти к следующему те­лу. В противном случае: 3.3. Проверить видимое протыкание. 3.3.1. Если zmin (пробный объект) > zmax (пробное тело), то пробный объект может проткнуть переднюю грань пробного тела. 3.3.2. Установить флаг видимого протыкания для последу­ющего использования. Занести проткнутое тело в спи­сок протыканий. 3.3.3. Если xmax (пробное тело) > xmin (пробный объект) или xmin (пробное тело) < xmax (пробный объект), то пробный объект может проткнуть бок пробного тела. 3.3.4. Установить флаг видимого протыкания для последу­ющего использования. Завести тело в список проты­каний. 3.3.5. Если ymax (пробное тело) > ymin (пробный объект) или ymin (пробное тело) < ymax (пробный объект), то пробный объект может проткнуть верх или виз пробного тела. 3.3.6. Установить флаг видимого протыкания для последующего использования. Занести проткнутое тело в список протыканий. 3.3.7. Если список протыканий пуст, то устанавливать флаг протыкания не надо. 3.4. Провести проверки экранирования ребер: 3.4.1. Вычислить s и d для ребра. 3.4.2. Вычислить p, q, w для каждой плоскости, несущей грань пробного тела. 3.4.3. Проверка полной видимости. Если ребро полностью, ви­димо, то перейти к следующему ребру. 3.4.4. Сформировать уравнения hj = 0 и решить их, объединяя попарно и включив в систему уравнения границ t = 0 и t = 1. Если установлен флаг видимого протыкания, то в систему надо включить и уравнение границы a = 0. За­помнить точки протыкания. В противном случае грани­цу a = 0 не учитывать. 3.4.5. Для каждой пары (t, a), являющейся решением проверить выполнение условий 0  t  1, a  0 и hj > 0 для всех других плоскостей. Если эти условия выпол­нены, то найти tmaxmin и tminmax. 3.4.6. Вычислить видимые участки отрезков и сохранить их для последующей проверки экранирования телами с бо­лее низкими приоритетами. 4. Определить видимые отрезки, связывающие точки протыка­ния: 4.1. Если флаг видимого протыкания не установлен, перейти к процедуре визуализации. 4.2. Если точек протыкания не обнаружено, перейти к процеду­ре визуализации. 4.3. Сформировать все возможные ребра, соединяющие точ­ки протыкания, для пар тел, связанных отношением протыкания. 4.4. Проверить экранирование всех соединяющих ребер обои­ми телами, связанными отношением протыкания. 4.5. Проверить экранирование оставшихся соединяющих ре­бер всеми прочими телами сцены. Запомнить видимые отрезки. 5. Визуализировать оставшиеся видимые отрезки ребер. Алгоритм художника Пусть имеется некий набор граней (т.е. сцена), который требуется нарисовать. Отсортируем грани по удаленности от камеры и отрисуем все грани, начиная с самых удаленных. Довольно распространенная характеристика удаленности для грани ABC - это среднее значение z, mid_z = (A.z+B.z+C.z)/3. Вот и весь алгоритм. Просто, и обычно достаточно быстро. Существует, правда, несколько проблем. Во-первых, при некотором расположении граней этот алгоритм вообще не может дать правильного результата - в каком порядке грани не рисуй, получится неправильно. Вот стандартный пример (Рис. 18.). Рис. 18. Пример расположения граней Во-вторых, при некотором расположении граней и использовании среднего значения z как характеристики удаленности алгоритм [7] тоже дает неправильный результат. Пример чуть ниже. В этом случае горизонтальную грань надо отрисовывать второй, но по среднему значению z она лежит дальше и таким образом получается, что ее надо отрисовывать первой. Возможные пути решения этой проблемы - какие-то изменения характеристики удаленности, либо моделирование, не вызывающее таких ситуаций. Рис. 19. Пример моделирования И наконец, при использовании этого алгоритма отрисовываются вообще все грани сцены, и при большом количестве загораживающих друг друга граней мы будем тратить большую часть времени на отрисовку невидимых в конечном итоге частей. То есть совершенно впустую. В таком случае целесообразно использовать какие-то другие методы (например BSP и PVS, порталы, и т.д). Алгоритм использующий Z-буфер Заведем буфер (собственно z-буфер [3,4,5,6]) размером с экран, и забьем его каким-то большим числом, настолько большим, что координаты z для точек сцены заведомо меньше. Например, если z - fixedpoint 16:16, то можно использовать максимально возможное значение, то есть 0x7FFFFFFF. Для каждой рисуемой точки считаем значение z; если оно больше, чем значение в z-буфере (точка закрыта какой-то другой точкой), или меньше, чем -dist (точка находится за камерой), то переходим к следующей точке. Если меньше, то рисуем точку на экране (или в видеобуфере), а в z-буфер записываем текущее значение z. Вот кусок кода для лучшего понимания: // ... if (z > -dist && z < zbuffer[screenX][screenY]) { screen[screenX][screenY] = color; zbuffer[screenX][screenY] = z; } // ... Имеет смысл считать значения не z, а z1 = 1/(z+dist), так как эта величина изменяется по грани линейно, и линейная интерполяция дает точные результаты. Тогда условия чуть изменяются - точка загорожена другой, если значение z1 *меньше* значения в z-буфере; и точка находится за камерой, если z1 < 0. Буфер инициализируем нулями. Тогда не нежна проверка на положительность z1 - точка попадает в z-буфер и на экран, только если z1 больше текущего значения, и поэтому точки, для которых z1 < 0 в буфер и без проверки никогда не попадут. Код тоже чуть изменится: // ... if (z1 > zbuffer[screenX][screenY]) { screen[screenX][screenY] = color; zbuffer[screenX][screenY] = z1; } // ... Вот и все. Осталось упомянуть, что этот метод иногда называют w-буфером, подчеркивая разницу между хранением z и какой-то обратной величины, w. Это самый простой метод удаления невидимых частей, причем всегда дающий полностью правильные результаты. Единственная проблема - скорость, z-буфер, как самый простой, является и самым медленным методом. Z-отсечение Необходимость в этой процедуре возникает, когда, в конце концов, оказывается, что надо нарисовать грань, у которой часть вершин лежит перед камерой, а часть - за камерой. То есть грань, пересекающуюся с экраном. Сама по себе она правильно не нарисуется. Поскольку камера видит только то, что перед ней находится, все те точки, для которых z < -dist, рисовать не надо. То есть, каждую грань надо обрезать плоскостью z = -dist. Принципиально различных случаев расположения грани относительно этой плоскости может быть всего четыре; когда перед камерой находятся соответственно 0, 1, 2 или 3 вершины. Первый и последний случаи тривиальны - если перед камерой находится 0 вершин, то грань просто не видна и рисовать ее не надо; если 3 вершины, то грань видна целиком и полностью и ее достаточно просто взять и нарисовать. Рассмотрим оставшиеся два случая. Случай первый, когда перед камерой находится только одна вершина: Рис 20. Случай с одной вершинной В этом случае перед камерой находится только треугольник CDE. Его и надо будет нарисовать вместо грани. Случай второй, когда перед камерой находятся две вершины: Рис 21. Случай с двумя вершинами Здесь уже надо будет нарисовать трапецию DABE; она разбивается на два треугольника, DAB и DBE. Их и рисуем вместо грани. Координаты и текстурные координаты для точек D, E считаются совсем просто: с одной стороны, D лежит на AC, с другой стороны, D.z = -dist. Для точки D как лежащей на AC любая величина t (вместо t подставляем x/y/u/v) считается следующим образом: D.t = A.t + (C.t - A.t) * (D.z - A.z) / (C.z - A.z) = A.t + (C.t - A.t) * (-dist - A.z) / (C.z - A.z) Все это сводится в следующий алгоритм отрисовки грани: выясняем, сколько вершин лежит перед камерой; то есть - какой из случаев мы имеем; ставим точки A, B, C в соответствие с вершинами (то есть, если вершина v0 находится перед камерой, а вершины v1, v2 - нет, то имеем первый случай, где C = v0, A = v1, B = v2); считаем, если нужно, координаты D, E; рисуем (или добавляем в список отрисовки) полученные треугольники. Осталось только добавить, что обрезание на самом деле надо проводить не плокостью z = -dist, а плоскостью z = -dist + smallvalue, smallvalue > 0, чтобы избежать проблем при проецировании. Алгоритм определения видимых поверхностей путём трассировки лучей       Это один из самых первых алгоритмов [7] создания игр, поэтому рассмотрим как работает алгоритм на примере устройства классической игры Wolfenstein 3D фирмы IDSoftware.        Наверное, одно из самых ключевых понятий Wolfenstein 3D - игровое поле. Оно представляет собой лабиринт. Конечно в общем случае для игр виртуальной реальности нет ограничений на высоту стен, на угол, под которым эти стены расположены, на наличие потолка и на замкнутость лабиринта. В нашем же случае смело можно отображать все игровое поле на клетчатой бумаге.       Рис 22. Игровое поле       Кроме того, в игре приняты следующие допущения. Стены могут быть только вертикальные и горизонтальные. Расстояние между потолком и полом и высота "глаз" над уровнем пола везде одинаковы. Еще немного упростим модель и будем рассматривать матрицу, элементами которой являются числа, полностью определяющие игровое поле, положение игрока и противников, а также все предметы. Теперь рассмотрим способы отображения игрового поля. Для этого нам понадобиться алгоритм трассировки лучей (ray casting), а точнее его двумерная интерпретация. Вот зачем он нужен. Рано или поздно при отрисовки некоторого числа поверхностей возникает вопрос о том, а действительно ли необходимо выводить на экран все из них. Оказывается, что нет. Некоторые стены можно выводить не до конца, т.к. они перекрываются другими, некоторые вообще не видны. Как же проверить, видно стену или нет. Для этого есть множество способов, но сначала определим одно важное понятие. Под камерой будем понимать объект, который имеет вектор направления (ракурс, угол зрения итд) и размерами этого объекта можно пренебречь. Можно также считать, что вместо камеры сидит наблюдатель и смотрит в сторону, заданную вектором направления. Посмотрим и мы на то, что видит этот наблюдатель. Заметим, что на экран как раз это и нужно выводить. Есть метод вывода на экран путем построчного сканирования. (вывод по строкам) В данной конкретной ситуации удобнее будет вывод на экран по столбцам. Пока что попробуем свести задачу определения ближайщих граней а пространстве, к аналогичной задаче на плоскости. Посмотрим на игровое поле сверху. Получилась задача на плоскости 0XY. (см. рис. 23.)       Рис 23. Задача на плоскости       Двумерная интерпретация алгоритма трассировки лучей заключается в следующем. Из точки, где находиться наблюдатель, выпускается пучок лучей. Далее для каждого луча находиться его ближайшее (первое) пересечение с другими объектами (в нашем случае со стенами). Но это еще не все. Просто алгоритм, где проверяются все стены на пересечение с лучом малоэффективен. Приятнее воспользоваться тем, что стены являются сегментами линий сетки. Для этого пересекаемые лучом клетки отслеживаются в порядке распространения от начала до того, пока не будет встречена непустая клетка. (см. рис. 24.)       Рис 24. Пример прохождения луча       Реализуем все это следующим образом. Проверим на пересечение с лучом сначала вертикальные, а потом горизонтальные стены. Далее выберем ближайшее пересечение.       Пусть наблюдатель находиться в точке с координатами (x*,y*), а угол между лучом и положительным направлением оси 0X равен alpha. Будем считать, что клетка, содержащая игрока, имеет индекс (i*,j*), а шаг сетки равен h. Найдем точки пересечения луча с вертикальными линиями x=ih. Если направляющий вектор луча имеет положительную х-составляющую (cos(alpha)>0 => alpha от -pi/2 до pi/2), то ближайшая точка будет иметь координаты x1=(i*+1)h, y1=y*+(h-(x*-i*h))tan(alpha)=y*+(x1-x*)tan(alpha). При этом эта точка лежит на границе клетки (i*+1,[y1/h]). Если эта клетка занята стеной, то пересечение сразу получается в точке (x1,y1). При этом расстояние до точки пересечения будет равно d=(x1-x*)/cos(alpha). Если же эта клетка пуста, то проверяем следующие точки: Xi+1=Xi+h, Yi+1=Yi+htan(alpha). Здесь i-ая точка соответствует клетке (i*+i,[Yi/h]). Проверка происходит до тех пор, пока мы либо не наткнемся на занятую клетку, либо не выйдем за пределы лабиринта.       Если клетка, соответствующая точке пересечения (Xi,Yi), занята, то расстояние до этой точки будет d=(Xi-x*)/cos(alpha).      Теперь рассмотрим случай, когда cos(alpha)<0 (alpha то pi/2 до 3pi/2). Ближайшая точка пересечения луча с линией вида x=ih описывается формулами: x1=i*h, y1=y*-(x*-x1)tan(alpha)=y*+(x1-x*)tan(alpha). Первой проверяется клетка (i*-1,[y1/h]). Если она занята, то пересечение найдено и расстояние до точки пересечения равно d=(x1-x*)/cos(alpha). Иначе необходимо проверить остальные точки пересечения: Xi+1=Xi-h, Yi+1=Yi-htan(alpha). Для точки (Xi,Yi) следует проверить клетку (i*-i,[Yi/h]). Если она занята, то расстояние до точки пересечения составит d=(Xi-x*)/cos(alpha).       получаем следующий код. float checkVWalls ( float angle ) { int xTile = (int) locX; // cell indices int yTile = (int) locY; float xIntercept; // intercept point float yIntercept; float xStep; // intercept steps float yStep; int dxTile; if ( fabs ( cos ( angle ) ) < 1e-7 ) return 10000.0; if ( angle >= ANGLE_270 || angle <= ANGLE_90 ) { xTile ++; xStep = 1; yStep = tan ( angle ); xIntercept = xTile; dxTile = 1; } else { xTile --; xStep = -1; yStep = -tan ( angle ); xIntercept = xTile + 1; dxTile = -1; } // find interception point yIntercept = locY + (xIntercept - locX) * tan ( angle ); for ( ; ; ) { yTile = yIntercept; if ( xTile < 0 || xTile > 52 || yTile < 0 || yTile > 9 ) return 10000.0; if ( worldMap [yTile][xTile] != ' ' ) return ( xIntercept - locX ) / cos ( angle ); xIntercept += xStep; yIntercept += yStep; xTile += dxTile; } }       Точно так же находится ближайшая точка пересечения луча с горизонтальными линиями сетки y=ih.       При alpha от 0 до pi: x1=x*+(y1-y*)ctg(alpha), y1=(j*+1)h, Xi+1=Xi+hctg(alpha), Yi+1=Yi+h. При alpha от pi до 2pi x1=x*+(y1-y*)ctg(alpha), y1=(j*-1)h, Xi+1=Xi-hctg(alpha), Yi+1=Yi-h.       Код для горизонтальной проверки выглядит так.       float checkHWalls ( float angle ) { int xTile = (int) locX; int yTile = (int) locY; float xIntercept; float yIntercept; float xStep; float yStep; int dyTile; if ( fabs ( sin ( angle ) ) < 1e-7 ) return 10000.0; if ( angle <= ANGLE_180 ) { yTile ++; xStep = 1 / tan ( angle ); yStep = 1; yIntercept = yTile; dyTile = 1; } else { yTile --; yStep = -1; xStep = -1 / tan ( angle ); yIntercept = yTile + 1; dyTile = -1; } xIntercept = locX + (yIntercept - locY) / tan ( angle ); for ( ; ; ) { xTile = xIntercept; if ( xTile < 0 || xTile > 52 || yTile < 0 || yTile > 9 ) return 10000.0; if ( worldMap [yTile][xTile] != ' ' ) return ( yIntercept - locY ) / sin ( angle ); xIntercept += xStep; yIntercept += yStep; yTile += dyTile; } }       После того, как найдены ближайшие точки пересечения луча как с вертикальными, так и с горизонтальными стенами, среди них выбирается наименее удаленная от игрока.       Теперь нужно понять, как по найденному расстоянию d строиться столбец пикселей. Для этого нам нужно ввести расстояние f до картинной плоскости. (см. рис. 25.) Рис 25. Схема получения изображения на плоскости       Найдем величины отрезков AB, BC и CD через f и d. Условимся, что камера находиться посередине между потолком и полом. Т.е. AB=CD. Тогда BC=(SCREEN_HEIGHT*f)/d, AB=(SCREEN_HEIGHT-BC)/2.       Реализация этого в коде ниже. void drawView () { float phi; float distance; totalFrames++; for ( int col = 0; col < 320; col++ ) { phi = angle + rayAngle [col]; if ( phi < 0 ) phi += 2 * M_PI; else if ( phi >= 2 * M_PI ) phi -= 2 * M_PI; float d1 = checkVWalls ( phi ); float d2 = checkHWalls ( phi ); distance = d1; if ( d2 < distance ) distance = d2; distance *= cos ( phi - angle ); // adjustment for fish-eye drawSpan ( distance, WALL_COLOR, col ); } }       Для задания углов лучей здесь используется массив rayAngle - для каждого луча указан угол между направлением луча и направлением взгляда игрока. Наиболее простым способом описания этого массива является задание углов с постоянным шагом, но, т.к. этот способ вызывает некоторые искажения, применим следующий алгоритм:       reyAngle[i]=arctg(tg(VIEW_ANGLE/2)*(1+i/(SCREEN_WIDTH-1)))       Полный текст программы приведен в приложении 1.       Алгоритм секторов и порталов Для описания алгоритма введем некоторые понятия.      Сектор - выпуклый объемный многоугольник, т.е. прямая проведенная через любые две диаметрально противоположные точки пересекает только граничные полигоны. Р ис. 26. Сектор      Портал - полигон, который указывает на другой сектор.   Портал является тем же полигоном, но не содержит текстуру и карт освещения, он используется как указатель на другой сектор.      Следует заметить, что если имеется сектора S1 и S2 и портал из сектора S1 указывает на сектор S2, то портал в секторе S2 должен указывать на S1.      Портал имеет свою матрицу преобразования, что позволяет добиться эффекта отражения. Использование портальной технологии позволяет динамически изменять нелинейную сцену (мир).      Например: в сцене состоящей из трех секторов S1, S2 и S3, портал в S1 указывает на S2, а портал в S2 указывает не на S1, а на S3, т.е. находясь в S1 можно видеть S2, а из сектора S2 будет виден сектор S3.      Порталы помогают решить проблему сортировки полигонов внутри секторов. Внутри сектора полигоны всегда видимы и их можно отрисовывать в любом порядке за исключением тех полигонов, которые находятся позади камеры обзора. На рис.27. порталы обозначены «А», «В» и выделены жирной линией. Рис. 27. Сектора и порталы Схема работы алгоритма:     1. Находим сектор в котором находится текущая камера.     2. Преобразование сектора:         - поворачиваем сектор относительно текущей камеры;         - отбрасываем невидимые полигоны;         - производим трехмерное отсечение по пирамиде всех полигонов сектора;         - берем первый видимый полигон;     3. Для текущего полигона:         - если полигон является порталом, то рекурсивно вызываем шаг 2;         - но с сектором, на который указывает портал;         - берем из cache нужную текстуру;         - отрисовываем данный полигон с коррекцией перспективы;         - если следующий полигон существует, то текущий приравниваем;         - следующему, переходим к шагу 3.     4. Выбираем первый объект.     5. Преобразование текущего объекта:         - поворачиваем объект относительно текущей камеры;         - отбрасываем невидимые полигоны;         - отсекаем по пирамиде все полигоны;         - рисуем все полигоны используя алгоритм "художника";         - переходим к следующему непустому объекту. Достоинства: очень быстрый алгоритм пригоден для создания динамических сцен легко представлять сцену алгоритм не содержит перерисовок легко реализовать спецэффекты (динамическое освещение, система соударений, зеркальные поверхности и т.д.) Недостатки: не является общим алгоритмом Структура представления информации Определение сцены (мира) Сцена (мир) представлена набором секторов с содержащимися в них предметах и соединенных между собой порталами (Рис. 28.). Рис. 28. Сцена Все сектора и объекты составлены из трехмерных полигонов. Эти полигоны должны быть выпуклыми. Вершины каждого полигона должны быть ориентированны против часовой стрелки - данный факт используется для определения видимости полигона (полигон имеет только одну видимую сторону). Каждый полигон растрируется с текстурой. Вид текстуры на полигоне задается следующими параметрами: угол поворота текстуры, коэффициенты масштабирования по осям t и s и смещение относительно каждой из осей. Вся сцена представлена непрерывным динамически выделяемым массивом из структур описания полигонов (все полигоны одного сектора следуют последовательно друг за другом): struct Map_Object { int chrome; применяется или нет эффект хрома int n_tex_chrome; номер текстуры для хрома int f_blend_chrome; прозрачность float color_chrome[4]; RGBA значения int Visible; видим или нет полигон int ntexture; номер текстуры для полигона float x1,x2,x3; координаты вершин полигона float y1,y2,y3; float z1,z2,z3; float t_x1,t_x2,t_x3; координаты тукстуры (x-t,y-s) float t_y1,t_y2,t_y3; float nx1,nx2,nx3; нормали для вершин float ny1,ny2,ny3; float nz1,nz2,nz3; };      Разбиение сцены на сектора хранится в динамически выделяемом массиве структур: struct Portal{ … int polygon_begin; номер 1-го полигона int polygon_end; номер последнего полигона int nsv; кол-во порталов float *x1, *x2, *x3, *x4; описание портала float *y1, *y2, *y3, *y4; float *z1, *z2, *z3, *z4; int *type; тип портала … }; Структура хранения обектов сцены В каждом секторе могут находиться различные обекты, которые могут содержать в себе анимацию. Обекты загружаются в программу из файлов формата 3DS, созданных в 3D StudioMax. Для хранения этих обектов была создана следующая структура: struct G_Object { … kfmesh3ds *obj; ключи анимации int length_anim; длина анимации float cur_key; текущий ключ int num_obj; кол-во подобъектов G_Object *Object; подобъекты IA3dSource *a3dsrc ; хранится звук (A3D) char sound_name[250]; имя звука float sound_length; дальность звучания int f_blend; прозрачность есть/нет int type; тип объекта int nVertex; кол-во вершин float *Vertex; вершины float *VColor; цвет вершин int Visible; видим или нет объект int nportal; принадлежность сектору int texture; номер текстуры … }; BSP – деревья Метод BSP - деревьев (Binary Space Partitioning Tree) - метод двоичного разбиения пространства. Для начала, нам надо построить двоичное дерево. В качестве главного узла в двоичном дереве берется произвольный полигон. Плоскость, в которой он лежит, делит пространство на два полупространства, в каждом полупространстве берутся следующие произвольные полигоны - это будут следующие узлы дерева; если часть вершин полигона после разбивки лежит в одном полупространстве, а часть - в другом, то он разбивается на 2 полигона. Дерево строится, пока остаются незадействованные в сортировке полигоны. Рис. 29. Построение BSP-дерева Разберем рис. 29. (на рисунке представлен 2D-случай для наглядности). За главный узел примем отрезок EF. прямая, которая проходит через EF разбивает отрезок CD на DD` и CD`. Дальше - смотрим: в одной полуплоскости лежит отрезок DD`, в другой - два отрезка: CD` и AB. В полуплоскости, где находится отрезок DD` больше нет других отрезков - ветвь дерева прекращается. В другой же полуплоскости лежат 2 отрезка - AB и CD`. За следующий узел принимаем CD`. В одной из полуплоскостей, образованных прямой, проходящей через отрезок CD` не лежит ни одного отрезка, в другой - отрезок AB; достраиваем дерево. Главный принцип BSP - это то, что ни один полигон, лежащий в полупространстве, где нет наблюдателя, не может загородить собой полигон, лежащий в полупространстве, где находится наблюдатель. Корректный последовательный вывод полигонов обеспечивается обходом ветвей дерева с учетом этого факта. Пример кода : void draw_bsp(bspn *b) { if (!back_face(f[b->face])) { if (b->right != NULL) draw_bsp(b->right); make_poly(f[b->face]); if (b->left != NULL) draw_bsp(b->left); } else { if (b->left != NULL) draw_bsp(b->left); make_poly(f[b->face]); if (b->right != NULL) draw_bsp(b->right); } } 3.9. Shadow Volumes или стенсельные тени Сейчас уже практически всем понятно, что без теней - никуда, а тем более динамических. Особенно в таких, которые подразумевают эффект присутствия. Для динамических теней наиболее популярны два алгоритма - Shadow Volumes [3,4,8,9] или стенсельные тени, и Shadow Mapping. У каждого из них - свои достоинства и недостатки. 3.9.1. Основная идея Shadow Volumes. Стенсил. Объект, отбрасывающий тень, называется Shadow Caster, объект, на которого отбрасывается тень - Shadow Receiver. В идеале вся сцена является и Shadow Caster'ом, и Shadow Receiver'ом, но часто можно указать Shadow Caster'ы и Shadow Receiver'ы более детально, и получить на этом неслабую экономию ресурсов. Например, если у нас есть более-менее плоский ландшафт с объектами на нем, то логично не делать ландшафт Shadow Caster'ом. При самозатенении Shadow Caster является еще и Shadow Receiver'ом своей же тени. Shadow Volumes не зря так называются. Вся идея в том чтобы построить такой объект, что бы все что внутрь него попадает считалось затененным. Отсюда и Shadow Volume - теневой объем. То есть для каждого объекта в сцене мы строим Shadow Volume - особый невидимый объект, такой чтобы все что попадало в тень от этого объекта находилось внутри него. Понятно, что этот волюм - это сам Shadow Caster, вытянутый по направлению от источника. Рис. 30. Рис. 31. После этого возникает два вопроса - как строить Shadow Volume для данного объекта, и как проверять, какая часть сцены находится внутри этого объекта. Надо сказать, что эти вопросы связаны друг с другом, то есть от того как строить Shadow Volume будет зависеть то, как мы будем находить часть сцены внутри него, и наоборот. В самом простом случае ответ на первый вопрос звучит так - Shadow Volume это силуэт объекта с точки зрения источника света, вытянутый до бесконечности. Рис. 32. То есть метод построения такой - находим все силуэтные ребра объекта (с позиции источника света), и каждое такое ребро превращаем в квад из двух треугольников, вытянутый по направлению света. Понятно, что до бесконечности мы вытянуть его не можем, поэтому вытягиваем на какую-то величину, заведомо превышающую размеры сцены. Сейчас, как находить часть сцены внутри объема. Именно здесь на сцену вступает стенсил-буфер (в дальнейшем - просто стенсил). Сначала вкратце о том, что такое стенсил-буфер. Это дополнительный буфер размера экрана, то есть каждому пикселю экрана соответствует свое значение в стенсил-буфере. Каждый раз когда точка рисуется на экран, то кроме тестов вроде сравнения с глубиной в Z-буфере она проходит еще и стенсил тест. То есть, например, можно сказать - точка рисуется, только если в стенсиле значение больше единицы. С другой стороны, можно сказать, как изменить значение стенсила после того как пиксель в этом месте отрисуется. Это, например, полезно для разного рода отсечений. Характерный пример - портальное отсечение. Вот есть у нас портал в виде какого-то набора треугольников, и нам не хочется чтобы та часть сцены что за порталом вылезала за его границы. Если портал произвольной формы, то гарантировать это при простой отрисовке сложновато. Но если есть стенсил, то все становится просто - сначала рисуем портал в стенсил определенным значением (запись на экран или в Z-буфер отключаем), а потом при отрисовке сцены за порталом включаем на это значение стенсил тест. На запись в стенсил есть следующие команды - что делать со стенсилом и при каких условиях. Возможности изменения, которые нам понадобятся такие - "увеличить значение в стенсиле", "уменьшить значение в стенсиле", "записать в стенсил данное значение". Условия на запись - "точка прошла Z-Test", "точка не прошла Z-Test", "точка прошла стенсил тест", "точка не прошла стенсил тест". То есть можно установить, например, что при пройденном Z-Test'e значение в стенсиле увеличивается, а при пройденном стенсил тесте, уменьшается и так далее, в любых комбинациях. Конечно же, есть свои тонкости, и набор возможных изменений стенсила зависит от конкретной карты. Итак, как же наличие стенсил-буфера помогает узнать какая часть сцены находится внутри волюма? Изначально мы рисуем всю сцену без теней. Основная задача - чтобы Z-буфер был правильно заполнен. Теперь мы два раза рисуем волюм (оба раза запись в Frame buffer отключена, то есть на экран мы ничего не рисуем). Первый раз рисуем те грани, которые повернуты лицевой стороной к камере (front-cull), и при этом увеличиваем стенсил там, где пройден Z-test. В результате в стенсиле мы получим значения больше нуля там, где передняя часть волюма находится к нам ближе чем к сцене: Рис. 33. За второй проход рисуем грани, которые повернуты лицевой стороной от камеры (back-cull), и уменьшаем значения стенсила там, где пройден Z-test. На картинке - те точки, где мы уменьшим значения стенсила: Рис. 34. В результате после обоих проходов мы получим ненулевые значения там где передняя часть волюма прошла тест, а задняя - не прошла. На самом деле, это и есть та часть сцены на экране, которая находится внутри волюма, а значит - в тени от того объекта, от которого строили волюм. Те области, которые мы не вычеркнули вторым проходом и есть то что лежит в тени. Рис. 35. Естественно, во время отрисовки никакие такие цвета не рисуются, все эти значения - только в стенсиле. Еще одна важная деталь - во время отрисовки волюмы мы выключаем запись в Z-буфер. То есть сам Z-буфер по-прежнему работает, но если точка волюма прошла Z-test, то ее координата не записывается в Z-буфер. После того как мы получили в стенсиле ненулевые значения только там где есть тень, то наложить эту тень уже несложно. Самый простой метод - нарисовать черный полупрозрачный квад во весь экран и выводить его с блендингом(прозрачностью) там где стенсил тест пройден. Тогда там где есть тень освещение станет меньше. Рис. 36. Для более сложных объектов все эти картинки становятся гораздо запутанней из-за того что по одному месту может проходить больше граней волюмов, но прицип остается тем же. 3.9.2. Построение волюма. Волюм - это все силуэтные ребра объекта вытянутые в квад по направлению от источника света, вопрос - как эти ребра находить. Ребра, как известно, находятся на стыке треугольников, и в этой реализации предполагается, что у любого ребра всегда можно выделить ровно 2 треугольника, между которыми оно находится. Понятное дело, это налагает некоторые ограничения на модель - во-первых, она должна быть замкнута, во-вторых, не должно быть ребер, на которых пересекаются больше 2-х треугольников. Если все эти условия выполнены, то условие того что ребро принадлежит силуэту - если один из треугольников ребра лицевой стороной повернут к свету, а второй - нет. Все эти данные можно просчитать заранее, тем более обсчет этого не такой быстрый. В принципе, эта информация эквивалентна так называемой adjacency - информации о соседях каждого треугольника по каждому ребру. То есть у нас есть структура вроде struct ADJ { DWORD face1; DWORD face2; DWORD face3; }; И массив ADJ Adjacency [FaceNum] Причем если треугольник состоит из индексов index1, index2, index3, то face1 - номер соседнего ему треугольника по ребру index1-index2, face2 - по ребру index2-index3, face3 - по index3-index1. Тогда алгоритм становится таким - сначала вычисляем ориентацию всех граней объекта относительно источника света (ориентацию определяет знак скалярного произведения нормали треугольника и направления на источик света), ищем все ребра, которые лежат между треугольниками разной ориентации. Вторую часть можно реализовать по разному - можно перебирать все ребра и смотреть ориентацию их треугольников, можно бегать по, например, front-треугольникам и искать у них back-соседей или наоборот. Псевдокод алгоритма выглядит примерно так: Цикл (по всем граням объекта) { если Dot3 (normal, направление к источнику света) >= 0 записать что этот треугольник - front culled иначе записать что этот треугольник - back culled } Цикл (по всем front-culled граням объекта) { Цикл (по соседям треугольника) если сосед back-culled Добавить ребро с этим соседом в волюм. } Немного подробнее об операции "Добавить ребро с этим соседом в волюм". Тут важно сделать у этого квада правильную ориентацию, потому что она очень важна при отрисовке. Пусть front-culled треугольник, у которого есть back-culled сосед граничит с ним по ребру из вершин с индексами index1 и index2 (порядок очень важен - именно index1, а потом index2), тогда мы добавляем в волюм две вершины (пусть у них будут индексы index3 и index4), только с координатами Verts [index3].pos = Verts [index1].pos + (Большое число) * lightdir. Verts [index4].pos = Verts [index2].pos + (Большое число) * lightdir. Большое число - это то на какое расстояние мы вытягиваем волюмы чтобы они точно ушли за границу сцены. Когда мы все это сделали, то у квада волюма от этого ребра будут индексы (index2, index1, index3) и (index4, index3, index1). 3.9.3. Отрисовка волюма. 1. Отрисовка сцены. Отрисовать всю сцену без теней. Отключить текстурирование. Следующие два шага повторяются для каждого источника света в сцене. 2. Отрисовка волюмов в стенсил. Очистить стенсил значением 1. Выставить: Стенсил-тест - никакого. Запись в frame buffer - выключить. Запись в ZBuffer - выключить. При прохожденнии Z-Test'a - увеличить стенсил. Выставить куллинг -против часовой стрелки. Отрисовать все волюмы от данного источника света. Выставить: Стенсил-тест - никакого. Запись в frame buffer - выключить. Запись в ZBuffer - выключить. При прохожденнии Z-Test'a - уменьшить стенсил. Выставить куллинг - по часовой стрелке. Отрисовать все волюмы от данного источника света. 3. Отобразить тень на экране. Выставить: Стенсил-тест - проходит только если значение в стенсиле больше единицы. Запись в frame buffer - включить. ZBuffer - отключить совсем, не только запись. Блендинг - включить MUL. Отрисовать квадрат во весь экран с цветом яркости затененного участка (то есть,например, цвет(127, 127, 127)означает что в тени в два раза темнее). Этот алгоритм не универсален. Самый большой его недостаток - он не будет правильно работать если камера находится внутри волюма. Другие недостатки - не совсем правильное затенение. Правильная модель освещения должна быть такой - если какая-то точка находится в тени от источника света, то в ней должен отсутствовать его вклад в освещение, а не просто уменьшение общей освещенности. Единственный способ убрать этот недостаток - накладывать освещение от каждого источника за отдельный проход с предварительной отрисовкой волюмов в стенсил и включенным стенсил-тестом. 4. ЗАКЛЮЧЕНИЕ В итоге проделанной работы было изучено функционирование целого класса алгоритмов и создание нескольких законченных программ: простейшее демонстрационное приложение, с использованием алгоритма трассировки лучей; демонстрационное интерактивное трехмерное приложение, которое поддерживает : отображение сцен с использованием алгоритма порталов; поддержку трехмерных объектов в формате .3ds, которые могут содержать в себе анимацию; использование как динамического, так и статического света; спецэффекты, такие как прозрачность и хромовые покрытия; проигрывание музыки в формате mp3; звуковые спецэффекты с использованием технологии A3D; консоль для управления программой. Результаты исследований представлялись на научных конференциях: 9 студенческая научная конференция «Студенческая наука на пороге III тысячелетия», Мозырь 2002; V международная научная конференция «Наука и образование в условиях социально-экономической трансформации общества», Гродно 2002. ЛИТЕРАТУРА Д. Роджерс Алгоритмические основы машинной графики – Москва: Мир, 1989 г. Е. В. Шикин, А. В. Боресков, А. А. Зайцев Начала компьютерной графики – Москва: Диалог - МИФИ, 1993 г.

Похожие:

	Контрольная работа №1 Тема контрольной работы №1 Базовые основы компьютерной Области применения компьютерной графики; технические средства компьютерной графики: мониторы, графические адаптеры		«Юго-Западный государственный университет» (юзгу) Кафедра программного... Цель работы: Исследование развития криптографии и способов применения шифров в деятельности человека
	Разработка и исследование интегрированных алгоритмов размещения элементов... Специальности: 05. 13. 12 – Системы автоматизации проектирования, 05. 13. 17 – Теоретические основы информатики		Факультет математики и информационных технологий Кафедра информатики и вычислительной техники Познакомить учащихся с планетами Солнечной системы, сформировать представление о них и о том, отчего на Земле сменяются день, ночь,...
	Учитель математики, информатики и вычислительной техники Образование высшее Стаж работы Урок Правила техники безопасности. Повторение курса 8 класса (двоичная система)		Программа дисциплины Современные проблемы информатики и вычислительной... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 09....
	Рабочая программа по дисциплине В. В основы компьютерной графики Дисциплина «Основы компьютерной графики» является фундаментальной дисциплиной в подготовке бакалавра. Это одна из основных дисциплин...		«Наука компьютерной графики» Сазерленд и доктор Дэвид Эванс (David... После защиты диссертации на тему «Наука компьютерной графики» Сазерленд и доктор Дэвид Эванс (David Evans) открывают в университете...
	Задача изучения дисциплины освоить основные понятия компьютерной... Цель преподавания дисциплины – ознакомление студентов с основами компьютерной графики и графическими программами		Задача изучения дисциплины освоить основные понятия компьютерной... Цель преподавания дисциплины – ознакомление студентов с основами компьютерной графики и графическими программами
	Информатика и вычислительная техника Аналитический обзор по курсу «Современные проблемы информатики и вычислительной техники»		Контрольная работа выполняется в два этапа Составитель: Е. В. Моисеенко, доцент кафедры информатики, инженерной и компьютерной графики вгуэс
	Конспект урока информатики и икт (с использованием технологии сдп... Тема "Использование вспомогательных алгоритмов для рисования орнаментов в исполнителе Чертежник"		Программа по формированию навыков безопасного поведения на дорогах... После защиты диссертации на тему «Наука компьютерной графики» Сазерленд и доктор Дэвид Эванс (David Evans) открывают в университете...
	Программа по формированию навыков безопасного поведения на дорогах... После защиты диссертации на тему «Наука компьютерной графики» Сазерленд и доктор Дэвид Эванс (David Evans) открывают в университете...		Курсовая работа по дисциплине «Информатика и программирование» Кафедра «Программное обеспечение вычислительной техники и автоматизированных систем»