Apostila de Computao Grfica(com nfase em sntese de imagens)

Bruno de Oliveira SchneiderDepartamento de Cincia da Computao

Universidade Federal de Lavras

Este texto uma obra em desenvolvimento.A reproduo sem permisso do autor proibida.

Verso: Fevereiro de 2015

Sumrio

1 Introduo 81.1 A Natureza dos Dados Numa Imagem . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.1.1 Formatos de Arquivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.2 O Processo de Criao de Imagens . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3 O Papel da Luz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.4 Um modelo para a formao de imagens . . . . . . . . . . . . . . . . . . . . . . . 111.5 Um modelo fsico: Ray Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.6 Um modelo geomtrico: Cmera Estenopeica. . . . . . . . . . . . . . . . . . . . . . 141.7 Reviso Matemtica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.7.1 Crculo trigonomtrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.7.2 Operaes com matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.7.3 Regra da mo direita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.7.4 Operaes com pontos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.7.4.1 Subtrao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.7.5 Operaes com vetores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.7.5.1 Soma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.7.5.2 Produto Escalar . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.7.5.3 Produto Vetorial . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.7.6 Equao da reta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.7.7 Clculo de uma posio na reta . . . . . . . . . . . . . . . . . . . . . . . . 201.7.8 Equao do plano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2 Representao de Slidos 222.1 Enumerao de ocupao espacial . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.2 Geometria slida construtiva (Constructive Solid Geometry - CSG) . . . . . . . . . . 222.3 Modelagem baseada em pontos (Point based modeling) . . . . . . . . . . . . . . . . 242.4 Modelagem tradicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3 Fundamentos Matemticos 283.1 Transformaes Geomtricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.1.1 Definio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.1.1.1 Translao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2

3.1.1.2 Rotao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.1.1.3 Escala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.1.1.4 Cisalhamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.1.2 Representao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.1.2.1 Matriz de Translao . . . . . . . . . . . . . . . . . . . . . . . . 32

3.1.2.2 Matriz de Rotao . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.1.2.3 Matriz de Escala . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.1.2.4 Matriz de Cisalhamento . . . . . . . . . . . . . . . . . . . . . . . 34

3.1.3 Aplicao de transformaes a objetos . . . . . . . . . . . . . . . . . . . . . 34

3.1.4 Combinao de transformaes . . . . . . . . . . . . . . . . . . . . . . . . 34

3.1.4.1 Rotao (2D) em torno de um ponto arbitrrio . . . . . . . . . . . 35

3.1.4.2 Escala fixando um ponto arbitrrio . . . . . . . . . . . . . . . . . 35

3.1.4.3 Transformao de instncia . . . . . . . . . . . . . . . . . . . . . 35

3.1.4.4 Rotao (3D) em torno de um eixo arbitrrio . . . . . . . . . . . . 35

3.1.5 Grafo de Cena . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.2 Mudanas Entre Sistemas de Coordenadas . . . . . . . . . . . . . . . . . . . . . . 35

3.3 Projeo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.3.1 Projeo Paralela . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.3.2 Projeo Perspectiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4 Mtodos de Recorte 424.1 Algoritmos de Recorte para Segmentos de Reta . . . . . . . . . . . . . . . . . . . . 42

4.1.1 Algoritmo de Cohen-Sutherland . . . . . . . . . . . . . . . . . . . . . . . . 42

4.1.2 Recorte Paramtrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.2 Recorte de Crculos e Elipses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.3 Recorte de Polgonos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.3.1 Algoritmo de Sutherland-Hodgman . . . . . . . . . . . . . . . . . . . . . . 48

4.4 Recorte em 3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5 Converso de Primitivas Grficas em Imagens Matriciais 515.1 Segmentos de Reta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.2 Crculos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.3 Elipses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.4 Tringulos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6 Determinao de Superfcies Visveis 606.1 Remoo de faces invisveis num slido (back-face culling) . . . . . . . . . . . . . . 60

6.2 Algoritmo do z-buffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3

7 Iluminao 637.1 Intensidade de Luz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637.2 Cor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637.3 Modelos de Iluminao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

7.3.1 Luz Ambiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657.3.2 Reflexo Difusa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667.3.3 Reflexo Especular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667.3.4 Atenuao Atmosfrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677.3.5 Criando um Modelo Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

7.4 Aplicao de Modelos de Iluminao a Malhas Poligonais . . . . . . . . . . . . . . 697.4.1 Iluminao Constante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 697.4.2 Mtodo de Gouraud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707.4.3 Mtodo de Phong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

8 Antialiasing (Tcnicas anti-serrilhado) 718.1 Amostragem Simples (Unweighted) . . . . . . . . . . . . . . . . . . . . . . . . . . 728.2 Amostragem Ponderada (Weighted) . . . . . . . . . . . . . . . . . . . . . . . . . . 73

9 Mapeamento de Texturas 759.1 Mapeamento Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 769.2 Mapeamento No-Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

10 Representao de Slidos Revisitada 79

4

Lista de Figuras

1.1 A Computao Grfica dividida em quatro sub-reas . . . . . . . . . . . . . . . . . 91.2 Comparao entre imagem vetorial e imagem matricial . . . . . . . . . . . . . . . . 91.3 Algumas situaes possveis de caminhos de luz num ambiente . . . . . . . . . . . . 121.4 Esquema de uma cmera estenopeica . . . . . . . . . . . . . . . . . . . . . . . . . . 121.5 Projees perspectivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.6 Projeo dos vrtices de um cubo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.7 Um cubo projetado com determinao das faces visveis (a) e o mesmo cubo aps a

determinao da cor de cada pixel (b) . . . . . . . . . . . . . . . . . . . . . . . . . 151.8 (a) Projeo dos pontos que descrevem o objeto; (b) determinao de superfcies es-

condidas e (c) aplicao de texturas e modelo de iluminao . . . . . . . . . . . . . 151.9 Viso geral do processo de sntese de imagens . . . . . . . . . . . . . . . . . . . . . 161.10 Crculo trigonomtrico. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.11 Multiplicao de matrizes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.12 A regra da mo direita: orientao de vetores de uma base (a) e sentido positivo de

rotao (b). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.13 A relao entre produto escalar e ngulo. . . . . . . . . . . . . . . . . . . . . . . . . 191.14 Mnemnico da frmula do produto vetorial. . . . . . . . . . . . . . . . . . . . . . . 191.15 Clculo de uma posio na reta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.1 (a) Elementos discretos segundo diviso regular (b) Conjunto de voxels representandoum carro. Imagem retirada de http://www.bilderzucht.de/blog/3d-pixel-voxel/. . . . . 23

2.2 Exemplo de representao de um slido por meio de operaes aplicadas a slidosprimitos. Imagem extrada de http://en.wikipedia.org/wiki/File:Csg_tree.png . . . . . 23

2.3 Imagem formada a partir de pontos da superfcie de um objeto. A quantidade depontos pequena e o espao entre pontos grande para destacar a natureza discretada imagem. Extrado de http://graphics.ethz.ch/publications/tutorials/eg2002/. . . . . 24

2.4 Quatros aproximaes diferentes para a superfcie de um objeto. Extrado de http://polygon-reducer.pc-guru.cz/reducing-level-of-detail. . . . . . . . . . . . . . . . . . . . . . . 25

2.5 As 6 faces e 8 vrtices de um cubo. . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.1 Exemplo de translao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.2 Exemplo de rotao 2D (a) e 3D (b) . . . . . . . . . . . . . . . . . . . . . . . . . . 303.3 Transformao de escala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.4 cisalhamento em x, associado a um ngulo . . . . . . . . . . . . . . . . . . . . . . . 313.5 Efeito da transformao de cisalhamento 2D . . . . . . . . . . . . . . . . . . . . . . 31

5

3.6 Efeito da transformao de cisalhamento 3D . . . . . . . . . . . . . . . . . . . . . . 313.7 Rotao no plano, em torno da origem . . . . . . . . . . . . . . . . . . . . . . . . . 333.8 Caso de uso da transformao de instncia. . . . . . . . . . . . . . . . . . . . . . . 363.9 Uma mudana de sistema de coordenadas representada por uma transformao geo-

mtrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.10 Projeo perpsectiva e projeo paralela . . . . . . . . . . . . . . . . . . . . . . . . 383.11 Projeo Paralela Especial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.12 Transformao de uma projeo paralela genrica numa projeo paralela especial . 393.13 Projeo Perspectiva Especial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.14 Transformao de uma projeo perspectiva genrica numa projeo perspectiva es-

pecial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.1 Exemplo de recorte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.2 Cdigos das regies de recorte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.3 Procedimento de recorte de acordo com o algoritmo Cohen-Sutherland. . . . . . . . 444.4 Determinao da interseo de um segmento com um lado da rea de recorte. . . . . 454.5 Exemplos de recorte paramtrico. . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.6 (a) Polgono original. (b) Recorte do lado superior. (c) Recorte do lado direito. (d)

Recorte do lado inferior. (e) Recorte do lado esquerdo. . . . . . . . . . . . . . . . . 484.7 Classificao dos lados de um polgono em relao rea de recorte. . . . . . . . . . 494.8 Pontos que resultam do recorte de um lado do polgono contra um lado da rea de

recorte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.9 O recorte de polgonos cncavos pode criar o surgimento de lados indesejveis. . . . 49

5.1 Escolha de pixels para desenhar uma reta. . . . . . . . . . . . . . . . . . . . . . . . 515.2 Pontos envolvidos na escolha do prximo pixel, pelo algoritmo do ponto mdio para

segmentos de reta. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525.3 Classificao proporcionada pela equao implcita da reta. . . . . . . . . . . . . . . 535.4 Simetria de pontos num crculo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.5 Pontos envolvidos na escolha do prximo pixel, pelo algoritmo do ponto mdio para

crculos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.6 Funo para determinar a posio de um ponto (x,y) em relao a um crculo de centro

na origem e raio R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.7 Pontos envolvidos na escolha do prximo pixel, pelo algoritmo do ponto mdio para

elipses em suas duas regies distintas. . . . . . . . . . . . . . . . . . . . . . . . . . 575.8 Retngulo rasterizado em intervalo aberto direita e acima. . . . . . . . . . . . . . . 585.9 Pixel compartilhado entre vrtices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.10 Classificao de arestas num tringulo. . . . . . . . . . . . . . . . . . . . . . . . . . 58

6.1 A projeo das seis faces de um cubo (a), que poderia ser interpretada como a geo-metria em (b) ou em (c). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

7.1 (a) modelo aditivo de composio de cores e (b) modelo subtrativo. . . . . . . . . . . 657.2 Um feixe de luz atinge uma superfcie maior quando ela inclinada. . . . . . . . . . 66

6

7.3 Reflexo especular numa superfcie. . . . . . . . . . . . . . . . . . . . . . . . . . . 677.4 A variao abrupta de intensidade destacada pelo crebro. . . . . . . . . . . . . . . 697.5 Comparao entre o mtodo de Gouraud e o de Phong quando a rea de reflexo

