Параллельные и распределенные архитектуры
Коммерческие графические аппаратные средства

Методы рендеринга объемов можно классифицировать как: рендеринг прямого хода (forward rendering) и рендеринг обратного хода (backward viewing). В рендеринге прямого хода производится обход всех вокселей объема в объектном пространстве. В алгоритме BTF (back-to-front - от заднего плана к переднему) порядок обхода определяется уменьшением расстояния до вокселей, а в алгоритме FTB (front-to-back - от переднего плана к заднему) порядок обратный. В методах обратного хода лучи испускаются из глаза в направлении каждого пикселя экрана.

Параллельные и распределенные архитектуры

Есть большое число разнообразных адаптаций алгоритмов видового преобразования для параллельной реализации. Это и традиционные методы прямого рендеринга объема, а также гибридные подходы, адаптированные для параллельных процессоров.

Построение вида параллельными методами прямого хода

Обычно для параллельных реализаций рендеринга объема используются метод множественных преобразований и метод сплатинга. Первый заключается в разложении трехмерной видовой матрицы в серию одномерных сдвигов и маштабирований по ортогональным осям. Одномерный сдвиг приводит к регулярной подкачке данных вдоль оси сдвига и, следовательно, декомпозиция видового преобразования в последовательность сдвигов является полезной. В двух работах этот метод реализован для рендеринга в объектном пространстве на процессорах SIMD (Single Instruction Multiple Data). В реализации для системы Maspar MP-1 пучки вокселей привязываются к тороидально соединенным процессорам. В этой реализации оптимизации обменов данными возлагается на эффективную межпроцессорную сеть MP-1. В другой реализации для CM-2 явное распределение или виртуализация данных не проводится, и применяется косвенная адресация, а межпроцессорный обмен данными исключается вплоть до фазы смешивания алгоритма рендеринга. Эта реализация, однако, имеет два недостатка: требуется большее число проходов для генерации одномерных интерполированных выборок данных, не поддерживается перспективная проекция.

Сплатинг - это еще один метод реконструкции. Самая ранняя реализация сплатинга была выполнена на сети из нескольких машин Sun. Воксельный объем может обходиться в либо от переднего плана к заднему (FTB), либо наоборот (BTF). Некоторое подмножество вокселей объема передается в N2 процессов, которые параллельно выполняются в сети. Эти процессы преобразуют воксели, производят их сплатинг и отображают на отдельные куски плоскости изображения, которые затем посылаются в N процессов для сочленения. Аналогичный алгоритм реализован на IBM Power Visualization System (PVS) где применена схема вычислений, обеспечивающая высокую эффективность преобразований путем использования инкрементальных векторизованных вычислений. Кроме того, объем статически делился на упорядоченное множество пачек, объединяющих некоторое количество срезов объема. Каждый срез в пачке независимо преобразовывался, закрашивался, подвергался сплатингу и смешивался с построенной к этому времени локальной частью изображения. Чтобы иерархически объединить все эти локальные части и получить конечное изображение, использовался алгоритм с древовидной структурой. Таким образом, передача данных между узлами требовалась только на завершающей стадии, что обеспечивает хорошую масштабируемость.

В реализации на архитектуре Pixel Planes 5 графические процессоры выполняют преобразование и закраску вокселей, в то же время процессоры рендеринга делают сплатинг и получают поток команд от графических процессоров. Каждому процессору рендеринга сопоставлена определенная область экрана. На данный процессор рендеринга посылаются только те воксели, которые отображаются на выделенную ему экранную область. Для того, чтобы выбрать, какому из процессоров рендеринга требуется послать ту или иную команду, требуется отдельный шаг сортировки. Графический процессор ожидает, пока пересылаемый элемент данных достигнет его, прежде чем он может послать следующий срез для рендеринга. В период ожидания он выполняет преобразование следующего назначенного ему среза. Недостаток этой реализации состоит в том, что для каждого среза требуется выполнять сортировку.

Эффективный сдвиговый алгоритм был также распараллелен для архитектур с разделяемой памятью SGI Challenge и TMC CM-5. В первом случае время синхронизации минимизируется посредством динамической балансировки нагрузки и такого разбиения задачи, которое минимизирует число событий, требующих синхронизации. Алгоритм основывается на аппаратной поддержке межпроцессорных соединений с малым временем ожидания и аппаратном кэшировании для уменьшения периодов ожидания.

