Программные продукты и системы

В основе всех подходов к построению изображений методами обратной трассировки лучей (ОТЛ) лежит алгоритм Витеда [1], в котором были развиты идеи Аппеля [2], Голдстейна и Нагеля [3]. С момента первых публикаций описания алгоритма ОТЛ прошло более 30 лет, однако он продолжает оставаться в центре внимания, составляя фундаментальную основу математического обеспечения синтеза изображений 3D-объектов. Практика показала, что обратная трассировка дает наиболее реалистичные изображения искусственных объектов, так как алгоритм ОТЛ позволяет непосредственно использовать законы оптики (в том числе законы переноса энергии излучения в различных средах, например, закон Бугера [4]).

Алгоритмы ОТЛ имеют еще одно преимущество перед алгоритмами буфера глубины: изображаемую поверхность можно описывать при помощи не только полигонального приближения, но и более сложных форм [5]. В результате радикально уменьшается объем описания сцены и существенно повышается качество самого изображения.

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

Картинная поверхность и параметрический проектор

В общепринятой постановке трассировка луча – это отыскание последовательности точек встречи луча с поверхностями 3D-объектов (3D-примитивов, [7]) на пути распространения луча от центра проекции до бесконечности. В каждой такой точке луч изменяет свое направление по законам геометрической оптики. Для определения координат первой точки встречи необходимо решить уравнение (систему уравнений), связывающее точку на поверхности и точку на луче (Ray Casting [2,3]).

Будем считать (см. рис.1), что в 3D-про­странстве задана прямоугольная система координат с началом в точке O, центр проекции C и картинная поверхность S (в частном случае картинная плоскость). Предположим, что на S задан массив точек {Pi}, расположенных в центрах элементов дискретного растра, и, соответственно, массив векторов {Pi}. Любой точке трассируемого луча соответствует связанный вектор V(w) с началом в точке C, проходящий через точку Pi на картинной поверхности:

Vi(w ) = C + (Pi - C) w.                                         (1)

Заметим, что описание трассируемого луча (1) не содержит ограничений на форму носителя точек {Pi} и положение центра проекции C (S вовсе не обязана быть плоскостью). Однако условия проецирования желательно все же ограничить отсутствием элементов растра, компланарных вектору сканирования, «складок» на картинной поверхности и т.п. В частности, картинная поверхность не должна содержать элементов растра, таких, что [Vi (w =1), ni] £ 0, где [·] – символ скалярного произведения; ni – нормаль элемента растра.

Формальная запись в 3D-координатах для условия встречи любого трассируемого луча V(w) и носителя M изображаемой поверхности D может быть представлена так:

V(w)=M(D),                                                           (2)

где M(D) – точка 3D-носителя поверхности D.

Выражение (2) можно рассматривать как обобщенную форму уравнения относительно скалярного параметра w, которое иногда разрешимо относительно w. При отсутствии пересечений луча и объекта отсутствуют и действительные решения (2). Если действительные решения существуют, то при w£1 точка встречи не изображается. Когда решений несколько, может быть поставлена задача определения ближайшей точки пересечения

w* = , j=1,2,…,n,                       (3)

где WV – множество всех встреч луча V(w) со всеми n примитивами.

Решением задачи (3) следует считать не только значение w*, а пару {w*, j*}, содержащую номер примитива j*, с которым произошла встреча (предполагается, что 3D-примитивы могут иметь разное математическое описание).

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

Помимо ограничений на форму S можно отказаться от других ограничений и рассмотреть задачу трассировки в еще более общем виде. Обычно в задаче проецирования в качестве обращенного источника принято использовать один центр проецирования. Однако нет причин для запрета на выбор нескольких обращенных источников луча. Вместо одного источника обращенного луча (центра проецирования C) можно ввести множество таких источников {C}, с каждым из которых по аналогии с (2), связан вектор P. Так как нет смысла вводить источников лучей больше, чем число элементов растра, можно использовать биекцию {P}Û{C}.