especular est dentro do polgono. . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

8.1 Aparecimento de padres moir. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718.2 Antialiasing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728.3 Uma reta com um pixel de espessura entre dois pontos cobre diferentes reas dos

pixels por onde passa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728.4 Segmento de reta desenhado usando amostragem simples. . . . . . . . . . . . . . . . 738.5 Pixels com a mesma rea coberta, com o segmento passando em posies diferentes. 738.6 Pixels com a mesma rea coberta, influenciados de maneiras difrentes . . . . . . . . 73

9.1 Comparao entre mapeamentos de textura (padres naturais). . . . . . . . . . . . . 769.2 Comparao entre mapeamentos de textura (padro xadrez). . . . . . . . . . . . . . 779.3 Variao de x e y na projeo perspectiva. . . . . . . . . . . . . . . . . . . . . . . . 77

10.1 Textura de um dado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

7

Captulo 1

Introduo

A Computao Grfica nasceu da necessidade de se apresentar dados processados por um computadorde uma maneira mais facilmente assimilvel por uma pessoa do que uma simples lista de nmeros.Dispositivos conhecidos como plotters j desenhavam grficos em papel numa poca em que com-putadores recebiam dados em papel perfurado e exibiam resultados em papel impresso. Mais tardesurgiu a ideia de se conectar um tubo de raios catdicos (CRT - o tubo de imagem das televises) aum computador, o que abriu grandes possibilidades neste campo, permitindo a apresentao rpida deinformaes que representam os mais variados modelos, dos mais variados campos de conhecimento,associados a estruturas fsicas, fenmenos naturais ou mesmo entidades abstratas.Podemos definir a Computao Grfica como a cincia que estuda os mtodos que permitem a vi-sualizao de informaes armazenadas na memria do computador [4]. Como existe uma enormevariedade de aplicaes nesta rea, pode ser interessante divid-la em sub-reas menores, de acordocom a natureza das informaes usadas no processo de computao, levando em considerao se essasinformaes so dados de entrada ou de sada (resultados).Assim, ainda conforme [4], podemos dividir a computao grfica em 4 sub-reas:

Modelagem Geomtrica: Trata do problema de descrever e estruturar dados geomtricos nocomputador

Sntese de Imagens: Processamento de dados gerados pelo sistema de modelagem, para produ-zir uma imagem que pode ser vista atravs de algum dispositivo de sada grfica.

Processamento de Imagens: Tem por objetivo identificar e realar algum tipo de informaocontida numa imagem, produzindo uma nova imagem como resultado.

Anlise de Imagens: Tem por objetivo extrair algum tipo de informao (topolgica, fsica, etc.)de uma imagem, produzindo dados que sero armazenados na memria para processamentoposterior.

Neste texto, estaremos preocupados principalmente com a sntese de imagens. Vamos supor que osdados necessrios para criar a imagem j existem ou podem ser criados de alguma maneira. Pre-cisamos agora converter estes dados de alguma maneira num dispositivo de apresentao, como ovdeo, por exemplo. A estratgia preferida para alcanar este objetivo imitar a formao de imagensreais. Vamos procurar entender o processo da criao de uma fotografia numa cmera para imple-mentar uma simplificao deste processo no computador. O processo de criao de uma foto muitoparecido com o processo de sensibilizao da retina de um olho, de maneira que ele ser chamadosimplesmente de processo de criao de imagens.

8

IMAGENS DADOSModelagemGeomtrica

Processamentode Imagens

Sntese deImagens

Anlise deImagens

Figura 1.1: A Computao Grfica dividida em quatro sub-reas

1.1 A Natureza dos Dados Numa Imagem

Podemos classificar a representao de uma imagem de duas maneiras, dependendo da natureza dosdados utilizados na representao:

Imagem vetorial: uma imagem cuja representao de natureza geomtrica, ou seja, ela definida em funo de elementos geomtricos e parmetros (linhas, circunferncias, pontos,preenchimentos, etc.)

Imagem matricial: uma imagem cuja representao de natureza discreta, ou seja, a imagem formada de elementos independentes, dispostos na forma de uma matriz, cada um contendouma unidade de informao da imagem.

Apesar de se dizer imagem vetorial ou imagem matricial, o que se est classificando no aimagem em si, mas os dados usados para represent-la.

(a) Imagem Vetorial (b) Imagem Matricial

Figura 1.2: Comparao entre imagem vetorial e imagem matricial

Na Figura 1.2, pode-se observar uma poro da imagem matricial ampliada onde percebe-se clara-mente os elementos discretos que formam a imagem (chamados pixels1). O modelo matricial de

1Apesar de no haver uma fonte de referncia formal, usualmente aceito que a palavra pixel deriva de pictureelement (elemento de imagem).

9

representao de imagens pode representar qualquer imagem, o que explica o fato dos dispositivosmatriciais de apresentao serem hoje muito mais comuns do que os dispositivos vetoriais. Imagensvetoriais, no entanto costumam ser pequenas (em relao quantidade de bytes) e podem ter suascaractersticas (dimenses, cores, espessura de linhas, etc.) facilmente alteradas. A converso de umaimagem vetorial para uma matricial pode ser vista como uma operao simples, entretanto, a con-verso inversa um processo complexo que dificilmente alcana os objetivos que se espera de umaconverso dessa natureza.Por necessitarem de menos espao em memria os dispositivos de apresentao vetoriais eram os maiscomuns antigamente. Por possibilitarem a representao de mais informao do que a imagem pro-priamente dita, as imagens vetoriais no sero deixadas de lado na Computao Grfica. De maneirageral, a representao matricial mais adequada para imagens naturais (fotos, por exemplo), paraimagens artificiais (logotipos, grficos comparativos, esquemas explicativos, etc.) a representaovetorial costuma ser mais indicada.

1.1.1 Formatos de Arquivo

Existems formatos de arquivo para armazenar imagens matriciais, para vetoriais e para ambos. Osformatos que podem armazenados os tipos representaes de imagens so frequentemente chamadosde containers e em geral, podem tambm armazenar dados de outras naturezas, ou seja, dados queno representam imagens.Alguns formatos de arquivo importantes so:

JPEG - representao matricial usando compactao com perdas;

PNG - representao matricial usando compactao sem perdas;

SVG - representao vetorial;2

PDF - container para imagens matriciais, vetoriais e outros tipos de dados.

1.2 O Processo de Criao de Imagens

Os dois elementos fundamentais no processo de criao de imagens so a cmera e o objeto doqual desejamos criar uma imagem. O objeto em questo no precisa necessariamente ser uma nicaentidade, entretanto, estaremos usando sempre o singular, j que a existncia de vrios objetos noprocesso de criao de imagens no afetar o processo descrito.A cmera afeta a imagem criada em vrios aspectos. Podemos citar, por exemplo, que a lente usadanum mquina fotogrfica influencia o tamanho da imagem criada, ou em outras palavras, a quantidadede informaes que so convertidas em imagem. o que chamamos de zoom da mquina. Dentre osaspectos da cmera, aquele mais facilmente identificvel a posio da cmera em relao ao objeto.A foto de prdio, por exemplo, certamente ser diferente, quando for feita de frente para o prdio oude dentro dele.De maneira geral, podemos dizer que os fatores principais para definir uma imagem so a posioda cmera e a descrio fsica do objeto. verdade que a luz presente no momento da criao daimagem tambm um fator fundamental para se definir qual ser a imagem formada. Sem luz, no

2Por ser um formato extensvel, vrios programas permitem a descrio de bitmaps dentro de um SVG, tornando oformato efetivamente um container.

10

seria possvel criar uma imagem mesmo com uma cmera e um objeto, uma vez que o objeto seriatodo preto e impossvel de ser notado.

Outro fator importante a ser observado uma foto de um objeto sempre 2D, mesmo que o objetorepresentado seja 3D. Quando chegar a hora de modelar matematicamente o processo de criao deimagens, vamos procurar entender o que causa essa eliminao de uma das dimenses fsicas. Porhora, basta lembrar que uma transformao matemtica que pega valores num conjunto de dimenson e os associa a valores num conjunto de dimenso menor que n chamada de projeo.

1.3 O Papel da Luz

Uma alternativa possvel para modelar o processo de criao de imagens tentar imitar o processode interao entre luz, objeto e cmera. Sabemos que um objeto torna-se visvel numa foto porqueexiste alguma fonte de luz que emite raios de luz. Estes raios por sua vez partem da fonte de luzdeslocando-se em linha reta, eventualmente atingindo o objeto em questo. Aps atingir o objeto,este raio sofre algum tipo de interao com o objeto e parte de sua energia deixa o objeto, na formade um novo raio de luz que eventualmente ir atingir e interagir com a cmera, formando a imagem.

Uma fonte de luz pode ser representada por um ponto no espao, de onde saem raios de luz em todasas direes. Destes raios, uma pequena poro acaba sensibilizando a cmera para formar a imagem.Existem vrias alternativas para um caminho de um raio de luz que deixa a fonte de luz e chega nacmera. Vamos analisar algumas:

Uma forma de se implementar este modelo de criao de imagens seria gerar raios de luz que partemda fonte de luz e seguem numa direo qualquer at atingir a cmera. Este mtodo, entretanto, invivel, pois a fonte de luz emite raios em todas as direes e, alm disso, um raio de luz segueseu caminho indefinidamente at que sua energia acabe, o que pode levar uma eternidade. Mesmoque estes dois problemas possam ser simplificados de maneira que possam ser implementados nocomputador ainda existe o problema de que somente um pequena parcela dos raios de luz que deixama fonte, chegam a interagir com a cmera, o que significaria um enorme desperdcio de processamento.

Precisamos usar algumas simplificaes matemticas e outros artifcios diversos para poder imple-mentar um processo de gerao de imagens, mas para isso, vamos analisar o processo de formao deimagens com mais detalhes.

1.4 Um modelo para a formao de imagens

possvel construir uma mquina fotogrfica utilizando uma caixa de sapatos (ou lata com tampa) epapel fotogrfico. Para tal necessrio fazer um pequeno furo com um prego numa das extremidadesda caixa e colocar o papel fotogrfico do outro lado. O furo deve ficar tampado (com fita adesiva,por exemplo) at o momento em que se deseja tirar a fotografia. Neste momento o furo deve serdestampado, mantendo-se a cmera parada por alguns instantes, e depois o furo deve ser novamentetampado. Durante o tempo que o furo fica destampado, a luz do ambiente pode entrar na caixa,sensibilizando o papel fotogrfico que pode ser revelado mais tarde.

Este equipamento simples ajuda a entender e modelar o processo de criao de imagens. Veja a figura1.4.

Para construir um modelo matemtico desta cmera, vamos supor que o furo da caixa to pequenoque, a partir de um ponto na posio (x, y, z), s pode passar um nico raio de luz, pelo furo, de tal

