книги / Основы САПР. CAD CAM CAE

72		Глава з. Основные концепции графического программирования
glRotated(GldouЫe angle.		GldouЫe х. GldouЫe у, GldouЫe z);

/* Умножает текущую матрицу на матрицу поворота объекта на угол angle против часовой стрелки вокруг луча. проведенного из начала координат в точку (х. у, z). */

Рассмотрим несколько примеров, поясняющих применение матриц преобразо­

ваний.

Пример 3.1

Объект в трехмерном пространстве транслируется на 5 единиц в направлении у мировой системы координат, после чего поворачивается на 90° вокруг оси х той

же системы координат. Если координаты точки объекта в модельной системе

имеют значения (0, О, 1), какими будут мировые координаты этой точки после трансляции и вращения?

Zw

Решение

Координаты (Х~.,У~, Z~ ) после преобразования трансляции могут быть вычисле­

ны следующим образом:

[Х~ У~ Z~]т = Trans(0,5,0)[0 О 1 1]т =[О 5 1 1]т

После этого применяется преобразование вращения:

[Х.., У." Z.., 1]т = Rot(x, 90° )[О 5 1 1]т

Следовательно, координаты точки после преобразований будут иметь значения (0, -1, 5). Обратите внимание, что предыдущие выражения можно объединить:

[Х", У", Z11, 1]т =Rot(x, 90°)Trans(0,5,0)[0 О 1 1]т

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

ординат множества точек. В последнем случае матрицы трансляции и вращения

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

ния в соответствующей последовательности называется конкатенацией (concatenation). Возможность выполнения конкатенации - одно из преимуществ ис­ пользования однородной системы координат, в которой трансляция записывается

через матричное умножение, а не через сложение.

Пример 3.2

Объект в пространстве поворачивается на 90° вокруг оси, параллельной оси х

мировой системы координат и проходящей через точку с мировыми координа-

3.7. Матрица преобраэования

73

тами (0, 3, 2). Если точка объекта имеет модельные координаты (0, О, 1), какими

будут мировые координаты той же точки после поворота?

Zw

Xw

Решение

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

вектор (0, -3, -2) даст нам совпадение оси вращения с осью х мировых коорди­

нат. Затем мы повернем объект вокруг осихна 90°, после чего сместим его об­ ратно на вектор (0, 3, 2), чтобы вернуться к исходному положению.

Эти операции могут быть записаны следующим образом:

[Х", Yu. Z111 1]т =Trans(0,3,2)Rot(x, 90°)Trans(0,-3,-2)[0 О 1 1]т

Обратите внимание на последовательность матриц в этой формуле. Результат легко проверить, применяя преобразования одно за другим, как в примере 3.1.

Раскрывая выражение, получим:									ш		о ~~1r11=
		о	о	о	1	о	о	о		о
	1 т == [1о		о1	о	13 о cosо90"			о		о	о
[Xw у"' z!D								-sin 90"		1	о
	]	О	О	1	2	О	sin 90°	cos 90"		о	1

==[О 4 -1 1]т

Результат соответствует приведеиной выше иллюстрации.

3.7.3. Отображение

Отображение (mapping) состоит в вычислении координат точкивнекоторой систе­ ме координат по известным координатам той же точки в другой системе координат.

Рассмотрим две системы координат (рис. 3.19). Предположим, что координаты

(X 2 ,Y2 ,Z2 )точки Р в системе координат x 2 y2 z2 должны быть вычислены по коор­

динатам (X1 ,Y1 ,Z1 )той же точки в системех1у1 z1• Далее, предположим, что вы­

числение производится применением матрицы преобразования Т1_2 к известным

координатам:

(3.11)

74	Глава З. Основные концепции графического программирования

Xt

Рис. 3.19. Отображение из одной системы координат в другую

Записав матрицу Тн в явном виде, мы получим из формулы (3.11) следующее

выражение:

о_,.	Рх][Х•]		(3.12)
	Ру	У.
	р,	z•.

оо 1 1

Чтобы найти неизвестные в уравнении (3.12), подставим в него конкретные зна­ чения Х1 = О, У1 = О и Z1 = О, в результате чего получим:

х2 =р_,.,У2 =р.ч,Z2 =р,.

(3.13)

Можно сказать, что р~, Ру и р, определяют координаты начала отсчета системы

x 1y 1z1 в системе координат x2y2 z2•

Теперь подставим в уравнение (3.12) значения Х1	= 1, У1 =О, Z 1 =О и получим:
Х2 =nx +р,.,У2 =ny +р_ч,Z2	=n, +р,.	(3.14)

Вычитая формулы (3.13) из (3.14), можно заключить, что nx, ny и n,- компонен­

ты х2, у2 и z2 единичного вектора, направленного вдоль оси х1 системы коорди­

нат х1 у1 z1• Следовательно, коэффициенты п_.., п_ч и n, легко вычислить с учетом взаимной ориентации систем координат.

Аналогичным образом, о_,., оу и о, представляют собой компоненты х2, у2 и z2 еди­

ничного вектора оси у 1, а компоненты а_,, ау и а,- вектора оси z1•

Следующий пример демонстрирует предлагаемую теорию в действии.

Пример 3.3 По заданному положению точки зрения (-1 О, О, 1), точки наблюдения (0, О, 1)

ивектора вертикали (0, О, 1) строится наблюдательская система координат

(см. представленный ниже рисунок). Обратите внимание, что все координатьr

икомпоненты векторов даны в мировой системе координат. Зная относительное

положение системы координат просмотра и мировой системы координат, рас­

считать:

76	Глава 3. Основные концепции графического nрограммирования

Решение

Наблюдательская система координат может быть изображена так, как показано

на рисунке выше. Заштрихованный треугольник на этом рисунке параллелен плоскости экрана. В этой плоскости лежат оси х,, и у11•

Чтобы вычислить элементы Тw-rл нам нужно получить компоненты х," у,, и z,, осей xi'DI Yw и Zw· Для этого обозначим единичные векторы осей Xv, у,, и Z11 буквами iv. jv и kv соответственно. Единичные векторы осей х~" Yw и Zw будут называться просто i, j и k.

Единичный вектор kv направлен из точки наблюдения в точку зрения, поэтому

k 1. 1. 1k v=.JЗI+.JЗJ+.JЗ •

Как отмечалось в разделе 3.2, единичный вектор jv должен быть коллинеарен

проекции вектора вертикали на экран. Другими словами, его направление будет

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

ли составляющей, перпендикулярной экрану. Обозначив вектор вертикали uP, запишем выражение для jv.

Последний единичный вектор iv вычисляется через векторное произведение:

.	. k	1 . 1 .
1v = Jv Х		v = -./21 + .J2 J.

Теперь вычислим п.т - компоненту х,, оси xw - как произведение:

. . 1

1·1v= -J2'

Аналогичным образом, компонента n9 равна

. . 1

1· Jv = --/6'

а компонента nz равна

i·kv=Jз.

Таким же путем получим второй и трети~ столбцы матрицы Т11,_1,. Компоненты

PJ.~ р9 и Pz можно не вычислять, потому что в этом примере начала координат на­

блюдательской и мировой систем совпадают. Следовательно, матрица преобра­

зования выглядит так:

	1	1	о	о
	-.J2	.J2
	1	1	2	о
т"_v =	-~	-~	~
	1	1	1	о
	.J3	..[3	.J3	1
	о	о	о

3.7. Матрица преобразования

77

Координаты точки (0, О, 5) в наблюдательской системе имеют значение

[Хи Уи Zи 1]т =Tw-v ·[О О 5 1]т =[о 5~ 5~ 1г

Экранные координаты точки в изометрической проекции получаются из наблю­

дательских координат непосредственно:

(о 5~}

Изометрическая проекЦия относится к параллельным, поэтому все точки на

оси Zw проецируются на ось у экранн~;>rх координат. Фактически задание вектора

вертикали, равного (0, О, 1), означает; что после проецирования ось Zw представ­

ляется на экране в виде вертикальной прямой.

3.7.4. Другие матрицы преобраэования

Помимо матриц преобразования, рассмотренных в предыдущих разделах, часто

используются матрицы масштабирования и зеркального отображения.

Для масштабирования объекта с коэффициентом sx по оси х, s11 по оси у, s, по оси z применяется следующая матрица преобразования:

(3.15)

Для двумерных объектов матрица масштабирования редуцируется до разме­ ра 3х3, как это было с матрицами трансляции и поворота. Эффекта масштабиро­

вания можно достичь, изменив размеры видового экрана или окна, не меняя зна­

чений координат.

Матрица преобразования (3.15) используется при масштабировании объекта от­ носительно начала координат. Часто бывает необходимо масштабировать объект относительно одliой из его точек Р с координатами (Хр, У,1, Zp). В этом случае

сначала к точке Р применяется преобразование трансляции Trans(-ХР, - Ур, -Zp),

которое перемешает эту точку в начало координат, затем применяется матрица

масштабировани.11 из (3.15), после чего объект возвращается в исходное положе­ ние действием Trans(Xp, Ур, Zp)·

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

ется в изменении знака координаты z.

[~}[~~~~~JIO	(3.16)

Матрицы преобразования для других отражений (относительно плоскостей xz

и yz) выводятся аналогичным образом.

78	Глава 3. Основные концепции графического программирования

3.8. Удаление невидимых линий и поверхностей

Проекция на экран станет более наглядной, если будет содержать только ви­

димые линии и nоверхности. Удале1luе иеаиди.мых лииий (hidden-/ine removal) заключается в блокировании отображения отрезков, скрытых от наблюдателя,

а удалеиие 1lевиди.мых поверхиостей (hidden-surface l'emoval) есть то же самое по отношению к nоверхностям. Удаление невидимых линий иллюстрируют рис. 3.20

и рис. 3.21. Очевидно, что эта nроцедура значительно облегчает восnриятие объ­

екта.

Рис. 3.20. Изображение до удаления невидимых линий

Рис. 3.21. Изображение после удаления невидимых линий

Оnубликовано множество nрограммных алгоритмов удаления невидимых линий

иnоверхностей. Их авторы nытаются nовысить вычислительную эффективность

ирасширить диаnазон объектов для nрименения своих алгоритмов. Однако луч­

ше всего удаление реализуется nосредством графического устройства, которое

называется z-буфером1, nоэтому в настоящее время исследования на эту тему nрактически не ведутся. В настоящем разделе мы рассмотрим несколько тиnич­

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

атакже изучим метод исnользования для той же цели z-буфера.

1Z-буфером называется область nамяти, аналогичная буферу кадра в том смысле, что

в нс\1 хранятся данные обо всех ликсслах. Однакоn z-буфере хранятся не цвета пикселов,

а z-коордшшты объектов, к 11роскцням которых эти лнкселы относятся. Коорщ1ната z из­

меряется в ttаблюдательскоii системе и потому является мерой расстояния от наблюдате­ ля до объекта.

3.8. Удаление невидимых линий и поверхностей

79

3.8.1. Алгоритм удаления невидимых граней

Алгоритм удшzеиия иевидимьtх граией (back-face removal algorithm) основан на том,

что грань объекта может быть видимой только в том случае, если вектор внеш­

ней нормали к этой грани направлен в сторону наблюдателя. В противном слу­

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

рис. 3.22, считается видимой, если вектор внешней нормали N имеет положи­

тельную составляющую в направлении вектора М, проведеиного из точки на гра­

ни к наблюдателю. Математически это записывается так:

Оесли М · N > О, поверхность видима;

Оесли М · N = О, поверхность проецируется в отрезок;

Оесли М · N < О, поверхность невидима.

Рис. 3.22. Векторы, определяющие видимость грани

Этот алгоритм легко применить к объекту, ограниченному плоскими поверхно­

стями, поскольку вектор нормали N постоянен в пределах поверхности. Однако

к вогнутому1 объекту алгоритм неприменим, поскольку грань, направленная

к наблюдателю, может быть закрыта другой гранью того же объекта (рис. 3.23). Та же проблема возникает в случае нескольких выпуклых объектов, которые мо­

гут закрывать грани друг друга. Следовательно, алгоритм удаления невидимых

граней применим только к одному выпуклому объекту. Более того, алгоритм не­ применим к объектам, для которых вектор внешней нормали определяется неод­ нозначно2 (см., например, рис. 3.24 ).

Если поверхности объекта не являются плоскими, значение N будет меняться в пределах одной грани в зависимости от выбранной точки. Одновременно может меняться и знак произведения М · N. Это означает, что у одной и той же грани будут как видимые, так и невидимые участки. Поэтому грань должна быть разде­ лена на две части вдоль кривой, на I<аторой выполняется равенство М · N = О.

Эта кривая называется силуэтиой лu1шей (sillюuette line). После разделения гра­

ни вдоль силуэтной линии знак М N будет постоянным на каждой из частей

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

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

невидимых граней - простота реализации.

1 Объскt называется вогнутым, если по крайней мере две его грани смыкаются nод внут­

ренним углом, большим 180°. Если все грани смыкаются с внутренними углами, меньши­

ми 180°, объект называется выпуклым.

2Такой объект вообще представляет собоt! достаточно сложную проблему, о чем будет

рассказано u глаuе 5.

3.8. Удаление невидимых линий и поверхностей

81

Легко сраnнивать координаты Z,, поверхностей, если максимальное значение Z,. одной из них меньше минимального значения Z11 другой. Однако в большинстве

случаев диапазон значений Z,, точек одной поверхности перекрывается с диапа­

зоном Z" другой поверхности. Неоднозначности можно избежать, разбивая все

поверхности на отдельные части до тех пор, пока диапазоны Z,, не перестанут пе­

рекрываться. Есть и другой, более простой в реализации способ решения про­

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

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

в нужной последовательности. Чем меньше размер треугольников, тем меньше шансов, что их диапазоны Zv перекроются. Такое приближение поверхности объ­ екта называется трuа1tгуляцией (triangulation) или фасетироваиием.

3.8.3. Алгоритм удаления невидимых линий

Алгоритм сортировки по глубине используется для удаления невидимых по­ верхностей. Алгоритм невидимых граней позволяет построить рисунок со скры­ тыми линиями, но имеет множество ограничений в общем случае. При примене­ нии алгоритма невидимых граней к множеству объектов удалено будет лишь около 50% невидимых линий. Нам нужен алгоритм, который удалял бы все не­

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

криволинейных поверхностей.

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

объектов. Закрытые части ребер последовательно исключаются до тех пор, пока не останется непроверенных поверхностей. Оставшиеся части всех ребер выво­

дятся на экран.

Реализация алгоритма включает несколько этапов.

1.Поверхности, направленные к наблюдателю, выделяются из всех остальных в отдельную группу при помощи алгоритма невидимых граней. Выделенные поверхнрсти сохраняются в массив FАСЕ-ТABLE. Грани, направленные от

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

а потому не скрывают ребра других граней. Для каждой грани сохраняется

максимальное и минимальное значение Zv. Криволинейные поверхности раз­ деляются по силуэтным линиям (как в алгоритме невидимых граней), а види­ мые части этих поверхностей также сохраняются в массиве FАСЕ-ТABLE

вместе с плоскими гранями.

2.Ребра граней из массива FАСЕ-ТABLE выделяются из всех прочих ребер и собираются в отдельный список. Ребра других граней, не входящих в FАСЕ­ ТABLE, можно не рассматривать, поскольку они невидимы. Затем для каждо­ го ребра из списка производится проверка, не закрывается ли это ребро гра­

нью из FАСЕ-ТABLE.

1Ребром объекта называется кривая пересечения соседних поверхностей, ограничиваю­

щих внутренний объем объекта.

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