Долгая М.В. Конспект лекций по дисциплине Основы компьютерной графики

Подождите немного. Документ загружается.

ЛЕКЦИЯ 8. АЛГОРИТМ УДАЛЕНИЕ НЕВИДИМЫХ ЛИНИЙ

(по Аммералу)

8.1 Анализ эффективности

Не всегда простые программы лучше сложных. В некоторых задачах простые алгоритмы

работают слишком медленно и требуются более мощные алгоритмы, иногда реализуемые в виде

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

сложность программ будет значительно возрастать, если потребуется авт

оматически удалять

невидимые части отрезков. Наряду со сложностью самой задачи неизбежно возникают другие

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

ности необходимо удовлетворить требования общности, устойчивости к ошибкам и удобства для

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

Начнем с программы, обладающей сложностью порядка

n . Это означает, время

вычислений будет примерно пропорционально

n , где n – число отрезков прямых линий или

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

вычерчивании простых объектов, содержащих несколько сотен граней. Данные, описывающие

объект, будут храниться в масштабах фиксированных размеров. Это также ограничит сложность

объектов. Кроме этих ограничений, в остальном программа будет достаточно общей: в принципе

могут быть вычерчены люб

ые конечные объекты, имеющие только конечное число плоских

граней. Что же касается устойчивости к ошибкам и удобства

пользователей, то не будем

требовать, чтобы все ошибки при их

появлении сопровождались четкими сообщениями и чтобы

объекты определялись наиболее удобным способом. Позднее эта

программа будет

усовершенствована, особенно в отношении эффективности. Проблема удаления невидимых

линий реализуется алгоритмами с чрезвычайно большими затратами вычислительного времени и

она всегда была хорошей задачей для программирующих математиков.

8.2 Входные данные и внутреннее представление

Ребро объекта может закрываться полностью или частично

одной или несколькими

гранями этого же объекта. Каждое ребро — это конечный отрезок прямой линии. Объект может

состоять из нескольких частей, не обязательно соединяющихся между собой. На рис. 10.1

изображены тетраэдр и куб с вершинами, обозначенными числами 0, 1, 2, ... вместо букв А, В, С,

.... Точки

обозначениями 12, 13, 14 позволяют вычертить положительны координатные полуоси.

Рисунок 8.1 - Тетра

эдр и. Куб

Для любой (реальной) точки наблюдения графический вывод будет представлять собой

изображение объекта. В противовес главе 4 будем считать объект непрозрачным. Как и в

параграфе 4.5, пользователь должен задать входные строки данных, определяющие точку О в

прямоугольной системе координат и сферические координаты р,

для точки наблюдения.

Для рис. 1 это будут следующие строки:

2.5 1 1 (центр объекта) 8 20 70 (rho,

theta, phi)

Не будем здесь уделять много внимания удобству пользователя, а лучше введем

концепцию кодирования вершин: поскольку каждая вершина потребуется несколько раз, то было

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

вершины будем задавать ее но

мер от 0 до 11 вместе со значениями координат по осям х, у, z.

Конец этой части вводимой информации будет обозначаться отдельной строкой с символом # в

первой позиции:

0 5 0 0 (x0=5,y0=0,z0=0) 8 2 0 2

1 3 2 0 (x1=3,y1=2,z1=0) 9 2 2 2

2 3 0 0 (и т.д.) 10 0 2 2

3 3 0 2 11 0 0 2

4 2 0 0 12 7 0 0

5 2 2 0 13 0 4 0

6 0 2 0 14 0 0 3

7 0 0 0 #

Точка О объекта является началом системы мировых координат, используемой в

программе (обратите внимание на различие между буквой О и цифр

ой 0). Поскольку она имеет

координаты (2.5,1,1), то внутри программы координаты точек с 0 по 14 будут уменьшены на эти

значения. Так, например точке 9 будут присвоены значения координат (-0.5,1,1) вместо заданных

(2,2,2).

Каждая грань объекта может быть описана в виде любой конечной области плоскости с

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

о назвать

полигон, в котором допустимы также и отверстия. Чтобы программа была проще, пользователь

должен сам разбить такие области на треугольники. Эти треугольники затем будут

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

которые поясним ниже, номера вершин в каждом треугольнике перечисляются в порядке

обхода про

тив часовой стрелки при рассматривании их с внешней стороны объекта. Каждая

грань куба разбивается на два треугольника. Эту часть входных данных опять завершает

символ # (на новой строке).

1 3 0 (треугольные грани тетраэдра)

1 2 3

2 0 3

