Алгоритм определения видимых поверхностей путем трассировки лучей | MetodPro.ru

Реклама на сайте

Алгоритм определения видимых поверхностей путем трассировки лучей


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


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

 

Предполагается, что наблюдатель находится на положительной полуоси z- Картинная плоскость, т. е. растр, перпендикулярна оси z. Задача состоит в том, чтобы построить одноточечную центральную проекцию на картинную плоскость.

Рис. 4

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

Чтобы избавиться от ненужного поиска пересечений, производится проверка пересечения луча с объемной оболочкой рассматриваемого объекта. И если луч не пересекает оболочки, то не нужно больше искать пересечений этого объекта с лучом. В качестве оболочки можно использовать прямоугольный параллелепипед или сферу, рис. 5. Факт пересечения трехмерного луча со сферой определяется очень просто. В частности, если расстояние от центра сферической оболочки до луча превосходит радиус этой сферы, то луч не пересекает оболочки. Следовательно, он не может пересечься и с объектом.

 

 

Рис. 5. Объемлющие оболочки

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

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

 

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

  • Подготовка данных для сцены;
  • Создать список объектов, содержащий по меньшей мере следующую информацию:
  • Полное описание объекта: тип, поверхность, характеристики и т. п.
  • Описание сферической оболочки: центр и радиус. Флаг прямоугольной оболочки.  Если этот флаг поднят,  то будет выполнен габаритный тест с прямоугольной оболочкой, если же он опушен, то тест выполняться не будет. Заметим, что габаритный тест необходим не для всех объектов, например для сферы он не нужен.
  • Описание  прямоугольной  оболочки:
  • Для каждого трассируемого луча:
  • Выполнить для каждого объекта трехмерный тест со сферической оболочкой в исходной системе координат. Если луч пересекает эту сферу, то занести объект в список активных объектов.
  • Если список активных объектов пуст, то изобразить данный пиксел с фоновым значением интенсивности и продолжать работу. В противном случае, перенести и повернуть луч так, чтобы он совместился с осью z. Запомнить это комбинированное преобразование.
  • Для каждого объекта из списка активных объектов:
    Если флаг прямоугольной оболочки поднят - преобразовать, используя комбинированное преобразование, эту оболочку в систему координат, в которой находится луч, и выполнить соответствующий тест.
  • Если пересечения с лучом нет, то перейти к следующему объекту.
  • В противном случае преобразовать,  используя комбинированное преобразование, объект в систему координат, в которой находится луч, и определить его пересечения с лучом, если они существуют. Занести все пересечения в список пересечений.
  • Если список пересечений пуст, то изобразить данный пиксел с фоновым значением интенсивности.
  • В противном случае определить Zmax. для списка пересечений.
  • jlВычислить преобразование, обратное комбинированному преобразованию.
  • Используя это обратное преобразование, определить точку пересечения в исходной системе координат.
  • Изобразить данный пиксел, используя атрибуты пересеченного объекта и соответствующую модель освещенности.

 

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



Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем