Методы удаления скрытых линий и поверхностей

Существуют различные алгоритмы, позволяющие удалять и не выводить как отдельные ребра объектов, скрытые видимыми поверхностями, так и невидимые грани [10, 14, 17].

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

· методы, работающие непосредственно в пространстве самих объектов;

· методы, работающие в пространстве картинной плоскости.

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

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

Для уменьшения времени расчетов используют когерентность различных видов:

· когерентность в картинной плоскости – если данный пиксель соответствует точке некоторой грани, то, скорее всего, соседние пиксели также соответствуют точкам этой грани;

· когерентность в пространстве объектов – если данная грань видима, то, скорее всего, и соседние с ней грани видимы;

· временная когерентность (для анимации) – грани, видимые в данном кадре, скорее всего будут видны и в следующем кадре.

7.7.1. Методы оптимизации

Методы оптимизации широко используются для уменьшения затрат времени на удаление невидимых линий и поверхностей.

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

При выполнении различных операций по выявлению перекрывающих друг друга граней широко используют ограничивающие грань тела (оболочки). В качестве оболочек чаще всего используют параллелепипеды с гранями, параллельными координатным плоскостям. Если такой ограничивающий грань параллелепипед задан координатами своих диагональных углов (x_min, y_min, z_min) и (x_max, y_max, z_max), то проверка пересечения оболочек двух граней сводится к простой процедуре проверки пересечения трех промежутков: от x_min до x_max, от y_min до y_max и от z_min до z_max. Если хотя бы один из этих промежутков не пересекается с аналогичным промежутком для оболочки другой грани, то оболочки граней не пересекаются и, следовательно, грани тоже не пересекаются. Грани, оболочки которых пересекаются, могут как пересекаться, так и не пересекаться, и в этом случае проводят более сложные вычисления.

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

Один из методов, позволяющих построить PVS – метод порталов. В начале сцена разбивается на набор выпуклых областей. Все грани внутри области могут быть видны, следовательно, они автоматически заносятся в PVS для этой области. Рассматриваются соседние области, соединенные с текущей порталами. Порталами называются те соединения, через которые можно видеть (окна, двери и т.п.). В соседних областях определяются грани, которые могут быть видны из текущей области через порталы. Эти грани заносятся в PVS для текущей области. На следующем этапе рассматриваются области, соединенные с соседними с текущей областями через порталы, в этих областях определяются грани, которые могут быть видны из текущей области (но уже через два портала), и т.д.

7.7.2. Метод сортировки граней по глубине

Визуализация граней проводится в порядке от самых дальних от наблюдателя к самым близким. Ближайшие многоугольники преобразуются в растр последними и закрывают более отдаленные многоугольники, т.к. записываются в буфер регенерации поверх старых.

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

7.7.3. Метод плавающего горизонта

Используется при построении графика функции двух переменных z=f(x,y) в виде сетки координатных линий x=const, y=const.

Грани выводятся в порядке от самых ближайших к самым дальним от наблюдателя. Все линии z=f(x, y_i), где y_i=const лежат в параллельных плоскостях и, следовательно, не пересекаются. Допустим, что координатные оси сориентированы так, что при y_i>y_i-1 плоскость y=y_i расположена ближе к наблюдателю, и значения у меняются от у₀ до у_n. На первом шаге рисуются ближайшие к наблюдателю грани (у_i= у_n).

Выведенные на первом шаге грани видимы (они самые ближние и их ничего не заслоняет) и образуют так называемый горизонт. На следующих шагах рисуются только те части линий z=f(x, y_i), которые не закрываются ранее нарисованными, т.е. лежат выше верхнего или ниже нижнего горизонтов.

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

7.7.4. Метод z-буфера

Этот метод работает в пространстве картинной плоскости.

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

Предположим, что ближе к наблюдателю располагаются объекты с наибольшими значениями z. Тогда метод z-буфера будет действовать так.

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

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

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

Данный метод прост и эффективен, не требует предварительной сортировки граней.

Закрашивание поверхностей

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

7.8.1. Модели отражения и преломления света

