ГРАФИЧЕСКИЙ ИНТЕРФЕЙС ОПЕРАТОРА. Учебное пособие для студентов специальности 220301 Москва 2011 2 Содержание
 Скачать 2.77 Mb.
|
|
X Y Z Проектирующий луч Орт оси OZ 83 4.4.5. Центральные (перспективные) проекции Перспективные (центральные) проекции строятся более сложно. Предположим для простоты, что центр проектирования лежит на оси Z в точке С (0, 0, с) и плоскость проектирования совпадает с координатной плоскостью XY (рис. 80). Возьмем в пространстве произвольную точку М(х, у, z), проведем через нее и точку С прямую и запишем соответствующие параметрические уравнения. Рис. 80. Пример центральной проекции Имеем: t c z c Z t y Y t x X ) ( , , Найдем координаты точки пересечения построенной прямой с плоскостью XY. Из условия Z' = 0 получаем, что c z t 1 1 и далее: y c z Y x c z X 1 1 , 1 1 Интересно заметить, что тот же самый результат можно получить, привлекая матрицу: 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 c В самом деле, переходя к однородным координатам, прямым вычислением легко проверить, что 84 c z y x c z y x 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 Вспоминая свойства однородных координат, запишем полученный результат в несколько ином виде: 1 0 1 1 c z y c z x и затем путем непосредственного сравнения убедимся в том, что это координаты той же самой точки. Замечание. Матрица проектирования, разумеется, вырождена. Матрица соответствующего перспективного преобразования (без проектирования) имеет следующий вид: 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 c Q Обратим внимание на то, что последняя матрица не вырождена. Рассмотрим пучок прямых, параллельных оси Z, и попробуем разобраться в том, что с ним происходит под действием матрицы Q. Каждая прямая пучка однозначно определяется точкой (скажем, М (х,у,z)) своего пересечения с плоскостью XY и описывается уравнениями t Z y Y x X , , Переходя к однородным координатам и используя матрицу Q, получаем: 1 1 1 или , 1 1 c t t c c t y c t x c t t y x Q t y x В пределе при t→∞ точка (х, у, t, 1) преобразуется в (0, 0, 1, 0). Для того, чтобы убедиться в этом, следует разделить каждую координату на t: t t y t x 1 1 Точка (0, 0, -с, 1) является пределом правой части рассматриваемого равенства при t : 1 0 0 1 1 1 lim c c t t c c t y c t x t Тем самым бесконечно удаленный (несобственный) центр (0, 0, 1, 0) пучка прямых, параллельных оси Z, переходит в точку (0, 0, - с, 1) оси Z. Вообще каждый несобственный пучок прямых (совокупность прямых, 85 параллельных заданному направлению), не параллельный картинной плоскости, 0 , , , n t n z Z t m y Y t l x X под действием преобразования, задаваемого матрицей Q, переходит в собственный пучок c t n t n t m y t l x Q t n t m y t l x 1 1 Центр этого пучка 1 c n mc n lc называется точкой схода. Принято выделять так называемые главные точки схода, которые соответствуют пучкам прямых, параллельных координатным осям. Для преобразования с матрицей Q существует лишь одна главная точка схода. В общем случае (когда оси координатной системы не параллельны плоскости экрана) таких точек три. Матрица соответствующего преобразования выглядит следующим образом: 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 c b a Пучок прямых, параллельных осиOX (1 0 0 0), OY(0 1 0 0) переходит в пучок прямых с центром. На рис. 81 и 82 изображены проекции куба со сторонами, параллельными координатным осям, с одной и с двумя главными точками схода соответственно: 1 0 0 1 0 0 , 1 0 1 0 1 0 0 1 b и a или b и a Точки (-а, 0, 0) и (0, -b, 0) есть главные точки схода. 86 Рис. 81. Проекция куба с одной главной точкой схода Рис. 82. Проекция куба с двумя главными точками схода 4.5. Растровые алгоритмы Подавляющее число графических устройств являются растровыми, представляя изображение в виде прямоугольной матрицы (сетки, целочисленной решетки) пикселей (растра), и большинство графических библиотек содержат внутри себя достаточное количество простейших растровых алгоритмов, таких, как: переведение идеального объекта (отрезка, окружности и др.) в их растровые образы; обработка растровых изображений. Тем не менее, часто возникает необходимость и явного построения растровых алгоритмов. -a -a b 87 4.5.1. Понятие связности Достаточно важным понятием для растровой сетки является связность – возможность соединения двух пикселей растровой линией, т. е. последовательным набором пикселей. Возникает вопрос, когда пиксели (х 1 ,y 1 ) и (x 2 ,y 2 ) можно считать соседними. Вводится два понятия связности: • 4-связность: пиксели считаются соседними, если либо их x-координаты, либо их y-координаты отличаются на единицу (рис. 83): 1 2 1 2 1 y y x x Рис. 83. Пример 4-связности • 8-связность: пиксели считаются соседними, если их x-координаты и у- координаты отличаются не более чем на единицу (рис. 84): 1 , 1 2 1 2 1 y y x x Рис. 84. Пример 8-связности Понятие 4-связности является более сильным: любые два 4-связных пикселя являются одновременно и 8-связными, но не наоборот. Существуют также целые линии, которые также могут быть 4-связными или 8-связными. На рис. 85 изображена 8-связная линия, а на рис. 86 – 4-связная линия. x y x y 88 В качестве линии на растровой сетке выступает набор пикселей P 1 , P 2 , ..., Р n , где любые два пикселя P i , P i+1 являются соседними в смысле заданной связности. Замечание. Так как понятие линии базируется на понятии связности, то естественным образом возникает понятие 4- и 8-связных линий. Поэтому, когда мы говорим о растровом представлении (например, отрезка), следует ясно понимать, о каком именно представлении идет речь. В общем случае растровое представление объекта не является единственным, и возможны различные способы его построения. Рис. 85. 8-связная линия Рис 86. 4-связная линия 4.5.2. Растровое представление отрезка. Алгоритм Брезенхейма Рассмотрим задачу построения растрового изображения отрезка, соединяющего точки А(х а , у a ) и В(х b , y b ). Для простоты будем считать, что a b a b x x y y 0 Тогда отрезок описывается уравнением b a a a b a b a x x x x x x x y y y y , ), ( , или иначе a a a b a b kx y b x x y y k b kx y , , Улучшить внешний вид получаемого растрового отрезка можно за счет округления значений y до ближайшего целого. Фактически это означает, что из двух возможных кандидатов (пикселей, расположенных друг над другом так, что прямая проходит между ними) всегда выбирается тот пиксель, который лежит ближе к изображаемой прямой (закрашенные кружки на рис. 87). Для этого достаточно сравнить дробную часть y со значением 1/2. 89 Рис. 87. Отрезок, получаемый в соответствии с алгоритмом Брезенхейма Пусть х 0 =х а , у 0 =y a , ..., х n =х b , y n =у b – последовательность изображаемых пикселей, причем х i +1–x i =1. Тогда каждому значению x i соответствует число kx i +b. Обозначим через с i дробную часть соответствующего значения функции kx i +b: c i =[kx i + b]. Тогда, если c i ≤½, положим y i =[kx i +b], в противном случае – y i =[kx i +b]+1. Рассмотрим, как изменяется величина с i при переходе от x i к следующему значению x i+1 Само значение функции при этом изменяется на k. Если с i +k≤½, то c i+1 =c i +k, y i+1 =y i В противном случае необходимо увеличить у на единицу и тогда приходим следующим соотношениям: c i+1 =c i +k–1, y i+1 = y i +1, так как kx i +b=y i +c i , kx i+1 +b=y i+1 +c i+1 , а (y i +1) – целочисленная величина. Заметим, что с 0 = 0, так как точка (x 0 , у 0 ) лежит на прямой y=kx+b. Замечание. Выбор точки можно трактовать и так: рассматривается середина отрезка между возможными кандидатами и проверяется, где (выше или ниже этой середины) лежит точка пересечения отрезка прямой, после чего выбирается соответствующий пиксель. Это метод срединной точки (midpoint algorithm). Сравнивать с нулем удобнее, чем с 1/2, поэтому введем новую вспомогательную величину d i =2с-1, заметив, что, d i =2k-1 (так как с 1 =k). B А y x x b y b x a y a 90 Несмотря на то, что и входные данные являются целочисленными величинами и все операции ведутся на целочисленной решетке, алгоритм использует операции с вещественными числами. Чтобы избавиться от необходимости их использования, заметим, что все вещественные числа, присутствующие в алгоритме, являются числами вида p/Δx, Z p . Поэтому если помножить величины d i и k на Δx=x b -x a , то в результате этого останутся только целые числа. Тем самым мы приходим к алгоритму Брезенхейма. 4.6. Алгоритмы вычислительной геометрии 4.6.1. Отсечение отрезка. Алгоритм Сазерленда – Коэна Необходимость отсечения выводимого изображения по границам некоторой области встречается довольно часто. В простейших ситуациях в качестве такой области, как правило, выступает прямоугольник, например, когда нужно вывести изображение на экран в пределах прямоугольного окна. Ниже рассматривается достаточно простой и эффективный алгоритм отсечения отрезков по границе произвольного прямоугольника. Предположим, что у нас есть некоторое окно, внутри которого нарисован отрезок. Т.к. при изменении размера окна возникнет необходимость, чтобы некоторые части отрезка изменялись в соответствии с изменением размера окна, то возникает необходимость применения данного алгоритма. Четырьмя прямыми вся плоскость разбивается на 9 областей (рис. 88). По отношению к прямоугольнику точки в каждой из этих областей расположены одинаково. Рис. 88. Последовательность отсечения отрезка по алгоритму Сазерленда-Коэна Определив, в какие области попали концы рассматриваемого отрезка, легко понять, где именно необходимо произвести отсечение. Для этого каждой области ставится в соответствие 4-битовый код, где установленный бит означает следующее: бит 0 означает, что точка лежит левее прямоугольника, бит 1 означает, что точка лежит выше прямоугольника, А B 91 бит 2 означает, что точка лежит правее прямоугольника, бит 3 означает, что точка лежит ниже прямоугольника. 4.5.2. Алгоритм определения принадлежности точки многоугольнику Одним из методов класса Polygon является метод isInside, служащий для проверки принадлежности точки многоугольнику. Рис. 89. Примеры случаев принадлежности точки многоугольнику Для решения этой задачи выпустим из точки А (x, y) произвольный луч и найдём количество точек пересечения этого луча с границей многоугольника. Если отбросить случай, когда луч проходит через вершину многоугольника, то решение задачи тривиально – точка лежит внутри, если общее число количество точек пересечения нечетно, и снаружи, если четно (рис. 89). Ясно, что для любого многоугольника всегда можно построить луч, не проходящий ни через одну из вершин. Однако построение такого луча связано с некоторыми трудностями и, кроме того, проверку пересечения границы многоугольника с произвольным лучом провести сложнее, чем с фиксированным, например горизонтальным. Возьмем луч, выходящий из произвольной точки А, и рассмотрим, к чему может привести прохождение луча через вершину многоугольника. Основные возможные случаи изображены на рис. 90. В случае а, когда ребра, выходящие из соответствующей вершины, лежат по одну сторону от луча, четность количества пересечений не меняется. Случай б, когда выходящие из вершины ребра лежат по разные стороны от луча, четность количества пересечений изменяется. Рис. 90. Возможные варианты прохождения луча через вершину многоугольника Число пересечений с фигурой три (нечётно) – точка A внутри Число пересечений с фигурой два (чётно) – точка B снаружи B 92 К случаям в и г такой подход непосредственно неприменим. Несколько изменим его, заметив, что в случаях а и б вершины, лежащие на луче, являются экстремальными значениями в тройке вершин соответствующих отрезков. В других же случаях экстремума нет. Исходя из этого, можно построить следующий алгоритм: выпускаем из точки А горизонтальный луч в направлении оси Ох и все ребра многоугольника, кроме горизонтальных, проверяем на пересечение с этим лучом. В случае, когда луч проходит через вершину, т. е. формально пересекает сразу два ребра, сходящихся в этой вершине, засчитаем это пересечение только для тех ребер, для которых эта вершина является верхней. 4.5.3. Закраска области, заданной цветом границы Рассмотрим область, ограниченную набором пикселей заданного цвета, и точку (х, у), лежащую внутри этой области. Задача заполнения области заданным цветом в случае, когда область не является выпуклой, может оказаться довольно сложной. Простейший алгоритм, хотя и абсолютно корректно заполняющий даже самые сложные области, является слишком неэффективным, так как для всякого уже отрисованного пикселя функция вызывается еще 3 раза и, кроме того, этот алгоритм требует слишком большого стека из-за большой глубины рекурсии (рис. 91). Рис. 91. Алгоритм закраски 4-х соседних пикселей относительно заданного Поэтому для решения задачи закраски области предпочтительнее алгоритмы, способные обрабатывать сразу целые группы пикселей, т. е. использовать их «связность» – если данный пиксель принадлежит области, то скорее всего его ближайшие соседи также принадлежат данной области. Ясно, что по заданной точке A(х, у) отрезок [x l , х r ], где x l =x |