/>Оглавление
Введение
1. Конструкторская часть
Трассировка лучей
Построение теней
— Сплошные тени
— Реалистичные тени
Математические и физические предпосылки алгоритма обратнойтрассировки
— Освещение
— Схема расчета интенсивности. Параметры, задающие свойства тел.
Вычисление нормалей
Вычисление отраженного луча
Вычисление преломленного луча
Вычисление точки пересечения с примитивом
Описание типов данных. Структура программы
Краткое описание структур и классов
2. Технологическая часть
Выбор языка программирования
Описание интерфейса программы
3. Исследовательская часть
Зависимость времени построения от глубины рекурсии
Зависимость времени построения от количества источников
Выводы по результатам исследований
Заключение
Список литературы
Введение
Эта программа посвященагенерации реалистичных изображений, в частности – реалистичному изображениюстекла.
Существует несколькометодов генерации реалистичных изображений, таких как прямая трассировка лучей(трассировка фотонов), обратная трассировка лучей, radiosity.
Методы трассировки лучейна сегодняшний день считаются наиболее мощными и универсальными методамисоздания реалистичных изображений. Известно много примеров реализацииалгоритмов трассировки для качественного отображения самых сложных трехмерныхсцен. Можно отметить, что универсальность методов трассировки в значительнойстепени обусловлена тем, что в их основе лежат простые и ясные понятия,отражающие наш опыт восприятия окружающего мира.
Окружающие нас объектыобладают по отношению к свету такими свойствами:
— излучают;
— отражают и поглощают;
— пропускают сквозь себя.
Каждое из этих свойствможно описать некоторым набором характеристик.
Излучение можноохарактеризовать интенсивностью и спектром.
Свойство отражения(поглощения) можно описать характеристиками диффузного рассеивания изеркального отражения. Прозрачность можно описать ослаблением интенсивности ипреломлением.
Из точек поверхности(объема) излучающих объектов исходят лучи света. Можно назвать такие лучипервичными – они освещают все остальное. От источников излучения исходит поразличным направлениям бесчисленное множество первичных лучей. Некоторые лучиуходят в свободное пространство, а некоторые попадают на другие объекты. Еслилуч попадает в прозрачный объект, то, преломляясь, он идет дальше, при этомнекоторая часть световой энергии поглощается.
В результате действия наобъекты первичных лучей возникают вторичные лучи. Некоторые из них попадают надругие объекты. Так, многократно отражаясь и преломляясь, отдельные световыелучи приходят в точку наблюдения. Таким образом, изображение сцены формируетсянекоторым множеством световых лучей.
Цвет отдельных точекизображения определяется спектром и интенсивностью первичных лучей источниковизлучения, а также поглощением световой энергии в объектах, встретившихся напути соответствующих лучей.
Непосредственнаяреализация данной лучевой модели формирования изображения представляетсязатруднительной. Можно попробовать построить алгоритм построения изображения указаннымспособом. В таком алгоритме необходимо предусмотреть перебор всех первичныхлучей и определить те из них, которые попадают в объекты и в камеру. Затемвыполнить перебор всех вторичных лучей, и также учесть только те, которыепопадают в объекты и в камеру. И так далее. Такой алгоритм называется прямойтрассировкой лучей. Главный недостаток этого метода – много лишних операций,связанных с расчетом лучей, которые затем не используются.
Обратная трассировкалучей.
Именно этому методугенерации реалистичных изображений посвящена эта работа.
Метод обратнойтрассировки лучей позволяет значительно сократить перебор световых лучей. Методразработан в 80-х годах, основополагающими считаются работы Уиттеда и Кэя.Согласно этому методу отслеживание лучей производится не от источников света, ав обратном направлении – от точки наблюдения. Так учитываются только те лучи,которые вносят вклад в формирование изображения.
Плоскость проецированияразбита на множество пикселов. Выберем центральную проекцию с центром схода нанекотором расстоянии от плоскости проецирования. Проведем прямую линию изцентра схода через середину пиксела плоскости проецирования. Это будетпервичный луч обратной трассировки. Если этот луч попадет в один или несколькообъектов сцены, то выбираем ближайшую точку пересечения. Для определения цветапиксела изображения нужно учитывать свойства объекта, а также то, какоесветовое излучение приходится на соответствующую точку объекта.
Если объект зеркальный(хотя бы частично), то строим вторичный луч – луч падения, считая лучомотражения предыдущий, первичный трассируемый луч. Для идеального зеркаладостаточно затем проследить лишь очередную точку пересечения вторичного луча снекоторым объектом. У идеального зеркала идеально ровная отполированная поверхность,поэтому одному отраженному лучу соответствует только один падающий луч. Зеркаломожет быть затемненным, то есть поглощать часть световой энергии, но все равноостается правило: один луч падает – один отражается.
Если объект прозрачный,то необходимо построить новый луч, такой, который при преломлении давал быпредыдущий трассируемый луч.
Для диффузного отраженияинтенсивность отраженного света, как известно, пропорциональна косинусу угламежду вектором луча от источника света и нормалью.Когда выясняется, что текущийлуч обратной трассировки не пересекает какой-либо объект, а уходит в свободноепространство, то на этом трассировка для этого луча заканчивается.
При практическойреализации метода обратной трассировки вводят ограничения. Некоторые из нихнеобходимы, чтобы можно было в принципе решить задачу синтеза изображения, анекоторые ограничения позволяют значительно повысить быстродействиетрассировки.
Ограничения приреализации трассировки.
1. Среди всех типов объектов выделимнекоторые, которые назовем источниками света. Источники света могут толькоизлучать свет, но не могут его отражать или преломлять. Будем рассматриватьтолько точечные источники света.
2. Свойства отражающих поверхностейописываются суммой двух составляющих – диффузной и зеркальной.
3. В свою очередь, зеркальность такжеописывается двумя составляющими. Первая (reflection) учитывает отражение от другихобъектов, не являющихся источниками света. Строится только один зеркальноотраженный луч r для дальнейшейтрассировки. Вторая компонента (specular) означает световые блики от источников света. Для этого направляютсялучи на все источники света и определяются углы, образуемые этими лучами сзеркально отраженным лучом обратной трассировки (r). При зеркальном отражении цвет точки поверхностиопределяется собственным цветом того, что отражается.
4. При диффузном отражении учитываютсятолько лучи от источников света. Лучи от зеркально отражающих поверхностейИГНОРИРУЮТСЯ. Если луч, направленный на данный источник света, закрываетсядругим объектом, значит, данная точка объекта находится в тени. При диффузномотражении цвет освещенной точки поверхности определяется собственным цветомповерхности и цветом источников света.
5. Для прозрачных (transparent) объектов не учитывается зависимостькоэффициента преломления от длины волны. (Иногда прозрачность вообще моделируютбез преломления, то есть направление преломленного луча t совпадает с направлением падающеголуча.)
6. Для учета освещенности объектовсветом, рассеянным другими объектами, вводится фоновая составляющая (ambient).
7. Для завершения трассировки вводитсяограничение количества итераций (глубины рекурсии).
RADIOSITY(ИЗЛУЧАТЕЛЬНОСТЬ).
Кроме вышеперечисленныхметодов генерации реалистичных изображений существует еще один метод. Онназывается radiosity. Этот метод рассматриваетраспространение в пространстве световых волн. Это более сложный метод, болееточно учитывающий законы распространения световой энергии и требующий большихзатрат времени и аппаратных ресурсов. С помощью этого метода реализуются нетолько такие явления, как зеркальное отражение и преломление, но и болеесложные явления, например, диффузное отражение и диффузное преломление.
Сцену можно представитькак набор поверхностей, обменивающихся световой энергией. Большинство реальныхповерхностей является диффузными отражателями, когда падающий луч отражаетсяили рассеивается во всех направлениях полусферы, находящейся над отражающейповерхностью.
Особый здесь случай — отражение Ламберта (идеальная диффузия). Метод излучательности описывает балансэнергетического равновесия в замкнутой системе.
Предполагается, чтоповерхности идеально диффузны, т.е. после отражения падающий луч пропадает.Излучательность отдельной поверхности включает самоизлучение и отраженный илипропущенный свет.
Выводы по методуобратной трассировки.
Положительные черты:
1. Универсальность метода, егоприменимость для синтеза изображений достаточно сложных пространственных схем.Воплощает многие законы геометрической оптики. Просто реализуются разнообразныепроекции.
2. Даже усеченные варианты данногометода позволяют получить достаточно реалистичные изображения. Например, еслиограничиться только первичными лучами (из точки проецирования), то это даетудаление невидимых точек. Трассировка уже одного-двух вторичных лучей даеттени, зеркальность прозрачность.
3. Все преобразования координат линейны,поэтому достаточно просто работать с текстурами.
Недостатки:
1. Проблемы с моделированием диффузногоотражения и преломления.
2. Для каждой точки изображениянеобходимо выполнять много вычислительных операций. Трассировка относится кчислу самых медленных алгоритмов синтеза изображений.
/>2.Конструкторская часть Алгоритмы Обратная трассировкалучей
/>
Рис. 2.1.1. Блок-схема рекуррентногоалгоритма обратной трассировки лучей.
В этой программе алгоритмобратной трассировки реализован рекуррентным образом. Функция расчетаинтенсивности первичного луча рекуррентно вызывает саму себя для нахожденияинтенсивностей отраженного и преломленного лучей.
Алгоритм:
Для расчета цвета каждогопиксела буфера кадра выполняются следующие действия:
1. Найти координатыпиксела в мировой системе координат.
2. Найти координатыпервичного луча.
3. Запуск функциивычисления интенсивности первичного луча.
4. Найти пересечения лучасо всеми примитивами сцены и выбрать ближайшее.
5. Если пересечение ненайдено, значит, луч ушел в свободное пространство.
Для расчета цветапринимаем полную интенсивность равной фоновой интенсивности. Перейти на шаг 12.Если пересечение найдено, перейти на шаг 6.
6. Рассчитываем«локальную» интенсивность цвета объекта, которому принадлежит точкапересечения. Под «локальной» интенсивностью понимается интенсивность с учетоминтенсивности диффузно отраженного света и интенсивность бликов.
7. Если материал отражаетсвет только диффузно, то считаем интенсивности отраженного и преломленногосвета нулевыми. Перейти на шаг 12. Иначе перейти на шаг 8.
8. Если достигнутамаксимальная глубина рекурсии, то принять интенсивности отраженного ипреломленного света нулевыми. Перейти на шаг 12. Иначе перейти на шаг 9.
9. Вычислить векторотраженного луча. Запуск рекурсии для нахождения интенсивности отраженноголуча.
10. Вычислить векторпреломленного луча. Запуск рекурсии для нахождения интенсивности преломленноголуча.
11. Вычисление полнойинтенсивности цвета. Полная интенсивность включает в себя интенсивностьрассеянного света, локальную интенсивность и интенсивности отраженного ипреломленного лучей.
12. Возврат в точкувызова функции вычисления интенсивности луча.
Если шел расчетпервичного луча, то в буфер кадра помещается пиксел вычисленного цвета.Переходим к расчету следующего пиксела буфера кадра Если шел расчет отраженного(преломленного) луча, то вычисленная интенсивность будет принята какинтенсивность отраженного (преломленного) луча на предыдущем шаге рекурсии.
Построение теней
СПЛОШНЫЕ ТЕНИ
Для построения сплошныхтеней в алгоритме трассировки на этапе вычисления «локальной» интенсивностицвета в точке объекта проверяется «видимость» каждого источника света из этойточки.
/>
Принцип работы алгоритма.
1. Из проверяемой точки строится луч, направленныйна источник света.
2. Производится поиск пересечений этоголуча с примитивами сцены между проверяемой точкой и источником.
3. Если найдено хотя бы однопересечение, то проверяемая точка находится в тени. При расчете ее цветаисточник, для которого проводилась проверка, не учитывается.
4. Если пересечений не найдено, точка нев тени. При расчете ее цвета учитываем проверяемый источник.
Такой метод нахождениятеней дает приемлемый результат до тех пор, пока на сцене нет прозрачныхобъектов. Однако сплошная черная тень от стакана выглядит не реалистично.Стекло частично пропускает свет, поэтому интенсивность заслоненного источникадолжна учитываться при подсчете интенсивности света в точке объекта, но онадолжна ослабляться при проходе света сквозь стекло.
РЕАЛИСТИЧНЫЕ ТЕНИ
В этой программепредлагается способ построения теней, хотя и не соответствующий физике процессаобразования тени, но, тем не менее, дающий более реалистичные результаты, чемобыкновенные сплошные тени. В этом алгоритме ослабление интенсивности света,дошедшего до проверяемой точки, привязано к расстоянию, пройденному светом вматериале (в стекле). При этом преломлением света полностью пренебрегаем.
/>
Алгоритм работаетследующим образом.
1. Из проверяемой точки строится луч,направленный на источник света.
2. Находятся ВСЕ пересечения этого лучас примитивами сцены между проверяемой точкой и источником и сохраняются вмассив пересечений. Первым элементом в массив заносится 0 (сама точка, для которой истроится тень). Одновременно с этимформируется массив, в котором хранятся данные о том, какому объекту сценыпринадлежит найденная точка пересечения.
3. Массив пересечений сортируется повозрастанию расстояния от проверяемой точки до точки пересечения. При этомабсолютно аналогичные операции проводятся и со вторым массивом.
4. Если в массив не была добавлена ниодна точка кроме начальной, то проверяемая точка не затенена. Берется полнаяинтенсивность источника. В противном случае начинаем проход массива со второйточки по всем точкам.
5. Если объект, которому принадлежиттекущая точка пересечения, абсолютно непрозрачный, то имеет место сплошнаятень, цикл прерываем. Иначе проверяем, входит луч в объект или выходит из него.Если входит – переход в следующей точке.
6. Если выходит, то вычисляем расстояниеот предыдущей точки до текущей. Это будет расстояние, пройденное светом внутриобъекта. В зависимости этого расстояния ослабляем интенсивность источника.Переходим к следующей точке.
Надо заметить, что различныепрозрачные объекты могут отбрасывать разную тень даже при одинаковомрасстоянии, пройденном светом в объекте. Так цветное стекло должно отбрасыватьболее темную тень, чем прозрачное. Для учета этого факта для каждого объектавведен специальный параметр — это расстояние, пройденное светом внутри объектадо полного затухания. Чем больше этот параметр, тем светлее тень, отбрасываемаяобъектом.
Математическиеи физические предпосылки алгоритма обратной трассировки лучей Освещение
Согласно модели Уиттедацвет некоторой точки объекта определяется суммарной интенсивностью
I(l)=Ka*Ia(l)C(l)+ Kd*Id(l)*C(l) +Ks*Is(l) + Kr*Ir(l) +Kt*It(l),
где l – длина волны, C(l) – заданный исходный цвет точки объекта, Ka, Kd, Ks, Kr и Kt – коэффициенты, учитывающие свойства конкретного объектапараметрами фоновой интенсивности, диффузного рассеивания, зеркальности,отражения и прозрачности.
Ia – интенсивность фоновой подсветки,
Id – интенсивность, учитываемая длядиффузного рассеивания,
Is – интенсивность, учитываемая длязеркальности,
Ir – интенсивность излучения, пришедшаяпо отраженному лучу,
It – интенсивность излучения, пришедшаяпо преломленному лучу.
Интенсивность фоновойподсветки (Ia) для некоторого объекта обычно константа.Запишем формулы для остальных интенсивностей.
Для диффузного отражения:
Id=∑I(l)cosӨ,
где I(l) – интенсивность излучения i-го источника света, Ө — угол между нормалью к поверхности объекта и направлением на i-й источник света.
Для зеркальности:
Id=∑I(l)cosα,
где p – показатель степени от единицы донескольких сотен (согласно модели Фонга), α –угол между отраженным лучом (обратной трассировки) и направлением на i-й источник света.
Надо заметить, что вмодели Уиттеда в чистом виде есть один существенный недостаток. Дело в том, чтодоля световой энергии отраженной от поверхности объекта зависит от угла паденияи преломления. Например, если смотреть вдоль поверхности стекла, то доляотраженного света повысится, а преломленного понизится. Но в модели Уиттедакоэффициенты, отражающие доли интенсивности отраженного и преломленного света всуммарной интенсивности точки поверхности объекта задаются константами (независят от угла). В большинстве случаев это дает приемлемый результат. Но примоделировании стекла мы встречаемся с эффектом полного внутреннего отражения.Некоторые лучи света не могут выйти из толщи стекла за заданное фиксированноечисло итераций. В результате этого по краям стакана возникает четкая чернаяполоса. Если учесть зависимость интенсивности отраженного и преломленного светаот углов падения и преломления, то эффект будет намного более реалистичным.Края черной области размоются.
Для вычислениякоэффициента при интенсивности отраженного луча используется следующая формула:
r = 0.5(cos α — Ncos β)2 /(cos α + Ncos β)2 +0.5(Ncos α – cos β)2 /(Ncos α + cos β)2,
где α – угол падения луча, β – угол преломления луча, N – относительный показатель преломлениядвух сред.
Коэффициент приинтенсивности преломленного луча вычисляется по формуле:
t = 1 – r.
Схема рассчетаинтенсивности.параметры, задающие свойства тел
В связи с недостаткамимодели Уиттеда в этой программе предлагается следующая система вычисленияинтенсивности света в точке.
Интенсивность светаскладывается из интенсивности фоновой подсветки сцены, интенсивности диффузноотраженного света источников, интенсивности бликов от источников («локальные»характеристики освещенности), интенсивности зеркально отраженного луча иинтенсивности преломленного луча, если таковые имеются.
Интенсивность фоновойподсветки (IA) задается некоторой константой.
Интенсивность диффузноотраженного света (ID) вычисляетсяпо классическому «закону косинуса».
ID = IL cos α,
где IL – интенсивность источника света, α – угол между нормалью к поверхностии направлением на источник.
В случае освещения сценынесколькими источниками Id вычисляется для каждого из них и затем суммируются.
IDi=Σ ILi cos αi.
Интенсивность блика отисточника (IS) вычисляется в соответствии с модельюФонга.
S = IL cosp β,
где IL – интенсивность источника света(0
Как и при вычислении IDв случае освещения сцены несколькимиисточниками IS вычисляется отдельно для каждогоисточника, а затем результаты суммируются.
Si =Σ ILicosp βi.
Интенсивности зеркальноотраженного (IR) и преломленного (IT) света рассчитываются дляотраженного и преломленного лучей на следующем шаге рекурсии. Если достигнутпредел глубины рекурсии, то эти интенсивности берутся нулевыми. От интенсивностиIR берется r процентов, а от IT – t = 1– r (см. предыдущий раздел).
Кроме того, вводятсяследующие коэффициенты: KD –коэффициент диффузного отражения поверхности, KS – коэффициент блика.
KD – этот коэффициент является характеристикой неровностиотражающей поверхности. Чем больше неровность поверхности, тем меньше светаотражается от неё зеркально и меньше света она пропускает, и соответственнобольше света она отражает диффузно. 0
При KD= 0 — весь свет, падающий на поверхность,отражается и преломляется. KD=1 — весь свет отражается диффузно. На этот коэффициент умножаются интенсивностьдиффузно отраженного света и интенсивность фоновой подсветки. Интенсивностизеркально отраженного и преломленного света умножаются на (1 – KD).
KS –этот коэффициент отвечает за яркость блика от источника. 0
Такимобразом, окончательная формула для расчета интенсивности объекта в какой-либоточке будет выглядеть следующим образом:
I = IAKD + Σ(ILiKDcosαi + ILiKScospβi) + (1 – KD )(IRr + IT(1– r)).
Приэтом надо заметить, что итоговая интенсивность не должна получиться большеединицы. Если такое происходит, то эта точка изображения будет засвеченной. Ееинтенсивность надо сбросить на единицу.
Дляполучения цветного изображения необходимо провести расчеты отдельно для красной,зеленой и синей компоненты света. Цвет пиксела изображения будет вычисляться путемумножения каждой компоненты интенсивности на число, определяющее максимальноеколичество градаций интенсивности изображения. Для 32-битного изображения оноравно 255 на каждый из цветов(R,G,B).
R = 255*IR,
G = 255*IG,
B = 255*IB.
ЗдесьIR(не путать с интенсивностью зеркальноотраженного света), IG, IB – интенсивности трех компонент светав точке, полученная по формуле, указанной выше.
КоэффициентыKD, KS, p – это индивидуальные характеристики объекта, отражающие егосвойства. Кроме этого имеется еще один коэффициент – абсолютный показательпреломления n. n = c / v, где c – скорость света в вакууме, v – скорость света в среде (внутри объекта). Для абсолютнонепрозрачных тел этот коэффициент равен ∞ (т.к. скорость света внутритела нулевая). В программе для задания абсолютно непрозрачного тела необходимопоставить этот коэффициент >> 1 (порядка 10 000). При этом долязеркально отраженного света rбудет стремиться к единице, а преломленного, соответственно, к нулю.
Вычисление нормалей
В алгоритме трассировкинормали к объектам необходимы для вычисления отраженного и преломленного лучей,а также для определения освещенности согласно модели Фонга.
В этой программеприсутствуют три вида примитивов, из которых строится сцена. Это полигон(треугольник), эллипсоид и параболоид. Последние два введены для болеереалистичной имитации стакана (его можно было бы построить и из полигонов, номодель получилась бы более грубая).
Вычисление нормали кполигону (Треугольнику).
Вычисление нормали ктреугольнику сводится к операции векторного умножения. Пусть задан треугольник ABC координатами трех своих вершин: XA, YA, ZA, XB, YB, ZB, XC, YC, ZC.
Вычислим координаты двухвекторов, например AB и AC:
XAB = XB – XA,
YAB = XB – XA,
ZAB= XB – XA,
XAC= XC – XA,
YAC= XC – XA,
ZAC= XC – XA.
Координаты векторанормали будут вычисляться по формулам:
Xn= YABZAC — YACZAB,
Yn= XABZAC — XACZAB,
Zn= XABYAC — XACYAB.
Нет необходимостивычислять координаты вектора нормали к треугольнику каждый раз в телетрассировки, так как в любой точке треугольника нормали одинаковые. Достаточноих посчитать один раз в инициализирующей части программы и сохранить. Приповороте треугольника надо поворачивать и его нормаль.
Вычисление нормали кповерхности второго порядка.
Поверхность второгопорядка задается в общем случае уравнением вида: Q(x,y,z) = a1x2 + a2y2 + a3z2 + b1yz + b2xz + b3xy + c1x +c2y +c3z + d =0.
Но мы будем использоватьдругую форму записи. Так уравнение эллипсоида будет выглядеть следующимобразом:
(x-x0)2/A2 + (y-y0)2/B2 + (z-z0)2 /C2 = 1,
где x0, y0, z0 – координаты центра эллипсоида, A, B, C – длины полуосей эллипсоида. Уравнение параболоида:
(x-x0)2/A2 + (y-y0)2/B2 — (z-z0)2 /C2 = 1,
где x0, y0, z0 – координаты центра параболоида, A, B, C – длины полуосей параболоида. Осьпараболоида расположена вдоль оси Oz мировой системы координат.
Для вычисления координатвектора нормали необходимо вычислить частные производные по x, y, z.
Координаты векторанормали эллипсоида:
Xn = 2(x-x0)/A2,
Yn= 2(y-y0)/B2,
Zn= 2(z-z0)/С2.
Направление вектора неизменится, если все его координаты разделить на 2:
Xn= (x-x0)/A2,
Yn= (y-y0)/B2,
Zn = (z-z0)/С2.
Координаты векторанормали параболоида вычисляются аналогично:
Xn= (x-x0)/A2,
Yn= (y-y0)/B2,
Zn = – (z-z0)/С2.
Нормаль для поверхностивторого порядка придется вычислять непосредственно в теле трассировки, так какв разных точках фигуры нормали разные.Вычисление отраженноголуча
Пусть задан вектор падающеголуча S, а также известен вектор нормали N. Требуется найти вектор отраженноголуча R.
Рассмотрим единичныевекторы R1, S1и N1. Поскольку векторы нормали, падающего луча и отраженноголуча находятся в одной плоскости, то можно записать R1 + S1 = N`, где N` — это вектор, соответствующий диагонали ромба и совпадающий по направлению снормалью. Длина вектора N`равна 2cosθ. Так как вектор N` по направлению совпадает с N1, то
N` = N`2cosθ.
Отсюда найдем единичныйвектор отраженного луча:
R1= N1 2cosθ – S1 = N/|N| 2cosθ – S/|S|.
/>
Найдем cosθ. Это можно сделать, используяскалярное произведение векторов N и S:
cosθ = N*S/(|N|*|S|).
Полагая, что искомыйвектор отраженного луча будет иметь такую же длину, что и вектор падающеголуча, то есть R = |S| R1, получим
R = N 2NS/|N|2 – S.
Это решение в векторнойформе. Запишем координаты вектора:
xR = 2xN(xNxS+yNyS+zNzS)/(xN2+yN2+zN2) – xS,
yR = 2yN(xNxS+yNyS+zNzS)/(xN2+yN2+zN2) – yS,
zR = 2zN(xNxS+yNyS+zNzS)/(xN2+yN2+zN2) – zS.Вычислениепреломленного луча
Пусть даны два единичныхвектора: S1 – вектор падающего луча, и N1 – вектор нормали к границе разделадвух сред. Также должны быть известны два коэффициента преломления для данныхсред – n1 и n2 (или их отношение).
Требуется найти единичныйвектор преломленного луча T1. Для решения выполним некоторыегеометрические построения.
Искомый вектор T1 равен сумме двух векторов:
T1 = NT + B.
Найдем вначале вектор NT. Он противоположен по направлениювектору нормали, а его длина равна |T1| cos α2 = cos α2 (поскольку T1 –единичный). Таким образом, NT = -N1 cos α2. Необходимо определить cos α2. Запишем закон преломления n1 sin α1 = n2 sin α2 в виде:
sin α2= n sin α1,
где n = n1 / n2.
Воспользуемся тождеством cos2α + sin2α = 1. Значение cos α1 можно выразить через скалярное произведение единичныхвекторов S1 и N1, то есть cos α1 = S1N1. Тогда мы можем записать такоевыражение для вектора NT:
NT = -N1√1+n2((S1N1)2 – 1).
Осталось найти выражениедля вектора B. Он располагается на одной прямой свектором A, причем A = S1 – NS. Учитывая, что NS равен N1 cosα1, то A = S1 – N1 cosα1. Так как cosα1 = S1N1, то A = S1 – N1 (S1N1).
Поскольку длина вектора A равна sin α1, а длина вектора B равна sin α2,
|B|/|A| = sin α2/ sin α1 = n2/n1 = n,
откуда |B| = n |A|. Учитываявзаимное расположение векторов A и B, получим
B = –nA =n(N1(S1N1) – S1).
Теперь мы можем записатьискомое выражение для единичного вектора луча преломления T1: Вычисление точки пересечения спримитивами
В алгоритме трассировкидля построения изображения необходимо вычислять точки пересечения лучей спримитивами сцены. Луч задается параметрическим уравнением прямой. Любая точкалуча удовлетворяет уравнению
R = A + Vt,
где R – радиус вектор произвольной точки,принадлежащей лучу, A – радиус- векторначальной точки луча, V –направляющий вектор луча, t –параметр.Если направляющий вектор V нормализовать, то параметр t будет численно равен расстоянию от начальной точки луча A до точки R.
Можно записать этоуравнение в координатном виде:
x = x1+ at,
y = y1+ bt,
z = z1+ ct.
Здесь x1, y1, z1 –координаты начальной точки луча в прямоугольной декартовой мировой системекоординат, a,b,c – координатынаправляющего вектора луча.
Вычисление точкипересечения луча с поверхностью второго порядка.
Для нахождения точкипересечения луча, заданного уравнениями (2) с поверхностью второго порядка,заданной уравнениями (2.2.2.3) или (2.2.2.4):
(x–x0)2/A2+ (y–y0)2/B2 + (z–z0)2 /C2= 1 (эллипсоид)
(x–x0)2/A2 + (y–y0)2/B2 – (z–z0)2 /C2 = 1 (параболоид),
нужно подставить вуравнение поверхности второго порядка вместо x, y и z соответствующие уравнения луча. Врезультате этого после раскрытия всех скобок и приведения подобных мы получимквадратное уравнение относительно параметра t. Если дискриминант квадратного уравнения меньше нуля, то лучи поверхность второго порядка общих точек пересечения не имеют. В противномслучае можно будет вычислить два значения параметра t. Дискриминант может быть равен нулю – это соответствуетпредельному случаю касания луча поверхности, и мы получим два совпадающихзначения параметра t.
Для нахождения координатточек пересечения луча и поверхности достаточно подставить найденные значенияпараметра t в уравнения луча (2).
В программе принахождении двух пересечений для визуализации выбирается ближнее из них. Ближнеепересечение определяется путем сравнения найденных параметров t. Ближе к точке наблюдения находитсято пересечение, которому соответствует меньший параметр t. Тут надо заметить, что в результатерешения квадратного уравнения одно или оба значения параметра t могут получиться отрицательными. Этоозначает, что точка пересечения лежит «сзади» относительно точки начала луча,на половине прямой, находящейся «по нашу сторону» относительно картиннойплоскости. Такие точки при поиске пересечения отбрасываются.
Кроме того, в программедля каждой фигуры введены верхняя и нижняя секущие плоскости. Отображаетсятолько часть фигуры, лежащая между ними.
Для этого посленахождения точки пересечения анализируется ее z-координата.
Вычисление точкипересечения луча с полигоном (Треугольником).
Для вычисления точкипересечения луча, заданного уравнениями (2) необходимо сначала определить точкупересечения этого луча с плоскостью, содержащей этот треугольник.
Уравнение плоскостивыглядит следующим образом:
Q(x, y, z) =Ax + By + Cz +D = 0.
Здесь коэффициенты A, B, C совпадают скоординатами нормали к этой плоскости. Координаты нормали плоскости совпадают скоординатами нормали треугольника, которые мы посчитали на этапе загрузки сцены.
Для нахождения свободногочлена D необходимо подставить координаты любойточки треугольника, например, одной из вершин.
D = –Ax –By – Cz.
По ходу выполненияпрограммы значение D меняться не будет, поэтому его целесообразнопосчитать при инициализации сцены и хранить, как и координаты нормали.Пересчитывать его необходимо только при изменении положения треугольника.
Теперь для нахожденияточки пересечения подставим уравнения луча (2) в уравнение плоскости.
A (x1+ at) + B (y1 + bt) + C (z1 + ct) + D = 0
t = – (Ax1+ By1 + Cz1 + D) / (Aa + Bb + Cc)
Если знаменатель этойдроби равен нулю, значит луч параллелен плоскости, в которой лежит треугольник.Точки пересечения нет.
Для нахождения координатточки пересечения надо подставить найденное значение параметра t в уравнения луча (2). Назовем точкупересечения D. Мы получим координаты xD, yD, zD.
Теперь необходимоопределить, попала ли точка Dвнутрь треугольника. Найдем координаты векторов AB, BC, CA (A, B, C – вершины треугольника) и координатывекторов AD, BD, CD. Затем найдемтри векторных произведения:
nA = AB x AD,
nB = BC x BD,
nC = CA x CD.
Эти вектора будутколлинеарны. Если все три вектора сонаправлены, то точка D лежит внутри треугольника.Сонаправленность определяется равенству знаков соответствующих координат всехтрех векторов.
Операцию проверкипринадлежности точки Dтреугольнику ABC можно ускорить. Если ортогонально спроецироватьтреугольник ABC и точку D на одну из плоскостей xOy, yOzили xOz, то попадание проекции точки впроекцию треугольника будет означить попадание самой точки в треугольник(конечно же, если уже известно, что точка D лежит в плоскости, содержащей треугольник ABC). При этом число операций заметно сокращается.Так для поиска координат всех векторов нужно искать по две координаты на каждыйвектор, а при поиске векторных произведений нужно искать только одну координату(остальные равны нулю).
Для проверкисонаправленности векторов, полученных при вычислении векторного произведениянужно проверить знаки этой единственной координаты для всех трех векторов. Есливсе знаки больше нуля, или меньше нуля, то вектора сонаправлены. Равенство нулюодного из векторных произведений соответствует случаю, когда точка D попадает на прямую, содержащую однуиз сторон треугольника.
Кроме того, передвычислениями векторов и векторных произведений можно провести простойгабаритный тест. Если проекция точки D лежит правее, левее, выше или ниже каждой из проекций вершин треугольника,то она не может лежать внутри.
Остается добавить, чтодля проецирования лучше выбирать ту из плоскостей, площадь проекциитреугольника на которую больше. При таком условии исключается случайпроецирования треугольника в отрезок (при условии, что проверяемый треугольникне вырожден в отрезок). Кроме того, при увеличении площади проекции уменьшаетсявероятность ошибки. Для определения такой плоскости проецирования достаточнопроверить три координаты нормали треугольника. Если z-координата нормали больше (по абсолютному значению) x и y, то проецировать надо на плоскость xOy. Если yбольше чем x и z, то проецируем на xOz. В оставшемся случае – на yOz./>Описаниетипов данных. Структура программы
Список модулей:
TTex.h - описаниеструктуры TTex
TSurfTex.h - описание структур TPlaneTex и TEllipsoidTex
TPoint.h - описание структур TPoint2d и TPoint3d
TRGBColor.h - описаниестрактуры TRGBColor
TLamp.h - описание класса TLamp
TCam.h - описание класса TCam
TPrimitive.h - описаниекласса TPrimitive
TFrstSurface.h - описание класса TFrstSurface
TScndSurface.h - описание класса TScndSurface
TTriangle.h - описание класса TTriangle
TEllipsoid.h - описаниекласса TEllipsoid
TParaboloid.h - описание класса TParaboloid
TScene.h - описание класса TScene
TTracer.h - описание класса TTracer
Модули реализующие, интерфейс программы:
_AboutUnit.h - модульформы «О программе»
_ZoomUnit.h - модульформы «Лупа»
_Options.h - модуль формы«Опции»
_ExtraGlassOptions.h - модуль формы«Свойства стекла»
_ExtraTableOptions.h - модуль формы «Свойства стола»
_ExtraCamOptions.h - модуль формы«Свойства камеры»
_MainUnit.h - модульглавной формы программы/>
Рис.2.3.1. Схема связеймежду модулями программы.
/>
Рис.2.3.2. Схема наследования примитивов
Краткое описание структур и классов программы
struct TPoint3d –структура, описывающая точку в мировой системе координат
struct TPoint2d –структура, описывающая точку на плоскости (в текстуре) с целочисленнымикоординатами
struct TRGBColor – структура, описывающая цвет потрем составляющим (RGB)
struct TTex – структура, описывающая текстуру – содержит адресмассива пикселей и его размеры
struct TPlaneTex – структура, описывающая привязкутекстуры к плоскости.
Содержит три точки, к которымпривязывается текстура
class TLamp – класс, описывающий источник освещения.
Содержит объект TPoint3d coord с координатами источника и три переменные типа float (Ir, Ig, Ib) для хранения интенсивности трехкомпонент света.
class TCam – класс, описывающий камеру.
Содержит два угла (a, b), указывающих направление зрения камеры, точку, на которуюнаправлена камера (viewP) и расстояниеот камеры до этой точки (r).
class TPrimitive – абстрактный класс примитива. Отнего наследуются поверхности первого и второго порядка.
class TFrstSurface – абстрактный класс поверхностипервого порядка. От него наследуется класс треугольника.
class TScndSurface – абстрактный класс поверхностивторого порядка. От него наследуются классы эллипсоида и параболоида.
class TTriangle – класс треугольника. Содержит тривершины треугольника и его нормаль
class TParaboloid – класс параболоида.
class TEllipsoid – класс эллипсоида.
class TScene – класс сцены. Содержит информацию о всех примитивах,источниках и камере.
class TTracer – класс, отвечающий за построения изображения.Содержит буфер (buffer) разметом400x400 пикселей, в котором формируетсяизображение сцены. Перед генерацией необходимо вызвать функцию
selectScene передав ей в качестве параметрауказатель на сцену, которуюнеобходимо сгенерировать. Для генерации вызвать функциюrender.
Все классы – потомки TPrimitiveпредоставляют следующие функции:
float getT(TPoint3d p0, TPoint3d viewDir) – возвращает расстояние от точкиначала(p0) луча viewDir до ближайшей точки пересечения с примитивом void getTArr(float*arr, int& n, TPoint3d p0, TPoint3d viewDir) – заполняет массив arr расстояниями от точки начала(p0) луча viewDir до ближайшей всех точек пересечения с примитивом void getNormal(TPoint3d&n, const TPoint3d&p) – возвращает координаты векторанормали к примитиву в точке p void getColor(TRGBColor& c, const TPoint3d& p) — возвращаетцвет примитива точке p (с учетом текстуры).
2.Технологическая часть
Выбор языкапрограммирования
При разработке программыбыл использован язык программирования высокого уровня C++ в составе среды визуального программирования CBuilder6.
Данный язык был выбранблагодаря тому, что он предоставляет максимально удобные средства по работе соперативной памятью, позволяет реализовывать алгоритмы более эффективно, посравнению с другими высокоуровневыми языками. Программы, написанные на C++, работают быстрее и занимаютменьше места на диске.
Кроме того, средавизуального программирования CBuilder6 предоставляет большое количество стандартных визуальных компонентов длясоздания интерфейса, и ряд библиотек с различными часто используемыми полезнымифункциями.Описаниеинтерфейса программы
/>
Главное меню программы:
— Файл
— Сохранить картинку –записать в файлсодержимое окна вывода изображения
— Выход – выход изпрограммы
— Настройки
— Опции – открытие формы «Опции»
— Инструменты
— Лупа – открытие формы «Лупа»
— Генерировать – запуск генерации изображения
— Помощь
— О программе – сведения о разработчике и версияпрограммы
Для генерации изображениянажмите кнопку ГЕНЕРИРОВАТЬ или выберите аналогичный пункт в главном меню.
В нижней строке во времягенерации изображения выдается сообщение ИДЕТ ГЕНЕРАЦИЯ ИЗОБРАЖЕНИЯ. Позавершении генерации здесь будет отображено время, затраченное на генерацию.
/>
На этой вкладке находятсясредства по настройке освещения сцены.
Координаты источника – координаты в мировой системекоординат источника света, выбранного в выпадающем списке.
Интенсивностьисточника – значениятрех компонент интенсивности источника света, выбранного в выпадающем списке.
Фоновая интенсивность – значения трех компонент фоновойинтенсивности.
Кнопка “+” (рядом с выпадающим списком) –добавление нового источника света.
Кнопка “–” (рядом с выпадающим списком)– удаление источника света, выбранного в выпадающем списке.
ФОРМА «ОПЦИИ». ВКЛАДКА «КАМЕРА».
/>
На этой вкладке находятсясредства по настройке опций камеры.
Предосмотр – здесь можно увидеть примерный видизображения до его генерации.
Навигация – настройки положения камеры.
Дополнительно – при нажатии на эту кнопку появляетсяформа Свойства камеры с дополнительными параметрами камеры.
ФОРМА «СВОЙСТВА КАМЕРЫ».
/>
Радиус –расстояние от камеры до точки, накоторую она направлена.
Шаг изменения радиуса – приращение радиуса камеры приоднократном нажатии кнопки “–” на вкладке “Камера” формы “Опции” (илиуменьшение при однократном нажатии кнопки “+”).
ФОРМА «ОПЦИИ». ВКЛАДКА«МАТЕРИАЛЫ».
/>
При нажатии на кнопку«Стекло» отображаются свойства материала стакана.
Цвет – цвет материала стакана.
Коэф. диффузногоотражения –коэффициент KD материала стакана (см. раздел 2.2.1). Коэф. преломления – абсолютный коэффициент преломления материала стакана. Дополнительно – при нажатии на эту кнопку появляется форма Свойствастекла с дополнительными параметрами материала стакана.
ФОРМА «СВОЙСТВА СТЕКЛА».
/>
Коэффициент блика – коэффициент KSматериала стакана (см. раздел 2.2.1). Размытость блика – показатель степени p материала стакана. Расстояниезатухания –максимальное расстояние, которое может пройти свет в материале до полного затухания. При нажатии на кнопку «Стол» отображаются свойства материаластола.
/>
Цвет – цвет материала стола.
Коэф. диффузногоотражения –коэффициент KD материала стола (см. раздел 2.2.1).
Текстура – если галочка установлена, то настоле будет отображаться текстура.
Выбрать текстуру – выбор файла изображения (*.bmp), который будет использоваться кактекстура стола.
Дополнительно – при нажатии на эту кнопкупоявляется форма Свойства стола с дополнительными параметрами материаластола.
ФОРМА «СВОЙСТВА СТОЛА».
/>
Коэффициент блика – коэффициент KSматериала стола (см. раздел 2.2.1).
Размытость блика – показатель степени p материала стола.
Повторения текстуры – сколько раз текстура стола будетповторяться вдоль осей OX и OY.
ФОРМА «ОПЦИИ». ВКЛАДКА«СИСТЕМНЫЕ».
/>
На этой вкладке можнонастраивать алгоритмы, реализованные в программе.
Глубина рекурсии – этот параметрустанавливаетглубину рекурсии в алгоритме трассировки. При бОльших значениях этого параметракачество сгенерированного изображения улучшается.
ВНИМАНИЕ!
Глубина рекурсии СИЛЬНОвлияет на скорость генерации изображения. Не рекомендуется ставить значенияэтого параметра больше 10.
Анитиалиазинг – включение алгоритма сглаживания изображения.
Тип тени – выбор алгоритма построения теней.
Лупа позволяетрассмотреть сгенерированное изображение в увеличенном виде.
Можно менять масштаб увеличениялупы (1:1, 1:2, 1:4, 1:8, 1:10, 1:16) в выпадающем меню.
3.Исследовательская часть
Исследования проводилисьна компьютере со следующей конфигурацией:
CPU AMD Athlon2100+
512 Mb DDRSDRAM
WindowsXPЗависимостьвремени генерации от глубины рекурсии
В этом тестеисследовалась зависимость времени генерации изображения от глубины рекурсии.Исследования проводились для сцены освещенной одним источником света.
T1 – время генерации без тени всекундах.
T2 – время генерации со сплошной теньюв секундах.
T3 – время генерации с реалистичнойтенью в секундах.
N – глубина рекурсии./>/>
Зависимость временигенерации от количества источников/>Анализрезультатов исследований
Из первого исследования видно, что график зависимостивремени генерации изображения от глубины рекурсии по виду совпадает с графикомфункции 2n. Это хорошо соответствует теории, т.к.количество лучей растет с увеличением глубины рекурсии как 2n.
Надо заметить, что для сцен с маленьким количествомполигонов нет необходимости задавать большие значения максимальной глубинырекурсии, т.к. разница в качестве сгенерированного изображения будетнесущественна.
/>Во втором исследовании показано, чтозависимость времени генерации от количества источников света линейна. Изполученных значений можно вычислить время, необходимое для расчета одногоисточника. На машине, на которой проводились исследования, при глубине рекурсии5 это время примерно равно 0,8 секунды.
Заключение
В этой программе былипродемонстрированы результаты роботы алгоритма генерации реалистичныхизображений – обратной трассировки лучей.
Данная реализация демонстрируетвозможности алгоритма строить изображения близкие к фотореалистичным.Трассировка является одним из самых совершенных алгоритмов генерацииреалистичных изображений. Качество получаемого изображения несравнимо лучше,чем качество изображения, полученного с помощью таких алгоритмов, как Z-буфер. Однако требования к вычислительным мощностям,необходимым для генерации одного кадра изображения намного выше, чем в том же Z-буфере. Это делает невозможным применение этого алгоритмадля реализации приложений, где необходима генерация изображений в реальномвремени (3D-игры, различного рода симуляторы). Существуют методыповышения быстродействия алгоритма. Для увеличения скорости генерацииизображения применяют такие средства, как метод порталов и метод оболочек.
Метод порталов подразумеваетделение виртуального пространства сцены на некоторые замкнутые области.Например, разделение дома на комнаты. Двери между комнатами закрыты, и мы неможем видеть объекты в другой комнате. Это значительно сокращает количествопримитивов, с которыми необходимо искать пересечения лучей при трассировке.
В методе оболочек примитивы сценыразделены на некоторые логические объекты, каждый из которых заключен воболочку простого вида (шар, цилиндр, параллелепипед). Перед нахождениемпересечения луча с примитивом проверяется пересечение с оболочкой, содержащейэтот примитив. Оболочки часто делают вложенными (образуется древовиднаяструктура), что заметно ускоряет поиск и отброс тех примитивов, пересечений скоторыми точно не будет.
Но даже со всемиусовершенствованиями на сегодняшний день реализация трассировки в реальномвремени представляется затруднительной. Известны попытки создания 3D-ускорителей с аппаратной поддержкой алгоритма обратнойтрассировки, однако широкого распространения они не получили из-за относительновысокой цены и недостаточного быстродействия (удовлетворительная скоростьпостроения изображения была только для изображения с разрешением 640x480).
Однако вычислительные мощностиперсональных компьютеров растут каждый день. В скором времени должны появитьсямашины, на которых алгоритм трассировки будет работать в реальном времени.Трассировка должна вытеснить другие алгоритмы ввиду явного превосходства вкачестве изображения и универсальности метода.
Список литературы
1. Роджерс Д.Алгоритмические основы машинной графики: пер. с англ.— М.: Мир, 1989.— 512 с.:ил.
2. Порев В. Н.Компьютерная графика. – СПб.: БХВ-Петербург, 2002. – 432 с.: ил.
3. Никулин Е. А.Компьютерная геометрия и алгоритмы машинной графики. СПб.: БХВ-Петербург, 2003. – 560с.: ил.
4. Авдеева С.М.,Куров А.В. Алгоритмы трехмерной машинной графики: Учебное пособие. – М.: Изд-воМГТУ им. Н.Э. Баумана, 1996. – 60 с.: ил.