Расположение точек С может быть самым разным, например, можно разместить их на поверхности или на пространственной кривой, то есть использовать некоторый носитель X множественных центров проецирования CÎX. В этом случае будем считать, что задано множество пар 3D-векторов p={(Ci,Pi)}, которые образуют «трассирующее множество», или «параметрический проектор». Тогда формулу (1) нужно записать в таком виде:

Vi(w) = Ci + w (Pi - Ci),   iÎ[1,N],                       (4)

где Ci – вектор с концом в точке выхода луча; Pi – вектор с концом в центре элемента растра; Vi(w) – точка на i-м луче; w – параметр, задающий положение точки на луче; N – мощность множества элементов растра.

Заметим, что задача параллельного проецирования вместо частного случая проецирования с бесконечно удаленным центром может рассматриваться как задача проецирования с множеством центров проецирования {C}.

Другим обобщением задачи проецирования можно считать рассмотрение вместо проецирующих лучей (параметрических прямых) проецирующих кривых (параметрических траекторий). Для задания точки на трассируемой кривой можно использовать любой подходящий способ (например, координатные функции x=x(w), y=y(w), z=z(w)).

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

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

Решение уравнений встречи

На практике для определения координат видимых точек V(w*) вместо (2) используются более конструктивные записи условий встречи луча и поверхности. Найденное значение w* определяет ближайшую видимую точку пересечения луча V(w) с поверхностью. Далее можно определить все необходимые атрибуты этой точки в контексте поверхности D (вектор нормали к M(D) в точке V(w) и т.п.).

Чаще всего применяются три формы записи (2), позволяющие построить уравнение (систему уравнений), из которых в конечном итоге можно найти w:

-    системы алгебраических уравнений в 3D-координатах;

-    неявная функция в 3D-координатах;

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

Алгебраические уравнения в 3D-координатах. Для некоторых видов поверхностей запись (2) можно непосредственно представить в виде

||V(w ) - M(q)||=0,                                                 (5)

где ||.|| – евклидова норма; qÎRn – вектор числовых параметров (констант, задающих форму поверхности).

Для сферы и ряда других поверхностей (эллипсоида, тора, параболоида и т.п.) конкретные формы записи (5) хорошо известны, и решение для отыскания w  может быть получено в явном виде. В частности, для сферы радиуса r с центром в точке O имеем:

||w P + (1–w )C – O|| = r,                                    (6)

откуда легко получить явное выражение для w  через C, P, O и r.

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

Неявная функция в 3D-координатах. При таком способе задания поверхности используется функция, по определению принимающая нулевые значения в точках, расположенных на носителе

F(M,q)=0.                                                              (7)

Заметим, что к виду (7) можно привести многие виды алгебраического описания поверхностей, например, в (6) для этого достаточно перенести r в левую часть выражения. Можно и наоборот, из условия F(V(w),q)=0 получить явное алгебраическое выражение для w .

Использование неявных функций удобно, если трудно или невозможно получить явное выражение для координат (знакопеременность неявной функции можно использовать для определения положения точки по отношению к поверхности). Часто оптимальным подходом является дихотомический поиск значения w. Число итераций составляет O(log2(d/e)), где d – характерное расстояние в сцене; e – допустимая погрешность определения расстояния. Одним из распространенных видов неявных функций, используемых для обратной трассировки, является описание замкнутых поверхностей 2-го порядка (квадрик), R-функций и т.п.

Уравнения в параметрических координатах. Эта форма используется в схеме формального определения поверхности как множества точек, задаваемых отображением плоской области D в точки носителя M поверхности S в трехмерном пространстве. Декартовы координаты x, y и z точек носителя задаются в виде параметрических координатных функций, а система уравнений для отыскания значения параметра w связывает значения координат трассирующего луча со значениями координатных функций: Vx(w)=rx(u,v), Vy(w)=ry(u,v), Vz(w)=rz(u,v).

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

Подходы к обратной трассировке поверхностей свободной формы

