Разработка фрактального алгоритма для построения трехмерной модели сердца

Олег Бодин, Андрей Кузьмин

1. Воксельное представление твердого тела

2. Представление твердого тела восьмеричным деревом

Известно, что к самым ресурсоемким при обработке информации приложениям относится 3D-графика. Описание, формирование, преобразование и представление сложных геометрических объектов являются основными операциями в компьютерной графике. При этом реализм представления информации жизненно необходим в ряде областей медицины. Например, реалистичное представление трехмерного изображения сердца пациента поможет кардиологу повысить точность диагноза и улучшить эффективность лечения. Сердце является сложным графическим объектом, описание формы которого трудно поддается формализации, а реализация модели очень требовательна к производительности компьютера, ибо для того, чтобы рассчитать секунду работы сердца, требуются сутки работы мощного компьютера.

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

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

Для получения твердотельного представления модели сердца воспользуемся двумя общеизвест­­ными подходами.

1. Воксельное представление твердого тела

Для получения воксельного представления внутрь сердца помещается исходный элемент — воксель (элементарная единица объема). Геометрически воксель представляет собой куб, размер которого определяется один раз перед началом работы и определяет точность, с которой сердце будет аппроксимировано (чем меньше элемент, тем меньше погрешность представления). У помещенного внутрь первого куба имеются шесть свободных граней, к каждой из которых затем пристраивается равный по размеру новый куб (рис. 2). Эта операция повторяется относительно всех шести новых кубов. На каждой итерации должны производиться две операции проверки:

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

• проверка исключения перекрытия — два куба, вершины (или координаты центра) которых совпадают, считаются одинаковыми, и в этом случае хранится только одна копия. Если же проверка показывает, что приращиваемый куб уже имеется, то данная ветвь тоже считается тупиковой.

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

Термин «фрактал» введен бельгийским математиком Бенуа Мандельбротом, а сам фрактал по Мандельброту состоит из геометрических фрагментов различного размера и ориентации, но аналогичных по форме. У фракталов есть общее свойство — это наличие рекурсивной процедуры их генерации, которая, как правило, достаточно проста и максимально учитывает свойство самоподобия. Использование системы итерированных функций позволяет математически описать алгоритм внутреннего заполнения сердца вокселями в терминах аффинных преобразований. При этом для реализации преобразований нужно задать одну систему итерированных функций, куда входят шесть аффинных преобразований (обозначим их F0-F5), позволяющих получить из исходного элемента шесть новых, которые пристраиваются к его свободным граням. Для исходного элемента приращение осуществляется в направлениях X, –X, Y, –Y, Z, –Z .

Представим аффинные преобразования в системе координат объекта, причем один из углов первого куба совпадает с началом координат, а длина ребра куба взята за единицу (см. рис. 2).

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

Блок-схема алгоритма воксельного представления твердого тела показана на рис. 3. К недостаткам воксельного представления относятся большие объемы памяти для хранения, резко возрастающие при увеличении разрешения. Затраты памяти увеличиваются обратно пропорционально кубу длины ребра: так, если уменьшить размер ребра в два раза, то требуемый объем памяти возрастет в восемь раз. Очевидно, что и вычислительные ресурсы расходуются в той же пропорции, поэтому воксельное представление является весьма затратным.

2. Представление твердого тела восьмеричным деревом

Вышеуказанного недостатка лишен другой подход к моделированию твердых тел — представление твердого тела восьмеричным деревом, что является иерархическим методом для представления группировок ортогональных трехмерных кубов. Если в алгоритме воксельного представления твердого тела объект заполнялся изнутри элементами заданного минимального размера, то в алгоритме представления твердого тела восьмеричным деревом объект заполняется элементами максимального размера. Объектное пространство представляется в виде куба и разделяется на восемь равных частей. Затем каждую часть можно точно так же разбить на восемь частей и т.д. После каждого такого разбиения нужно проверять одно условие — пересечение граней куба с границей объекта. В зависимости от результатов проверки кубу присваивается статус: куб снаружи объекта (в этом случае он не подлежит дроблению) ; куб внутри объекта (он тоже не подлежит дроблению); куб пересекается с границей объекта (и тогда он дробится дальше). Дробление прекращается, когда все кубы будут иметь первый или второй статус. Набор элементов, которые находятся во внутренней области, будет являться представлением объекта.

Аналогично алгоритму воксельного представления в данном алгоритме также можно заметить самоподобие и итеративный характер преобразований: элементы представляют собой кубы (хотя и разного размера), а действие, производимое над ними, — одно и то же, только каждый раз на новом уровне (каждый раз, когда дробится очередной элемент, повышается уровень детализации). Каждый куб представляет собой узел восьмеричного дерева: исходный — корневой узел, а тот, который более не подлежит дроблению, — листовой. Из всех узлов, кроме листовых, исходят восемь ветвей, так как каждый куб дробится на восемь новых. Восьмеричное дерево легко представить графически (рис. 4).

Аналитически данный алгоритм тоже описывается системой итерированных функций. Преобразования задаются в системе координат объекта, причем один из углов первого куба совпадает с началом координат, а длина ребра куба взята за единицу (рис. 5).

Блок-схема алгоритма представления твердого тела восьмеричным деревом дана на рис. 6. Такой вариант твердотельного представления объекта намного эффективнее традиционного воксельного представления. На рис. 7 и 8 представлены результаты работы алгоритма с разными уровнями детализации.

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

«САПР и графика» 3'2005