0 2 1 (передняя грань куба)

4 5 8 (правая грань)

9 6 10

8 9 10 (верхняя грань)

8 10 11

6 7 10 (задняя грань)

10 7 11

7 4 8 (левая грань)

7 8 11

6 5 4 (нижняя грань)

6 4 7

Теперь необходимо задать каждое ребро объекта. Хотя эти ребра уже известны как

стороны тр

еугольников, их следует описать снова. Во-первых, не все стороны треугольников

являются ребрами объекта и, во-вторых, желательно иметь возможность вычерчивания

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

положительных координат полуосей, как показано на рис. 10.1. Как это ни курьезно, но в данном

примере количество входных строк не увеличится, по

скольку ребра объекта, лежащие на

координатных осях, не нужно задавать повторно. Следовательно, имеем 17 входных строк:

(осьх) 6

(ось у) 9

(ось z) 9

(тетраэдр) 10

(куб)

Программа выполнит считывание всех входных данных из Ала, имя которого передается

в качестве аргументов программы (argc и argv), как описано в параграфе 4.5. Координаты каждой

вершины сохраняются в массиве VЕRТЕХ, элементами которого являются структуры, содержащие

три поля х, у, z. Заданные пользовательские координаты сначала переводятся в координаты и

системы, начало которой ра

сположено в объектной точке О. „Внутренние мировые координаты, в

свою очередь, преобразуются в видовые координаты с помощью видовых преобразований (см.

параграф 4.2). И именно эти видовые координаты записываются в массив VЕRТЕХ:

i VЕ

RТЕХ [i]

0 . . .

1 . . .

. . . .

Как мы уже знаем, точка Е — начало системы видовых координат, и направление

наблюдения совпадает с направлением оси 2. Следовательно, все значения VЕRТЕХ [i].z должны

быть положительными. Это условие проверяется в программе, и выполнение программы

прекращается, если оно не выполнено.

Список треугольников запоминается в массиве TRIANGLE:

RIANGLE j]

Вместе с номерами вершин для каждого треугольника записываются коэффициенты а, b,

с, h уравнения плоскости

ax + by + cz = h (10.1)

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

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

поскольку они требуются довольно часто. (Здесь четвертый коэффициент обозначен через h

вмест

о d, так как эта буква уже использована для обозначения расстояния до экрана.)

Коэффициенты а, b, с выбираются такими, чтобы удовлетворялось условие

+ b

+ с

= 1 и h ≥ 0

Тогда уравнение (10.1) можно записать в виде скалярного произведения

n ⋅ x = h

где

n = [ a b c ]

x = [ x y z ]

Так называемый вектор нормали n представляет собой вектор единичной длины,

перпендикулярный плоскости треугольника. Для любой точки Х, в этой плоскости вектор х = ЕХ

имеет такое свойство, что его скалярное произведение h = n ⋅ х равно расст

оянию между точкой Е

и плоскостью.

Скалярное произведение было введено в параграфе 3.2. Заметим, что здесь мы используем

систему видовых координат с точкой Е в качестве начала системы координат и отрезок ЕО

определяет положительное направление оси z. Плоскость, параллельная экрану, описывается

уравнением z = h, которое является вырожденным случаем общего уравнения (10.1) при a=b=0,

c=1. В общем случае коэффициенты a, b, с, h вычисляются по координатам вершин треугольника

А, В, С. В параграфе 3.3 мы видели, что плоскость, проходящая через эти точки, описывается

уравнением

CCC

BBB

AAA

zyx

Это уравнение можно переписать в виде

CCC

BBB

AAA

zyx

=+−

Если мы посмотрим на грань 123 на рис. 10.1 в трехмерном пространстве извне (то есть со

стороны отрицательной полуоси х) порядок обхода вершин 123 при вводе будет против часовой,

поскольку такая ориентация требовалась при определении входной последовательности. Однако

на рис. 10.1 порядок обхода 123 соответствует движению часовой стрелки. Это означает, что на

картинке эта грань видна через тело об

ъекта, а не извне. Таким образом, грань 123 — задняя.

Применение этого способа определения положения граней для других треугольников на рис. 10.1

может послужить хорошим упражнением. Обращаясь к концу параграфа 3.4, можно обнаружить,

что в этом случае требуется найти значение детерминанта

D =

где Х

, Y

, Х

, Y

, Х

, Y

— экранные координаты вершин А, В, С треугольника.

Треугольник АВС будет задним, если D < 0. Но нет необходимости в действительном вычислении

детерминанта, поскольку можно записать