Термин «поверхность свободной формы» в разных источниках трактуется по-разному. В данной работе под поверхностью свободной формы понимается поверхность, при задании которой не используется триангуляционное или какое-либо другое ее приближение, заменяющее поверхность набором плоских граней. В этом контексте к поверхностям свободной формы можно отнести все поверхности, форма которых описывается в том или ином виде аналитически, в частности сфера, конус, замкнутые поверхности 2-го порядка (квадрики, поверхности, описываемые R-функциями [5] и т.п.). К числу поверхностей свободной формы с этой точки зрения можно отнести и подмножества любой связности на плоскости. Границы таких подмножеств могут описываться достаточно сложными контурами (кривыми, ломаными и т.п.), однако их трассировка очень проста.

Несколько обособленное положение занимают поверхности, образованные пересечением полупространств с плоскими границами – их описание нельзя, строго говоря, считать аналитическим (вместо формул задаются связанные нормали), но для их трассировки удалось построить эффективные алгоритмы, в частности отсекатель Сайруса-Бека [5].

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

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

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

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

Попробуем определить и описать более общие закономерности, сопутствующие пересечению трассирующего луча и поверхности. Если описывать координаты точек носителя поверхности в системе координат проектора, то пересечение трассирующего луча с поверхностью означает совпадение двух векторов – трассирующего вектора V(w) и радиуса-вектора поверхности. При этом радиус-вектор поверхности исчисляется не в системе местных координат поверхности, а в системе координат, начало которой совмещено с центром проецирования C (рис. 3).

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

Точку носителя поверхности в общем случае независимо от разновидности параметрического описания можно представить следующим образом: M(x,y,z) = R + s(u,u), где R – вектор, проведенный из начала системы координат проектора; s(u,u) – сумма векторов, образующих «путь» от начала местных координат до точки на носителе поверхности. Например, для карты высот путь может быть представлен как перемещение по координатным направлениям s(u,u)=ix+jy+uh, где i, j, u – орты компонент местной системы координат; h – высота над плоскостью в точке (x,y) области D. Для последовательности плоских сечений могут использоваться разные виды описаний, например s(u,u)=ix+r(j,x) (здесь r(j,x) – радиус-вектор по направлению j в плоскости сечения с координатой x вдоль направления i). При использовании сферических координат путь s определяется проще всего: s(u,u)=r(j,l) (однократное перемещение вдоль радиуса-вектора r(j,l) из начала сферической системы координат).

Рассмотрим проектор и носитель поверхности M(D) в единой системе координат. Совместим в точке C центр системы координат, центр единичной сферы и центр проекции. Считаем, что центр системы координат носителя M(D) представлен вектором R (в точку O отображен центр параметрической системы координат, координаты точек носителя преобразованы соответствующим образом и т.п.).

Пронормируем все точки картинной поверхности и все точки носителя поверхности:

, .                           (8)

При центральном проецировании поверхности M(S) на единичную сферу векторы r(u,u) переходят в нормированные векторы r(u,u). Все трассируемые лучи как продолжения векторов V растра картинной поверхности переходят в нормированные радиусы-векторы g и оказываются в пределах другого сегмента. Изображение поверхности также становится «нормированным» и лежит на единичной сфере в области пересечения этих сегментов.

Для описания факта пересечения трассируемого луча и точки на поверхности можно использовать два равносильных (в данном контексте) критерия: совпадение координатных компонент векторов r(u,u) и g либо коллинеарность векторов r(u,u) и g.

Использование совпадения векторов в качестве критерия пересечения приводит к необходимости решения системы из трех уравнений (по координатам x, y и z) относительно неизвестных u,u и w. Критерий коллинеарности нормированных векторов r и g (фактически критерий их совпадения) равносилен критерию [r,g]=1.

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

В качестве функционала F для экстремальной задачи можно использовать скалярное произведение, которое зависит от параметров u,u и вектора u:

F(u,u,g) = [r(u,u),g].                                                  (9)

Заметим, что скалярное произведение в (9) нормированных векторов r и g обладает рядом нужных свойств для использования его как функционала. В частности, на единичной сфере эта функция имеет (точнее, может иметь) максимум, который соответствует коллинеарности векторов r(u,u) и V(w), градиент функционала в точке экстремума обращается в ноль и т.д.

При встрече фиксированного трассирующего луча V с поверхностью, заданной на D=U´V, имеем

(u*,u*)=(F(u,u)), F(u*,u*)=1,        (10)

причем при описании замкнутых поверхностей u и u часто используются сферические координаты (F Ì {j | j Î[-p,p]}, LÌ {l | l Î[0,2p]}).

Для пары (u*,u*), соответствующей точке встречи, искомое значение параметра w* определяется из соотношения .

Некоторые из таких точек поверхности при проецировании на сферу станут кратными, и для выбора w* необходимо использовать дополнительное условие, аналогичное (3) (или алгоритм анализа последовательности {w}, соответствующий конкретному виду CSG-формы).

Экстремальную задачу (10) можно решать на любом из взаимно биективных множеств: K={k} (kÎK нумерует элементы растра и векторы сканирования), на множестве векторов сканирования V={Vk} и множестве элементов растра T={Tk}, например:

g*=(F(g)), F(g*)=1.                            (11)

Заметим, что D и V можно рассматривать как множества, сопряженные относительно функционала (9), и их можно сопоставить с двумя разновидностями алгоритмов синтеза проекций – алгоритмами трассировки и алгоритмами буфера глубины. При этом алгоритм буфера глубины, фактически работает «внутри» алгоритма обратной трассировки, поскольку основной задачей все же является определение координат точки встречи трассирующего луча и поверхности через значение параметра w* на луче.

Алгоритмы трассировки. Для каждого вектора uk сканирования растра можно сформировать подмножество параметров W* для точек встречи, которые на множестве U´V являются точками локальных экстремумов функции скалярного произведения (10)

.        (12)

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

Иногда вместо поиска всех локальных экстремумов (12) можно рассмотреть более простую задачу перебора на конечном подмножестве упорядоченных пар из D* Ì D = U´V

,

в которой конечное подмножество пар D* для перебора определяется, например, следующим образом:

D* = {m* | ( [r (m*),gk ] < 1-e ).                          (13)

Параметр e играет в (13) роль регулятора чувствительности в ходе селекции элементов для подмножества D*, и важно иметь достаточную разрешающую способность подмножества D*, которая пропорциональна его мощности. Далее из WD* выбирается значение w* и определяются координаты ближайшей среди всех точки встречи.

При недостаточной мощности D* и высокой чувствительности (1-e) трассировка может давать артефакты в виде пропадания изображения поверхности между границами областей чувствительности. Низкая чувствительность приводит к искажению изображения из-за увеличения  угловых размеров фрагментов поверхности. Сбалансированный выбор D* и e, как и алгоритм поиска экстремума на D*, является отдельной проблемой.

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

g* = (r (m),g ).                                     (14)

Эта задача может иметь единственное решение, соответствующее одному элементу растра (если трассирующие лучи пересекают картинную поверхность только по одному разу), для которого выполняется V(w*) = g* ||Vk||. Затем по этому решению определяется значение для обновляемого элемента буфера глубины .

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

Обе разновидности алгоритмов синтеза в описанной постановке могут гибко дополнять друг друга в рамках одной системы благодаря общей основе. Причем использование буфера глубины даже более эффективно при определении координат точки встречи в первой ветви трассировки (для схемы ray-casting).

В качестве характерного примера трассировки невыпуклой поверхности можно привести трассировку так называемой поверхности Цао Ена. Эта поверхность определена в [10] как результат непрерывного преобразования (деформации) сферической поверхности. Преобразование действует в пространствах любой размерности и применимо для преобразования не только сферических поверхностей, но важно, что оно применимо для замкнутых поверхностей, преобразование которых в 3D-пространстве можно трактовать как «вылепливание» некоторой формы из пластического материала.

Возможности поверхности Цао Ена [9] сходны с возможностями деформации квадрик, и для трассировки применим, в частности, бинарный поиск. Однако интерес представляет реализация подхода именно к непосредственной трассировке на основе решения системы уравнений встречи (причем с параметрическим заданием поверхности).

В заключение отметим, что рассмотренной постановке задачи ОТЛ вместо общепринятых понятий и моделей трассируемого луча и картинной плоскости используются их обобщения в виде параметрического проектора и картинной поверхности. Это, в частности, позволяет получать изображения для вывода на носители растра сложной формы, а также использовать возможности ОТЛ для решения задач, не связанных непосредственно с оптикой (например, для анализа воздействия потоков твердых частиц на поверхности [11]).

Сложности, возникающие при использовании алгоритмов ОТЛ для систем реального времени, хорошо известны отсутствием развитой аппаратной поддержки. Основным путем повышения быстродействия алгоритмов трассировки является распараллеливание на уровне сегментов растра. Расширение множества 3D-примитивов, дополняющих возможности полигонального описания поверхностей, дает еще один путь к распараллеливанию алгоритмов обратной трассировки – это использование множества 3D-примитивов («параллелизм на уровне примитивов»).

Дополнительные перспективы для аппаратной поддержки обратной трассировки открывает появление вычислительных устройств с логикой, перепрограммируемой в режиме run-time, в том числе архитектуры на основе FPGA-чипов. При использовании вычислителей с FPGA могут быть достигнуты большие коэффициенты сжатия программного кода (до нескольких сотен инструкций, выполняемых за один тактовый цикл в процессоре S5000 [6]), что и делает перспективным использование ОТЛ составных полиморфных поверхностей.

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

Список литературы

1.        Whitted T. An Improved Illumination Model for Shaded Display. - Comm. of the ACM, 23(6), pp.343-349 (June 1980).

2.        Appel A. Some techniques for shading machine renderings of solids. - Proc. AFIPS JSCC, 32, pp.37-45 (1968).

3.        Goldstein R.A. and Nagel R. 3D Visual Simulation. - Simulation, pp. 25-31 (January 1971).

4.        Ландсберг Г.С. Оптика.-М.:Наука, 1976. – 928 с.

5.        Хилл Ф. OpenGL. Программирование компьютерной графики. –СПб.: Питер, 2002.- 1088 с.

6.        http://www.stretchinc.com/news/pr_051704.php.

7.        Афанасьев В.О. Система полиморфных 3D-примити­вов для порождения виртуальных актеров. / Имитационное моделирование и автоматизация программирования: // Сб. науч. тр. /Под ред. Н.В.Макарова-Землянского. - М.: Изд-во МГУ, 1997. - С. 71-79.

8.        Афанасьев В.О. Обратная трассировка на продолжении вектора сканирования картинной поверхности. - Моделирование сложных систем и виртуальная реальность: Вопр. кибернетики.- М.: Изд-во РАН, 1995. - № 181. - С.41-55.

9.        Афанасьев В.О. Задачи обратной трассировки пространственных объектов произвольной формы. - Моделирование сложных систем и виртуальная реальность: Вопр. кибернетики. – М.: Изд-во РАН, 1995. - № 181. - С. 21-41.

10.     Вайвил Д., Цао Ен, Тротмен А. Поверхность Цао Ена: новый подход к геометрическим моделям произвольных форм. // Программирование. – 1992. -№ 4. - С.4-16.

11.     Utkin V.F., Afanasiev V.O., Brovkin A.G., Menshikov G.P., Romanchenkov V.P., Sokolov Y.A., Zinchenko L.V., Reshetin I.A., Sokolov V.G. Risk of Functioning of International Space Station Connected with Influence of Meteoroids and Space Debris. - Proc of 49th International Astronautical Congress (Sept.28-Oct.2, 1998/Melbourne, Australia).