Рони Ягель
Кафедра информатики, Университет шт. Огайо, США
yagel@cis.ohio-state.edu

Алгоритмическая оптимизация
Взгляд в будущее
Литература

Задача рендеринга в реальном времени объемных данных - сегодня объект приложения усилий многих исследовательских групп. Оценка количества вычислений, требующихся для рендеринга объема с высоким разрешением в реальном времени, составляет сотни TFLOPS. И, тем не менее, потребность в таком рендеринге постоянно возрастает со стороны нарождающихся технологий, таких, как виртуальная хирургия и быстрое прототипирование. Существует пять основных подходов, чтобы победить кажущиеся непреодолимыми барьеры повышения производительности: 1) уменьшение количества данных путем построения модели; 2) разработка специализированных аппаратных устройств; 3) оптимизация существующих и изобретение более быстрых алгоритмов; 4) реализация на параллельных архитектурах общего назначения, и 5) использование современной графической аппаратуры. Попытаемся оценить ресурсы, необходимые для выполнения объемного рендеринга с высоким разрешением в реальном времени и проведем обзор современного состояния исследований в области быстрого рендеринга.

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

Главным недостатком объемов является их размер. Объем со средним разрешением 256*256*256 требует хранения 16 млн. вокселей. Чтобы сгенерировать изображение трехмерного объекта на 2D экране, требуется обработать все это количество вокселей. Однако, объем имеет и ряд важных достоинств: он может представлять внутренность объекта, а не только внешний слой. Рендеринг и обработка зависят не от сложности или типа объекта, а только от разрешения объема. Легко могут быть реализованы такие операции, как вычитание, сложение, детектирование столкновений и деформация. Полное сравнение двух главных методов представления приводится в [1].

Хотя вычислительная мощность, требуемая для рендеринга объема, колоссальна, настолько же велики и выгоды от некоторых потенциальных приложений, базирующихся на этом подходе. Например - моделирование хирургических операций на виртуальном пациенте [2]. Вначале пациент "оцифровывается" посредством медицинских сканеров: томографических (CT), магнитно-резонансных (MRI) или ультразвуковых. Затем можно спланировать, отрепетировать и построить альтернативный план хирургической операции на цифровой модели в безопасной виртуальной среде. Очевидно, что такой медицинский "летный тренажер" должен вести себя так - же как и "реальный мир", чтобы максимизировать переносимость навыков в действительную практику. Кроме этого, взаимодействие в реальном времени является наиболее существенным требованием - врач предпочтет оперировать в интерактивной среде, даже если она изображается не слишком реалистично.

Самый простой путь для построения визуального образа - это обойти весь объем, рассматривая каждый воксель как 3D точку, которая преобразуется по матрице видового преобразования, затем проецируется в Z-буфер и рисуется на экране. Такой способ визуализации называют рендерингом в объектном пространстве (object-space rendering) или рендерингом прямого хода (forward rendering).

Другой алгоритм - BTF (back-to-front) по-существу совпадает с методом Z-буфера, и отличается только предварительной сортировкой массива вокселей, которая позволяет сканировать его компоненты в порядке уменьшения или увеличения расстояния до наблюдателя. Используя предварительно отсортированные массивы вокселей, в BTF-алгоритме обход объема производится в порядке уменьшения расстояния до наблюдателя, а Z-буфер становится не нужен для отсева невидимых вокселей. Алгоритм рисования просто записывает очередной воксель поверх уже отрисованных или смешивает его со значением экрана [3, 4].

Алгоритм FTB (front-to-back) в основном совпадает с BTF, однако в нем воксели обходятся в порядке возрастания расстояния. Это надо отметить, имея в виду, что чистый метод Z-буфера не может обеспечивать рендеринг полупрозрачных материалов, так как воксели отображаются на экран в произвольном порядке. Смешение света основывается на вычислениях, моделирующих его прохождение через разные материалы. Таким образом, можно легко реализовать полупрозрачность и в BTF, и в FTB, поскольку в этих методах объекты отображаются на экран в том же порядке, в котором по сцене проходят световые лучи.

Одна из основных трудностей при использовании описанного простейшего подхода состоит в том, что при преобразовании (например, повороте) дискретного носителя объемных данных требуется правильная реконструкция сигнала и генерация значений данных (выборки) в новых точках сетки. Одно из решений основано на преобразовании каждого среза объема из пространства вокселей в пространство пикселей с использованием для этого 3D афинных преобразований [5,6,7]. Затем с помощью алгоритма FTB осуществляется проецирование на экран и смешивание с проекцией, полученной от предыдущих срезов [8].

В работе [9] предложен другой способ реконструкции для методов прямого хода, работающих в объектном пространстве - алгоритм сплатинга (splatting). Каждый воксель после отображения на экран, размывается по нескольким соседним пикселям с использованием 2D таблицы прямого доступа (таблицы следа). В этой таблице хранятся "отпечатки" вокселей, которые при сплатинге смешиваются с массивом изображения.

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

Простейший метод для формирования новой выборки - двигаться с некоторым шагом вдоль луча, находя воксели, ближайшие к дискретным точкам траектории и выполняя интерполяцию нулевого порядка между ними [15]. Альтернативный способ состоит в том, чтобы брать в качестве точек новой выборки пересечения луча и граней вокселей. Значение точки выборки находится путем интерполяции и затем смешивается с лучом [12]. В более точном алгоритме для вычисления значений равномерно расположенных вдоль луча точек выборки используется интерполяция более высокого порядка [13, 10, 14].

Так как в методе отслеживания лучей (ray casting) - учитываются только первичные лучи, он не позволяет прямо моделировать такие световые явления, как отражение, тени и преломление. В качестве альтернативы мы разработали 3D растровый трассировщик лучей (RRT) [16], в котором рекурсивно обрабатываются и первичные, и вторичные лучи, и, который, таким образом, может создавать "фотореалистичные" изображения. В обычных алгоритмах трассировки лучей (ray tracing) при поиске ближайшего пересечения тестового луча находятся его пересечения со всеми объектами. В нашем подходе, наоборот, для поиска первых вокселей поверхности дискретные 3D лучи проводятся по 3D растру. Встреча непрозрачного вокселя означает, что луч наткнулся на поверхность.

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

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

A = a + A*(1-a) 
Cl = cl * a + Cl * (1-A),

где l обозначает 3 цвета RGB, С и А - цвет и непрозрачность аккумулирующего буфера, с и a - цвет и непрозрачность точки. Простая арифметика дает:

Т = N3 * ((16 tm + 12 ta) + K2 * (3 tm + 8 ta)),

где ta и tm обозначают, соответственно, времена сложения и умножения. Для среднего разрешения и изображения среднего качества (N = 256, K = 3), требуется примерно 1.8 * 109 операций с плавающей точкой (FP) для рендеринга одного кадра или 5.4 * 1010 FP для рендеринга в реальном времени (30 кадров в секунду). Если мы попытаемся осуществить рендеринг объема с большим разрешением и более высоким качеством изображения (N = 512 и К = 5), нам потребуется 4 * 1010 FP на кадр и 1.2 * 1012 FP для рендеринга в реальном времени. Очевидно, что вряд ли можно надеяться в ближайшем будущем на реализацию рендеринга объема в реальном времени без затрат на создание ускорителей процесса обработки, в виде оптимизационных алгоритмов и аппаратных средств.

Всего можно назвать пять основных подходов для преодоления барьера недостаточной производительности: уменьшение количества данных путем построения модели; разработка специализированных аппаратных устройств; оптимизация и изобретение более быстрых алгоритмов; использование параллельных архитектур общего назначения; использование современной графической аппаратуры. Подробно остановимся на оптимизации алгоритмов, а об их реализации на параллельных архитектурах, а также использовании современных графических аппаратных средств речь пойдет в [29].

Алгоритмическая оптимизация

Оптимизация рендеринга прямого хода в объектном пространстве

С целью уменьшения количества вычислений, необходимых для преобразований, было предложено несколько методов, использующих пространственную когерентность между вокселями. Такими методами являются: рекурсивный метод "разделяй и властвуй", предварительно вычисленные таблицы [4], инкрементальные преобразования и преобразования на основе сдвига [5].

Первый метод использует когерентность в пространстве вокселей, представляя 3D объем в виде октантного дерева. Совокупность соседних вокселей, имеющих одинаковые или близкие с некоторой точностью значения, может, при некоторых ограничениях, быть сгруппирована в однородный кубический подобъем. Такой агрегат вокселей может быть преобразован и подвергнут рендерингу, как однородная единицы, а не как совокупность индивидуальных вокселей. Кроме того, поскольку каждый узел октантного дерева содержит восемь октантов одинакового размера, то если задано преобразование родительского узла, можно эффективно вычислить преобразования вложенных октантов. В основе метода таблично управляемых преобразований [4] лежит наблюдение, что преобразование объема включает умножение матричных элементов на целые числа из диапазона [1, ..., N], где N - разрешение объема. Поэтому на короткой стадии предобработки каждому элементу матрицы tij сопоставляется таблица Tij[N] такая, что Tij[k] = tij * k. На этапе преобразования при вычислении координат матричное умножение заменяется выборкой из таблицы.

