71

4.Удаление невидимых элементов

Задача удаления невидимых линий (hidden lines) и поверхностей (hidden surfaces) является одной из наиболее сложных в машинной графике. Сложность задачи привела к появлению большого числа различных способов ее решения. Наилучшего решения общей задачи удаления невидимых линий и поверхностей не существует.

Существует тесная взаимосвязь между скоростью работы алгоритма и детальностью его результатов. Ни один из алгоритмов не может достигнуть хороших оценок для этих двух показателей одновременно. Все алгоритмы удаления невидимых элементов включают в себя сортировку. Главная сортировка ведется по геометрическому расстоянию от тела, поверхности, ребра или точки до точки наблюдения. Основная идея, положенная в основу сортировки по расстоянию, заключается в том, что чем дальше расположен объект от точки наблюдения, тем больше вероятность, что он будет полностью или частично заслонен одним из объектов, более близких к точке наблюдения. После определения расстояний или приоритетов по глубине проводится сортировка по горизонтали и по вертикали. Эффективность любого алгоритма удаления невидимых элементов в большой степени зависит от эффективности процесса сортировки.

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

4.1.Алгоритм Робертса

Алгоритм Робертса представляет собой первое известное решение задачи об удалении невидимых линий (1963 г.) для векторных устройств вывода графической информации. Метод работает в объектном пространстве.

Метод требует, чтобы моделируемое тело было выпуклым. Невыпуклые объекты должны быть расчленены на выпуклые, для каждого из которых осуществляются необходимые расчеты. Суть алгоритма заключается в том, что на основании расчета нормалей к каждой грани объекта все грани, имеющие неположительные нормали по отношению линии наблюдения, полагаются нелицевыми. Разделение граней объекта на лицевые и нелицевые позволяет решить вопрос о видимости ребер.

Алгоритм Робертса для обработки геометрической модели отдельного объекта, включающей топологические отношения, введенные во 2-ом разделе настоящего курса, имеет следующий вид.

1. Для каждой грани (, n –количество граней модели) выполнить следующие действия:

• исходя из топологического отношения (дескриптора грани) f_i(S) для трех последовательных вершин L, M и N (рис.4.1,а) и значений координат этих вершин в дескрипторе S(X,Y,Z) определить проекцию вектора нормали к данной грани на ось аппликат согласно (2.5) или (3.9) и расчетной схемы (рис.4.1,б):

• если n_Z > 0, то установить признак видимости грани, иначе установить признак невидимости грани.

2) Для каждого ребра, исходя из топологического отношения A(F), выполнить:

• если обе грани ребра имеют признак невидимости, то ребро получает признак невидимости, иначе - признак видимости.

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

В таблицах 4.1 и 4.2 приведены расчетные данные по определению видимости граней и ребер модели (рис.2.1), подвергшейся преобразованиям поворотов и изометрии (табл.3.4). На рис.4.2 представлена каркасная визуализация рассчитанной модели.

Табл.4.1.Последовательность действий по определению признаков видимости

F

F(S)

L

M

N

xL

yL

xM

yM

xN

yN

f1

s2

s1

s4

s7

s2

s1

s4

120a

20b

70a

70b

70a

170b

f2

s1

s2

s5

s1

s2

s5

70a

70b

120a

20b

20a

20b

f3

s3

s2

s7

s3

s2

s7

80a

80b

120a

20b

110a

190b

f4

s2

s3

s5

s2

s3

s5

120a

20b

80a

80b

20a

20b

f5

s6

s3

s7

s4

s6

s3

s7

20a

120b

80a

80b

110a

190b

f6

s5

s6

s4

s1

s5

s6

s4

20a

20b

20a

120b

70a

170b

f7

s3

s6

s5

s3

s6

s5

80a

80b

20a

120b

20a

20b

граней по алгоритму Робертса

F	yM-yN	yN-yL	yL-yM	xL(yM-yN)	xM(yN-yL)	xN(yL-yM)	nZ	видимость
f1	-100b	150b	-50b	-12000ab	10500ab	-3500ab	<0	-
f2	0	-50b	50b	0	-6000ab	1000ab	<0	-
f3	-170b	110b	60b	-13600ab	13200ab	6600ab	>0	+
f4	60b	0	-60b	7200ab	0	-1200ab	>0	+
f5	-110b	70b	40b	-2200ab	5600ab	4400ab	>0	+
f6	-50b	150b	-100b	-1000ab	3000ab	-7000ab	<0	-
f7	100b	-60b	-40b	8000ab	-1200ab	-800ab	>0	+

Табл.4.2.Определение видимости ребер по алгоритму Робертса

A

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

A(F)

f2

f7

f6

f4

f1

f6

f3

f5

f2

f5

f1

f4

f1

f5

f7

f3

f5

f2

f1

f6

f4

f3

f6

f7

Видимость

-

+

-

+

-

-

+

+

-

+

-

+

граней

-

+

+

+

+

-

-

-

+

+

-

+

ребер

-

+

+

+

+

-

+

+

+

+

-

+