Introdução à Computação GráficaIntrodução à Computação GráficaGeometriaGeometria

Claudio EsperançaPaulo Roma Cavalcanti

Pontos e Vetores (2D)Pontos e Vetores (2D)

• Ponto: Denota posição no plano

• Vetor: Denota deslocamento, isto é, inclui a noção de direção e magnitude

• Ambos são normalmente expressos por pares de coordenadas (em 2D) mas não são a “mesma coisa”

x

yP

v

),(

),(

vv

PP

yxv

yxP

Operações com Pontos e Vetores (2D)Operações com Pontos e Vetores (2D)

• Soma de vetorest = v + u

• Multiplicação de vetor por escalaru = 2 v

• Subtração de pontosv = Q – P

• Soma de ponto com vetorQ = P + v

x

y

v

u

t = v

+ u

x

yv

x

y P

v

v

u = 2 v

Q

TransformaçõesTransformações

• Transformação é uma função que mapeia pontos de um espaço Euclidiano em outros (ou possivelmente os mesmos) pontos do mesmo espaço.

• Se uma transformação é linear, então Se um conjunto de pontos está contido em uma

reta, depois de transformados eles também estarão contidos sobre uma reta.

Se um ponto P guarda uma relação de distância com dois outros pontos Q e R, então essa relação de distância é mantida pela transformação.

• Transformação mapeia origem na origem? Sim: Transformação Linear Não: Transformação Linear Afim: Translações são

permitidas

Transformações Lineares em 2DTransformações Lineares em 2D

• Uma transformação linear

• Uma transformação linear afim

dycxy

byaxx

'

'

fdycxy

ebyaxx

'

'

Forma MatricialForma Matricial

• Mais conveniente para uso em um computador. Sejam

• Então uma transformação linear afim pode ser escrita T (P ) = P’ onde

f

eD

dc

baA

y

xP

y

xP

'

''

DPAP '

Transformando VetoresTransformando Vetores

• Um vetor não está atrelado a um ponto no espaço

• Uma transformação linear afim aplicada a um vetor não inclui translação

• Prova: Seja V um vetor e V’ sua imagem sob a transformação linear afim, então:

''' PQVPQV

VA

PQA

DPADQA

PQV

)(

)()(

'''

Coordenadas HomogêneasCoordenadas Homogêneas

• A transformação de vetores é operacionalmente diferente da de pontos

• Coordenadas homogêneas permitem unificar o tratamento

• Problema é levado para uma dimensão superior: Coordenada extra w= 0 para vetores e =1 p/

pontos Termos independentes formam uma coluna extra

na matriz de transformação

11001

'

'

y

x

fdc

eba

y

x

01000

'

'

y

x

fdc

eba

y

x

Coordenadas Homogêneas - InterpretaçãoCoordenadas Homogêneas - Interpretação

x

y

w

Plano 1w =

Plano 0w =

Modelando TransformaçõesModelando Transformações

• Uma t.l.a. em 2D pode ser definida se dispusermos da imagem de 3 pontos do domínio

P P ’

Q

Q ’

R

R ’

x

y

fydxcy

eybxax

fydxcy

eybxax

fydxcy

eybxax

RRR

RRR

QQQ

QQQ

PPP

PPP

..

..

..

..

..

..

'

'

'

'

'

'

Sistemas de coordenadasSistemas de coordenadas

• Um sistema de coordenadas para Rn é definido por um ponto (origem) e n vetores

• Ex. Seja um sistema de coordenadas para R2 definido pelo ponto O e os vetores X e Y. Então, Um ponto P é dado por coordenadas xP e yP tais

que

Um vetor V é dado por coordenadas xV e yV tais que

OYyXxP PP ..

YyXxV VV ..

Mudança de Sistema de CoordenadasMudança de Sistema de Coordenadas

• Se estabelecemos um outro sistema (ex.: Q/T/U), como computar as novas coordenadas dadas as antigas?

X

Y

O

U

T

Q

P

YyXx PP

UuTt PP

Mudança de Sistema de CoordenadasMudança de Sistema de Coordenadas

• Como computar as coordenadas de um ponto P = (xP, yP) em O/X/Y dadas as coordenadas de P em Q/T/U, isto é, (tP, uP) ?

OYyyuytXxxuxt

OYyXxYyXxuYyXxt

QUuTtP

QUPTPQUPTP

QQUUPTTP

PP

)...()...(

)..()...()...(

..

QUPTPP xxuxtx ..

QUPTPP yyuyty ..

Logo,

Mudança de Sistema de CoordenadasMudança de Sistema de Coordenadas

• Matricialmente:

• Usando coordenadas homogêneas:

• Para resolver o problema inverso:

Q

Q

P

P

UT

UT

P

P

y

x

u

t

yy

xx

y

x

11001P

P

QUT

QUT

P

Put

yyy

xxxyx

11001

1

P

P

QUT

QUT

P

Pyx

yyy

xxxut

Transformações em 3DTransformações em 3D

• Vetores e pontos em 3D

• Transformação linear afim

0z

y

x

V

V

V

V

1z

y

x

P

P

P

P

1000

lihg

kfed

jcba

T

Transformações RígidasTransformações Rígidas

• Não modificam a forma (dimensões /ângulos) do objeto

• São compostas de uma rotação e uma translação

1000

lihg

kfed

jcba

T

Submatriz de

Rotação

Vetor de

Translação

TranslaçãoTranslação

10

1000

100

010

001

3 tI

t

t

t

Tz

y

x

tPtP

tP

tP

P

P

P

t

t

t

PTPzz

yy

xx

z

y

x

z

y

x

111000

100

010

001

'

• Observe que translações são comutativas:P + t + v = P + v + t

x

y

z

Rotação em torno do eixo Rotação em torno do eixo ZZ

• Podemos ver que o vetor (1,0,0)T é mapeado em (cos , sen , 0)T e que o vetor (0,1,0)T é mapeado em (- sen , cos , 0)T

x

y

cos

cos

sen

- sen

x’

y’

x

y

z

Rotação em torno do eixo Rotação em torno do eixo ZZ

• Outra maneira de ver:

sin

cos

rP

rP

y

x

P

P’

x

y

rr

• Sabemos que

)sin(

)cos(

rP

rP

y

x

• Então

cossinsincos

sinsincoscos

rrP

rrP

y

x

cossin

sincos

yxy

yxx

PPP

PPP

• Ou, finalmente,

Rotação em torno dos eixos coordenadosRotação em torno dos eixos coordenados

• Similarmente, em torno dos eixos X e Y

1000

0100

00cossin

00sincos

1000

0cossin0

0sincos0

0001

1000

0cos0sin

0010

0sin0cos

• Rotação em torno de Z é dada pela matriz

Rotações em geralRotações em geral

• Qualquer rotação pode ser definida por um eixo de rotação dado pelo vetor unitário u = (x, y, z)T e um ângulo de rotação

• Seja S a matriz

• Então a submatriz de Rotação M é dada por

0

0

0

S

xy

xz

yz

Ssin()uuI)((cosuuM TT

Inclinação (“Inclinação (“shearshear”) ”)

• É uma transformação de deformação onde um eixo é “entortado” em relação aos demais

x

yz

x

yzz´

• Se o vetor unitário do eixo z é levado em [Shx Shy 1 0]T, então a matriz de transformação é dada por

1000

0100

010

001

y

x

inclinação

Sh

Sh

T

EscalaEscala

• Especificada por três fatores (Sx, Sy , Sz) que multiplicam os vetores unitários x, y, z

• Escala não é uma transformação rígida,• Escala uniforme (Sx = Sy = Sz) entretanto, é uma operação

ortogonal ou homotética, isto é, preserva os ângulos• Para obter reflexão em torno do plano z=0, usar fatores de

escala (1, 1, -1)

1000

000

000

000

z

y

x

escala S

S

S

T

x

y

z

x

y

z

Composição de transformações em 3DComposição de transformações em 3D

• Em nossa notação, usamos pré-multiplicação: P’ = T x P

• Para compor 2 transformações temos: Se P’ = T1 x P e P’’ = T2 x P’ , então, P’’ = T2 x T1

x P

1T 2T

12 TT

Geometria AfimGeometria Afim

• Composta dos elementos básicos escalares pontos - denotam posição vetores - denotam deslocamento

(direção e magnitude)• Operações

escalar · vetor = vetor vetor + vetor ou vetor – vetor = vetor ponto – ponto = vetor ponto + vetor ou ponto – vetor = ponto

Combinações AfimCombinações Afim

• Maneira especial de combinar pontos

• Para 2 pontos P e Q poderíamos ter uma combinação afim R = (1 – )P +Q = P +(Q – P)

1 onde

...

1

2211

n

ii

nnPPP

P

Q

R= P+(P – Q)

P

Q0 < < 1

< 0

> 1

Combinações ConvexasCombinações Convexas

• Combinações afim onde se garante que todos os coeficientes i são positivos (ou zero)

• Usa-se esse nome porque qualquer ponto que é uma combinação convexa de n outros pontos pertence à envoltória convexa desses pontos

P1

P2

P3

P4 P5

Q

Geometria Euclidiana Geometria Euclidiana

• Extensão da geometria afim pela adição de um operador chamado produto interno

• Produto interno é um operador que mapeia um par de vetores em um escalar. Tem as seguintes propriedades: Positividade : (u,u) 0 e (u,u) = 0 sse u=0 Simetria: (u,v) = (v,u) Bilinearidade: (u,v+w)= (u,v)+ (u,w) e (u,v)= (u,v)

Geometria EuclidianaGeometria Euclidiana

• Normalmente usamos o produto escalar como operador de produto interno:

• Comprimento de um vetor é definido como:

• Vetor unitário (normalizado):

d

iiivuvu

1

vvv

v

vv

ˆ

Geometria EuclidianaGeometria Euclidiana

• Distância entre dois pontos P e Q =|P – Q |• O ângulo entre dois vetores pode ser

determinado por

• Projeção ortogonal: dados dois vetores u e v, deseja-se decompor u na soma de dois vetores u1 e u2 tais que u1 é paralelo a v e u2 é perpendicular a v

)ˆˆ(coscos),( 11 vuvu

vuvuângulo

121 uuuvvv

vuu

v

u

u1

u2

Produto Vetorial (3D)Produto Vetorial (3D)

• Permite achar um vetor perpendicular a outros dois dados• Útil na construção de sistemas de coordenadas

zyx

zyx

xyyx

zxxz

yzzy

vvv

uuu

kji

vuvu

vuvu

vuvu

vu

• Propriedades (assume-se u, v linearmente independentes): Antisimetria: u × v = – v × u Bilinearidade: u × (v) = (u × v) e u × (v + w) = (u × v) + (u × w) u × v é perpendicular tanto a u quanto a v O comprimento de u × v é igual a área do paralelogramo definido por u e v, isto é, | u × v | = | u | | v | sin

u

vu×v

.

OrientaçãoOrientação

• Orientação de 2 pontos em 1D P1 < P2 , P1 = P2 ou P1 > P2

• Orientação de 3 pontos em 2D O percurso P1 , P2 , P3 é feito no sentido dos

ponteiros do relógio, no sentido contrário ou são colineares

P1

P3 P2

P3

P1 P2

P3

P2

P1

Or (P1, P2, P3) = +1 Or (P1, P2, P3) = -1 Or (P1, P2, P3) = 0

OrientaçãoOrientação

• Orientação de 4 pontos em 3D O percurso P1 , P2 , P3 , P4 define um

parafuso segundo a regra da mão direita, mão esquerda ou são coplanares

P1

P4 P2

Or (P1, P2, P3, P4) = +1

P3

• O conceito pode ser estendido a qualquer número de dimensões ...

Computando orientaçãoComputando orientação

• A orientação de n+1 pontos em um espaço n-dimensional é dado pelo sinal do determinante da matriz cujas colunas são as coordenadas homogêneas dos pontos com o 1 vindo primeiro

321

3213212

111

sign),,(Or

yyy

xxxPPP

4321

4321

432143213

1111

sign),,,(Or

zzzz

yyyy

xxxxPPPP