11

A

B

C

D

E

F

fonte de luz

Figura 1.3: Algumas situaes possveis de caminhos de luz num ambienteA) raio vai direto da fonte de luz cmera; B) o raio de luz absorvido pelo objeto; C) o raio de luz refletido na esfera, depois no cilindro, indo depois para a cmera; D) parte da energia do raio de luz refletida e parte sofre refrao, atravessando o paraleleppedo; E) o raiz de luz atinge uma superfciee sua energia dividida em infinitos novos raios de luz; F)o raiz de luz refletido mas no contribuipara a formao da imagem.

x

y

z

papel fotogrfico

( , , )x y z

( , , )x y zp p p

d

Figura 1.4: Esquema de uma cmera estenopeica

12

forma que este raio atinge o papel fotogrfico no ponto que est na posio (xp, yp, zp). A transfor-mao do valor (x, y, z) em (xp, yp, zp) nos fornecer as coordenadas (xp, yp), que so as coordenadasdo ponto na imagem (foto). Este processo chamado de projeo. Todos os pontos visveis do objetoso projetados no papel fotogrfico, passo pelo furo da caixa, assim, chamamos o papel fotogrficode plano de projeo e o furo de centro de projeo. Este modelo matemtico usualmente chamadode modelo da cmera sinttica.

Matematicamente, no existem grandes diferenas entre uma projeo onde o plano de projeo estentre o objeto e o centro de projeo e uma projeo onde o centro de projeo est entre o plano deprojeo e o objeto.

(a) (b)

Figura 1.5: Projees perspectivasEm (a) O centro de projeo encontra-se depois do plano de projeo e em (b) o centro de projeoencontra-se antes do plano de projeo.

A projeo perspectiva mostrada na Figura 1.5 (b), mais fiel ao que acontece fisicamente numamquina fotogrfica ou em nossos olhos, entretanto a imagem formada invertida (de cima parabaixo, da direita para a esquerda). A projeo mostrada em (a) alm de formar uma imagem coma mesma orientao do objeto, ela pode representar um modelo onde uma pessoa, sentada em suacadeira frente de uma tela de vdeo, observa um objeto atrs do vdeo.

Se considerarmos que a imagem formada uma matriz de pontos (pixels) discretos, podemos calculara cor de cada ponto da imagem, analisando qual raio poderia passar pelo furo da caixa at chegar nopapel fotogrfico.

1.5 Um modelo fsico: Ray Tracing

A ideia de seguir os raios de luz em seu caminho inverso, ou seja, do papel fotogrfico at um objetoe possivelmente do objeto at uma fonte de luz, elimina a necessidade de se seguir raios de luz queno contribuem para a formao da imagem. Outras dificuldades advindas da quantidade de clculosrelativos interao da luz com o objeto tambm podem ser reduzidas pela simplificao do modelofsico. Pode-se por exemplo, limitar o nmero de reflexes que o raio pode sofrer.

Alm de tornar vivel uma implementao que faz anlise dos raios de luz, essa ideia pode ser aplicadaindependentemente da posio do plano de projeo em relao ao centro de projeo (ver Figura1.5). Para cada pixel na imagem deve sair um raio que passa pelo centro de projeo. Deve-se entoverificar quais so os pontos de interseo do raio com a superfcie do objeto e ento fazer o clculoda cor do pixel.

Esta uma viso geral e simplificada do algoritmo conhecido como ray tracing ou ray casting. Acriao de imagens usando ray tracing conhecida pela realismo das imagens criadas, entretanto este um processo lento, que normalmente no usada para gerar grficos interativos.

13

1.6 Um modelo geomtrico: Cmera Estenopeica.

Uma maneira mais rpida de se criar uma imagem a partir da descrio matemtica de um objeto calcular a projeo deste objeto e identificar a cor de cada pixel a ser exibido. Esse mtodo consideravelmente mais rpido que o ray-tracing, visto anteriormente. Por outro lado, esse mtododificulta o clculo do efeito da luz interagindo com vrios objetos.Vamos supor que desejamos criar a imagem de um cubo. Este cubo definido matematicamente comoum conjunto de 6 lados (chamados de faces) cada lado do cubo definido em relao a 4 pontos 3D(com coordenadas x, y e z). Como algumas faces compartilham pontos, existe um total de 8 pontos 3Dna definio do cubo. Devemos ento calcular a projeo de cada um dos pontos, obtendo 8 pontos2D, que definem os mesmos 6 lados. Com a projeo alguns pontos podem se sobrepor, ou seja,podem ser projetados nas mesmas coordenadas (xp, yp) mas todos os pontos continuam existindo.

projeo

xx

yy

z(a) (b)

Figura 1.6: Projeo dos vrtices de um cubo

Mas no basta desenhar os pontos projetados para se ter a imagem do cubo, tambm no basta dese-nhar as linhas entre os pontos que formam as arestas de cada face. necessrio saber quais arestasno esto visveis (porque esto atrs de uma ou mais faces). Alm disso, precisamos tambm definira cor de cada pixel dentro de cada face. A eliminao das arestas que no esto visveis vai melhorara sensao de profundidade e a definio de cor de cada pixel do cubo vai aumentar a sensao derealismo, esse realismo ser to bom quanto o modelo matemtico utilizado no clculo. Modelosprecisos significam mais clculos, que por sua vez significam um gasto maior de tempo no processo.Veremos como gerar a imagem da Figura 1.7a na seo Tratamento de Linhas e Superfcies Escon-didas e depois veremos como gerar a imagem da Figura 1.7b na seo Iluminao.A determinao da cor de cada pixel um processo complexo e existem vrias abordagens pararesolver este problema. Se tentarmos simular a realidade com muita preciso, certamente seremosobrigados a gastar muito tempo com clculos. No adianta pensar que um dia os computadores seroto rpidos que este problema ser irrelevante. Este processo pode ser to complicado quanto sequeira. necessrio encontrar uma regio de equilbrio entre o realismo proporcionado pelo mtodode criao de imagens e tempo disponvel para clculos.A Computao Grfica Interativa e a Realidade Virtual enfrentam o desafio de tentar sintetizar ima-gens de boa qualidade em muito pouco tempo. Para se ter uma ideia melhor do problema do tempo,imagine que o ser humano consegue distinguir eventos e imagens distantes aproximadamente 100msno tempo. Isso quer dizer que um sistema interativo de computao (como um sistema de realidadevirtual) deve exibir o estado de uma operao qualquer no mnimo dez vezes por segundo, o que lhe

14

(a) (b)

Figura 1.7: Um cubo projetado com determinao das faces visveis (a) e o mesmo cubo aps adeterminao da cor de cada pixel (b)

deixa um tempo de 100ms para processar toda a informao colhida da interao do usurio e apre-sentar resultados. Agora olhe ao seu redor e imagine como seria possvel sintetizar a imagem quevoc v em menos de 100ms.

Uma boa tcnica para se acrescentar realismo a uma imagem sintetizada o uso de texturas. Umatextura uma imagem mapeada sobre um polgono plano (uma face) que por sua vez parte de umobjeto 3D. A funo da textura proporcionar realismo a um objeto que tenha modelo geomtricosimples. Apresentar a imagem de um objeto com textura um processo mais lento que apresentara imagem de um objeto sem textura. Entretanto, apresentar a imagem de um objeto com textura mais rpido que apresentar a imagem de um objeto com modelo geomtrico complexo, que dispensea textura.

(a) (b) (c)

Figura 1.8: (a) Projeo dos pontos que descrevem o objeto; (b) determinao de superfcies escon-didas e (c) aplicao de texturas e modelo de iluminao

Alm de todo o processo j discutido, a criao de imagens em tempo interativo envolve ainda aeliminao de pores no visveis do objeto na tentativa de evitar o processamento de dados que noiro contribuir para a formao da imagem. Neste instante, por exemplo, voc no v aquilo que estatrs de voc. Um sistema que simula o processo de viso de algum deve ser capaz de eliminar oprocessamento dos objetos fora de alcance da viso. Essa eliminao chamada de recorte.

15

De maneira geral o processo de sntese de imagens em tempo interativo pode ser representado pelodiagrama da figura 1.9. Esse process conhecido como pipeline grfico tradicional.

VrticesDeterminaode superfcies

visveis

ProjeoTransformao

GeomtricaRecorte Pixels

Figura 1.9: Viso geral do processo de sntese de imagens

1.7 Reviso Matemtica

Os elementos dessa seo so parte do contedo programtico de disciplinas que so pr-requisitospara Computao Grfica ou so abordados no ensino mdio. Porm, a experincia mostra que necessrio que eles sejam revistos antes da apresentao dos tpicos posteriores.

1.7.1 Crculo trigonomtrico

importante lembrar as relaes entre ngulo, seno, cosseno, tangente, cotangente, graus, radianos,alm das posies dos quadrantes e octantes da trigonometria. A figura 1.10 ajuda nesta tarefa.

x

y

0

30

4560

90120

135

150

180

210

225240

270

116

74

0

533

2

43

54

76

56

34

23

6

4

3

2

330

315

300

cos

sen

tan

cot

Figura 1.10: Crculo trigonomtrico.

1.7.2 Operaes com matrizes

A multiplicao de matrizes feita em linhas e colunas correspondentes conforme mostrado na figura1.11. O nmero de colunas do primeiro operando deve ser igual ao nmero de linhas do segundooperando. Mais formalmente, a multiplicao de matrizes dada por:

16

(AB)i j =n

k=1

aikbk j = ai1b1 j + + ainbn j

A

B

A*B

Figura 1.11: Multiplicao de matrizes.

A multiplicao de matrizes associativa (ABC = (AB)C = A(BC)) mas no comutativa (AB , BA).Nem toda matriz inversvel. Toda matriz que inversvel quadrada. A multiplicao de matrizespode ser implementada conforme o algoritmo 1.1.

Algoritmo 1.1 Multiplicao de matrizesDadas duas matrizes compatveis, m1 e m2, o produto m3 = m1*m2 pode ser calculado assim:1. Para cada linha da matriz m1:1.1. Para cada coluna da matriz m2:1.1.1. soma01.1.2. Para cada ndice de coluna de m1 (i):1.1.2.1. somam1(linha, i) + m2(i, coluna)1.1.3. m3(linha, coluna)soma

1.7.3 Regra da mo direita

Para fazer operaes no espao, geralmente precisamos de alguma conveno que determine o que positivo e o que negativo. Uma referncia muito comum de orientao sentido horrio ou anti-horrio, porm essa referncia costuma causar confuso num espao 3D. Na lgebra Linear existe oconceito de bases3 com orientao positiva (bases positivas) e bases com orientao negativa (basesnegativas). Essas duas classes de bases podem ser distinguidas pela regra da mo direita.

