27. Отсечение нелицевых граней.

Пусть у нас есть объект, внутри которого камера заведомо не окажется. Обычно такие объекты составляют большую часть или всю сцену. Тогда для каждой грани мы можем увидеть только одну ее сторону - лицевую. Грань - плоскость, она делит все 3D пространство на два полупространства. Так вот, лицевую сторону видно только из одного полупространства, из того, в которое "смотрит" нормаль к этой грани, направленная *из* объекта. Проверив, в какое полупространство попадает камера, можно сразу определить, является ли грань лицевой (то есть, может ли камера увидеть лицевую сторону этой грани) и надо ли ее рисовать.

Пусть грань имеет вершины v1, v2, v3 и нормаль (nx,ny,nz). Тогда уравнение плоскости, в которой она лежит, будет иметь вид

nx*x+ny*y+nz*z+d = 0.

d находим из того факта, что v1 в плоскости лежит:

nx*v1.x+ny*v1.y+nz*v1.z+d = 0, d = -(nx*v1.x+ny*v1.y+nz*v1.z).  Функция nx*x+ny*y+nz*z+d принимает положительные значения по одну сторону от плоскости, отрицательные по другую и равна нулю на самой плоскости. Точка (v1.x+nx,v1.y+ny,v1.z+nz) лежит, очевидно, в том полупространстве, откуда грань видно. Значение функции (назовем ее функцией видимости) в этой точке равно

nx*(v1.x+nx)+ny*(v1.y+ny)+nz*(v1.z+nz)+d = nx*(v1.x+nx)+ny*(v1.y+ny)+nz*(v1.z+nz)-(nx*v1.x+ny*v1.y+nz*v1.z) = nx*nx+ny*ny+nz*nz > 0.  Таким образом, если значение функции в какой-то точке больше нуля, то грань из этой точки потенциально видна. Нас интересует видимость грани из нашей камеры, а камера у нас зафиксирована в точке (0,0,-dist). Таким образом, получаем, что грани, для которых

-nz*dist-(nx*v1.x+ny*v1.y+nz*v1.z) < 0,

или, что равносильно,

nz*dist+nx*v1.x+ny*v1.y+nz*v1.z > 0,

заведомо не видны и время на их обработку и отрисовку тратить не стоит.

Отдельный вопрос - как считать нормали к граням. Точнее, как выбрать одну из двух нормалей, которая будет смотреть из объекта. Обычно эта проблема решается еще на этапе построения 3D моделей - например, пакет 3D Studio записывает вершины граней в порядке A-B-C так, чтобы векторное произведение BA*CA и было нормалью. Еще один способ - выбрать внутренную точку для объекта (либо вручную, либо взять его центр тяжести, либо еще как-нибудь - методов может быть придумано сколько угодно) и использовать ее: если для этой точки функция видимости положительна, то есть грань якобы видна, то надо поменять знак nx, ny и nz.

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

28. Однородные координаты и их особенности.

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

Далее большими буквами X, Y, Z будут обозначаться обычные декартовые координаты, а маленькие буквы x, y, z будут использоваться для обозначения т.н. однородных координат.

 Двумерные геометрические преобразования

Параллельный перенос

 

 

Параллельный перенос в плоском случае имеет вид:

 

x` = x + Dx

y` = y + Dy

 

[x’, y’] = [x, y] + [Dx, Dy]

 

P’ P T

 

или в векторной форме:

P` = P + T,

где P` = [x` y`] - вектор-строка преобразованных координат,

 

где x, y - исходные координаты точки, Tx, Ty - величина сдвига по осям, x`, y` - преобразованные координаты. P = [x y] -- вектор-строка исходных координат, P` = [x` y`] -- вектор-строка преобразованных координат, T = [Tx Ty] -- вектор-строка сдвига.

 

 

Масштабирование

Преобразование масштабирования относительно начала координат имеет вид:

x` = x ·Sx

y` = y ·Sy или

 

Sx 0

[x`, y`] = [x, y] ·

0 Sy

P` P

S

 или в матричной форме:

P` = P ·S,

где Sx, Sy -- коэффициенты масштабирования по осям, а

S - матрица масштабирования

  Поворот

 

 

Преобразование поворота относительно начала координат имеет вид:

 

x`= x·cos(φ) – y·sin(φ)

y`= x·sin(φ) + y·cos(φ)

 

или

cos(φ) sin(φ)

[x`, y`] = [x, y] ·

–sin(φ) cos(φ)

P` P

R

Где R – матрица поворота

φ – положительный угол поворота

или в матричной форме:

P` = P ·R,

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

cos·cos+sin·sin = 1

 

(-sin) ·(-sin)+cos·cos = 1,

а скалярное произведение векторов-строк есть

cos·(-sin) + sin·cos = 0.

Так как скалярное произведение векторов A ·B = A ·B ·cos, где A - длина вектора A, B - длина вектора B, а  - наименьший положительный угол между ними, то из равенства скалярного произведения двух векторов-строк длины 1 следует, что угол между ними равен 90^.

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

 

cos

-sin



·



cos

s in



=



1 0



,

-sin

cos

т.е. это единичный вектор вдоль оси X.

Аналогично, произведение второго столбца на матрицу даст вектор [ 0 1 ]. Это позволяет сформировать матрицу, если известны результаты преобразования.

Преобразование в однородную систему координат

 Как видно двумерные преобразования имеют различный вид. Сдвиг реализуется сложением, а масштабирование и поворот - умножением. Это различие затрудняет формирование суммарного преобразования и устраняется использованием двумерных однородных координат точки, имеющих вид:

[ X Y W ].

Здесь W - произвольный множитель не равный 0.

Двумерные декартовые координаты точки получаются из однородных делением на множитель W:

x = X / W, y = Y / W, W 0

Однородные координаты можно представить как промасштабированные с коэффициентом W значения двумерных координат, расположенные в плоскости с Z = W.

В силу произвольности значения W в однородных координатах не существует единственного представления точки, заданной в декартовых координатах.

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

Будем брать W=1.

 

Параллельный перенос:

 

 

1 0 0

[X`, Y`, 1]=[X, Y, 1] 0 1 0

Dx Dy 1

Перемножив, получим: [X + Dx, Y + Dy, 1].

 

 

Масштабирование:

 

P` = P·S; где

 

 

Поворот:

 

Рё = Р·R; где