Дискретная трассировка лучей в октантных деревьях

Применяется для воксельных моделей. Рис. 2. иллюстрирует основной принцип метода: луч отслеживается из точки наблюдения, пересекает плоскость экрана в точке (х_s, у_s) и ударяется в бокс, содержащий дискретную информацию об объекте. Бокс разделен на подбоксы, пронумерованные от 2° до 2⁷, которые далее рекурсивно делятся на более мелкие подбоксы, формируя октантное дерево. (Все ячейки пространства, отличные от вокселя, именуются "подбоксами" или "боксами", и только элементарные неделимые элементы объема называются вокселями).

Рис. 14.3. Основная идея метода

В основном, алгоритм работает как многие методы обратной трассировки лучей (backward raytracing). Лучи испускаются из точки наблюдения через пиксели на экране и отслеживаются до момента пересечения с объектом. В этой точке вычисляется цвет пикселя или порождаются вторичные отраженные или преломленные лучи, если таковые имеются. Главный вопрос трассировки лучей: "Как найти точку пересечения луча и объекта?". Алгоритм решает эту задачу следующим образом:

· находит точку пересечения луча и бокса, содержащего объект (вычисляются точки входа и выхода луча из бокса);

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

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

Рис. 14.4

На рис. 14.4 проиллюстрирован метод поиска точки пересечения.

Луч входит в бокс в точке "пола" Р₀, проходит через среднюю точку Р₁ и покидает бокс в точке "потолка" Р₂. Важно, чтобы три точки располагались на трех параллельных плоскостях, две из которых — плоскости, содержащие противоположные грани бокса, а третья — делит бокс на две равных половины. {Совершенно очевидно, что точки Р₀ и Р₂ не обязательно будут принадлежать граням бокса, в то время как средняя точка Р₁обязательно будет находиться внутри бокса.

Всего может быть три варианта выбора для плоскостей, содержащих точки "пола" и "потолка": плоскости могут быть перпендикулярны одной из трех координатных осей X, Y или Z. Пусть точка на луче описывается в системе координат бокса следующим уравнением:

где S₀ — начальная точка луча, (dx, dy, dz) — вектор направления луча, t — скалярный параметр.

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

Методика выбора главного направления совпадает с использованной в целочисленном алгоритме Брезенхема [12] и служит тем же целям: избежать появления разрывов во время дискретизации прямой луча.

Плоскости "пола" и "потолка" выбираются перпендикулярными оси главного направления луча.

Для определения точки пересечения луча и модели используется двоичный рекурсивный поиск вдоль луча между плоскостями "пола" и "потолка". Процедура поиска должна получить следующие входные параметры:

· ОГНЛ,

· двумерные координаты точек "пола" и "потолка" в соответствующей системе координат,

· текущий узел дерева.

Важно отметить, что при двоичном поиске точки пересечения используются двумерные координаты точек, так как третья координата точки на луче (координата вдоль ОГНЛ) выполняется непосредственно во время отслеживания луча.

Несмотря на то, что алгоритм трассировки луча очень прост и использует всего несколько целочисленных и логических операций, он требует, чтобы точки "пола" и "потолка" были вычислены для каждого пикселя изображения для того, чтобы инициализировать процесс трассировки.

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

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

· количество информации и скорость визуализации почти не зависят от сложности объектов;

· нет необходимости в специальных алгоритмах нанесения текстур, так как каждый воксель имеет собственный цвет;

· высокая точность определения нормалей, так как они сопоставлены каждому вокселю;

· высокая точность определения точек пересечения;

· есть возможность непосредственной визуализации наборов данных с измерительных устройств без преобразования в сложные полигональные модели;

· простота реализации алгоритмов определения пересечения двух объектов (например, для CAD/CAM систем).

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

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

· Более высокая скорость: типичные медицинские объекты, полученные методом компьютерной томографии (разрешение воксельного пространства — 256³, разрешение изображения — 320²;) визуализируются за 0.3-0.9 секунд/кадр на ПК с процессором Pentium на тактовой частоте 200 МГц (разброс в длительности интервалов обусловлен различием в углах наблюдения моделей). Такая скорость визуализации достигнута благодаря следующим свойствам алгоритма:

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

— наиболее длительные операции были ускорены с использованием 1оок-up таблиц или интерполяции конечными разностями;

— использование иерархических структур данных позволяет сократить количество операций при поиске точки пересечения луча и объекта;

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

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