Метод трассировки лучей
Суть метода заключается в том, что для каждой точки на проектируемой плоскости строится луч, начало которого совпадает с положением наблюдателя, а угол луча по отношению к направлению наблюдения определяется характеристиками наблюдателя (максимальный угол зрения относительно горизонтальной и вертикальной плоскостей) и точкой плоскости проецирования (картинная плоскость), для которой строится луч. После построения луча определяется его пересечение со всеми гранями, из которых состоит сцена и выбирается та грань, расстояние от которой до наблюдателя минимально. Далее в данной точке картинной плоскости рисуется пиксель цветом, определяемым в точке пересечения луча и выбранной грани. Этот метод является довольно простым и позволяет совместить определение видимости с расчётом цвета соответствующего пикселя. Ещё одним преимуществом метода является то, что сцена может состоять не из треугольников, а быть заданна набором геометрических примитивов (например, поверхностями второго порядка). В этом случае пересечение луча с геометрическим примитивом вычисляется аналитически (точное решение задачи построения геометрического примитива), в отличие от разбивания произвольного геометрического примитива (например, сферы) на треугольники и решения более простой задачи пересечения луча с треугольником. Для данного метода разработано довольно большое количество методов оптимизации, позволяющих сократить временную сложность данного алгоритма в общем виде (когда вычисляется пересечение каждого луча с каждым треугольником, входящим в сцену). Тем не менее для реализации метода требуется довольно большое количество вычислений и в настоящее время он применяется в основном для построения реалистичных изображений не в реальном масштабе времени.
|
|
Метод z-буфера
Данный метод является одним из самых простых и распространённых методов удаления невидимых граней и имеет аппаратную реализацию в большинстве современных графических акселераторах. Метод заключается в том, что для каждого пикселя, выводимого на экран, находится грань, расстояние до которой минимально. Для этого каждому пикселю, выводимому на экран, кроме его цвета ставится в соответствие расстояние до картинной плоскости вдоль направления проектирования (его глубина). z-буфер инициализируется значением +Ґ. Для вывода произвольной грани, эта грань сначала переводится в растровое представление (используя конкретное перспективное преобразование), а затем для каждого пикселя этой грани вычисляется значение его глубины. Если это значение глубины меньше значения, хранящегося значения в z-буфере для соответствующего пикселя, то это значение глубины заносится в z-буфер, а пиксель выводится на экран. Если это не так, то в z-буфер ничего не заносится, а пиксель не выводится на экран. Таким образом, после выполнения этих операций в каждой точке экрана будет находиться пиксель, соответствующий грани, находящейся ближе всего к картинной плоскости в данной точке. Довольно эффективным является совмещение растеризации грани с выводом в z-буфер. При этом могут применяться инкрементальные методы, требующие всего нескольких операций сложения на пиксель. В этом случае грань рисуется построчно, с применением линейной интерполяции для вычисления координат строки и её длины. Так как при использовании перспективного преобразования значения глубины пикселя изменяются нелинейно при линейном изменении значений координат X и Y пикселя, то для вычисления значения глубины пикселя инкрементальными методами используется w-буфер, в котором хранятся не значения глубины (z) пикселя, а значения 1/z, которые уже изменяются линейно при линейном изменении координат X и Y пикселя, и для нахождения значений 1/z могут применяться инкрементальные методы.
|
|
Порядок вывода граней в z-буфер не имеет значения, так как для каждой из них всё равно выполняется сравнение глубин пикселей с соответствующими значениями, находящимися в z-буфере.
Метод z-буфера является избыточным так как в одну точку экрана могут выводиться несколько пикселей за один проход рисования всех граней сцены. Каждый последующий пиксель, выводимый на экран, перекрывает предыдущий. Поэтому возникает вопрос о том, какие грани не могут быть потенциально видимы по отношению к z-буферу.
Одним из наиболее распространённых модификаций алгоритма z-буфера является алгоритм иерархического z-буфера. Назовём грань скрытой (невидимой) по отношению к z-буферу, если для всех её точкек их глубины не меньше соответствующих значений в z-буфере (при попытке вывести такую грань в z-буфер ничего не изменится). Куб (прямоугольный параллелепипед) назовём скрытым по отношению к z-буферу, если все его лицевые грани являются скрытыми. Теперь объединим несколько граней сцены и обведём вокруг них куб. Для вывода этих граней в z-буфер проверяется, является ли этот куб скрытым по отношению к z-буферу. Если это так, что и все грани, объединённые кубом являются скрытыми по отношению к z-буферу и не выводятся в него, сокращая количество вычислений и ненужных операций сравнения. Если же это не так, то всё равно не все грани, объединённые кубом являются видимыми и этот куб разбивается на части, а затем для каждой части выполняются такие же операции сравнения. Таким образом реализация данного алгоритма может выглядеть следующим образом. Вокруг всей сцены описывается куб, он разбивается на 8 частей (тоже кубы), а каждая из частей, в свою очередь, разбивается ещё на 8 частей и так до тех пор, пока количество граней в кубе не станет меньше заданного числа, при котором уже нет смысла в дальнейшей разбивке на части. Далее для вывода очередного куба в z-буфер для него проверяется, является он скрытым или нет. Если да, то все грани, объединённые этим кубом игнорируются, а если нет, то соответствующая проверка выполняется для всех его частей и т.д. Для упрощения проверки на скрытость грани строится z-пирамида. Основанием такой пирамиды является сам z-буфер, каждый последующий уровень пирамиды образуется из предыдущего объединением 4 (2 на 2) пикселей предыдущего уровня и присваиванием наибольшей глубины из этих 4 пикселей значению глубины соответствующего пикселя последующего уровня пирамиды. Вершиной пирамиды является уровень, состоящий из одного единственного пикселя. Далее для проверки скрытости грани по отношению к z-буферу сначала сравнивается значение минимальной глубины для этой грани с значением в вершине пирамиды. Если значение в вершине пирамиды меньше, то грань игнорируется, в противном случае она разбивается на 4 части и для каждой части выполняется сравнение с значениями на следующем (более низком) уровне пирамиды. И так до тех пор пока все части грани не будут отвергнуты, или пока текущим уровнем пирамиды не станет её основание.
|
|
Для ещё большей оптимизации вывода в z-буфер и для снижения количества вычислений используется тот факт, что чем раньше видимая грань будет выведена в z-буфер, тем больше невидимых граней, закрываемых ею, будет отвергнуто. Для этого строится список тех граней, которые были выведены в предыдущем кадре. В последующем кадре эти грани выводятся в z-буфер самыми первыми, так как почти наверняка они будут оставаться видимыми и в этом кадре.
Метод отсечения по нормалям
Данный метод заключается в том, что если грань является нелицевой, то она не может быть видима. Лицевой называется грань, для которй скалярное произведение вектора нормали к этой грани и вектора направления взгляда наблюдателя должно быть отрицательным. Таким образом, этот простой метод можно использовать до применения метода z-буфера при построении сцены - для всех граней, выводимых в z-буфер, проверяется значение скалярного произведения векторов нормалей граней и вектора нормали к картинной плоскости (в направлении от наблюдателя) и если значение этого скалярного произведения больше 0, то соответствующая грань удаляется из списка граней, подвергаемых выводу в z-буфер.