6. Базовая графика PostScript

Это стандарт de facto для настольных издательских систем. Изначально формат предназначался для компьютеров Macintosh и их периферии (принтеров и других устройств вывода). Сейчас он используется на PC- и UNIX-платформах как для вывода, так и для хранения и передачи изображений, особенно в формате инкапсулированного PostScript (Encapsulated PostScript  EPS). Тип изображения  векторное и bitmap (векторное и растровое). По типу формата PostScript относится к языкам описания страниц. EPS  подмножество языка Adobe PostScript, владельцем которого является Adobe Systemc Inc. Файлы в DOS имеют расширение *.eps.

Базовая графика PostScript имеет 4 варианта: Level 1, Level 2, Encapsulated PostScript, Display PostScript. Level 1  исходное подмножество языка. Используется, в основном, для черно-белой графики до 8 бит глубиной. Может также работать в RGB и CMYK. Level 2 включает Level 1 и ряд усовершенствований. Используются различные методы сжатия, колориметрия. Глубина цвета до 32 бит. Вместо ASCII-кода можно использовать бинарный код. EPS описывает одну страницу, которая без модификации включается в большие PostScript-документы. В основном используется для обмена. Допускает 24-битные RGB и HSB, 32-битный CMYK, индексирование палитры цветов. EPS “понимается” большинством издательских систем. Интерпретаторы Display PostScript являются аппаратно-независимыми интерфейсами для мониторов в режиме реального времени. Они поддерживают многозадачность, окна и т.д.

PostScript по сути является языком программирования. Он похож на язык программирования FORT. PostScript очень детализирован, из-за чего интерпретатор занимает большой объем памяти. Руководство по 2 редакции языка содержит более 700 страниц. PostScript позволяет описать документы в сотни страниц с включением в текст рисунков и установок для печати. Имеются средства эскизного просмотра, линейого преобразования изображений (в том числе векторных шрифтов). Можно получить до 12 разрядов глубины серого, 36-битовый RGB. Язык имеет большие возможности, прекрасно служит для согласования различных платформ при цветных и черно-белых изображениях. Для bitmap-изображений он обычно неэффективен. К недостаткам следует отнести жесткую ориентацию языка на принтеры PostScript. Для других принтеров на месте изображения печатается пустая рамка.

Разбиение картинной плоскости

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

Оценим выгоду. При прямом переборе оценка количества операций O(N²), при разбиении - O(N). Однако, требуется память для хранения информации о клетках, в которые попадает проекция ребра.

На этих же принципах основан алгоритм Варнака. Картинная плоскость разбивается на 4 равные части. При этом возможны следующие случаи:

• область пуста (в нее не попадает ни одной проекции), следовательно она закрашивается цветом фона;

• область целиком занята проекцией одной грани, следовательно она закрашивается цветом грани;

• не выполняется ни одно из вышеуказанных условий, область разбивается на части, анализ повторяется.

Очевидно, разбиение имеет смысл проводить до тех пор, пока размер области превышает один пиксел. Для части размером в 1 пиксел принимается специальное решение, например, закраска цветом ближайшей грани. Возможны и иные правила анализа активной области.

МЕТОДОД ДВОИЧНОГО РАЗБИЕНИЯ ПРОСТРАНСТВА

В основе - известный прием дихотомии (половинного деления). Пространство делится плоскостью на два полупространства. Далее используется исходная эвристика №2 (п. 6.5.1). Внутри каждого полупространства разбиение повторяется. Можно также секущую плоскость провес через произвольно выбранную грань (модификация алгоритма). Фактически строится двоичное дерево, узла! которого являются грани. Древовидные структуры достаточно легко программируются с помощью списков объектно-ориентированного подхода. Объект - грань, методы - различные виды прохода по дереву (получить следующий выше/нижележащий элемент, получить следующий элемент на том же уровне соседней ветви и т.д

Как выбрать грани для разбиения? Существует два основных критерия:

• получить как можно более сбалансированное дерево;

• минимизировать количество разбиений.

Эти критерии обычно являются взаимно исключающими, требуется компромисс.

Алгоритм работает в объектном пространстве. Его сильная сторона - независимость от положения центра проектирования (точки наблюдения). Одну и ту же сцену можно перерисовывать для разных точек наблюдение

К методам упорядочения относится также МЕТОД ПЛАВАЮЩЕГО ГОРИЗОНТА. В отличие от вышеизложенных, в этом методе сначала выводятся ближние к наблюдателю фрагменты. Пусть требуется получи каркасное изображение гладкой поверхности. Для изображения проекции ребра на картинную плоскость и пользуется растровый алгоритм, например, алгоритм Брезенхейма. При выводе очередной точки проекции видимость анализируется с учетом нижней и верхней границ уже полученной части изображения. Эти границы и зывают соответственно нижним и верхним плавающим горизонтом, т.к. в процессе работы алгоритма их пол жение меняется. Горизонты можно представить как 2 целочисленных массива. В процессе работы изображения достраивается вне области, где оно уже построено.