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. Для представления рассмотренной в предыдущем разделе фигурки киборга нам понадобится восемь узлов, соответствующих восьми компонентам фигурки: