Конспект 4-3 (Конспект лекций), страница 2

0 – точка левее прямоугольника,

1 – точка выше прямоугольника,

2 – точка правее прямоугольника,

3 – точка ниже прямоугольника.

Тогда для произвольной точки M(x,y) на прямой L можно определить тетраду (полубайт) принадлежности внутренности прямоугольника, исходя из условия, что если Code = 0000B, точка находится внутри прямоугольника, иначе – точка вне прямоугольника.

ОПРЕДЕЛЕНИЕ ПРИНАДЛЕЖНОСТИ ТОЧКИ

ВНУТРЕННОСТИ МНОГОУГОЛЬНИКА

В общем случае многоугольник ограничивается ломанной p₁, p₂,…, p_n (см. рис. 49). Для некоторой точки M(x,y) задача принадлежности может быть решена путем построения произвольного луча из точки М и определения числа пересечений этого луча с границей многоугольника.

Удобно использовать горизонтальные или вертикальные лучи, тогда:

1. если луч не проходит через вершину (рис.49а), то условие принадлежности точки внутренности многоугольника – нечетное число пересечений луча со сторонами многоугольника, если число пересечений четное, то точка лежит вне многоугольника;

2. если луч проходит через вершину, то возможны следующие 4 варианта

• (рис. 49 б) М₁ и М₂ – простые случаи, ребра, выходящие из вершины лежат либо по одну сторону от луча, либо по разные стороны. Это – экстремальные случаи, и четность числа пересечений инвертируется для М₁ и сохраняется для М_2;

• (рис. 49 в) для точек М₃ и М₄ такой подход непосредственно не годится.

В общем случае получаем алгоритм:

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

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

ЗАКРАСКА ОБЛАСТИ, ЗАДАННОЙ ЦВЕТОМ ГРАНИЦЫ

Рассмотрим область, ограниченную набором пикселей заданного цвета, и точку M(x,y), лежащую в этой области (см. рис. 50).

Задача заполнения заданным цветом,

е сли область не является выпуклой, может

о казаться сложной.

Существуют несколько алгоритмов закраски.

Алгоритм “растекания цвета”:

1. о рганизавать цикл закраски пикселей

до достижения границы области,

2) закрасить пиксель M(x,y) заданным цветом,

1. закрасить соседние пиксели в смысле 4-х

или 8-связности. Рис. 50

Этот алгоритм не эффективен, т.к. для уже закрашенного пикселя функция закраски выполняется еще три раза.

Алгоритм «штриховка»:

1. для заданной точки M(x,y) определить и закрасить максимальный горизонтальный отрезок внутри области,

2. проверить отрезки выше и ниже в поисках незакрашенных пикселей,

3. если такие пиксели найдены, то повторяется п.1.

Алгоритм работает эффективно для областей любой формы.

УДАЛЕНИЕ НЕЛИЦЕВЫХ ГРАНЕЙ

Р ассмотрим многогранник ( рис. 51) и решим задачу

в идимости граней аналогично задаче освещенности,

рассмотренной выше. n₁ n₂

Е сли вектор нормали какой-либо

г рани n составляет с вектором L, задающим n₃

н аправление проецирования, тупой угол,

т о эта грань не видна и называется n₄

н елицевой. L

Когда соответствующий угол является

острым, грань называется лицевой. Рис. 51

В случае параллельного проецирования имеем для лицевой грани

(n,L)  0

При центральном проецировании с центром в точке C вектор проецирования для произвольной точки P будет равен

L = C – P

Условие видимости для любой точки P грани то же

(n,L)  0

Знак скалярного произведения не зависит от выбора тоски p, а определяется тем, в каком полупространстве относительно плоскости, содержащей данную грань, лежит центр проецирования.

Для выпуклого многогранника удаление нелицевых граней решает задачу удаления невидимых ребер.

Рассмотрим подробнее алгоритмы.

УДАЛЕНИЕ НЕВИДИМЫХ ЛИНИЙ

1. Алгоритм Робертса предназначен для фигур, у которых каждая грань – выпуклый многоугольник:

1. отбрасываются все ребра, обе образующие грани которых являются нелицевыми;

2. проверяется каждое из оставшихся ребер со всеми гранями многогранника на закрывание. При этом возможны три случая (см. рис.52):

а ) б) в)

Рис. 52

а) грань не закрывает ребро (рис.52а);

б) грань полностью закрывает ребро, тогда ребро удаляется из списка видимых (рис.52а);

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

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

1. Алгоритм Аппеля применим для произвольного многогранника.

Введем понятие количественной невидимости точки – это количество лицевых граней, закрывающих ее.

Точка является видимой только в случае, если ее количественная невидимость равна нулю. A B

К онтурная линия – это ломанная,

состоящая из ребер, для которых одна D C

и з граней является лицевой, а другая – нелицевой.

Например, линия ABCC’D’DEE’A’A (см. рис.53). E

Количественная невидимость точек ребра A’ B’

и зменяется на единицу при прохождении ребра

позади контурной линии. D’ C’

E’

Рис. 53

Алгоритм определения видимости ребер произвольного многогранника:

а) берется какая-либо его вершина и определяется ее количественная невидимость;

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

в) выполняется переход к следующей вершине и возврат к п.а);

г) если ребро выходит из вершины, принадлежащей контурной линии, проверяется, не закрывается ли это ребро одной из граней (например, линия DD’).

Так как у реальных многогранников количество ребер, входящих в контурную линию, намного меньше общего числа ребер, то алгоритм Аппеля более эффективен, чем алгоритм Робертса.

Удаление невидимых граней

Метод z-буфера (буфера глубины)

Каждому пикселю p(x,y) картинной плоскости, кроме цвета, хранящегося в видеопамяти, сопоставляется расстояние его от картинной плоскости вдоль направления проецирования z (его глубина). Вначале массив глубин инициализируется со значением +.

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

АЛГОРИТМЫ УПОРЯДОЧЕНИЯ

Введем понятие сцены как комплекса изображений пространственных фигур на экране дисплея (или в кадре), т.е. на картинной плоскости.

69