()

CBA

CCC

BBB

AAA

CCCC

BBBB

AAAA

zzzh

zzz

zyx

zyzx

1//

===

(10.2)

Так как значения z

, z

всегда положительны, то D имеет тот же знак, что и величина

h. Если h = 0, то плоскость АВС проходит через точку начала координат Е, совпадающей с точкой

наблюдения. В этом случае треугольник АВС не будет закрывать никаких отрезков и его не надо

запоминать в массиве TRIANGLE. При h < 0 детерминант D также имеет от

рицательный знак и

треугольник АВС является задним. Поэтому треугольник АВС будем записывать в массив только

в том случае, если h > 0 или, другими словами, если D > 0.

С помощью векторного произведения можно убедиться, что треугольник АВС — задний,

из условия h < 0 и без привлечения экранных координат. Но доказательство этого условия оставля-

ем для упражнения читателям с хор

ошей математической подготовкой.

8.3 АЛГОРИТМ ОПРЕДЕЛЕНИЯ НЕВИДИМЫХ ЛИНИЙ

Разработаем теперь очень важный алгоритм, задача которого заключается в вычерчивании

только видимых частей отрезка PQ. Для краткости часто будем записывать "РQ" для обозначения

“отрезка а прямой линии PQ", являющегося частью бесконечной, проходящей через точки Р и Q.

Для каждого треугольника АВС из списка, записанно

го в массив TRIANGLE, необходимо

выполнить проверку — не будет ли он закрывать PQ (или ее часть). Как и ранее, R — точка

наблюдения. Будем говорить, угольник АВС закрывает точку R, если отрезок ЕR пересекает

треугольник АВС в точке, внутренней как по отношению к отрезку, так и по отношению к

треугольнику. Стороны треугольника не относятся к внутренним точкам, а концевые точки

от

резка не являются внутренними для отрезка. Таким образом, тока R не закрывается

треугольником АВС ни в том случае, когда точка R принадлежит внутренней части треугольника,

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

Если треугольник АВС не закрывает точку R, то будем говорить, что точка R видима по

отношению к треугольнику АВС. Если тольк

о конечное число точек отрезка PQ видимо по

отношению к треугольнику АВС, все равно будем говорить, что АВС закрывает РQ. Например, на

рис. 10.1 треугольник 130 закрывает отрезок 12, хотя этот треугольник не закрывает точку 1. Если

треугольник не закрывает РQ, нельзя сделать заключение, что все точки PQ видимы по

отношению к этому треугольнику, поскол

ьку треугольник может закрыть PQ частично.

Треугольник частично закрывает PQ, если он закрывает бесконечно много

Рисунок 8.2 - Пирамида

точек отрезка PQ и в то же время бесконечно много точек этого отрезка остаются

видимыми по отношению к этому треугольнику.

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

треугольники в списке, но можно немедленно пр

ийти к заключению, что PQ закрыт и не должен

вычерчиваться.

Обсудим видимость отрезка прямой линии PQ по отношению к треугольнику АВС в

алгоритмическом смысле. Пусть заданы видовые координаты x

, y

, z

, x

, ,... и так далее для пяти

точек P, Q, A, В, С и коэффициенты а, о, с, h уравнения ах + bу + сz = h. Вся информация о

треугольнике АВС сохраняется в элементе массива TRIANGLE[j]. Ключевым фактором в нашем

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

проходят через стороны треуго

льника АВ, ВС, СА. Эту пирамиду для краткости назовем одним

словом "пирамида", а треугольник АВС — термином "треугольник".

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

пирамиды — видимыми (относительно данного треугольника). На рис. 10.2 отрезок прямой линии

PQ пересекает пирамиду в двух точках — I и J. Часть IJ отрезка PQ будет невидимой, а части PI

JQ — видимыми. (Ради краткости вместо фразы "видимый по отношению к треугольнику АВС"

будем применять термин "видимый".)

Сложность нашей задачи заключается в очень большом количестве случаев, которые

предстоит рассмотреть. В ситуации, показанной на рис. 10.2, можем вычислить положение точки I

следующим образом. Векторное представление прямой линии PQ записывается в виде

ЕР+λr

где r = [r

] = РQ, откуда

= x

- x

= y

- y

= z

- z

точка (x, y, z) принадлежит прямой линии PQ, если

x = x

+ λr

y = y

+ λr

(10.3)

z = z

+ λr

Для значений λ между 0 и 1 точка лежит между точками Р и Q. Уравнение плоскости ЕАВ

может быть записано как

BBB