A regra da mo direita recurso mnemnico para se determinar uma orientao positiva no espao.Ela usada em Fsica, lgebra, Computao Grfica e outras reas do conhecimento. Para determinaro sentido positivo no espao, use o dedo da mo direita espalmada, enquanto alinha os outros dedoscom os elementos verificados. Com ela fica fcil determinar a orientao dos vetores de uma basepositiva (figura 1.12 - a) e o sentido de rotao em relao a um eixo (figura 1.12 - b).

3Uma base um conjunto de vetores linearmente independentes que geram todos os vetores possveis de um espaovetorial.

17

z

x

y

+

(a) (b)

Figura 1.12: A regra da mo direita: orientao de vetores de uma base (a) e sentido positivo derotao (b).

1.7.4 Operaes com pontos

1.7.4.1 Subtrao

A subtrao de dois pontos (P1 - P2) pode ser definida com um segmento de reta orientado que vai dede P2 para P1, ou tambm como a direo (vetor) que leva a posio P2 para P1.

P1 P2 = (x1 x2, y1 y2, z1 z2)

1.7.5 Operaes com vetores

1.7.5.1 Soma

A soma de dois vetores pode ser entendida como o segmento de reta orientado que une a base doprimeiro vetor ponta do segundo vetor.

P1 + P2 = (x1 + x2, y1 + y2, z1 + z2)

1.7.5.2 Produto Escalar

Dados dois vetores u = (ux, uy, uz) e v = (vx, vy, vz), o produto escalar :

u v = uxvx + uyvy + uzvz

Ele tem a propriedade geomtrica de estar relacionado com o ngulo entre os dois vetores, conformemostra a figura 1.13. Para vetores normalizados, o produto escalar o cosseno do ngulo entre osvetores.

18

uv = u v cos

u

v

u

v

Figura 1.13: A relao entre produto escalar e ngulo.

1.7.5.3 Produto Vetorial

Dados dois vetores u = (ux, uy, uz) e v = (vx, vy, vz), produto vetorial :

u v = (uyvz uzvy, uzvx uxvz, uxvy uyvx)

Ele tem a propriedade geomtrica de que o resultado um vetor perpendicular tanto a u quanto av. Dados dois vetores u e v, existem dois vetores que so perpendiculares a eles: u v e (u v).Para saber qual dos dois resultado, pode-se usar a regra da mo direita, colocando o indicador nadireo do primeiro operando e o dedo mdio na direo do segundo, temos o resultado na direo dopolegar. O produto vetorial anticomutativo, ou seja u v = v u. A norma do produto vetorial proporcional norma de seus operandos.A frmula do produto vetorial 3D mais facilmente lembrada se associada ao determinante da matriz3x3 em que a primeira linha tem os vetores unitrios que compe um sistema ortogonal de coordena-das, a segunda tem as coordenadas do primeiro operando e a terceira tem as coordenadas do segundooperando, conforme visto na figura 1.14.

Figura 1.14: Mnemnico da frmula do produto vetorial.

1.7.6 Equao da reta

Uma reta um conjunto infinito de pontos ao longo de uma dimenso. Esse conjunto de pontos podeser descrito no plano (deixaremos o espao 3D para depois) de vrias formas. A forma mais lembrada

19

a equao explcita, em que a coordenada y dada em funo da coordenada x.

y = ax + b

Com frequncia, deseja-se encontrar a equao a partir de dois pontos (P1 e P2) da reta. Nesse caso,os parmetros so dados por:

a =y2 y1x2 x1

b = y1 ax1

A equao explcita no pode ser usada para representar retas verticais, ou seja, cuja coordenada x constante ao longo de toda a reta. Neste caso, a equao implcita mais til:

Ax + By + C = 0

Os parmetros podem ser encontrados a partir de dois pontos:

A = y1 y2 B = x2 x1 C = x1y2 x2y1

Por fim, podemos descrever uma reta em funo de um parmetro que um nmero real e serdenominado t. Para isso, precisamos de dois pontos (P1 e P2) da reta. Portanto, dados dois pontos,podemos representar todos os outros infinitos pontos da reta em funo de t pela equao paramtrica:

P(t) = P1 + (P2 P1)t

A equao paramtrica faz uso de algumas das operaes vistas nas sees 1.7.5 e 1.7.4 e tem avantagem de ser independente do nmero de dimenses do espao.

1.7.7 Clculo de uma posio na reta

Com alguma frequncia, temos uma reta (ou segmento de reta), e queremos saber qual o valor de xpara determinado y (ou vice-versa). A seo 4.1 tem algumas dessas situaes.Esse problema facilmente resolvido por semelhana de tringulos, ou regra de trs. Por exemplo:suponha a situao da Figura 1.15 em que dados dois pontos P0 e P1, queremos calcular o valor de xpara um dado y.

P0 (x0, y0)

P1(x1, y1)

y

x = ?

y-y 0

y 1-y

0

x-x0 x1-x0

Figura 1.15: Clculo de uma posio na reta

Temos que:

y1 y0x1 x0

=y y0x x0

= x = x0 +(x1 x0)(y y0)

y1 y0

20

1.7.8 Equao do plano

Na seo 6.2 vamos precisar encontrar as constantes A, B, C e D que descrevem um plano por meiode sua equao implcita

Ax + By + Cz + D = 0

dados trs pontos P0 = (x0, y0, z0), P1 = (x1, y1, z1) e P2 = (x2, y2, z2). Os trs pontos esto em sentidopositivo, conforme a regra da mo direita. Assim, a normal ao plano :

~N = (P1 P0) (P2 P1) = (nx, ny, nz)

Dado um ponto P = (x, y, z) qualquer no plano definido por P0, P1 e P2sabemos que que um vetorque vai de P a P1 forma um ngulo de 90 com o vetor normal, portanto:

(x x1, y y1, z z1) ~N = 0

xnx x1nx + yny y1ny + znz z1nz = 0

nxx + nyy + nzz (x1nx + y1ny + z1nz) = 0

Assim, conclumos que:

A = nxB = nyC = nzD = (x1nx + y1ny + z1nz)

21

Captulo 2

Representao de Slidos

Para produzir imagens de objetos preciso ter alguma forma computacionalmente eficiente pararepresent-los. Na Orientao Objetos aprendemos a determinar quais so os elementos importan-tes de um objeto para possibilitar a computao daquele tipo de informao. Quais so os elementosimportantes para sintetizar a imagem de objeto?Vamos tomar como exemplo uma cadeira. Atributos de uma cadeira, poderiam ser o peso, a corpredominante, o nmero de patrimnio, o nome da empresa fabricante, etc. Esses atributos podemser teis para um sistema de controle de inventrio, mas certamente no contribuem para produziruma imagem da cadeira. Para produzir uma imagem da mesma, preciso uma descrio geomtricada mesma, alm de propriedades de material que sejam importantes para determinar como o objeto visto (uma mesa de vidro no vista da mesma forma que uma mesa de madeira, mesmo que ageometria das duas seja equivalente).Por hora, a preocupao a representao da geometria. As propriedades de material sero abordadasno captulo 7.Estamos interessados na representao da geometria de slidos, pois na natureza no existem objetosplanos. Existem objetos sem geometria bem definida como fogo, fumaa, etc., mas os soldos sosuficientes para representar uma grande quantidade de situaes reais ou imaginrias.Existem diversas formas para representar slidos. Algumas das mais diretas e comumente usadas soapresentadas aqui.

2.1 Enumerao de ocupao espacial

Provavelmente a forma mais direta de representao de slidos dividir o espao em elementosdiscretos que podem ou no fazer parte do solido. A diviso mais simples seria uma diviso regular,em que todas as clulas tm o mesmo volume. Assim, uma matriz 3D (considerando um espao3D) binria pode ser usada para representar uma cadeira ou qualquer outro slido. Neste tipo derepresentao, cada clula chamada de voxel (de volume element).

2.2 Geometria slida construtiva (Constructive Solid Geometry -CSG)

Conisiste em determinar uma srie de slidos primitivos (cubo, cone, esfera, etc.) e combin-los poroperaes matemticas (unio, interseo, diferena, etc.) para produo de outros slidos.

22

(a) (b)

Figura 2.1: (a) Elementos discretos segundo diviso regular (b) Conjunto de voxels representando umcarro. Imagem retirada de http://www.bilderzucht.de/blog/3d-pixel-voxel/.

Figura 2.2: Exemplo de representao de um slido por meio de operaes aplicadas a slidos primi-tos. Imagem extrada de http://en.wikipedia.org/wiki/File:Csg_tree.png

23

2.3 Modelagem baseada em pontos (Point based modeling)

Com o aumento da complexidade dos objetos cuja imagem pretende-se produzir, a modelagem base-ada em pontos tem ganhado fora recentemente. A ideia fundamental reproduzir uma quantidademassiva de detalhes de geometria. Todos esses detalhes de geometria sero eventualmente transfor-mados em pixels e a quantidade de pixels num dispositivo de apresentao no tem crescido tantoquando a informao geomtrica. Assim, existem vantagens a representao de slidos a partir deconjuntos de pontos procura tirar proveito dessa situao. Para mais informaes sobre modelagembaseada em pontos, veja [5].O barateamento de sensores espaciais, baseados em laser, ultrassom, ou infravermelho e luz visveltambm tem ajudado a popularizar o uso e processamento de modelos de slidos baseados em pontos,visto que estes aparelhos discretizam o espao sendo escaneado e localizam uma quantidade de pon-tos, produzindo um conjunto, frequentemente chamado de nuvem de pontos que representa o objetodigitalizado.

Figura 2.3: Imagem formada a partir de pontos da superfcie de um objeto. A quantidade de pontos pequena e o espao entre pontos grande para destacar a natureza discreta da imagem. Extrado dehttp://graphics.ethz.ch/publications/tutorials/eg2002/.

2.4 Modelagem tradicional

A maneira tradicional para representao de slidos envolve a descrio da sua superfcie a partirde um conjunto de polgonos chamados de faces. As faces so frequentemente tringulos, que soos polgonos mais simples. Um modelo geomtrico formado por um conjunto de tringulos quecompartilham arestas, determinando a superfcie de um slido frequentemente chamado de malhade tringulos.Esse tipo mais comum de modelagem de objeto e foco deste curso. Os objetos usados para sntesede imagens sero sempre representados por malhas de polgonos, a menos que algo contrrio seja

24

explcito.Vrios polgonos representam uma superfcie qualquer de maneira aproximada. Quanto maior a quan-tidade de polgonos, melhor ser a aproximao da representao em relao ao objeto. A figura 2.4apresenta um mesmo objeto aproximados por quantidades diferentes de tringulos. Nota-se que sonecessrios vrios tringulos para representar detalhes de uma superfcie.

Figura 2.4: Quatros aproximaes diferentes para a superfcie de um objeto. Extrado dehttp://polygon-reducer.pc-guru.cz/reducing-level-of-detail.

