Программирование, 2022, № 3, стр. 50-58

МОДЕЛИРОВАНИЕ ДИНАМИЧЕСКИХ ТЕНЕЙ РЕЛЬЕФА В МАСШТАБЕ РЕАЛЬНОГО ВРЕМЕНИ НА ОСНОВЕ МНОГОУРОВНЕВОГО РЭЙКАСТИНГА

П. Ю. Тимохин a*, М. В. Михайлюк a**

a ФГУ «ФНЦ Научно-исследовательский институт системных исследований РАН»
117218 Москва, Нахимовский пр., 36, к.1, Россия

* E-mail: webpismo@yahoo.de
** E-mail: mix@niisi.ras.ru

Поступила в редакцию 25.12.2021
После доработки 16.01.2022
Принята к публикации 21.01.2022

Полный текст (PDF)

Аннотация

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

1. ВВЕДЕНИЕ

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

В условиях динамически меняющейся виртуальной обстановки надежным подходом к синтезу качественных и геометрически точных теней рельефа местности является рэйкастинг [5] – частный случай трассировки лучей, широко применяемой в области фотореалистичного рендеринга [6]. При данном подходе изображения теней просчитываются на основе исходной цифровой модели рельефа – карты высот и их качество не зависит от методов построения и визуализации 3D=модели рельефа [7], которые могут содержать неточности и скрытые уязвимости. В классической реализации [8] производительность рэйкастинга сильно падает с увеличением размеров карты высот. На практике, в случае детализированных карт высот (от 1Kx1K) просчет теней может нарушить интерактивность визуализации, что неприемлемо для СВО. В этой связи возникает задача разработки эффективных технологий, методов и алгоритмов реализации рэйкастинга, обеспечивающих построение теней рельефа на основе детализированных карт высот в масштабе реального времени (не более 40 мс на кадр). Для решения этой задачи в данной работе предлагается технология рэйкастинга теней, при которой детализация теней рельефа понижается в областях изображения, где это незаметно для наблюдателя. Просчет рэйкастинга на каждом уровне детализации тени выполняется на GPU и ускорен с помощью карты локальных экстремумов высоты. Предлагаемое решение реализовано на языке C++ с использованием языка GLSL программирования шейдеров и графической библиотеки OpenGL.

2. СОВРЕМЕННЫЕ ПОДХОДЫ

Можно выделить три крупных подхода к моделированию теней рельефа в реальном времени.

Первый подход основан на построении теневых карт виртуальной сцены из позиции источника света и их применении при визуализации сцены из позиции наблюдателя. Одним из наиболее распространенных является метод каскадных карт теней, при котором создается ряд теневых карт одинакового размера для переднего, промежуточных и заднего планов [9, 10]. Благодаря высокой производительности, реализации данного метода часто встречаются в современных играх. Особенностью таких реализаций является необходимость тщательной настройки под конкретный игровой сценарий во избежание появления характерных визуальных артефактов (“ступенчатости” границ теней, ошибочного самозатенения, усечения теней и др.). Для повышения качества синтезируемых теней продвинутые реализации используют процентно-приближенную фильтрацию [11], нерегулярный Z-буфер [12], нелинейное отображение теней [13, 14] и другие решения. Важно отметить, что надежность данного подхода зависит не только от самого алгоритма построения тени, но и от надежности методов построения и визуализации модели рельефа местности. Они могут содержать оптимизации или уязвимости, скрытые в процессе визуализации рельефа, но проявляющиеся при визуализации его тени (в нашем исследовании [5] продемонстрирован пример такой ситуации).

При втором подходе построение теней выполняется на основе проверки попадания точек в теневой объем – область пространства, закрываемую рельефом от источника света. Распространенная реализация данного подхода предполагает вытягивание полигональной модели теневого объема из силуэта рельефа и подсчет пересечений лучей, испущенных из проверяемых точек, с гранями модели теневого объема с помощью буфера трафарета [15]. Благодаря доступу непосредственно к геометрии рельефа, подход теневых объемов позволяет получать качественные, геометрически точные тени для любого положения наблюдателя. Однако, при этом в виртуальной сцене генерируются сложные вспомогательные геометрические объекты, обработка которых может истратить существенную часть ресурсов, отводимых для работы всей системы визуализации. Кроме того, имеется ряд ограничений (на допустимые представления геометрии рельефа, на попадание в теневой объем ближней/дальней отсекающих плоскостей камеры и др.), которые приводят к усложнению структур данных и отрицательно влияют на масштабируемость системы. В направлении преодоления этих недостатков были предложены методы, основанные на комбинации алгоритмов Z‑pass и Z-fail обновления буфера трафарета [16], извлечении силуэтов объектов с помощью геометрического шейдера [17], построении теневого объема по треугольникам с помощью программно-аппаратной архитектуры CUDA параллельных вычислений на GPU [18], ускорении детектирования силуэтов объектов сцены с помощью хэш-таблиц [19] и др.

