Mathematical justification of efficiency of low-polygonal modeling in problems of constructing dynamic shadows of three-dimensional objects

Borevich Ekaterina Vladislavovna Assistant, Department of Engineering Graphics and Design, Peter the Great St. Petersburg Polytechnic University 195251, Russia, g. Saint Petersburg, ul. Politekhnicheskaya, 29 plasma5210@mail.ru Other publications by this author     Meshcheriakov Sergei Vladimirovich Doctor of Technical Science Professor, Department of Engineering Graphics and Design, Peter the Great St. Petersburg Polytechnic University 195251, Russia, g. Saint Petersburg, ul. Politekhnicheskaya, 29 serg-phd@mail.ru Other publications by this author

Yanchus Viktor Edmundasovich senior lecturer, Department of Engineering Graphics and Design, Peter the Great St. Petersburg Polytechnic University 195251, Russia, g. Saint Petersburg, ul. Politekhnicheskaya, 29 victorimop@mail.ru Other publications by this author

Введение

Трехмерное моделирование динамических объектов на этапе цифровой постобработки отснятого видео или киноматериала не требуется в реальном режиме времени, но является сложным и затратным процессом с точки зрения длительности и объема геометрических вычислений ^[1]. После захвата движения персонажа и его переноса в виртуальную 3D сцену необходимо заново воссоздавать утраченные тени всех динамических трехмерных объектов в каждом кадре видеоматериала ^[2]. Эти цифровые технологии связаны с так называемой проблемой «больших данных» (big data) ^[3] и требуют значительных компьютерных ресурсов памяти и процессоров, имеющихся главным образом в крупных киностудиях и IT компаниях с распределенными вычислительными комплексами ^[4].

Авторами предложен новый подход к трехмерному моделированию, который позволяет более эффективно решать задачи воссоздания реалистичных теней динамических 3D объектов за счет радикального сокращения объема геометрических вычислений без ухудшения качества видеоматериала. Приведено математическое обоснование выбора низкополигональной поверхностной модели 3D объектов, и дана сравнительная оценка эффективности нового подхода. Разработанные вычислительные методы реализованы программно, апробированы на практике в одном из короткометражных видеопроектов и рекомендованы к применению в небольших IT компаниях, виртуальных 3D видеостудиях без макетов и декораций и даже в домашних условиях.

Математическая модель распределения освещенности 3D сцены

Для достижения реалистичности изображений теней их вычисление требует учета следующих характеристик освещенности 3D сцены и переменных параметров источников света:

— количество, удаленность, мощность, динамика изменения источников света, которые влияют на четкость контуров теней;

— спектральный состав и длина волны источников света, влияющие на яркость и интенсивность затухания освещенности;

— влажность, физико-химический состав воздуха, его концентрация и другие характеристики прозрачности, которые влияют на рассеяние света;

— материалы, текстура, цвета объектов 3D сцены, которые влияют на диффузное отражение света;

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

В задаче построения теней не требуется учитывать абсолютно все факторы освещенности 3D сцены, такие как поглощение, пропускание, преломление света и пр., поэтому исследованы только те параметры света, которые влияют на формирование теней. Такая модель освещенности является суммарной трех составляющих интенсивности света — рассеяние, диффузное и зеркальное отражение ^[5]:

(1)

где — интенсивность рассеянного света; — коэффициент диффузного отражения материала поверхности, причем для черной поверхности и для белой; — интенсивность диффузного отражения; — интенсивность зеркального отражения.

Для зеркальной и диффузной составляющих отражения света расчетные схемы приведены соответственно на рис. 1 и рис. 2.

Рис. 1. Модель зеркального отражения направленного потока света от гладкой поверхности: L — направление к источнику света; — угол рассеяния света; N — вектор нормали к поверхности; R — вектор зеркального отражения света; — угол зеркального отражения; S — направление на точку наблюдения; — угол между вектором зеркального отражения R и направлением на точку наблюдения S

Рис. 2. Модель диффузного отражения света от шероховатой поверхности

Интенсивность диффузной составляющей традиционно вычисляется по известному закону косинусов Ламберта ^[6], согласно которому диффузное рассеяние отраженного света от шероховатой поверхности в разных направлениях разное по силе с максимальным значением в направлении нормали к поверхности (рис. 2):

(2)

где — интенсивность направленного источника света, падающего на поверхность; — угол между направлением к источнику света и нормалью к поверхности N (рис. 1); dΩ и dA — изменение угла диффузного рассеяния отраженного света и амплитуды силы света соответственно.

Модель (2) не учитывает зависимость силы света от расстояния до объекта, который становится ярче с приближением к источнику света и наоборот темнее по мере удаления:

(3)

где E — сила энергии источника света; D — удаленность источника света от поверхности отражения.

На практике расстояние до удаленных источников света (солнце, луна, уличные фонари) может намного превышать расстояние от объекта до точки наблюдения, поэтому можно заменить его постоянным коэффициентом:

(4)

где — коэффициент удаленности источника света; d — расстояние от объекта до наблюдателя или съемочной камеры.

Объединение выражений (1)–(4) дает модель освещенности объекта с учетом интенсивности диффузного отражения:

(5)

Коэффициент диффузного отражения в математическом выражении (5) может принимать различные значения для цветных материалов поверхности. Согласно классической теории цвета Иттена ^[7], модель зрительного восприятия глаза человека является композицией трех независимых каналов — красного, зеленого и синего (RGB — red, green, blue). Значит интенсивность диффузно отраженного от цветной поверхности света является суммой интенсивностей каждого из трех RGB цветов:

(6)

где — интенсивности диффузного отражения света соответственно красного, зеленого и синего цветов.

Интенсивность диффузного отражения каждого из RGB цветов в отдельности оценивается формулой (5) с разными коэффициентами:

(7)

где — интенсивности рассеянного света соответственно красного, зеленого и синего цветов; — коэффициенты диффузного отражения материала поверхности соответственно красного, зеленого и синего цветов; — сила энергии источника соответственно красного, зеленого и синего света.

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

— угол падения луча к поверхности отражения;

— цвет, длина волны падающего света;

— физические свойства материала поверхности, его оптические отражающие свойства.

Для идеально гладкой поверхности угол падения луча равен углу отражения (рис. 1), но в реальности поверхности всех материалов являются шероховатыми, поэтому интенсивность зеркальной составляющей отражения света описывается известной моделью Фонга ^[8]:

(8)

где — угол падения луча к поверхности отражения; — длина волны падающего света; — коэффициент зеркального отражения, зависящий от угла падения луча и длины волны и определяемый экспериментально; p — коэффициент шероховатости поверхности, причем для шероховатых поверхностей и для идеально гладких; — угол между вектором зеркального отражения R и направлением на точку наблюдения S (рис. 1).

С учетом выражения для зеркальной составляющей (8) модель освещенности объекта одним направленным источником света (5) имеет вид:

(9)

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

(10)

где q — коэффициент рассеяния света, причем 1 ≤ q ≤ 20, q = 20 для узконаправленного света (как лазерный луч), q = 1 соответствует равномерному заливающему освещению и полному отсутствию теней у объектов сцены.

С учетом разнонаправленных источников света i модель освещенности 3D сцены имеет вид:

(11)

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

Постановка задачи геометрического построения теней 3D объектов

Геометрически постановка задачи построения теней 3D объектов означает вычисление их центральных проекций на поверхности 3D сцены от направленных источников света (рис. 3), математические модели которых рассмотрены в предыдущем разделе.

Рис. 3. Построение теней как центральных проекций 3D объектов на поверхность от направленного источника света

Поставленная задача разделена на 2 части:

1. Вычисление линии очерка на поверхности 3D объекта, разделяющей видимую и невидимую области объекта, которые отображаются по-разному со стороны наблюдателя. Для разных точек наблюдения и при движении 3D объекта необходимо каждый раз вычислять линии очерка заново.

2. Вычисление центральной проекции линии очерка на поверхность 3D сцены и цветокоррекция полученных областей тени, отбрасываемой от 3D объекта.

Линия очерка вычисляется как пространственная кривая, в каждой точке которой радиус-вектор r(u, v) нормали поверхности 3D объекта перпендикулярен вектору, направленному к источнику света. При перемещении по поверхности 3D объекта через линию очерка знак радиус-вектора r(u, v) меняется на противоположный. Это свойство использовано для вычисления координат точек линии очерка, лежащих на поверхности 3D объекта, с некоторым шагом t, определяющим точность вычислений.