Para representar um objeto precisamos ento de polgonos. Para representar polgonos, precisamosde pontos. Pontos so posies no espao e no tem tamanho. Trs pontos no colineares repre-sentam um tringulo. Ateno para o fato de que quatro pontos no colineares no necessriamenterepresentam um quadriltero. Para tanto, preciso que os pontos sejam tambm coplanares.Queremos fazer programas de computador que produzem imagens de objetos, ento precisamos re-presentar esses objetos de forma que um programa possa fazer a leitura dos dados de maneira simplese eficiente. Vamos inventar um formato de arquivo que representa slidos. Para guiar este exerc-cio, vamos supor que queremos representar um cubo, que tem uma das pontas (chamadas de vrtices)na origem do sistema de coordenadas e aresta de tamanho 1, todas as trs se extendendo no sentidopositivo do sistema de coordenadas. Assim, o objeto em questo tem 6 faces (quadrados) definidaspor 8 vrtices, conforme apresentado na figura 2.5.Para representar o cubo, podemos usar um arquivo texto, descrevendo cada uma das seis faces, a partirde seus vrtices. As faces precisam conter informao suficente para determinar qual o lado de forae qual o lado de dentro do slido. Para isso vamos usar a conveno da regra da mo direita (seo1.7.3) e descrever os vrtices em sentido positivo com o dedo apontando para o lado de fora. Dessaforma sabemos no apenas qual polgono define a face mas tambm sabemos qual o lado visvel (olado interno de uma face de um slido no visvel). Na seo 1.7.8 foi mencionado o clculo deuma normal a partir de trs pontos em um plano. Num slido, existe a conveno de que a normal deuma face aponta para fora.A face1, por exemplo, determinada pelos vrtices 3, 8, 4 e 7. Devemos coloc-los em sequncia ede acordo com a regra da mo direita. Assim, a face1 pode ser descrita de quatro formas possveis:{7, 3, 4 e 8 }, {3, 4, 8 e 7}, {4, 8, 7 e 3} ou {8, 7, 3 e 4}. Vamos escolher essa ltima. Sabemos que ovrtice 8 tem coordenadas (0, 1, 1), o vrtice 7 tem coordenadas (1, 1, 1), o vrtice 3 tem coordenadas(1, 1, 0) e o vrtice 4 tem coordenadas (0, 1, 0).Assim, a face 1 poderia ser descrita por:

25

face1

face3

face4

face6

face5

face2

vrtice1

vrtice2

vrtice3vrtice4

vrtice5 vrtice6

vrtice7

vrtice8

x

y

z

Figura 2.5: As 6 faces e 8 vrtices de um cubo.

(0, 1, 1)(1, 1, 1)(1, 1, 0)(0, 1, 0)

Supondo que o slido um conjunto de faces e que cada face uma linha no arquivo texto, o cuboseria:

(0, 1, 1)(1, 1, 1)(1, 1, 0)(0, 1, 0)(0, 0, 0)(0, 1, 0)(1, 1, 0)(1, 0, 0)(1, 0, 0)(1, 1, 0)(1, 1, 1)(1, 0, 1)(0, 0, 1)(0, 0, 0)(1, 0, 0)(1, 0, 1)(1, 1, 1)(0, 1, 1)(0, 0, 1)(1, 0, 1)(0, 1, 0)(0, 0, 0)(0, 0, 1)(0, 1, 1)

Porm, esse arquivo seria muito difcil de ser lido por um programa com todos esses parnteses evrgulas. Vamos simplificar isso usando apenas nmeros separados por espao. Outro problema que existe muita redundncia no arquivo. Cada vrtice participa de trs faces e sua descrio aparecetrs vezes. Alm de ocupar mais espao do que necessrio, isso traria dificuldade para realizaralteraes nos dados. Se alterarmos um vrtice, ser necessrio procurar e alterar todas as suas outrasocorrncias. Para evitar isso, cada vrtice ser descrito uma nica vez no incio do arquivo. Depois,cada face ser descrita por ndices que representam os vrtices, comeando em 0.

Precisamos de algo que separe as descries de vrtices das descries de faces. Para essa separao,os dados vo comear um um nmero que indica a quantidade de vrtices no slido. Como cadavrtice tem trs coordenadas, fica fcil saber quantos nmeros devem ser lidos representando vrtices.Os outros representaro faces.

Para indicar o final de cada face, ao invs de usar o final de linha, usaremos um nmero: um ndiceinvlido, isso vai facilitar a leitura j que cada face poderia ter uma quantidade indeterminda devrtices. Assim, usaremos o valor -1 para indicar um final de face. O final de linha ao final decada face ser mantido apenas para facilitar a visualizao do arquivo, j que finais de linha sofacilmente descartados na leitura de nmeros em qualquer linguagem de programao. O arquivoficaria portanto:

26

80 0 01 0 01 1 00 1 00 0 11 0 11 1 10 1 17 6 2 3 -10 3 2 1 -11 2 6 5 -14 0 1 5 -16 7 4 5 -13 0 4 7 -1

Com essas regras simples, conseguimos descrever a geometria de um objeto qualquer. Nenhum re-curso para descrever mais de um objeto foi inventado. Formatos reais de representao de objetoscontm muito mais informaes que somente a geometria dos slidos. Outros elementos importantessero vistos ao longo do curso.

27

Captulo 3

Fundamentos Matemticos

Vamos estudar mtodos para gerar imagens a partir da descrio matemtica de um objeto. Essadescrio matemtica dever conter, entre outras coisas, uma descrio geomtrica do objeto, ou sejauma descrio de sua forma fsica. Mesmo que o objeto seja algo imaginrio, necessrio que eletenha forma para que se possa gerar sua imagem.

Em Computao Grfica, trabalharemos com trs grupos bsicos: escalares, pontos e vetores. Estestrs grupos podem ser definidos de pelo menos trs maneiras diferentes: matematicamente, geometri-camente ou do ponto de vista de estruturas de dados. Vamos tentar misturar estas trs definies.

Um escalar representa uma quantidade, seguindo algum padro de medio. Ele um nmero.

Um ponto representa uma posio no espao. Ele no tem dimenso e definido (no espao tridimen-sional) por trs coordenadas (trs nmeros), medidas em relao uma referncia pr-estabelecidaque chamaremos de sistema de coordenadas ou orientao.

Um vetor representa uma direo no espao. Ele no possui posio associada. Neste texto iremosevitar diferenciar os termos direo e sentido, aos quais no acostumamos por causa das aulas de f-sica. Estaremos usando direo para significar uma direo e sentido. Vetores dos quais diramos quetem mesma direo e sentidos opostos, sero ditos como tendo direes opostas, o que se aproximamais da linguagem popular. Por no possuir posio associada, vetores que estvamos acostumados achamar de paralelos, sero tratados neste texto como sendo vetores equivalentes, ou seja, vetores queindicam a mesma direo e que portanto so, na verdade, o mesmo vetor. Um vetor (no espao tridi-mensional) pode ser definido por trs coordenadas. Por exemplo: o vetor (0,1,0) pode ser entendidocomo o vetor que vai da origem (0,0,0) at o ponto (0,1,0) e, normalmente, poderamos chamar essadireo de para cima.

3.1 Transformaes Geomtricas

3.1.1 Definio

As transformaes geomtricas tm papel de destaque na computao grfica. Elas so a base ma-temtica que permite a obteno de resultados importantes em programas que trabalham com dados2D e 3D. Dentre as vrias aplicaes das transformaes geomtricas, temos interesse especial emutiliz-las para fazer projees seguindo o modelo da cmera estenopeica. Antes de utiliz-las, noentanto, importante defin-las formalmente para que seu significado fique bem claro.

28

3.1.1.1 Translao

Podemos entender a transformao de translao como o sendo um deslocamento em linha reta. Po-demos associar um fator de deslocamento a cada dimenso do espao onde estamos trabalhando, deforma que uma translao pode ser representada por vetor. No faz sentido aplicar uma translao avetor, j que no estamos associando posio a ele.

4 13

2

6T

P

P

Figura 3.1: Exemplo de translao

Na figura acima, vemos o ponto P(4, 2) onde foi aplicada uma translao (9, 4) transformando-o noponto P (13, 6).Muitas pessoas estranham o fato da translao ser um deslocamento em linha reta ou numa direo.Isso se deve associao do nome com movimento de deslocamento da Terra em torno do Sol ou daLua em torno da Terra. Esses movimentos no so em linha reta, mas isto deve ao fato deste movi-mento ser analisado em relao ao tempo. Como a direo do deslocamento muda a cada instante,o resultado final do deslocamento curvo. Matematicamente falando, uma translao no envolvetempo.

3.1.1.2 Rotao

A rotao pode ser definida como um movimento de giro, num plano, em relao a um referencial. Oresultado um deslocamento que preserva a distncia entre o ponto rotacionado e o referencial. Estatransformao preserva ngulos e distncias.No espao tridimensional, o referencial pode ser definido atravs da associao de um ponto com umvetor, que chamaremos de eixo. Assim, podemos dizer que um eixo um vetor ao qual existe umaposio associada ou, um vetor que passa por algum lugar. No espao bidimensional, o referencialpode ser definido por um ponto.A rotao, portanto, pode ser definida por um ngulo e um referencial (ponto ou eixo).

3.1.1.3 Escala

A transformao de escala pode ser entendida como a mudana de unidade de medida em uma oumais dimenses. Ela produz um efeito que pode ser associado ao zoom. Normalmente, a mudanade escala igual em todas as dimenses, de forma a preservar ngulos, mas isso no obrigatrio.Associaremos um fator de escala a cada dimenso. Apesar de no preservar ngulos e distncias, umatransformao de escala preserva o paralelismo entre linhas. Na figura 3.3, temos duas transformaes

29

eixo de referncia

P

PP

P

x

y

x

y

z

ponto de referncia

(a) (b)

Figura 3.2: Exemplo de rotao 2D (a) e 3D (b)

de escala no plano. Em (a) temos um fator de escala em x igual a 2 e fator de escala em y igual a 1.Note que no s as dimenses da casa mudaram, mas a tambm a sua posio relativa origem. Em(b) temos um fator de escala de 1.5 em x e em y. Note que os ngulos foram preservados.

(a) (b)

Figura 3.3: Transformao de escala

Quando um ou mais fatores de escala so negativos, dizemos que h espelhamento.A transformao de escala, portanto, representada por um conjunto de escalares (um para cadadimenso do espao).

3.1.1.4 Cisalhamento

A transformao de cisalhamento (shear) no um transformao primria, ela pode ser definida emtermos das transformaes anteriores, entretanto, devido sua utilidade, ela ser vista separadamente.Uma transformao de cisalhamento tem o efeito de puxar um objeto em uma ou mais dimensese no deve ser confundida com a rotao. Esta transformao definida por um escalar (fator decisalhamento) em cada dimenso que indica o quanto uma coordenada ser transladada em funo deoutra coordenada em outra dimenso. Apesar de no ser normalmente especificado em termos de umngulo, esse fator pode ser facilmente associado a um ngulo, conforme mostra a figura 3.4:

