Оптимизации трассировки лучей

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

Особенно долго ищется пересечение с объектами сложной формы. Объект можно поместить внутрь простой фигуры (например, сферы). Если луч не пересекает эту фигуру, то он не пересекает и обьект, который исследовать не надо. Пересечение со сферой определить просто, можно использовать, например, аналитический метод (уравнение). Вспомогательную фигуру пересечет небольшая часть рассматриваемых лучей. Эти лучи проверяются на пересе­чение со сложной фигурой. Здесь очевиден выигрыш за счет уменьшения количества лучей. Можно описать фигуру вокруг нескольких объектов. При пересечении - аналогичное разбиение группы на подгруппы и т.д. Стро­ится дерево разбиений. Начальная простая фигура содержит всю сцену (аналог дихотомии). Количество прове­рок на пересечение для данного метода пропорционально O (log n), где n - общее количество объектов.

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

37. Метод излучательности.

Основной недостаток метода трассировки лучей - неэффективность работы с диффузными поверхно­стями и зависимость подсчитываемой освещенности от положения наблюдателя. Из-за этого при изменении по­ложения наблюдателя вся сцена перестраивается. Метод излучательности устраняет этот недостаток. В основе метода лежит закон сохранения энергии в замкнутой системе. Все объекты разбиваются на фрагменты, для этих фрагментов составляются уравнения баланса энергии.

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

Bi=Ei+piSFi,j*Bj i=1..n

гдеBi - энергия, отбрасываемая i-тым фрагментом сцены,

Ei - собственная излучательность фрагмента,

Fi,j - доля энергии j-того фрагмента, попадающая на i-тый фрагмент (коэффициент формы),

рi - коэффициент отражения.

Если пройти по всем объектам, получим систему линейных алгебраических уравнений.

Из закона сохранения энергии следует, что SFi,j <1 для всех i.

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

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

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

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

38. Системы цветов.

До сих пор цвет рассматривался в так называемой аддитивной форме как композиция в некоторой пропорции 3 базовых цветов - RGB. Соединение всех трех цветов в равной пропорции образует белый цвет, отсутствие всех цветов - черный (фон). Система RGB естественна для компьютера.

Существует и другой подход к формированию цвета - субтрактивный. Он характерен для полиграфии и учитывает поглощение и отражение света от белой поверхности (бумага). Подход основан на вычитании цветов. Здесь белый цвет (фон) - отсутствие всех цветов, черный - соединение в равной пропорции голубого (cyan), пурпурного (magenta) и желтого (yellow). На практике только сочетанием 3 базовых цветов достигается не черный, а темно-коричневый цвет из-за неполного поглощения света типографскими красками. Поэтому для представления истинно черного делают 4-цветную печать с добавлением черного, система цветов называется CMYK (чтобы не путать с Blue - синий, взята последняя буква слова blacK - черный). Происходит как бы вычитание цвета из белого. Данная система была разработана давно и применялась в полиграфии. Для цветоделения (разделения цветов на основные цвета CMYK) применялись фотомеханические методы.

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

Системы цветов RGB и CMYK базируются на ограничениях, накладываемых аппаратурой (дисплей, типографское оборудование), и основаны на смешении красок. Существует другой подход, учитывающий яркость (насыщенность) цветов. Его реализация - системы HSI(HSL) и YcbCr.

Аббревиатура HSI (HSL) означает Hue - цвет, оттенок, Saturation - насыщенность, Intensity или Luminosity - яркость. Насыщенность трактуется как количество белого, подмешанного к основному цвету (темно-синий/голубой), яркость может отражать, например, освещенность (апельсин в солнечном свете или в сумерках). HSI - более интуитивный способ определения цветов, не зависящий от схемы смешения. В этой системе работают некоторые пакеты программ, имеются графические адаптеры, которые “понимают” HSI и преобразуют ее в RGB. HSI больше соответствует природе света.

Аббревиатура YcbCr происходит от Y(luminositY, яркость), Cb (chrominance blue, цветность исходного синего), Cr (chrominance red, цветность исходного красного). Зеленый - комбинация этих трех значений. Отделение яркости от цветности позволяет более эффективное сжимать изображения (см. п. 7.3), т.к. глаз человека больше реагирует на интенсивность, чем на разрешение цвета. Представление YcbCr все шире используется для настольных видеосистем.

Все системы, кроме CMYK, состоят из 3 компонентов, т.е. описывают 3-цветное пространство. Система CMYK описывает 4-цветное пространство. Поэтому преобразование не всегда взаимно однозначно, возникает неточность преобразования и восстановления изображений, искажения. Обычно изображение, полученное программно, корректируется человеком.

Монохромные изображения (градации серого) выводятся на дисплей или лазерный принтер. Используются точки одного цвета. Их густота дает оттенок. Изображение называется полутоновым, если обеспечивается непрерывность оттенка. При редактировании на дисплее используют биты интенсивности. При печати это не подходит. Используется добавочный псевдослучайный сигнал, который позволяет регулировать количество черных точек. Он накладывается на основной рисунок, что создает эффект “размытости”. При этом разрешение устройства уменьшается, т.к. часть битов используется для изображения, часть – для дополнительного сигнала. Аналог - увеличение цветности за счет уменьшения разрешения видеоадаптера. Таким образом, печать выполняется с псевдослучайным сигналом, редактирование - с битами интенсивности, т.к. большинство графических приложений не различает точки для основного рисунка и точки для оттенения.

При переносе изображений между носителями возникает также проблема точности цветов и для цветных, и для полутоновых изображений. Например, на разных дисплеях различны оттенки красного, белая точка имеет не совсем белый цвет, хотя значения R, G и B равны. Требуется калибровка входных и выходных устройств, например, цветного сканера и монитора, на который идет изображение. Используют различные колориметрические стандарты. Наиболее известные из них: CIE (Commitee International de l’Eclairage), NTSC (National Television System Commitee), SMPTE (Society of Motion Picture and Television Engineers), ISO (International Standards Organization). В каждом стандарте устанавливается комплект чисел, используемых для определения объективно измеренного цвета. Цвет, который входным и выходным устройством определен как белый, может быть измерен поставщиком устройства и выражен комплектом чисел. Этот результат называется белой точкой устройства. Следовательно, для точной передачи цвета графический файл должен содержать описание в некотором стандарте белой точки передатчика. Пока это реализуется весьма редко, не поддерживается форматами графических файлов. В большинстве устройств также отсутствует автоматическая подстройка цветности.

39. Основные методы сжатия изображений.

Сжатие изображений

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

Групповое кодирование

Один из самых простых методов сжатия - групповое кодирование или групповое сжатие. Другое название - "сжатие методом RLE" (run-length encoding). Идея состоит в том, что вместо повторяющихся пикселов хранится информация о цвете точки и количестве повторений. Представление данных имеет варианты: может сначала идти запись о цвете, потом о количестве, может - наоборот. Это порождает проблемы воспроизведения. Для большинства растровых файлов, особенно для фотореалистических сжатие RLE не эффективно, т.к. мало повторяющихся пикселов. Возникает даже лишняя трата ресурсов.

Поиск по сайту: