Алгоритм «Марширующие кубы»

Его можно разбить на два этапа:

· Разбиение области G пространства R3 на конечное множество ячеек, поиск ячеек пересекаемых искомой поверхностью.

· Аппроксимация поверхности в найденных ячейках.

Две эти подзадачи являются независимыми. Рассмотрим их подробнее.

Основные проблемы первого этапа заключается в следующем:

· Разбить область G на ячейки.

· Выбрать ячейки, которые пересекаются с искомой поверхностью.

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

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

Рис. 9.6. На схеме квадрат обозначает ячейку, овал - некий изгиб искомой поверхности.

Как видно из рис.9.6, при большом размере ячейки некоторые части искомой поверхности просто не будут видны. Однако выбирать ячейки очень маленького размера не очень хорошо с точки зрения быстродействия. Поэтому размер ячейки надо выбирать не меньше допустимой погрешности построения искомой поверхности.

Работает алгоритм следующим образом:

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

Алгоритм Канейро

Алгоритм Канейро [2], основанный на разбиении пространства на треугольные пирамиды, как и алгоритм «Марширующие кубы», состоит из двух этапов:

· Разбиение пространства на конечное множество ячеек, поиск ячеек пересекаемых искомой поверхностью.

· Аппроксимация поверхности в найденных ячейках.

Как уже было сказано, алгоритм использует в качестве ячеек треугольные пирамиды. Для этого пространство разбивается на параллелепипеды в соответствии с сеткой, на которой задана функция, а затем каждый параллелепипед разбивается на треугольные пирамиды. Такой же подход применяется в алгоритмах Скалы и МТ6. Разбиение параллелепипеда на треугольные пирамиды по методу Канейро показано на рис.9.7.

Рис. 9.7. Разбиение параллелепипеда на треугольные пирамиды по методу Канейро.

Однако при подобном разбиении «швы» «разрезов» не совпадают. Другими словами, стороны треугольников, полученных в результате триангуляции соседних ячеек, не будут совпадать, что повлечет за собой появление «дырок». Для решения этой проблемы предлагается разбивать параллелепипеды в «шахматном порядке» - по очереди меняя шаблон разбиения: с показанного на рис.9.7 на зеркальный, как показано на рис. 9.8

Рис. 9.8. Разбиение параллелепипеда на треугольные пирамиды со сменой шаблона.

Задача второго этапа - аппроксимация поверхности в ячейке. Для алгоритмов Канейро, Скалы и алгоритма МТ6, второй этап один и тот же - производится триангуляция треугольной пирамиды в соответствии со значениями функции в вершинах.

Посчитаем, сколько способов триангуляции имеет треугольная пирамида. Пусть имеется 4-битовый индекс. Тогда сопоставим каждой вершине один бит в индексе, таким же образом, как и для параллелепипеда. Тогда количество разных типов триангуляции будет 24=16. Однако, используя симметрию и вращение, 16 способов можно свести к 3.

Рис. 9.9

Алгоритм «МТ6»

Алгоритм «МТ6» был предложен Гуезеком как альтернатива алгоритму Канейро. Основное отличие этих двух методов в том, что для алгоритма «МТ6» отпадает необходимость смены шаблонов с прямого на зеркальный и обратно. Это достигается путем симметричного разбиения параллелепипеда, показанного на рис.9.10.

Рис. 9.10. Симметричное разбиение параллелепипеда.

Алгоритм Скалы

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

Для разбиения пространства на ячейки метод Скалы использует узлы регулярной сетки, находящиеся в вершинах параллелепипеда, полученного тем же способом, что и в предыдущих рассмотренных методах, и дополнительную точку, находящуюся на пересечении диагоналей этого параллелепипеда. Значение функции в этой точке предлагается считать как линейную интерполяцию значений функции в вершинах параллелепипеда. Для каждого параллелепипеда, полученного из узлов регулярной сетки, строится ячейка способом, показанным на рис. 10. При таком разбиении для каждой ячейки используются «срединные» точки «соседних» параллелепипедов. На рис.10 это точки I,K,D. Итог этого разбиения - 12 треугольных пирамид (DEAC, DABC, DFBC, DFEC, IEAC, IAHC, IGHC, IEGC, KAHC, KHJC, KJBC, KABC).

Рис. 9.11. Способ построения ячейки.