AAA

zyx

поскольку эта плоскость проходит через точки Е(0, 0, 0), А, В. Уравнение можно

переписать в виде

x + С

y + С

z = 0 (10.4)

где

= y

– y

= x

– x

= x

– x

Подставляя правые части уравнений (10.3) в уравнение (10.4), находим

()

332211

321

rCrCrC

zCyCxC

PPP

−=

(10.5)

Используя значение λ в уравнении (10.3), получаем координаты точки I. Изображенная на

рис. 10.2 ситуация возникает только тогда, когда значение λ находится в пределах от 0 до 1. Для

других значений λ точка I лежит не на отрезке РQ, а на одном из его продолжений. Нельзя

утверждать, что при значении λ от 0 до 1 отрезок РQ пересекает пирамиду, верн

о лишь обратное

утверждение. На рис. 10.3 показана ситуация, видимая из точки Е, когда значение λ лежит в

пределах от 0 до 1, хотя отрезок РQ не пересекает пирамиду.

Возвращаясь к трехмерному пространству (рис. 10.2), можно представить плоскость,

проходящую через прямую линию PQ и точку наблюдения Е. Теперь мы хотим узнать, не будет

ли эта пло

скость проходить через точки, принадлежащие отрезку АВ.

Рас. 10. 3 Отрезок РQ вне пирамиды

Здесь необходимо выполнить вычисления, аналогичные проводимым при определении

значения λ. Запишем векторное представление прямой линии АВ

ЕА + μ АВ

