Ячеечные методы (cell-based)

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

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

Наиболее известные ячеечные алгоритмы: метод Канейро, метод, предложенный Гуэзеком, метод Скалы, метод марширующих кубов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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