Как претворить в жизнь идею компьютерной игры? Приходилось ли вам, играя в свою любимую игру, мечтать о том, как можно было бы ее улучшить

Вид материала

Содержание

Алгоритм Художника, Тест 1
Алгоритм Художника, Тесты 3 и 4
Алгоритм Художника, Тест 5
Время выполнения Алгоритма Художника

Подобный материал:

1 ... 5 6 7 8 9 10 11 12 ... 37

Фаза 1. Прежде всего удаляются поверхности, которые никогда не будут видны с точки зрения наблюдателя. Для этого мы должны использовать точку пересечения между вектором наблюдения и вектором нормали к каждой из рассматриваемых плоскостей. Мы вычисляем это значение. Если значение угла меньше 90°, то поверхность видна, если больше 90° - нет и она удаляется.

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

Существует популярный Алгоритм Художника, который это хорошо умеет делать. Он работает, выполняя пять тестов для каждой видимой пары многоугольников (поверхностей) и затем создает последовательность их окраски от дальней части изображения к ближней.

Другая техника создания этой последовательности носит название Алгоритма Z-буфера. Он работает в пространстве образа на уровне пикселей. Он прост в реализации, но медленно работает и требует много памяти.

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

Алгоритм художника

Алгоритм Художника — это один из тех алгоритмов, которые могут создавать ощущение реальности. Основная идея Алгоритма Художника состоит в сортировке поверхностей таким образом, что при рендеринге это выглядит корректно. Наиболее просто этот алгоритм может быть реализован, когда каждая поверхность параллельна плану просмотра (то есть перпендикулярна лучу зрения). В этом случае нам достаточно отсортировать поверхности в порядке уменьшения значения координаты Z. Затем мы сначала нарисуем самую дальнюю поверхность, потом более близкую и т, д. Это достаточно специфичное условие, но и у него есть свои реализации.

Проблемы начинают возникать, когда поверхность не параллельна плану просмотра. При этом все/разбивается на куски и мы вязнем в выполняемых тестах. Это значит, что нам надо выполнить множество вычислений. Рисунок 6.13 показывает вид сверху вниз двух многоугольников в одном из самых неудачных случаев.

Безразлично, как мы будем сортировать эти многоугольники - по минимуму, максимуму или среднему значению Z - мы всегда получим неверный результат. Чтобы этого избежать, мы должны проделать пять тестов для каждой пары многоугольников.

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

Алгоритм Художника, Тест 1

Имеются ли общие значения Х-координат для многоугольника 1 и многоугольника 2, как это изображено на рисунке 6.14

Если нет, то с этой парой многоугольников все в порядке. Последовательность их рисования не играет роли, поскольку они не закрывают друг друга;
Если да, то перейти к Тесту 2.

Алгоритм Художника, Тест 2

Имеются ли общие значения Y-координат для многоугольника 1 и многоугольника 2, как это показано на рисунке 6.15?

Если нет, то их можно рисовать также в любом порядке;
Если да, то выполнить Тесты 3 и 4.

Алгоритм Художника, Тесты 3 и 4

Тесты 3 и 4 похожи, поскольку оба они работают с отсекающими плоскостями. Чтобы понять тест, мысленно продолжите грани многоугольника в бесконечность в обоих направлениях, создавая плоскость. Это плоскость отсечения. Посмотрите на рисунок 6.16.

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

Если ни одна из построенных плоскостей отсечения не пересекает другой многоугольник, то они могут быть корректно отрисованы;
Иначе перейти к Тесту 5.

Алгоритм Художника, Тест 5

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

Обработка такой ситуации настолько сложна, что в этом случае не существует каких-либо общих рекомендаций,
^

Время выполнения Алгоритма Художника

Алгоритм художника хорошо, но, к сожалению, медленно работает. В худшем случае, количество операций примерно равно O(n²), где n - количество многоугольников.

Алгоритм Z - буфера

Поскольку скорость и объем памяти ПК постоянно увеличивается, на смену Алгоритму Художника пришел Алгоритм Z-буфера. Этот алгоритм более прост в реализации, чем Алгоритм Художника. (Сегодня большинство высокопроизводительных графических систем и графических станций имеют аппаратную реализацию этого алгоритма, что избавляет от необходимости решать проблему удаления невидимых поверхностей самостоятельно).

Реализация Алгоритма Z-буфера проста. Все, что для этого нужно - сам 2-буфер, который имеет такой же объем, как и видеобуфер. В нашем случае это будет матрица целых чисел размером 320х200. Затем мы заполняем ее значениями Z-координат многоугольников, следуя таким правилам: