Визуализация в научных исследованиях. Ечкина Е.Ю - 10 стр.

Е. Ю. Ечкина, С. Б. Базаров, И. Н. Иновенков «Визуализация в научных исследованиях»


поверхности в каждой ячейке отдельно. Причем каждая ячейка триангулируется одним
из заданных ранее способов, т.е. значения координат для треугольников просто
берутся из заранее заданной таблицы.
Для применения методов этого типа необходимо задать допустимую ошибку
аппроксимации, исходя из которой, следует выбрать размер ячейки - куба или
тетраэдра (если быть точным - то треугольной пирамиды, т.к. тетраэдрами нельзя
замостить пространство без пропусков и наложений.) После этого с помощью уже
известных таблиц триангуляции можно получить искомое множество треугольников.
При этом процедура триангуляции каждой ячейки сводится к анализу значений
функции в вершинах этой ячейки - другими словами, определяется, какие вершины
лежат внутри поверхности, а какие - снаружи. На основе этого можно сделать вывод о
достаточности определения функции только в вершинах ячеек.
Наиболее известные ячеечные алгоритмы: метод Канейро (Caneiro), метод,
предложенный Гуэзеком (Gueziec), метод Скалы (Skala), метод «Марширующих
кубов».

Метод типа предиктор-корректор (predictor-corrector)

Методы из этого класса основаны на добавлении к уже имеющемуся множеству точек
триангуляции ещё одной, лежащей на касательной плоскости к заданной функции (это
положение предиктора (predictor) - предсказанное) и затем передвижению её до
визуализируемой поверхности (это положение корректора (corrector) -
скорректированное).
При использовании методов из этого класса необходимо знать значение функции во
всех точках пространства и найти хотя бы одну точку, принадлежащую искомой
поверхности. Метод заключается в наращивании треугольников - на каждой итерации
метода к уже существующему множеству треугольников добавляется еще один,
построенный на ребре крайнего треугольника и предсказанной (а затем
скорректированной по кривизне поверхности) точки на поверхности.

Алгоритм "марширующих кубов"

Алгоритм «Марширующих кубов», предложенный Лоренсеном, можно разбить на два
этапа:
1. разбиение области G пространства R3 на конечное множество ячеек,
    поиск ячеек пересекаемых искомой поверхностью;
2. аппроксимация поверхности в найденных ячейках.
Две эти подзадачи являются независимыми. Рассмотрим их подробнее.

Первый этап

На этом этапе необходимо:
1. разбить область G на ячейки,
2. выбрать ячейки, которые пересекаются с искомой поверхностью.
После того как область G будет разбита на ячейки, значения функции, задающей
поверхность, будут известны только в вершинах этих ячеек. Таким образом, на этом
этапе ячейка является главной структурной единицей во всех алгоритмах.
В тех задачах, в которых функция, задающая поверхность задана таблицей на
регулярной сетке, проблема разбиения области G на ячейки сразу отпадает, ввиду
однозначности ее решения - ячейка должна быть параллелепипедом - для того, чтобы
знать значения функции в вершинах ячейки. Если же функция задана явно, то ячейку
можно выбрать произвольной формы и размера. Однако следует учесть некоторые
Кафедра АНИ факультета ВМК МГУ имени М. В. Ломоносова http://ani.cs.msu.su            10