В компьютерной графике рассматриваются объекты, которые по отношению к свету обладают следующими свойствами:

· излучают свет;

· отражают и поглощают свет;

· пропускают свет сквозь себя.

Каждое из этих свойств можно описать некоторым набором характеристик.

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

Отражение света может быть нескольких видов – зеркальное, диффузное, обратное [10].

Зеркальное отражение (рис. 7.2, а) – падающий на поверхность луч (l) и отраженный луч (s) лежат в одной плоскости, причем угол падения светового луча равен углу отражения. Цвет отраженного луча совпадает с цветом падающего луча, т.е. собственного цвета у зеркальной поверхности нет. Наблюдатель будет видеть отраженный луч только если угол g между направлением отраженного луча (s) и направлением на наблюдателя (v) равен нулю (рис. 7., а).

Не идеальное зеркальное отражение происходит при падении света на слегка шероховатую поверхность (рис. 7.2, б). В этом случае возникает несколько отраженных лучей, рассеиваемых по различным направлениям. Зона рассеивания зависит от качества полировки и, как правило, симметрична относительно направления идеально отраженного луча, а ее форма может быть описана некоторым законом распределения. Одной из простейших моделей распределения, наиболее часто используемой в компьютерной графике, является модель Фонга:

I_s = I k_s cos^Рa,

где I_s – интенсивность отраженного луча, I – интенсивность падающего луча, k_s – коэффициент пропорциональности, р=1…200 – показатель качества полировки поверхности, a – угол отклонения от направления идеально отраженного луча.

Сильно шероховатым (матовым) поверхностям присуще диффузное отражение, при котором падающий луч равномерно рассеивается во все стороны (рис 7.2, в). Матовая поверхность имеет свой цвет – наблюдаемый цвет матовой поверхности определяется комбинацией собственного цвета поверхности и цвета падающего луча. Интенсивность диффузно отраженного света не зависит от положения наблюдателя.

Диффузное отражение описывается законом Ламбера:

I_d = I k_d cos q,

где I_d – интенсивность диффузно отраженного луча, I – интенсивность падающего луча, k_d – коэффициент, учитывающий свойства материала поверхности, q – угол между нормалью (n) к поверхности и направлением падающего луча (l).

Рис. 7.2. Отражение света: а) идеальное зеркальное, б) не идеальное зеркальное, в) диффузное.

Существует еще и обратное отражение, при котором максимум интенсивности отраженного света соответствует направлению на источник света.

При изображении объектов в компьютерной графике обычно моделируют сумму зеркального и диффузного отражений:

I_отр = I (k_d cos q + k_s cos^Рa),

где I_отр – интенсивность отраженного луча.

При некоторых значениях углов q и a интенсивность отраженного света будет равна нулю. Однако, в реальных сценах полностью затемненные объекты используют редко, т.к. учитывают освещение отраженным от других объектов светом (фоновую подсветку) с интенсивностью I_а:

I_отр = I_а k_а + I (k_d cos q + k_s cos^Рa).

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

I_отр = I_а k_а + I (k_d cos q + k_s cos^Рa) / (R + k),

где R – расстояние до источника света, k – константа.

При прохождении световых лучей через полупрозрачную среду происходит их преломление. Падающий и преломленные лучи лежат в одной плоскости, причем:

h₁ sina₁ = h₂ sina₂,

где h₁ и h₂ – показатели преломления двух сред, a₁ и a₂ – углы падения и преломления светового луча (рис. 7.3.).

Рис. 7.3. Преломление светового луча на границе двух сред.

Показатель преломления зависит не только от материала среды, но и от длины световой волны: чем меньше длина волны (фиолетовые цвета), тем сильнее отклоняется луч. Существует и диффузное преломление, когда преломленный луч рассеивается равномерно во все стороны, но в компьютерной графике оно используется редко из-за трудности расчета.

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

7.8.2. Определение цвета закрашивания

Наиболее просто выполняется расчет при закрашивании в градациях серого цвета (для источника белого света и серых объектов). В этом случае вычисленная интенсивность отраженного света будет просто соответствовать яркости.

Для цветных объектов, освещаемых цветным источником света, составляются три формулы расчета интенсивности отраженного света – по одной на каждую цветовую компоненту в модели RGB. Цвет источника будет выражаться значениями интенсивности I для каждой цветовой компоненты. Коэффициенты k_а и k_d выражают собственный цвет поверхности и, следовательно, для одной и той же поверхности будут различны для каждой из компонент. Коэффициент k_s будет одинаков для всех цветовых компонент, т.к. цвет зеркально отраженного луча равен цвету источника.

7.8.3. Модели закрашивания

Существует несколько моделей закрашивания плоских граней.

На закрашивание грани в общем случае влияют направления четырех векторов: нормали к плоскости грани (n), направления на источник света (l), направления идеального зеркального отражения (s) и направления на наблюдателя (v). При переходе от одной точки плоской грани к другой направление вектора n остается постоянным, изменяются только вектора l, s и v. Однако, в случае удаленного источника света и далеко расположенного наблюдателя этими изменениями можно пренебречь.

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

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

Для сглаживания полос Маха применяются интерполяционное закрашивание и закрашивание методом Гуро.

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

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

n = .

Закраска методом Гуро позволяет визуально сгладить переходы между гранями, однако в некоторых случаях не удается избежать появления полос Маха.

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

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

Расчет закраски объектов в сложно построенных сценах с несколькими источниками освещения выполняется более сложно. Обычно в этом случае используют трассировку лучей или метод анализа излучательности.

При выполнении трассировки лучей предполагается, что световой луч в свободном пространстве распространяется вдоль прямой линии. От источников излучения в разных направлениях исходит бесчисленное множество лучей. Некоторые лучи уходят в свободное пространство, а некоторые лучи попадают на объекты. При попадании на прозрачный объект световой луч преломляется, при этом некоторая часть световой энергии поглощается. При попадании на зеркальную поверхность луч изменяет направление (отражается), часть световой энергии при этом также поглощается. Если объект и отражает и поглощает, то световой луч расщепляется. Таким образом, в результате действия на объекты первичных лучей возникают вторичные лучи, которые также могут попадать на объекты. После многократных отражений и преломлений световой некоторая часть световых лучей попадает в точку зрения, т.е. изображение сцены формируется множеством световых лучей [10, 14, 20].

Трассировку лучей обычно выполняют в обратном порядке (обратная трассировка) – от наблюдателя. Трассируется не бесконечное, а конечное множество лучей, исходящих из точки зрения и проходящих через каждый пиксель изображения. Каждый луч проверяется на пересечение с объектами сцены. Когда выясняется, что текущий луч обратной трассировки не пересекает никакого объекта, а уходит в пространство, трассировка для этого луча заканчивается.

Для повышения быстродействия метода используются некоторые ограничения, например:

· источники света могут только излучать свет, но не могут его отражать и преломлять;

· рассматриваются только точечные источники света;

· для учета освещенности светом, рассеиваемым другими объектами сцены, вводится фоновая составляющая;

· для прозрачных объектов не учитывается зависимость коэффициента преломления от длины волны или вообще прозрачность моделируют без преломления луча света;

· отражение описывается диффузной и зеркальной составляющими;

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

· при диффузном отражении игнорируются лучи от зеркально отражающих поверхностей;

· для завершения трассировки вводят некоторое пороговое значение освещенности или ограничивают число итераций.

Метод анализа излучательности используется для тонирования сцен, в которых подавляющее число объектов имеет поверхности с диффузным рассеиванием [20]. Формируется глобальное уравнение энергетического баланса, решение которого позволяет получить цвет каждой матовой поверхности.

Закрашиванием объектов можно передать иллюзию глубины пространства или эффект тумана.

В природе контуры отдаленных объектов кажутся наблюдателю размытыми, затуманенными. Этот эффект можно смоделировать в процессе закраски объектов [20]. Для этого среда, в которой находятся объекты формируется полупрозрачной. Итоговый цвет объекта С расчитывается по формуле:

C = f C_o + (1 – f) C_f,

