1-3 ПОДГОТОВКА ИЗОБРАЖЕНИЙ ДЛЯ ВЫВОДА

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

Точки — основные строительные блоки графической базы данных, именно поэтому особый интерес представляют основные операции преобразования точек. Существуют три типа операций, в которых точки используются как графические примитивы: во-первых, перемещение пера и курсора, след курсора (в дальнейшем просто курсор), невидимая точка; во-вторых, изображение линии между двумя точками; в третьих, вывод точки в заданном месте. В общем случае местоположение точки можно описать двумя способами: с помощью абсолютных и относительных (инкрементальных) координат. В системе относительных координат позиция точки определяется путем задания ее положения относительно предыдущей точки. Все программное обеспечение машинной графики базируется на этих основных понятиях и операциях. Более подробно основы построения программ машинной графики излагаются в разд. 1-22 и в приложении А.

Местоположения точки могут быть описаны с помощью вещественных (с плавающей точкой) или целых чисел. В случае применения целых чисел возникает множество проблем, связанных с ограниченной длиной слова компьютера. Для представления целых координат, как правило, используется полное машинное слово. Наибольшее целое число, занимающее полное машинное слово и необходимое для представления величин со знаком из положительного и отрицательного диапазонов, равно , где  — количество битов в слове. Для 16 битового слова это число равно 32 767. Для многих приложений этого бывает вполне достаточно, однако возникают серьезные проблемы, когда требуются большие числа, которые невозможно представить с помощью одного слова компьютера. Эту трудность можно преодолеть, например, воспользовавшись относительными координатами в случае, когда их величина не превышает 60 000. При этом в абсолютной системе координат устанавливаются точки с координатами (30000,30000), а затем с помощью относительных координат (30 000,30 000) строится точка, с координатами (60 000,60 000). Однако этот способ обладает значительным недостатком: попытка сохранить относительные координаты, превышающие максимально допустимую величину, вызывает переполнение. В большинстве компьютеров результатом целочисленного переполнения является генерация чисел с противоположным знаком и неверным абсолютным значением.

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

В системе однородных координат n-мерное пространство представляется  измерением, т. е. трехмерные координаты, однозначно задаваемые тройкой , выражаются через четыре координаты , где  — произвольный множитель. Если все координатное пространство в 16-битовом компьютере представляется числами меньше 32 767, то  будет равно 1, а координаты будут представляться путем прямых преобразований. Однако если хотя бы одна из координат превышает число 32 767, например, , то преимущества использования однородных координат становятся очевидны. В данном случае мы установили  и координаты точки теперь можно представить в 16-битовом компьютере как . Однако в этом случае неизбежно снижение разрешающей способности, так как, например, значения  и  теперь представляются одинаковой однородной координатой. Фактически разрешение ухудшается для всех координат даже в том случае, если только одна из них превышает максимально допустимое для целых чисел значение.