Алгоритм вокселизации, основанный на глубине

Реферат

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

1. Введение

Объемная графика – одно из последних достижений в компьютерной графике, но, очевидно, она имеет потенциал чтобы стать одной из наиболее полезных технологий в представлении и обработке трехмерных объектов. Воксельные модели используются в разнообразных приложениях, в том числе в (но не ограничиваясь)приложениях медицинской визуализации [2],[11], генерации текстур[5],[8] и в последнее время даже в компьютерных играх.

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

Основной идеей в большинстве алгоритмов вокселизации является проверка принадлежности каждого вокселя к объекту и присвоение 1 или 0 значению вокселя в зависимости от результата такой проверки. Это достигается путем исследования, лежит ли центр вокселя внутри объекта либо выбором всех вокселей, которые пересекаются объектом. Более сложные алгоритмы генерации гладкой модели без контурных неровностей используют фильтрацию объема [12], деление исходного объекта [1] или расчет точного расстояния от вокселя до поверхности объекта [4].

Следует отметить, что большинство методов вокселизации ориентированы на один тип объектов, например, полигональные сетки, линии, параметрические поверхности и т.д.

В этой статье мы представляем простой и быстрый алгоритм, который создает объемные данные из любого вида исходной модели, в которой может быть применен z-buffer. Раздел 2 описывает основную идею метода, в то время как в разделе 3 описываются преимущества алгоритма и проводится его сравнение ее с уже известными методами. В разделе 4 представлены два варианта метода, которые вокселизируют только поверхность или весь объем данных различной плотности. В разделе 5 приведены результаты испытаний.

2. Обзор алгоритма

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

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

2.1. Настройка буферов

Первый шаг метода представляет собой размещение объекта на сцене, как мы обычно делаем для рендеринга, независимо от типа объекта. Для того, чтобы приступить к вокселизации, мы должны создать три пары буферов глубины ([x₁, x₂], [y₁, y₂], [z₁, z₂]), смотрящее вдоль трех осей X, Y, Z , которые определяют глобальную систему координат. Каждая пара состоит из двух буферов, перпендикулярных одной и той же оси, но на противоположных сторонах объекта, таким образом, что они смотрят друг на друга, как показано на рисунке 1.

Рисунок 1 – Пары буферов глубины

Буферы этой же пары хранят противоположные виды объекта и соответствуют той же оси просмотра. Первый буфер каждой пары x₁, y₁, z₁ (R, U, F на рисунке 1) содержит наиболее близкую глубину для зрителя, в то время как второй буфер x₂, y₂, z₂ (L, D, B на рисунке 1) хранит максимумальное расстояние от зрителя по соответствующей оси.

Поскольку данные о глубине обычно хранятся в z-буфере, то есть в буфере вдоль оси Z, в нашем случае необходим объект, который будет вращаться дважды, чтобы получить пары x-буфера и y-буфера. Не требуется никаких дополнительных преобразований для получения второго буфера каждой пары, так как это может быть легко достигнуто путем модификации функции сравнения, используемой в z-буфере, для сохранения наибольшего расстояние вместо наименьшего. Контроль за функцией сравнения предоставляется большинством распространенных API, таких как OpenGL.

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

2.2. Вокселизация

После того как все шесть буферов созданы, мы можем приступить к фактическому шагу вокселизации. Пусть V = {v(i,j,k): i,j,k ∈ [0, N)} – воксельный куб.

Окончательная воксель-ориентированная модель ограничена разрешением буфера, поэтому мы должны выбрать размер буферов N x N для N³ воксельного куба. Ориентация куба определяется тремя глобальными осями X, Y, Z.

Преобразование в объемные данные состоит из тройного цикла для покрытия воксельного пространства. Воксель v(i,j,k) связан с шестью проекциями точек на буферы глубины, координатами которых на оси X, Y, Z являются пары (j,k), (k,i) и (j,i) соответственно. Глубины заданы соответствующими буферами: x₁(j,k), x₂(j,k), y₁(k,i), у₂(k,i), z₁(j,i), z₂(j,i).

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

Рисунок 2 – Проверка принадлежности вокселя объекту

Так как воксельные координаты определяются относительно размера воксельного куба (на интервале [0 , N)), а значения z-буфера лежат в диапазоне [depth_min , depth_max] (зависящем от реализации), для сравнения необходимы некоторые преобразования. Позиция v(i,j,k), преобразованная в значение диапазона z-буфера:

(x, y, z) = (i, j, k) * (depth_max - depth_min) / (N - 1) (1)

v(i,j,k) лежит внутри объекта, только если выполняются условия:

x₁(j,k) ≤ x ≤ x₂(j,k)

AND y₁(k,i) ≤ y ≤ y₂(k,i)(2)

AND z₁(j,i) ≤ z ≤ z₂(j,i)

2.3. Область применения