где C_o – исходный цвет объекта, рассчитанный с учетом его освещенности, C_f – цвет полупрозрачной среды (тумана), f – функция туманности, которая зависит от расстояния между объектом и наблюдателем.

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

Детализация поверхностей

Существуют два типа детализации поверхностей – цветом (наложение проективных текстур) и фактурой (микрорельефом поверхности) [14].

Текстура представляет собой массив растрового узора, который налагается на поверхность трехмерного объекта на этапе тонирования. Узор текстуры задается функцией интенсивности, которая используется либо для модификации цвета основной поверхности, определяемого с учетом освещенности, либо для назначения для основной поверхности цвета только текстуры.

Основные трудности возникают при наложении плоской текстуры на трехмерные кривые поверхности объектов (например, на шар).

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

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

Текстуры могут быть и анимированными (движущимися) [1].

Текстуры можно использовать и для имитации фактуры (микрорельефа) поверхности. Однако, если положение объекта относительно источников света будет изменяться, ненатуральность такого «микрорельефа» будет сразу заметна.

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

Существуют и более сложные способы непосредственного моделирования рельефа поверхности, например использование фрактальных поверхностей [14]. Фрактал – это объект довольно сложной формы, получающийся в результате выполнения простого итерационного цикла. Фракталы хорошо описывают природные объекты и большинство искусственных [4, 10, 15].

Построение трехмерных сцен

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

Для описания трехмерных моделей используются разные подходы.

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

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Авраамова О.Д. Язык VRML. Практическое руководство. – М.: ДИАЛОГ-МИФИ, 2000. – 288 с.

2. Боресков А.В., Шикин Е.В., Шикина Г.Е. Компьютерная графика: первое знакомство. – М.: Финансы и статистика, 1996. – 176 с.

3. Борн Г. Форматы данных. – СПб.: БХВ, 1995. – 472 с.

4. Гулд Х., Тобочник Я. Компьютерное моделирование в физике: В 2-х частях. Часть 2: Пер. с англ. – М.: Мир, 1990. – 400 с.

5. Залогова Л.А. Практикум по компьютерной графике. – М.: ЛБЗ, 2001. – 320 с.

6. Иванов В.П., Батраков А.С. Трехмерная компьютерная графика. – М.: Радио и связь. – 223 с.

7. Кадиев А.Р., Степанова И.В. Компьютерная графика. Учебное пособие. Часть I. – М.: МГАПИ, 2001. – 24 с.

8. Мюррей Д., ван Райпер У. Энциклопедия форматов графических файлов: пер. с англ. – К.: БХВ, 1997. – 672 с.

9. Павлидис Т. Алгоритмы машинной графики и обработки изображений. – М.: Радио и связь, 1986.

10. Порев В.Н. Компьютерная графика. – СПб.: БХВ-Петербург, 2002. – 432 с.

11. Роджерс Д., Адамс Дж. Математические основы машинной графики: Пер. с англ. – М.: Мир, 2001. – 604 с.

12. Тихомиров Ю. Программирование трехмерной графики. – СПб.: BHV, 1998 – 256 с.

13. Томпсон Н. Секреты программирования трехмерной графики для Windows 95. Пер. с англ. – СПб.: Питер, 1997. – 352 с.

14. Фоли Дж., вэн Дэм А. Основы интерактивной машинной графики: В 2-х книгах. Пер. с англ. – М.: Мир, 1985.

15. Федер Е. Фракталы. – М.: Мир, 1991. – 254 с.

16. Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения. – М.: Диалог-МИФИ, 1995.

17. Шикин Е.В., Боресков А.В. Компьютерная графика. Полигональные модели. – М.: Диалог-МИФИ, 2000. – 464 с.

18. Шикин Е.В., Плис А.И. Кривые и поверхности на экране компьютера. – М.: Диалог-МИФИ, 1996.

19. Эгрон Ж. Синтез изображений. Базовые алгоритмы. – М.: Радио и связь, 1993.

20. Эйнджел Э. Интерактивная компьютерная графика. Вводный курс на базе OpenGL. – 2 изд.: Пер. с англ. – М.: Вильямс, 2001. – 592 с.

Учебное пособие