ОТСЕЧЕНИЕ
· Алгоритм двумерного отсечения
Сазерленда-Коэна
· Алгоритм трехмерного отсечения
Сазерленда-Коэна
· Алгоритм двумерного отсечения Кируса-Бека
· Алгоритм трехмерного отсечения Кируса-Бека
· Особенности реализации внешнего и
комбинированного отсечений
Отсечение – это процесс, связанный с выделением и визуализацией фрагмента плоской или
пространственной сцены, расположенного внутри (внутреннее отсечение)
или, наоборот, вне (внешнее
отсечение) некоторой соответственно
двумерной или трехмерной отсекающей фигуры (отсекателя).
Оставшаяся часть сцены при этом игнорируется, т.е. визуализации не подлежит.
При реализации такого процесса используются
алгоритмы двумерного или трехмерного отсечения. Специфика
конкретного алгоритма определяется, в первую очередь, формой отсекающей фигуры, которая может быть регулярной (стандартной,
такой, например, какую имеют прямоугольник или прямоугольный параллелепипед)
или нерегулярной (нестандартной). При регулярной форме отсекателя
важным фактором является также его ориентация относительно системы координат.
Как уже отмечалось, изображение в
компьютерной графике формируется с использованием, прежде всего, отрезков.
Совокупностями определенным образом ориентированных отрезков представляются не
только ломаные линии, многоугольники и многогранники, но также разомкнутые и
замкнутые кривые. Трехмерные поверхности аппроксимируют наборами плоских
полигонов, ограниченных многоугольниками (чаще всего, треугольниками), т.е. опять
же наборами отрезков. Поэтому и алгоритмы отсечения работают, в первую очередь,
с отрезками.
Алгоритм
двумерного отсечения Сазерленда-Коэна
Данный алгоритм реализует
отсечение отрезков координатно-ориентированным прямоугольником, границы
которого: левая, правая, нижняя и верхняя – задаются координатами
соответственно xл
, xп ,
yн и yв (рис.8.1).
При таком
отсечении отсекатель часто называют отсекающим
окном. Рассмотрим сначала основные принципы построения алгоритма применительно
к внутреннему отсечению. Точка P (x, y) находится внутри отсекающего окна, если ее координаты
удовлетворяют двум условиям:
;
(здесь
и далее принадлежность точки границе отсекателя приравнивается случаю ее
расположения внутри него).
Если для обоих концов отрезка
эти условия выполняются, он целиком расположен внутри отсекающего окна, т.е.
является, как говорят, полностью видимым (как отрезок ab на рис.8.1). Если оба конца отрезка находятся левее
отсекающего окна (их горизонтальные координаты удовлетворяют неравенству 
, как у отрезка cd ) отрезок
безусловно невидим. То же самое можно сказать про отрезки, расположенные
целиком правее, ниже или выше отсекателя (для обоих концов отрезков при этом
справедливы неравенства соответственно 
, 
или 
). Сложности возникают при отсечении таких отрезков,
как ef и ij. Изначально они не идентифицируются как полностью
видимые или безусловно невидимые. В действительности
же каждый из таких отрезков может быть частично видимым (как отрезок ef ) или
полностью невидимым (как отрезок ij ). Поэтому при анализе подобных отрезков необходимы какие-либо
формальные методы, позволяющие определить реальные точки пересечения отрезков с
границами отсекающего окна или установить, что они отсутствуют. Задача
нахождения реальной точки пересечения отрезка с какой-либо одной границей
отсекателя возникает и в случае, когда один из концов отрезка расположен внутри
отсекающего окна, а второй – вне его (как у отрезка gh).
В алгоритме Сазерленда-Коэна
при обработке отрезков используются четырехразрядные (битовые) коды, определяющие
расположение концов отрезков относительно границ отсекающего окна – концевые
коды. При формировании кода конца отрезка с координатами (x, y) в первый
(крайний правый) бит заносится 1, если x < xл , во второй – если x > xп ,
в третий – если y < yн , в четвертый – если y > yв .
В остальных случаях в соответствующие биты заносится 0. Таким образом, вся
координатная плоскость разбивается на девять областей, в каждой из которых
концу отрезка присваивается уникальный концевой код (см. рис.8.1). Выявить
целиком видимый отрезок при этом достаточно просто: оба концевых кода у него
полностью нулевые (как у отрезка ab на рис.8.1). Если отрезок не идентифицирован как целиком видимый, для
него определяется также побитовое логическое произведение концевых кодов.
Очевидно, что у отрезков, целиком расположенных левее, правее, ниже или выше
отсекающего окна, в какой-либо один разряд обоих концевых кодов при их
формировании будет занесено по 1; это обусловит наличие 1
в соответствующем разряде побитового логического произведения этих концевых
кодов (так, у отрезка cd,
расположенного целиком левее отсекающего окна, с кодами концов 0101
и 0001
побитовое логическое произведение равно 0001). Поэтому отличное от нуля
побитовое логическое произведение является признаком безусловной невидимости
отрезка. Вместе с тем, при полностью нулевом побитовом логическом произведении
концевых кодов отрезок может оказаться частично видимым (как отрезки ef и gh) или полностью невидимым (как отрезок ij ). Для
подобных отрезков при выявлении их видимых частей или идентификации как
полностью невидимых используются результаты расчета точек пересечения
бесконечной прямой линии, проведенной через отрезок, с бесконечными прямыми
линиями, проведенными через ребра отсекающего окна.
Для отрезка с началом в точке
(
,
) и концом
в точке 
(
,
), если он
не вертикален (
), такие точки пересечения на прямых,
проведенных через левое и правое ребра, будут иметь координаты соответственно:
, 
; 
, 
.
Если отрезок не горизонтален
(
), координаты аналогичных точек пересечения на прямых,
проведенных через нижнее и верхнее ребра, будут равны
соответственно:
, 
; 
, 
.
Последовательность действий в алгоритме двумерного
внутреннего отсечения Сазерленда-Коэна следующая. С использованием концевых
кодов отрезок проверяется на полную видимость и безусловную невидимость. Если
проверка не дает очевидного результата, поочередно работают четыре бесконечные
отсекающие прямые, проходящие соответственно через левое, правое, нижнее и
верхнее ребра отсекающего окна. В каждом случае проверяется,
не лежит ли отрезок полностью в той же стороне от отсекающей прямой, что и само
окно (очевидно, например, что если в первом бите кодов концов отрезка
содержится 0, отрезок полностью лежит правее левой отсекающей прямой).
Если это так, переходят к следующей отсекающей прямой.
В противном случае проверяют, не лежит ли начало отрезка в той же стороне, что
и окно. Если это подтверждается, начало и конец отрезка меняются
местами. Начало отрезка в любом случае оказывается по
отношению к отсекающей прямой в стороне, противоположной той, в которой
находится окно. После определения точки пересечения прямой,
проведенной через отрезок, с текущей отсекающей прямой начало отрезка
переносится в эту точку (удаляется часть отрезка). Полученный новый
отрезок вновь проверяется на полную видимость и безусловную невидимость. В
зависимости от результата переходят к следующей
отсекающей прямой или алгоритм заканчивает работу.
Практическая реализация
алгоритма двумерного отсечения Сазерленда-Коэна представлена на следующих
примерах
Алгоритм трехмерного отсечения
Сазерленда-Коэна
При помощи этого алгоритма можно осуществлять
отсечение отрезков двумя наиболее распространенными объемными отсекателями
регулярной формы: координатно-ориентированным прямоугольным параллелепипедом
(рис.8.2а) и усеченной пирамидой (рис.8.2б), называемой также пирамидой
видимости. Каждый из названных отсекателей имеет
шесть граней: левую, правую, нижнюю, верхнюю, ближнюю
и дальнюю. Так же, как и при двумерном отсечении, положение каждого конца
отсекаемого отрезка относительно границ отсекателя (точнее – относительно
бесконечных плоскостей, проходящих через его грани) можно связать с
соответствующим концевым кодом, имеющим в данном случае шесть разрядов (бит).
Границы первого отсекателя –
прямоугольного параллелепипеда – задаются шестью координатами: 
, 
, 
, 
, 
и 
(рис.8.2а). При этом процесс формирования кода конца отрезка с координатами (x, y, z) полностью аналогичен тому, который применяется при
двумерном отсечении: 1 заносится в первый (крайний
правый) бит, если (конец левее отсекателя), во второй – если (конец правее отсекателя), в третий – если (конец ниже отсекателя), в четвертый – если (конец выше отсекателя), в пятый – если 
(конец ближе отсекателя), в шестой – если 
(конец дальше
отсекателя);
в остальных случаях в соответствующие биты заносится 0.
При использовании в качестве отсекателя усеченной
пирамиды концевые коды формируются с учетом специфики геометрии данного
объемного тела. Допустим, что она задана следующим образом
(рис.8.4а и 8.4б): 
– z-координата центра
проекции, расположенного на оси z; и – координаты
соответственно ближней и дальней граней по оси z; и – координаты
соответственно левой и правой граней по оси x при 
(см. рис.8.4а);
и – координаты соответственно нижней и верхней граней по
оси y при (см. рис.8.4б).
Для анализа положения конца
отрезка относительно левой, правой, нижней и верхней граней отсекающей пирамиды
используются так называемые пробные функции. Идея их составления довольно
проста. Уравнения плоскостей, несущих указанные грани, будут выглядеть
соответственно так (см. рис.8.4):
; 
;
; 
.
Пробные функции применительно к этим граням совпадают с
левыми частями приведенных уравнений:
; 
;
; 
.
Значение пробной функции
после подстановки в нее координат конца отрезка (x, y, z) позволяет определить положение этого конца
относительно соответствующей грани и, в свою очередь, заполнить надлежащим
образом соответствующий бит концевого кода. При внутреннем отсечении это
осуществляется так.
Если 
, конец расположен левее плоскости левой грани, и в
первый бит концевого кода заносится 1; если же 
или 
, конец расположен соответственно на плоскости левой
грани или правее нее, и в первый бит заносится 0.
Если 
, конец расположен правее плоскости правой грани, и во
второй бит концевого кода заносится 1; если же 
или 
, конец расположен соответственно на плоскости правой
грани или левее нее, и во второй бит заносится 0.
Если 
, конец расположен ниже плоскости нижней грани, и в
третий бит концевого кода заносится 1; если же 
или 
, конец расположен соответственно на плоскости нижней
грани или выше нее, и в третий бит заносится 0.
Если 
, конец расположен выше плоскости верхней грани, и в
четвертый бит концевого кода заносится 1; если же 
или 
, конец расположен соответственно на плоскости верхней
грани или ниже нее, и в четвертый бит заносится 0.
Аналогичный подход применим и
для заполнения пятого и шестого битов концевых кодов с учетом положения концов
отрезка относительно ближней и дальней граней. Уравнения плоскостей, проходящих
через эти грани, выглядят соответственно так:
; 
.
Вид соответствующих пробных
функций очевиден:
; 
.
Если после подстановки в
первую из них z-координаты
конца отрезка 
, конец расположен перед плоскостью ближней грани, и в
пятый бит концевого кода заносится 1; если же 
или 
конец
расположен соответственно на плоскости ближней грани или за ней, и в пятый бит
заносится 0.
Если после такой же
подстановки во вторую пробную функцию оказывается, что 
, конец расположен за плоскостью дальней грани, и в
шестой бит концевого кода заносится 1; если же 
или 
конец
расположен соответственно на плоскости дальней грани или перед ней, и в шестой
бит заносится 0.
Таким образом, если отсечение
осуществляется прямоугольным параллелепипедом, то все координатное пространство
разбивается на двадцать семь областей, в каждой из которых концу отрезка
присваивается уникальный код.
Если отсекателем является
усеченная пирамида, координатное пространство разбивается в общем случае на
тридцать шесть областей с уникальным кодом конца отрезка в каждой из них:
двадцать семь областей – спереди от центра проекции, т.е. перед точкой
наблюдения, и девять – позади от центра проекции, т.е. за точкой наблюдения.
Вместе с тем, представляется
целесообразным использовать иной подход к решению этой задачи. Все, что
находится позади от центра проекции, наблюдатель видеть не может. Поэтому,
независимо от того, какое именно отсечение реализуется – внутреннее или
внешнее, начать обработку трехмерной сцены можно с удаления ее части,
расположенной за центром проекции, т.е., иными словами, в полупространстве 
(здесь и далее принадлежность
точки плоскости 
приравнивается
случаю ее расположения перед этой плоскостью). Применительно к конкретному
отрезку с началом в точке (,,
) и
концом в точке (,,
) это можно
сделать, используя данную плоскость в качестве отсекающей (по аналогии с
работой бесконечной отсекающей прямой, проходящей через ребро отсекающего
прямоугольника, в алгоритме двумерного отсечения Сазерленда-Коэна).
Последовательность действий
при этом должна быть следующей. Сначала следует проверить, не принадлежит ли
весь отрезок полупространству . Если это подтверждается (z-координаты концов отрезка удовлетворяют неравенствам 
, 
), отрезок идентифицируется как полностью невидимый, и
обработка завершается. В противном случае проверяется, не
расположен ли отрезок целиком в доступном наблюдению замкнутом полупространстве
. Если это так
(
, 
), можно приступать к основной обработке (к отсечению
отрезка пирамидой видимости), если нет (что на данном этапе проверки возможно в
случаях, когда , или , ) – надо найти точку пересечения отрезка с плоскостью и перенести в нее
тот конец отрезка, который оказался позади от центра проекции.
Координаты точки пересечения определяются путем подстановки в уравнение прямой,
проведенной через отрезок, т.е. в уравнение вида
,
значения .
Введем обозначения (все они будут использоваться и далее в
рамках настоящего раздела):
; 
;
.
Используя два из них, запишем решения приведенного выше
уравнения относительно координат искомой точки пересечения в следующем виде:
; 
; .
Если в результате описанных
действий отрезок не идентифицирован как целиком невидимый, его следует
подвергнуть дальнейшей обработке традиционным для алгоритма Сазерленда-Коэна
образом. При этом концам отрезка, каждый из которых гарантированно попадает в
одну из двадцати семи областей перед центром проекции, присваиваются вполне
адекватные концевые коды (как и в случае отсечения отрезка
прямоугольным параллелепипедом).
При изложенном подходе
последующие действия алгоритма трехмерного отсечения Сазерленда-Коэна при обеих
возможных формах отсекателя будут полностью аналогичны тем, которые
осуществляются в соответствующем алгоритме двумерного отсечения. Приведем их
краткое описание.
Если после определения
концевых кодов выясняется, что оба они равны нулю, отрезок полагается видимым
полностью, и обработка заканчивается. Если это не подтверждается, то
вычисляется побитовое логическое произведение концевых кодов. При отличном от
нуля значении этого произведения отрезок идентифицируется как
безусловно невидимый, что также приводит к завершению обработки. При полностью
нулевом побитовом логическом произведении отрезок может оказаться как частично
видимым, так и полностью невидимым. Дальнейшая его обработка связана с
поочередной работой шести бесконечных отсекающих плоскостей, несущих
соответственно левую, правую, нижнюю, верхнюю, ближнюю и дальнюю грани
объемного отсекателя (по аналогии с работой четырех бесконечных отсекающих прямых,
проходящих через ребра отсекающего прямоугольника а
двумерном алгоритме отсечения). В каждом случае проверяется, не лежит ли
отрезок полностью в той же стороне от отсекающей плоскости, что и сам
отсекатель. Если это так, переходят к следующей отсекающей плоскости. В
противном случае проверяют, не лежит ли начало отрезка в той же стороне, что и
отсекатель. Если это подтверждается, начало и конец отрезка меняют местами.
Начало отрезка в любом случае оказывается по отношению
к отсекающей плоскости в стороне, противоположной той, в которой находится
отсекатель. После определения точки пересечения прямой, проведенной через
отрезок, с текущей отсекающей плоскостью начало отрезка переносится в эту точку
(удаляется часть отрезка). Полученный новый отрезок вновь проверяется на полную
видимость и безусловную невидимость. В зависимости от результата переходят к
следующей отсекающей плоскости или алгоритм завершает работу.
Алгоритм двумерного отсечения Кируса-Бека
Данный алгоритм реализует отсечение
отрезков произвольным выпуклым многоугольником. В его основу положено
параметрическое представление отрезка.
Параметрическая форма записи уравнения отрезка с концами и имеет следующий вид:
,
где t – параметр, принимающий значения
в диапазоне 
.
В декартовой системе
координат приведенное выше уравнение сводится к двум одномерным параметрическим
уравнениям:
; 
;
здесь , и , – координаты соответственно начала и конца
отрезка.
На координатной плоскости xy точкам начала и конца отрезка можно поставить в соответствие
векторы (рис.8.5):
; 
;
в
приведенных выражениях 
и 
– это единичные векторы (орты), направленные
вдоль осей x и y соответственно.
Для вектора, связанного с
произвольной точкой 
отрезка, выражение в параметрическом виде
запишется так:
.
Точке f (расположенной, например, на границе 1 отсекателя в одной из сопряженных с этой
границей вершин, см. рис.8.5) с координатами 
и 
будет
соответствовать вектор
.
Ориентацию же точки относительно
точки f
можно характеризовать вектором
.
О расположении произвольной точки , принадлежащей отрезку 
, по отношению к какой-либо границе
(например, опять к границе
,
где 
– вектор внутренней (т.е. направленной внутрь
отсекателя) нормали к данной границе.
Если это произведение больше или меньше
нуля, то точка расположена относительно границы, точнее –
относительно бесконечной прямой, проходящей через границу, соответственно в той
же стороне, что и сам отсекатель, или в противоположной (рис.8.5). И
только в том случае, когда это произведение равно нулю, точка лежит непосредственно на
указанной прямой и является возможной точкой
пересечения (рис.8.5).
Поэтому в алгоритме Кируса-Бека реальные
точки пересечения отрезка с границами отсекающего многоугольника ищутся среди
решений уравнений вида
;
здесь 
– внутренняя нормаль к i-ой к границе
многоугольника, 
–
вектор, соответствующий принадлежащей этой границе точке 
, 
– значение
параметра t в возможной точке пересечения отрезка с i-ой
границей.
После подстановки в это уравнение выражения для вектора 
в параметрическом виде оно будет выглядеть так:
.
Введем обозначения: 
– вектор,
называемый директрисой отрезка и соединяющий начало отрезка с его концом; 
–
вектор, соединяющий точку с
началом отрезка.
Используя
вновь введенные векторы, преобразуем последнее уравнение и решим его в общем
виде относительно 
:
.
Полученное выражение позволяет рассчитывать
значения параметра отрезка в возможных точках пересечения с границами
отсекающего многоугольника при условии, что 
(случай 
является особым и будет рассмотрен ниже). Если при внутреннем отсечении найденное значение выходит за
пределы интервала 
, то его следует проигнорировать (как значения 
и 
для отрезка на рис.8.6),
т.к. соответствующая точка пересечения, несмотря на то, что она лежит на
прямой, проходящей через отрезок, самому отрезку не принадлежит. Вместе
с тем, количество полученных значений , принадлежащих указанному интервалу, может оказаться
больше двух (
, 
, 
, 
и
для отрезка на
рис.8.6).
В этом случае среди группы точек с`
– группы нижнего предела ( и на рис.8.6), расположенных ближе к началу
отрезка, следует выбрать точку с максимальным значением параметра, т.к. именно она является
реальной точкой пересечения и определяет так называемый нижний предел 
(
на
рис.8.6). Среди группы точек с`
– группы верхнего предела (, и на рис.8.6),
лежащих ближе к концу отрезка, надо выбрать точку с минимальным значением
параметра,
т.к. она является реальной точкой пересечения и определяет верхний предел (
на
рис.8.6). В случае, когда и 
определены,
т.е. выявлены две реальные точки пересечения, часть отрезка между этими точками
будет видима, и ее следует визуализировать
(здесь и далее полагается, что реализуется внутреннее отсечение).
Практическая реализация алгоритма двумерного отсечения Кируса-Бека представлена на примере, программная реализация которого составлена студентами
и сотрудниками МИРЭА (Морозов М.Н.)
Алгоритм трехмерного отсечения Кируса-Бека
Данный алгоритм осуществляет отсечение отрезков
произвольным выпуклым многогранником. По сути, он является полным аналогом
соответствующего двумерного алгоритма. В нем применяются абсолютно те же
подходы, что и в двумерном варианте, но распространенные на трехмерный случай. Понятие «граница (или сторона, или ребро) отсекающего
многоугольника», используемое в двумерном алгоритме, в трехмерном алгоритме
трансформируется в понятие «граница (или грань) отсекающего многогранника».
Бесконечные прямые, проведенные через ребра многоугольника, заменяются
бесконечными плоскостями, несущими грани многогранника. Все векторы в трехмерной
версии алгоритма имеют не две, а три компоненты: вдоль координатных осей x, y и z. В выражениях для векторов при записи третьей компоненты
используется единичный вектор (орт) 
, направленный вдоль оси z.
При этом, однако, надо учитывать следующее. В трехмерной
версии значение M должно соответствовать числу граней отсекающего
многогранника. Подпрограмма расчета скалярного
произведения векторов реализуется по аналогии с тем, как это сделано в
двумерном алгоритме, но векторы 
и 
задаются
тремя компонентами (по осям x, y и z): Вект1x, Вект1y, Вект1z и Вект2x, Вект2y, Вект2z
соответственно.
Рассмотрим пример работы
трехмерного алгоритма Кируса-Бека при внутреннем отсечении отрезка с координатами
начала и конца соответственно (–2,
–1, 1/2) и (3/2, 3/2, –1/2) кубом (
) с гранями, заданными координатами 
, 
, 
, 
, 
, 
(рис.8.7).
При
проведении расчетов полагалось, что в главном цикле грани обрабатываются в
следующей последовательности: левая (
), правая (
), нижняя (
), верхняя (
), ближняя (
), дальняя (
). Причем при обработке левой, нижней и дальней граней
в качестве точки f
использовалась вершина куба с координатами (–1, –1, –1), а при обработке правой,
верхней и ближней граней – вершина куба с координатами (1, 1, 1). Векторы
внутренних нормалей задавались по геометрическим соображениям.
Таким образом, отрезок частично видим в интервале изменения
значений параметра от 
до 
. Подстановка этих значений в одномерные параметрические
уравнения отрезка дает координаты точек пересечения, соответствующих нижнему и верхнему пределам (см. также рис.8.7):
,
,
;
,
,
.
До начала работы трехмерного
алгоритма Кируса-Бека необходимо убедиться в выпуклости отсекающего
многогранника, а также определить внутренние нормали к его границам (граням).
Практическая реализация алгоритма трехмерного отсечения Кируса-Бека представлена на примере,
Особенности реализации внешнего и
комбинированного отсечений
Задачи внутреннего отсечения
легко адаптировать к решению задач внешнего отсечения. Для этого достаточно
учесть только то обстоятельство, что результаты внешнего отсечения могут быть
получены путем инвертирования (обращения) результатов внутреннего отсечения:
отрезки или их части, которые при внутреннем отсечении определяются как
видимые, при внешнем отсечении на экран не выводятся, и, наоборот, отрезки или
их части, которые алгоритмом внутреннего отсечения игнорируются, при внешнем
отсечении идентифицируются как видимые и визуализируются.
В ряде случаев может возникнуть необходимость
осуществления комбинации внутреннего и внешнего отсечений, т.е.
комбинированного отсечения. Характерный пример подобного
отсечения наблюдается на экране компьютерного дисплея при многооконном режиме
его работы под управлением операционной системы Windows (рис.8.8): содержимое рабочей
области пассивного окна 3 подвергается внутреннему отсечению прямоугольником,
образованным границами этой области; само окно 3 со всем содержимым подвергается
внешнему отсечению окнами 1 и 2, имеющими приоритеты выше, чем окно 3.
Комбинированное отсечение
позволяет реализовать также внутреннее или внешнее отсечение графических
объектов невыпуклыми (частично вогнутыми)
отсекателями. При этом в качестве базового используется соответствующий
алгоритм двумерного или трехмерного отсечения Кируса-Бека.