Третий подход основан на поиске пересечений лучей источника света с поверхностью рельефа, заданной картой высот (рэйкастинг теней). Согласно классическому алгоритму рэйкастинга [8] для каждого пиксела изображения рельефа необходимо построить луч направления на источник света и проверить вдоль него друг за другом текселы карты высот, пока не будет найдена высота рельефа, пересекающая луч (или достигнута граница карты высот). Это позволяет получать физически корректные тени рельефа сложной формы, независимо от надежности методов его моделирования и визуализации [20]. Сравнительно долгое время медленная скорость работы на детализированных картах высот существенно ограничивала широкое применение данного подхода в компьютерной графике реального времени. Однако ситуация изменилась, благодаря активному прогрессу архитектуры и технологий параллельных вычислений на GPU, которые дали новый толчок в развитии методов, основанных на трассировке лучей [21]. В работе [22] был предложен метод ускорения поиска пересечений луч-карта высот с помощью конической карты, рассчитываемой на этапе предобработки. На практике, время построения такой карты резко возрастает с увеличением размеров карты высот (около 15 минут для карты 512 × 512 и около 8 часов для карты 1024 × 1024 [23]). В исследовании [23] разработан метод ускорения на GPU рэйкастинга динамической модели рельефа, заданного картой высот, с помощью мип-карты наибольших высот. Автор работы [20] описал гибридный метод ускорения рэйкастинга теней рельефа за счет пропуска проверки точек, не принадлежащих силуэту рельефа (если смотреть из позиции источника света). В исследовании [24] описана реализация распараллеливания рейкастинга теней рельефа с помощью архитектуры CUDA, где выборка текселов вдоль лучей выполняется с одинаковым шагом. В недавней работе [25] предложен алгоритм реализации рэйкастинга теней рельефа, основанный на [23]. Как утверждают авторы, в текущей реализации их алгоритм имеет некоторые неточности, ухудшающие качество теней, что приходится компенсировать сдвигом вершин рельефа.

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

3. ТЕХНОЛОГИЯ МНОГОУРОВНЕВОГО РЭЙКАСТИНГА ТЕНЕЙ

В данной работе мы будем рассматривать задачу многоуровневого рэйкастинга теней участка рельефа по детализированной карте высот размера 2m × 2m текселов ($m \geqslant 10$) без учета кривизны поверхности уровня моря. Предлагаемая технология включает в себя следующие две стадии.

На первой стадии (предварительной обработки данных) создается мип-пирамида [26] детализированной карты высот (см. рис. 1) и карта локальных экстремумов высоты (далее карта Hext). Карта Hext представляет собой упорядоченный набор двухканальных текстур (R и G компоненты), обладающий следующими свойствами:

Рис. 1.

Мип-пирамида карты высот.

– у 0-й (самой первой) текстуры ширина и высота в 2 раза меньше, чем у исходной карты высот;

– в каждом (i0, j0)-м текселе 0-й текстуры хранятся наибольшее hmax и наименьшее hmin значения, выбранные из исходной карты высот с помощью матрицы 3 × 3, показанной на рисунке 2a;

Рис. 2.

Матрицы выборки для построения карты локальных экстремумов: (a) 0-го уровня, (б) уровня k > 0.

– ширина и высота k-й текстуры ($k \ne 0$) в 2 раза меньше, чем у (k – 1)-й текстуры (текстура 1 × 1 не создается);

– в каждом (ik, jk)-м текселе k-й текстуры хранятся наибольшее hmax и наименьшее hmin значения, выбранные из (k – 1)-й текстуры с помощью матрицы 2 × 2, показанной на рис. 2б.

Отметим, что в матрице 3 × 3 точками выборки являются правые верхние углы 0, …, 8-го текселов карты высот, и выборка выполняется с помощью билинейной интерполяции (GL_LINEAR). В матрице 2 × 2 точками выборки являются центры 0, …, 3-го текселов (k – 1)-й текстуры и выборка выполняется по принципу “ближайший сосед” (GL_NEAREST). Построение карты Hext выполняется на GPU с помощью разработанного фрагментного шейдера.