Метод инкрементальных преобразований основан на том, что преобразование вокселя [x+1, y, z] может быть вычислено по шагам, если известен преобразованный вектор [x", y", z"] вокселя [x, y, z]. При использовании этого метода должны быть преобразованы все элементы объема, в том числе и пустые. Поэтому это больше подходит для параллельных архитектур, в которых желательно поддерживать загрузку вычислительного конвейера. Подход особенно привлекателен для векторных процессоров, так как преобразование множества вокселей [x+1, 1, z], [x+1, 2, z],..., [x+1, N, z], обозначаемого [x+1, 1...N, z], может быть вычислено из преобразования вектора [x", (1...N)", z"], путем добавления к каждому элементу этого вектора одних и тех же трех элементов матрицы.

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

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

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

Экранное преобразование вокселей в методах прямого хода полезно выполнять таким образом, чтобы избежать наложений на те пиксели, которые уже стали непрозрачными. В работе [20] разработан метод динамического экрана, в котором строкам экрана сопоставляется длина пробега непрозрачных пикселей. Видовое преобразование гарантирует, что строка вокселей всегда отображается в строку пикселей. Поэтому при отображении можно сравнивать строки, а не отдельные воксели. Эта идея была позднее адаптирована для ускорения сдвигового алгоритма [6].

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

Оптимизация рендеринга обратного хода в пространстве изображений

Построение вида объема обратным ходом, основанное на методе отслеживания лучей (ray casting), имеет три основных варианта: параллельное ортографическое отслеживание лучей, перспективное отслеживание лучей, трассировка лучей. Первые два метода являются модификациями метода отслеживания лучей, в котором учитываются только первичные лучи от глаза к экрану. Далее среди методов отслеживания лучей можно выделить те, которые поддерживают только параллельные проекции - глаз помещается в бесконечность, а все лучи параллельны одному вектору зрения. Эта схема наблюдения используется в таких приложениях, как биомедицина, где учет перспективы не дает сколь - нибудь ценной дополнительной информации. Возможна реализация альтернативного метода отслеживания лучей, который поддерживает и схему наблюдения с перспективной проекцией. Так как в методе отслеживания лучей учитываются только первичные лучи, он не позволяет прямо моделировать такие световые явления, как отражение, тени и преломление. В качестве альтернативы мы разработали 3D растровый трассировщик лучей (RRT) [16], рекурсивно обрабатывающий и первичные, и вторичные лучи, и который, таким образом, может создавать "фотореалистичные" изображения.

Рассмотрение существующих методов ускорения процесса отслеживания лучей показывает, что большинство из них базируется на одном или на нескольких принципах: когерентность в пиксельном пространстве; когерентность в объектном пространстве; когерентность лучей; когерентность кадров; пространственные скачки (space-leaping).

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

Когерентность в объектном пространстве. Расширение понятия когерентности в пиксельном пространстве на 3D трактуется, как когерентность между вокселями в объектном пространстве. По аналогии можно рассчитывать на допустимость уменьшения выборки вокселей в 3D областях, содержащих одинаковые или близкие значения. Когерентность вокселей была использована в работе [21]. Вначале при прохождении луча рассматривается низкочастотная выборка точек объема - берется большой шаг между точками выборки. Если между двумя соседними точками выборки обнаруживается большая разница значений, между ними выбирается дополнительная точка и тем самым разрешается неопределенность в этой области высоких частот. Недавно эта базовая идея была обобщена с целью снижения объема выборки в любых областях, в которых непрозрачность вносит небольшой вклад или в областях, где объем однороден [22]. Предложенный метод эффективно определяет пустые и почти однородные области, используя для этого пирамиду объемов, в которой хранятся минимальные/максимальные значения вокселей небольшой окрестности и расстояние между этими значениями.

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

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

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

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

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

Иерархическое представление (например, октантное дерево) разбивает объем на однородные области, которые можно представить в виде узлов иерархической структуры данных. В алгоритме [24] перескок пустого пространства осуществляется путем прохода по иерархической структуре данных. Можно также заметить, что прохождение по иерархической структуре данных не эффективно в сравнении с прохождением по регулярной сетке. Однородный буфер комбинирует достоинства обоих представлений. "Информация об однородности", которая кодируется в октантном дереве, может храниться в пустых областях регулярного 3D растра. Это означает, что воксели в однородном буфере содержат либо значения данных, либо информацию о размере пустого октанта, к которому они принадлежат. Лучи, которые проходят внутрь объема, встречают воксель данных или воксель, содержащий "информацию об однородности", которая говорит о том, как выполнить скачок луча вперед до первого вокселя за пределами однородной области [25]. В этом подходе не нужно искать подходящего соседа по дереву - такая операция расходует больше всего времени и является главным недостатком иерархических структур данных.

Если объем состоит из одного объекта, окруженного пустым пространством, обычный простой метод перескока использует хорошо известную технику ограничивающих оболочек. Объект окружается плотно подогнанным параллелепипедом или другим объектом, например, сферой, для которого легко вычислить пересечение. Находится пересечение луча с ограничивающим объектом и обход существенной части объем начинается от этой точки пересечения, а не от границы объема. В методе PARC (Polygon Assisted Ray Casting) [26] делается попытка более точно подогнать оболочку путем использования выпуклых многогранников. PARC использует доступные аппаратные средства для рендеринга передних граней оболочки - с целью определить для каждого пикселя точку входа луча и задних граней - для определения точки выхода луча. Затем луч отслеживается от точки входа до точки выхода. Луч, который не попадает в какой - либо объект, не отслеживается вообще.

Очевидно, что в пустом пространстве не нужно проводить выборку данных - эту часть пространства необходимо как можно быстрее просто пересечь. Поэтому ([16]) в пустом пространстве предлагается использовать один алгоритм генерации линии, быстрый, но грубый, а вблизи и внутри объектов - другой, более медленный, но точный. Эффективность такого подхода зависит от того, насколько эффективно происходит переключение между двумя алгоритмами генерации линий и определяется близость вокселей, принадлежащих объекту. Это достигается тем, что непустые воксели окружаются "облаком" из маркировочных вокселей глубиной в один воксель - всем пустым вокселям, окружающим занятый, на стадии предобработки присваивается специальный "флаг окрестности". Для быстрого прохождения пустой области применяется грубый алгоритм генерации луча до тех пор, пока не встретится воксель окрестности. Тогда происходит переключение на более точный алгоритм.

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

