8.5. Обход древовидных структур

Описанный в этом разделе подход основан на стандартных средствах представления в программе древовидных структур иерархических моделей, обработка которых производится средствами, не зависящими от вида конкретной модели. Мы будем рассматривать структуру, которая получила название слева - ребенок, справа - братья и сестры (left-child right-sibling)

Рассмотрим альтернативное представление иерархии компонентов фигурки (рис. 8.15).

Это дерево построено таким образом, что все элементы одного уровня иерархии связаны слева направо. Дочерние узлы данного узла представлены вторым списком, элементы в котором перечислены в порядке от самого левого до самого правого. Этот второй список представлен на рис. 8.15, снизу. Такое представление описывает структуру фигурки, но в нем отсутствует графическая информация.

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

typedef struct treenode {
GLfloat m[16]; void (*f)();
struct treenode *sibling; struct treenode *child; }treenode;

Рис. 8.15. Представление фигурки с помощью структур слева - ребенок, справа - братья и сестры

Иерархические графические модели

Массив m хранит по столбцам 4х4-матрицу преобразования в однородных координатах, как это принято в графической системе OpenGL. При обработке такой структуры в программе сначала выполняется умножение текущей матрицы вида на матрицу, хранящуюся в массиве m, а затем вызывается функция формирования изображения компонента f (), в которой генерируются нужные графические примитивы. В структуре также хранятся указатель child на аналогичную структуру, представляющую самого левого ребенка, и указатель sibling на структуру, представляющую цепочку расположенных правее его братьев и сестер. Если узлы того или иного вида в иерархии модели отсутствуют, соответствующий указатель имеет значение NOLL. Для представления рассмотренной в предыдущем разделе фигурки киборга нам понадобится восемь узлов, соответствующих восьми компонентам фигурки:


⇐ Предыдущая| |Следующая ⇒