Пересечение прямоугольной области в преобразованной системе координат

3.14 Пересечение прямоугольной области в преобразованной системе координат

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

Q (x, y, z) = a₁x² + a₂y² + a₃z² +

 b₁yz + b₂xz + b3xy +

 c₁x + c₂y + c₃z +d = 0

После применения преобразования, которое является комбинацией переноса и поворота и используется для совмещения луча с осью z, пересечение этого луча с поверхностью, если оно имеет место, возникает при x = y = 0. Поэтому в общем случае точки пересечения являются решениями уравнения:

т.е.

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

Вычисления пересечений для элементов биполиномиальных параметрических поверхностей более сложны. Уиттед предложил простой метод разбиения для элемента бикубической поверхности. Вычисления выполняются с элементом поверхности в его исходном положении. Если луч пересекает сферическую оболочку элемента поверхности, то этот кусок разбивается с помощью алгоритма разбиения предложенного Кэтмулом. Затем луч проверяется на пересечение со сферическими оболочками подэлементов. Если пересечение не обнаружено, то луч не пересекается и с самим элементом. Если же луч пересекается со сферической оболочкой какого-нибудь подэлемента, то последний разбивается дальше. Процесс завершается, если ни одна из сферических оболочек не пересечена или если достигнут заранее определенный их минимальный размер. Эти сферические оболочки минимального размера и являются искомыми пересечениями луча и элемента поверхности.

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

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

Q (u, w) = 0

с компонентами

x = f (u, w)

y = g (u, w)

z = h (u, w)

в преобразованной системе координат выполнено условие x = y = 0. Значит,

f (u, w) = 0

g (u, w) = 0

Совместное решение этой пары уравнений дает значения u и w для точек пересечения. Подстановка этих значений в уравнение z = h (u, w) дает компоненту z для точек пересечения. Неудача попытки найти действительное решение означает, что луч не пересекает поверхность. Степень системы уравнений для u, w равна произведению степеней биполиномиальных поверхностей. Бикубическая поверхность, например, имеет шестую степень. Следовательно, в общем случае потребуются численные методы решения. Там, где это допустимо, для начального приближения u и w можно использовать пересечения луча с выпуклой оболочкой. Для получения пересечений в исходной системе координат, как и ранее, следует использовать обратное преобразование.

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

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

Подготовка данных для сцены:

Создать список объектов, содержащий по меньшей мере следующую информацию:

Полное описание объекта: тип, поверхность, характеристики и т. п.

Описание сферической оболочки: центр и радиус,

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

Описание прямоугольной оболочки: x_min, x_max, y_min, y_max, z_min, z_max.

Для каждого трассируемого луча:

Выполнить для каждого объекта трехмерный тест со сферической оболочкой в исходной системе координат. Если луч пересекает эту сферу, то занести объект в список активных объектов. Если список активных объектов пуст, то изобразить данный пиксел с фоновым значением интенсивности и продолжать работу. В противном случае, перенести и повернуть луч так, чтобы он совместился с осью z. Запомнить это комбинированное преобразование.

Для каждого объекта из списка активных объектов:

Если флаг прямоугольной оболочки поднят, преобразовать, используя комбинированное преобразование, эту оболочку в систему координат, в которой находится луч₁ и выполнить соответствующий тест. Если пересечения с лучом нет, то перейти к следующему объекту. В противном случае преобразовать, используя комбинированное преобразование, объект в систему координат, в которой находится луч, и определить его пересечения с лучом, если они существуют. Занести все пересечения в список пересечений.

Если список пересечений пуст, то изобразить данный пиксел с фоновым значением интенсивности.

В противном случае определить z для списка пересечений.

Вычислить преобразование, обратное комбинированному преобразованию.

Используя это обратное преобразование, определить точку пересечения в исходной системе координат.

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

Заметим, что алгоритм определения видимости простых непрозрачных поверхностей, не требует вычислять преобразование, обратное комбинированному, или определять точку пересечения в исходной системе координат, если в модели освещения не возникает необходимость включения в алгоритм свойств поверхности объекта или ее ориентации в точке пересечения. Эти шаги включены в данный алгоритм для полноты и удобства при реализации алгоритма трассировки лучей с учетом общей модели освещенности.

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

Вторая модификация использует упорядочение по приоритет чтобы сократить число объектов, для которых вычисляются пересечения с лучом. Вместо того, чтобы немедленно производить вычисление пересечения объекта к лучом, как это делается в изложенном выше простом алгоритме, объект помещается в список пересечённых объектов. После рассмотрения всех объектов сцены преобразованный список пересеченных объектов упорядочивается по приоритету глубины. Для определения приоритетного порядка можно использовать центры сферических оболочек или наибольшие (наименьшие) значения 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), следовательно, становится возможным реализация “медленных”, но дающих лучшее качество изображения алгоритмов. Отдельно следует отметить такое явления, как виртуальная реальность, которая уже в настоящее время получает широкое распространение. Одним словом, компьютерная графика будет развиваться до тех пор – пока будет развиваться и совершенствоваться компьютерная техника.

Похожие работы

Компьютерная графика и решаемые ею задачи

Скачать

17177

0

0

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

Тенденции развития рынка компьютерной графики и анимации

Скачать

20082

0

0

... в качестве реальной альтернативы системе Unix.  _ 23.Платформа Intel ПК с процессором Intel продолжает оставаться наиболее распространённой платформой в сфере компьютерной графики и анимации. Главным событием, имеющим к ней непосредственное отноше- ние, стала демонстрация компанией Autodesk четвёртой версии программы 3D Studio - ...

Компьютерная графика

Скачать

29081

0

3

... простыми. Большинство цветовых оттенков образуется смешением основных цветов. Способ разделения цветового оттенка на составляющие компоненты называется цветовой моделью. Существует много различных типов цветовых моделей, но в компьютерной графике, как правило, применяется не более трех. Эти модели известны под названиями: RGB, CMYK, НSB. Цветовая модель RGB Наиболее проста для понимания и ...

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

Скачать

66016

2

0

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