На второй стадии (визуализации) выполняется синтез изображения затененной модели рельефа. Это реализуется в два шага. На первом шаге для каждого пиксела синтезируемого изображения вычисляется наименьший необходимый уровень q детализации карты высот. На втором шаге на основе вычисленного уровня q, мип-пирамиды карты высот и карты Hext  для каждого пиксела вычисляется коэффициент kshadow затенения. Рассмотрим методы реализации этих шагов.

3.1. Метод вычисления минимального уровня детализации карты высот

Расчет наименьшего необходимого уровня q детализации карты высот реализуется на основе подсчета числа текселов, которое охватывает проекция пиксела (ее стороны) в текстурной системе координат карты высот. На практике используется эффективное приближение такой проекции в виде параллелограмма (рис. 3), а его длины сторон вычисляются с помощью частных производных текстурных координат (s, t) пиксела по X и Y экранной системы координат (рис. 3a) [27]. Также в данной работе выполняется компенсация анизотропного изменения сторон параллелограмма [28], возникающего при наблюдении карты высот под малым углом. Расчет минимального уровня q реализует следующий алгоритм Algo 1:

Рис. 3.

Отображение пиксела: a) в экранной системе координат; б) в текстурной системе координат карты высот.

1. Вычислим частные производные текстурных координат (s, t) пиксела:

${{s}_{x}} = w\frac{{\partial s}}{{\partial x}}$, ${{s}_{y}} = w\frac{{\partial s}}{{\partial y}}$, ${{t}_{x}} = h\frac{{\partial t}}{{\partial x}}$, ${{t}_{y}} = h\frac{{\partial t}}{{\partial y}}$, где w и h – ширина и высота карты высот, в текселах.

2. Вычислим квадраты наибольшей dmax и наименьшей dmin длин сторон параллелограмма (см. рис. 3б):

$d_{{\max }}^{2} = \max ({{\left| {{\mathbf{a}}{\kern 1pt} '} \right|}^{2}},{{\left| {{\mathbf{b}}{\kern 1pt} '} \right|}^{2}})$, $d_{{\min }}^{2} = \min ({{\left| {{\mathbf{a}}{\kern 1pt} '} \right|}^{2}},{{\left| {{\mathbf{b}}{\kern 1pt} '} \right|}^{2}})$, где ${{\left| {{\mathbf{a}}{\kern 1pt} '} \right|}^{2}} = s_{x}^{2} + t_{x}^{2}$, ${\text{|}}{\mathbf{b}}'{{{\text{|}}}^{2}} = s_{y}^{2} + t_{y}^{2}$.

3. Вычислим коэффициент na компенсации анизотропного изменения:

${{n}_{a}} = \min (\left\lceil {\sqrt {{{d_{{\max }}^{2}} \mathord{\left/ {\vphantom {{d_{{\max }}^{2}} {d_{{\min }}^{2}}}} \right. \kern-0em} {d_{{\min }}^{2}}}} } \right\rceil ,{{n}_{{a,\max }}})$, где ${{n}_{{a,\max }}}$ – наибольшее число выборок при анизотропной фильтрации текстуры, поддерживаемое видеокартой.

4. Вычислим минимальный уровень q детализации:

$q = \left\lfloor {{{{\log }}_{2}}\left( {{{{{d}_{{\max }}}} \mathord{\left/ {\vphantom {{{{d}_{{\max }}}} {{{n}_{a}}}}} \right. \kern-0em} {{{n}_{a}}}}} \right)} \right\rfloor = \left\lfloor {0.5{{{\log }}_{2}}(d_{{\max }}^{2}) - {{{\log }}_{2}}\left( {{{n}_{a}}} \right)} \right\rfloor $.

5. Уточним уровень q с учетом мип-пирамиды карты высот:

$q = \min \left( {\max \left( {q,0} \right),L} \right)$, где L – самый грубый уровень детализации мип-пирамиды карты высот.

Конец алгоритма.

3.2. Метод вычисления коэффициента затенения пиксела

Определение коэффициента затенения. Обозначим через bshadow булевский флаг наличия тени в рассматриваемом пикселе (1 означает, что тень есть, 0 – нет). Введем коэффициент kshadow затенения пиксела, определяемый по следующей формуле

(1)
$\begin{gathered} {{k}_{{shadow}}} = {{({{k}_{{dark}}} + ({{k}_{{bright}}} - {{k}_{{dark}}}){\text{cos}}\alpha )}^{{{{b}_{{shadow}}}}}} = \\ = {{({{k}_{{dark}}} + ({{k}_{{bright}}} - {{k}_{{dark}}})({\mathbf{s}} \cdot {\mathbf{n}}))}^{{{{b}_{{shadow}}}}}}, \\ \end{gathered} $
где α – угол между вектором n нормали к поверхности уровня моря в точке P рельефа (см. рис. 4), соответствующей рассматриваемому пикселу, и единичным вектором s направления на солнце (бесконечно удаленный источник света); kdark – коэффициент затенения, соответствующий наиболее плотной тени, а kbright – наиболее разреженной, kdark, kbright ∈ [0, 1]. Значения kdark и kbright выбираются, исходя из диапазона яркостей, в котором выполняется рендеринг виртуальной сцены.

Рис. 4.

Затенение точки P.

Вычисление флага bshadow. Чтобы вычислить kshadow с помощью выражения (1), необходимо найти значение флага bshadow. Вначале определим bshadow. Для этого выберем точку Ptest рельефа, лежащую в плоскости {s, n, P} между точкой P и источником света и проведем луч v из P в Ptest. Из рисунка 4 видно, что точка P будет затенена, если луч v будет направлен не ниже вектора s, т.е. будет неположительным смешанное произведение $p = {\mathbf{r}} \cdot ({\mathbf{v}} \times {\mathbf{s}})$, где ${\mathbf{r}} = {\mathbf{s}} \times {\mathbf{n}}$ – единичный вектор, дополняющий s и n до правой тройки. Исходя из этого, запишем определение:

(2)
${{b}_{{shadow}}} = \left\{ \begin{gathered} 1,\;{\text{если}}\,p \leqslant 0\,\,\,{\text{и}}\,\,\left( {{\mathbf{s}} \cdot {\mathbf{n}}} \right) \ne 1, \hfill \\ 0,\,\,{\text{в}}\,\,{\text{остальных}}\,\,{\text{случаях}}{\text{.}} \hfill \\ \end{gathered} \right.$

Вычисление значения флага bshadow будем выполнять на q-м уровне детализации мип-пирамиды карты высот (далее – карта Hq). Обозначим через P' точку на карте Hq, соответствующую точке P рельефа, через s' – трассу солнечного луча, проведенную из точки P' в системе текстурных координат карты Hq. Рассмотрим некоторый Ti j-й тексел, лежащий на трассе s' (см. рис. 5а). Данный тексел отсекает от трассы s' участок PinPout (см. рис. 5б), которому соответствует своя кривая на поверхности рельефа (далее – кривая g). Теоретически, чтобы найти значение флага bshadow в Ti j-м текселе, необходимо выбрать в качестве точки Ptest (см. рис. 4) наиболее высокую точку кривой g и посчитать смешанное произведение из выражения (2). Наши эксперименты показали, что в случае детализированных карт высот является допустимым (не образует “рваные” края у синтезируемых теней) приближение, при котором в качестве Ptest берется средняя точка кривой g. Соответствующая ей точка Ps на карте Hq показана на рис. 5б. В данной работе мы вычисляем координаты точки Ps как среднее координат транзитных точек – точек Pin входа и Pout выхода трассы s' из Ti j-го тексела. Из рисунка 5б видно, что точка Pout выхода из Ti, j-го тексела будет точкой Pin входа в следующий Ti, j +1-й тексел, таким образом, при проверке каждого Ti, j-го тексела достаточно вычислить только транзитную точку Pout. Обозначим через u единичный вектор направления трассы s', тогда координаты точки Pout можно записать в параметрическом виде

(3)
${{P}_{{out}}} = {{P}_{{in}}} + {\mathbf{u}}t.$
Рис. 5.

Тексел Ti, j, лежащий на трассе солнечного луча (a), транзитные точки Ti, j-го тексела (б).

Вычисление параметра t и сдвигов (ioffset, joffset) номеров строки и столбца следующего по трассе тексела реализует следующий разработанный алгоритм Algo 2:

1. Сформируем массив K текстурных координат четырех угловых точек Ti, j-го тексела:

K [4] = $\{ \{ {{s}_{0}},{{t}_{0}}\} ,\{ {{s}_{0}} + ds,{{t}_{0}}\} ,$ $\{ {{s}_{0}},{{t}_{0}} + dt\} $, $\{ {{s}_{0}}\, + \,ds,{{t}_{0}}\, + \,dt\} \} $, где $ds\, = \,2{\kern 1pt} '{\text{/}}w$, $dt = 2'{\text{/}}h$, а l = q, ..., L.

2. Если $\left| {{{u}_{x}}} \right| \leqslant \varepsilon $ и $\left| {{{u}_{y}}} \right| \leqslant \varepsilon $, то: t = –1, ioffset = 0, joffset = 0 (ε – машинная погрешность действительных чисел), выходим из алгоритма.

3. Вычислим порядковый номер nout угла Ti, j-ого тексела, из которого выходит трасса s':

${{n}_{{out}}} = {{b}_{0}} + 2{{b}_{1}}$, где b0, b1 – булевские флаги: ${{b}_{0}} = \left( {\left| {{{u}_{x}}} \right| \geqslant 0} \right)$), ${{b}_{1}} = \left( {\left| {{{u}_{y}}} \right| \geqslant 0} \right)$.

4. Запишем разность $dP = K\left[ {{{n}_{{out}}}} \right] - {{P}_{{in}}}$.

5. Если $\left| {{{u}_{x}}} \right| \leqslant \varepsilon $, то: $t = {\text{|}}d{{P}_{y}}{\text{|}}/{\text{|}}{{u}_{y}}{\text{|}}$, ${{i}_{{offset}}} = sign\left( {{{u}_{y}}} \right)$, joffset = 0 (sign – функция, возвращающая знак переменной), выходим из алгоритма.

6. Если $\left| {{{u}_{y}}} \right| \leqslant \varepsilon $, то: $t = {\text{|}}d{{P}_{x}}{\text{|}}/{\text{|}}{{u}_{x}}{\text{|}}$, ioffset = 0, joffset = = $sign({{u}_{x}})$, выходим из алгоритма.

7. Запишем $e = {{dP} \mathord{\left/ {\vphantom {{dP} u}} \right. \kern-0em} u}$ и булевские флаги b2 = = $({{e}_{x}} \leqslant {{e}_{y}})$, ${{b}_{3}} = \left( {{{e}_{y}} \leqslant {{e}_{x}}} \right)$.

8. $t\, = \,\min ({{e}_{x}},{{e}_{y}})$, ${{i}_{{offset}}}\, = \,{{b}_{3}}sign({{u}_{y}})$, joffset = ${{b}_{2}}sign({{u}_{x}})$.

Конец алгоритма.

Подставив полученное значение t в выражение (3), получим координаты точки Pout, а, следовательно, и координаты Ps, по которым извлечем из карты Hq значение htest высоты точки Ptest. Зная высоту htest и нормаль n, нетрудно вычислить координаты точки Ptest (координаты точки P вычисляются аналогично) и получить значение флага bshadow с помощью выражения (2).

Поиск ненулевого флага bshadow. Для этого на основе разработанного алгоритма Algo 2 мы проверяем текселы вдоль трассы s', пытаясь с помощью карты Hext локальных экстремумов “проскочить” крупные участки карты высот, начиная с самого грубого уровня детализации. Если проверка по карте Hext показывает, что нет пересечения солнечного луча s с наименьшей высотой, но есть пересечение с наибольшей высотой, то мы спускаемся на более детальный уровень карты Hext и так далее до q-го уровня детализации (см. рис. 6). На q-м уровне проверяется уже непосредственно тексел карты Hq высот. Для выполнения этих проверок введем следующие обозначения: l – уровень детализации: l = q карта высот, q + 1, q + 2, …, L – это q-й, (q + 1)-й, …, L – 1 уровни карты Hext; (i, j) – номера строки и столбца (далее – номера) стартового тексела на q-м уровне; (icur, l, jcur, l), (inext, l, jnext, l) – номера текущего и следующего (по трассе солнечного луча) текселов на l-м уровне; Pout – точка выхода трассы луча из стартового тексела; Pout, l – точка выхода трассы луча из (icur, l, jcur, l)-го тексела; P – координаты точки модели рельефа (в системе OCS), соответствующей точке P' на карте высот; Pmin, l, Pmax, l – координаты наиболее низкой и высокой точек участка модели рельефа (в системе OCS), соответствующие (icur, l, jcur, l)-му текселу (на q-м уровне Pmin, l  совпадает с Pmax, l). Поиск ненулевого значения флага bshadow реализует следующий разработанный алгоритм Algo 3:

Рис. 6.

Продвижение вдоль трассы солнечного луча на карте высот q-го уровня.

1. Стадия инициализации:

   Вычислим P и (i, j); зададим Pin = P' в Algo 2; вычислим Pout и (inext, 0, jnext, 0) согласно Algo 2;

   зададим (icur, q, jcur, q) = (inext, q, jnext, q), Pin = Pout в Algo 2 и l = q.

2. Стадия многоуровневого рэйкастинга:

   Цикл, пока хотя бы один из номеров (icur, q, jcur, q) не выйдет за пределы карты высот:

     Вычислим (icur, l, jcur, l) из (icur, q, jcur, q). Вычислим Pout, l и (inext, l, jnext, l) согласно Algo 2.

     Если l > q, то выполним проверку пересечения луча s с наименьшей высотой:

        Вычислим Pmin, l на основе Pout, l и высоты hmin, выбранной из (icur,l, jcur, l)-го тексела.

        Вычислим для луча v = (Pmin, lP) значение флага bshadow согласно (2);

        Если bshadow равен 1, то выходим из алгоритма.

     Выполним проверку пересечения луча s с наибольшей высотой:

        Если l равен q, то вычислим Pmax, l на основе Ps (см. рис. 5б) и высоты hmax,                                       выбранной из (icur, l, jcur, l)-го тексела карты высот Hq.

        В противном случае: вычислим Pmax, l на основе Pout, l и hmax, выбранной                                       из (icur, l, jcur, l)-го тексела карты Hext локальных экстремумов;           Вычислим для луча v = (Pmax, lP) значение флага                                       bshadow согласно (2);

        Если bshadow равен 1, то:

         Если l равен q, то выходим из цикла, в противном случае l = l – 1.

        В противном случае: зададим (icur, l, jcur, l) = (inext, l, jnext, l); вычислим (icur, 0, jcur.0) из Pout, l;

зададим Pin = Pout, l в Algo 2 и l = L.

   Конец цикла.

   bshadow = 0.

Конец алгоритма.

Отметим, что в приведенном алгоритме извлечение значений высот из карты Hq высот производится с помощью билинейной интерполяции, а из карты Hext локальных экстремумов – без интерполяции (по номерам строки и столбца тексела). В результате выполнения алгоритма Algo 3 мы получаем значение флага bshadow наличия тени для рассматриваемого пиксела. Подставив значение bshadow в формулу (1), мы получаем искомое значение коэффициента затенения kshadow. Описанный в данной работе процесс вычисления уровня q и коэффициента kshadow для каждого пиксела изображения рельефа выполняется полностью на GPU, параллельно, независимо друг от друга с помощью разработанного фрагментного шейдера. При выполнении данного шейдера вычисленные коэффициенты kshadow смешиваются с цветами освещенной модели рельефа, и в результате формируется изображение модели рельефа с тенями.

4. РЕЗУЛЬТАТЫ

Предложенная технология и методы были реализованы в программном комплексе моделирования динамических теней рельефа, входящем в систему виртуального окружения VirSim [2], разработанную в ФГУ ФНЦ НИИСИ РАН. В качестве эксперимента, мы интегрировали наше решение в реализацию метода каскадных карт теней (CSM) от NVidia [10] и сравнили визуализацию теней. Для этого была использована карта высот Великого Каньона [29] размера 2K × 2K (см. рисунок 7). При методе CSM при некотором положении наблюдателя образовалась потеря теней на заднем плане и внутри ущелья (см. рис. 7a). В нашей реализации все тени были отрисованы аккуратно и точно независимо от расположения наблюдателя и солнца (см. рис. 7б). Тестирование проводилось при разрешении Full HD на персональном компьютере (Intel Core i7-6800K 3.40GHz, 16Gb RAM, NVidia GeForce RTX 2080, 16x анизотропная фильтрация, 8x сглаживание). На рисунке 8 показаны графики изменения частоты визуализации затененной модели рельефа Великого Каньона (с помощью нашей технологии) для различных уровней детализации карты высот при увеличении высоты солнца.

Рис. 7.

Построение теней Великого Каньона: (a) каскадные карты теней (4 плоскости отсечения, размеры карт 4K × 4K), и (б) наша технология многоуровневого рэй-кастинга (q = 0)

Рис. 8.

Изменение частоты визуализации модели рельефа Великого Каньона (наша технология многоуровнего рэйкастинга) при уменьшении детализации карты высот и увеличении высоты солнца (0 – на горизонте, 90 – в зените).

5. ЗАКЛЮЧЕНИЕ

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

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

  1. Алтунин А.А., Долгов П.П., Жамалетдинов Н.Р., Иродов Е.Ю., Коренной В.С. Направления применения технологий виртуальной реальности при подготовке космонавтов к внекорабельной деятельности // Пилотируемые полеты в космос. 2021. № 1 (38). С. 72–88. https://doi.org/10.34131/MSF.21.1.72-88

  2. Михайлюк М.В., Мальцев А.В., Тимохин П.Ю., Страшнов Е.В., Крючков Б.И., Усов В.М. Система виртуального окружения VirSim для имитационно-тренажерных комплексов подготовки космонавтов // Пилотируемые полеты в космос. 2020. № 4 (37). С. 72–95. https://doi.org/10.34131/MSF.20.4.72-95

  3. Piovano L., Basso V., Rocci L., Pasquinelli M., Bar C., Marello M., Vizzi C., Lucenteforte M., Brunello M., Racca F., Rabaioli M., Menduni E., Cencetti M. Virtual Simulation of Hostile Environments for Space Industry: From Space Missions to Territory Monitoring // Virtual Reality – Human Computer Interaction, IntechOpen. 2012. P. 153–178. https://doi.org/10.5772/51121. https://www.intechopen.com/chapters/38748.

  4. Тимохин П.Ю., Михайлюк М.В. Метод сжатия разрядности карт высот на основе критерия визуальной значимости // Труды НИИСИ РАН. 2017. Том 7. № 1. С. 30–35. https://www.niisi.ru/tr/2017_T7_N1.pdf.

  5. Timokhin P., Mikhaylyuk M. Reliable GPU-based methods and algorithms of implementation dynamic relief shadows in virtual environment systems // Proceedings of the 31th International Conference on Computer Graphics and Vision (GraphiCon 2021). 2021. V. 3027. P. 83–94. https://doi.org/10.20948/graphicon-2021-3027-83-94.

  6. Фролов В.A., Волобой А.Г., Ершов С.В., Галактионов В.А. Современное состояние методов расчёта глобальной освещённости в задачах реалистичной компьютерной графики // Труды ИСП РАН. 2021. Том 33. Вып. 2. С. 7–48. DOI: https://ispranproceedings.elpub.ru/jour/article/ view/1384/1222.https://doi.org/10.15514/ISPRAS-2021-33(2)-1

  7. Brawley Z., Tatarchuk N. Parallax Occlusion Mapping: Self-Shadowing, Perspective-Correct Bump Mapping Using Reverse Height Map Tracing // ShaderX3: Advanced Rendering with DirectX and OpenGL. 1st. ed. Charles River Media. 2004. P. 135–154.

  8. Amanatides J., Woo A. A Fast Voxel Traversal Algorithm for Ray Tracing // Proceedings of the 8th European Computer Graphics Conference and Exhibition (Eurographics ’87), Amsterdam. 1987. P. 3–10. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3443.

  9. Fan Z., Sun H., Xu L., Lee K. L. Parallel-Split Shadow Maps for Large-Scale Virtual Environments // Proceedings of the 2006 ACM International Conference on Virtual Reality Continuum and its Applications (VRCIA’06), Association for Computing Machinery. New York. 2006. P. 311–318. https://doi.org/10.1145/1128923.1128975.

  10. Dimitrov R. Cascaded shadow maps // Developer Documentation. NVIDIA Corp. 2007. http://developer.download.nvidia.com/SDK/10/opengl/samples.html#cascaded_shadow_maps.

  11. Bunnell M., Pellacini F. Shadow Map Antialiasing // GPU Gems: Programming Techniques, Tips and Tricks for Real-Time Graphics. 1st. ed. Addison-Wesley. 2004. P. 185–192. https://developer.download.nvidia.com/books/HTML/gpugems/gpugems_ch11.html.

  12. Johnson G.S., Mark W.R., Burns C.A. The Irregular Z-Buffer and its Application to Shadow Mapping // Department of Computer Sciences and Texas Advanced Computing Center of the University of Texas at Austin. 2004. https://www.cs.utexas.edu/ftp/techreports/tr04-09.pdf.

  13. Lefohn A.E., Sengupta S., Owens J.D. Resolution-Matched Shadow Maps // ACM Transactions on Graphics. 2007. v. 26. № 4. article 20. https://doi.org/10.1145/1289603.1289611

  14. Rosen P. Rectilinear texture warping for fast adaptive shadow mapping // Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D 2012). 2012. P. 151–158. https://doi.org/10.1145/2159616.2159641.

  15. Everitt C., Kilgard M.J. Optimized Stencil Shadow Volumes // Game Developer Conference. 2003. https://www.nvidia.com/docs/IO/8230/GDC2003_ShadowVolumes.pdf.

  16. Laine S. Split-plane shadow volumes // Proceedings of Graphics Hardware. Eurographics Association. 2005. P. 23–32. https://doi.org/10.1145/1071866.1071870. https://users.aalto.fi/~laines9/publications/laine2005gh_paper.pdf.

  17. Stich M., Wächter C., Keller A. Efficient and Robust Shadow Volumes Using Hierarchical Occlusion Culling and Geometry Shaders // GPU Gems 3. Addison-Wesley Professional. 2007. P. 239–256. https://developer.nvidia.com/gpugems/gpugems3/part-ii-light-and-shadows/chapter-11-efficient-and-robust-shadow-volumes-using.

  18. Sintorn E., Olsson O., Assarsson U. An Efficient Alias-free Shadow Algorithm for Opaque and Transparent Objects using per-triangle Shadow Volumes // ACM Transactions on Graphics. 2011. v. 30. № 6. article 153. DOI. http://portal.acm.org/ft_gateway.cfm?id= 2024187&type=pdf.https://doi.org/10.1145/2024156.2024187

  19. Fu Z., Zhang H., Wang R., Li Z., Yang P., Sheng B., Mao L. Dynamic Shadow Rendering with Shadow Volume Optimization // Advances in Computer Graphics, Proceedings of the 37th Computer Graphics International Conference (CGI 2020). 2020. v. 12221. P. 96–106. https://doi.org/10.1007/978-3-030-61864-3_9.

  20. Sakalauskas T. Hybrid Terrain Shadow Ray Casting // Proceedings of the 16-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG’2008). Plzen. 2008. P. 175–182. http://wscg.zcu.cz/wscg2008/Papers_2008/short/!_WSCG2008_Short_final.zip.

  21. Sanzharov V.V., Gorbonosov A.I., Frolov V.A., Voloboy A.G. Examination of the Nvidia RTX // Proceedings of the 29th International Conference on Computer Graphics and Vision (GraphiCon'2019), Bryansk, Russia (CEUR Workshop Proceedings). 2019. v. 2485. P. 7–12. https://doi.org/10.30987/graphicon-2019-2-7-12.

  22. Policarpo F., Oliveira M.M. Relaxed Cone Stepping for Relief Mapping // GPU Gems 3. Addison-Wesley Professional. 2007. P. 409–428. https://developer.nvidia.com/gpugems/gpugems3/part-iii-rendering/chapter-18-relaxed-cone-stepping-relief-mapping.

  23. Tevs A., Ihrke I., Seidel H.-P. Maximum Mipmaps for Fast, Accurate, and Scalable Dynamic Height Field Rendering // Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games (I3D’08). New York. 2008. P. 183–190. https://doi.org/10.1145/1342250.1342279.

  24. Aslandere T., Flatken M., Gerndt A. A Real-Time Physically Based Algorithm for Hard Shadows on Dynamic Height-Fields // Proceedings of 12. Workshop der GI-Fachgruppe on Virtuelle und Erweiterte Realität, Aachen Verlag, Bonn. 2015. P. 101–112. https://elib.dlr.de/101497/.

  25. Jung D., Schrempp F., Son S. Optimally Fast Soft Shadows on Curved Terrain with Dynamic Programming and Maximum Mipmaps. 2020. https://arxiv.org/pdf/2005.06671.pdf.

  26. Lengyel E. Mathematics for 3D Game Programming and Computer Graphics. 3rd. ed. Course Technology. Boston. 2012.

  27. Ewins J.P., Waller M.D., White M., Lister P.F. MIP-map Level Selection for Texture Mapping // IEEE Transactions on Visualization and Computer Graphics. 1998. V. 4, № 4. P. 317–329. https://doi.org/10.1109/2945.765326

  28. OpenGL Extension. Texture Filter Anisotropic. NVIDIA. 2018. http://www.opengl.org/registry/specs/ EXT/ texture_filter_anisotropic.txt.

  29. Large Geometric Models Archive, Georgia Institute of Technology. https://www.cc.gatech.edu/projects/ large_models/.

Дополнительные материалы отсутствуют.