Построение вида параллельными методами обратного хода

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

Реализация трассировщика лучей на Intel iPSC/2 использует чисто статическую схему распределения данных. Сканирующие линии делятся черезстрочно между процессорными кластерами. Объемные данные целиком дублируются на всех кластерах, каждый узел кластера получает свою пачку срезов. Узел выполняет трассировку луча только внутри своего подобъема. Используется подход луч - поток данных, в котором луч разбивается на несколько порций и каждая порция трассируется индивидуально. Позднее, когда все узлы завершают работу, все эти порции комбинируются и получается истинный цвет. Данная схема может привести к сбалансированной по загрузке и масштабируемой реализации, а схема распределения данных хорошо ложится на сеть межпроцессорных связей типа Hypercube.

Реализация на многопроцессорной рабочей станции Silicon Graphics похожа по духу на реализацию для CM-2. Объем поворачивается вокруг направления наблюдения, а затем производится отслеживание множества параллельных лучей. Для распределения срезов по множеству узлов используется динамическая схема загрузки данных. Преобразования отдельных срезов выполняются эффективным методом инкрементальных преобразований.

Отслеживатель лучей был реализован на MPP-системе Fujitsu AP1000 MIMD. Для динамического распределения квадратных областей пикселей между вычислительными ячейками была применена парадигма "хозяин-слуга". Адаптивность схемы распределения достигается посредством того, что когда "слуги" затрачивают больше времени для рендеринга своей части изображения, чем было выделено, они уведомляют об этом "хозяина", который делает более мелкое разбиение областей изображения. Для поддержки динамической схемы объем дублируется на кластерах из соседних ячеек.

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

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

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

Параллельные гибридные методы

Гибридные методы не привлекли такого же внимания, как чистые методы прямого и обратного хода. Известны лишь две реализации. Метод, реализованный в одной из них, применим к аффинным преобразованиям - преобразование расщепляется на серию сдвигов, по которым определяется адрес вокселя в преобразованном пространстве. Это адрес используется для интерполяции в объектном пространстве и получения значений точек выборки. Преимущество такой схемы вычисления адреса заключается в том, что подкачка данных для интерполяции требуется только из ближайшей окрестности и является регулярной. На заключительном этапе требуется еще один шаг подкачки данных для реального переупорядочения преобразованного объема. Гибридный метод реализован и на IBM PVS. Объемные данные разбиваются на подкубы и присваиваются различным процессорам. В пространстве изображения определяется преобразованные границы этих подкубов, в пределах которых выполняется построчное сканирование изображения и интерполяция в объектное пространство. Для получения точек в объектном пространстве применяется эффективное обратное инкрементальное преобразование.

Недавно был предложен метод Активных Лучей, использующий когерентность в объектом пространстве. Данные делятся на ячейки, которые распределяются случайным образом между процессорами. Находятся точки пересечения лучей с границами ячеек. Каждый луч помещается в очередь, привязанную к той ячейке, которую он пересекает первой. Ячейки закачиваются в память по мере потребности в порядке от переднего плана к заднему. Лучи, содержащиеся в очереди ячейки, которая выбрана в память процессора, отслеживаются в пределах ее границ. Луч либо останавливается из-за накопления непрозрачности, либо помещается в очередь ячейки, которая встретится ему следующей. Этот гибридный метод пожинает плоды и от упорядочения в пространстве изображения - быстрая остановка луча, и от упорядочения в объектном пространстве - регулярность обхода объема.

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

Коммерческие графические аппаратные средства

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

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

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

Коммерчески доступные аппаратные средства нанесения объемной текстуры позволяют наложить на полигональные объекты трехмерный растр (объем). Трехмерные растры, называемые 3D текстурными картами, налагаются на полигоны в 3D с использованием интерполяции нулевого или первого порядка. Визуальный образ прямоугольного множества объемных данных строится путем рендеринга полигонов, являющихся срезами объема и перпендикулярных к направлению наблюдения [23]. Производя рендеринг полигонов в порядке от заднего плана к переднему и смешивая их в буфере кадра, мы получаем правильное изображение объема.