30

(,)xy (',')xy

x x' = + y cot

y y'=

x

y

Figura 3.4: cisalhamento em x, associado a um ngulo

A figura 3.4 mostra um cisalhamento em x, em relao a y. Notamos que um ponto sofre uma trans-lao em x que diretamente proporcional sua coordenada y.

(a) (b) (c)

Figura 3.5: Efeito da transformao de cisalhamento 2D

Na figura 3.5, podemos observar o efeito do cisalhamento sobre o um quadrado (a), comparando-ocom o resultado do cisalhamento em x (b) e em y (c).

x x

y y

z z

Figura 3.6: Efeito da transformao de cisalhamento 3D

Na figura 3.6, observa-se o efeito do cisalhamento em x e y em relao a z, sobre um cubo de centrona origem.

3.1.2 Representao

As transformaes apresentadas so representveis de maneiras diferentes, o que ruim para sistemasde computador pois, no final, todas representam um mesmo tipo de informao: uma transformao.Seria interessante que uma transformao pudesse ser tratada num programa como um objeto. Umatransformao deveria ser capaz de interagir com um ponto ou um vetor, gerando um novo ponto (ouvetor) que representaria a entidade inicial com suas caractersticas modificadas.

31

Vetores e pontos so um conjunto de coordenadas e portanto podem ser facilmente associados estrutura de dados vetor (da o nome ser o mesmo). As transformaes poderiam ser representadas pormatrizes (vetores de duas dimenses). Essas matrizes poderiam interagir com os vetores, produzindonovos vetores, o que nos leva ideia de representar os pontos (e vetores) como matrizes de umanica linha ou coluna que interagem com as matrizes por meio de operaes aritmticas tradicionais.Uma translao poderia ser representada pela soma de uma matriz de transformao com um ponto,enquanto que uma transformao de escala poderia ser representada pela multiplicao de uma matrizpor um ponto.Entretanto, desejvel que todas as matrizes de transformao sejam de um mesmo formato e quetodas as transformaes possam interagir com pontos da mesma maneira (com a mesma operaoaritmtica).Este objetivo pode ser alcanado se usarmos coordenadas homogneas para representar os pontos e osvetores. Desta forma, temos quatro coordenadas para representar um ponto no espao tridimensional.Em coordenadas homogneas, convencionamos que o ponto (x, y, z, w) o mesmo ponto no espaoque (x/w, y/w, z/w, 1), ou seja, (2, 1, 3, 1), (4, 2, 6, 2) e (1, 0.5, 1.5, 0.5) so representaes do mesmoponto. Um ponto cuja coordenada w 0, pode ser entendido com um ponto no infinito. Podemos dizerque no existe posio associada a um ponto no infinito, ento tal ponto passa a ser uma direo, ouseja, um vetor.Usando coordenadas homogneas, podemos representar qualquer transformao atravs de uma ma-triz 4x4 e a pr-multiplicao dessa matriz por um ponto (representado por uma matriz 4x1 resultanuma nova matriz 4x1 que representa o ponto depois da transformao. A grande vantagem dessarepresentao que duas transformaes podem ser combinadas pela multiplicao de suas matrizes,o que resulta numa nova matriz 4x4 que representa as duas transformaes iniciais ao mesmo tempo(ver seo 3.1.4).Alguns textos convencionam representar os vetores por matrizes linha que podem ser multiplicados direita por matrizes de transformao. Essas representaes para transformaes so conhecidas pormatrizes de ps multiplicao.

3.1.2.1 Matriz de Translao

Sabemos que, na transformao de translao, temos 3 fatores de translao (Tx, Ty, Tz), de tal formaque um ponto P (x, y, z), aps sofrer uma translao T (Tx, Ty, Tz), vira o ponto P (x, y, z) de talforma que:x = x + Txy = y + Tyz = z + TzIsso pode ser representado da seguinte forma:

x

y

z

1

=

1 0 0 T x0 1 0 Ty0 0 1 Tz0 0 0 1

xyz1

3.1.2.2 Matriz de Rotao

Para encontrar a frmula da rotao, vamos primeiro analisar a figura 3.7, que demostra uma rotaono plano, onde o ponto P (x, y), aps sofrer uma rotao em relao origem vira o ponto P (x, y):

32

P (,)xy

P' (',')xy

x

y

r

Figura 3.7: Rotao no plano, em torno da origem

Podemos identificar um segundo ngulo, na figura 3.7 (). Observa-se que:

x = r cos()y = r sin()e tambm que:

x = r cos( + )y = r sin( + )Logo:

x = r (cos() cos() sin() sin())y = r (sin() cos() + sin() cos())Donde:

x = r cos() cos() r sin() sin()y = r cos() sin() + r sin() cos()Portanto:

x = x cos() y sin()y = x sin() + y cos()No espao, esta a rotao em z, que pode ser representado da seguinte forma:

x

y

z

1

=

cos() sin() 0 0sin() cos() 0 0

0 0 1 00 0 0 1

xyz1

Analogamente, temos a rotao em x pode ser representada assim:

x

y

z

1

=

1 0 0 00 cos() sin() 00 sin() cos() 00 0 0 1

xyz1

E a rotao em y:

x

y

z

1

=

cos() 0 sin() 00 1 0 0

sin() 0 cos() 00 0 0 1

xyz1

33

3.1.2.3 Matriz de Escala

Da transformao de escala, sabemos que:x = sx xy = sy yz = sz zDe maneira que a transformao de escala pode ser representada assim:

x

y

z

1

=

sx 0 0 00 sy 0 00 0 sz 00 0 0 1

xyz1

3.1.2.4 Matriz de Cisalhamento

Estamos interessados no cisalhamento (shear) no espao, mas somente nas dimenses x e y. Cujoefeito ser importante no processo de projeo. Sabemos que:x = x + shx zy = y + shy zEsta transformao pode ser representada assim:

x

y

z

1

=

1 0 shx 00 1 shy 00 0 1 00 0 0 1

xyz1

3.1.3 Aplicao de transformaes a objetos

A aplicao transformaes a pontos ou vetores uma operao calculada pela multiplicao de ma-trizes. Dado um vetor e uma transformao, podemos encontrar o vetor transformado. O uso decoordenadas homogneas permite uma representao nica para pontos e vetores, alm de permitiruma representao nica para qualquer transformaes e uma nica maneira de aplicar transforma-es. Observe que mesmo em casos mais extremos como a aplicao de uma translao a um vetor(direo)1 esta abordagem vlida.A aplicao de transformaes objetos (polgonos, slidos, etc.) feita aplicao da transformao todos os elementos (pontos e vetores) que constituem o objeto. Considerendo que os objetos sotradicionalmente representados por descries vetoriais, ou seja, uma srie de parmetros para pri-mitivas, basta aplicar as transformaes nesses parmetros. Casos existam parmetros que no soposies nem direes, preciso encontrar uma representao para eles usando esses dois elementos.Por exemplo: distncias podem ser entendidas como a magnitude de um vetor.

3.1.4 Combinao de transformaes

As matrizes de transformao vistas na seo 3.1 podem ser combinadas para produzir outras transfor-maes mais sofisticadas. Assim, a partir de algumas poucas operaes cujas matrizes so facilmenteproduzidas, conseguimos produzir qualquer transformao desejada.

1Direes no esto em lugar algum e portanto transladar uma direo no teria nenhuma utilidade prtica. Observeque qualquer translao aplicada a uma direo resulta na mesma direo.

34

Suponha que desejamos apliacar ao ponto P uma translao T seguida de uma rotao R, produzindoo ponto P. Existe uma transformao que aplicada a P produz P? Sabemos que P = R(T P) e pelaassociatividade da multiplicao de matrizes, temos que P = (RT )P. Assim, se chamarmos RT deM, temos que P = MP e portanto a matriz M representa uma transformao equivalente transladare depois rotacionar.Assim, a multiplicao de duas ou mais matrizes de transformao produz uma matriz que representatoda a sequncia de transformaes. Como usamos matrizes de pr-multiplicao, a sequncia detransformaes pode ser entendida como acontecendo da direita para a esquerda.

3.1.4.1 Rotao (2D) em torno de um ponto arbitrrio

3.1.4.2 Escala fixando um ponto arbitrrio

3.1.4.3 Transformao de instncia

Com frequncia queremos produzir uma sequncia de transformaes para acomodar um objeto mo-delado num sistema de coordenadas em outro sistema de coordenadas. Para tanto, pode-se esperar anecessidade de uma transformao de escala (para deixar o objeto com o tamanho adequado), uma oumais transformaes de rotao (para deixar o objeto com a orientao adequada) e uma transforma-o de translao (para deixar o objeto no local adequado).A sequncia mais adequada para produzir os resultados esperados :

1. transformao de escala,

2. transformao (ou transformaes) de rotao.

3. transformao de translao.

Essa sequncia permite que os parmetros sejam encontrados de forma independente, sem neces-sidade de muita conta, provalvelmente mentalmente. Por exemplo, suponha que carro apresentadona figura 3.8-a deve ser colocado numa determinada posio do mundo (figura 3.8-b) com um tama-nho adequado (bem menor nessa imagem) e com uma orientao adequada (diferente da original).Fazendo a transformao de instncia na sequncia indicada, sabemos que a escala somente umaproporo entre o tamanho original e o tamanho final, a rotao em torno da origem e dada pelongulo entre a posio inicial e a final, alm de que a translao dada pela nova posio do carro(supondo a posio do carro como sendo a origem do sistema de coordenadas original).Outras sequncias de transformaes seriam menos idenpendentes e mais difceis de calcular. Porexemplo, se a translao for feita primeiro e a escala depois, a escala tambm vai alterar a posio docarro.

3.1.4.4 Rotao (3D) em torno de um eixo arbitrrio

3.1.5 Grafo de Cena

3.2 Mudanas Entre Sistemas de Coordenadas

As transformaes vistas anteriormente podem ser vistas como mudanas de um sistema de coorde-nadas.

35

(a) (b)

Figura 3.8: Caso de uso da transformao de instncia.

Na figura 3.9, vemos dois sistemas de coordenadas (SC1 e SC2), alm de uma rotao em torno daorigem que transforma SC2 em SC1. Essa mesma rotao transforma o ponto P no ponto P. Almdisso, notamos que as coordenadas de P em relao a SC2 so as mesmas de P em relao a SC1.

xSC1

xSC2

ySC1y

SC2

P

P'

Figura 3.9: Uma mudana de sistema de coordenadas representada por uma transformao geomtrica

Assim temos uma maneira prtica de transformar coordenadas medidas em SC1 para coordenadasmedidas em SC2: basta encontrar uma ou mais transformaes geomtricas que transformem SC2em SC1. No exemplo acima, para saber as coordenadas de P de acordo com SC2, aplicamos em P,com relao SC1, transformaes que levariam SC2 em SC1.Essas transformaes so facilmente visveis no plano, entretanto queremos trabalhar com sistemasde coordenadas de trs dimenses. Um sistema de coordenadas de trs dimenses pode ser trans-formado num outro sistema qualquer atravs de 6 transformaes simples: uma translao em cadadimenso mais uma rotao em cada dimenso. Isso porque trabalhamos com sistemas de coordena-das onde as 3 dimenses so perpendiculares entre si com sinal que respeita a regra da mo direita. Sepensarmos numa escala usada para fazer medies no sistema de coordenadas, precisaramos de maistrs transformaes de escala (uma em cada dimenso), mas isto no ser importante por enquanto.As trs translaes podem ser reduzidas numa s com fatores de translao nas trs dimenses mas astrs rotaes sero analisadas separadamente, de forma que possamos utilizar a matrizes de rotaovistas na seo 3.1.2.2.Para transformar um sistema de coordenadas em outro qualquer vamos ento utilizar a seguinte

36

sequncia de transformaes:

Uma translao que leve a origem de SC2 na origem de SC1;

uma rotao no eixo y, em torno da origem (relativa a SC1) que leve a direo de x em SC2 noplano xy de SC1. O valor absoluto do ngulo dessa rotao dado pelo ngulo entre a projeode x de SC2 no plano xz de SC1 e a direo de x em SC1;

uma rotao no eixo z, em torno da origem (relativa a SC1) que leve a direo de x em SC2 (jtransformada pelo passo 2) a ficar coincidente com a direo de x em SC1. O valor absolutodo ngulo dessa rotao dado pelo ngulo entre a direo de x em SC2 (j transformada pelopasso 2) e a direo de x em SC1;

uma rotao no eixo x, em torno da origem (relativa a SC1) que leve a direo de y em SC2 (jtransformada pelos passos 2 e 3) a ficar coincidente com a direo de y em SC1. O valor abso-luto do ngulo dessa rotao dado pelo ngulo entre a direo de y em SC2 (j transformadapelos passos 2 e 3) e a direo de y em SC1.

Uma observao importante que as direes das dimenses de SC2 devem ser conhecidas em coor-denadas medidas em SC1, para que seja possvel calcular os ngulos mencionados acima.Outras sequncias de transformaes (com outros valores) tambm podem transformar um sistema decoordenadas em outro (sempre uma translao e trs rotaes no mximo). Qualquer sequncia podeser usada.

3.3 Projeo

Conforme comentado anteriormente, para gerar a imagem de um objeto 3D, precisamos converteras coordenadas 3D em coordenadas 2D que correspondem a uma viso especfica do objeto. Esseprocesso chamado de projeo.Existem dois tipos de projeo: a perspectiva e a paralela. A projeo perspectiva aquela queacontece no processo de formao de imagens em nossos olhos ou numa cmera fotogrfica (verFigura 1.5), por isso a que gera imagens mais realistas. A projeo paralela pode ser vista comouma projeo perspectiva onde o centro de projeo est no infinito.Uma projeo pode, portanto, ser definida por um plano de projeo e um centro de projeo (ponto)ou direo de projeo (vetor). O plano de projeo no entanto, precisa estar relacionado com umsistema de coordenadas, ou seja, no basta que o plano esteja definido, preciso ser capaz de serepresentar qualquer posio nesse plano em relao a um referencial prprio.Conforme podemos observar na figura 3.10, na projeo paralela, as linhas que unem os pontos Ae B s suas projees A e B so paralelas, isto faz com que o segmento projetado tenha o mesmotamanho para qualquer distncia entre o plano de projeo e o objeto. Esta propriedade da projeoparalela bastante desejvel em reas como engenharia ou arquitetura porque torna possvel quealgum possa calcular as dimenses do objeto desenhado a partir de seu desenho.No processo de sntese de imagens, o plano de projeo ser uma representao de algum dispositivode apresentao (ex.: vdeo ou papel num impressora), por isso importante que exista um sistemade coordenadas embutido no plano de projeo (PP), de maneira que, a partir da coordenadas depontos de um objeto, descritas no sistema de coordenadas do mundo (SCM), seja possvel encontrarcoordenadas das projees desses pontos num sistema de coordenadas de apresentao (SCA). Essasnovas coordenadas sero usadas para enviar comando de desenho para dispositivo de apresentao,formando a imagem desejada.

37

A A

B B

A' A'

B' B'

centro deprojeo

centro deprojeo

no infinito

ProjeoPerspectiva

ProjeoParalela

Figura 3.10: Projeo perpsectiva e projeo paralela

3.3.1 Projeo Paralela

Para encontrar uma frmula que nos permita fazer uma projeo paralela qualquer, vamos primeiroimaginar um projeo paralela simples o suficiente para que o clculo da projeo seja trivial.Tal projeo poderia ser aquela definida por um PP que coincide com o plano XY do SCM de talforma que a origem do PP coincida com a origem do SCM, a direo de X e de Y do SCA coincidamcom a direo de X e de Y do SCM, e a escala nos dois sistemas seja a mesma. A direo de projeoseria paralela direo do eixo Z do SCM, com o vetor (0, 0, -1), por exemplo.Neste caso fica visvel que a projeo do ponto (x, y, z) com coordenadas medidas no SCM temcoordenadas (x, y) no SCA.

ySCM

ySCA

xSCM

xSCA

zSCM

origem de SCAe de SCM

direo de projeo(0, 0, -1)

SCM

P

P'

Figura 3.11: Projeo Paralela Especial

Na figura 3.11 observamos que P tem as mesmas coordenadas x e y de P, mesmo considerando queas coordenadas de P so medidas de acordo com SCM e as coordenadas de P so medidas em SCA.Esta no a nica projeo paralela cujo resultado trivial, entretanto, ela suficiente para desen-volvermos uma frmula para uma projeo qualquer. Quando uma projeo paralela no estiver deacordo com este caso especial, aplicaremos em P uma srie de transformaes que transformariamSCA em SCM. Os valores das coordenadas x e y de P aps essas transformaes sero os valores dascoordenadas x e y de P em SCA, conforme visto na seo 3.2.

38

Existem vrias maneiras de aplicar um conjunto de transformaes geomtricas simples, numa deter-minada ordem, de maneira a resolver esse problema. Na figura 3.12 vemos dois dos caminhos maisusados:

Projeo Paralela Genrica

Transladar a origem doplano de projeo paraa origem

"Rotacionar" o planode projeo para queele coincida com oplano xy

"Rotacionar" o planode projeo para queele coincida com oplano xy

z

x

z

x

z

x

z

x

z

x

Inclinar

ou

Transladar a origem doplano de projeo paraa origem

Figura 3.12: Transformao de uma projeo paralela genrica numa projeo paralela especial

Uma seqncia de transformaes pode ser representada pela multiplicao das matrizes de transfor-mao. Com isso obtemos uma matriz 4x4 que representa a projeo paralela desejada. Essa matrizser aplicada em cada ponto do objeto cuja imagem deseja-se criar.

3.3.2 Projeo Perspectiva

Da mesma forma que no caso da projeo paralela, pretendemos encontrar uma projeo perspectivacom caractersticas especiais que permitam encontrar seu resultado de maneira trivial. Tal projeo

39

poderia ser:

ySCM

ySCA

xSCM

xSCM

zSCM

zSCM

xSCA

xSCA

plano deprojeo

P

P

P'

P'CP

zP

xP

xP'

zP'

(a) (b)

Figura 3.13: Projeo Perspectiva Especial

Na figura 3.13 (a), as coordenadas (x, y) que representam o ponto P de acordo com SCA podem serencontradas por semelhana de tringulos como mostrado em (b), que representa a mesma situao,vista de cima do eixo y. Portanto, sabemos que:x = x z / zy = y z / zO que pode ser representado pela matriz de transformao:

1 0 0 00 1 0 00 0 1 00 0 1/z 0

A matriz acima altera o valor da coordenada w de um ponto e portanto altera as coordenadas x, y ez. Infelizmente a alterao da coordenada z no era desejvel, entretanto, essa coordenada no temimportncia no resultado da projeo.Queremos agora, encontrar um conjunto de transformaes simples que transformariam uma pro-jeo perspectiva qualquer na projeo perspectiva especial que acabamos de ver. Na figura 3.14,observamos duas das maneiras mais utilizadas:Assim como na projeo paralela, podemos obter uma matriz de projeo perspectiva, multiplicandoas matrizes de cada transformao mais simples, sem esquecer da matriz de projeo perspectivaespecial que eqivale aplicao da regra de trs.

40

Projeo Perspectiva Genrica

z

x

z

x

z

x

z

x

z

x

z

x

Transladar a origemdo plano de projeopara a origem do sis-tema de coorde-nadas do mundo

"Rotacionar" o planode projeo para queele coincida com oplano xy (eixos namesma direo)

"Rotacionar" o planode projeo para queele fique paralelo aoplano xy (eixos namesma direo)

Transladar o centrode projeo paraa origem

Transladar o centrode projeo paraa origem

Inclinar atque a origemdo plano deprojeo estejano eixo z

Figura 3.14: Transformao de uma projeo perspectiva genrica numa projeo perspectiva especial

41

Captulo 4

Mtodos de Recorte

Recorte o nome dado ao processo de eliminao de partes de um desenho que esto fora de umarea de interesse. Por exemplo: Pode ser necessrio apresentar uma imagem de maneira que ela nocaiba totalmente na janela de apresentao. Para evitar erros que podem ser causados pela tentativade se desenhar algo numa regio invlida, determina-se o que que pode realmente ser desenhado.

exemplo de texto

janela de apresentao janela de apresentao

recorte

Figura 4.1: Exemplo de recorte

A primitiva de desenho mais importante o segmento de reta, pois qualquer outra forma ou primitivapode ser aproximada por um conjunto de segmentos de reta. Abaixo veremos alguns do principaisalgoritmos para recorte de segmentos de reta.

4.1 Algoritmos de Recorte para Segmentos de Reta

Conjuntos de segmentos de reta podem ser usados como aproximao para outros elementos grficos.Sabendo recortar segmentos de reta, grande parte dos problemas de recorte podem ser resolvidos.

4.1.1 Algoritmo de Cohen-Sutherland

Este algoritmo realiza testes iniciais para verificar quando necessrio calcular pontos de interse-o com o retngulo de recorte. Alguns casos onde o segmento de reta est totalmente dentro doretngulo de recorte ou totalmente fora so facilmente reconhecidos, no havendo necessidade de serealizar clculos, o que pode significar um grande ganho de tempo, nos casos em que o retngulo derecorte muito pequeno ou muito grande. Se ele for muito pequeno, poucas intersees precisam sercalculadas, se ele for muito grande, acontece o mesmo.

42

Para realizar esses testes iniciais, divide-se o plano do retngulo de recorte em 9 regies. Cada regio rotulada com um cdigo binrio conforme a figura 4.2:

0001 0000 0010

1001 1000 1010

0101 0100 0110

Figura 4.2: Cdigos das regies de recorte.

O primeiro bit (o bit mais esquerda) ser 1 se e somente se a regio rotulada estiver acima doretngulo de recorte. O segundo bit ser 1 quando a regio estiver abaixo do retngulo de recorte.O terceiro bit ser 1 se ela estiver direita e quarto ser 1 se ela estiver esquerda. Para realizaro recorte de um segmento de reta, classifica-se as duas extremidades do segmento de acordo com ortulo da regio onde a extremidade se encontra.

Se ambos os cdigos forem zero, o segmento est todo dentro da regio de recorte e no necessriocalcular nenhum ponto de interseo. Alm disso, se o resultado de um operao de e lgico bita bit for diferente de zero, ento os dois cdigos tem um bit em comum e portanto o segmento esttotalmente fora do retngulo de recorte (veja Figura 4.3).

Se nenhum desses dois testes for verdadeiro, o segmento pode estar interceptando o retngulo derecorte ou pode estar totalmente fora dele. Neste caso, devemos calcular uma interseo do segmentode reta com um dos lados do retngulo de recorte. Os dois novos segmentos de retas resultantesdo clculo desta interseo sero recortados recursivamente pelo algoritmo, at que cada segmentoresultante esteja totalmente dentro ou totalmente fora do retngulo de recorte.

No pior dos casos, quatro intersees devero ser calculadas para se encontrar o recorte de um seg-mento, alm disso a maneira como os limites so escolhidos para clculo da interseo afeta o desem-penho do algoritmo, por exemplo, no caso da 4.3, calcular a interseo com o lado de baixo (ao invsdo lado de cima), seria um desperdcio. Porm, o clculo da interseo com o lado direito poderia serfeito, j que a interseo est dentro do segmento de reta.

Para escolher um lado da rea de recorte que fornea um ponto dentro do segmento, para consultaros bits do cdigo de cada ponto. Sabemos que um dos cdigos diferente de zero, ento olharemoscada bit desse cdigo at encontrar um que seja igual a 1. O lado correspondente a esse bit um bomcandidato a produzir uma interseo til. Se voc no lembra como calcular uma interseo, reveja aseo 1.7.7.

Calculada a interseo existe um problema de classificao. Ainda conforme o exemplo da figura,existem duas possibilidades para a classificao da interseo:

1. a interseo classificada como dentro da rea de recorte, fazendo com que o segmento superiorda subdiviso precise ser recortado com o lado superior novamente e

2. a interseo classificada como acima da rea de recorte, fazendo com que o segmento inferiordo da subdiviso precise ser recortado com o lado superior novamente.

43

Segmento inicial a ser recortado

chamadasrecursivas

Sub-segmento totalmentefora da rea de recorte

Sub-segmento totalmentedentro da rea de recorte

fim do recorte

Figura 4.3: Procedimento de recorte de acordo com o algoritmo Cohen-Sutherland.

Dessa forma, uma implementao desenvolvida com pouca ateno nunca terminaria. Esse problemapode ser resolvido fazendo com que a interseo calculada seja classificada com dois cdigos diferen-tes. Ao ser associada com o ponto acima da rea de recorte, o bit correspondente da interseo seria1, proporcionando o descarte da parte superior da subdiviso. Ao ser associada com o ponto abaixodo limite superior da rea de recorte, o bit correspondente da interseo seria 0, proporcionando aclassificao da parte inferior da subdiviso como totalmente dentro da rea de recorte.

Entretanto, facil ver que com o clculo de uma interseo, uma das subdivises do segmento de retapode ser diretamente descartada (aquela que a interseo forma com o ponto cujo cdigo diferentede zero e foi usado para escolha do lado a ser usado no clculo da interseo). Assim, percebe-se quecada segmento de reta gera um nico novo segmento, menor, a ser recortado e a implementao podeser facilmente transformada numa iterao.

4.1.2 Recorte Paramtrico

Em 1978, Cyrus e Beck propuseram um outro algoritmo, geralmente mais eficiente do que o algoritmode Cohen-Sutherland. Este algoritmo pode ser usado no recorte de segmentos de reta no plano, etambm no recorte de segmentos de retas no espao, em relao a um slido convexo. Veremos ocaso 2D.

Vamos representar o segmento de reta que vai do ponto P0 a P1 pela equao paramtrica da reta:

P(t) = P0 + (P1 - P0)t

Onde t varia de 0 a 1, sendo 0 no ponto P0 e 1 no ponto P1. Seja PLi um ponto aleatrio sobre umdos lados da rea de recorte (lado Li). Um ponto qualquer do segmento a ser recortado pode estar emuma de trs situaes possveis: fora da rea de recorte, sobre o lado Li ou dentro da rea de recorte.Podemos determinar em qual dessas trs situaes um ponto P(t) est, calculando o produto escalar

44

entre o vetor que vai de PLi at P(t) e o vetor que vai de P0 a P1, conforme mostra a figura 4.41. Ovalor do produto escalar ser positivo se P(t) estiver fora da rea de recorte, ser zero se estiver sobreo lado e ser menor que zero se estiver dentro da rea de recorte.

Figura 4.4: Determinao da interseo de um segmento com um lado da rea de recorte.

Mais ainda, podemos usar o produto escalar para determinar qual o ponto que est sobre o lado Li,ou seja, qual a interseo entre o segmento e o lado da rea de recorte. Para tanto, basta isolar o valorde t na equao do ponto que est na interseo. Desta forma, temos:Ni [P(t) PLi] = 0Substituindo o valor de P(t):Ni [P0 + (P1 P0) t PLi] = 0A seguir, agrupamos termos:Ni [(P0 PLi) + (P1 P0) t] = 0Distribuindo o Ni, temos:Ni [P0 PLi] + Ni [P1 P0] t = 0Chamamos o vetor (P1 P0) de D:Ni [P0 PLi] + Ni Dt = 0E isolamos o t do lado esquerdo:

t =Ni [P0 PLi]Ni D

Observe que a equao acima vlida somente se o denominador da equao for diferente de zero.Isso poderia acontecer se o segmento a ser recortado for paralelo linha de recorte (ou se P0 = P1).Se o denominador for igual a zero, podemos verificar o sinal do numerador. Se ele for positivo, entoP0 est fora da rea de recorte (reveja a Figura 4.4), portanto todo o segmento est fora da rea de

1Note que essa classificao relativa a um dos lados da rea de recorte, e no relativa rea toda.

45

recorte e deve ser descartado. Se o numerador for negativo, deixaremos que o clculo das interseescom os outros lados da rea de recorte prossigam.

Temos portanto uma frmula para calcular a interseo entre um segmento qualquer e um dos ladosda rea de recorte. Esta frmula produz a descrio de um ponto por meio de seu parmtero t eno por meio de suas coordenadas. Poderamos calcular todos os valores de t e us-los para calcularas coordenadas dos pontos de interseo e consequentemente o segmento recortado, porm ainda preciso diferenciar quais valores de t so teis e quais no so. Teremos at quatro de valores det resultantes dos clculos, mas s alguns deles so realmente teis para determinar o resultado dorecorte. Queremos que essa determinao seja feita com um mnimo de processamento.

O primeiro passo classificar cada ponto de interseo como potencialmente entrando (PE) ou po-tencialmente saindo (PS), ou seja, queremos saber se o segmento de reta sendo recortado pareceentrar ou sair da rea de recorte pelo lado em questo. Isso pode ser feito pelo sinal do denominador,que indica se o ngulo dos vetores em questo maior ou menor que 90. O sinal do denominadortem sinal contrrio ao do produto escalar e portanto contrrio ao seno do ngulo. O segmento estpotencialmente saindo se o denominador for maior que zero e vice-versa.

Valores de t PE devem ser descartados se forem anteriores a um ponto de entrada conhecido, j que osegmento no pode entrar duas vezes na rea de recorte. Se o valor de t for posterior um ponto desada do segmento, o segmento todo est fora da rea de recorte, j que o segmento no pode primeirosair da rea de recorte e depois entrar.

De forma anloga, valores de t PS devem ser descartados se forem posteriores a um ponto de sadaconhecido e o segemento todo deve ser descartado se um t PS for anterior a um ponto de entrada dosegmento.

Os pontos de entrada e sada do segmento na rea de recorte podem ser inicializados respectivamentecom valores de 0 e 1 para t. Assim somente valores entre 0 e 1 sero usados e os pontos P0 e P1faroparte do resultado a menos que pontos mais internos ao segmento sejam encontrados.

Ao final do recorte em relao aos quatros lados, teremos um valor de t para o ponto de entrada,cujas coordenadas devem ser calculadas se t > 0 (se t = 0, o ponto de entrada P0 e portanto temcoordenadas conhecidas). Teremos tambm um valor de t para o ponto de sada, cujas coordenadasdevem ser calculadas se t < 1. Assim no so calculadas coordenadas que no faam parte doresultado. O algoritmo 4.1 formaliza uma forma de estabelecer a sequncia dos testes e clculos.

A fim de fixar a ideia deste algoritmo, a figura 4.5 apresenta vrios casos possveis de recorte de umsegmento de reta em relao a um retngulo de recorte, junto com uma classificao PE/PS para cadainterseo. Procure verificar mentalmente a sequncia de testes em cada caso para garantir que vocentendeu o processo.

Em 1984 este algoritmo foi aperfeioado por Liang e Barsky tornando-se mais eficiente nos casos emque o volume de recorte um retngulo alinhado com os eixos do sistema de coordenadas, que sojustamente os casos que nos interessam. Considerando esta situao especial, sabemos que a normalN i sempre tem uma coordenada com valor 0, o que significa que o produto escalar N i (P0 PLi)no precisa considerar a coordenada correspondente no vetor (P0PLi), justamente a coordenada queprecisaria ser aleatriamente escolhida. Exemplo: para o limite esquerdo do retngulo de recorte,N i = (1, 0), logo no precisamos considerar a coordenada y (indeterminada para uma linha vertical).O numerador do clculo de t fica ento 1(x0 xmin) = xmin x0.Da mesma forma, o denominador do clculo de t, fica reduzido a dx ou dy. A tabela 4.1 mostraa frmula para o clculo de t em cada um dos lados de um retngulo alinhado com o sistema decoordenadas. Essas frmulas representam uma boa economia de operaes aritmticas em relao formula geral apresentada antes.

46

Algoritmo 4.1 Recorte Paramtrico.1. Inicializar a posio de incio com 0.2. Inicializar a posio de fim com 1.3. Para cada lado da rea de recorte:3.1. Calcular o nmerador e o denominador da frmula de t.3.2. Se o segmento for paralelo ao lado de recorte, ento3.2.1. Se o segmento estiver fora da rea em relao ao lado, ento3.2.1.1. Responder com segmento vazio.

seno:3.2.2. Calcular o valor de