Операции кадрирования и отсечения

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

Чтобы выполнить это преобразование, необходимо знать, какая часть неограниченного мирового пространства должна попасть на экран графического устройства. Заданная часть виртуального пространства, в котором формируется изображение для вывода на графическое устройство, называется окном. Заданная часть пространства для визуализации, на которую отображается окно называют полем вывода. Операция отображения окна на поле вывода называется видовой операцией (преобразованием). Задание окна используется для построения изображения, в котором границы окна совпадают с рамкой экрана, то есть, с полем вывода. Но иногда необходимо выделить лишь часть изображения, то есть выполнить операцию называемую, отсечением.

Видовые операции преобразования и отсечения дают возможность выводить на экран только те части изображения, которые находятся внутри окна.

Перемещая окно и задавая его размеры, можно создавать такие кинематографические эффекты, панорамирование, крупный и мелкий план.

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

В случае, если стороны окна наклонены по отношению к осям мировой

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

На рис. 3.16 иллюстрируется операция отсечения точек, линий последовательности символов для типового прямоугольного окна. Точка А находится внутри окна, и поэтому она изображается внутри поля вывода. Точка B находится вне окна и поэтому не изображается на видовой поверхности. Отрезок EF весь лежит в поле вывода и поэтому изображается полностью; отрезки GH и IJ по понятным причинам изображаются не полностью (то есть частично отсекаются); отрезки KL и СD не изображаются совсем. Отсечение символов здесь изображено на уровне отдельных объектов, что вообще говоря не всегда реализуемо. По тому, как выполнено отсечение по границе окна ясно, что точки (отрезка или собственно точки), попадающие на границу окна, считаются граничными (внутренними) и изображаются в поле вывода.

Для того, чтобы точка была видимой, необходимо и достаточно, чтобы выполнялись следующие неравенства:

X_min £ X £ X_max

Y_min £ Y £ Y_max

И если хотя бы одно из этих неравенств не выполняется, то точка в поле вывода не изображается.

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

1. Концевые точки отрезка лежат в поле вывода (отрезок EF рис. 3.16), отрезок полностью отображается.

2. Одна точка лежит вне окна вывода, другая вне его (отрезок GH). Подобная ситуация требует выполнения операции отсечения над отрезком.

3. Обе концевые точки отрезка лежат вне границы окна вывода. В этом случае необходимо проверить возможность его пересечения с границами окна: при обнаружении пересечения необходимо выполнить отсечение в противном случае отрезок находится вне окна вывода (отрезок IJ подлежит отсечению, а KL лежит вне окна).

Одним из способов решения задачи на отсечение отрезка, который нельзя принять целиком, является нахождение точек пересечения отрезка с каждой из сторон окна, с которыми отрезок пересекается. Если эти точки найдены, то отрезок частично находится в окне, поскольку необходимо определить и отбросить те части прямой, которые находятся вне окна. При таком подходе для каждой пары (сторона - отрезок) необходимо решать систему двух уравнений. Более эффективным решением является параметрическое задание прямых:

X=x₁ + t(x₂ – x₁)

Y=y₁ + t(y₂ – y₁).

Для t из диапазона (0,1) уравнения определяют точки x, y, находящиеся на ориентированном отрезке, начинающемся в точке x₁, y₁ и заканчивающемся в точке x₂, y₂. _. При этом необходимо решить систему уравнений относительно t_{сторона} и t_{отрезок}. Если найденные значения t_{сторона} и t_{отрезок} лежат в диапазоне (0,1), то отрезок пересекается с окном.

Поскольку поле вывода имеет форму прямоугольника (квадрата), каждому отрезку прямой принадлежит не более одного видимого участка. Алгоритм выделения видимых участков отрезков, приведенный в работе, разработан Д. Коэном и А. Сазерлендом. В основе алгоритма лежит принцип, согласно которому, каждый отрезок либо полностью лежит в пределах поля вывода, либо его можно разделить так, чтобы одна из его частей была удалена.

Алгоритм отсечения Коэна - Созерленда позволяет быстро выявить отрезки, которые можно отвергнуть или принять целиком; при этом использовать проверку области расположения отрезков. Вычисления точек пересечения необходимо проводить в том случае, если отрезки не попадают ни в один из случаев:

· большое окно, содержащее большинство примитивов;

· малое окно и обширное, насыщенное изображение, в котором большинство примитивов лежат вне окна.

В обоих случаях большинство отрезков можно принять или отбросить целиком.

Для удаления отрезка границы поля вывода продлеваются так, чтобы они делили поверхность изображения на девять подобластей, каждой из которых присваивается четырехразрядный код. Этот же код получают конечные точки отрезков, находящиеся в соответствующих подобластях.

Окно

Центральной областью является окно вывод. Для определения принадлежности отрезка или его концов соответствующей подобласти окна вывода, вводится четырех битный код (см. рис. 3.16).

Крайний правый бит считается первым. В соответствующий бит заносится 1 при выполнении следующих условий:

бит 1 - точка левее окна;

бит 2 - точка правее окна;

бит 3 - точка ниже окна;

бит 4 – точка выше окна.

В противном случае в бит заносится нуль. Отсюда следует, что если коды обоих концов ребер равны нулю, то эти точки лежат внутри окна, и отрезок видимый. Отрезок отбрасывается без вычислений, если оба его конца находятся выше, ниже, левее или правее окна. В этих случаях соответствующие биты в обоих кодах равняются 1, что легко проверяется при помощи операции логического “И”, примененной к кодам концов отрезка. Если результат логического произведения отличен от 0000, то отрезок лежит вне приделов окна. Несколько примеров приведенных в таблице 3.4 для отрезков рис. 3.22 подтверждают сказанное.

Если результат логического произведения побитно равен нулю, то отрезок может оказаться целиком или частично видимым или даже целиком невидимым. Из рис. 3.22 и таб. 3.4 видно, что отрезки IJ и GH являются именно такими отрезками. Они действительно пересекаются с окном. Таким образом, для определения полной видимости необходимо проверять значения кодов обоих концов отрезков по отдельности.

Таблица 3.4

Отрезок	Коды концов	Результат логического умножения	Примечание
CD				Невидим
EF				Видим
IJ				Частично видим
GH				Частично видим
KL				Невидим

Здесь необходимо сделать замечание следующего порядка. При разработке алгоритма надо помнить следующее: если наклон отрезка бесконечен, то возможно пересечение его только с верхней и нижней сторонами окна; если же наклон равен нулю, то пересечение возможно только с правой и левой сторонами. А если код одного из концов отрезка равен 0000, то этот конец лежит внутри окна, и поэтому отрезок может пересекать только одну из сторон окна.

Для разрешения вопроса о принадлежности окну отрезка, логическое произведение концов которого равно 0000, эффективно использовать алгоритм деления отрезка пополам. Если отрезок нельзя ни принять, ни отбросить целиком, он делится пополам. Общая стратегия состоит в повторении этого процесса (подобно процедуре двоичного поиска) до тех пор, пока один из сегментов исходного отрезка не будет принят целиком (если пересечение существует), а другой целиком отброшен. Для принятия этого решения используются коды Коэна – Созерленда.

Отсечение текста. Решение об отсечении текста в общем случае зависит от способа генерации литер и возможны три исхода.

Если каждую литеру представлять в виде множества коротких отрезков прямых линий (штрихов)[5], то операции отсечения можно подвергнуть каждый отрезок, подлежащий отсечению. Такой подход дает однозначный ответ и четкое изображение, но работает очень медленно.

В общем случае каждая литера рассматривается как неделимый объект (вспомним клеточное кодирование, где каждая литера мысленно помещается в ячейку (клетку)) и базовая точка (центр ячейки или один из ее углов) сопоставляется с окном вывода. Если базовая точка внутри окна, то литера рисуется, в противном случае - нет.

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

Отображение окна на поле вывода. После отсечения примитива по границам окна процессор видовой операции отображает его на поле вывода. На рис. 3.17 точка X,Y отражается в точку x,y с сохранением пропорций, с сохранением относительного положения внутри окна, то есть отношение расстояния от точки до y-границы к длине x-границы и отношение расстояния от точки до x-границы к длине y-границы должны быть одинаковы для окна и поля вывода.

Это соотношение может быть записано в виде:

Отсюда получаем уравнения отображения

или

или .

Здесь s_x и s_y коэффициенты масштабирования, согласующие размеры окна и поля, x_{v_min} и y_{v_min} параметры переноса, привязывающие относительные координаты окна (X_w - X_{w_min}) и (Y_w - Y_{w_min} ) к левому нижнему углу поля вывода, что хорошо согласуется с формулами преобразования, полученными ранее.

С помощью этих уравнений получаются значения координат в нормированной системе координат либо полученные умножением на 1024 в физической системе координат. С точки зрения здравого смысла удобнее было реализовать преобразование МК Þ ФК, но исходя из необходимости ориентации графических пакетов на широкое применение (с широким рядом дисплеев) более целесообразно преобразование НК -Þ ФК.

[1] Речь идет об упорядоченных парах чисел, для которых известно, какое число является первым и какое – вторым.

[2] Разнообразие КС обусловлено спецификой решения прикладных задач. Выбор КС обеспечивает снижение вычислительных затрат и формирует изображение объектов на экране, отображая независимые от устройства координаты в координаты, зависящие от устройства вывода.

[3] Положительным (выбранным) направленным отрезком называется отрезок прямой, ограниченный концевыми точками, если указано, какая из этих точек является началом, какая – концом.

[4] На первом месте пишется полярный радиус на втором угол.

[5] Этот вариант характерен при создании литер пользователем по задуманному им шаблону. Но и в этом случае каждая литера может быть объявлена сегментом (блоком) и при отсечении либо удаляется, либо принимается целиком.