introducao

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
*
Introdução à
Computação Gráfica
Luis Carlos Retondaro, Pb., M.Sc.
Universidade Federal do Rio de Janeiro (UFRJ) 
Centro Federal de Educação Tecnológica Celso Sukow da Fonseca (CEFET-RJ) – UnED Petrópolis.
*
*
*
Bibliografia
Computer Graphics - Principles and Practice Foley - van Dam - Feiner - Hughes 2nd edition in C - Addison and Wesley
Notas do Curso ministrado na Universidade de Maryland pelo Prof. David Mount 
Apostila Prof. Paulo Roma (UFRJ)
OpenGL® Programming Guide, 2nd Edition. Mason Woo, Jackie Neider, Tom Davis. Addison Wesley.
Notas de Aula Prof. Luis Retondaro (Estácio)
Site oficial do OpenGL:
http://www.opengl.org
Acesse o site do professor para saber mais: 
http://www.retondaro.pro.br
*
*
*
Introdução
*
*
*
Computação Gráfica
Modelagem
Geométrica
Processamento de Imagens
Dados
Análise (reconhecimento de padrões)
Síntese (rendering)
Imagens
*
*
*
Disciplinas relacionadas
Computação 
Algoritmos
Estruturas de Dados
Métodos Numéricos
Matemática 
Geometria 
Álgebra Linear
Física 
Ótica
Mecânica 
Psicologia 
Percepção
Artes
*
*
*
Aplicações
Arte Efeitos especiais, modelagens criativas, esculturas e pinturas. 
Medicina Exames, diagnósticos, estudo, planejamento de procedimentos. 
Arquitetura Perspectivas, projetos de interiores e paisagismo.
Engenharia Em todas as suas áreas (mecânica, civil, aeronáutica etc.)
Geografia Cartografia, GIS, georreferenciamento, previsão de colheitas. 
Meteorologia Previsão do tempo, reconhecimento de poluição.
Astronomia Tratamento de imagens, modelagem de superfícies.
Marketing Efeitos especiais, tratamento de imagens, projetos de criação. 
Segurança Pública Definição de estratégias, treinamento, reconhecimento.
Indústria Treinamento, controle de qualidade, projetos.
Turismo Visitas virtuais, mapas, divulgação e reservas.
Moda Padronagem, estamparias, criação, modelagens, gradeamentos.
Lazer Jogos, efeitos em filmes, desenhos animados, propaganda. 
Processamento de Dados Interface, projeto de sistemas, mineração de dados.
Psicologia Terapias de fobia e dor, reabilitação.
Educação Aprendizado, desenvolvimento motor, reabilitação.
*
*
*
Representações Gráficas
Gráficos “Vetoriais”
Representados por coleções de objetos geométricos 
Pontos
Retas
Curvas
Planos
Polígonos
Gráficos “Matriciais”
Amostragem em grades retangulares
> imagens digitais 
Matrizes de “pixels” 
Cada pixel representa uma cor 
Dados volumétricos
ex. Imagens médicas
Cada pixel representa densidade ou intensidade de algum campo
*
*
*
Representações Vetoriais
Permitem uma série de operações sem (quase) perda de precisão
Transformações lineares / afim
Deformações
Por que “quase”? Estruturas de dados utilizam pontos e vetores cujas coordenadas são números reais
É necessário usar aproximações
Representação em ponto-flutuante
Números racionais
Complexidade de processamento = O (no vértices / vetores) 
Exibição
Dispositivos vetoriais
Dispositivos matriciais (requer amostragem, i.e., rasterização)
*
*
*
Representações Matriciais
Representação flexível e muito comum
Complexidade de processamento = O (no de pixels)
Muitas operações implicam em perda de precisão (reamostragem)
Ex.: rotação, escala
Técnicas para lidar com o problema 
Ex.: técnicas anti-serrilhado (anti-aliasing)
Exibição
Dispositivos matriciais
Dispositivos vetoriais (requer uso de técnicas de reconhecimento de padrões)
*
*
*
Conversão entre representações
 Repr. Vetoriais 
 Rasterização, Reconhecimento
 “Scan conversion” de padrões
Repr. Matriciais
*
*
*
Dispositivos Gráficos
Dispositivos vetoriais
Terminais gráficos vetoriais (obsoletos)
Traçadores (plotters)
Dispositivos virtuais
Ex.: Linguagens de descrição de página (HPGL / Postscript)
Dispositivos Matriciais
Praticamente sinônimo de dispositivo gráfico
Impressoras, displays
*
*
*
Displays
Resolução espacial
Tipicamente de 640x480 até 1600x1200
Tendência de aumento
Resolução no espaço de cor
Monocromático (preto e branco)
Praticamente restrito a PDAs e equipamentos de baixo custo
Tabela de cores
Cada pixel é representado por um número (tipicamente 8 bits – de 0 a 255) que indexa uma tabela de cores (tipicamente RGB 24 bits)
Poucas (ex.: 256) cores simultâneas mas cada cor pode ser escolhida de um universo grande (ex.: 224)
Problema da quantização de cores
RGB
Cor é expressa por quantidades discretas de vermelho (red), verde (green) e azul (blue)
Tipicamente 24 bits (8 bits para cada componente)
Quando o número de bits não é divisível por 3, a resolução do azul costuma ser menor que das outras 2 componentes
*
*
*
Arquitetura de Sistemas Gráficos
Barramento (BUS)
CPU
Periféricos
Memória
Frame Buffer
Controlador de vídeo
Monitor
Arquitetura Simples
*
*
*
Arquitetura de Sistemas Gráficos
Barramento (BUS)
CPU
Periféricos
Memória
Frame Buffer
Contro-
lador de vídeo
Monitor
Proces- sador gráfico
Memória do Sistema
Arquitetura com processador gráfico
*
*
*
Processador (acelerador) gráfico
Hardware especializado
Uso de paralelismo para atingir alto desempenho
Alivia a CPU do sistema de algumas tarefas, incluindo:
Transformações 
Rotação, translação, escala, etc
Recorte (clipping)
Supressão de elementos fora da janela de visualização
Projeção (3D 2D)
Mapeamento de texturas
Rasterização
Amostragem de curvas e superfícies paramétricas
Geração de pontos a partir de formas polinomiais
Normalmente usa memória separada da do sistema
Maior banda
*
*
*
Programação Gráfica
À primeira vista: basta desenhar
Uma subrotina para desenhar cada tipo de objeto
Mas ...
Como fazer interação?
Como estruturar a cena?
Como controlar os atributos dos objetos?
Como resolver problemas de visibilidade?
Como suportar diversos dispositivos gráficos?
Como fazer programas independentes dos sistemas operacionais?
Ferramentas:
APIs gráficas (ex.: OpenGL, PHIGS, Java3D) 
Camadas de interface com o S.O. / sistema de janelas
*
*
*
Rasterização
*
*
*
Representação Vetorial x Matricial
Normalmente, gráficos são definidos através de primitivas geométricas como pontos, segmentos de retas, polígonos, etc
Representação vetorial
Dispositivos gráficos podem ser pensados como matrizes de pixels (rasters)
Representação matricial
Rasterização é o processo de conversão entre representações vetorial e matricial
*
*
*
Considerações Gerais
Rasterização é um processo de amostragem
Domínio contínuo  discreto
Problemas de aliasing são esperados
Cada primitiva pode gerar um grande número de pixels 
Rapidez é essencial
Em geral, rasterização é feita por hardware
Técnicas de antialiasing podem ser empregadas, usualmente extraindo um custo em termos de desempenho
*
*
*
Rasterização de Segmentos de Reta
Segmento de reta entre P1= (x1, y1) e P2= (x2, y2)
Já foi recortado com relação ao viewport
Objetivo é pintar os pixels atravessados pelo segmento de reta
Na verdade, nem todos, apenas os mais próximos
Reta de suporte dada por a x + b y + c = 0
Queremos distinguir os casos
Linhas ~ horizontais  computar y como função de x
Linhas ~ verticais  computar x como função de y
*
*
*
Algoritmo Simples
Assumimos segmentos de reta no primeiro octante, com
Demais casos resolvidos de forma simétrica
Inclinação (entre 0 e 1) dada por m = (y2 – y1) / (x2 – x1)
Algoritmo:
Para x desde x1 até x2 fazer:
y ← y1 + m * (x – x1) + 0.5
Pintar pixel (x, y)
P1
P2
*
*
*
Algoritmo Incremental
Algoritmo simples tem vários problemas:
Utiliza aritmética de ponto-flutuante
Sujeito a erros de arredondamento
Usa multiplicação
Lento
Se observarmos que m é a variação em y para um incremento unitário de x, podemos fazer ligeiramente melhor:
x ← x1 ; y ← y1 
Enquanto x ≤ x2 fazer:
x ← x + 1 
y ← y + m
Pintar
pixel (x, y + 0.5 )
Ainda usa ponto-flutuante
*
*
*
Algoritmo de Bresenham
Algoritmo clássico da computação gráfica
Algoritmo incremental que utiliza apenas soma e subtração de inteiros
Idéia básica:
Em vez de computar o valor do próximo y em ponto flutuante, decidir se o próximo pixel vai ter coordenadas (x + 1, y) ou (x + 1, y + 1)
Decisão requer que se avalie se a linha passa acima ou abaixo do ponto médio (x + 1, y + ½)
(x + 1, y)
(x + 1, y + 1)
(x, y)
(x + 1, y + ½)
*
*
*
Algoritmo de Bresenham
Variável de decisão V é dada pela classificação do ponto médio com relação ao semi-espaço definido pela reta
Caso 1: Linha passou abaixo do ponto médio
(x,y)
(x+1,y)
(x+1,y+1)
(x+1,y+½)
(x,y+½)
V1
V0
(x,y+1)
*
*
*
Algoritmo de Bresenham
Caso 2: Linha passou acima do ponto médio
(x,y)
(x+1,y+1)
(x+1,y+ 1+ ½)
(x,y+½)
V1
V0
(x,y+1)
(x+1,y+2)
*
*
*
Algoritmo de Bresenham
Coeficientes da reta
a = y2 – y1 
b = x1 – x2
c = x2 y1 – x1 y2
Para iniciar o algoritmo, precisamos saber o valor de V em (x1+ 1, y1 + ½)
V = a (x1 + 1) + b (y1 + ½) + c 	 = a x1 + b y1 + c + a + b/2 = a + b/2 
Podemos evitar a divisão por 2 multiplicando a, b e c por 2 (não altera a equação da reta)
*
*
*
Algoritmo de Bresenham - Resumo
a ← y2 – y1 
b ← x1 – x2
V ← 2 * a + b
x ← x1
y ← y1
Enquanto x ≤ x2 fazer:
Pintar pixel (x, y)
x ← x + 1
Se V ≤ 0 
Então V ← V + 2 * a 
Senão V ← V + 2 * (a + b) ; y ← y + 1
*
*
*
Extensão para demais Octantes
Se x2 < x1 
Trocar P1 com P2
Se y2 < y1 
 y1 ← - y1 
 y2 ← - y2 
Pintar pixel (x, -y) 
Se |y2 – y1| > |x2 – x1| 
Repetir o algoritmo trocando “y” com “x”
*
*
*
Rasterização de Círculos
Mesma idéia de avaliar incrementalmente uma função que classifica o ponto médio entre um pixel e outro com relação a uma função implícita
Apenas um octante precisa ser avaliado, os demais são simétricos
Para cada pixel computado, oito são pintados
Derivação um pouco mais difícil que a da reta
Outras cônicas podem também ser rasterizadas de forma semelhante
E
SE
V0
C(x,y) = 0
V1’
V1
*
*
*
Preenchimento de Regiões
Não é propriamente rasterização uma vez que operação se dá no espaço da imagem
Regiões são definidas por critérios de vizinhança a um pixel dado (semente)
4-conexa (borda 8-conexa)
8-conexa (borda 4-conexa)
Exemplo: 
Pixels com cor semelhante à semente
Borda tem cor diferente
Pixels com cor diferente de uma cor dada
Borda tem cor igual à cor dada
*
*
*
Algoritmo de Preenchimento
Conhecido como “Flood Fill”
Algoritmo recursivo
Preenche vizinhos da semente que atendem ao critério
Aplica o algoritmo recursivamente tomando esses vizinhos como sementes
Termina quando nenhum vizinho atende o critério
*
*
*
Algoritmo de Preenchimento
Pseudo-código:
Procedure FloodFill (x, y, cor, novaCor)
Se pixel (x, y) = cor então
pixel (x, y) ← novaCor
FloodFill (x + 1, y, cor , novaCor)
FloodFill (x, y + 1, cor , novaCor)
FloodFill (x - 1, y, cor , novaCor)
FloodFill (x, y - 1, cor , novaCor)
Uso abusivo de recursão pode ser contornado preenchendo intervalos horizontais iterativamente
Pode ser necessário usar um bitmap auxiliar para marcar os pixels visitados. Por exemplo
Critério é pixel (x, y) ≈ cor
Se cor ≈ novaCor, não há meio de distinguir um pixel visitado de um não visitado
*
*
*
Rasterização de Polígonos
Operação fundamental em computação gráfica
Polígono é dado por uma lista de vértices
Último vértice = primeiro vértice
Obs.: OpenGL rasteriza apenas triângulos
Triângulos são casos especiais de polígonos
Polígonos genéricos precisam ser triangulados
Triangulação faz parte da biblioteca de utilitários (gluTesselate) 
*
*
*
Rasterização de Polígonos
Algoritmo clássico usa técnica de varredura
Arestas são ordenadas 
Chave primária: y mínimo
Chave secundária: x mín. 
Exemplo: (e,d,a,b,c)
Linha de varredura perpendicular ao eixo y percorre o polígono (desde ymin até ymax)
Intervalos horizontais entre pares de arestas são preenchidos
y
x
*
*
*
Rasterização de Polígonos
Cuidados devem ser tomados para evitar pintar um mesmo pixel mais de uma vez
Dois polígonos adjacentes
Vértices (pertencem a 2 arestas)
*
*
*
Rasterização de Polígonos
Intervalos de preenchimento
Definidos sobre a linha de varredura
Cada intervalo começa e termina sobre um pixel interceptado por uma aresta
Primeiro pixel é pintado, último não
Arestas horizontais não são consideradas
Um vértice de uma aresta não horizontal é considerado apenas se for o vértice com menor y
*
*
*
Rasterização de Polígonos – 
Estruturas de Dados
Aresta
y inicial (y mínimo)
y final 
x corrente (inicialmente, x inicial)
dx (incremento x)
Lista de Arestas – arestas do polígono
Ordenadas por y inicial / x inicial
Lista de Arestas Ativas – arestas do polígono que interceptam linha de varredura corrente
Ordenadas por coordenada x de interseção
y final
y inicial
1
incremento x
x inicial
*
*
*
Rasterização de Polígonos – 
Pseudo Código
Inicialização
Criar e ordenar LA (lista de arestas)
Computar ymin e ymax
LAA ← nulo
Para y desde ymin até ymax fazer
Inserir em LAA todas as arestas com yinicial = y
Retirar da LAA todas as arestas com yfinal = y
Para cada par de arestas A1/A2 da LAA fazer 
Desenhar todos os pixels com x entre A1.xcorrente e A2.xcorrente (exclusive)
Para cada aresta A da LAA fazer
A.xcorrente ← A.xcorrente + A.dx
Reordenar a LAA (arestas cruzadas)
*
*
*
Geometria
*
*
*
Pontos e Vetores (2D)
Ponto: Denota posição no plano
Vetor: Denota deslocamento, isto é, inclui a noção de direção e magnitude
Ambos são normalmente expressos por pares de coordenadas (em 2D) mas não são a “mesma coisa”
x
y
P
v
*
*
*
Operações com Pontos e Vetores (2D)
Soma de vetores
t = v + u
Multiplicação de vetor por escalar
u = 2 v 
Subtração de pontos
v = Q – P
Soma de ponto com vetor
Q = P + v
x
y
v
u
t = v + u
x
y
v
x
y
P
v
v
u = 2 v
Q
*
*
*
Transformações
Transformação é uma função que mapeia pontos de um espaço Euclidiano em outros (ou possivelmente os mesmos) pontos do mesmo espaço. 
Se uma transformação é linear, então
Se um conjunto de pontos está contido em uma reta, depois de transformados eles também estarão contidos sobre uma reta.
Se um ponto P guarda uma relação de distância com dois outros pontos Q e R, então essa relação de distância é mantida pela transformação. 
Transformação mapeia origem na origem?
Sim: Transformação Linear
Não: Transformação Linear Afim: Translações são permitidas 
*
*
*
Transformações Lineares em 2D
Uma transformação linear
Uma transformação linear afim
*
*
*
Forma Matricial
Mais conveniente para uso em um computador. Sejam
Então uma transformação linear afim pode ser escrita T (P ) = P’ onde
*
*
*
Transformando Vetores
Um vetor não está atrelado a um ponto no espaço
Uma transformação linear afim aplicada a um vetor não inclui translação
Prova: Seja V um vetor e V’ sua imagem sob a transformação linear afim, então:
*
*
*
Coordenadas Homogêneas
A transformação de vetores é operacionalmente diferente da de pontos
Coordenadas homogêneas permitem unificar o tratamento
Problema é levado para uma dimensão superior:
Coordenada extra w= 0 para vetores e =1 p/ pontos
Termos independentes formam uma coluna extra na matriz de transformação
*
*
*
Coordenadas Homogêneas - Interpretação
*
*
*
Transformações em 3D
Vetores e pontos em 3D
Transformação linear afim 
*
*
*
Transformações Rígidas
Não modificam a forma (dimensões/ângulos) do objeto 
São compostas de uma rotação e uma translação
Submatriz de
Rotação
Vetor de 
Translação
*
*
*
Composição de transformações em 3D
Em nossa notação, usamos pré-multiplicação:
P’
= T x P
Para compor 2 transformações temos:
Se P’ = T1 x P e P’’ = T2 x P’ , então, P’’ = T2 x T1 x P 
*
*
*
Geometria Afim
Composta dos elementos básicos
escalares
pontos - denotam posição
vetores - denotam deslocamento (direção e magnitude)
Operações
escalar · vetor = vetor 
vetor + vetor ou vetor – vetor = vetor 
ponto – ponto = vetor
ponto + vetor ou ponto – vetor = ponto
*
*
*
Combinações Afim
Maneira especial de combinar pontos
Para 2 pontos P e Q poderíamos ter uma combinação afim R = (1 – )P +Q = P +(P – Q)
P
Q
R= P+(P – Q)
P
Q
0 <  < 1
  < 0
  > 1
