Визуализация пространственных реалистических сцен

Свето-теневой анализ

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

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

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

Впервые идея совмещенного анализа видимости и затененности была предложена в 1968 г. Аппелем. В качестве примера рассмотрим один алгоритм на основе построчного сканирования, состоящий из двух основных этапов.

I. Анализ сцены по отношению к источнику света. Для всех многоугольников, полученных в результате проецирования сцены, определяются неосвещенные (затененные) участки и теневые многоугольники (проекционные тени), причем многоугольники образуют пронумерованный список. Для этих многоугольников формируется матрица $$A=(a_{ij})$$, позволяющая определить, отбрасывает ли многоугольник тень и какие из многоугольников он может закрывать. Если для некоторых значений $$i,j \quad a_{ij}=1$$, то это означает, что многоугольник с номером $$i$$ может отбрасывать тень на многоугольник с номером $$j$$.

Таким образом, на этом этапе основным является вопрос об эффективном алгоритме построения такой матрицы. Если проекция включает $$N$$ многоугольников, то необходимо рассмотреть "взаимоотношения" $$N\cdot(N-1)$$ пар многоугольников. Сократить перебор можно за счет погружения объектов в прямоугольные или сферические оболочки или путем использования сортировки по глубине.

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

Для каждого видимого отрезка

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

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

Еще один алгоритм, часто применяемый при построении теней, носит название метода теневого буфера. Он строится на основе метода Z-буфера, описанного в лекции 7. Теневой буфер - это тот же Z-буфер, только с точки зрения источника света. Таким образом, используются два буфера: один - для расстояния от картинной плоскости до точек изображаемой сцены, а другой - для расстояний от этих же точек до источника света. Алгоритм позволяет изображать сцены с полным затенением и сводится к двум основным этапам:

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

При наличии нескольких источников света количество освещенных участков естественным образом увеличивается.

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

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

Представим сцену из $$N$$ элементов (участков поверхностей). Освещенность будем моделировать как количество энергии, излучаемое поверхностью. Для каждого элемента это количество энергии складывается из собственной энергии $$(E_k)$$ и отраженной доли энергии, полученной от других объектов. Предполагается, что для каждой пары элементов с номерами $$i,j$$ можно определить, какая доля энергии одного попадает на другой $$(w_{ij})$$. Пусть $$\alpha_i$$ - коэффициент отражения энергии $$i-\text{м}$$ элементом. Тогда полная энергия, излучаемая этим элементом, будет определяться уравнением $$U_i=E_i+\alpha_i\sum_{j=1}^N w_{ij}U_j$$.

Таким образом, мы получаем систему уравнений для нахождения значений $$U_i$$, которая в матричном виде выглядит следующим образом:$$(I-W)\cdot U=E$$ где $$I$$ - единичная матрица, $$U$$ и $$E$$ - векторы излучаемой и собственной энергий, а матрица $$W$$ состоит из элементов $$(\alpha_i w_{ij})$$. Поскольку часть излучения элемента может не попадать ни на один из оставшихся, то$$\sum_{i=1}^N w_{ij}\le 1,$$ а это условие в сочетании с тем, что $$\alpha_i < 1$$ (отражение не является полным), приводит к тому, что матрица системы имеет так называемое диагональное преобладание, т.е. диагональный элемент по абсолютной величине больше, чем сумма остальных элементов строки. В таком случае система уравнений имеет решение, которое можно найти с помощью численных методов.

Итак, шаги алгоритма изображения сцены сводятся к следующим:

Сложным моментом в модели излучательности является расчет коэффициентов $$w_{ij}$$.

Рассмотрим один пример. Пусть имеется два элемента сцены $$S_1$$ и $$S_1$$ (рис. 10.2). Поскольку используется диффузная модель освещения, то доля энергии малого участка $$dS_1$$ с нормалью $$\overrightarrow{n}_1$$, излучаемая под углом $$\alpha_1$$ к этой нормали, пропорциональна косинусу угла. Следовательно, в направлении элементарного участка $$dS_2$$ уходит доля энергии, пропорциональная косинусу угла между $$\overrightarrow{n}_1$$ и отрезком, который соединяет эти участки. Соответственно, получаемая вторым участком доля этой энергии будет пропорциональна косинусу угла между нормалью $$\overrightarrow{n}_2$$ и этим же отрезком. Итак, доля энергии, получаемая элементом $$dS_2$$ от элемента , $$dS_1$$ - $$dw_{21}=\cos(\alpha_1)\cdot\cos(\alpha_2)/\pi r^2$$, где $$r$$ - расстояние между элементами. Кроме того, необходимо учесть, что излучаемая элементарным участком энергия равномерно распределена по всем направлениям. И, наконец, в каждой сцене одни объекты могут частично экранировать другие, поэтому надо ввести коэффициент, определяющий степень видимости объекта с позиции другого. Далее полученное выражение интегрируется по $$S_1$$ и $$S_2$$, что также может быть сложной задачей.

