Baixe o app para aproveitar ainda mais
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 .
Compartilhar