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

 Если отрезок частично видимый, разбиваем его средней точкой на 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	0000	Целиком видим
ij	0010 0110	0010	Целиком невидим
ij	1001 1000	1000	-"-
ij	0101 0001	0001	-"-
ij	0100 0100	0100	-"-
cd	0000 0010	0000	Частично видим
ef	0001 0000	0000	-"-
gh	0001 1000	0000	-"-
kl	1000 0010	0000	Целиком невидим

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

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

у = т(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

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

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

Лабораторная работа N6 по компьютерной графике.

ТЕМА: «Реализация алгоритма отсечения отрезка методом разбиения средней точкой»

Постановка задачи

Реализовать алгоритм отисечения отрезка методом разбиения средней точкой.

Алгоритм разбиения

Для обоих концевых точек отрезка:

1. Проверить видимость конечной точки. Если точка видна, то она – наиболее удаленная видимая точка, иначе:

2. Проверить тривиальную невидимость отрезка.

3. Если отрезок не является тривиально невидимым, то разбить его на два отрезка средней точкой, повторить пункты 1 – 3 с обоими отрезками, если их длина больше заданной погрешности.

Результаты

Окно: (-10, -10, 90, 90)

№ отрезка		Исходный отрезок		Отсеченный отрезок		Расчетный отрезок
1	X1 Y1 X2 Y2		5 10 70 100		5 10 63 91		5 10 63 90
2	X1 Y1 X2 Y2		-30 -50 110 80		11 -11 91 62		10 -10 90 64
3	X1 Y1 X2 Y2		-20 70 70 110		-11 73 27 91		-10 73 27 90
4	X1 Y1 X2 Y2		25 -16 70 -24		Полностью невидим		Полностью невидим
5	X1 Y1 X2 Y2		-25 105 105 -25		-11 90 90 -11		-10 90 90 -10

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

uses

Graph;

type

TRect = record

Left, Top, Right, Bottom: Integer;

end;

procedure DRect(X1, Y1, X2, Y2: Integer);

begin

Rectangle(320 + X1, 240 - Y1, 320 + X2, 240 - Y2);

end;

procedure DLine(X1, Y1, X2, Y2: Integer);

begin

Line(320 + X1, 240 - Y1, 320 + X2, 240 - Y2);

end;

function IntToStr(N: Integer): String;

var

S: String;

begin

Str(N, S);

IntToStr := S;

end;

var

LineY: Integer;

procedure WriteLine(S: String; X1, Y1, X2, Y2: Integer);

begin

S := S + '(' + IntToStr(X1) + ', ' +

IntToStr(Y1) + ', ' +

IntToStr(X2) + ', ' +

IntToStr(Y2) + ')';

OutTextXY(10, LineY, S);

Inc(LineY, 10);

end;

var

Window: TRect;

function EvalCode(X, Y: Integer): Byte;

var

Code: Byte;

begin

Code := 0;

with Window do

begin

Code := Code or Byte(X < Left);

Code := Code or Byte(X > Right) shl 1;

Code := Code or Byte(Y < Bottom) shl 2;

Code := Code or Byte(Y > Top) shl 3;

end;

EvalCode := Code;

end;

procedure DrawLine(X1, Y1, X2, Y2: Integer);

var

Code1, Code2: Byte;

I, Wx, Wy, Mx, My, MemX, MemY: Integer;

Cont: Boolean;

procedure TmpProc;

begin

X1 := X2;

Y1 := Y2;

X2 := Wx;

Y2 := Wy;

Inc(I);

Cont := True;

end;

begin

SetColor(Red);

DLine(X1, Y1, X2, Y2);

SetColor(7);

Inc(LineY, 5);

WriteLine('Линия: ', X1, Y1, X2, Y2);

SetColor(Yellow);

I := 0;

repeat

Cont := False;

Code1 := EvalCode(X1, Y1);

Code2 := EvalCode(X2, Y2);

if Boolean(Code1 or Code2) then

begin

if Boolean(Code1 and Code2) then Exit;

Wx := X1;

Wy := Y1;

if I <= 1 then

begin

if Boolean(Code2) then

begin

repeat

if (X1 = ((X1 + X2) div 2)) and (Y1 = ((Y1 + Y2) div 2)) then

TmpProc

else

begin

Mx := (X1 + X2) div 2;

My := (Y1 + Y2) div 2;

MemX := X1;

MemY := Y1;

X1 := Mx;

Y1 := My;

Code1 := EvalCode(X1, Y1);

if Boolean(Code1 and Code2) then

begin

X1 := MemX;

Y1 := MemY;

X2 := Mx;

Y2 := My;

end;

end;

until Cont;

end

else

TmpProc;

end

else

if not Boolean(Code1 and Code2) then

DLine(X1, Y1, X2, Y2);

end

else

DLine(X1, Y1, X2, Y2);

until not Cont;

SetColor(7);

WriteLine('После отсечения: ', X1, Y1, X2, Y2);

end;

var

GrD, GrM: Integer;

begin

LineY := 10;

DetectGraph(GrD, GrM);

InitGraph(GrD, GrM, '');

SetColor(8);

Line(0, 240, 639, 240);

Line(320, 0, 320, 479);

SetColor(Cyan);

with Window do

begin

Left := -10;

Top := 90;

Right := 90;

Bottom := -10;

DRect(Left, Top, Right, Bottom);

end;

DrawLine(5, 10, 70, 100);

DrawLine(-30, -50, 110, 80);

DrawLine(-20, 70, 70, 110);

DrawLine(25, -16, 70, -24);

DrawLine(-25, 105, 105, -25);

ReadLn;

CloseGraph;

end.