Тогда точка (х, у, z) принадлежит прямой линии АВ, если

)(

ABA

zzzz

yyyy

xxxx

−+=

(10.6)

Для значений μ. от 0 до 1 точка лежит между А и В.

Уравнение плоскости ЕРQ

QQQ

PPP

zyx

Перепишем это уравнение в виде

321

+ zKyKxK (10.7)

где

PQQP

QPPQ

PQQP

yxyxK

zxzxK

zyzyK

−=

−

Совмещая уравнения (10.6) и (10.7), получаем

)()()(

321

ABABAB

AAA

zzKyyKxxK

zKyKxK

−+−+−

(10.8)

Отрезок прямой линии РQ и плоскость пирамиды ЕАВ имеют общую точку, если, и

только если

0 ≤ λ ≤ 1 и 0 ≤ μ ≤ 1

До сих пор мы рассматривали пересечение прямой РQ только с одной из плоскостей

пирамиды, а именно с ЕАВ. Необходимо также рассмотреть плоскости ЕВС и ЕСА. Отрезок РQ

может не иметь либо иметь одн

о или два пересечения с пирамидой. Соответственно, точки Р и Q

могут лежать внутри, вне или на пирамиде, то есть располагаться впереди, позади или на

плоскости АВС. Для проверки каждой пары из одного отрезка и одного треугольника может

потребоваться большой объем работы. Обычно имеется очень много отрезков прямых, и каждый

из них н

еобходимо проверять относительно большого количества треугольников. Такие проверки

нужно выполнять с большой эффективностью. Желательно как можно раньше начинать с таких

случаев, которые встречаются наиболее часто, особенно если не требуются большие затраты

машинного времени. При успешном выполнении теста остальные тесты игнорируются.

Тест1 (рис. 10.4)

Если точки Р и Q лежат пер

ед или на плоскости АВС (но не позади нее), то отрезок PQ —

видимый. Это происходит когда

n EP ≤ h и n EQ ≤ h

где n=[a b c]. Напомним, что коэффициенты а, Ь, с, h появились в уравнении (10.1) и они

записаны в элементе массива TRIANGLE[j].

Тест1 охватывает и тот важный случай, когда PQ представляет собой одну из сто

рон

треугольника.

Рис. 10.4. Точки. Р и Q расположены не сзади плоскости

Тест2 (рис.10.5)

Если бесконечная прямая линия РQ лежит вне пирамиды, то линия PQ видима. Для

выполнения теста можно подставить значения координат точек А, В, С в левую часть уравнения

(10.7), определяющего плоскость ЕPQ. Если все три вычисленных значения (для точек А, В и С)

имеют о

динаковые знаки (все положительные или все отрицательные), то все точки А, В, С лежат

по одну сторону от плоскости ЕРQ

(а)

Рис.10.5.

(а) — модуль суммы знаков = 3; (б) — модуль суммы знаков = 2

Следовательно, линия РQ расположена вне пирамиды и является видимой. Несколько ос-

лабим это знаковое условие в том смысле, что один из знаков может быть равен нулю.

Предположим, что каждый из знаков обозначается одним из чисел -1, 0, 1, и проверим, не будет ли

сумма знаков для точек А, В, С равн

а одному из чисел -3, -2, 2, 3. Заметим, что на рис. 10.5(б)

может произойти и такой случай, когда точка Р совпадает с точкой А. Это тоже очень важный

специальный случай.

Тест3

Теперь найдем точку пересечения прямой линии РQ с плоскостями ЕАВ, ЕВС и ЕАС.

Вычислим значения параметров λ для то

чки пересечения прямой линии РQ с плоскостью ЕАВ по

уравнению (10.5) и μ для точки пересечения прямой АВ с плоскостью ЕРQ по уравнению (10.8).

(В обоих случаях прямая линия может оказаться параллельной плоскости, поэтому параметрам λ и

μ будут присвоены очень большие числа.) Уравнение (10.4) описывает плоскость ЕАВ. Если левая

часть эт

ого уравнения при подстановке координат точек Р и С принимает разные знаки, то это

означает, что точки Р и С лежат по разные стороны от прямой АВ. Тогда можно сказать, что точка

Р лежит за прямой АВ. Если точка лежит за одной из сторон треугольника, то она расположена

вне этого тр

еугольника. Запомним эту информацию в логической переменной Poutside ("точка Р

вне").

Рис.10.6 (а) – точки P и Q за АВ; (б) – точка Р за АВ, точка Q на АВ

Аналогично для точки Q введена переменная Qoutside ("точка Q вне"). Эти переменные

будут проверяться в тестах 4 и 6. Если точки Р и Q лежат за одной и той же ст

ороной треугольника

или одна точка находиться за стороной, а другая — точно на этой стороне, то будем говорить, что

отрезок РQ лежит вне этого треугольника. Тогда отрезок PQ — видимый. Обе ситуации показаны

на рис. 10.6. Важный специальный случай возникает при небольшой модификации рис.10.6(б),

когда точка Q совпадает с точкой А. Заметим, что в отличие от рис.1

0.5(б) бесконечная прямая

линия РQ на рис.10.6(б) может пересекать отрезок ВС между точками В и С так, что тест 3 будет

выполнен в том случае, когда тест 2 оказался невыполненным.

Большая часть работы должна быть выполнена трижды, а именно: для каждой из

плоскостей ЕАВ, ЕВС и ЕСА, следовательно, будем иметь три пары значений (λ

, μ

) (I = 1, 2, 3).

Затем найдем минимальное и максимальное из значений λ

, удовлетворяющие условиям

0 ≤ λ ≤ 1 и 0 ≤ μ ≤ 1

и эти значения обозначим М1N и МАХ, соответственно. Они являются побочным

продуктом этого теста и определяются только тогда, когда отрезок РQ пересекает треугольник, то

есть если тесты 3 и 4 (см. ниже) не выполнены.

Тест4 (рис. 10.7)

Если и точка Р, и точка Q находятся внутри пирамиды, а предыдущий тест не

удовлетворен, то от

резок РQ лежит позади треугольника и, следовательно, невидим.

При выполнении этого теста также может встретиться весьма хитрая ситуация.

Предположим, например, что отрезок РQ лежит на пирамиде позади отрезка АВ. Поскольку

отрезок РQ не находится ни снаружи, ни внутри пирамиды, то кажется сомнительным, можем

ли мы сказать, что треугольник закрывает отрезок PQ. Однако отр

езок АВ может быть не

ребром, а диагональю грани. Тогда эта грань определенно закрывает отрезок и он не должен

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

РQ вычерчивать было бы не нужно, поскольку изображение отрезка РQ совпадало бы с ребром

АВ, а чертить совпада

ющие отрезки линий нет никакого смысла.

Рис. 10.7. Отрезок РQ позади треугольника АВС

Тест 5 (рис. 10.8)

Если точка I, в которой прямая линия РQ пересекает пирамиду, лежит впереди

треугольника, то прямая PQ видима. Этот тест основан на том факте, что объект является

сплошным телом, поэтому прямая РQ не может проходить через внутренние точки треугольника.

Для нахождения такой точки I используем значения МIN и МАХ пар

аметра λ, вычисленные при

выполнении теста 3. Затем можно просто проверить, не будет ли скалярное произведение векторов

ЕI и n = [а b c] меньше, чем h.

Тест 6

Этот тест выполняется только в том случае, если все предыдущие тесты не дали

положительного результата, то есть когда прямая PQ пересекает пирамиду позади треугольника.