Алгоритм, представленный выше сдерживается определенными ограничениями, налагаемыми самими буферами. Поскольку метод использует данные из z-буфера, информация об объекте ограничивается частями объекта, видимого по трем главным осям просмотра. В результате метод не может правильно реконструировать объекты с внутренними полостями или другими частями, которые не видны из выбранных углов обзора. Это не ограничивает метод выпуклых объектов; невыпуклые объекты могут быть вокселизированы, если нет скрытых полостей.

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

3. Преимущества

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

Другой важной особенностью алгоритма является то, что он может быть использован для все типов 3D-объектов (полигональных, аналитических или даже объемных данных) без модификаций и увеличения вычислительных затрат, в отличие от многих существующих методов вокселизации, которые ограничены конкретными видами объектов [7],[4]. Данный метод может быть использован для одновременной вокселизации нескольких объектов, пока нет перекрытия из-за скрытых областей между ними во всех видах.

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

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

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

4. Модификации базового алгоритма

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

4.1. Вокселизация поверхности

Воксель v(i,j,k) является частью поверхности объекта, если по крайней мере одна из его координат, рассчитанная по формуле (1), находится близко к одному из соответствующих значений буфера, в то время как остальные координаты удовлетворяют условиям (2). Поэтому v(i,j,k) лежит на поверхности, если выполнено следующее условие (или любое из двух аналогичных условий для осей Y и Z):

(x₁(j,k) ≤ x ≤ x₁(j,k) + d_x1(j,k) OR x₂(j,k) - d_x2(j,k) ≤ x ≤ x₂(j,k))

AND y₁(k,i) ≤ y ≤ y₂(k,i)(3)

AND z₁(j,i) ≤ z ≤ z₂(j,i)

x, y, z вычислены с использованием формулы (1) и d – порог отклонения, определяющий, насколько близко воксель должен быть к поверхности объекта. Другими словами, d – мера толщины поверхности в каждой точке по отношению к оси просмотра. Толщина поверхности измеряется от контура объекта к внутринности объекта, поэтому приведенные неравенства для х несимметричны.

Значение d должно быть выбрано таким образом, чтобы сочетать в себе две цели [6]:

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

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

Рассмотрим пример на рисунке 3, который сводится к двум размерностям для простоты. v(i,j) и v(i + 1, j + 3) являются последовательными видимыми вокселями для буфера z1(отмечены Х) и правильно определены как поверхностные воксели. Тем не менее, воксели v(i, j + e), е = 1..3, которые также поверхностные, (отмечены О), скрытые для буфера z₁. если эти вокселей могут быть видимыми в другом буфере (x₂ в этом примере), они будут правильно определены как принадлежащие к поверхности. Это не всегда так, особенно в невыпуклых объектах (например, v(i, j + 2) скрыт для всех буферов).

Рисунок 3 – Пример

Во избежание этой проблемы мы расчитываем толщину поверхности d_z1(i,j) для v(i,j) как видимую из буфера z₁ и отмечаем все воксели v(i,l + е), е = 1..d_z1(i,j). Эти воксели принадлежат к поверхности объекта, при условии, что оставшиеся критерии (3) в отношении остальных осей совпадают. d_z1(i,j) может быть непосредственно получено из буфера z₁ путем вычисления разницы интенсивности между z₁(i) и соседними буферными точками, что соответствует различию глубины в пространстве объекта:

d_z1(i, j) = z_1max(i) - z₁(i) if z_1max ≥ z₁(i)

d_z1(i, j) = 0 otherwise(4)

z_1max = max{zz₁(i - 1), z₁(i + 1)}. Если выбирается меньшее значение d_z1(i, j), контур будет иметь отверстия, в то время как большее значение будет давать избыточные воксели в окончательной модели. Если обрабатывать противоположный буфер, z₂, критерий сравнение будет обратным, и будет рассчитан z_2min вместо этого. Эта же процедура повторяется для двух x-буферов.

Расширить процедуру для трех измерениях просто. Единственная разница в том, что для определения толщины поверхности, мы должны изучить 4 или 8 соседей буферной точки, в зависимости от желаемого соединения.

Расчеты толщины поверхности выполнены в виде этапа первичной обработки перед процедурой вокселизации поверхности. Вычислительная сложность является пропорциональной размерам буферов и составляет O(N²), что не является существенным расходом по сравнению с O(N³) сложностью вокселизации поверхности. Алгоритм вокселизации приводится ниже:

Шаг 1. Прочитать буферы глубины (x1,x2,y1,y2,z1,z2).

Шаг 2. Для каждого буфера:

    Для каждой ячейки буфера:

        Вычислить максимальную разницу глубины между ячейкой и ее соседями. 

        Сохранить результат как новую толщину буфера (dx1,dx2,dy1,dy2,dz1,dz2).

Шаг 3. Для каждого вокселя v(i,j,k) проверить его принадлежность поверхности с помощью (3).

4.2. Вокселизация переменной плотности

Некоторые приложения объемной визуализации требуют изображения с объемными данными с более чем двумя значениями для вокселя, для того , чтобы уменьшить эффект квадратиков, который присутствует в методах бинарного решения (1 – если воксель внутри объекта, 0 в противном случае ). В этом случае вокселям присваивается значение, которое является функцией их расстояния от поверхности объекта или сглаживающий эффект достигается путем фильтрации. Сглаживание вобщем полезно для внешней поверхности объекта, которая подвержена зубчатому ??эффекту. Наш метод может быть легко модифицирован для выпуклых объектов, чтобы генерировать вокселы той или иной плотности. Плотность воксела оценивается в соответствии с процентом вокселя, который на самом деле внутри объекта. Внешние воксели имеют плотность 0, в то время как вокселям, полностью лежащим внутри объекта назначаются плотность d_max. Воксели на контуре имеют значение плотности, пропорциональное объему охватываемыемому объектом. Этот процент рассчитывается следующим образом.

Рассмотрим сначала ось Х. Буфер значений x₁(j,k) и x₂(j,k) для вокселя v(i,j,k) извлекаются и результат преобразуется в соответствующие значения i₁ и i₂ в диапазоне [0 , N] обратным (1) образом:

i₁, i₂ = x₁,₂ * N / (depth_max - depth_min)(5)

Обратите внимание, что значения буфера определяются в диапазоне [depth_min, depth_max] и поэтому преобразуется в диапазоне [0, N], а [0, N), что оправдывает наличие N в числителе вместо N – 1, чего можно было бы ожидать в (1). i (которая представляет координаты вокселя на оси Х в воксельном пространства) имеет целое значение в [0, N), в то время как i₁ и i₂ (которые являются глубинами поверхности объекта на оси х) – числа с плавающей точкой в [0, N]. Таким образом, v(i,j,k) является поверхностным вокселем относительно оси X только если i = [i₁] или i = [i₂].

• eсли i = [i₁], то воксельное покрытие оси Х установлено в c_x = [i] + 1 - i₁, если i = [i₂], соотвествующиее покрытие – c_x = i₂ - [i];
• если i < [i₁] или i ≥ [i₂], тогда v(i,j,k) – внешний воксель и мы устанавливаем c_x = 0;
• во всех других случаях i лежит между [i₁] и [i₂].

Таким же образом мы определим покрытие в остальных двух направлениях Y и Z, су и cz соответственно. Общая плотность вокселя d_v представляет собой сочетание процентов покрытия во всех трех направлениях:

d_v = c_x * c_y * c_z * d_max(6)

Список использованной литературы

1. D.Cohen, A.Kaufman and Y.Wang. “Generating a Smooth Voxel-Based Model from an Irregular Polygon Mesh.” The Visual Computer, 10:295-305 (1994).
2. D.Cohen-Or. “Exact antialiasing of textured terrain models.” The Visual Computer, 13:184-199 (1997).
3. T.Galyean and J.Hughes. “Sculpting: an Interactive Volumetric Modeling Technique.” Computer Graphics ( Proc. SIGGRAPH ’91), 25: 267-274 (1991).
4. M.Jones. “The Production of Volume Data from Triangular Meshes Using Voxelization.” Computer Graphics Forum, 15:311-318 (1996).
5. J.T.Kajiya and T.L.Kay. “Rendering Fur with Three Dimensional Textures.” Computer Graphics (Proc. SIGGRAPH ’89), 23:271-280 (1989).
6. A.Kaufman, D.Cohen and R.Yagel. “Volume Graphics.” IEEE Computer, 26:51-64 (1993).
7. A.Kaufman and E.Shimony. “3D Scan Conversion Algorithms for Voxel-Based Graphics.” In Proc. ACM 1986 Workshop on Interactive 3D Graphics, pp 45-76. Chapel Hill, NC, 1986.
8. F.Neyret. “Modeling, Animating and Rendering Complex Scenes Using Volumetric Textures.” IEEE Transactions on Visualization and Computer Graphics, 4:55-70 (1998).
9. A.Pommert, M.Bomans, M.Riemer et al. “Volume Visualization in Medicine: Techniques and Applications.” In Focus on Scientific Visualization, edited by H.Hagen, pp 41-71. Berlin: Springer, 1992.
10. C.E. Prakash and S.Manohar. “Volume Rendering of Unstructured Grids – A Voxelization Approach.” Computer Graphics, 19(5):711-726 (1995).
11. M.R.Stytz, G.Frieder and O.Frieder. “Three-dimensional Medical Imaging: Algorithms and Computer Systems.” ACM Computing Surveys, 23:421-499 (1991).
12. S.Wang and A.Kaufman. “Volume Sampled Voxelization of Geometric Primitives.” In Proceedings of the Visualization '93 Conference, pp 78-85. IEEE Computer Society Press, 1993
13. S.Wang and A.Kaufman. “Volume-Sampled 3D Modeling.” IEEE Computer Graphics and Applications, 14:26-32 (1994).
14. S.Wang and A.Kaufman. “Volume Sculpting.” In Symposium on Interactive 3D Graphics, pp151-156. ACM Press, 1995.