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

Adaptação: João Paulo PereiraAntónio Costa

Autoria: Claudio EsperançaPaulo Roma Cavalcanti

Pontos e Vectores (2D)Pontos e Vectores (2D)

• Ponto: Denota posição no plano

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

),(

),(

vv

PP

yxv

yxP

==

r

01-03-2007 2

magnitude• Ambos são normalmente

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

x

yP

v

vv

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

• Soma de vectorest = v + u

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

• Subtracção de pontosv = Q – P

x

y

v

u

01-03-2007 3

v = Q – P• Soma de ponto com vector

Q = P + v

x

yv

x

y P

v

v

Q

TransformaçõesTransformações

• Transformação é uma função que faz corresponder pontos de um espaço Euclidiano a outros (ou possivelmente os mesmos) pontos do mesmo espaço

• Se uma transformação é linear, então� Se um conjunto de pontos pertence a uma recta, depois de transformados eles também pertencerão a uma recta

01-03-2007 4

uma recta� 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 faz corresponder a origem à 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

'

'

01-03-2007 5

• Uma transformação linear afim

++=++=

fdycxy

ebyaxx

'

'

Forma MatricialForma Matricial

• Mais conveniente para uso em computador. Sejam

=

=

=

=

f

eD

dc

baA

y

xP

y

xP

'

''

01-03-2007 6

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

fdcyy '

DPAP +×='

Transformação de VectoresTransformação de Vectores

• Um vector não está aplicado a um ponto no espaço• Uma transformação linear afim aplicada a um vector não inclui translação

• Demonstração: Seja V um vector e V’ a sua imagem sob a transformação linear afim. Então:

01-03-2007 7

sob a transformação linear afim. Então:

''' PQVPQV −=⇔−=

VA

PQA

DPADQA

PQV

×=−×=

+×−+×=−=

)(

)()(

'''

Coordenadas HomogéneasCoordenadas Homogéneas

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

• Coordenadas homogéneas permitem unificar o tratamento• Problema é levado para uma dimensão superior:

� Coordenada extra w = 0 para vectores e w = 1 para pontos� Termos independentes formam uma coluna extra na matriz de

transformação

01-03-2007 8

� 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 Coordenadas Homogéneas --InterpretaçãoInterpretação

y

Plano 1w=

Plano 0w=

01-03-2007 9

xw

Plano 1w=

Modelação de TransformaçõesModelação de Transformações

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

P P’y

++=++=

fydxcy

eybxax

PPP

PPP

..

..

'

'

01-03-2007 10

Q

Q’

R

R’

x

++=++=++=++=++=

fydxcy

eybxax

fydxcy

eybxax

fydxcy

RRR

RRR

QQQ

QQQ

PPP

..

..

..

..

..

'

'

'

'

'

Sistemas de coordenadasSistemas de coordenadas

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

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

01-03-2007 11

Um ponto P é dado por coordenadas xP e yP tais que

� Um vector V é dado por coordenadas xV e yV tais que

OYyXxP PP ++= ..

YyXxV VV .. +=

Mudança de Sistema de Mudança de Sistema de CoordenadasCoordenadas

• Se estabelecemos um outro sistema (ex.: Q/T/U), como calcular as novas coordenadas em função das antigas?

T

QUuTt PP +

01-03-2007 12X

Y

O

U

P

YyXx PP +

UuTt PP +

Mudança de Sistema de Mudança de Sistema de CoordenadasCoordenadas

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

OYyXxYyXxuYyXxt

QUuTtP PP

++++++=++=

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

..

01-03-2007 13

OYyyuytXxxuxt

OYyXxYyXxuYyXxt

QUPTPQUPTP

QQUUPTTP

++++++=++++++=

)...()...(

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

QUPTPP xxuxtx ++= ..

QUPTPP yyuyty ++= ..

Logo,

Mudança de Sistema de Mudança de Sistema de CoordenadasCoordenadas

• Matricialmente:

• Usando coordenadas homogéneas:

+

×

=

Q

Q

P

P

UT

UT

P

P

y

x

u

t

yy

xx

y

x

txxxx

01-03-2007 14

• Para resolver o problema inverso:

×

=

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

• Vectores e pontos em 3D

=z

y

x

V

V

V

Vr

=z

y

x

P

P

P

P

01-03-2007 15

• Transformação linear afim

0zV

1

z

=

1000

lihg

kfed

jcba

T

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

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

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

Submatriz de

Rotação

Vector de

Translação

01-03-2007 16

=

1000

lihg

kfed

jcba

T

Rotação Translação

TranslaçãoTranslação

=

=10

1000

100

010

001

3 tI

t

t

t

Tz

y

x

x

y

01-03-2007 17

tPtP

tP

tP

P

P

P

t

t

t

PTPzz

yy

xx

z

y

x

z

y

x

+=

+++

=

×

=×=

111000

100

010

001

'

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

x

z

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

• Podemos ver que ao vector (1,0,0)T corresponde (cos α, sen α, 0)T e que ao vector (0,1,0)T corresponde(- sen α, cos α, 0)T

ycos αy’

01-03-2007 18

α x

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’y

Sabemos que

)sin(

)cos(

θαθα

+=′+=′

rP

rP

y

x

Então

01-03-2007 19

θ

α

P

P’

x

rr

θαθαθαθα

cossinsincos

sinsincoscos

rrP

rrP

y

x

+=′−=′

θθθθ

cossin

sincos

yxy

yxx

PPP

PPP

+=′−=′

Então

Resultando que

Rotação em torno dos eixos Rotação em torno dos eixos coordenadoscoordenados

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

−

0100

00cossin

00sincos

θθθθ

01-03-2007 20

• Do mesmo modo, em torno dos eixos Y e X

−1000

0cos0sin

0010

0sin0cos

θθ

θθ

−1000

0cossin0

0sincos0

0001

θθθθ

1000

Rotações em geralRotações em geral

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

• Seja S a matriz

01-03-2007 21

• 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 restantes

yzyz

z´

01-03-2007 22

xx

• Se o vector unitário do eixo z é transformado 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

EscalamentoEscalamento

• Especificado por três factores (Sx, Sy , Sz) que multiplicam os vectores unitários x, y, z

• Escalamento não é uma transformação rígida• Escalamento uniforme (Sx = Sy = Sz) é uma operação ortogonal ou

homotética, isto é, preserva os ângulos• Para obter reflexão em torno do plano y=0, usar os factores de escala

(1, -1, 1)

01-03-2007 23

(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 Composição de transformações em 3Dem 3D

• Na nossa notação, usamos a 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

01-03-2007 24

1T 2T

12 TT ×

Geometria AfimGeometria Afim

• Composta dos elementos básicos� escalares� pontos - denotam posição� vectores - denotam deslocamento (direcção e magnitude)

01-03-2007 25

� vectores - denotam deslocamento (direcção e magnitude)

• Operações� escalar� vector = vector � vector + vector ou vector – vector = vector � ponto – ponto = vector� ponto + vector ou ponto – vector = ponto

Combinações AfimCombinações Afim

• Maneira especial de combinar pontos

• Para 2 pontos P e Q poderíamos ter uma combinação

1 onde

...

1

2211

=

+++

∑=

n

ii

nnPPP

α

ααα

01-03-2007 26

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

P

Q

R= P + α(Q – P)

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 nulos)

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

01-03-2007 27

pontos pertence à envolvente 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 transforma um par de vectores num escalar.

01-03-2007 28

transforma um par de vectores num 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 vector é definido como:

∑=

=⋅d

iiivuvu

1

rr

01-03-2007 29

• Comprimento de um vector é definido como:

• Vector unitário (normalizado):

vvvrrr ⋅=

v

vv r

r

=ˆ

Geometria EuclidianaGeometria Euclidiana

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

)ˆˆ(coscos),( 11 vuvu

vuvuângulo ⋅=

⋅= −−rr

rrrr

01-03-2007 30

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

121 uuuvvv

vuu

rrrrrr

rrr −=

⋅⋅=

v

u

u1

u2

Produto Vectorial (3D)Produto Vectorial (3D)

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

zyxzxxz

yzzy

uuu

kji

vuvu

vuvu

vu

rrr

rr =

−−

=× u

vu×v

.

01-03-2007 31

zyxxyyx vvvvuvu

−

• 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.

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

01-03-2007 32

1 2 3

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

01-03-2007 33

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 ...

Determinação da OrientaçãoDeterminação da Orientação

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

01-03-2007 34

=

321

3213212

111

sign),,(Or

yyy

xxxPPP

=

4321

4321

432143213

1111

sign),,,(Or

zzzz

yyyy

xxxxPPPP