apostila-Computação -Grafica3, Notas de estudo de Informática

Baixe apostila-Computação -Grafica3 e outras Notas de estudo em PDF para Informática, somente na Docsity! Introduc~ao a Computac~ao Gra ca Notas do Curso de Computac~ao Gra ca I, 2000 Paulo Roma Cavalcanti Universidade Federal do Rio de Janeiro - UFRJ 2 SUMARIO 5 10.5 Aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 10.6 Tipos de Amostragem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 10.7 Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 11 Visibilidade 143 11.1 Classi cac~ao dos Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 11.2 Transformac~ao Perspectiva . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 11.3 Back-Face Culling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 11.4 z-Bu er . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 11.5 Scan-Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 11.6 z-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 11.7 Partic~ao do Espaco - BSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 11.8 Subdivis~ao de Area . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 11.9 Recorte Recursivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 11.10Tracado de raios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 11.11Linhas Escondidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 11.12Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 12 Iluminac~ao 157 12.1 Modelos de Iluminac~ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 12.2 Calculo do Vetor de Re ex~ao . . . . . . . . . . . . . . . . . . . . . . . . . . 161 12.3 Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 13 Colorizac~ao 165 13.1 Colorizac~ao Constante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 13.2 Colorizac~ao de Gouraud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 13.3 Colorizac~ao de Phong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 13.4 Colorizac~ao por Tracado de Raios . . . . . . . . . . . . . . . . . . . . . . . . 170 13.5 Integrac~ao da Equac~ao de Iluminac~ao . . . . . . . . . . . . . . . . . . . . . 170 13.6 Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 14 Mapeamentos 173 14.1 Mapeamento de Textura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 14.2 Mapeamento de Rugosidade . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 14.3 Mapeamento de Ambiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 6 SUMARIO Captulo 1 Introduc~ao O objetivo deste texto e servir como base a um curso introdutorio de Computac~ao Gra ca. Considerando a Computac~ao Gra ca, em ultima analise, como uma forma de matematica aplicada, isto signi ca que ir~ao ser utilizados, na maioria das vezes, modelos matematicos simpli cados, cando para os cursos mais avancados o estudo dos modelos mais complexos, que procuram retratar a realidade mais elmente. 1.1 Areas Correlatas O primeiro ponto a ser discutido e: qual o objetivo da Computac~ao Gra ca? Colocando de maneira extremamente espartana, pode-se a rmar que o objetivo primordial da Computac~ao Gra ca e transformar dados em imagens. Assim, existe o problema da modelagem dos dados (criac~ao, estruturac~ao e analise dos dados) e o problema da visualizac~ao destes dados. O objetivo inverso, ou seja, a recuperac~ao dos dados a partir de uma imagem (analise de imagem), corresponde a area de Vis~ao Computacional, que e muito importante, por exemplo, em robotica. Por m, ainda existe a necessidade de manipulac~ao de imagens com o objetivo de processar, de alguma forma, uma imagem, para produzir uma nova imagem, a partir de operac~oes de ltragem e de deformac~ao, ou simplesmente com o objetivo de compactac~ao. Estes problemas s~ao tratados na area de Processamento de Imagens. Tanto a area de Vis~ao Computacional como a area de Processamento de Imagens n~ao ser~ao abordadas neste texto. A gura 1.1 busca esquematizar os relacionamentos entre as areas citadas. 1.2 Paradigma dos Universos Um paradigma de abstrac~ao util consiste em estabelecer quatro universos (conjuntos) dis- tintos:  o universo fsico F , que contem os objetos do mundo real que pretende-se estudar;  o universo matematico M , que contem uma descric~ao matematica abstrata dos objetos do universo fsico, em geral, idealizados (simpli cados), para permitir a sua descric~ao atraves de um modelo matematico simples; 7 10 CAPITULO 1. INTRODUC ~AO 1.4 Estrutura do Livro Como ja foi dito, o problema basico da Computac~ao Gra ca consiste em transformar dados em imagens (gerar uma fotogra a virtual). Desse modo, de um ponto de vista didatico, esse processo de transformac~ao pode ser dividido em duas etapas: Modelagem e Visualizac~ao. A Modelagem se ocupa da criac~ao e representac~ao dos objetos, chamados modelos, no computador. Na Modelagem, tenta-se representar no computador o mundo fsico real. Ja a visualizac~ao estuda os metodos e tecnicas utilizados para obter-se, a partir do modelo, uma imagem, que e o produto nal da Computac~ao Gra ca. Uma proposta deste texto e que as noc~oes basicas sobre cor e imagem sejam apresentadas antes que se discutam a visualizac~ao e iluminac~ao, e n~ao, como faz a maioria dos livros de Computac~ao Gra ca, apos. Isto evita que o aluno que com uma vis~ao distorcida ou simpli cada do problema e que possa entender (ou implementar) algoritmos capazes de lidar adequadamente com cores (algoritmos policromaticos). Desta forma, este texto se divide do seguinte modo:  Noc~oes Preliminares Fundamentos de Cor Dispositivos Gra cos Imagem Digital  Modelagem Geometrica Geometria e Transformac~oes Esquemas de Representac~ao Sistemas de Modelagem  Visualizac~ao Câmera e Recorte Rasterizac~ao e Amostragem Visibilidade  Iluminac~ao Propriedades dos Materiais e Modelos de Iluminac~ao Colorizac~ao e Mapeamentos  Decis~oes de Sistema 1.5 Objetivos e Pre-Requisitos Os objetivos que pretendem-se atingir s~ao:  Oferecer uma vis~ao global da area de Computac~ao Gra ca  Discutir os conceitos pre-estabelecidos 1.6. REFERÊNCIAS BIBLIOGRAFICAS 11  Apresentar os principais problemas da area  Fornecer uma base solida para um desenvolvimento futuro O publico alvo deste texto e composto por:  Futuros Pesquisadores  Projetistas de Sistemas Gra cos  Programadores de Computac~ao Gra ca e os pre-requisitos necessarios s~ao:  Programac~ao de Computadores  Algebra Linear  Calculo 1.6 Referências Bibliogra cas Existem varios livros de Computac~ao Gra ca, geralmente em lngua inglesa, no merca- do. Eles podem ser consultados dependendo da disponibilidade e interesse de cada leitor. Indicam-se aqui os mais adequados, na opini~ao dos autores:  De carater Geral Foley [1] Newman [2] Watt [3] Slater  Modelagem Farin [4] Mantyla [5] Ho man [6] K B's [7]  Visualizac~ao Glassner [8] Hall [9]  Processamento de Imagem Gonzalez [10] Wolberg [11] 12 CAPITULO 1. INTRODUC ~AO  Implementac~ao Harrington [12] Gems [13] [14] [15] [16] [17]  Outros Samet [18] Pavlidis [19] Rogers [20] 1.7 Exerccios 1.1 Faca uma comparac~ao entre as areas de Computac~ao Gra ca, Processamento de Ima- gens e Vis~ao Computacional. Dê pelo menos dois exemplos de aplicac~ao em cada uma dessas areas. 1.2 Explique o Paradigma dos Universos. Discuta a natureza de cada nvel de abstrac~ao. 1.3 Considere o seguinte problema: Implementar no computador um sistema para desenhos de discos metalicos. Discuta detalhadamente esse problema do ponto de vista do paradigma dos quatro universos (incluindo implementac~ao). 2.3. REPRESENTAC ~AO DISCRETA DE COR 15 uma antena e o sinal original e reconstrudo pelo monitor da televis~ao. A cor reconstruda e idêntica (perceptualmente) a cor original devido ao fenômeno do metamerismo, de nido na proxima sec~ao. A gura 2.3 ilustra o processo. TV(R,G,B) camara Sinal Original Cena amostragem antena Transmissao Reconstrucao Sinal Reconstruido Figura 2.3: Amostragem e Reconstruc~ao. 2.3 Representac~ao Discreta de Cor O espaco de todas as distribuic~oes espectrais possui dimens~ao in nita. Para obter-se uma representac~ao nita, ou seja, aproximar este espaco de dimens~ao in nita por um espaco de dimens~ao nita, e necessario fazer algum tipo de amostragem. Isto faz com que se utilize um vetor de dimens~ao nita na representac~ao de uma func~ao: R : f 2 D ! (f(x1); f(x2); :::; f(xn)) 2 <n: Esta representac~ao de ne uma transformac~ao linear, pois: R(af1+ bf2) = aR(f1)+ bR(f2): E claro que este processo de amostragem acarreta em perda de informac~ao ( g. 2.4) (a representac~ao e ambgua, ou seja, um mesmo vetor pode representar mais de uma func~ao). Este tipo de representac~ao e valida, no entanto, porque o problema de cor deve ser abordado do ponto de vista perceptual e n~ao do ponto de vista fsico (na realidade e um problema psico-fsico). Em 1807, Young concluiu, a partir de experimentos, que o olho hu- mano possui três tipos de receptores luminosos (celulas) que s~ao mais sensveis ao intervalo (da radiac~ao) que corresponde aos comprimentos de onda na faixa do vermelho, verde e azul, respectivamente. Estes três tipos de receptores fazem uma amostragem da radiac~ao nestes três comprimentos de onda. Desta forma, o espaco perceptual de cor e um espaco de dimens~ao nita (dimens~ao três). Isto signi ca que uma mesma sensac~ao de cor pode ser obtida a partir de distribuic~oes espectrais distintas, um fenômeno conhecido por metame- rismo. Gracas a isto a televis~ao produz imagens aceitaveis ao ser humano, uma vez que o conjunto de distribuic~oes espectrais existentes na natureza e muito mais rico do que aquele que pode ser produzido arti cialmente no monitor de uma televis~ao. 16 CAPITULO 2. COR x1 x2 x3 E y blue (400 nm) red (700 nm) (comprimento de onda) Figura 2.4: Representac~ao Finita de duas Func~oes. 2.4 Espacos de Cor Dada uma func~ao de distribuic~ao espectral C() (que corresponde a uma sensac~ao de cor), um sistema emissivo com uma certa base de primarias Pk() e um sistema re etivo, como calcular as componentes na base de primarias de forma a que a cor reconstruda Cr() seja perceptualmente equivalente a cor original em relac~ao ao sistema re etivo? E possvel mostrar que conhecendo-se a resposta espectral do sistema em cada compri- mento de onda, obtêm-se as func~oes de reconstruc~ao de cor rk() ( g 2.5), que indicam as proporc~oes nas quais as cores primarias devem ser combinadas para igualar a cor desejada. Por de nic~ao, a resposta espectral do sistema e dada para um certo comprimento de onda pelas componentes, na base de primarias, da distribuic~ao espectral conhecida como cor espectral ( g. 2.6), que e diferente de zero apenas neste comprimento de onda. Desta forma, tem-se que Cr() = nX k=1 ckPk(); ck = Z +1 0 C()rk()d: A resposta espectral do sistema pode ser obtida experimentalmente. Para isto usam-se quatro emissores de luz. Os três primeiros correspondem as cores primarias e podem ter as intensidades controladas. O quarto emite a luz monocromatica que se deseja igualar. Direcionando os três fachos de luz provenientes dos três emissores primarios para um unico ponto, e ajustando as suas intensidades ate que, para um observador padr~ao, a cor resultante seja idêntica a cor do quarto emissor, obtêm-se as componentes da luz monocromatica de teste em relac~ao a base de primarias ( g. 2.7). Algumas cores n~ao s~ao igualadas, a menos que se adicione uma primaria junto com a cor de teste. Matematicamente, isto corresponde a uma intensidade negativa. Neste ponto o leitor ja deve ter percebido que o objetivo e escrever uma dada cor como 2.4. ESPACOS DE COR 17 XYZ 1.061.00 1.78 599555446 770 XY Z RGB 1.97 1.22 1.80 604543446 R G B -1.6-1.4-1.2 0.2 -1.0 0.4 -0.8 0.6 -0.6 0.8 -0.4 1.0 -0.2 1.2 1.4 0.2 1.6 0.4 1.8 0.6 2.0 0.8 2.2 1.0 2.4 1.2 2.6 1.4 2.8 r g X Y Z 0.2 0.2 0.4 0.4 0.6 0.6 0.8 0.8 1.0 1.0 x y 700 - red 546 - green 435.8 - blue Figura 2.5: Func~oes de Reconstruc~ao de Cor. 0 Figura 2.6: Cor Espectral. 20 CAPITULO 2. COR R G B c’ Linha Purpura Ponto Acromatico (1/3,1/3,1/3) 1 1 1 Cor c Comprimento de onda dominannte da cor c cor complementar Figura 2.8: Diagrama de Cromaticidade. Todo vetor de cor c pode ser escrito, de modo unico, como soma direta de um vetor pertencente a ker(L) = fc 2 <3 : L(c) = 0g (nucleo de L) e de um vetor pertencente a um subespaco complementar de ker(L) | na forma c = ker(L) `; c = cc + cl. Sabe-se da algebra linear que a dimens~ao do nucleo mais a dimens~ao da imagem de uma transformac~ao linear L : <n ! <m e igual a dimens~ao do domnio da transformac~ao: dim(Ker(L)) + dim(Im(L)) = n: No caso presente, isto signi ca que a dimens~ao do nucleo do funcional de luminância e 2. Se duas cores têm a mesma luminância, L(c1) = L(c2), conclui-se que c1 e c2 est~ao em um hiperplano a m cv = c0 + v, paralelo ao nucleo do operador de luminância ( g. 2.9): L(c1 c2) = 0) c1 c2 2 ker(L): Cada hiperplano a m paralelo ao nucleo do operador de luminância e chamado de um hiperplano de crominância (luminância constante). A decomposic~ao em crominância-luminância e de extrema importância na de nic~ao de diversos sistemas de coordenadas no espaco de cor. Para nalizar, de ne-se um solido de cor como sendo o conjunto de cores realizaveis em um espaco de cor e um mapa de cor como sendo uma curva no solido de cor ' : I  < ! S  <3: 2.6. LUMINÂNCIA 21 c1 c2 c1-c2 ker(L) c1-c2 l Figura 2.9: Decomposic~ao Crominância-Luminância. 2.6 Luminância Apos a discus~ao sobre decomposic~ao crominância-luminância, o leitor deve estar se pergun- tando o que e, a nal de contas, a luminância. Para compreender este conceito, suponha-se uma luz monocromatica com potência constante de 1 watt. Sera que a resposta do olho a este estmulo e linear, ou seja, perceptualmente, se variarmos o comprimento de onda, sera que um observador padr~ao concluira que as luzes tem brilho constante? A resposta e n~ao. A resposta e maxima para comprimento de onda igual a 555 nm (faixa do verde). A gura 2.10 mostra a sensibilidade relativa do olho em func~ao do comprimento de onda. 400 700555 sensibili- dade relativa V( ) 1.0 (nm) Figura 2.10: Curva de Sensibilidade Relativa. Convencionou-se que uma luz monocromatica com comprimento de onda igual a 555 nm e com 1 watt de potência produz 680 lumens. A constante K() = 680 V () lm=w per- mite converter de watts para lumens. Note-se ent~ao que a luminância3 e uma grandeza 3 Luminância = lumens=(m2Sr). 22 CAPITULO 2. COR colorimetrica que corresponde aos termos perceptuais de brilho (para emissores) ou lumi- nosidade (para re etores). Se a luz n~ao for monocromatica, mas sim caracterizada por uma distribuic~ao espectral C(), tem-se que: L(C()) = K() Z 1 0 C() V () d: Isto pode ser expresso em func~ao da representac~ao de C no sistema CIE4 -RGB por L(C()) =< L; c >=< (0:177; 0:812; 0:0106); (cr ; cg; cb) > : 2.7 Padr~ao CIE-XYZ Para evitarem-se coordenadas de cromaticidade negativas (por que isto e importante?), foi criado um outro padr~ao de cor chamado de CIE-XYZ. As primarias deste sistema n~ao est~ao contidas no solido de cor justamente para que qualquer cor possa ser expressa, apenas com coordenadas positivas, como combinac~ao linear das cores primarias. A convers~ao do sistema CIE-RGB para o CIE-XYZ e uma mera mudanca de sistema de coordenadas. Como foi criado o sistema CIE-XYZ? De niu-se que duas cores primarias têm luminância zero (pertencem ao nucleo do operador de luminância). Traca-se ent~ao uma reta coincidente com o segmento (quase) retilneo do diagrama de cromaticidade. A intersec~ao desta reta com a reta de luminância zero (que passa pela origem e e perpendicular ao vetor (0:176; 0:81)) de ne a primaria X. As duas outras primarias cam de nidas pelo tracado de uma segunda reta que e tangente ao diagrama de cromaticidade pela esquerda e que minimiza a area do triângulo formado pela reta de luminância zero, a reta anterior e esta reta. A primaria Z esta na reta de luminância zero e a Y no terceiro vertice do triângulo ( g. 2.5). rgb x y z xyz r g b r 1.2750 -1.7395 -0.7431 x 0.73467 0.27376 0.16658 g -0.2779 2.7675 0.1409 y 0.26533 0.71741 0.00886 b 0.0029 -0.0280 1.6022 z 0.00000 0.00883 0.82456 Tabela 2.1: Bases do CIE (vetores coluna). Aqui talvez valha a pena reavivar a memoria daqueles que n~ao est~ao muito familiarizados com algebra linear. Considere-se o seguinte problema: obter as coordenadas do objeto da gura 2.11 no sistema de coordenadas b). 2.7.1 Mudanca de Sistema de Coordenadas Uma mudanca de sistema de coordenadas corresponde a uma transformac~ao linear. Desta forma, basta que seja determinado como a transformac~ao age nos vetores de uma base para que se tenha a transformac~ao correspondente. Assim se v = P aiei; ai 2 <, v,ei 2 <n (feig 4 Comission Internationale de Eclairage. 2.8. SISTEMAS DE COR 25 2.8 Sistemas de Cor Um sistema de cor e o espaco de cor mais um sistema de coordenadas nele de nido. Existem varios sistemas de cor. Uma classi cac~ao possvel e a seguinte:  Sistemas padr~ao;  Sistemas dos dispositivos;  Sistemas computacionais;  Sistemas de interface. 2.8.1 Sistemas Padr~ao Os sistemas padr~ao s~ao aqueles homologados por alguma instituic~ao normativa. Pode-se citar o sistema de cor CIE-RGB, criado em 1931, que xa uma base de primarias composta pelas cores monocromaticas de comprimento de onda 700 m(Red); 546 m(Green) e 435.8 m(Blue); o sistema CIE-CMY, que utiliza como primarias as cores complementares cia- no (azul-piscina), magenta (violeta) e amarelo para simular um sistema subtrativo de cor ( g. 2.12); e o sistema CIE-XYZ, cuja base de primarias, chamadas X, Y e Z, esta fora do espectro visvel. A principal nalidade de um sistema padr~ao e que, por ser independente de qualquer dispositivo fsico, possibilita a mudanca de coordenadas entre sistemas distintos e fornece uma maneira de armazenamento de imagens que independe de um dispositivo particular. 2.8.2 Sistemas dos Dispositivos Os sistemas dos dispositivos s~ao de nidos pelas bases de primarias dos dispositivos. O ga- mute de um dispositivo (o conjunto de cores realizaveis pelo dispositivo) e um triângulo contido no diagrama de cromaticidade (por que?). Os sistemas dos dispositivos têm uma importância intrnseca porque, em ultima analise, s~ao com eles que as imagens s~ao recons- trudas. O espaco de cor de um dispositivo e um subconjunto do solido de cor que, em geral, tem a forma de um paraleleppedo cujas faces s~ao paralelogramos. Quando se efetua a mudanca de coordenadas tem-se ent~ao um cubo ( g. 2.12). 2.8.3 Sistemas Computacionais Os sistemas computacionais s~ao sistemas utilizados tanto para sntese de imagens como no processamento de imagens. Podem ser, por exemplo, sistemas padr~ao, ou sistemas com alguma caracterstica propria, tal como utilizar uma base com mais de três primarias. 2.8.4 Sistemas de Interface Sistemas de cor baseados em espacos vetoriais s~ao praticos do ponto de vista computacional, mas s~ao muito ruins para serem usados na interface com o usuario. Os sistemas de interface objetivam oferecer uma interface adequada a especi cac~ao de cores por um usuario comum, 26 CAPITULO 2. COR G R B 1 1 1 Y M C branco preto Figura 2.12: Espaco de Cor de um Dispositivo (cubo RGB). sem qualquer conhecimento espec co a respeito de colorimetria. Alguns sistemas permitem escolher uma cor a partir de três parâmetros: tonalidade, saturac~ao e luminância.  tonalidade ou matiz (comprimento de onda dominante).  saturac~ao (pureza da cor).  brilho ou valor (luminância). A tonalidade varia quando se caminha angularmente no diagrama de cromaticidade e a saturac~ao quando se caminha radialmente. A saturac~ao tem a ver com a pureza da cor (o quanto ela contem de branco). As cores espectrais s~ao as cores consideradas puras. Consulte-se a gura 2.13. Existem dois metodos basicos para se criar um sistema de interface de cor:  por coordenadas: utilizam-se coordenadas (ex, HSV e HSL).  por amostras: discretiza-se o solido de cor criando-se um atlas de cor (ex, Pantone e Munsell). O sistema HSV (Hue, Saturation, Value), criado por Alvy Ray Smith, projeta o cubo RGB sobre o plano perpendicular a linha de luminância (a diagonal do cubo) x+y+ z = 3, conforme pode ser visto na gura 2.14. 2.8. SISTEMAS DE COR 27 brilho saturacao tonalidade tons branco cor pura cinzas preto tintas shades Figura 2.13: Paradigmas de Cor. x y z Figura 2.14: Projec~ao do Cubo RGB no plano x+y+z=3. Este sistema de coordenadas n~ao se baseia numa base de um espaco vetorial. Logo, a convers~ao do sistema HSV para o sistema RGB n~ao e dada por uma transformac~ao projetiva e consequentemente n~ao pode ser representada por uma matriz. A coordenada valor de uma cor c = (cr; cg; cb) e de nida como max(cr; cg; cb) ( g. 2.15). O sistema HSL (Hue, Lightness, Saturation) foi criado pela Tektronix e e muito pa- recido com o sistema HSV. Neste sistema o brilho e de nido por 1=2(max(cr ; cg; cb) min(cr; cg; cb)) (preto tem brilho 0 e branco brilho 1). O modelo geometrico do sistema HSL e um hexacone duplo. 30 CAPITULO 2. COR d) Diga como pode ser feita uma interpolac~ao entre duas cores no sistema HSV. 2.13 Dado um monitor com base de primarias com coordenadas de cromaticidade R(0.628, 0.346), G(0.268, 0.588) e B(0.150, 0.070). a) Mostre que a cor com coordenadas de cromaticidade (0.274, 0.717) n~ao pode ser exibida de modo preciso neste monitor. b) Qual a denominac~ao da cor do item anterior? 2.14 Considere o solido de cor de um dispositivo gra co e uma cor que n~ao pode ser representada acuradamente neste dispositivo. a) Quais s~ao os tipos de situac~ao que podem causar este problema. b) Proponha metodos de aproximar esta cor no dispositivo. c) Discuta os aspectos positivos e negativos de cada metodo proposto. 2.15 Calcule as coordenadas de cromaticidade de uma cor com coordenadas C = (r; g; b). 2.16 Dado que a mistura de duas cores, segundo as leis de Grassman, pode ser calculada pela adic~ao de suas coordenadas tricromaticas (X,Y,Z) e que os valores de cromaticidade (x; y; z) de uma cor s~ao x = X (X + Y + Z) ; y = Y (X + Y + Z) ; z = Z (X + Y + Z) ou X = xY y ; Y = Y ; Z = (1 x y)Y y ; determine as coordenadas de cromaticidade da mistura das três cores c1; c2; c3 dadas no sistema CIE-xyY, respectivamente, por (0.1,0.3,10.0), (0.35,0.2,10.0), (0.2,0.5,10.0). T1 = Y1 y1 ; T2 = Y2 y2 ; X1 = (x1T1; Y1; (1 x1 y1)T1); X2 = (x2T2; Y2; (1 x2 y2)T2): X12 = X1 +X2 = (x1T1 + x2T2; Y1 + Y 2; (1 x1 y1)T1 + (1 x2 y2)T2)) X12x +X12y +X12z = x1T1 + x2T2 + Y1 + Y2 + T1 x1T1 y1T1 + T2 x2T2 y2T2 = T1 + T2: (2.1) ) x12 = x1T1 + x2T2 T1 + T2 ; y12 = y1T1 + y2T2 T1 + T2 ; Y12 = Y1 + Y2: (2.2) 2.9. EXERCICIOS 31 x y x1 x12 x2 X1 X12 X2 Figura 2.17: Combinac~ao de Cores. 2.17 Dada uma cor c1 = (x1; y1; Y1) e o ponto acromatico a = (ax; ay; 1) derive a formula para calcular a cor c2 = (x2; y2; Y2) complementar de c1. c1 + c2 = a (2:2)) 8< : x1T1 + x2T2 = ax(T1 + T2); y1T1 + y2T2 = ay(T1 + T2); Y1 + Y2 = y1T1 + y2T2 = 1: (2.3) ay(T1 + T2) = 1) (T1 + T2) = 1 ay ) T2 = 1 ay T1: x2 = ax(T1 + T2) x1T1 T2 = ax ay x1T1 1 ay T1 ; y2 = ay(T1 + T2) y1T1 T2 = 1 y1T1 1 ay T1 ; Y2 = 1 Y1: (2.4) 2.18 O comprimento de onda dominante de uma cor c e obtido, calculando-se a intersec~ao da reta de nida pelas coordenadas de cromaticidade de c e do ponto acromatico com o bordo do diagrama de cromaticidade. Pela de nic~ao acima, alguns pontos contidos no diagrama de cromaticidade n~ao têm comprimento de onda dominante no espectro visvel. a) Por que? b) Proponha um esquema que permita representar o comprimento de onda dominante de um desses pontos, baseado no conceito de complementaridade. 2.19 Dados dois espacos tricromaticos de cor A e B com bases (A1; A2; A3) e (B1; B2; B3), respectivamente, e a matriz [aij ] de mudanca de base entre A e B. a) Mostre como calcular as coordenadas (c1; c2; c3) de uma cor c em A a partir de suas coordenadas em B. 32 CAPITULO 2. COR b) Sendo rBi() as func~oes de reconstruc~ao de cor associadas as primarias (B1; B2; B3), diga como podem-se obter as func~oes de reconstruc~ao de cor rAi() associadas as primarias (A1; A2; A3). c) Justi que os itens anteriores. 2.20 Considere o sistema de cor RGB do monitor (mRGB). a) Qual a geometria do solido de cor desse sistema? b) Faca um esboco do solido de cor. c) Considere as cores do sistema mRGB normalizadas para o interval0 [0; 1]. De na o sistema de cores complementares CMY , correspondentes as cores primarias do sistema mRGB. Mostre que C = 1R; M = 1G; Y = 1B: 3.2. CLASSIFICAC ~AO DOS DISPOSITIVOS 35 Figura 3.3: Formato Matricial. formato matricial ( g. 3.4 (a)). Essa tecnica, que constitui uma parte fundamental dos algoritmos de sntese de imagens, e estudada em detalhe no Captulo 10. A transformac~ao oposta, ou seja, de dados no formato matricial para o formato vetorial, e chamada de segmentac~ao e faz parte da area de Vis~ao Computacional. Essa convers~ao, em alguns casos, n~ao e bem de nida, sendo impossvel de ser realizada ( g. 3.4 (b)). (a) (b) Figura 3.4: Convers~ao entre Formatos. 3.2 Classi cac~ao dos Dispositivos Os dispositivos gra cos s~ao projetados usualmente de forma a privilegiar um dos formatos de dados descritos acima. Isso n~ao signi ca que um tipo de equipamento somente possa operar com um determinado formato de dados. Os dispositivos do tipo matricial podem, por exemplo, reproduzir segmentos de reta utilizando processos de rasterizac~ao. Alguns equipamentos deste tipo disp~oem ate mesmo de suporte em hardware para tal operac~ao. Embora n~ao seja t~ao comum, os dispositivos do tipo vetorial podem tambem reproduzir imagens utilizando padr~oes de linhas. Por exemplo, em mapas e desenhos tecnicos, varios tipos de hachuras s~ao empregados para diferenciar areas, simulando tonalidades de cinza. 36 CAPITULO 3. DISPOSITIVOS GRAFICOS A evoluc~ao dos equipamentos gra cos re ete, de uma certa forma, o desenvolvimento da computac~ao gra ca como um todo. Inicialmente, quando havia uma grande preocupac~ao com a modelagem geometrica, os dispositivos vetoriais eram mais populares. Depois, com a ênfase na sntese de imagens so sticadas, os equipamentos matriciais passaram a ser mais utilizados. Atualmente, a tendência e a busca de soluc~oes integradas, combinando dispositivos do tipo vetorial e matricial nas diversas fases do processo da computac~ao gra ca para atender classes espec cas de aplicac~oes. De um modo geral, os dispositivos vetoriais est~ao vinculados a especi cac~ao e manipulac~ao dos modelos geometricos, enquanto que os dispositivos matriciais est~ao relacionados com a exibic~ao e o processamento de imagens. Alem disso, varios fatores de natureza tecnica, industrial e econômica, determinaram a evoluc~ao dos equipamentos gra cos. Os dispositivos do tipo matricial necessitam do uso de muita memoria para armazenar a imagem. Por outro lado, os dispositivos do tipo vetorial se bene ciaram da tecnologia de radar, numa epoca em que o custo da memoria inviabilizava o uso de dispositivos de formato matricial (decada de 60 e 70). Ja os dispositivos do tipo matricial foram impulsionados na decada de 80 por dois fatores: a queda do preco de memoria, e a revoluc~ao nas comunicac~oes que a televis~ao provocou (neste captulo sera visto que os dispositivos de sada gra ca mais comuns utilizam o formato matricial e se baseiam na tecnologia de monitores de televis~ao). Os avancos recentes nas areas da supercomputac~ao e da computac~ao paralela têm tido um impacto signi cativo nos dispositivos de processamento gra co. 3.2.1 Criterios de Classi cac~ao No estudo dos dispositivos gra cos e necessario criar abstrac~oes das suas caractersticas operacionais, de modo que o vnculo entre programas e equipamentos n~ao se transforme num fator de dependência. Varios aspectos contribuem para o estabelecimento de criterios para uma classi cac~ao dos equipamentos gra cos. Nessa analise ha categorias de equipamentos estruturadas, hierarquicamente, segundo dois pontos de vista: o funcional, e o do formato dos dados gra cos. Em relac~ao ao criterio funcional, dividem-se os dispositivos gra cos em:  equipamentos de entrada;  equipamentos de processamento;  equipamentos de sada. Quanto ao formato de dados os dispositivos gra cos se dividem em equipamentos do tipo vetorial e do tipo matricial. O diagrama da gura 3.5 mostra como essas classi cac~oes se relacionam. 3.3 Equipamentos de Entrada Gra ca. Os equipamentos de entrada de dados gra cos s~ao equipamentos de captac~ao de informac~oes gra cas. Do ponto de vista do formato da imagem, os dispositivos podem ser classi cados como vetoriais e matriciais. 3.3. EQUIPAMENTOS DE ENTRADA GRAFICA. 37 Graphics Devices Input Process Output Vector Matrix Vector Matrix Hybrid Vector Matrix Figura 3.5: Classi cac~ao dos Equipamentos. Os dispositivos de entrada vetorial s~ao em sua maioria utilizados como componentes de estac~oes gra cas interativas. Um exemplo tpico e o \mouse", componente indispensavel em uma estac~ao de trabalho interativa que utilize ambiente de janelas. Os dispositivos de entrada matricial s~ao tradicionalmente utilizados de modo n~ao-interativo, devido, principalmente, ao grande volume de dados que devem ser manipulados. Esta si- tuac~ao tende a se modi car com a evoluc~ao dos equipamentos de aquisic~ao, exibic~ao e pro- cessamento de imagens, que poder~ao tornar possvel aplicac~oes em tempo real envolvendo dados matriciais. 3.3.1 Dispositivos de Entrada Vetorial Os dispositivos cujo sistema de coordenadas e absoluto s~ao: a \light pen", a \tablet", o \touch pannel", e o \3D-digitizer". As caractersticas tecnicas relevantes dos dispositivos de entrada vetorial absolutos s~ao a sua resoluc~ao, linearidade, repetibilidade, e area de ac~ao. A light pen e um dispositivo bidimensional que funciona necessariamente acoplado a um terminal de vdeo. Este equipamento e composto por uma caneta com uma foto-celula na ponta ligada ao circuito de vdeo do terminal. Dessa maneira, e possvel detectar pontos apresentados na tela e consequentemente sua localizac~ao. Este dispositivo surgiu com os primeiros equipamentos gra cos interativos. Atualmente ele caiu em desuso devido a alguns problemas tecnicos apresentados. O touch pannel tambem e um dispositivo bidimensional de entrada que deve ser integra- do a um terminal de vdeo. Ele consiste em uma tela transparente, sensvel ao toque, que e sobreposta a tela do terminal. Este dispositivo apresenta severas limitac~oes em termos de resoluc~ao. Por este motivo, ele e indicado apenas para a selec~ao de objetos gra cos apre- sentados na tela. Um exemplo desse tipo de utilizac~ao pode ser visto em alguns terminais eletrônicos de banco. A tablet ou mesa digitalizadora consiste em uma base plana e um instrumento indicador em forma de caneta ou bloco. No indicador existem um ou mais bot~oes. O equipamento 40 CAPITULO 3. DISPOSITIVOS GRAFICOS 3.4.1 Dispositivos de Processamento Vetorial Os dispositivos do tipo vetorial se destinam principalmente ao processamento de mode- los geometricos. Eles atuam portanto sobre as coordenadas das diversas componentes dos modelos, tais como segmentos de reta, polgonos, e etc. Em func~ao do numero de proces- sadores, podem-se ter dispositivos do tipo SISD (single-instruction, single data stream), ou MISD (multiple-instruction, single data stream). Os dispositivos do tipo SISD s~ao uniprocessadores que possuem instruc~oes especiais para processamento de dados geometricos, do tipo multiplicac~ao de matrizes por vetores. Os dispositivos do tipo MISD s~ao pipelines compostas de varios processadores organiza- dos sequencialmente. O processamento gra co e dividido em etapas, onde cada processador e especializado numa classe de operac~oes gra cas, como projec~ao, recorte, etc. 3.4.2 Dispositivos de Processamento Matricial Os dispositivos do tipo matricial s~ao equipamentos multiprocessadores utilizados para o processamento de imagens, para a rasterizac~ao (Captulo 10) e outros algoritmos gra cos paralelizaveis. Ha os dispositivos do tipo SIMD (single-instruction, multiple data stream), ou MIMD (multiple-instruction, multiple data stream) com diferentes con gurac~oes dos processadores. Os dispositivos do tipo SIMD s~ao utilizados para realizar a mesma operac~ao em varios elementos simultaneamente. Um exemplo desse tipo de equipamento e o computador de imagem Pixar. Os dispositivos do tipo SIMD s~ao processadores paralelos que se comunicam entre si. A maneira como eles est~ao interligados de ne uma topologia de rede e, consequentemente, o uxo de dados. Um equipamento desse tipo e a estac~ao gra ca Pixel Machine. 3.5 Equipamentos de Sada Gra ca Os equipamentos de sada gra ca s~ao equipamentos que permitem a visualizac~ao de dados gra cos. Podem ser subdivididos em dispositivos vetoriais ou matriciais, de acordo com o tipo de dado gra co por eles manipulado. Dentre todos os equipamentos gra cos de sada, os dispositivos de exibic~ao de vdeo s~ao, sem duvida alguma, os mais importantes e mais comuns. A tecnologia de vdeo implica em uma serie de caractersticas comuns aos equipamentos vetoriais e matriciais. Por esse motivo, inicia-se esta sec~ao analisando a estrutura basica dos dispositivos de exibic~ao de vdeo. Em seguida discutem-se os detalhes espec cos dos diversos tipos de equipamentos de vdeo no contexto dos dispositivos vetoriais e matriciais. 3.5.1 Dispositivos de Exibic~ao de Vdeo Um dispositivo de exibic~ao de vdeo e constitudo por quatro elementos: um monitor, um controlador de vdeo, uma memoria de exibic~ao (\frame bu er") e um conversor digital analogico ( g. 3.6). 3.5. EQUIPAMENTOS DE SAIDA GRAFICA 41 CPU BUS Memory Frame Buffer Video Controler Monitor Perifericos (a) endereco linear end. x end. y inicia ou incrementa inicia ou decrementa sinal de deflexao raster. CONTROLADOR DE VIDEO valor do pixel cor ou luminancia conversor D/A sinal de video F R A M E B U F F E R CONVERSOR D/A (b) Figura 3.6: Dispositivo de Vdeo. O monitor de vdeo ( g. 3.7) consiste em um tubo de raios catodicos com uma tela e um canh~ao que produz um ou mais feixes de eletrons controlado por um sistema de focalizac~ao e explorac~ao. Em cada ponto da tela se colocam uma ou mais camadas de fosforo, de modo que, ao atingir um desses pontos, o feixe de eletrons provoca a emiss~ao de radiac~ao eletromagnetica na faixa visvel do espectro. O funcionamento basico de qualquer monitor de vdeo e bastante similar ao funcionamento de um monitor de televis~ao. No sistema NTSC1 e PAL-M2 existem 525 linhas (483 visveis) e 644 pixels por linha (raz~ao de aspecto 4:3). Monitores para aplicac~oes gra cas, no entanto, costumam ter uma resoluc~ao muito maior, algo em torno de 1024  1024 pontos enderecaveis. O espaco de cor do monitor de vdeo depende do numero de camadas de fosforo em cada ponto. Os monitores monocromaticos, ou de dois nveis (bitmapped), utilizam uma unica camada de um fosforo que e sensibilizado com voltagem mnima ou maxima; os monitores que permitem a exibic~ao de tons de cinza (gray scale) utilizam uma unica camada de fosforo cuja sensibilidade produz uma radiac~ao com a luminância proporcional a voltagem aplicada 1 National Television System Cometee. 2 Phase Alternating Lines. 42 CAPITULO 3. DISPOSITIVOS GRAFICOS ao feixe de eletrons do canh~ao. O espaco tricromatico de cor e implementado por meio de três tipos de fosforo diferentes em cada ponto (e três feixes de eletrons), de modo que cada fosforo emite uma das cores primarias do sistema. A distância entre os centros dos pontos R, G e B de ne o pitch do tubo, que varia de 0.60 mm num monitor de televis~ao ate 0.21 mm em monitores de alta resoluc~ao. Uma mascara metalica perfurada colocada a frente da camada de fosforo garante que cada feixe de eletrons atinge e excita apenas o ponto correspondente ao tipo correto de fosforo. catodo amplificador de deflexao vertical grade de foco amplificador de deflexao horizontal feixe defletido feixe de eletrons (-) anodo (+) cobertura metalica (+) 15 a 20000 V luz visivel cobertura de fosforo (-) Figura 3.7: Monitor de Vdeo. Como a resposta luminosa do fosforo utilizado na tela decai exponencialmente com o tempo, a imagem precisa ser redesenhada periodicamente. O numero de vezes por segundo que a imagem deve ser exibida na tela para que seja percebida como um fenômeno contnuo no tempo, e chamado de frequencia crtica de fus~ao. Este numero e determinado por varios fatores, desde a persistência do fosforo, ate a aspectos psico siologicos. Em media ele se situa proximo dos 50 Hz. O controlador de vdeo, tambem chamado de DPU (Display Processing Unit), tem a nalidade de controlar o movimento de explorac~ao na tela do feixe de eletrons, para que a imagem desejada seja produzida. Esse processo, denominado de varredura, pode ser aleatorio ou regular. Na varredura aleatoria, o feixe se desloca numa trajetoria que segue o desenho das curvas da imagem. Na varredura regular, o feixe se movimenta de acordo com um padr~ao xo que percorre toda a tela da esquerda para a direita e de cima para baixo, cobrindo-a por linhas horizontais. Este padr~ao regular e chamado de raster. A gura 3.8 ilustra os dois padr~oes utilizados. Os dispositivos de exibic~ao vetorial empregam a varredura 3.5. EQUIPAMENTOS DE SAIDA GRAFICA 45 manter a imagem visvel na tela. 3.5.2 Dispositivos de Sada Vetorial Os dispositivos de sada vetorial produzem imagens tracando segmentos de reta descritos pelas coordenadas de seus pontos iniciais e nais. Nesta categoria de equipamentos est~ao: o display caligra co, o display de armazenamento, e as tracadoras. O display caligra co e um dispositivo de exibic~ao de vdeo interativo. O sistema de varredura e aleatorio e o fosforo do monitor e de baixa persistência e distribudo de for- ma contnua sobre a tela, ou seja, o feixe de eletrons se movimenta livremente sobre a tela e a imagem precisa ser regenerada constantemente. Essas caractersticas permitem a manipulac~ao dos dados em tempo real ( g. 3.10). M x,y D x,y ControllerDisplay List Figura 3.10: Display Caligra co. O display de armazenamento ou DVST (Direct View Storage Tube) disp~oe de um mo- nitor de vdeo com fosforo de alta persistência (cerca de uma hora no maximo). Nesse equipamento a imagem tracada e mantida na tela atraves de um circuito especial, sem ne- cessidade de regenerac~ao. Uma desvantagem desse tipo de monitor e que partes da imagem n~ao podem ser modi cadas sem que a imagem inteira seja apagada (o que leva cerca de um segundo) e redesenhada. Esses monitores têm uma importância historica em Computac~ao Gra ca: devido ao baixo custo, pelo fato de n~ao necessitarem de uma memoria de exibic~ao, eles deram incio a grande expans~ao das aplicac~oes da Computac~ao Gra ca nas diversas areas 3. As tracadoras s~ao equipamentos eletromecânicos para o desenho de linhas sobre papel ou lme. Esse equipamento e constitudo por um suporte para a super ce de desenho, e um mecanismo de controle do instrumento de tracado. Quanto ao suporte, as tracadoras podem ser de mesa ou de tambor. Quanto ao mecanismo de desenho, podem ser do tipo contnuo ou incremental. 3A importância desse tipo de display pode ser avaliada pelo seguinte fato. Esse foi o criterio escolhido pela SIGGRAPH para de nir quem pode pertencer ao grupo dos Pioneiros da Computac~ao Gra ca. A pessoa deve ter trabalhado na area antes do aparecimento do primeiro display DVST da Tektronix 46 CAPITULO 3. DISPOSITIVOS GRAFICOS 3.5.3 Dispositivos de Sada Matricial Os dispositivos de sada matricial produzem imagens a partir de uma matriz de intensidades. Nesta categoria de equipamentos est~ao: o display raster, o painel de plasma, o display de cristal liqudo, as impressoras de impacto, as impressoras gra cas, e o lm recorder. O display raster e um dispositivo de exibic~ao de vdeo matricial. Ele consiste em um monitor, um controlador de vdeo e uma memoria de display que armazena a matriz de ima- gem. Esse equipamento normalmente disp~oe de uma \look up table" ( g. 3.11). Projetores de vdeo tambem podem ser utilizados nos displays raster em substituic~ao aos monitores. LUTFrame Buffer Figura 3.11: Display Raster. O painel de plasma e constitudo por uma matriz de celulas microscopicas de neon. Ele e um display monocromatico, bitmap de armazenamento, n~ao precisando portanto de memoria adicional nem de regenerac~ao da imagem. O display de cristal liqudo e semelhante ao painel de plasma, mas utiliza celulas de cristal lquido na matriz de imagem. Essa tecnologia tem um grande potencial, por permitir displays coloridos e monitores com tela plana. As impressoras de impacto s~ao destinadas principalmente para sada alfa-numerica. Al- gumas delas, do tipo \dot matrix", têm capacidade gra ca. Possuem cabecas com um conjunto que contem de sete a vinte e quatro pinos (7, 9, 18 ou 24) que s~ao impulsionados contra uma ta impregnada de tinta sobre o papel. As impressoras gra cas podem utilizar uma tecnica de reproduc~ao a laser, eletrostatica, termica, ou por jato de tinta. As impressoras laser utilizam um raio de laser para sensibilizar os pontos que n~ao aparecem na imagem (permanecem brancos), retirando a carga de um ponto (tornando-o negativo) sobre um cilindro rotativo de selênio | que e um material foto-sensvel | carregado positivamente. Partculas de toner (carregado negativamente) s~ao atradas para a superfcie do cilindro e, em seguida, transferidas para o papel ( g. 3.12). As impressoras eletrostaticas carregam negativamente os pontos do papel | por meio de um pente com contatos eletricos | que devem receber tinta. E utilizado um toner carregado positivamente. As impressoras termicas transferem seletivamente pigmentos de tinta para o papel por calor. As impressoras da jato de tinta possuem uma cabeca de impress~ao que lanca gotculas de tinta no papel por meio de pequenos jatos. As impressoras gra cas podem ser monocromaticas ou coloridas. 3.6. ESTAC ~OES GRAFICAS INTERATIVAS 47 papel Laser (-) espelho lente toner (-) cilindro de selenium + fuser Figura 3.12: Impressora a Laser. O \ lm recorder" registra em pelcula fotogra ca imagens geradas por computador. Para reproduzir a cor, o lme e exposto três vezes, atraves de ltros, para as componentes de cor azul, verde e vermelha. 3.6 Estac~oes Gra cas Interativas As estac~oes gra cas combinam dispositivos gra cos de entrada, sada e processamento em um sistema destinado ao uso interativo. Nesta sec~ao descrevem-se os tipos mais comuns de estac~oes gra cas, que podem ser classi cadas em estac~oes caligra cas e estac~oes matriciais. Estas, por sua vez, se divididem em estac~oes de baixa e alta performance. Alem destas, existem estac~oes com uma arquitetura dedicada para aplicac~oes espec cas, tais como o processamento de imagens em tempo real e a visualizac~ao de dados volumetricos. As estac~oes caligra cas s~ao constitudas por um monitor de exibic~ao de vdeo do tipo caligra co, um processador de display e varios dispositivos de entrada, tais como teclado, mesa digitalizadora e dials. Um exemplo classico desse tipo de equipamento s~ao as estac~oes da serie PS-300 produzidas pela Evans & Sutherland ( g. 3.13). Graphics Processor Display Processing Unit Keyboard Tablet Dials Monitor HOST Figura 3.13: Estac~ao Caligra ca. As estac~oes gra cas de baixa performance integram um computador de uso geral com um 50 CAPITULO 3. DISPOSITIVOS GRAFICOS Captulo 4 Imagem A imagem digital e a materializac~ao de grande parte dos processos de Computac~ao Gra ca, servindo como elo de ligac~ao entre o usuario e esses processos, evidenciando, desta forma, os seus resultados. E valido a rmar-se que a imagem esta presente em todas as areas da Computac~ao Gra ca, seja como produto nal, como no caso da visualizac~ao, ou como parte essencial do processo de interac~ao, no caso da Modelagem. Por este motivo, e de fundamen- tal importância a perfeita compreens~ao do signi cado da imagem nos diversos contextos. Neste captulo vai-se desenvolver uma conceitualizac~ao da imagem digital, apresentando-se modelos abstratos para uma imagem e diversas formas de representac~ao. Aqui, mais uma vez, o paradigma dos quatro universos e bastante apropriado para obter-se um perfeito entendimento dos diversos modelos de imagem que v~ao-se estudar ( g. 4.1). Imagem Modelo Continuo Representacao Matricial Imagem Digital Figura 4.1: Modelo Conceitual. 4.1 Modelo de Imagem Uma imagem e o resultado de estmulos luminosos associados a um suporte bidimensional que corresponde a superfcie (curva) da retina do olho humano. Essa e a forma de percepc~ao do universo fsico no qual habitamos atraves da vis~ao, um sentido que processa imagens, sejam elas o resultado de um processo intermediado, como por exemplo uma fotogra a, ou o resultado de um processo de projec~ao do mundo tridimensional diretamente na retina. Para representar e manipular imagens no computador, devem-se de nir modelos ma- tematicos adequados a esses objetivos. Uma imagem pode ser de nida como uma aplicac~ao  : U  <2 !   <3 51 52 CAPITULO 4. IMAGEM de um subconjunto do plano (um retângulo, na pratica) em um espaco de cor. Com um espaco de cor de dimens~ao 1, o gra co da func~ao imagem e o conjunto dos pontos do R3 dado abaixo: G() = f(x; y; z); (x; y) 2 U; z = (x; y)g Esta de nic~ao, embora pareca um tanto abstrata, capta com precis~ao a noc~ao de que uma imagem e de nida pelas cores dos seus pontos. O espaco de cor e identi cado com o <3 se for usado um espaco perceptual de cor de dimens~ao 3. Assim, cada ponto da imagem tem a sua cor de nida por uma tripla de numeros reais. Uma fotogra a e um exemplo de uma imagem contnua, no sentido de que assume va- lores em todos os pontos do domnio1. Um problema no armazenamento da imagem no computador e que ela possui um numero in nito de pontos. Novamente, deve-se obter uma representac~ao nita por um processo de discretizac~ao. 4.2 Discretizac~ao O processo de discretizac~ao produz uma imagem discreta, a partir de um numero nito de amostras colhidas da imagem contnua. Isto signi ca que a func~ao  e amostrada num subconjunto discreto U 0  U : U = [a; b] [c; d] = f(x; y) 2 <2; x 2 [a; b]; y 2 [c; d]g; U 0 = f(xi; yj) 2 U ; xi = i
x; yj = j
y; i; j 2 Z;
x;
y 2 <:g Para codi car uma imagem, em geral, discretiza-se, tambem, o espaco de cor, para que a informac~ao de cor possa ser armazenada com um numero nito de bits. A discretizac~ao do espaco de cor e chamada de quantizac~ao. A rigor, quando se trabalha com numeros em ponto utuante, signi ca que ja foi feita uma quantizac~ao, no entanto, ignora-se esse fato. Uma imagem digital e uma imagem discretizada no domnio espacial e no espaco de cor ( g. 4.2). 4.3 Representac~ao Matricial Uma imagem digital pode utilizar a representac~ao matricial. Considerando que o domnio espacial de uma imagem e um retângulo, pode-se xar um par de eixos ortogonais, paralelos aos lados do retângulo. Cada um desses eixos e particionado uniformemente em celulas de comprimento
x e
y, respectivamente. Ao se fazer o produto cartesiano das celulas correspondentes, obtem-se um reticulado. Cada celula (i; j) deste reticulado e chamada de pixel ( g. 4.3). A representac~ao matricial utiliza uma matriz Amn, onde m e a resoluc~ao vertical e n a resoluc~ao horizontal da imagem. O produto m  n do numero de pixels em cada dimens~ao da imagem e chamado de resoluc~ao espacial da imagem. A densidade de resoluc~ao e o numero de pixels por unidade de comprimento e a resoluc~ao de cor e o numero de bits usados para armazenar uma componente de cor do pixel. Com m bits e possvel codi car 23m cores. 1 Isto n~ao quer dizer que a func~ao  e contnua. Em geral, ela n~ao e. 4.5. QUANTIZAC ~AO 55 c1 c2 c3 c4 S S 1 2 Niveis de Quantizacao Celulas de Quantizacao (2 conjuntos)m Figura 4.4: Celulas de Quantizac~ao.  metodos adaptativos (levam em conta a distribuic~ao das cores na imagem). Neste texto, v~ao-se considerar dois algoritmos de quantizac~ao: o algoritmo por populo- sidade e o algoritmo do corte mediano. 4.5.1 O Algoritmo de Populosidade O algoritmo por populosidade baseia-se no histograma de frequência das cores na imagem. No eixo das abcissas est~ao as cores e no eixo das ordenadas e indicado quantos pixels possuem aquela cor ( g. 4.5). Dado o numero de nveis de quantizac~ao, s~ao escolhidas as cores mais frequentes. As celulas de quantizac~ao s~ao determinadas, ent~ao, a partir de alguma metrica. Se for utilizada a metrica Euclideana, as celulas podem ser determinadas com a construc~ao do diagrama de Voronoi. Uma observac~ao importante e que o algoritmo de populosiade ignora completamente as cores com baixa populosidade. Frequencia Corc1 c2 cn f1 f2 f3 Figura 4.5: Histograma de Frequência. 56 CAPITULO 4. IMAGEM 4.5.2 O Algoritmo do Corte Mediano O algoritmo do corte mediano, criado por Paul Heckbert em 1982, determina, em primeiro lugar, as celulas de quantizac~ao. O objetivo do algoritmo e que cada celula de quantizac~ao possua mais ou menos o mesmo numero de cores da imagem. O primeiro passo e determinar o menor retângulo no espaco de cor (bounding box) que engloba todas as cores da imagem. Em seguida ele ordena as cores usando como chave a componente (r; g ou b) que corresponde ao eixo coordenado paralelo a maior dimens~ao do retângulo. Por m ele calcula a mediana deste conjunto ordenado levando em conta o histograma de frequência das cores. Por de nic~ao a mediana de um conjunto ordenado " = f1  2  :::  n1  ng e:  n impar: (n+1 2 );  n par: ((n 2 ) + (n 2 +1))=2. Feito isto, corta-se o retângulo por um plano que contem a mediana do conjunto de cores e e perpendicular ao eixo coordenado escolhido. Este processo e repetido ent~ao, recursivamente, para cada sub-retângulo resultante, ate que se atinja o numero de celulas de quantizac~ao desejado. Os nveis de quantizac~ao podem ser escolhidos, por exemplo, tomando-se a media das cores de cada celula de quantizac~ao. O algoritmo do corte mediano e o melhor algoritmo de quantizac~ao para 8 bits conhecido. A implementac~ao e ciente do algoritmo necessita de uma estrutura de dados espaciais adequada ao processo de subdivis~ao recursiva do espaco. 4.6 Dithering Dithering e um processo de ltragem para minimizar a percepc~ao dos contornos de quan- tizac~ao. Em certos casos, mesmo utilizando-se bons algoritmos de quantizac~ao ca difcil n~ao perceber os contornos de quantizac~ao, por exemplo, na quantizac~ao para dois nveis. Em geral, quando se faz uma quantizac~ao comete-se um erro. Os contornos de quanti- zac~ao surgem devido a forte correlac~ao entre a cor de um pixel e a cor dos seus vizinhos. Geometricamente trata-se de uma curva conexa, o que acarreta que a passagem entre os diferentes nveis de quantizac~ao seja perceptvel. O objetivo de um algoritmo de dithering e descorrelacionar o erro de quantizac~ao. O erro torna-se crtico quando a quantizac~ao e para 1 bit apenas. Neste caso, existem somente duas celulas de quantizac~ao, que correspondem a dois nveis de quantizac~ao, conforme pode ser visto na gura 4.6. 4.6.1 Por que Funciona? O sistema visual humano integra (soma) os estmulos luminosos recebidos dentro de um certo ângulo solido. Assim e possvel perceberem-se intensidades que n~ao existem individu- almente. Na realidade, o que e importante e o meio tom em uma regi~ao e n~ao os tons dos pixels individualmente. 4.6. DITHERING 57 c1 c2 C1 C2 Figura 4.6: Quantizac~ao de 1 bit. O ângulo de vis~ao humano e de 150Æ na horizontal e 120Æ na vertical e a acuidade mnima e de 1=60Æ = 10. A percepc~ao de detalhes depende ent~ao de três fatores:  distância da imagem ao olho;  densidade de resoluc~ao da imagem;  abertura do olho. 4.6.2 Classi cac~ao dos Algoritmos Os algoritmos de meio tom para industria gra ca datam do incio do seculo. O metodo utiliza um processo fotogra co tradicional. A imagem e refotografada com uma retcula sobreposta. Regi~oes de alta luminância (claras) geram pontos pequenos enquanto regi~oes de baixa luminância (escuras) geram pontos grandes que se superp~oem. Os algoritmos de dithering devem preservar as altas frequências, que correspondem aos contornos das areas de interesse, e substituir as baixas frequências, que correspondem as texturas presentes no interior das areas, por outras perceptualmente equivalentes. A classi cac~ao dos algoritmos e feita utilizando padr~oes produzidos em areas de intensi- dade constante. De acordo com a regularidade dos padr~oes, estes podem ser periodicos ou aperiodicos e de acordo com a estrutura podem estar aglomerados ou dispersos.  periodicos: processos determinsticos que usam grades de amostras regulares.  aperiodicos: minimizam o erro distribuindo-o globalmente.  dispersos: criam os tons de cinza com pontos individuais uniformemente distribudos (indicado para dispositivos com controle preciso, ex. monitores de vdeo).  aglomerados: concentram os pontos em pequenos grupos de mesmo valor (indicado para dispositivos sem controle preciso, ex. impressoras). 4.6.3 Dithering com Modulac~ao Aleatoria O algoritmo de dithering com modulac~ao aleatoria aplica uma pequena perturbac~ao ale- atoria, uniformemente distribuda no intervalo das intensidades, ao valor de uma cor c antes de quantiza-la: 60 CAPITULO 4. IMAGEM bons resultados. Isto signi ca que o dispositivo de exibic~ao deve ter uma resoluc~ao entre 150  8 = 1200 dpi3 e 150  10 = 1500 dpi. 4.6.7 Algoritmo de Dithering Aperiodico O algoritmo de Floyd-Steinberg procura dispersar o erro de quantizac~ao, ocorrido em um pixel, para os pixels vizinhos ( g. 4.9). Q(i,j) = (f(i,j)>0.5); erro = Q(i,j) - f(i,j); f(i+1,j) += erro*3/8; f(i,j+1) += erro*3/8; f(i+1,j+1) += erro*1/4; Como consequência do modo com que o erro e propagado, surge um contorno de quantizac~ao que se propaga na direc~ao da diagonal da imagem. (i,j) (i+1,j) (i,j+1) (i+1,j+1) Figura 4.9: Algoritmo de Floyd-Steinberg. Em geral, os algoritmos de dithering eliminam as altas frequências presentes na imagem, como consequência do descorrelacionamento do erro. Este problema pode ser atenuado, usando-se um ltro de passa alta, para realcar as altas frequências, antes de empregar-se o algoritmo de dithering4. 4.7 Codi cac~ao de Imagem A codi cac~ao e o terceiro nvel de abstrac~ao de uma imagem, conforme o modelo concei- tual apresentado no incio deste captulo ( g. 4.1). Na codi cac~ao a representac~ao discreta da imagem e quantizada e a imagem digital resultante e transformada em um conjunto de smbolos organizados segundo uma estrutura de dados. A codi cac~ao pode ser feita utilizan- do um numero de bits constante para codi car cada parte da imagem, sendo chamada neste caso de codi cac~ao uniforme, ou pode se valer da probabiliade de ocorrência dos diferentes 3 Dots per inch. 4 A traduc~ao de dithering seria exitac~ao. 4.8. EXERCICIOS 61 nveis de quantizac~ao e utilizar um numero de bits variavel de acordo com a distribuic~ao de probalidade de ocorrência destes nveis. Neste caso, a codi cac~ao e dita adaptativa. Para se conseguir uma reduc~ao no espaco necessario ao armazenamento de uma imagem, costumam-se utilizar metodos de compress~ao de imagens. Isto e possvel porque as imagens tendem a apresentar um alto grau de coerência, que se traduz em uma redundância de informac~ao quando codi cada. Existem metodos de compress~ao reversveis e irreversveis, dependendo da possibilidade de recuperac~ao exata da imagem ou n~ao (com ou sem perda de informac~ao). Quando utilizar um ou outro metodo ira depender da natureza da aplicac~ao, que pode ser objetiva ou subjetiva. Os metodos de compress~ao podem ser classi cados em metodos espaciais, por transfor- mada ou por modelo. Os metodos espaciais utilizam diretamente a representac~ao espacial da imagem para fazer a compress~ao, por exemplo, o metodo conhecido como Run-length Encoding. Nos metodos por transformada, a compress~ao e feita com base em uma representac~ao n~ao espacial da imagem (por exemplo, representac~ao espectral). Como exemplos citam-se os metodos baseados em transformadas de Fourier, Cosseno ou de Hadamard. Nos metodos de compress~ao por modelo utiliza-se um modelo da imagem para obter-se a compress~ao. Como exemplo, cita-se a compress~ao por fractais. Existem, na pratica, diversos padr~oes (a maioria padr~oes de fato) para armazenamento de imagens. Cada padr~ao costuma utilizar algum metodo de compress~ao, alguns suportam true-color, outros s~ao mais adequados ao armazenamento de sequências animadas, etc. Os mais famosos s~ao os padr~oes GIF (Graphics Interface Format), TIFF (Tagged Image File Format), JPEG (Joint Photograph Expert Group), MPEG (Motion Photograph Expert Group), SUN-raster le, Encapsulated PostScript. 4.8 Exerccios 4.1 De na e explique a correc~ao gama. 4.2 De na quantizac~ao de uma imagem. 4.3 Discuta o problema de um sistema de cor para armazenamento de imagens. 4.4 Considere o algoritmo de populosidade para quantizac~ao de cor. a) Qual o procedimento de ordenac~ao mais adequado ao algoritmo? b) Em que condic~oes o algoritmo apresenta resultados insatisfatorios? c) Escreva um pseudo-codigo para o algoritmo. d) Faca uma analise da complexidade do algoritmo. 4.5 O metodo de quantizac~ao por subdivis~ao do espaco obtem as celulas de quantizac~ao pelo particionamento recursivo do volume de cor. Em cada iterac~ao, este e dividido em dois sub-volumes por um hiperplano ortogonal a uma das direc~oes principais do espaco. 62 CAPITULO 4. IMAGEM a) Qual o criterio utilizado pelo algoritmo do corte mediano para escolher a direc~ao e o ponto de subdivis~ao? b) Qual a raz~ao desta escolha? c) Sugira um outro criterio de subdivis~ao. 4.6 Considere o conjunto de cores, e a tabela de frequência dessas cores numa imagem digital, mostrado na gura 4.10. Obtenha a quantizac~ao da imagem para quatro nveis. a) Determine a func~ao de quantizac~ao para o algoritmo de populosidade. b) Esboce as celulas de quantizac~ao pelo algoritmo do corte mediano. C6 C3 C1 C9 C8 C2 C4 C5 C7 Cor Freq 2 3 2 1 2 1 1 1 2 C1 C2 C3 C4 C5 C6 C7 C8 C9 Figura 4.10: Conjunto de Cores e Tabela de Frequência. 4.7 Considere-se a imagem de uma esfera metalica com a re ex~ao especular de uma fonte de luz pontual (\highlight"). a) O que pode ocorrer com esse highlight se for feita uma quantizac~ao da imagem por populosidade. b) Que modi cac~ao pode ser feita no algoritmo de populosidade para minimizar o problema levantado no item anterior? 4.8 Como transformar uma imagem digital colorida em uma imagem em preto e branco (ou seja, \descolorizar" a imagem)? Captulo 5 Geometria As transformac~oes Geometricas ocupam uma posic~ao de destaque em Computac~ao Gra ca. Elas permitem o reposicionamento de objetos no espaco, favorecendo o agrupamento desses objetos e a gerac~ao de famlias de modelos a partir de um modelo basico. Os objetos geometricos representados por estes modelos podem ser transformados aplicando-se uma transformac~ao geometrica a um numero nito de pontos, por exemplo, nos vertices de curvas poligonais ou de polgonos de controle de curvas algebricas por partes. Espacos Geometria Relacoes Operacoes Figura 5.1: Modelo Conceitual. As transformac~oes geometricas que podem ser aplicadas a um objeto s~ao induzidas pelo tipo de geometria adotado e a pergunta a ser respondida e: qual o tipo de geometria mais adequado as necessidades da Computac~ao Gra ca? 5.1 Geometria Euclideana Uma geometria pode ser de nida de forma sintetica, a partir de axiomas e teoremas, ou por coordenadas, como e feito em Algebra Linear. No caso da Geometria Euclideana, por exemplo, pode-se constru-la a partir de um espaco vetorial (<3) munido de produto interno: < x; y >= P3 i=1 xiyi; os comprimentos s~ao dados pela norma Euclideana kxk = p< x; x >. Sera que a Geometria Euclideana | com o seu postulado basico que diz que dado um ponto p e uma reta r existe uma unica reta paralela a r que passa pelo ponto p | e a mais adequada? Se n~ao, como nega-la? Basicamente existem duas formas: dizer que existe uma in nidade de retas paralelas (Geometria Hiperbolica) ou dizer que n~ao existe paralelismo (Geometria Projetiva). 65 66 CAPITULO 5. GEOMETRIA Neste captulo vai ser visto que, embora seja natural de nir os objetos no espaco Eucli- deano, a geometria projetiva e a mais adequada para a computac~ao gra ca, pois estende a geometria Euclideana com uma serie de vantagens. 5.2 Transformac~oes Lineares Neste texto, entenda-se por transformac~ao n-dimensional uma aplicac~ao invertvel T : U  <n ! <n: Os modelos poligonais e poliedrais s~ao comuns em Computac~ao Gra ca, pois podem ser exibidos em qualquer dispositivo gra co e, assim, uma classe importante de transformac~oes e formada por aquelas que preservam estruturas lineares. Estas transfor- mac~oes s~ao conhecidas como transformac~oes lineares em <n, ou operadores lineares, e se caracterizam por transformarem retas em retas e a origem na propria origem. De nic~ao: Um operador linear e uma transformac~ao T que 8x; y 2 <n;  2 <:  T (x+ y) = T (x) + T (y),  T (x) = T (x). Da algebra linear, sabe-se que o conjunto de todos os operadores lineares em <n forma um espaco vetorial de dimens~ao n2. Um resultado importante e que existe um isomor smo entre a algebra dos operadores lineares em <n, determinado por uma base, sobre a algebra das matrizes quadradas nn. Note-se que qualquer matriz quadrada nn, A, sobre < de ne um operador linear em <n, pela transformac~ao v ! Av (onde v e escrito como um vetor coluna). E possvel mostrar que a representac~ao matricial deste operador e, justamente, a matriz A, se for usada a base canônica do <n. A representac~ao matricial de um operador linear e bastante adequada do ponto de vista computacional, pois permite que a composic~ao de diversas transformac~oes seja alcancado atraves do produto de matrizes. 5.2.1 Transformac~oes Lineares Bi-dimensionais Vai-se iniciar o estudo das transformac~oes lineares bi-dimensionais considerando o seu efeito sobre os pontos do plano. Como foi visto anteriormente, um operador linear bi-dimensional pode ser representado por uma matriz 2  2. O resultado da multiplicac~ao de um vetor coluna (x; y)T , que contem as coordenadas de um ponto, por uma matriz 2  2 generica pode ser escrito como: T (X) =  a c b d  x y  =  ax+ cy bx+ dy  =  x y  : Atribuindo valores aos elementos a; b; c; d, pode-se obter uma relac~ao entre o ponto trans- formado e o ponto original, conforme mostrado abaixo. a; d > 0; b = c = 0 ! x = ax; y = dy { escalamento das componentes x e y. a = 1; d = 1; b = c = 0 ! x = x; y = y { re ex~ao em relac~ao ao eixo y. a = 1; d = 1; b = c = 0 ! x = x; y = y { re ex~ao em relac~ao ao eixo x. a = d = 1; b = c = 0 ! x = x; y = y { re ex~ao em relac~ao a origem. 5.2. TRANSFORMAC ~OES LINEARES 67 a = d = 0; b = c = 1 ! x = y; y = x { re ex~ao em relac~ao a reta y = x. a = d = 0; b = c = 1 ! x = y; y = x { re ex~ao em relac~ao a reta y = x. a = d = 1; b = 0 ! x = x+ cy; y = y { cisalhamento na direc~ao x. a = d = 1; c = 0 ! x = x; y = bx+ y { cisalhamento na direc~ao y. Um objeto geometrico qualquer pode ser transformado por um operador linear, aplican- do-se a matriz de transformac~ao a cada um de seus pontos. A area do objeto transformado e dada pelo produto do determinante da matriz de transformac~ao pela area do objeto original. Uma mudanca de variavel no <n e dada por T : <n ! <n, onde T e um operador continuamente diferenciavel. Sendo R  <n com fronteira constituda por um numero nito de conjuntos diferenciaveis e supondo-se que R e sua fronteira est~ao contidos no domnio de T , e que:  T e injetiva em R;  det T 0, o determinante jacobiano de T , e diferente de zero em R; ent~ao, se a func~ao f e limitada e contnua em T (R) (a imagem de R por T ), tem-se: Z T (R) fdv = Z R (f:T ) det T 0 dv; T 0 =  @x @u (u; v) @x @v (u; v) @y @u (u; v) @y @v (u; v)  : R u v x y T(R) T Dominio de T u v x y T(R)R T Figura 5.2: Mudanca de Variavel. Como exemplo, tem-se a conhecida mudanca para coordenadas polares, dada pela transfor- mac~ao abaixo ( g. 5.2):  x y  =  x(u; v) y(u; v)  =  ucos(v) usin(v)  ; J =  cos(v) usin(v) sin(v) ucos(v)  ; det J = u: 70 CAPITULO 5. GEOMETRIA Transformacao nao Linear Fotografia Linha do Horizonte Cena Original Figura 5.3: Transformac~ao Projetiva. impossibilitanto que o efeito de translac~ao seja representado por um operador linear bi- dimensional. Alem disso, um paralelogramo n~ao pode ser transformado num quadrilatero arbitrario por um operador linear. Estes problemas podem ser tratados, de forma uni cada, com a introduc~ao de coordenadas homogêneas e o uso da Geometria Projetiva. De nic~ao: O plano projetivo RP 2 e conjunto das retas do <3 que passam pela origem, a menos da propria origem. Um ponto no plano projetivo e um conjunto P = f(x; y; z);  6= 0; (x; y; z) 6= (0; 0; 0)g: Este ponto e denotado por P = [x; y; z] em coordenadas homogêneas. Considerando o plano z = 1 como sendo o plano a m Euclideano mergulhado no plano projetivo, ent~ao, qualquer ponto P = [x; y; z] 2 RP 2; z 6= 0 pode ser escrito como: P =  x z ; y z ; 1  ; que representa a intersec~ao da reta (x; y; z) com o plano z = 1 ( = 1=z). Os pontos [x; y; 0] do plano projetivo n~ao possuem representantes no plano z = 1. Tem-se, desta forma, uma partic~ao natural do plano projetivo em dois conjuntos: RP 2 = f[x; y; 1]g [ f[x; y; 0]g: Os pontos [x; y; 0] s~ao os pontos ideais do plano projetivo. E interessante veri car que, nesse modelo, duas retas paralelas l e m no plano a m se interceptam em um ponto ideal, uma vez que a intersec~ao de dois planos, que passam pela origem, contendo l e m, e uma reta no plano z = 0 (um ponto ideal), conforme pode ser visto na gura 5.4. Uma reta no plano projetivo e o conjunto dos pontos [x; y; z] que satisfazem a uma equac~ao linear ax + by + cz = 0: Note-se que, se a equac~ao e satisfeita por um ponto (x0; y0; z0) 6= (0; 0; 0), ent~ao, ela tambem e satisfeita por qualquer ponto com coordenadas homogêneas (x0; y0; z0). Isto signi ca que o ponto [x0; y0; z0] do plano projetivo pertence a reta. No modelo a m do plano projetivo, a equac~ao da reta projetiva representa um plano em <3 passando pela origem e, portanto, se esse plano contem o ponto (x0; y0; z0), ent~ao, ele tambem contem a reta que passa por esse ponto e pela origem. 5.5. TRANSFORMAC ~OES PROJETIVAS 71 Indica-se por  a aplicac~ao que associa a cada ponto v = (x; y; z) no espaco a m <3, o ponto [x; y; z] do plano projetivo (isto e, (x; y; z) = [x; y; z] e a reta do espaco Euclideano de nida pelo vetor v). Essa aplicac~ao e chamada de aplicac~ao quociente. Plano Afim x y z RP 2 r 1 r2 (x,y,z) (x/z,y/z,1) ponto projetivo retas projetivas ponto ideal (intersecao de r1 e r2), ~ Reta Ideal (plano xy) Figura 5.4: Plano Projetivo. Se T e uma operador linear invertvel do <3, ent~ao T transforma retas em retas e deixa a origem (0; 0; 0) xa. Desse modo, T de ne naturalmente uma transformac~ao no plano projetivo. Essa transformac~ao e chamada de transformac~ao projetiva induzida por T e sera indicada por T . Se [x; y; z] s~ao as coordenadas homogêneas do ponto P e M e a matriz 33 do operador T , ent~ao: T (P ) =M(x; y; z)T . Diz-se queM e a matriz da transformac~ao projetiva T . Utilizando coordenadas homogêneas, pode-se representar uma transformac~ao a m bi-dimenional (A(u) = Tu+ v) por uma matriz 3 3. A matriz projetivaM , 33, generica pode ser dividida, para efeito de estudo, em quatro partes: M = 0 BB@ a c j m b d j n p q j s 1 CCA : Colocando a = d = s = 1 e b = c = p = q = 0, obtem-se a matriz de translac~ao pura: 0 @ 1 0 m0 1 n 0 0 1 1 A 0 @xy 1 1 A = 0 @x+my + n 1 1 A : Com s = 1 e m = n = p = q = 0, obtem-se escala, rotac~ao, re ex~ao e cisalhamento, produzindo os mesmos efeitos dos operadores lineares bi-dimensionais: 0 @ a c 0b d 0 0 0 1 1 A 0 @xy 1 1 A = 0 @ ax+ cybx+ dy 1 1 A : 72 CAPITULO 5. GEOMETRIA Em ambos os casos, vê-se que pontos do plano a m s~ao levados em pontos do plano a m e que pontos ideais s~ao levados em pontos ideais. Para mostrar o efeito de p; q 6= 0 na terceira linha da matriz, considere-se o seguinte: 0 @XY Z 1 A = 0 @xy z 1 A = 0 @ 1 0 00 1 0 p q 1 1 A 0 @xy 1 1 A = 0 @ xy px+ qy + 1 1 A : Agora, um ponto do plano a m, expresso em coordenadas homogêneas, e levado para um ponto do espaco tri-dimensional de nido por z = px + qy + 1. Aplicando esta mesma transformac~ao a um ponto ideal obtem-se: M(x; y; 0)T = (x; y; px+ qy)T : Observando as equac~oes acima, vê-se que n~ao ocorre o efeito de invariância dos casos anteriores: pontos ideais podem ser transformados em pontos do plano a m e vice-versa. Geometricamente, se um ponto ideal e transformado em um ponto P0 do plano a m, ent~ao a famlia de retas paralelas, que se interceptam nesse ponto ideal, s~ao transformadas em uma famlia de retas incidentes no ponto P0 ( g. 5.5). O ponto P0 e chamado de ponto de fuga da transformac~ao. Um ponto de fuga correspondendo a uma direc~ao paralela a um dos eixos coordenados e chamado ponto de fuga principal. Como no plano a m existem no maximo duas direc~oes ortogonais, podem-se ter transformac~oes projetivas com no maximo dois pontos de fuga principais. Cada um desses pontos de fuga e a imagem do ponto ideal que corresponde a estas direc~oes: [x; 0; 0] e [0; y; 0]. A existência desses pontos de fuga e controlada pelos elementos p e q, correspondendo as direc~oes x e y, respectivamente. Plano Afim x y z RP 2 r2 Reta Ideal (plano xy) ponto de fuga transformacao perspectiva r 1 Figura 5.5: Ponto Ideal Transformado em Ponto Real. Entretanto, interessa obter o resultado desta transformac~ao nos pontos do plano a m. Isto e feito considerando a intersec~ao com o plano z = 1: [x; y; z] =  x z ; y z ; 1  ; z = px+ qy + 1: 5.7. TRANSFORMAC ~OES TRI-DIMENSIONAIS 75 por um ângulo , ao redor do eixo x: 0 BB@ 1 0 0 0 0 cos() sin() 0 0 sin() cos() 0 0 0 0 1 1 CCA : A rotac~ao e positiva (sentido anti-horario) quando se olha para a origem, a partir do lado positivo do eixo de rotac~ao. Analogamente, a matriz de rotac~ao, por um ângulo , ao redor do eixo z e: 0 BB@ cos( ) sin( ) 0 0 sin( ) cos( ) 0 0 0 0 1 0 0 0 0 1 1 CCA : Para a rotac~ao, por um ângulo , ao redor do eixo y a matriz e: 0 BB@ cos() 0 sin() 0 0 1 0 0 sin() 0 cos() 0 0 0 0 1 1 CCA : Neste ultimo caso, o sinal dos senos foram trocados para manter a convenc~ao da direc~ao positiva de rotac~ao. A rotac~ao ao redor de um eixo arbitrario do espaco e obtida, em coordenadas homogêneas, com uma composic~ao de transformac~oes (o eixo e especi cado por um ponto (x0; y0; z0) e uma direc~ao (cx; cy; cz)):  Transladando o ponto (x0; y0; z0) para a origem.  Rotacionando o eixo de rotac~ao de forma a que coincida com o eixo z. Em geral, este passo envolve duas rotac~oes; uma em torno do eixo x e a outra em torno do eixo y.  Rotacionando em torno de z pelo ângulo desejado.  Rotacionando pelo inverso das rotac~oes aplicadas ao eixo de rotac~ao.  Transladando de volta ao ponto (x0; y0; z0).  [Re] = [T1][R1x ][R1y ][Rz][Ry][Rx][T ] Algumas orientac~oes de um objeto tri-dimensional n~ao podem ser obtidas usando rotac~oes puras; elas requerem re ex~oes. Em 3D, uma re ex~ao ocorre em relac~ao a um plano. Uma re ex~ao em relac~ao ao plano xy altera somente as coordenadas z (seus sinais s~ao trocados). A matriz de re ex~ao e idêntica a matriz identidade, a menos do elemento (3,3), que e negativo. O mesmo vale para os planos xz e yz, onde o elemento negativo e o elemento (2,2) e (1,1), respectivamente. Uma re ex~ao em relac~ao a um plano arbitrario, tambem pode ser obtida, em coordenadas homogêneas, por uma composic~ao de transformac~oes. Os passos necessarios s~ao:  Transladar um ponto qualquer do plano de re ex~ao para a origem. 76 CAPITULO 5. GEOMETRIA  Rodar o vetor normal ao plano de re ex~ao, em relac~ao a origem, ate que coincida com o eixo z. Tambem envolve, tipicamente, duas rotac~oes; uma em relac~ao a x e a outra em relac~ao a y.  Re etir o objeto em relac~ao ao plano z = 0.  Executar as transformac~oes inversas daquelas aplicadas ao plano de re ex~ao.  [Rfltp] = [T1][R1x ][R1y ][Rfltz][Ry][Rx][T ] 5.8 Transformac~ao Perspectiva Chama-se de transformac~ao perspectiva a uma transformac~ao projetiva cuja imagem de algum ponto ideal P0 e um ponto P do espaco a m. Neste caso, as retas paralelas na direc~ao do ponto P0 s~ao transformadas em retas incidentes a P . Este tipo de transformac~ao e muito importante no processo de visualizac~ao. Quando algum elemento da submatriz (13) e diferente de 0, ocorre uma transformac~ao perspectiva. Uma transformac~ao perspectiva com um unico ponto de fuga, sobre o eixo z, e dada por: 0 BB@ 1 0 0 0 0 1 0 0 0 0 1 0 0 0 r 1 1 CCA 0 BB@ x y z 1 1 CCA = 0 BB@ x y z rz + 1 1 CCA : Aqui, um ponto do espaco a m e levado para o hiperplano w = rz + 1 6= 1. As coordena- das homogêneas usuais s~ao obtidas dividindo-se por w : [x0; y0; z0; 1] = [x=w; y=w; z=w; 1]: Note-se que os pontos do espaco a m com coordenada z = 0 n~ao s~ao afetados por esta transformac~ao e aqueles com coordenada z = 1=r s~ao transformados em pontos ideais ( g. 5.6). Uma projec~ao perspectiva em algum plano de vis~ao bi-dimensional e obtida pre-multi- plicando-se, uma matriz de projec~ao ortogra ca5, a matriz de transformac~ao perspectiva (projetanto no plano z = 0, o efeito e descartar a coordenada z). Escolhendo-se um centro de projec~ao zc, sobre o eixo z, e fazendo r = 1=zc; obtem-se o mesmo resultado de uma projec~ao sobre o plano z = 0. Aplicando a transformac~ao perspectiva ao ponto ideal [0; 0; 1; 0], que corresponde a inter- sec~ao das retas paralelas ao eixo z, obtem-se [0; 0; 1; r]. O ponto [x0; y0; z0; 1] = [0; 0; 1=r; 1] representa a imagem deste ponto ideal. Dessa forma, vê-se que as retas paralelas a direc~ao z convergem para um ponto de fuga, de coordenada 1=r, sobre o eixo z. Isto signi ca que o semi-espaco in nito 0  z  1 e transformado no semi-espaco nito 0  z0  1=r. Quando mais de um elemento da submatriz (1  3) e n~ao nulo, têm-se transformac~oes perspectivas com dois ou três pontos de fuga. A transformac~ao perspectiva com três pontos 5 Esta matriz e singular (n~ao e invertvel), pois possui as terceiras linha e coluna, nulas. 5.8. TRANSFORMAC ~AO PERSPECTIVA 77 A B A’ B’ A* B* -1/r 1/r z x y ponto de fuga centro de projecao~, segmento AB projetado no plano z=0. segmento AB transformado pela transf. perspectiva. Figura 5.6: Perspectiva com um ponto de fuga. de fuga e dada por: 0 BB@ 1 0 0 0 0 1 0 0 0 0 1 0 p q r 1 1 CCA 0 BB@ x y z 1 1 CCA = 0 BB@ x y z w = px+ qy + rz + 1 1 CCA ; 0 BB@ x0 y0 z0 1 1 CCA = 0 BB@ x=w y=w z=w 1 1 CCA : A transformac~ao perspectiva com três pontos de fuga tem três centros de projec~ao: um sobre o eixo x, com coordenadas [1=p; 0; 0; 1]; outro sobre o eixo y, com coordenadas [0;1=q; 0; 1]; e o terceiro sobre o eixo z, com coordenadas [0; 0;1=r; 1]. Os pontos de fuga se localizam sobre o eixo x, com coordenadas [1=p; 0; 0; 1]; sobre o eixo y, com coordenadas [0; 1=q; 0; 1]; e sobre o eixo z, com coordenadas [0; 0; 1=r; 1]. O mesmo resultado e obtido pela aplicac~ao, em cascata, de três transformac~oes perspectivas com um unico ponto de fuga, um em cada eixo coordenado. Transformac~oes perspectivas com dois pontos de fuga podem ser obtidas pela composic~ao de uma transformac~ao perspectiva, com um unico ponto de fuga, com uma transformac~ao de rotac~ao ao redor de um eixo coordenado perpendicular ao eixo coordenado que contem o centro de projec~ao. Se forem usadas duas rotac~oes, obtem-se uma transformac~ao perspectiva com três pontos de fuga: [T3pf ] = [Prz][Rx][Ry]: Os pontos de fuga correspondendo as direc~oes n~ao paralelas aos eixos principais podem ser encontrados calculando, diretamente, a intersec~ao de dois segmentos (originalmente paralelos a direc~ao desejada) transformados, ou encontrando a imagem do ponto ideal cor- respondente. 80 CAPITULO 6. MODELAGEM GEOMETRICA Formas Modelos Representacoes Estruturas de Dados Figura 6.1: Modelo Conceitual.  por coordenadas (parametricamente);  por densidade (implicitamente). Estes dois tipos de descric~ao originam dois tipos de representac~ao de solidos a saber:  Representac~ao por bordo, B-rep (Boundary representation);  Representac~ao implcita, CSG (Constructive Solid Geometry). 6.2 Representac~ao por Bordo Na representac~ao por bordo ou por fronteira, o solido e de nido indiretamente, atraves da superfcie, compacta4 e sem bordo, que o delimita (forma a sua fronteira). Esta superfcie e descrita parametricamente por um mapeamento, ' : U  <2 ! <3, chamado de uma parametrizac~ao da superfcie ou carta local ( g. 6.2). u v sistema de coordenadas herdado u v u v 1 2 3 Figura 6.2: Parametrizac~ao de uma Superfcie. Desta forma, a parametrizac~ao '(u; v) = ('1(u; v); '2(u; v); '3(u; v)) = (x; y; z) associa a cada ponto do plano, um ponto do espaco tri-dimensional. Para que o solido seja bem de nido, exige-se que a superfcie n~ao apresente auto-intersec~ao e que o vetor normal, (@'=@u  @'=@v), n~ao se anule em algum ponto da superfcie. Isto porque a normal e 4 Fechada e limitada. 6.2. REPRESENTAC ~AO POR BORDO 81 utilizada para determinar o interior e o exterior do solido, a partir de alguma convenc~ao, por exemplo, que a normal em qualquer ponto da superfcie aponte, localmente, para o exterior do solido. A parametrizac~ao estabelece um sistema de coordenadas sobre a superfcie, herdado de um sistema de coordenadas no plano. Em geral, e impossvel cobrir (descrever) toda a superfcie com uma unica parametrizac~ao. Por isso, s~ao utilizadas descric~oes por partes, onde empregam-se varias parametrizac~oes que de nem pedacos de superfcie que v~ao sendo colados uns aos outros ( g. 6.2), formando um atlas. A parametrizac~ao de uma esfera de raio um, centrada na origem, e dada por exemplo: f(; ) = (cossin; sinsin; cos): O vetor normal e dado em cada ponto por: @f @  @f @ = (sinsin; cossin; 0) (coscos; sincos; sin): Se  =  ou  = 0 a normal a esfera n~ao esta de nida, por esta parametrizac~ao, nos polos. Assim, o domnio U desta parametrizac~ao e dado por: U = f(; ) 2 <2; 0 <  < ; 0   < 2g: 6.2.1 Representac~ao Linear por partes Uma superfcie parametrizada e geometricamente complexa pode ser aproximada por uma superfcie linear por partes. Um metodo bastante empregado consiste em poligonizar o domnio da parametrizac~ao (em geral s~ao utilizados triângulos ou quadrilateros). Cada vertice no domnio poligonal e levado para a superfcie pela parametrizac~ao e ligado aos vertices adjacentes. Este processo cria uma superfcie poligonizada, chamada de malha poligonal. Com isto, obtem-se uma geometria aproximada mas, em compensac~ao, bastante simples. Uma malha poligonal nada mais e do que uma decomposic~ao celular5 poligonal de nida por uma colec~ao conexa de vertices, arestas e polgonos, tal que cada aresta e compartilhada por no maximo dois polgonos e a intersec~ao de dois polgonos quaisquer e uma aresta, um vertice ou e vazia. Algumas operac~oes basicas com malhas poligonais correspondem a:  achar todas as arestas que incidem em um vertice;  achar os polgonos que compartilham uma aresta ou um vertice;  achar as aresta que delimitam um polgono;  exibir a malha. Existem quatro formas basicas para codi car uma malha poligonal:  codi cac~ao explcita; 5 Um complexo a m homeomorfo a superfcie. 82 CAPITULO 6. MODELAGEM GEOMETRICA  codi cac~ao com ponteiros para lista de vertices;  codi cac~ao com ponteiros para lista de arestas;  codi cac~ao com arestas aladas (winged-edge). Codi cac~ao Explcita Nesta codi cac~ao, cada polgono armazena explicitamente uma lista de coordenadas de vertices: P = f(x1; y1; z1); (x2; y2; z2); :::; (xn; yn; zn)g. Esta codi cac~ao e adequada para armazenar um unico polgono. No entanto, produz redundância de informac~ao, quando o objetivo e armazenar varios polgonos, uma vez que s~ao armazenados vertices duplicados. Alem disso, cada aresta compartilhada e desenhada duas vezes na exibic~ao da malha, o que e problematico quando se utilizam plotadoras ou lme. A execuc~ao de querys tambem e complicada, porque os relacionamentos de adjacência entre vertices, arestas e polgonos n~ao s~ao armazenados explicitamente (obriga a execuc~ao de algoritmos geometricos). Codi cac~ao com Ponteiros para Lista de Vertices Neste tipo de codi cac~ao, os vertices s~ao armazenados separadamente, em uma lista de vertices. Cada polgono faz referência aos seus vertices, na lista de vertices, por meio de ponteiros ( g. 6.3). V1 V2 V3 V4 P1 P2 E1 E2 E5 E3 E4 Figura 6.3: Codi cac~ao com Ponteiros para Lista de Vertices.  V = fV1 = (x1; y1; z1); V2 = (x2; y2; z2); V3 = (x3; y3; z3); V4 = (x4; y4; z4)g;  P1 = fV1; V2; V4g;  P2 = fV4; V2; V3g: Esta codi cac~ao proporciona uma maior economia de espaco, pois cada vertice e ar- mazenado uma unica vez. Alem disso, as coordenadas de um vertice podem ser alteradas facilmente. Porem, ainda e di cl determinar os polgonos que compartilham uma aresta e as arestas compartilhadas ainda s~ao desenhadas duas vezes. 6.3. REPRESENTAC ~AO IMPLICITA 85 rF = (2x; 2y) se anula na origem. Neste caso, 0 n~ao e um valor regular de F e, por conseguinte, F (x; y) = 0 n~ao de ne uma superfcie implcita6. Pode-se mostrar que o vetor gradiente e perpendicular a curva de nvel em cada ponto (faca-o!). c x y F(x,y) F(c) -1 Figura 6.5: Crculo De nido Implicitamente. Um outro exemplo s~ao cascas esfericas de nidas implicitamente por uma func~ao F (x; y; z) = x2 + y2 + z2: Para todo k > 0; F1(k) representa a superfcie de uma esfera no <3. Novamente, 0 n~ao e um valor regular de F , pois F1(0) = (0; 0; 0) e rF = (2x; 2y; 2z) se anula na origem. Um exemplo mais interessante e dado pela func~ao abaixo: F (x; y) = y2 x2 x3; rF = (2y;3x2 2x); ou na forma parametrica, x(t) = t2 1; y(t) = t(t2 1): (6.1) Note-se que a curva de nvel 0 de F e um laco, que apresenta uma singularidade na origem ( g. 6.6): z = F (x; y) = y2 x2 x3 = 0: Se olhar-se agora para F(x,y) como superfcie de nvel 0 da func~ao H : <3 ! <; H(x; y; z) = z + y2 x2 x3; rH = (3x2 2x; 2y;1); rH(0;0;0) = (0; 0;1); 6F1(0) = (0; 0). 86 CAPITULO 6. MODELAGEM GEOMETRICA vê-se que todos os pontos s~ao regulares, pois o gradiente de H e diferente de (0; 0; 0) em todos os pontos do <3. Conclui-se ent~ao que o gra co de F no <3 e realmente gra co de uma func~ao. F(x,y) < 0 F(x,y) > 0 x y -2/3 20/27 t = +-1 t = 8 8t = - -1 t = 0 Figura 6.6: Curva do Laco. 6.3.1 Objeto Implcito Ate aqui foram dados exemplos de superfcies implcitas. Na realidade, necessita-se do conceito de objeto implcito, para que se possa construir uma representac~ao para solidos. De nic~ao: Um subconjunto O  <n e chamado de objeto implcito ( g. 6.7) se existe F : U ! <; O  U; e existe um subconjunto V  < tal que O = F1(V ) ou O = fp 2 U; F (p) 2 V g: Um objeto implcito e regular se a func~ao F satisfaz a condic~ao de regularidade. Um objeto implcito e valido se ele de ne uma superfcie no <n. Seja p = (x; y; z). Ent~ao, vai-se considerar que sendo F (p):  > 0 ) p 2 exterior de O;  = 0 ) p 2 fronteira de O;  < 0 ) p 2 interior de O. A func~ao F faz uma classi cac~ao dos pontos do espaco. Dado qualquer ponto, F permite decidir se o ponto esta no interior, na fronteira ou no exterior do objeto. 6.4. CONVERS~AO ENTRE REPRESENTAC ~OES 87 R c F F-1 Figura 6.7: Objeto Implcito. 6.3.2 Esquema de Representac~ao CSG Um metodo efetivo para construir objetos complexos, a partir de objetos simples, e atraves de operac~oes CSG (Constructive Solid Geometry). Este esquema e baseado em operac~oes booleanas regularizadas de conjuntos de pontos: [; \; = (uni~ao, intersec~ao e diferenca). Um objeto e regular se o fecho do interior do seu conjunto de pontos e igual ao proprio conjunto de pontos. Um modelo CSG e codi cado por uma arvore, onde os nos contêm operac~oes de conjunto ou transformac~oes geometricas e as folhas contêm objetos primitivos. Um solido CSG e de nido como um conjunto de pontos do <n que satisfaz F (X)  0 para algum F : <3 ! < de classe C1. As operac~oes booleanas s~ao de nidas por (prove!):  F1 [ F2 = min(F1; F2);  F1 \ F2 = max(F1; F2);  F1=F2 = F1 \ F2 = max(F1;F2): 6.4 Convers~ao entre Representac~oes A convers~ao entre as representac~oes por bordo e implcita e um topico importante porque ambas apresentam vantagens e desvantagens. Na representac~ao por bordo as intersec~oes de superfcies est~ao armazenadas explicitamente, alem de ser facil exibir um ponto sobre uma superfcie. Em contra partida, a determinac~ao da inclus~ao de um ponto em um objeto requer algoritmos n~ao triviais, especialmente em dimens~ao três. A avaliac~ao de operac~oes booleanas e bastante trabalhosa do ponto de vista algoritmico. Na representac~ao implcita, a determinac~ao da inclus~ao de um ponto e imediata, bastando avaliar o sinal da func~ao de densidade no ponto. Porem, exibir um ponto sobre a superfcie de um objeto implica em resolver uma equac~ao que pode ser complicada, mas a avaliac~ao de operac~oes booleanas e simples. Estas considerac~oes apontam na direc~ao de sistemas com multi-representac~ao. Determi- nados algoritmos s~ao mais facilmente implementados a partir de uma certa representac~ao. Assim, caso exista convers~ao entre as representac~oes, cada algoritmo pode se valer da re- 90 CAPITULO 6. MODELAGEM GEOMETRICA p0 p1 p2p6 p7 p5 p4 a) b) p3  (p0; p1; p3; p7) (p0; p1; p5; p7)  (p0; p2; p3; p7) (p0; p2; p6; p7)  (p0; p4; p5; p7) (p0; p4; p6; p7) Figura 6.10: Triangulac~ao CFK. chamados octantes, por três planos ortogonais aos eixos coordenados. Cada octante e ent~ao classi cado em:  cheio - completamente contido no interior do objeto;  vazio - completamente contido no exterior do objeto;  incompleto - uma parte esta contida no interior e a outra no exterior do objeto. Octantes incompletos s~ao subdivididos, recursivamente, ate um nvel maximo. Neste ponto, os octantes incompletos s~ao considerados cheios. 6.5 Ambiguidade e Unicidade de Representac~oes Retornando ao paradigma dos quatro universos, de ne-se que uma representac~ao e unica quando um modelo possui uma, apenas uma, representac~ao. Em geral, a condic~ao de unicidade e de difcil obtenc~ao. Tanto a representac~ao implcita como a representac~ao por bordo n~ao s~ao representac~oes que apresentam unicidade (dê exemplos!). O conceito de ambiguidade e mais importante pois estabelece que, dada uma represen- tac~ao, existe um unico modelo associado. Uma representac~ao ambgua e catastro ca, pois n~ao se consegue determinar qual o modelo que ela representa (tornaria uma maquina de controle numerico, inviavel). A representac~ao wire-frame e extremamente ambgua. Um dos problemas que se coloca na area de Modelagem Geometrica diz respeito a ob- tenc~ao de algoritmos robustos para a convers~ao (aproximada) entre representac~oes distintas. 6.6. EXERCICIOS 91 M R M R ambiguidade nao unicidade Universos Figura 6.11: Unicidade e Ambiguidade de Representac~ao. 6.6 Exerccios 6.1 Discuta a obtenc~ao dos relacionamentos de adjacência, entre vertices, arestas e faces, a partir das seguintes estruturas de dados:  lista de faces;  ponteiros para lista de vertices;  ponteiros para listas de arestas;  winged edge. 6.2 Considerando apenas vertices, arestas e faces e possvel formar 9 tipos de relacio- namentos de adjacência diferentes. Por exemplo, F(A) refere-se ao conjunto de arestas em torno de uma face, F(V) ao conjunto de vertices em torno da face, etc. Quais destes conjuntos podem ser ordenados? 6.3 Como alterar a estrutura de dados baseada em ponteiros para lista de arestas de forma a que a determinac~ao das faces que compartilham uma aresta possa ser executada e cien- temente? 6.4 Prove as seguintes igualdades:  F1 \ F2 = max(F1; F2);  F1 [ F2 = min(F1; F2);  F1 F2 = max(F1;F2); 92 CAPITULO 6. MODELAGEM GEOMETRICA onde Fi : <n ! < s~ao func~oes que determinam um objeto implcito como a imagem inversa do ponto zero (assumindo que zero e um ponto regular de Fi). Qual a importância deste resultado? 6.5 Construa um programa para gerar uma aproximac~ao poligonal para uma superfcie implcita de dimens~ao 1 (curva), compacta e sem bordo. 6.6 Estenda a implementac~ao do exerccio anterior de forma a a aproximar tambem su- perfcies implcitas de dimens~ao 2. 6.7 Discuta as vantagens e desvantagens da representac~ao por bordo, que usa uma des- cric~ao parametrica do solido, e volumetrica, que usa uma descric~ao implcita do solido. Que tipos de aplicac~ao se adequam mais a cada uma destas representac~oes? Por que? 6.8 Construa uma parametrizac~ao,  : <2 ! <3, para um triângulo no espaco, dado pelas coordenadas dos seus três vertices. Sugest~ao: utilize coordenadas baricêntricas. 6.9 Um esquema de representac~ao para poli-linhas usando segmentos de reta associa a uma poli-linha L o conjunto f(x0; y0; x1; y1); (x1; y1; x2; y2); :::; (xn1; yn1; xn; yn)g onde (xi; yi; xi+1; yi+1) representam as coordenadas iniciais e nais de cada segmento de reta que comp~oe a poli- linha. a) Discuta essa representac~ao em relac~ao as propriedades de validade, ambiguidade e uni- cidade. b) De na uma noc~ao de proximidade entre poli-linhas e discuta a representac~ao em relac~ao a este conceito. 6.10 Um polgono P no espaco e uma sequência V1; V2; :::; Vk de pontos distintos, situados no mesmo plano, tal que V1 = Vk. O esquema de representac~ao LV associa a P a n-tupla LV (P ) = (V1; V2; :::; Vk1): a) Especi que um tipo abstrato de dados (TAD) para implementar essa representac~ao. b) Relacione as operac~oes associadas a esse TAD com operac~oes no modelo. c) Investigue as possveis inconsistências topologicas e geometricas que podem ocorrer nes- sa representac~ao. d) Descreva procedimentos para identi car as inconsistências no item anterior. 6.11 Considere o universo dos polgonos convexos de n lados e elabore metodos de repre- sentac~ao geometrica para descrever os elementos desse universo. a) Usando um esquema construtivo. b) Usando um esquema de decomposic~ao. c) Usando um esquema de aproximac~ao. 6.6. EXERCICIOS 95 (x(t), y(t)) t t(-1, 0) x y y = tx + t Figura 6.14: Convers~ao Implcita - Parametrica. 6.16 Para uma cônica geral, o ponto p do exerccio anterior pode n~ao ser t~ao obvio. Para estes casos, e mais facil considerar a equac~ao homogeneizada ([x; y; w] = (x=w; y=w; 1)): a11x 2 + a22y 2 + a33w 2 + 2a12xy + 2a13xw + 2a23yw = 0: Se a cônica contem um dos pontos fundamentais ((0; 0; 1), (0; 1; 0) ou (0; 0; 1)) ent~ao a equac~ao e linear na variavel correspondente, que pode ser explicitada em func~ao das outras duas. Considerando-as coordenadas projetivas parametrizadas, tem-se uma parametrizac~ao da cônica. a) Considere o crculo x2+y22xw que contem a origem (0; 0; 1). Derive a parametrizac~ao projetiva da forma projetiva da cônica: x = s y = t w = (s2 + t2)=2s: b) Coloque s = 1 e obtenha coordenadas a ns parametrizadas. Divida por w e obtenha uma parametrizac~ao a m da forma a m do crculo ( g. 6.15): x(t) = 2=(1 + t2) y(t) = 2t=(1 + t2): 96 CAPITULO 6. MODELAGEM GEOMETRICA t < 0 t > 0 t = 0 8 x y t = 8t = - x w y (0,0,1) Figura 6.15: Parametrizac~ao de Cônicas. 6.17 Considere a cônica x2+6xy+5y22x2y1 = 0. Na forma homogênea, x2+6xy+ 5y2 2xw 2yw w2 = 0, vê-se que ela n~ao contem nenhum dos pontos fundamentais, uma vez que possui os termos quadrados em x; y e w. A estrategia e ent~ao encontrar um ponto no in nito (correspondendo a w = 0), e leva-lo para (0; 1; 0). Parametriza-se ent~ao a cônica transformada e aplica-se a transformac~ao inversa a parametrizac~ao obtida. a) Ache os dois pontos no in nito resolvendo a11x 2+2a12xy+a22y 2 = 0, fazendo y = a11 e resolvendo uma equac~ao do segundo grau para encontrar duas coordenadas x. b) Seja (u; v; 0) um ponto no in nito. Aplicando a transformac~ao x = x1 + uy1; y = vy1; w = w1; que leva (u; v; 0)! (0; 1; 0), encontre a equac~ao a m da cônica transformada. c) Parametrizando a cônica resultante e aplicando a transformac~ao inversa, obtenha a parametrizac~ao da cônica original: x(t) = 5t2 2t 1 4t ; y(t) = 1 + 2t t2 4t : d) Entenda o que foi feito desenhando cada passo no plano projetivo. No caso presente, a interpretac~ao geometrica e que a cônica original, que representa uma hiperbole, e levada em uma elipse por uma rotac~ao. 6.6. EXERCICIOS 97 6.18 Um ponto p de uma curva algebrica de grau n tem multiplicidade m se um numero in nito de retas por p interceptam a curva em nm pontos adicionais (considerando pontos complexos e intersec~oes no in nito). Nem todas as cubicas irredutveis possuem uma forma parametrica racional. Aquelas que têm um ponto singular devem tê-lo com multiplicidade 2. Geometricamente, a parametri- zac~ao de uma cubica e analoga a parametrizac~ao de uma cônica; consideram-se as retas que passam pelo ponto singular duplo e calculam-se as intersec~oes com a cubica. So pode haver mais uma unica intersec~ao. a) Considere a cubica y2 x2 x3. Mostre que a origem e um ponto singular duplo. b) Parametrizando as retas r(t) : y = tx que passam pela origem, obtenha a parametri- zac~ao apresentada na sec~ao 6.3. 6.19 O teorema de Bezout diz que duas curvas algebricas de grau m e n se interceptam em exatamente mn pontos ou têm uma componente comum. a) Explique o metodo de parametrizac~ao de cônicas e cubicas, baseado na intersec~ao de retas com a curva, em face ao teorema de Bezout. b) Uma curva algebrica possui um numero nito de pontos multiplos. Um monoide e uma curva algebrica de grau n com um ponto de multiplicidade n 1. Generalize o metodo de parametrizac~ao do item anterior para monoides. 6.20 Suponha que se deseja ter apenas planos com coe cientes racionais. Uma rotac~ao de um ângulo em torno de um eixo qualquer pode fazer com que o plano transformado passe a ter coe cientes irracionais. a) Dado qualquer encontre um novo ângulo 0 tal que (u; v) = (cos( 0); sin( 0)) seja racional. Sugest~ao: use a parametrizac~ao racional do crculo unitario do exerccio 6.15, onde t = m=n = tan( 0=2). b) Encontre os novos coe cientes (racionais) do plano rodado em torno do eixo z. c) Componha três rotac~oes racionais para obter a rotac~ao racional em torno de um eixo arbitrario.