Отсюда видно, насколько трудоемкой может оказаться процедура вычисления коэффициентов $$w_{ij}$$. Поэтому, как правило, используются приближенные методы их вычисления. В частности, можно рассматривать поверхности объектов как многогранники, тогда элементами сцены будут плоские многоугольники, для которых формулы несколько упрощаются.

Глобальная модель освещения с трассировкой лучей

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

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

Если рассмотреть сцену, содержащую в числе прочих зеркальные и полупрозрачные поверхности (рис. 10.3), то изображение будет включать, во-первых, проекции самих объектов, освещенных одним или несколькими источниками света. В некоторых своих частях эти объекты будут искажены за счет преломления лучей в прозрачных и полупрозрачных телах. Во- вторых, часть объектов будет отражаться зеркальными поверхностями, и эти отражения появятся на проекциях зеркальных объектов. В изображенной на рис. 10.3 сцене точки на поверхности призмы $$C, \: D$$ видны на картинной плоскости дважды: один раз - сквозь полупрозрачный параллелепипед в виде точек $$\widetilde{C},\:\widetilde{D}$$, а второй раз - как дважды отраженные невидимой поверхностью параллелепипеда и зеркалом $$C'',\: D''$$. Параллелепипед в данном случае частично обладает зеркальными свойствами.

Глобальная модель освещения для каждого пикселя изображения определяет его интенсивность. Будем для простоты считать, что все источники света - точечные. Сначала определяется непосредственная освещенность источниками без учета отражений от других поверхностей (вторичная освещенность): отслеживаются лучи, направленные ко всем источникам. Тогда наблюдаемая интенсивность (или отраженная точкой энергия) выражается следующим соотношением:$$I=k_0 I_0+k_d\sum_j I_j(\overrightarrow{n}\cdot\overrightarrow{l}_j)+k_r\sum_j I_j(\overrightarrow{s}\cdot\overrightarrow{r}_j)^\beta+k_r I_r+k_t I_t,$$ где

$$k_0$$ - коэффициент фонового (рассеянного) освещения;

$$k_d$$ - коэффициент диффузного отражения;

$$k_r$$ - коэффициент зеркального отражения;

$$k_t$$ - коэффициент пропускания;

$$\overrightarrow{n}$$ - единичный вектор нормали к поверхности в точке;

$$\overrightarrow{l}_j$$ - единичный вектор, направленный к $$j$$ -му источнику света;

$$\overrightarrow{s}$$ - единичный локальный вектор, направленный в точку наблюдения;

$$\overrightarrow{r}_j$$ - отраженный вектор $$\overrightarrow{l}_j$$ ;

$$I_0$$ - интенсивность фонового освещения;

$$I_j$$ - интенсивность $$j$$ -го источника света;

$$I_r$$ - интенсивность, приходящая по зеркально отраженному лучу;

$$I_t$$ - интенсивность, приходящая по преломленному лучу.

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

Пусть $$\overrightarrow{v},\overrightarrow{r},\overrightarrow{t}$$ - направления падающего, отраженного и преломленного лучей (рис. 10.4), $$\overrightarrow{v}_1=\overrightarrow{v}/\cos(\theta_1)$$, $$\overrightarrow{n}$$ - единичная внешняя нормаль, $$\eta_1,\eta_2$$ - коэффициенты преломления сред, разделенных поверхностью. Тогда можно показать, что$$\overrightarrow{r}_1=\overrightarrow{v}_1+2\cdot\overrightarrow{n}, \quad \overrightarrow{t}_1=\kappa(\overrightarrow{n}+v_1)-\overrightarrow{n}, \quad\\ \kappa=(k_{\eta}^2\cdot|\overrightarrow{v}_1|^2-|\overrightarrow{v}|_1+\overrightarrow{n}^2)^{-1/2}, \quad k_{\eta}=\frac{\eta_2}{\eta_1}.$$ Соответствующие единичные векторы получить нетрудно.

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

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

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