Такая постановка задачи позволяет ее решить известными геометрическими методами ^[9] по итерационному алгоритму в 2 этапа:

1. На первом этапе итерационного процесса определяется начальная точка линии очерка. Ее координаты вычисляются путем перемещения по поверхности 3D объекта в любом направлении с заданным шагом t до тех пор, пока радиус-вектор r(u, v) не поменяет знак в двух соседних точках и . Координаты начальной точки вначале аппроксимируются известным методом хорд:

(12)

а затем более точно вычисляются известным итерационным методом касательных Ньютона:

(13)

где m(u, v) — нормаль поверхности 3D объекта r = r(u, v) в точке ; , — производные касательной плоскости, которые вычисляются известными деривационными формулами Вейнгартена ^[10].

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

(14)

где w — радиус-вектор w = w(u, v) точки наблюдения.

Выражения (13) и (14) означают большой объем вычислений в каждом кадре для всех полигонов 3D объектов. Тем не менее расчеты можно значительно сократить за счет обоснованного упрощения полигональной модели. В задаче построения теней не требуется высокой степени детализации персонажа, в том числе его лица (рис. 4), и изображения теней будут такими же реалистичными при замене модели на низкополигональную. Далее дано ее математическое обоснование.

Рис. 4. Низкополигональное моделирование 3D персонажа четырехугольными полигонами

Математическое обоснование и сравнительная оценка эффективности низкополигонального моделирования

В задаче построения теней динамических 3D объектов использовано поверхностное моделирование на четырехугольной полигональной сетке (рис. 4). Но математическое обоснование эффективности низкополигональной модели выполнено на треугольных полигонах, т. к. известен достаточно хорошо изученный математический аппарат триангуляции ^{[5, 9]}, а треугольники можно легко получить из четырехугольных полигонов путем добавления диагонального ребра. При этом для некоторого числа точек полигональной сетки n количество треугольников будет в 2 раза больше, чем четырехугольников, но это не влияет на сравнительную оценку объема геометрических вычислений O(n) для обоих видов полигональной модели.

Пусть имеется триангуляция выпуклой поверхности S, состоящая из n точек. Для перехода к низкополигональной модели необходимо объединить треугольники и тем самым сократить их количество в пределах имеющейся полигональной сетки S. Для этого использован известный алгоритм Киркпатрика ^[11], согласно которому количество треугольников уменьшается путем циклического удаления вершин и соединенных с ними ребер. Каждый i-й цикл преобразования триангуляции с количеством треугольников состоит из следующих шагов:

1. Из триангуляции удаляются несмежные вершины (не соединенные между собой ребром).

2. Из триангуляции удаляются все ребра, соединенные с удаленными на шаге 1 вершинами.

3. Если после шагов 1 и 2 остаются многоугольники с числом ребер r>3, то они преобразуются в треугольники путем добавления недостающих r–3 ребер, вследствие чего из каждого r-угольника образуется r–2 треугольника.

Результатом каждого i-го цикла выполнения шагов 1–3 является новая триангуляция с меньшим количеством треугольников . В конечном итоге получается последовательность триангуляций T:

(15)

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

Описанный алгоритм может быть реализован программно. Расчетная последовательность триангуляций T в выражении (15), их ребер и вершин формирует многоуровневый набор данных большого размера. Производительность итерационного процесса сокращения количества треугольников и их вершин, т. е. понижения степени детализации модели до уровня низкополигональной, зависит от варианта организации иерархии данных ^[12]. Традиционные модели иерархических данных в зависимости от глубины вложенности далеко не всегда эффективны по причине наличия рекурсии в вычислениях. Более эффективные нерекурсивные модели описания иерархических объектов и их программную реализацию можно заимствовать в работах ^{[13, 14]}.

Кроме модели данных, важно правильно определить стратегию алгоритма выбора удаляемых вершин треугольников за одну итерацию . Чем меньше степень вершины, т. е. число соединенных с ней ребер, тем большее их количество можно удалить за одну итерацию на шаге 1 и тем выше результативность процесса. И наоборот, чем больше степень удаляемой вершины, тем больше остается ребер многоугольников, у которых необходимо дополнительно вычислять ребра для триангуляции на шаге 3. Помимо быстродействия этого процесса, важно также получить достаточно низкую результирующую размерность триангуляции по сравнению с исходной, т. к. чем меньше число треугольников и их вершин, тем меньше объем геометрических вычислений в задаче построения теней.