Взгляд в будущее

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

  • Интеграция существующих методов в единый мощный алгоритм, в котором были бы задействованы известные методы ускорения. Одним из примеров этой тенденции является алгоритм сдвига - деформации, который комбинирует рендеринг на основе сдвигов [5], кодирование длины пробега [20], минимаксные пирамиды [22] и многомерные таблицы суммируемых областей.
  • Параллельные реализации на экспериментальных машинах с распределенной разделяемой памятью, использующие преимущества аппаратных кэшей и специализированных связных процессоров.
  • Миграция простых приложений объемного рендеринга на платформу ПК в связи с недавним колоссальным прогрессом в графических платах.
  • Увеличивающееся использование существующих графических машин общего назначения и окончательное исчезновение специализированных машин объемного рендеринга. Хотя самые быстрые из известных параллельных реализаций на дорогостоящих параллельных машинах высшего класса достигают скоростей, близких к реальному времени (около 10 кадров в секунду) [27], такие же или даже немного лучшие показатели достигнуты на средней по классу графической аппаратуре нанесения текстуры [28].
  • Кроме того, мы не сомневаемся в необходимости продолжения работ по созданию эффективных схем памяти, использованию когерентности кадров, оптимизации освещения, рендерингу сверхбольших наборов данных и ждем появления новых неожиданных вдохновляющих идей.


    Литература

    [1]. Kaufman A., D. Cohen, and R. Yagel, "Volumetric Graphics", IEEE Computer,26(7):51-64, July 1993.

    [2]. R. Yagel, D.Stredney, et. all, "Multisensory Platform for Surgical Simulation", IEEE Virtual Reality Annual International Symposium 1996 - VRAIS"96, Santa Clara CA, March 1996, pp. 72-78.

    [3]. Farrel, E.J., Zappulla, R., and Yang, W.C., "Color 3D Imaging of Normal and Pathologic Intracranial Structures", IEEE Computer Graphics and Applications,4(9):5-17, September 1984.

    [4]. Frieder,G., Gordon,D., and Reinolds,R.A., "Back-to-Front Display of Voxel-Based Objects", IEEE Computer Graphics and Applications,5(1):52-60, January 1985.

    [5]. Hanrahan,P., "Three-Pass Affine Transforms for Volume Rendering", Computer Graphics, 24(5):71-78, Proceedings of San Diego Workshop on Volume Visualization, November 1990.

    [6]. Lacroute P. and M.Levoy, "Fast Volume Rendering Using a Shear-Warp Factorization of the Viewing Transformation", Proceedings SIGGRAPH"94, Orlando, Florida, July 24-29, 1994. In Computer Graphics Proceedings, Annual Conference Series, 1994, ACM SIGGRAPH, pp. 451-458.

    [7]. Schroeder,P. and Salem,J.B., "Fast Rotation of Volume Data on Data Parallel Architecture", Proceedings of Visualization"91, San Diego, CA, 50-57, October 1991.

    [8]. Drebin,R.A., Carpenter,L., and Hanrahan,P., "Volume Rendering", Computer Graphics, 22(4):65-74, August 1988.

    [9]. Westover,L., "Footprint Evaluation for Volume Rendering", Computer Graphics, 24(4):367-376, August 1990.

    [10]. Levoy,M., "Display of Surfaces from Volume Data", IEEE Computer Graphics and Applications,8(5):29-37, May 1988.

    [11]. Tuy,H.K. and Tuy,L.T., "Direct 2-D Display of 3-D Objects", Computer Graphics and Applications,4(10):29-33, November 1984.

    [12]. Upson,C. and Keeler,M., "V-BUFFER: Visible Volume Rendering", Computer Graphics, 22(4):59-64, August 1988.

    [13]. Kajiya,J.T. and Von Herzen,B.P., "Ray Tracing Volume Densities", Computer Graphics, 18(3):165-174, July 1984.

    [14]. Sabella,P., "A Rendering Algorithm for Visualizing 3D Scalar Fields", Computer Graphics, 22(4):51-58, August 1988.

    [15]. Schlusselberg,D.S., Smith,K., and Woodward,D.J., "Three- Dimensional Display of Medical Image Volumes", Proceedings of NCGA"86 Conference,III, 114-123, May 1986.

    [16]. Yagel,R., Cohen, D., and Kaufman, A., "Discrete Ray Tracing", IEEE Computer Graphics and Applications,12(5):19-28, September 1992.

    [17]. Krueger W., "The Application of Transport Theory to Visualization of 3D Scalar Data Field", Proceedings Visualization"90, October 1990, San Francisco, CA, pp. 273-280.

    [18]. Max N., "Optical Models of Direct Volume Rendering", IEEE Transactions on Visualization and Computer Graphics, 1(2), June 1995.

    [19]. Sobeirajski L., D. Cohen, A.Kaufman, R.Yagel, and D.Acker, "A Fast Display Method for Volumetric Data", The Visual Computer, 10(2):116-124,1993.

    [20]. Reynolds,R.A., Gordon, D., and Chen,L.S., "A Dynamic Screen Technique for Shaded Graphic Display of Slice- Represented Objects", Computer Vision, Graphics and Image Processing, 38(3):275-298, June 1987.

    [21]. van Walsum,T., Hin,A.J.S., Versloot,J., and Post,F.H., "Efficient Hybrid Rendering of Volume data and Polygons", Second Eurographics Workshop on Visualization in Scientific Computing, Delft, Netherlands, April 1991.

    [22]. Danskin,J. and Hanrahan,P., "Fast Algorithms for Volume Ray Tracing", Proceedings of 1992 Workshop on Volume Visualization, Boston, MA, 91-105, October 1992.

    [23]. Yagel,R., and Z.Shi, "Accelerating Volume Animation by Space Leaping", Proceedings of Visualization"93, San Jose, California, October 1993, pp.62-69.

    [24]. Levoy,M., "Efficient Ray Tracing of Volume Data", ACM Transactions on Graphics, 9(3):245-261, July 1990.

    [25]. Cohen,D., and Shefer,Z., "Proximity Clouds- An Acceleration Technique for 3D Grid Traversal", Technical Report FC 93-01, Ben Gurion University of Negev, February 1993.

    [26]. Avila,R., Sobierajski,L.M., and Kaufman,A.E., "Towards a Comprehensive Volume Visualization System", Proceedings Visualization"92, Boston, MA, 13-20, October 1992.

    [27]. Lacroute P., "Real-Time Volume Rendering on Shared Memory Multiprocessors Using Shear-Warp Factorization", Proceedings 1995 Parallel Rendering Simposium, Atlanta, Georgia, October 1995, pp. 15-22.

    [28]. Cabral B., N.Cam and J.Foran, "Accelerated Volume Rendering and Tomographic Reconstruction Using Texture Mapping Hardware", Proceedings 1994 Simposium on Volume Visualization, pp. 91-98.

    [29]. Р.Ягель, Аппаратный рендеринг объема. Открытые Системы, 5, 96.

    Поделитесь материалом с коллегами и друзьями