кривых Безье, так что ri (1) = ri+1 (0), i = 0...n -1. При этом легко контролировать непрерывность первой производной.

6.5.3. Удаление невидимых частей изображения. Закрашивание граней

6.5.3.1 2D алгоритм Сазерленда-Кохена

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

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

Рисунок 59 – Разбиение плоскости по алгоритму Сазерленда-Кохена. Алгоритм сводится к следующей последовательности действий для каж-

дого из обрабатываемых отрезков:

1. Определяются коды для концов отрезка. Для одного из них в нотации языка Си построение кодов выглядит так:

int code1=0;

if ( y < YB ) code1 |= 0x01; if ( y > YT ) code1 |= 0x02; if ( x > XR ) code1 |= 0x04;

129

if ( x < XL ) code1 |= 0x08; // побитовое <OR>

2.Определяются отрезки, которые не нужно обрабатывать(т.е. они либо полностью лежат внутри прямоугольника, как отрезок |AB| на рисунке, либо полностью невидимы, как отрезок |CD|):

int inside = ( code1 | code2 ) == 0;

int outside = ( code1 & code2 ) != 0; // побитовое <AND> while ( !outside && !inside ) {выполнять пункт 3}

3.Если отрезок видим частично, идёт его постепенное усечение до границы области вывода, пользуясь уравнением прямой. Подобная процедура выполняется для каждого установленного в единицу бита в коде каждого из концов отрезка. Например, для младшего бита следует проводить усечение по границе

Y

B:

if ( code1 & 0x01 )

{

x1 += (long)(x2-x1)*(YB-y1)/(y2-y1);

y1 = YB;

}

// подобным образом для остальных трёх битов, и переход к п. 1

4. If inside, рисуется видимая часть отрезка с помощью растрового алгоритма (Брезенхема).

6.5.3.2 3D алгоритм Робертса, алгоритм Варнока

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

1. Алгоритмы объектного пространства: за основу берётся система ми-

ровых координат. Для такого типа алгоритмов характерны сложные векторные расчёты и высокая точность результатов. Объём вычислений ~ n2 , где n – число объектов.

2. Алгоритмы пространства изображений: за основу берётся система двумерных экранных координат. Характерны высокая скорость (объём вычислений ~ n × N , где N – число пикселей) и низкая точность расчётов.

130

3. Алгоритм Робертса – первое известное решение задачи об удалении невидимых граней. Относится к алгоритмам объектного пространства. При этом требуется, чтобы все изображаемые тела или объекты были выпуклыми фигурами20, а грани тел являлись плоскостями(рисунок 60). Хорошо подходит для отображения каркасных объектов.

Рисунок 60 – Объект с плоскостными гранями Общая схема алгоритма такова:

1.Находятся нелицевые плоскости для каждого тела в сцене. Отбрасыва-

ются все рёбра, обе определяющие грани которых являются нелицевыми.

2.Удаляются из рассмотрения те рёбра, которые экранируются всеми остальными телами в сцене. При этом рассматриваются случаи(а) полной видимости или невидимости ребра; (б) частичной видимости ребра, в этом случае ребро делится на несколько отрезков.

3.Создаётся список всех видимых рёбер и отрезков рёбер, которые затем будут визуализированы.

Рассмотрим более подробно первую часть алгоритма Робертса:

Пусть грань принадлежит плоскости ax + by + cz + d = 0 . Плоскость одно-

значно определяется вектором P = [a b c d ]T . В дальнейшем будем считать,

что введена нормировка d =1. Любое выпуклое тело можно выразить матрицей тела V, определяющей все его грани:

	éa1		a2		...an ù
V	êb		b		...b		ú	(59)
	= ê	1	c	2	...c	n	ú
	êc					n	ú
	ê	1		2			ú
	ë	1	1...1				û

20

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

131

Пусть S – точка в однородных координатахS = [x y z 1] . Если точка принадлежит плоскости, то S × P = 0 . Если же точка не принадлежит плоскости, то знак скалярного произведения показывает, по какую сторону от плоскости расположена точка.

Как же нам найти коэффициенты для(59), если наше тело задано, как обычно бывает, координатами вершин? Связать уравнение плоскости и координаты трёх точек(например, вершин), лежащих в этой плоскости, можно сле-

дующим образом:

éx1

y1

z1 ù

éaù

é-1ù

ê

ú

ê

ú

ê

ú

y2

z2

×

=

или X × P = -1 .

(60)

êx2

ú

êb

ú

ê-1ú

,

êx

3

y

3

z

3

ú

êc

ú

ê-1ú

ë

û

ë

û

ë

û

= -X -1

)

Отсюда

P

×1 .

Перед началом работы алгоритма удаления невидимых линий и поверхностей для получения желаемого вида сцены часто применяется трёхмерное видовое преобразование.

Пусть B – матрица однородных координат вершин тела, T – матрица ви-

дового преобразования. Тогда
B* = B ×T	(61)

где B * – преобразованная матрица вершин.

Очевидно, что B ×V = 0 , так как V – матрица тела. Напишем аналогичное выражение и для преобразованных матриц: B *×V * = 0 , хотя пока V *нам неиз-

вестна. Найдём её, исходя из вышесказанного:
B * ×V * = B ×V .	(62)
Тогда, исходя из (63) B ×T ×V * = B ×V , т.е. преобразованная матрица тела
выражается так:
V * = T -1 ×V .	(63)

C помощью (61) можно добиться выполнения следующего правила: ска-

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

132