«Разработка методов распределения процедур рендеринга трехмерных изображений»

Согласно закону Мура[4], количество транзисторов каждые два года должны удваиваться, а, следовательно, и мощность вычислительных устройств должна расти экспоненциально. Так как увеличение тактовой частоты процессора стало невозможным[3], акцент был сделан на многоядерных процессорах. Параллельные вычисления обычно реализуются с использованием многоядерных процессоров. Процесс рендеринга изображений очень хорошо вписывается в модель параллельных вычислений. Каждое ядро процессора может выполнять обработку отдельного кадра или даже отдельной части изображения. Но даже несмотря на это, мощности одного многоядерного процессора может быть недостаточно. Поэтому при рендеринге комплексных анимационных сцен или фотореалистичных изображений не редко используются группы компьютеров - вычислительные кластеры. Кластеры позволяют использовать мощь нескольких вычислительных узлов для параллельной работы над задачей.

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

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

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

• Проанализировать современные алгоритмы и методы рендеринга[5] 3D изображений, выбрать из них наиболее вычислительно-трудоёмкий;

• Реализовать выбранный алгоритм рендеринга

• Разработать метод распределения и распараллеливания выбранного алгоритма рендеринга используя модель акторов

Объектом исследования ВКР является 3D визуализация.

Предметом исследования ВКР являются методы распределения и распараллеливания алгоритмов пре-рендеринга 3D изображений

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

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

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

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

Рендеринг используется в самых разных областях: в архитектуре, видео-играх, симуляторах, киноиндустрии, телевидении, а также для создания прототипа дизайна (например, дизайна квартиры).

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

Метод растеризации

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

По сравнению с другими методами рендеринга, метод растеризации является очень быстрым. Тем не менее, метод растеризации, по сути, является простым процессом сопоставления объектов из сцены на пиксели экрана. Метод не имеет каких-либо строго определенных путей для вычисления цвета пикселей. Процесс растеризации 3D модели в двумерное пространство часто выполняется с помощью специальных функций аппаратного обеспечения в графическом конвейере (graphic pipeline).

Принцип работы

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

Преобразования

Основными преобразованиями в методе растеризации являются сдвиги, масштабирование, повороты и проекция[9].

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

где X, Y и Z – смещения в трехмерном пространстве.

Масштабирование производится с помощью умножения координаты вершины на скалярную величину. Масштабирование может быть представлено с помощью следующей матрицы:

где X, Y и Z – значения, на которые умножаются значения координаты.

Поворот матриц зависит от оси вокруг которой будет поворачиваться координата.

Поворот относительно оси X:

Поворот относительно оси Y:

Поворот относительно оси Z:

где θ – угол поворота

Набор операций сдвига, масштабирования и поворота логически описывают большинство преобразований. Система растеризации обычно использует стек преобразований для перемещения потока вершин на какое-либо место другое место[9].

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

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

где F – расстояние до самого дальнего объекта, а N – до самого ближнего. Результирующий вектор будет вектором где значение однородной переменной не равняется единице. В результате умножение вектора на однородную переменную с противоположным знаком мы получим X, Y координаты в 2D пространстве.

Метод трассировки лучей

Трассировка лучей (англ. Ray tracing; рейтрейсинг) —технология построения фотореалистичных изображений сложных сцен, с учетом таких эффектов как отражение и преломление, при которых отслеживается обратная траектория распространения луча (от камеры к источнику).

Принцип работы

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

ИСПОЛЬЗОВАННЫЕ СРЕДСТВА И ТЕХНОЛОГИИ

Язык программирования Scala

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

Scala - универсальный язык программирования, который работает на платформах JVM и. NET. В связи с активным появлением новых языков программирования для JVM,. NET и других платформ, возникает вопрос, с которым сталкивается каждый программист: какой язык программирования изучать? Какие из языков уже готовы для применения в корпоративных масштабах? Чем Scala лучше многих других языков программирования, например, таких как Groovy, Ruby, Clojure, Erlang, и F#? Чтобы ответить на эти вопросы нужно сначала понять чем является Scala.

