Трёхмерная компьютерная графика (стр. 12 из 12)

Вторая модификация использует упорядочение по приоритет чтобы сократить число объектов, для которых вычисляются пересечения с лучом. Вместо того, чтобы немедленно производить вычисление пересечения объекта к лучом, как это делается в изложенном выше простом алгоритме, объект помещается в список пересечённых объектов. После рассмотрения всех объектов сцены преобразованный список пересеченных объектов упорядочивается по приоритету глубины. Для определения приоритетного порядка можно использовать центры сферических оболочек или наибольшие (наименьшие) значения z прямоугольных оболочек. Пересечения луча с объектами из списка пересеченных объектов определяются в порядке их приоритетов. К сожалению точка пересечения луча с первым из объектов вупорядоченном по приоритетам списке пересеченных объектов необязательно будет видимой. Необходимо определить точки пересечения луча со всеми потенциально видимыми объектами из множества {Q} и занести их в список пересечений. Затем модифицированный алгоритм упорядочивает этотсписок пересечений так, как это делалось и в простом алгоритме. К счастью, множество {Q} потенциально видимых объектов обычно значительно меньше числа объектов в списке пересеченных лучом. Следовательно, эффективность алгоритма возрастет. Обе эти модификации применимы также и к общему алгоритму трассировки лучей, учитывающему отражение, преломление и прозрачность.

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

Д. Рот указал, что алгоритм трассировки лучей можно использовать также и для создания каркасных чертежей сплошных тел. При этом предполагается, что лучи порождаются в том порядке, в каком происходит сканирование экрана, т. е. сверху вниз и слева направо. Получающаяся процедура такова:

Если видимая поверхность для Пиксел(x, y) соответствует фону или отличается от видимой поверхности для Пиксел(x – 1, y) или для Пиксел(x, y – 1), то изобразить этот пиксел.В противном случае пиксел не изображать.

Алгоритм трассировки лучей можно использовать, кроме того, для определения физических свойств сплошного тела. Полное рассмотрение этого вопроса не входит в эту работу. Однако для иллюстрации этого подхода приведем один пример. В частности, объем любого сплошного тела можно определить, аппроксимируя его суммой маленьких прямоугольных параллелепипедов. Это можно проделать, породив множество параллельных лучей, расположенных на определенных расстояниях друг от друга. Точки пересечения каждого луча с заданным объемом вычисляются и упорядочиваются вдоль направления этого луча. Если подвергнуть луч переносу, совмещающему его с осью z, как это было описано выше, то объем каждого прямоугольного параллелепипеда будет равен:

где l_xи l_y – расстояниемежду лучами по горизонтали и вертикали соответственно. Каждое слагаемое (z_i-1 – z_i) представляет собой участок луча, лежащий внутри заданного тела. Объем тела, следовательно, равен сумме объемов всех таких прямоугольных параллелепипедов. Точность результатов зависит от числа использованных лучей. Точность можно повысить, умеренно увеличив объем вычислений и рекурсивно уменьшив размер “пиксела”, в том случае, если объемы смежных прямоугольных параллелепипедов различаются более чем на заранее заданную величину. При таком подходе точнее определяются объемы тех элементов тела, где имеют место быстрые изменения, например в окрестностях ребер тел, ограниченных криволинейными поверхностями.

Ввиду внутренне присущей алгоритму трассировки лучей параллельности вычислений (здесь все лучи обрабатываются одинаково и независимо друг от друга) его можно реализовать аппаратно на основе интегральных схем с использованием методов параллельной обработки.

Резюме

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

Другим примером является предложенный Азертоном интервальный алгоритм построчного сканирования, который используется для визуализации сцен, получающихся в системе конструктивного моделирования сплошных тел. Внутренний цикл этого алгоритма изменен так, чтобы можно было реализовать одномерные теоретико-множественные операции, необходимые для моделирующей системы, которая пользуется алгоритмом трассировки лучей. Азертон указывает, что этот интервальный алгоритм построчного сканирования требует примерно в 60 раз меньше времени, чем обычный алгоритм трассировки лучей.

В заключении хочу сказать, что компьютерная графика не стоит на месте. Уже давно существуют многочисленные программные и аппаратные реализации алгоритмов построения изображения. На рынке достаточно широко представлены всевозможные графические акселераторы и массивы быстрой памяти. Ведущие производители электронных компонентов поддерживают обработку изображения на уровне процессорной техники (MMX – Intel, 3D Now – AMD), следовательно, становится возможным реализация “медленных”, но дающих лучшее качество изображения алгоритмов.Отдельно следует отметить такое явления, как виртуальная реальность, которая уже в настоящее время получает широкое распространение. Одним словом, компьютерная графика будет развиваться до тех пор – пока будет развиваться и совершенствоваться компьютерная техника.