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

Алгоритм Канейро [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. Симметричное разбиение параллелепипеда.