6.10. СТРУКТУРЫ ДАННЫХ ДЛЯ ВОСПРОИЗВЕДЕНИЯ ВИЗУАЛЬНЫХ ОТОБРАЖЕНИЙ

Структуры данных, рассмотренные выше, удобно использовать в случаях, когда работа ведется с собственно изображениями. В машинной графике исходными данными служат описания изображений, причем задаваться они могут не в виде изображений. В общем случае эти описания представляют собой кусочно-полиномиальные функции одной переменной (для кривых) или двух переменных (для поверхностей). При работе с векторными графическими устройствами, элементарные команды которых обеспечивают лишь отображение прямых, эти функции являются кусочно-линейными, что позволяет строить многоугольники и многогранники. В любом случае описание объекта представляет собой некоторый граф, ребрами которого служат отрезки прямых. Говоря об этой структуре данных, можно пользоваться термином граф объекта. Если в описание входят отрезки кривых или участки поверхностей высших порядков, ограниченные замкнутыми кривыми, то и в этом случае можно строить граф объекта, но с помеченными ребрами — метками служат коэффициенты уравнения кривой или поверхности. Другим возможным вариантом является использование некоторого (неплоского) ГСО, вершины которого соответствуют участкам поверхностей, ограниченным замкнутыми кривыми, и, если эти участки оказываются смежными, соответствующие им вершины соединяются ребрами. Такой «граф смежности участков поверхности», ограниченных замкнутыми кривыми, целесообразно применять при работе с растровыми графическими устройствами.

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