Сказанное продемонстрировано ниже на примере последовательности из четырех триангуляций . На рис. 5 стрелками указаны вершины треугольников, удаленные в каждой триангуляции на шаге 1 и 2 с добавлением недостающих ребер на шаге 3. Так в триангуляции удалены 2 вершины и добавлено 4 ребра для образования треугольников 12–14 и 15–17 в последующей триангуляции , в результате чего число треугольников снижено с 11 до 7. В триангуляции удалены 2 вершины и добавлено 1 ребро для образования треугольников 18 и 20 в последующей триангуляции , в результате чего количество треугольников снизилось еще с 7 до 3. Наконец, в триангуляции удалена 1 вершина, и в конечном итоге остался 1 треугольник.

Рис. 5. Демонстрация алгоритма сокращения количества треугольников в триангуляции

В результате преобразований всей последовательности триангуляций получены наборы значений количества треугольников и их вершин на полигональной сетке:

(16)

(17)

Из полученных выражений (16) и (17) следует, что уменьшение детализации триангуляции подчиняется геометрической прогрессии с некоторым усредненным коэффициентом :

(18)

(19)

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

(20)

(21)

Следовательно, возвращаясь к четырехугольным полигонам, их общее количество на полигональной сетке Q в 2 раза меньше количества треугольников в триангуляции T и оценивается выражениями:

(22)

(23)

Отсюда следует, что в рассмотренном примере (рис. 5) уменьшение степени детализации полигональной сетки в задаче построения теней 3D объектов дает экономию объема геометрических вычислений как минимум в 4 раза:

(24)

Применим другой альтернативный метод сравнительной оценки объема вычислений ^[15], согласно которому общие затраты на все операции на выпуклой трехмерной поверхности зависят логарифмически от количества точек вычисляемой поверхности:

(25)

Данный метод оценки объема вычислений показывает достигнутую эффективность в 5 раз в рассмотренном примере (рис. 5), что свидетельствует о правильности применяемого подхода и достоверности полученных в формулах (16)–(24) результатов:

(26)

На практике кинокадр содержит сотни динамических 3D объектов, моделируемых сотнями тысяч полигонов каждый, а степень их детализации зависит от разрешения экрана и удаленности 3D объекта в кадре. Разрешающая способность современных цифровых систем составляет 1200 пиксел с частотой 50 кадров в секунду (стандарт full HD) и 4–12 К пиксел в 2D–3D кинотеатрах (стандарт IMAX). До 10К полигонов 3D модель считается низкополигональной, значит максимальный эффект от ее использования в задаче построения теней может составить, согласно формулы (25), почти 150 раз:

(27)

Предложенные методы и алгоритмы низкополигонального моделирования успешно апробированы на практике при реализации видеопроекта воссоздания реалистичных теней в фильме Е. Шварца «Тень» ^[16], представленном на ежегодном международном молодежном фестивале короткометражного кино MovieArtFest–2017 ^[17]. На рис. 6 наглядно продемонстрированы кинокадры временной замены 3D объекта на низкополигональную модель компьютерными средствами трехмерной графики Autodesk Maya ^[18] и результат воссоздания реалистичных теней персонажа фильма.

а) выделение трехмерного объекта (персонажа) в реальном кинокадре фильма Е. Шварца «Тень»

б) замена персонажа на низкополигональную 3D модель компьютерными средствами Maya

в) построение теней низкополигональной 3D модели от двух источников света (луна и уличный фонарь)

г) обратная замена низкополигональной 3D модели на реальный трехмерный персонаж

Рис. 6. Пример воссоздания реалистичных теней персонажа путем замены на низкополигональную 3D модель в реконструкции фильма Е. Шварца «Тень»

Выводы

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

1. Применительно к задаче построения теней 3D объектов на этапе постобработки видеоматериала, целесообразно снижать степень детализации 3D модели до уровня низкополигональной, что позволяет значительно сократить объем геометрических вычислений без ущерба качеству и реалистичности видеоматериала.

2. Математическое обоснование низкополигонального моделирования 3D объектов подтверждает достоверность полученных результатов и эффективность вычислений от 5 до 150 раз в зависимости от разрешения экрана и относительного размера 3D объекта в кинокадре.

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