Язык Scala используется для написания приложений в различных предметных областях, включая телекоммуникации, социальные сети, Semantic Web и банковское дело. Например, библиотека с открытым исходным кодом Apache Camel использует Scala для создания своего собственного предметно-ориентированного языка создания правил маршрутизации. Веб-фреймворк Lift это мощный фреймворк построенный с использованием Scala. Он использует в себе все преимущества языка, такие как лаконичность, выразительность, сопоставление с образцом и высокая абстракция при написании многопоточного кода.

Что такое Scala?

Мартин Одерски (создатель Scala) и его команда приступила к разработке на Scala в 2001 году в лаборатории методов программирования в EPFL (Федеральная политехническая школа Лозанны). Язык Scala был дебютирован в январе 2004 года, в то время он использовал платформу JVM, но через несколько месяцев спустя появилась и версия языка для .NET платформы.

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

Язык интегрирует как особенности объектно-ориентированного так и особенности функционального языка программирования, что позволяет программистам быть более продуктивным.

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

Тем не менее, есть одна оговорка: краткость языка Scala иногда может приводить к трудночитаемому коду. Операторы и конструкции в Scala могут выглядеть странными для новичка. Синтаксис языка не является легким для изучения. Но с приобретением опыта программирования на языке Scala, подход к написанию кода кардинально меняется – программист избегает написания трудночитаемого кода, и соответственно написанный код становится не только более легким для понимания, но и более легким для поддержания.

Некоторые ключевые достоинства языка:

• Имеет встроенную событийно-управляемую модель обработки конкурентных программ.

• Поддерживает как императивный стиль, так и функциональный

• Полностью объектно-ориентирован

• Предоставляют легкое взаимодействие с Java программами

• Обеспечивает статическое типизирование

• Является кратким и выразительным

• Основан на небольшом ядре

• Является масштабируемым языком

• Позволяет писать меньше программного кода, при этом достигая большего результата

Scala на плфтформе .NET.

В настоящее время поддержка платформы .NET не стабильна. По информации с официального сайта языка программирования Scala (w*w.scala-lang.org), в настоящий момент Scala может компилировать программы для .NET платформы, но некоторые библиотеки не поддерживается. Основная трудность при поддержке .NET платформы возникает потому, что язык Scala часто использует Java JDK , который не доступен из коробки на платформе .NET.Чтобы решить эту проблему, нынешняя стратегия заключается в использовании утилиты IKVM (w*w.ikvm.net), которая позволяет преобразовывать Java-программы в промежуточный код для платформы .NET.

Scala как объектно-ориентированный язык

Популярность таких языков программирования как Java, C # и Ruby привела к широкому распространению объектно-ориентированного программирования (ООП). ООП, как следует из названия, это парадигма программирования, которая оперирует объектами. Объекты это структуры данных, которые состоят из полей и методов. ООП помогает создавать структурированные программы, используя классы и объекты. Парадигма ООП облегчает процесс написания программ, т.к. с помощью ООП можно создавать крупные приложения, формируя программу из небольших кусков (классов). Есть много ООП языков, но лишь немногие из них являются чисто объектно-ориентированными.

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

• Были проанализированы современные методы визуализации изображений.

• Был отобран один из самых качественных, но трудоемкий метод визуализации – трассировка лучей (ray tracing).

• Был реализован базовый алгоритм метода трассировки лучей, поддерживающий распараллеливание с помощью модели акторов.

• Был реализован метод распределенного рендеринга на основе модели акторов.

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

К достоинствам разработанного метода можно отнести следующее:

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

• Горизонтальная масштабируемость: для подключения нового узла к вычислительному кластеру достаточно лишь установить и запустить программу-клиента на новом узле. После чего новый узел также как и остальные будет задействован в процессе визуализации.

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

9. Rasterization. h**t://en.wikipedia.org/wiki/Rasterisation