Алгоритм разбиения средней точкой

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

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

 

На рис.5.1 показана плоская сцена и отсекающее окно регулярной формы. Окно задается левым (Л), правым (П), верхним (В) и нижним (Н) двумерными ребрами. Регулярным отсекающим окном является прямоугольник, стороны которого параллельны осям координат объектного пространства или осям координат экрана. Целью алгоритма отсечения является определение тех точек, отрезков или их частей, которые лежат внутри отсекающего окна. Эти точки, отрезки или их части остаются для визуализации. А все остальное отбрасывается.

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

Точки, лежащие внутри отсекающего окна, удовлетворяют условию:

x_л <= х <= x_п и у_н <= у <= у_в.

 

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

Отрезок лежит внутри окна и, следовательно, является видимым, если обе его концевые точки лежат внутри окна, например отрезок ab на рис. 5.1. Однако если оба конца отрезка лежат вне окна, то этот отрезок не обязательно лежит целиком вне окна, например отрезок gh на рис. 5.1. Если же оба конца отрезка лежат справа, слева, выше или ниже окна, то этот отрезок целиком лежит вне окна, а значит, невидим. Проверка последнего условия устранит все отрезки, помеченные ij на рис. 5.1. Но она не устранит ни отрезка gh, который видим частично, ни отрезка kl, который целиком невидим.

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

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

для первого бита - если точка левее окна

для второго бита - если точка правее окна

для третьего бита - если точка ниже окна

для четвертого бита ~ если точка выше окна

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

 

Если побитовое логическое произведение кодов концевых точек отрезка не равно нулю, то отрезок полностью невидим и его можно отбросить тривиально. Несколько примеров, приведенных в табл.5.1, помогут прояснить высказанные утверждения. Из табл.5.1 видно, что если результат логического умножения не равен нулю, то фактически отрезок будет целиком невидим. Однако если логическое произведение равно нулю, то отрезок может оказаться целиком или частично видимым или даже целиком невидимым. Поэтому для определения полной видимости необходимо проверять значения кодов обоих концов отрезка по отдельности.

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

Таблица 5.1. Коды концов отрезков

Отрезок (рис.5.1)	Коды концов (рис.5.2)	Результаты логического умножения	Примечание
ab	0000 0000		Целиком видим
ij	0010 0110		Целиком невидим
ij	1001 1000		-"-
ij	0101 0001		-"-
ij	0100 0100		-"-
cd	0000 0010		Частично видим
ef	0001 0000		-"-
gh	0001 1000		-"-
kl	1000 0010		Целиком невидим

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

Пересечение двух отрезков можно искать как параметрическим, так и непараметрическим способами. Очевидно, что уравнение бесконечной прямой, проходящей через точки Р₁ (х₁ , у₁) и Р₂ (х₂, у₂), имеет вид

у = т(x - х₁) + у ₁ , или у = т(х - х₂ ) + у₂ , где m = (у₂ - у₁)/ (x₂ - x₁ ) - это наклон данной прямой.

Точки пересечения этой прямой со сторонами окна имеют следующие координаты:

с левой: x_л , у = т(х_л - х₁) + у₁ т??

с правой: x_п, у = т(x_п - x₁) + у₁ т??

с верхней: у_в, х = x₁ + (1/т)(у_н - у₁) т? 0

с нижней: у_н, х = х₁ + (1/т)(у_н - у₁) т? 0

В примере 1 показано, как этот простой метод позволяет отбросить некорректные пересечения путем простого сравнения координат точек пересечения с координатами сторон окна.

Пример 1. Простое двумерное отсечение

Рассмотрим отсекающее окно и отрезки, изображенные на рис.5.3.

Наклон отрезка от Р₁ (- 3/2, 1/6) до Р₂ (1/2, 3/2) равен m = (у₂ - у₁)/ (x₂ - x₁ ) = (3/2 - 1/6)/ [1/2 - (- 3/2)] = 2/3. Его пересечения со сторонами окна таковы:

с левой:.x = -1 у = (2/З) [-1 - (- 3/2)] + 1/6 = 1/2

с правой: x =1 y = (2/3)[1 - (- 3/2)] + 1/6 = 11/6

(последнее число больше, чем у_в и поэтому отвергается)

с верхней: у =1 х = - 3/2+ (3/2)[1 - 1/6] = - 1/4

с нижней: y = - 1 x = - 3/2 + (3/2)[- 1 - (1/6)] = - 13/4

(последнее число меньше, чем х_л, и поэтому отвергается).

 

Аналогично, отрезок от Р₃ (- 3/2, - 1) до Р₄ (3/2, 2) имеет

(у₂ - у₁) &nbsp2- (- 1)
m = ---- = ------- = 1 (x₂ - x₁ ) &nbsp3/ 2 - (- 3/ 2)

и пересечения:

с левой: х = - 1 у = (1)[- 1 - (- 3/2)] + (- 1)= - 1/2

с правой: х = 1 у = (1)[1 - (- 3/2)] + (-1) = 3/2

(последнее число больше, чем у_в, и поэтому отвергается)

с верхней: y = 1 x = - 3/2 + (1)[1 - (- 1)] = 1/2

с нижней: у = - 1 x = - 3/2 + (1)[-1 - (-1)] = - 3/2

(последнее число больше, чем х_л, и поэтому отвергается).

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