Текстуры

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

Сначала рассмотрим методы отображения узоров. Чаще всего узор задается в виде образца, заданного на прямоугольнике в декартовой системе координат $$\eta,\xi$$ в пространстве текстуры. Фрагмент поверхности может быть задан в параметрическом виде в трехмерной декартовой системе координат:$$x=f(u,v), \quad y=g(u,v), \quad z=h(u,v), \quad a\le u\le b, \quad c\le v\le d.$$

Теперь достаточно построить отображение области в пространстве текстуры в область параметров поверхности$$u=\varphi(\eta,\xi), \quad v=\psi(\eta,\xi),$$ или$$\eta=\chi(u,v), \quad \xi=\theta(u,v),$$ и тем самым каждой точке поверхности будет соответствовать точка образца текстуры. Пусть, например, поверхность представляет собой один октант сферы единичного радиуса, заданный формулами$$x=\sin\alpha\cdot\sin\beta, \quad y=\cos\beta, \quad z=\cos\alpha\cdot\sin\beta, \quad\\ 0\le\alpha\le\pi/2, \quad \pi/4\le\beta\le\pi/2$$

а образец текстуры задан на квадрате $$0\le\eta\le 1, \quad 0\le\xi\le 1$$. Тогда можно воспользоваться линейным отображением вида$$\alpha=a\eta+b, \quad \beta=c\eta+d.$$

Если положить $$a=\pi/2, \quad b=0, \quad c=-\pi/4, \quad d=\pi/2$$, то углы образца отобразятся в углы криволинейного четырехугольника, как это показано на рис. 10.6.

Обратное отображение имеет вид$$\eta=\frac{\alpha}{\pi/2}, \quad \xi=\frac{\pi/2-\beta}{\pi/4},$$ следовательно, вертикальные и горизонтальные линии образца отобразятся на окружности большого круга сферы.

Пусть теперь нужно нанести текстуру при перспективном проецировании произвольно ориентированной прямоугольной грани. Грань задана в пространстве набором своих вершин $$A,B,C,D$$. Построим векторы $$\overrightarrow{e}_1=B-A$$ и $$\overrightarrow{e}_2=D-A$$, направленные вдоль сторон прямоугольника. Любую точку прямоугольника можно единственным образом представить в виде$$P=A+u\overrightarrow{e}_1+v\overrightarrow{e}_2.$$ Будем считать, что используется простейший случай перспективного преобразования, задаваемый формулами$$x'=\frac{x}{z}, \quad y'={y}{z}.$$