*
*
*
Combinações Convexas
Combinações afim onde se garante que todos os coeficientes i são positivos (ou zero)
Usa-se esse nome porque qualquer ponto que é uma combinação convexa de n outros pontos pertence à envoltória convexa desses pontos
P1
P2
P3
P4
P5
Q
*
*
*
Geometria Euclidiana 
Extensão da geometria afim pela adição de um operador chamado produto interno
Produto interno é um operador que mapeia um par de vetores em um escalar. Tem as seguintes propriedades:
Positividade : (u,u)  0 e (u,u) = 0 sse u=0
Simetria: (u,v) = (v,u)
Bilinearidade: (u,v+w)= (u,v)+ (u,w) e
 				 (u,v)= (u,v)
*
*
*
Geometria Euclidiana
Normalmente usamos o produto escalar como operador de produto interno:
Comprimento de um vetor é definido como:
Vetor unitário (normalizado):
*
*
*
Geometria Euclidiana
Distância entre dois pontos P e Q =|P – Q |
O ângulo entre dois vetores pode ser determinado por 
Projeção ortogonal: dados dois vetores u e v, deseja-se decompor u na soma de dois vetores u1 e u2 tais que u1 é paralelo a v e u2 é perpendicular a v
v
u
u1
u2
*
*
*
Produto Vetorial (3D)
Permite achar um vetor perpendicular a outros dois dados
Útil na construção de sistemas de coordenadas
Propriedades (assume-se u, v linearmente independentes):
Antisimetria: u × v = – v × u
Bilinearidade: u × (v) =  (u × v) e u × (v + w) = (u × v) + (u × w) 
u × v é perpendicular tanto a u quanto a v 
O comprimento de u × v é igual a área do paralelogramo definido por u e v, isto é, | u × v | = | u | | v | sin 
u
v
u×v
.