Найдем образ точки P при таком преобразовании:$$x'=\frac{A_x+u\overrightarrow{e}_{1x}+v\overrightarrow{e}_{2x}}{A_z+u\overrightarrow{e}_{1z}+v\overrightarrow{e}_{2z}}, \quad y'=\frac{A_y+u\overrightarrow{e}_{1y}+v\overrightarrow{e}_{2y}}{A_z+u\overrightarrow{e}_{1z}+v\overrightarrow{e}_{2x}},$$ или$$\left\{ \begin{aligned} u(x'\overrightarrow{e}_{1z}-\overrightarrow{e}_{1x})+v(x'\overrightarrow{e}_{2z}-\overrightarrow{e}_{2x})=A_x-A_z x' \\ \\ u(y'\overrightarrow{e}_{1z}-\overrightarrow{e}_{1y})+v(y'\overrightarrow{e}_{2z}-\overrightarrow{e}_{2y})=A_y-A_z y' \end{aligned} \right. .$$ Если теперь рассматривать эти соотношения как систему уравнений для нахождения параметров $$u,v$$, то, решив ее, получим требуемое обратное преобразование. Для решения можно воспользоваться, например, правилом Крамера:$$u=\Delta_u/\Delta, \quad v=\Delta_v/\Delta$$ где$$\begin{aligned} \Delta=(x'\overrightarrow{e}_{1z}-\overrightarrow{e}_{1x})\cdot(y'\overrightarrow{e}_{2z}-\overrightarrow{e}_{2y})-(x'\overrightarrow{e}_{2z}-\overrightarrow{e}_{2x})\cdot(y'\overrightarrow{e}_{1z}-\overrightarrow{e}_{1y}); \\ \Delta_1=(A_x-A_z x')\cdot(y'\overrightarrow{e}_{2z}-\overrightarrow{e}_{2y})-(x'\overrightarrow{e}_{2z}-\overrightarrow{e}_{2x})\cdot(A_y-A_z y'); \\ \Delta_2=(x'\overrightarrow{e}_{1z}-\overrightarrow{e}_{1x})\cdot(A_y-A_z y')-(A_x-A_z x')\cdot(y'\overrightarrow{e}_{1z}-\overrightarrow{e}_{1y}). \end{aligned}$$ Найденные параметры будут определять точку текстуры, соответствующую точке проекции.

Можно рассмотреть более общий случай перспективной проекции, задаваемый соотношениями$$x'=\frac{x}{1+\frac{z}{d}}, \quad y'=\frac{y}{1+\frac{z}{d}}$$ Тогда уравнения для определения $$u,v$$ немного усложнятся:$$\left\{ \begin{aligned} u(x'\overrightarrow{e}_{1z}/d-\overrightarrow{e}_{1x})+v(x'\overrightarrow{e}_{2z}/d-\overrightarrow{e}_{2x})=A_x-(1+A_z/d)x' \\ \\ u(y'\overrightarrow{e}_{1z}/d-\overrightarrow{e}_{1y})+v(y'\overrightarrow{e}_{2z}/d-\overrightarrow{e}_{2y})=A_y-(1+A_z/d)y' \end{aligned} \right. .$$ Соответственно, изменится и решение:$$\begin{aligned} \Delta=(x'\overrightarrow{e}_{1z}/d-\overrightarrow{e}_{1x})\cdot(y'\overrightarrow{e}_{2z}/d-\overrightarrow{e}_{2y})-\\-(x'\overrightarrow{e}_{2z}/d-\overrightarrow{e}_{2x})\cdot(y'\overrightarrow{e}_{1z}/d-\overrightarrow{e}_{1y}); \\ \Delta_1=(A_x-(1+A_z/d)x')\cdot(y'\overrightarrow{e}_{2z}/d-\overrightarrow{e}_2y)-\\-(x'\overrightarrow{e}_{2z}/d-\overrightarrow{e}_{2x})\cdot(A_y-(1+A_z/d)y') \\ \Delta_2=(x'\overrightarrow{e}_{1z}/d-\overrightarrow{e}_{1x})\cdot(A_y-(1+A_z/d)y')-\\-(A_x-(1+A_z/d)x')\cdot(y'\overrightarrow{e}_{1z}/d-\overrightarrow{e}_{1y}). \end{aligned}$$

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

Пусть, как и ранее, поверхность задана в параметрическом виде с помощью векторной функции $$\overrightarrow{F}(u,v)$$. В каждой ее точке можно построить вектор нормали, воспользовавшись частными производными этой функции. Известно, что производные $$\overrightarrow{F}_u$$ и $$\overrightarrow{F}_v$$ представляют собой векторы, лежащие в касательной плоскости данной поверхности. Тогда вектор нормали может быть получен как векторное произведение этих двух векторов $$\overrightarrow{n}=\overrightarrow{F}_u \times \overrightarrow{F}_v$$. После этого точку поверхности можно отклонить от первоначального положения в направлении нормали на некоторую малую величину, задаваемую с помощью функции возмущения $$P(u,v)$$:$$\overrightarrow{F}'(u,v)=\overrightarrow{F}(u,v)+P(u,v)\cdot\overrightarrow{n}(u,v).$$

Можно показать, что нормаль к новой возмущенной поверхности будет определяться выражением$$\overrightarrow{n}'=\overrightarrow{n}+\frac{P_u\cdot(\overrightarrow{n}\times\overrightarrow{F}_u)}{|\overrightarrow{n}|}+\frac{P_v\cdot(\overrightarrow{n}\times\overrightarrow{F}_v)}{|\overrightarrow{n}|}.$$ Применяя в модели освещения новую нормаль, можно получить эффект шероховатости поверхности. В качестве функции возмущения можно использовать произвольную дифференцируемую по каждой из переменных функцию.

Вопросы и упражнения