Unidade Curricular

Pretende-se que os alunos dominem efetivamente os conceitos e técnicas fundamentais da computação gráfica 2D e 3D.

Para os gráficos 2D são desenvolvidos temas como primitivas de desenho procedimental e gráficos vetoriais, transformações e técnicas de animação. Nos gráficos 3D são tratados os grafos de cena, pontos de vista, geometria e aspeto, transformações, iluminação e animação.

Os conceitos e técnicas são transmitidos no contexto da web, usando as tecnologias mais recentes deste domínio.

• Programa
• Avaliação
• Bibliografia

Programa

Avaliação

• A avaliação de Computação Gráfica tem uma componente teórica e uma componente prática.
• A componente teórica pode ser realizada por exame, ou por testes (ie frequências).
• A componente prática consiste na realização de quatro trabalhos dentro do processo e condições indicadas a seguir.
• Os exames correspondem apenas à componente teórica da avaliação.
• Se reprovar no exame normal pode fazer o exame de recurso.

Veja as datas das provas nos anúncios do moodle.

Componente Teórica

• A componente teórica vale 60% da nota final (12 valores).
• Cada teste vale 20% da nota final (4 valores).
• Pode realizar os testes que desejar e também os exames (normal e de recurso).
• A nota final desta componente é a combinação mais vantajosa que resulta dos testes e dos exames.
• Exemplo 01. Testes: 03, 03, NA; Exame: 11; Nota final: 11.
• Exemplo 02. Testes: 04, 03, 03; Exame: 08; Nota final: 10.
• Exemplo 03. Testes: 04, NA, 04; Exame: NA; Nota final: 08.

Componente Prática

• A componente prática vale 40% da nota final (8 valores).
• Cada trabalho conta 10% da nota final (2 valores).
• Cada trabalho corresponde a uma das tecnologias: SVG, C2D, X3D e 3JS.
• A componente prática não tem «recurso».
• A classificação de cada trabalho é calculada segundo os Critérios de Avaliação dos Trabalhos Práticos.

Todos os trabalhos terão de ser entregues até à data do «Exame Normal».

Critérios de Avaliação dos Trabalhos Práticos

Bibliografia

• João Madeiras Pereira, João Brisson, António Coelho, Alfredo Ferreira, Mário Rui Gomes - Introdução à Computação Gráfica (2019).
• Marschner, S., Shirley, P. - Fundamentals of Computer Graphics (2016).
• Hughes J.F., et al. - Computer graphics. Principles and practice (2014).
• Ammeraal, L., Zhang, K. - Computer Graphics for Java Programmers (2007).

Introdução

Conceitos Fundamentais

Processo da Computação Gráfica

• Modelação: Especificação do modelo gráfico.
  • Grafo de Cena: Estrutura de dados que define e organiza o modelo gráfico.
  • Programação gráfica: Uso de uma linguagem de programação, ou um documento, para descrever o grafo de cena.
• Construção: Transformação do modelo gráfico numa imagem.

Definição e Disciplinas Relacionadas.

• Computação Gráfica: É o estudo e aplicação das técnicas de modelação, processamento e construção de objetos gráficos em computadores.
• Visão Artificial: É o oposto da computação gráfica: procura reconstruir um modelo (virtual) a partir de imagens reais.
• Programação de Jogos: É uma aplicação da computação gráfica: usa um modelo (virtual) onde o utilizador interage.
• Processamento de Imagem: Tem técnicas para:
  • Melhoramento de imagem (equalização do histograma, etc).
  • Compressão de imagem.
  • Deteção de features: arestas,super-pixeis, etc..
  • Resolver crimes (CSI).
• Álgebra Linear: Proporciona as bases formais e numéricas para a CG.

Modelação

A modelação consiste em especificar o modelo gráfico que define a imagem.

• Espaço do Modelo: É um espaço 2D ou 3D onde é definido o modelo, juntando e organizando vários objetos gráficos - nos espaços 3D os problemas são mais complexos e tratados de forma significativamente diferente dos espaços 2D.

• Objetos Gráficos: Entidades geométricas (linhas, superfícies) ou luzes, textos, imagens.

• Representações Matemáticas: Permitem definir e transformar os objetos gráficos.

• Vistas: Mostram um modelo numa perspetiva específica e enquadram o passo da construção

  • Os modelos 2D têm vistas relativamente simples.
  • Para modelos 3D é necessário ter em conta inúmeras propriedades que envolvem a câmara, a iluminação, entre outras.

Grafo de Cena

O Grafo de Cena é a estrutura de dados que define o modelo gráfico.

---
config:
  theme: neutral
---
flowchart TD;
scene([scene]) --> person([person])
person --> head([head])
person --> body([body])
person --> arms([arms])
person --> legs([legs])
head --> leye([left eye])
head --> reye([right eye])
head --> mouth([mouth])

arms --> larm([left arm])
arms --> rarm([right arm])

legs --> lleg([left leg])
legs --> rleg([right leg])

Além do "simples" desenho de objetos, interessa definir um modelo onde os objetos são colocados e geridos. O grafo de cena organiza os vários objetos gráficos numa única estrutura de dados que "alimenta" a rotina de rendering.

Programação Gráfica

A programação gráfica consiste em especificar um modelo (i.e. um grafo de cena), usando um programa ou um documento.

• Iniciar o modelo:

  • Colocar e ligar objetos gráficos.
  • Definir vistas.

• Evoluir o modelo:

  • Remover e/ou acrescentar novos objetos.
  • Alterar atributos (posições, ...).

Construção

Construção (ou Rendering) é o processo computacional que transforma um modelo gráfico numa imagem exibida num dispositivo físico.

A construção pode ser feita de dois "modos" distintos:

• Modo Retido: O modelo é definido e depois a imagem é construída.
• Modo Imediato: Os objetos são imediatamente desenhados.

Outros Aspetos da Computação Gráfica

• Problemas:

  • Oclusão: o que está "à frente" e o que "fica tapado"?
  • Colocação: posição, rotação, tamanho.
  • Aspeto: cores, texturas, iluminação, sombras.
  • etc.

• Hardware: Ecrãs, Impressoras, Plotters, Projetores holográficos, etc.

• Animação:

  • Filmes: uma sequência de imagens.
  • Jogos: uma sequência de imagens, com interação.
  • Simulações: uma sequência de imagens, seguindo as "leis de um sistema".

• Interação: Teclados e Ratos, Rede, Interfaces Gráficos, etc.

Aplicações

Filmes

Jogos

Visualização

Simulação

Estatística

Medicina

Computação Gráfica na Web

A Computação Gráfica na web proporciona:

• Normas Abertas com ecossistema enorme:
  • Aplicações, Ferramentas.
  • Informação, Comunidade.
• Paradigmas modernos de descrição de dados e de programação.
• Suporte para gráficos 2D (canvas, svg, etc) e 3D (x3dom, three.js, etc).

Web 2D

Os elementos canvas e svg:

• São elementos HTML para gráficos 2D (e 3D).

• Proporcionam ferramentas para modelar:

  • Figuras Geométricas, Texto, Imagens.
  • Transparências, Gradientes, Transformações, Glifos.

Web 3D

• O elemento x3d é usado para integrar conteúdo 3D diretamente num documento html, sem extensões.
• A biblioteca threejs usa o elemento canvas com contexto webgl permite o rendering de gráficos 2D e 3D, sem extensões.

Exemplos elementares

Contexto 2D

<canvas id="cg:exemplos:c2d" width="256" height="128" />
<script>
  const gc = document.getElementById("cg:exemplos:c2d").getContext("2d");
  gc.fillStyle = "steelblue";
  gc.fillRect(64, 32, 128, 64);
</script>

SVG

<svg
    width = "256"
    height = "128">
  <rect
    x = "64" y = "32"
    width = "128" height = "64"
    style = "fill:steelblue"></rect>
</svg>

ThreeJS

<div id="gc:exemplos:3js"></div>
<script>
  const renderer = new THREE.WebGLRenderer( {alpha: true} );
  renderer.setSize(256, 256);
  renderer.setClearColor( 0xffffff, 0);
  const container = document.getElementById("gc:exemplos:3js")
  container.appendChild(renderer.domElement);
  const scene = new THREE.Scene();
  const camera = new THREE.PerspectiveCamera(
    35,       // abertura
    500/500,  // proporção largura/altura
    0.1,      // corte perto
    10000     // corte longe
    );
  camera.position.set( -2.5, 0, 20 );
  camera.lookAt( scene.position );
  const geometry = new THREE.BoxGeometry( 5, 5, 5 );
  const material = new THREE.MeshLambertMaterial( {color: "steelblue"} );
  const mesh = new THREE.Mesh( geometry, material );
  scene.add( mesh );
  const light = new THREE.AmbientLight( "white" );
  scene.add( light );
  function animate() {
      mesh.rotation.x += 0.005;
      mesh.rotation.y += 0.005;
      renderer.render(scene, camera);
      requestAnimationFrame(animate);
  }
  animate();
</script>

X3D

<x3d
    width = "256px"
    height = "256px">
  <scene>
    <shape>
      <appearance>
        <twosidedmaterial
          diffuseColor = "steelblue">
        </twosidedmaterial>
      </appearance>
      <box></box>
    </shape>
  </scene>
</x3d>

Gráficos 2D

Conceitos Fundamentais 2D

Na computação gráfica 2D, tanto os espaços dos objetos (onde são definidos os objetos gráficos) como o espaço do modelo (onde é definido o modelo) são 2D (isto é, planos).

Modelação. O processo de modelação é relativamente simples:

1. Cada objeto gráfico é definido (pela a sua geometria e outras propriedades não-geométricas, como a cor) no seu próprio espaço do objeto.
2. O modelo é constituído juntando e organizando os vários objetos gráficos já definidos num grafo de cena.

Modelação de Objetos Gráficos

• Geometria (forma). A geometria de um objeto gráfico (2D ou 3D) é geralmente obtida com:

  • Objetos básicos como retas, quadrados, círculos, caminhos ou cubos, cilindros, reticulados, etc.
  • Textos.

• Transformações. As transformações são usadas para:

  • Construir objetos gráficos compostos a partir de outros, mais simples.
  • Posicionar cada objeto gráfico (definido no seu próprio espaço do objeto) no espaço do modelo.
  • Modificar a geometria de objetos usando:
    • Rotações.
    • Escalas.
    • Translações.
    • e outras operações.

• Aspeto (propriedades não geométricas). Além da construção da geometria (isto é, da forma) também são usadas propriedades que dizem respeito ao aspeto:

  • Cores e transparências.
  • Texturas.
  • Estilos de linhas.

Geometria 2D

A geometria dos objetos gráficos usa linhas e outros conjuntos de pontos, como polígonos ou elipses.

O problema que se coloca aqui é saber como representar essas linhas, conjuntos de pontos, etc.

A representação dos objetos gráficos assenta na aplicação da matemática, em particular da Álgebra Linear e da Geometria Analítica, que proporcionam as definições formais (como ponto, plano, etc) e propriedades relevantes.

Neste capítulo vamos explorar a representação matemática das entidades geométricas:

• Sistemas de coordenadas (ou Referenciais).
• Equações para retas, circunferências e elipses.
• Equações paramétricas.
• Caminhos e formas «irregulares».

Referenciais

Referenciais
Referencial Cartesiano x Referencial Ecrã

Um referencial é a ferramenta matemática que permite representar numericamente espaços geométricos.

Uma vez escolhido um referencial, cada ponto do espaço fica identificado por uma lista de números: as coordenadas desse ponto.

Num espaço 2D as coordenadas têm duas componentes, (x, y) e no espaços 3D têm três componentes (x, y, z).

Podemos escolher diferentes referenciais para tratar problemas diferentes. Dois dos referenciais 2D mais comuns são:

• O referencial cartesiano, normalmente usado na aulas de matemática.
• O referencial do ecrã, normalmente usado em dispositivos gráficos;

Geometrias Primitivas

Matematicamente, um objeto gráfico, como uma linha reta ou uma circunferência, é um conjunto de pontos.

Ingenuamente, poderíamos pensar em usar (digamos) listas com esses pontos. O problema é que mesmo os objetos gráficos mais simples são formados por infinitos pontos (quantos pontos existem numa linha?).

A solução para representar objetos gráficos consistem em usar equações.

Uma equação tem uma quantidade finita de informação que define um conjunto infinito de pontos.

Por exemplo $(x-2{)}^2+(y+1{)}^2=9$ é um texto finito que define os infinitos pontos da circunferência de raio $3$ centrada em $(2,-1)$.

Consideremos as equações mais comuns:

• Equações da Reta $$Ax+By+C=0$$ ou $$X=P+\lambda v$$
• Equação da Circunferência $$(x-x_0{)}^2+(y-y_0{)}^2=R^2$$
• Equação da Elipse $${\left(\frac{x-x_0}{a}\right)}^2+{\left(\frac{y-y_0}{b}\right)}^2=1$$

Mas:

1. Quantos números são usados para representar uma reta? Quantos pontos estão nessa reta?
2. Porque não se usa, para as retas, a equação mais comum $y=mx+b$?
3. Ainda para a equação da reta, como é que se obtém a equação da reta que passa em dois pontos dados?
   • Solução: Dados dois pontos $A=(x_A,y_A)$ e $B=(x_B,y_B)$ uma equação paramétrica da reta que passa em $A$ e $B$ é $$X=A+\lambda (B-A)=(x_A,y_A)+\lambda (x_B-x_A,y_B-y_A)$$ Esta equação tem a seguinte propriedade conveniente: $X=A$ quando $\lambda =0$ e $X=B$ quando $\lambda =1$.

As equações dadas acima não são a forma mais adequada de trabalhar com objetos gráficos para efeitos da computação gráfica.

Desafio. Como obter $100$ pontos da circunferência $x^2+y^2=3$?

Com equações paramétricas, que indicam explicitamente as coordenadas $(x,y)$ dos pontos do objeto.

• Para a reta: $$X=P+tv\Rightarrow (x,y)=(P_x,P_y)+t(v_x,v_y)\Rightarrow \{\begin{array}{rl}x& =P_x+t{v}_x\\ y& =P_y+t{v}_y\end{array}$$

• Para a circunferência: $$(x-x_0{)}^2+(y-y_0{)}^2=R^2\Rightarrow \{\begin{array}{rl}x& =x_0+R\cos t\\ y& =y_0+R\sin t\end{array}$$

• Para a elipse: $${\left(\frac{x-x_0}{a}\right)}^2+{\left(\frac{y-y_0}{b}\right)}^2=1\Rightarrow \{\begin{array}{rl}x& =x_0+a\cos t\\ y& =y_0+b\sin t\end{array}$$

Equações Paramétricas e Geometria

As equações paramétricas usam um parâmetro (nestes exemplos, a variável $t$) que imaginamos que está a percorrer um certo intervalo (digamos $\left[0,2\pi \right]$) num certo número de passos ($100$ por exemplo).

Conforme $t$ vai tomando diferentes valores nesse intervalo, vamos também obtendo diferentes valores das coordenadas $(x,y)$ dos pontos que formam a geometria do objeto gráfico.

function parametric_circle(cx, cy, r) {
    return function(t) { return {
        x: cx + r * Math.cos(t),
        y: cy + r * Math.sin(t)
        };
    }
}
const ctx = document.getElementById("2d:geo:parametric").getContext("2d");
const my_circle = parametric_circle(128, 128, 64);
ctx.fillStyle = "steelblue";
const n = 64;
for (let t = 0; t <= n; t++) {
    const angle = t * 2 * Math.PI / n;
    p = my_circle(angle);
    ctx.fillRect(p.x - 2, p.y - 2, 4, 4);
};

Desafio. A equação paramétrica da reta tem um problema: O que acontece quando $B=0$?

Caminhos

As equações permitem representar eficientemente formas «regulares», mas nem sempre existe uma forma «regular» adequada ao objeto que se pretende construir…​

Os caminhos permitem definir formas «irregulares» que podem ser tratadas como "objetos básicos".

<svg>
    <path
        fill="none"
        stroke="steelblue"
        stroke-width="4"
        stroke-linecap="round"
        fill-rule="evenodd"
        transform="translate(256,128)"
        d="
            M -200 0
            Q 0 -200 200 0
            Q 0 200 -200 0
            M -100 50
            L -100 -50
            L 100 50
            L 100 -50
            L -100 50
            Z
        "/>
</svg>

Pensamos num caminho como (o resultado d)as operações que fazemos com um lápis numa folha de papel:

• traçar um contorno;
• pintar o interior dum contorno;

Traçar o contorno dum caminho

Um contorno é formado por por vários segmentos. Cada segmento é traçado a partir do fim do segmento anterior, como um lápis numa folha de papel.

Há quatro tipos básicos de segmentos:

• salto. O lápis salta para uma certa posição.
• linha. O lápis desenha uma reta até uma certa posição.
• curva quadrática. O lápis desenha uma curva, controlada por um ponto, até uma certa posição.
• curva cúbica (ou bezier). O lápis desenha uma curva, controlada por dois pontos, até uma certa posição.

Exemplo da construção do contorno dum caminho, segmento-a-segmento

Pintar o interior dum caminho

Pintar o interior dum caminho (isto é, encher a zona delimitada pelo caminho) é uma tarefa surpreendentemente difícil.

Definido um caminho fechado, como determinar se um dado ponto está dentro ou fora da região delimitada pelo caminho?

Para responder a esta questão é usado um de dois algoritmos (regras) para encher um caminho:

• A regra par-ímpar é mais simples e por isso menos controlável.
• A regra não-zero é mais complexa do que a regra par-ímpar mas permite tirar partido da orientação dos segmentos para definir o interior do caminho.

Ambas as regras funcionam com base no seguinte princípio:

1. O retângulo é «varrido de cima para baixo» por linhas que «andam» da esquerda para a direita.
2. Em cada uma dessas linhas são calculados os pontos que intersectam o caminho.
3. É aplicada uma das regras para determinar quais segmentos limitados por esses pontos são interiores e quais são exteriores ao caminho.

Par-ímpar	Não-zero
	Os segmentos do caminho têm de ser orientados.
Os pontos de interseção são numerados da esquerda para a direita (a começar em zero).	Os pontos de interseção são:
	Positivos (azuis) se o segmento vem pela direita da linha.
	Negativos (vermelhos) se o segmento vem pela esquerda da linha.
Os segmentos interiores estão entre um ponto par (azul) e um ponto ímpar (vermelho).	Os segmentos interiores estão entre pontos com total acumulado não zero (estritamente positivo ou negativo).

Explore o código SVG sobre caminhos

<path id="thePath"
    d="
        M 50 50
        L 90 10
        Q 10 10 10 50
        L 50 50
        C 10 90 90 90 70 50
        Z" />

em

Aspeto 2D

A apresentação de um objeto gráfico, além da forma (definida pela geometria) também depende de outras propriedades visuais:

• cores, traços e tintas;
• textos e fontes;

Cores

A especificação numérica de uma cor depende de um espaço numérico.

Conforme a aplicação do modelo gráfico, certos espaços são mais adequados que outros:

• Para ecrãs, onde a cor é emitida, a escolha mais comum é um espaço RGB onde cada cor fica definida por três componentes (r, g, b) correspondentes a vermelho, verde e azul.
• Para impressão, onde a cor é refletida, usam-se espaços CMY (cião, magenta e amarelo) ou CMYK (cião, magenta, amarelo e preto). A adição do preto resulta da dificuldade de se produzir economicamente o preto com as restantes componentes.
• Para certas aplicações a escolha de uma cor em termos de RGB ou CMY (definidos em função do hardware) pode iludir a perceção humana; Um espaço de cor definido em termos de perceção humana é o HSL (de hue=tom, saturation=saturação e luminosity=luminosidade).

No contexto da web o espaço de cor normal é o RGB; Há imensas formas de especificar concretamente uma cor mas a mais comum é da forma #rrggbb em que rr, gg e bb são números entre 0 e 255 representados em notação hexadecimal. Por exemplo:

Além disso, através do CSS, também estão disponível cores por nome (ver as tabelas de cores na norma w3 ou na wikipedia).

Testar cores HSL

Traços

Os traços (isto é, as propriedades visuais das linhas) são inesperadamente complexos.

Uma linha desenhada num dispositivo não é um objeto abstrato (como uma linha matemática, de espessura 0). Na prática as linhas têm formas específicas.

Os traços são definidos por:

• uma espessura.
• um tracejado
• as extremidades.
• as junções com outros traços.
• o corte das junções.

Exemplos de traços	CSS
Espessuras	stroke-width
	0.15, 1, 2, 4, 8
Tracejados	stroke-dasharray
	2 2, 1 2, 2 1 4 1, 1 2 2 1
Extremidades	stroke-linecap
	butt, round, square
Junções	stroke-linejoin
	miter, round, bevel
Cortes	stroke-miterlimit
	1, 4

Testar traços

Tintas

A tinta define como uma forma é pintada. Há várias formas de pintar uma geometria:

• usando uma cor sólida;
• usando um mosaico (uma imagem repetida);
• usando um gradiente de cores (uma variação suave entre cores);

Uma tinta pode ser aplicada apenas ao contorno (stroke) ou encher (fill) o interior da geometria:

Traçar e Pintar um caminho
Traçar x Pintar

Mosaicos

O uso de mosaicos para traçar ou encher o contorno é semelhante à aplicação de uma cor sólida, com a particularidade de que a «cor» é um padrão repetido:

Tinta do tipo "mosaico"
Traçar x Pintar com mosaicos

Gradientes de Cores

Os gradientes mais simples são lineares: uma cor inicial vai mudando suavemente ao longo de uma linha, até chegar a uma cor final. Também podemos definir versões um pouco mais complexas, com várias cores:

Um gradiente linear

A forma de definir gradientes "multi-coloridos" consiste em associar cores a pontos de paragem. Um ponto de paragem fica definido por um certo offset (deslocamento) do caminho entre o ponto mais à esquerda e o ponto mais à direita:

• o ponto mais à esquerda tem offset 0;
• o ponto mais à direita tem offset 1;
• pontos intermédios têm offset entre 0 e 1. Por exemplo, um ponto exatamente a meio tem offset 0.5 e um ponto a um quarto "do início do caminho" tem offset 0.25;

Por exemplo, o gradiente acima está definido com:

1. Uma paragem com offset 0.00 e cor khaki:

2. Uma paragem com offset 0.20 e cor steelblue:

3. Uma paragem com offset 0.75 e cor crimson:

4. Uma paragem com offset 1.00 e cor darkseagreen:

Outra propriedade que controla a aplicação dos gradientes é o prolongamento, que em geral tem três formas:

Finalmente, um gradiente também pode ser circular (em vez de linear):

Um gradiente circular

Texto

Texto e Fonte

O uso de textos envolve selecionar uma fonte e desenhar o texto de acordo com essa fonte.

• Um texto é um tipo especial de objeto geométrico, definido por uma sequência de carateres (letras, dígitos, etc);
• Uma fonte define os desenhos dos carateres;

Letras, Dígitos, Glifos

Tecnicamente, glifo é o termo que designa, em conjunto:

• As letras (a é β etc).
• Os dígitos (0 1 9 etc).
• Símbolos de pontuação (! , . etc).
• As ligaturas (Æ Œ fi etc).
• Outros símbolos (± ∫ → etc).

As propriedades das fontes estão definidas na norma CSS Fonts Module Level 3 e incluem, entre outras:

Transformações 2D

O processo da computação gráfica determina os seguintes passos:

1. Modelação:
   1. Definição de cada objeto gráfico no respetivo espaço do objeto;
   2. Definição do modelo, no espaço do mundo, juntando os vários objetos gráficos do ponto anterior num único grafo de cena;
2. Construção (Rendering): No espaço do dispositivo, com base no modelo do ponto anterior e das definições da vista;

A construção assenta num conjunto de operações (por exemplo, clipping) que, normalmente, são automaticamente tratadas pelo sistema gráfico em que se está a trabalhar.

Sobre a modelação falta esclarecer:

• Como cada objeto gráfico é definido no seu espaço;
• Como esse objeto é «transportado» para o espaço do mundo;

As Transformações são as principais ferramentas nestes passos. Neste capítulo vamos ilustrar o papel que desempenham.

Transformações: Representação Matricial e Casos Especiais

Uma transformação é uma função que aplica pontos em pontos:

$$p=(p_x,p_y)\stackrel{T}{⟶}q=(q_x,q_y)$$

Os tipos principais de transformações são:

• Translação: $q=(q_x,q_y)$ resulta de mover $p=(p_x,p_y)$ segundo uma certa direção;

• Rotação: $q=(q_x,q_y)$ resulta de rodar $p=(p_x,p_y)$ um certo ângulo em torno da origem;p_0 =

• Escala: $q=(q_x,q_y)$ resulta de aumentar ou reduzir $p=(p_x,p_y)$ por um certo fator;

• Composição: $q=(q_x,q_y)$ resulta de aplicar a $p=(p_x,p_y)$ uma sequência de transformações;

Adicionalmente ainda podem ser usadas reflexões (em relação a um certo eixo ou ponto) e deslizamentos (numa certa direção).

A escolha destes quatro tipos de transformações principais assenta nas seguintes razões:

• são suficientemente expressivos para a maior parte das necessidades da computação gráfica;
• são intuitivamente acessíveis;
• são numericamente eficientes;

A eficiência numérica assenta na forma como os cálculos são efetuados: as coordenadas transformadas $(q_x,q_y)$ resultam de multiplicar as coordenadas originais $(p_x,p_y)$ por uma matriz de transformação:

$$\left[\begin{array}{c}{q}_x\\ q_y\\ 1\end{array}\right]=\left[\begin{array}{ccc}a& b& c\\ d& e& f\\ 0& 0& 1\end{array}\right]\left[\begin{array}{c}{p}_x\\ p_y\\ 1\end{array}\right]$$

Os valores concretos dos parâmetros a,b,c,d,e,f dependem da transformação concreta que se pretende aplicar às coordenadas originais.

Nas páginas seguintes vamos ver como esses valores também dependem do tipo de transformação.

Translações

Exemplo de uma Translação

Uma translação consiste em mover as coordenadas originais $p=(p_x,p_y)$ segundo um certo vetor $d=(d_x,d_y)$ de forma que $$q=p+d.$$

Isto é, as coordenadas transformadas são obtidas por $$(q_x,q_y)=q=p+d=(p_x,p_y)+(d_x,d_y)$$

A matriz de translação é

$$\begin{array}{rl}T(d_x,d_y)& =\left[\begin{array}{ccc}1& 0& d_x\\ 0& 1& d_y\\ 0& 0& 1\end{array}\right]\end{array}$$

e temos

$$\begin{array}{rl}(q_x,q_y,1)& =T(d_x,d_y)\left[\begin{array}{c}{p}_x\\ p_y\\ 1\end{array}\right]\end{array}$$

Rotações

Exemplo de uma Rotação

Uma rotação consiste em rodar as coordenadas originais $(p_x,p_y)$ segundo um certo ângulo $\alpha$ em torno da origem $(0,0)$.

A matriz de rotação é

$$\begin{array}{rl}R(\alpha )& =\left[\begin{array}{ccc}\cos \alpha & \sin \alpha & 0\\ -\sin \alpha & \cos \alpha & 0\\ 0& 0& 1\end{array}\right]\end{array}$$

e temos

$$\begin{array}{rl}(q_x,q_y,1)& =R(\alpha )\left[\begin{array}{c}{p}_x\\ p_y\\ 1\end{array}\right]\end{array}$$

Escalas

Exemplo de uma Escala

Uma escala consiste em encolher ou esticar as coordenadas originais $(p_x,p_y)$ segundo um certo fator $(s_x,s_y)$.

A matriz de escala é

$$\begin{array}{rl}S(s_x,s_y)& =\left[\begin{array}{ccc}{s}_x& 0& 0\\ 0& s_y& 0\\ 0& 0& 1\end{array}\right]\end{array}$$

e temos

$$\begin{array}{rl}(q_x,q_y,1)& =S(s_x,s_y)\left[\begin{array}{c}{p}_x\\ p_y\\ 1\end{array}\right]\end{array}$$

Composição

Nem sempre as transformações básicas são suficientes para construir os objetos gráficos pretendidos.

Nesse caso é necessário compor as transformações básicas de forma a obter-se o efeito pretendido.

Motivação da composição

Exemplo de uma Composição

Supondo que se pretende escalar e rodar um certo objeto gráfico, sem o deslocar da posição em que está. O problema está na rotação, quo o feita em torno da origem do referencial, e não em torno do «centro do objeto».

A solução consiste em compor várias transformações de forma a obter-se o efeito pretendido. Geometricamente:

1. Colocamos o referencial no «centro» do objeto, com uma translação.
2. Com o referencial no «centro» do objeto, fazemos as operações de escala e de rotação.
3. Repomos o referencial na posição em que estava inicialmente, de novo com uma translação.

Explore transformações com o seguinte código SVG:

Transformações

Gráficos 3D

Conceitos Fundamentais 3D

A Computação Gráfica 3D trata o problema da visualização a 2D de modelos 3D. Estes são compostos por objetos gráficos, fontes de luz e câmaras.

Um sistema gráfico 3D tem de resolver os muitos problemas derivados da representação dos objetos, das transformações, da organização e da construção da cena.

Funções de um Sistema Gráfico 3D

• Definir a geometria dos objetos gráficos.
• Aplicar transformações geométricas, aos objetos e às câmaras para os localizar e posicionar.
• Definir o aspeto (usando Texturas e Materiais) dos objetos.
• Iluminar a cena.
• Definir a vista (usando propriedades como projeção, localização, atitude, abertura, etc) do modelo.

Geometria 3D

Geometria de um rosto

Tipos de Geometrias

A geometria de um objeto 3D pode ser aproximada por várias técnicas.

Formas Básicas

Cubos, esferas, pirâmides, cones, etc.

As formas básicas são proporcionadas «diretamente» pelo sistema gráfico.

Geometrias Parametrizadas

Um cilindro é o rasto que uma circunferência deixa quando se desloca ao longo de um segmento de reta perpendicular ao plano da circunferência.

Certas formas podem ser definidas por um pequeno conjunto de parâmetros e objetos auxiliares e são proporcionadas por «funções» do sistema gráfico.

Conjuntos de Faces

Um rosto, o relevo de um terreno.

Formas mais irregulares têm de ser construídas definido individualmente as coordenadas dos vértices de uma rede de polígonos.

Além destas formas de construção de geometrias «estáticas» também são usadas técnicas que deformam a geometria inicial e que envolvem «esqueletos» e/ou «morphing». Estes técnicas não constam do programa deste curso.

Geometria construída

A geometria de um barco, construida a partir de proa, uma quilha e uma popa.

A popa e a proa são transformadas para se ajustarem à quilha. A quilha é uma extrusão, a proa é um conjunto de faces e a proa é uma transformação da popa.

Além das formas básicas, em geral estão disponíveis outras métodos para definir a geometria dos objetos gráficos.

Os métodos principais para construir geometrias são:

• As geometrias parametrizadas; em particular, extrusões.
• Os conjuntos de faces.

Exemplo/Aplicação da construção de geometrias.

Vamos ilustrar estes dois métodos construindo um objeto que usa ambos. O casco de um barco tem três partes:

• A proa (bow), usando um conjunto de faces.
• A quilha (keel), com uma extrusão.
• A popa (stern), transformando a proa.

Extrusões

Peças de alumínio feitas por extrusão (fonte: Wikipedia)

A secção transportada ao longo da espinha gera uma geometria 3D :

Exemplos de extrusões

• [2D] Um segmento é o rasto dum ponto quando se movimenta «a direito».
• [2D] Um quadrado é o rasto dum segmento quando se movimenta «a direito»
• [2D] Um círculo é o rasto dum segmento quando roda em torno dum ponto.
• [3D] Um cubo é o rasto dum quadrado ao longo dum segmento.
• [3D] Um cilindro é o rasto duma circunferência ao longo dum segmento.

Parâmetros das extrusões

Uma extrusão é definida por:

• A secção
  • Uma superfície 2D assente no plano Y=0.
  • Por exemplo, uma circunferência, um disco, um «L».
• A espinha
  • Uma sequência de pontos no espaço 3D.
• Parâmetros adicionais
  • Parâmetros específicos de cada sistema gráfico, que controlam pormenores do rendering desta geometria.
  • Por exemplo, no sistema X3D as extrusões podem ter rotações e escalas definidas ao longo da espinha.

Estes parâmetros definem uma geometria de acordo com o seguinte processo:

1. A secção, que é definida no plano Y=0 é «transportada» para o primeiro ponto da espinha e orientada para o ponto seguinte.
2. Da mesma forma, a secção é colocada no segundo ponto da espinha.
3. Os vértices correspondentes da primeira e da segunda secções são ligados, formando um quadrilátero entre cada par de vértices.
4. Este processo é depois repetido para o resto dos pontos da espinha, resultando numa superfície de extrusão («arrasto») ao longo da espinha.

Conjuntos de Faces

Aproximações de uma geometria por conjuntos de faces
fonte: Artigo «Computer Graphics (computer science)» na Wikipédia

Formas pouco regulares (por exemplo, um rosto ou um terreno) têm de ser construídas definido individualmente as coordenadas dos vértices e ligando esses vértices para formar faces (triângulos ou quadriláteros).

Parâmetros dos conjuntos de faces

Um conjunto de faces é definido por:

• Os vértices
  • Um ponto no espaço 3D, dado pelas suas coordenadas x, y, z.
  • Em geral os vértices são «arrumados» numa lista e referenciados pelo seu índice nessa lista.
• As faces
  • Uma lista de três (ou, no caso do X3D, mais) vértices.
  • Normalmente é usado o índice na lista dos vértices, em vez das coordenadas.

Regra da mão direita

Um aspeto importante na definição de uma face é a ordem em que os (índices dos) vértices são dados.

Dados três pontos no espaço 3D, A, B, C, a face «para cima» é definida pela regra da mão direita. Se os pontos forem dados pela ordem A, C, B então a face «para cima» é oposta.

Quando esta regra é esquecida o resultado típico são «faces invisíveis».

Aspeto 3D

Efeito da iluminação na perceção de um objeto

A luz é refletida segundo um certo ângulo tangente à superfície do objeto no ponto onde incide:

• O ângulo é determinado pelas normais (que dependem da geometria do objeto).
• As cores somam a cor própria do objeto à cor da luz incidente.
• Os reflexos definem quanta luz incidente é refletida pelo objeto.

O aspeto percecionado de um objeto depende:

• Da iluminação da cena.
• Da textura desse objeto.

Parâmetros das texturas

As texturas (ou materiais) são propriedades do objeto que contribuem para a sua perceção e definem como o objeto é «pintado» e como transforma a luz.

• Cores (difusão: diffuse)
  • São as cores próprias do objeto: luz refletida = cor do objeto + luz incidente.
  • Por exemplo, um cubo laranja difunde a cor laranja e um cubo verde difunde verde.
• Reflexos (specular)
  • Determinam a quantidade de luz refletida: luz refletida = reflexo _ luz incidente.
  • Por exemplo, um cubo brilhante reflete quase toda a luz que recebe, enquanto que um cubo baço quase não reflete a luz que recebe.
• Normais (normals)
  • Dependem da geometria do objeto e determinam a direção da luz refletida: ângulo da luz refletida = normal + ângulo da luz incidente.
  • Por exemplo, num cubo liso as normais são perpendiculares às faces mas num cubo rugoso as normais têm desvios da perpendicular.

Tipos de iluminação

A iluminação resulta de um conjunto de propriedades do modelo (da cena) que contribuem para a perceção dos vários objetos nesse modelo.

As fontes de Luz definem propriedades como «cor emitida», «atenuação», etc e, em geral, incluem os seguintes tipos:

• Luz Ambiente
  • Incide igualmente em todos os objetos gráficos, independentemente da posição ou pose.
• Ponto de Luz
  • Emite luz em todas as direções, a partir de uma certa posição.
  • Por exemplo, uma lâmpada numa sala.
• Foco
  • Emite um cone de luz (com uma certa orientação) a partir de uma certa posição.
  • Por exemplo, um projetor numa secretária.
• Direcional
  • Emite luz em «raios paralelos» a uma certa orientação.
  • Por exemplo, o sol a iluminar uma cena na superfície da terra.

Mapas de texturas

Não é viável definir-se ponto-a-ponto os parâmetros de textura numa geometria. Em vez disso, usam-se imagens especiais, os mapas de textura, para aplicar cores, reflexos e normais a uma geometria.

Vejamos o efeito que cada caraterística das texturas tem na perceção (e realismo) do objeto seguindo um exemplo: o planeta terra.

Modelo da terra: geometria

A geometria da terra é (aproximadamente) uma esfera, e vamos supor que na cena há um ponto de luz razoavelmente afastado, de forma a simular o sol.

Modelo da terra: difusão

A difusão define as cores «próprias» do objeto: luz refletida = cor do objeto + luz incidente.

Difusão da terra
Uma imagem com as cores da superfície da terra

Para pintar «num passo» todas as cores da superfície da esfera usa-se uma textura para a difusão das cores.

Modelo da terra: reflexos

Os reflexos determinam a quantidade de luz refletida: luz refletida = reflexo * luz incidente.

Reflexos da terra
Uma imagem com os reflexos da superfície da terra

Para pintar «num passo» todos os reflexos na superfície da esfera usa-se uma textura para a reflexão das cores.

Nestas texturas branco significa «reflete 100%», preto significa «reflete 0%» e tons intermédios refletem percentagens intermédias.

A principal diferença em relação aos mapas de difusão «simples» está nas zonas que devem brilhar. Por exemplo, nas zonas com água (rios, lagos, mares, oceanos) pode ver-se o reflexo do «sol» enquanto que nas zonas «de terra» não há grandes diferenças.

Modelo da terra: normais

As normais determinam a direção da luz refletida: ângulo da luz refletida = normal + ângulo da luz incidente.

Normais da terra
Uma imagem com as normais da superfície da terra

Para pintar «num passo» as normais à superfície da esfera usa-se uma textura para as normais.

Representação das normais por uma imagem

Uma normal é um vetor no espaço 3D e, como tal, tem três componentes, xyz.

Uma cor também tem três componentes, RGB, e nestes mapas uma cor RGB representa um vetor xyz associando: R → x, G → y, B → z.

Mapas UV

A aplicação de uma textura à geometria tem de ser controlada, de forma a aplicar as partes corretas da textura às faces da geometria. Esse controlo é definido por um mapa UV.

Aplicação das texturas por faces

Uma textura para um dado

As texturas definidas por imagens são uma forma conveniente de refinar o aspeto de um objeto gráfico.

Para funcionar corretamente, é preciso controlar como cada setor da textura é associado a cada face da geometria do objeto.

As coordenadas uv são usadas para posicionar os pontos da textura:

• Usa-se «uv» em vez de «xy» para evitar confusões com as coordenadas xyz da geometria.
• O referencial uv é adaptado de forma a que toda a imagem da textura fique no quadrado $(0,0)-(1,1)$.

Pontos e setores de uma textura
Cada setor (amarelo) é definido por pontos uv (vermelhos)
O setor 4 é definido pelos pontos uv 4, 5, 10, e 9
O ponto 0 tem coordenadas uv $(0,0)$; O ponto 9 tem coordenadas uv $(0.5,0.66)$

Especificamente:

• Os vértices estão na geometria 3D
  • Têm coordenadas xyz.
• As faces estão na geometria 3D
  • Definem-se com listas de índices de vértices.
• Os pontos estão na textura 2D
  • Têm coordenadas uv.
• Os setores são «pedaços» da textura 2D
  • Definem-se com listas de índices dos pontos.

A aplicação de mapas UV é adequado a geometrias definidas por conjunto de faces onde os vértices e as faces estão explicitamente indicados.

Processo para definir um mapa UV

O processo para ilustrar a aplicação dos mapas UV é o seguinte:

1. Definir os vértices e a lista de faces da geometria 3D.
2. Definir os pontos e a lista de setores da textura 2D.
3. O primeiro setor é aplicado à primeira face, etc.

Regra da mão direita. Na definição dos setores, 7 8 3 2 não é o mesmo que 7 8 2 3.

Tem de usar a regra da mão direita para se determinar o lado da face como uma página numa folha de papel.

Transformações 3D

Investigação da perspetiva (gravura de Albrecht Dürer, 1525)
Representação 2D de um objecto 3D

São usados dois tipos de transformações num sistema gráfico 3D:

• Transformações afins. Alteram o tamanho, posição e orientação de objectos no espaço 3D.
  • São geralmente usadas no espaço do mundo ou do objeto e generalizam as transformações dos sistemas gráficos 2D. São usadas para posicionar, rodar e escalar os objetos gráficos.
• Projeções. Produzem a vista 2D do modelo 3D.
  • Estão associadas a câmaras e são usadas para definir a vista da cena, isto é, a transformação espaço 3D do modelo → espaço 2D do dispositivo.

Parâmetros de vistas e de câmaras

Uma vista de uma cena é obtida fazendo uma certa projeção do modelo, precisamente da mesma forma que uma câmara fotográfica produz uma imagem 2D de um ambiente 3D.

A projeção que define a vista é normalmente designada câmara e depende de um conjunto de parâmetros. Os mais comuns são:

• Tipo

  • Tipo da projeção (ortográfica, projetiva, etc depende do sistema gráfico).

• Abertura (FOV)

  • Ângulo de captura (depende do tipo de câmara).

• Proporção (Ratio, Aspect)

  • Relação entre a altura e a largura (depende do tipo de câmara).

• Perto (Near)

  • Distância do plano de corte «perto».

• Longe (Far)

  • Distância do plano de corte «longe».

Animação

Com animação uma cena estática ganha vida e torna-se mais informativa e interessante.

A animação resulta de mostrar imagens, os fotogramas (em inglês frames) em rápida sucessão: Animação = Imagem x Tempo.

Animação por Fotogramas

O número de fotogramas e de FPS são fixos.

Por exemplo: 480 fotogramas a 24 FPS proporcionam uma animação (um filme) com 20 segundos de duração.

O limiar perceção humana anda perto dos 24FPS.

• Se os fotogramas forem substituídos a um ritmo de 24 por segundo, a maioria das pessoas não distingue a passagem de um fotograma para o seguinte e interpreta «o que está a ver» como um movimento fluído.
  • Na realidade, 24 fotogramas por segundo está demasiado perto do limiar de perceção e a esta frequência muitas pessoas apercebem-se da substituição dos fotogramas.
• Os primeiros filmes foram filmados e projetados entre 16FPS e 24FPS.
• A frequência «padrão» 24FPS foi adotado no início da computação gráfica.
• Atualmente as placas gráficas proporcionam facilmente 60+FPS.

Uma animação por fotogramas é feita para uma certo número de FPS e não resulta bem com FPS diferentes.

• O número de FPS pode variar em função do dispositivo, da "carga", etc.

A animação por tempo resolve o problema das diferenças de frequências na animação por fotogramas.

Animação por tempo

A animação por tempo resulta de definir chaves (keys): Os valores de certos parâmetros em determinados instantes.

Por exemplo: A posição x = 1 no instante t = 0 e x = 2 no instante t = 2.

É necessário calcular automaticamente os valores intermédios dos parâmetros que controlam uma animação.

Por exemplo:

• A posição de objeto é definida pelo parâmetro x.
• É data a posição inicial: x = 1 quando t = 0.5.
• E a posição final: x = 2 quando t = 2.5.
• Sempre que necessário, pretende-se calcular as posições intermédias desse objeto.

const keys = [
  {
    t: 0.0,
    parameters: {  x: 1.00  }
  },
  {
    t: 2.0,
    parameters: {  x: 2.00  }
  }
];

Processo da Animação por Tempo

1. São definidas chaves (keys) específicas.

• Cada chave define um instante e valores de parâmetros.

2. Durante a animação:

• Os valores dos parâmetros são recalculados sempre que necessário.
• O modelo gráfico é atualizado com os novos valores dos parâmetros e construído/desenhado de novo.

A animação por tempo resolve o problema das diferenças de frequências que a animação por fotogramas coloca.

Sempre que o sistema gráfico está pronto para mostrar um novo fotograma, os valores dos parâmetros são recalculados; o modelo gráfico é atualizado com os novos valores dos parâmetros e desenhado de novo.

Isto significa que a definição de uma animação é feita através de modelo e esse modelo tem parâmetros que definem cada «fotograma» na sequência.

Modelos e Parâmetros

• Modelo
  • Conjunto de variáveis (parâmetros) que definem cada «fotograma» na sequência.
• Parâmetro
  • Variável que define um elemento da animação.

Exemplos de Modelos e Parâmetros

1. Um quadrado vermelho desloca-se da esquerda para a direita. Neste caso o modelo necessita apenas de um parâmetro, a abcissa ($x$) do quadrado:

   const model = { x: 0 };
   

2. Um quadrado vermelho desloca-se na horizontal e na vertical. O modelo necessita de dois parâmetros, a abcissa ($x$) e a ordenada ($y$) do quadrado:

   const model = { x: 0, y: 0 };
   

3. Um quadrado desloca-se na horizontal, na vertical e pode mudar de cor:

   const model = { x: 0, y: 0, color: 'crimson' };
   

4. Vários quadrados deslocam-se na horizontal, na vertical e podem mudar a cor:

   const model = { my_squares: [
     { x: 0, y: 0, color: 'crimson' },
     { x: 0, y: 8, color: 'khaki' }
   ] };
   

Tweens

Os tweens (contração do inglês «in-between») assentam uma técnica simples mas flexível e eficiente para:

• calcular os valores intermédios entre
• um valor inicial $x_I$ e
• um valor final $x_F$ durante
• um certo intervalo de tempo $[t_I,t_F]$.

O valor intermédio, $x_t$, quando $t_I\le t\le t_F$, é calculado usando a fórmula: $$x_t=\frac{(t_F-t)x_I+(t-t_I)x_F}{t_F-t_I}$$

Um tween atualiza, ao longo de um certo intervalo de tempo $[t_I,t_F]$, um valor $x_t$ que varia de $x_I$ quanto $t=t_I$ para $x_F$ quando $t=t_F$.

Os parâmetros fundamentais de um tween são:

• Valor Inicial ($x_I$)
  • Em que valor começa a variação do parâmetro.
• Valor Final ($x_F$)
  • Em que valor termina a variação do parâmetro.
• Tempo Inicial ($t_I$)
  • Em que instante começa a variação do parâmetro.
• Tempo Final ($t_F$) ou Duração ($d$)
  • Em que instante termina a variação (tempo final) ou quanto tempo demora a variação (duração). A relação entre o tempo inicial, o tempo final e a duração é: $$d=t_F-t_I$$

Os tweens são usados para fazer animações com modelos parametrizados.

Tipos de Tweens

Os tweens descritos acima são lineares: a variação do parâmetro é proporcional ao tempo decorrido.

function draw(c, m) {
  c.fillStyle = "steelblue";
  c.fillRect(0, 0, 480, 120);
  c.fillStyle = "crimson";
  c.fillRect(m.linear.x, 10, 40, 40);
  c.fillStyle = "khaki";
  c.fillRect(m.nonlinear.x, 70, 40, 40);
}

const context = document
    .getElementById("anim:tween:1")
    .getContext("2d");

const model = {
  linear: {x:  10,},
  nonlinear: {x: 10}
};

const linear = new TWEEN.Tween(model.linear)
    .to({x: 430}, 2000)
    .easing(TWEEN.Easing.Linear.None)
    .yoyo(true)
    .repeat(Infinity)
    .start();

const cubic = new TWEEN.Tween(model.nonlinear)
    .to({x: 430}, 2000)
    .easing(TWEEN.Easing.Quadratic.InOut)
    .yoyo(true)
    .repeat(Infinity)
    .start();

const step = function(ctx, mdl) {
    TWEEN.update();
    draw(ctx, mdl);
    requestAnimationFrame(function () {
      step(ctx, mdl)
    });
  }

step(context, model);

Para animações com «objetos naturais» este tipo de tween não funciona bem porque produz movimentos uniformes, com velocidade constante.

• O resultado é semelhante ao movimento dos robots nos filmes antigos, ou de segunda categoria e também de alguns estilos de dança.

Os movimentos naturais não são lineares. Alguns aceleram no início e travam no fim. Outros têm uma fase de «ganhar balanço». As variantes são muitas.

• Easing define a aceleração de um tween e, em geral, tem as algumas variantes bem definidas.
• Ease-In tipo de aceleração no início da variação.
• Ease-Out tipo de aceleração no fim da variação.

Suporte para Tweens

A biblioteca tween.js proporciona um sistema flexível e eficiente para definir e usar tweens. Os tweens desta biblioteca:

1. São construídos com um valor inicial, um valor final e uma duração.
2. Aceitam uma grande variedade de easings.
3. Podem ser operados de várias formas:
   • yoyo: depois de atingir o valor final, o tween volta ao inicial.
   • repetir: o tween é repetido um certo número de vezes.
   • encadear: aplicar um segundo tween após a conclusão do primeiro.
   • etc.

O Ciclo de Animação

Qualquer animação é um ciclo infinito de atualização (update) e construção (render) de um modelo.

Os ciclos de animação e o uso dos tweens têm essencialmente a mesma estrutura e podem ser facilmente unificados.

const m = initial_model();
while (true) {
    m.update();
    m.render();
}

const t = TWEEN.Tween(...) ... ;
t.start();
while (true) {
    t.update();
    const x = t.value();
    ...
}

Programação Web e Ciclos Infinitos

function draw(context, model) {
  /// Desenha o modelo atualizado no contexto fornecido.
}

function update(model) {
  // Por exemplo, usando TWEEN.update();
}

const model = {
  // valores iniciais dos parâmetros;
};

const step = function(ctx, mdl) {
    update(mdl);    // Atualiza os parâmetros do modelo.
    draw(ctx, mdl); // Desenha o modelo atualizado.
    requestAnimationFrame(function () { // Repete o ciclo de animação.
      step(ctx, mdl)
    });
  }

step(context, model); // Inicia o ciclo de animação.

A razão para fazer o ciclo de animação com a função requestAnimationFrame é que, desta forma, o navegador pode pausar a execução do código JavaScript quando necessário.

Na versão seguinte versão alternativa, o ciclo de animação é implementado usando um ciclo while infinito que bloqueia o navegador e portanto, deve ser evitado.

function draw(context, model) {
  /// Desenha o modelo atualizado no contexto fornecido.
}

function update(model) {
  // Por exemplo, usando TWEEN.update();
}

const model = {
  // valores iniciais dos parâmetros;
};

// BAD BAD NOT GOOD
while (true) {  // ** O NAVEGADOR FICA BLOQUEADO AQUI **
  update(model);        // Atualiza os parâmetros do modelo.
  draw(context, model); // Desenha o modelo atualizado.
}

Animação por passos

Embora flexíveis, nos tweens todos os valores estão determinados antes da animação começar. Uma vez iniciado, o tween vai seguir um «percurso» fixo, previsível.

Quando a animação dum objeto depende doutros objetos ou eventos, é necessário ir além dos tweens.

Por exemplo:

• Com movimentos baseados na física é preciso tratar da aceleração, colisões com outros objetos, etc.
• Os comportamentos reativos («seguir ...», «olhar para ...», etc) dependem dos valores de outros objetos.
• Os objetos controlados por interação (do teclado, rato, etc) dependem de valores externos ao próprio modelo.

m = initial_model();  // Inicialização do modelo
while (true) {        // Ciclo de animação
    m.update()          // Atualizar o modelo
    m.render()          // Construir a imagem
}

A estrutura básica da animação por tempo, com modelos parametrizados e o ciclo seguinte é válida em geral: a animação resulta da variação dos parâmetros calculada na atualização, quer esta variação resulte de tweens ou de outros cálculos.

Atualização Dinâmica

Intervalo entre fotogramas consecutivos
A atualização dos parâmetros adaptar-se ao intervalo entre fotogramas consecutivos.

Quando o tempo decorrido entre dois fotogramas não é constante, a atualização dos parâmetros do modelo tem de adaptar-se a essa variação.

Os tweens fazem automaticamente esta adaptação: O «valor» do tween é atualizado «internamente».

Para animações gerais, é necessário proporcionar, ao ciclo de animação, informação sobre o tempo: A forma universal e prática para lidar com a variação do tempo no ciclo da animação consiste em passar informação temporal para guiar a atualização dos parâmetros do modelo.

Revisitar o Ciclo de Animação

A função requestAnimationFrame é o elemento fundamental das animações na web (veja a documentação completa em MDN).

window.requestAnimationFrame(callback)

• A função indicada como argumento (callback) é «chamada» cada vez que o sistema (por exemplo, o browser) está pronto para iniciar um novo passo da animação.
• Quando a função callback é «chamada» recebe um único argumento, timestamp que assinala esse preciso momento.

function render(element, model) {
  const count   = model.count;
  const time    = Math.round(model.time * 0.001);
  const elapsed = Math.round(model.elapsed);
  const fps     = Math.round(1000 * model.count / model.time);
  element.innerHTML = `<table>` +
    `<tr><td>Count</td><td>Time</td><td>Elapsed (dt)</td><td>FPS</td></tr>` +
      `<tr>` +
      `<td> ${count} </td>` +
      `<td> ${time}s </td>` +
      `<td> ${elapsed}ms </td>` +
      `<td> ${fps} </td>` +
      `</tr>` +
  `</table>`;
}

let element = document.getElementById("anim:steps:counter");
let model = {
    count: 0, time: 0, elapsed: 0
};

let start_time = performance.now();
let last_time = performance.now();

animation_step = function (timestamp) {
    let progress = timestamp - start_time;
    let elapsed = timestamp - last_time;
    last_time = timestamp;
    model.count += 1;
    model.time = progress;
    model.elapsed = elapsed;
    render(element, model);
    requestAnimationFrame(animation_step);
}

requestAnimationFrame(animation_step);

Exemplo: Movimentos Baseados na Física

Para ilustrar uma aplicação da animação por passos usamos uma (simples) simulação física do movimento uniformemente acelerado.

Esta animação não é possível usando apenas tweens porque as colições e as interações modificam o modelo de formas que não podem ser antecipadas.

const model = {
    x: 64, y: 64,           //  ball position
    vx: 0, vy: 0,           //  ball velocity
    ax: 0, ay: 0,           //  ball acceleration
    r: 16,                  //  ball radius
    min_x: 0, max_x: 256,   //  box bounds: x
    min_y: 0, max_y: 256,   //  box bounds: y
    G: 0.25e-3, D: 0.8,     //  physics constants
    K: 0.8,                 //  kick strength
    kick: true,             //  kick flag
};

// Record time of the animation start
const start = performance.now();

// Record time of the previous step
let prev_ts = performance.now();

// Record time of the step start
const start_ts = performance.now();

// Animation step function
const step = function (ts) {
  const dt = ts - prev_ts;
  prev_ts = ts;

  // update acceleration
  if (model.kick) {   // KICK
      model.ax = model.K * linmap(model.x, model.min_x, model.max_x, -1, 1);
      model.ay = model.K * linmap(model.y, model.min_y, model.max_y, -1, 1);
      model.kick = false;
  } else {                // NO KICK
      model.ax = 0.0;
      model.ay = model.G; // gravity
  }

  // update velocity
  model.vx = model.vx + model.ax * dt;
  model.vy = model.vy + model.ay * dt;

  // update position
  model.x = model.x + model.vx * dt;
  model.y = model.y + model.vy * dt;

  // check collisions
  if (model.x - model.r < model.min_x) {
    model.vx = -model.D * model.vx;
    model.x = model.min_x + model.r;
  }
  if (model.x + model.r > model.max_x) {
    model.vx = -model.D * model.vx;
    model.x = model.max_x - model.r;
  }
  if (model.y - model.r < model.min_y) {
    model.vy = -model.D * model.vy;
    model.y = model.min_y + model.r;
  }
  if (model.y + model.r > model.max_y) {
    model.vy = -model.D * model.vy;
    model.y = model.max_y - model.r;
  }

  // Render the model in the graphics system
  render(context, model);
  requestAnimationFrame(step);
}
requestAnimationFrame(step);
}

Exercícios

Desenho original por Enki Bilal

Exercícios Javascript

Funções geradoras

Funções que geram coleções de valores.

Uma coleção é uma estrutura de dados que armazena ou produz valores, como arrays ou listas.

Por exemplo:

const numbers = [1, 2, 3, 4];

1. Escreva uma função repete(x, n) que devolve um array com n cópias de x.
2. Escreva uma função aleatorios(n) que devolve um array com n números aleatórios.
3. Escreva uma função intervalo(a, b) que devolve um array com os números inteiros entre a e b incluindo ambos os extremos. Se b < a o resultado deve ser a lista vazia [].
4. Escreva uma função linspace(a, b, n) que enche um array com n números reais (float) entre a e b, igualmente espaçados.
   • Por exemplo linspace(0, 1, 3) devolve [0.0, 0.5, 1.0].

Filtros

Funções que selecionam elementos de uma coleção.

Em geral, a seleção pode ser feita por meio de condições booleanas.

Por exemplo:

const even_numbers = numbers.filter(x => x % 2 === 0);
// [2, 4]

1. Escreva uma função pares(x) que tem como argumento um array x de números inteiros e que devolve um array apenas com os números pares.
   • Por exemplo pares([1, 2, 4, 5, 2, 3]) devolve [2, 4, 2].
2. Escreva uma função positivos(x) que tem como argumento um array x de números reais e que devolve um array apenas com os números positivos.
   • Por exemplo positivos([1, -2.5, 0.4, 0.0, -1.5, 2, 2.3]) devolve [1, 0.4, 2, 2.3].
3. Escreva uma função limite_sup(x, a) que tem como argumentos um array x de números reais e um valor a e que devolve um array apenas com os números menores ou iguais que o valor a.
   • Por exemplo limite_sup([1, -2.5, 0.4, 0.0, -1.5, 2, 2.3], 0.4) devolve [-2.5, 0.4, 0.0, -1.5].
4. Escreva uma função filtro(f, x) que tem como argumentos uma função f: float -> boolean e um array x de números reais e que devolve um array apenas com os números xi de x tais que f(xi) === true.
   • Por exemplo filtro(x => x % 2 === 0, [1, 2, 4, 5, 2, 3]) devolve [2, 4, 2]. Quais das alíneas acima consegue tornar a resolver usando esta função?

Mapas

Funções que transformam elementos de uma coleção.

Em geral, a transformação pode ser feita por uma função que aplica um valor num outro valor.

Por exemplo:

const square_numbers = numbers.map(x => x ** 2);
// [1, 4, 8, 16]

1. Escreva uma função dobro(x) que tem como argumento um array x de números reais e que devolve um array com os dobros desses números.
   • Por exemplo dobro([1, 2.1, 4, 5, -2, 3]) devolve [2, 4.2, 8, 10, -4, 6].
2. Escreva uma função quadrado(x) que tem como argumento um array x de números reais e que devolve um array com os quadrados desses números.
   • Por exemplo quadrado([1, -2.5, 0.4]) devolve [1, 6.25, 0.16].
3. Escreva uma função unicos(x) que tem como argumento um array x de números reais e que devolve um array sem valores repetidos.
   • Por exemplo quadrado([1, -2.5, 1]) devolve [1, -2.5].
4. Escreva uma função crescente(x) que tem como argumento um array x de números reais e que devolve um array com os valores por ordem crescente.
   • Por exemplo crescente([1, -2.5, 1]) devolve [-2.5, 1, 1].
5. Escreva uma função estender(x, n) que tem como argumento um array x de números reais e um valor inteiro n e que devolve um array exatamente de comprimento n. Se o comprimento de x for menor que n devem ser acrescentados zeros suficientes. Se o comprimento de x for maior que n os valores a mais são descartados.
   • Por exemplo estender([1, -2.5], 4) devolve [1, -2.5, 0, 0], e estender([1, 6.25, 0.16], 2) devolve [1, 6.25].
6. Escreva uma função mapa(f, x) que tem como argumentos uma função f: float -> float e um array x de números reais e que devolve um array com números yi = f(xi) em que x = [ ..., xi, ...].
   • Por exemplo mapa(x => 2 * x, [1, 2.1, 4, 5, -2, 3]) devolve [2, 4.2, 8, 10, -4, 6]. Quais das alíneas acima consegue tornar a resolver usando esta função?

Combinações

Funções que combinam uma ou várias coleções numa coleção nova.

Por exemplo:

const descending_numbers = numbers.reverse();
// [4, 3, 2, 1]
const seesaw = numbers.concat(descending_numbers);
// [1, 2, 3, 4, 4, 3, 2, 1]

1. Escreva uma função inverte(x) que tem como argumentos o array x de números reais e que devolve um array com os valores de x por ordem inversa (do último para o primeiro).

2. Assegure-se que x = cadeia(cabeca(n, x), cauda(n, x)) para qualquer x e qualquer n, em que:

   1. A função cadeia(x, y) tem como argumentos dois array x, y de números reais e devolve um array com os valores de x seguidos pelos valores de y.
      • Por exemplo cadeia([1, 2.1, 4], [5, -2, 3]) devolve [1, 2.1, 4, 5, -2, 3].
   2. A função cabeca(n, x) tem como argumentos o int n e o array x de números reais e devolve o array dos primeiros n valores de x.
   3. A função cauda(n, x) tem como argumentos o int n e o array x de números reais e devolve o array com os valores de x a partir do n-ésimo elemento.

3. Escreva uma função somar(x, y) que tem como argumentos dois array x, y de números reais e que devolve um array com os valores de x somados aos valores de y pela mesma ordem. Se os argumentos tiverem comprimentos diferentes o resultado deve ser a lista vazia: [].

   • Por exemplo somar([1, 2.1, 4], [5, -2, 3]) devolve [6, 0.1, 7] e somar([1, 2], [3]) devolve [].

4. Escreva uma função emparelhar(x, y) que tem como argumentos dois array x, y de números reais e que devolve um array com objetos {x: xi, y: yi} onde xi, yi estão nas mesmas posições de x, y. Se os argumentos tiverem comprimentos diferentes o resultado deve ser a lista vazia: [].

   • Por exemplo emparelhar([1, 2.1, 4], [5, -2, 3]) devolve [{x: 1, y: 5}, {x: 2.1, y: -2}, {x: 4, y: 3}] e emparelhar([1, 2], [3]) devolve []. Consegue usar a função mapa do exercício anterior para resolver esta alínea?

Reduções

Funções que reduzem uma coleção a um valor.

Por exemplo:

const numbers_count = numbers.length;
// 4
Math.min(...numbers);
// 1

1. Escreva uma função conta(x) que tem como argumento um array x de números reais e que devolve o comprimento do array.
   • Por exemplo conta([1, 2, 3, 4]) devolve 4.
2. Escreva uma função soma(x) que tem como argumento um array x de números reais e que devolve a soma desses números.
   • Por exemplo soma([1, 2, 3, 4]) devolve 10.
3. Escreva uma função media(x) que tem como argumento um array x de números reais e que devolve a média desses números.
   • Por exemplo media([1, 2, 3, 4]) devolve 2.5.
4. Escreva uma função max(x) que tem como argumento um array x de números reais e que devolve o maior desses números.
   • Por exemplo max([1, 2, 3, 4]) devolve 4.
5. Escreva uma função min(x) que tem como argumento um array x de números reais e que devolve o menor desses números.
   • Por exemplo min([1, 2, 3, 4]) devolve 1.
6. Escreva uma função stats(x) que tem como argumento um array x de números reais e que devolve um sumário estatístico desses valores: um objeto com atributos count, mean, stdev, min, max. O atributo count é o comprimento de x, os valores de mean, min, max resultam das alíneas anteriores e stdev (o desvio padrão) pode ser calculado pela fórmula $$\text{stdev}(x)=\sqrt{\frac{1}{n-1}\sum (x_i-m{)}^2}$$ onde $n$ é a dimensão do vetor e $m$ a sua média.
   • Por exemplo stats([1, 2, 3, 4]) devolve {count: 4, mean: 2.5, stdev: 1.291, min: 1, max: 4}.

Álgebra Linear

Métodos numéricos fundamentais para a computação gráfica.

Por exemplo:

Um segmento pode ser definida por dois pontos, $A=(a_x,a_y)$ e $B=(b_x,b_y)$. O comprimento deste segmento resulta do produto interno através da fórmula

$$\overline{AB}=\Vert B-A\Vert =\sqrt{(B-A)\cdot (B-A)}=\sqrt{(b_x-a_x{)}^2+(b_y-a_y{)}^2}$$

1. Escreva uma função dot(x, y) que tem como argumentos dois array x, y de números reais e que devolve o produto interno dos vetores $x$ e $y$. O produto interno de $x=(x_1,\dots ,x_n)$ e $y=(y_1,\dots ,y_n)$ é $$x\cdot y=\sum x_i{y}_i$$ Se os argumentos tiverem comprimentos diferentes o resultado deve ser a lista vazia: [].
   • Por exemplo dot([1, 2, 3], [4, 5, 6]) devolve 32. Torne a resolver esta alínea usando as alíneas e exercícios anteriores.
2. Escreva uma função norma(x) que tem como argumento um array x de números reais e que devolve a norma do vetor $x$.
   • Por exemplo norma([1, 1]) devolve 1.4142135624. Lembre-se que a norma de um vetor $x=(x_1,\dots ,x_n)$ é $$\Vert x\Vert =\sqrt{\sum x_i^2}=\sqrt{x\cdot x}.$$

Exercícios 2D

Reveja a matéria de Álgebra Linear e de Geometria Analítica.

Geometria 2D

Distância de um ponto a uma reta

1. A distância ($d$) entre o ponto vermelho ($A$) e a reta azul é a distância entre o ponto vermelho ($A$) e o ponto azul ($B$).
2. O ponto azul ($B$) é a interseção entre a reta azul e a reta verde tracejada.
3. A reta verde tracejada tem equação paramétrica $X=A+\lambda u$ - falta determinar o vetor $u$.
4. O parâmetro $u$ da reta verde tracejada é perpendicular ao parâmetro $v$ da reta azul: $$u=(u_x,u_y)=(-v_y,v_x)$$

Exercício 1

Considere a equação paramétrica da reta, $X=P+\lambda v$.

Suponha que são dados dois pontos, $A=(a_x,a_y)$ e $B=(b_x,b_y)$.

Determine os valores dos parâmetros $P,v$ da reta que passa em $A,B$ e tais que:

• $A=P+\lambda v$ quando $\lambda =0$ e
• $B=P+\lambda v$ quando $\lambda =1$.

Exercício 2

Escreva uma expressão matemática para definir:

1. Os segmentos de reta $(0,0)-(0,1)$, $(0,0)-(1,0)$ e $(0,0)-(1,1)$.
2. O triângulo de vértices $(0,0)-(0,1)-(1,0)$.
3. O quadrado $(0,0)-(1,0)-(1,1)-(0,1)$.
4. O interior do quadrado e triângulo anteriores.

Exercício 3

Encontre os valores dos parâmetros da equação paramétrica:

1. Da reta:
   1. Que passa nos pontos $(0,0)$ e $(0,1)$.
   2. Que passa nos pontos $(0,0)$ e $(1,0)$.
   3. Que passa nos pontos $(0,0)$ e $(1,1)$.
2. Da reta com equação algébrica:
   1. $2x+3y-4=0$.
   2. $3x-2y-4=0$.
   3. $4x+6y-8=0$.
3. Da circunferência:
   1. Centrada em $(0,1)$ e de raio $2$.
   2. Centrada em $(1,0)$ e de raio $2$.
   3. Centrada em $(1,1)$ e de raio $2$.
   4. Centrada em $(0,1)$ e que passa no ponto $(0,0)$.
   5. Centrada em $(1,0)$ e que passa no ponto $(0,0)$.
   6. Centrada em $(1,1)$ e que passa no ponto $(0,0)$.

Programação 2D

Reveja a programação, em particular a linguagem JavaScript.

Exercício 4

Calcule os parâmetros $A,B,C$ da equação algébrica da reta ($Ax+By+C=0$), dadas as coordenadas $(x_1,y_1),(x_2,y_2)$ de dois pontos.

1. Implemente a função eqna_s(x1, y1, x2, y2) que devolve um objeto com atributos {A, B, C}.
2. Em que casos é que as entradas x1, y1, x2, y2 não definem uma reta? No seu código detete esse caso e devolva null.
3. Em que casos é que $A_1,B_1,C_1$ define a mesma reta que $A_2,B_2,C_2$? Implemente uma função equala_ss(A1, B1, C1, A2, B2, C2) que devolve true se os parâmetros definem a mesma reta e false caso contrário.

Exercício 5

Calcule os parâmetros $P,v$ da equação paramétrica da reta ($X=P+\lambda v$), dadas as coordenadas $(x_1,y_1),(x_2,y_2)$ de dois pontos.

1. Implemente a função eqnp_s(x1, y1, x2, y2) que devolve um objeto com atributos {P, v}.
2. Em que casos é que as entradas x1, y1, x2, y2 não definem uma reta? No seu código detete esse caso e devolva null.
3. Em que casos é que os parâmetros $P_1,v_1$ definem a mesma reta que os parâmetros $P_2,v_2$? Implemente uma função equalp_ss(P1, v1, P2, v2) que devolve true se os parâmetros definem a mesma reta e false caso contrário.

Exercício 6

Implemente uma função dot(x1, y1, x2, y2) para calcular o produto interno $$(x_1,y_1)\cdot (x_2,y_2)=x_1{x}_2+y_1{y}_2$$

Use essa função para implementar funções para calcular:

1. O comprimento de um vetor, length_v: $\Vert v\Vert =\sqrt{v\cdot v}$.
2. A distância entre dois pontos, dist_pp: $d(A,B)=\Vert B-A\Vert$.
3. A distância de um ponto a uma reta, dist_ps. Sugestão: Use a equação paramétrica da reta.
4. O «reflexo» de um ponto por uma reta, mirror_ps.
5. O «reflexo» de uma reta por outra reta, mirror_ss.
6. Se duas retas são perpendiculares, are_perp.

Exercício 7

Pode gerar pontos de uma circunferência usando uma equação paramétrica.

Implemente a função points_c(x1, y1, r, n) que gera uma lista com $n$ pontos equidistantes da circunferência de centro $(x_1,y_1)$ e raio $r$.

Use a função points_c para estimar a distância de uma circunferência a:

1. Um ponto: edist_cp.
2. Uma reta: edist_cl.
3. Outra circunferência: edist_cc.

Exercício 8

Pode gerar pontos de um segmento de reta usando os dois extremos do segmento e uma equação paramétrica.

Implemente a função points_s(x1, y1, x2, y2, n) que gera uma lista com $n$ pontos equidistantes do segmento limitado pelos pontos $(x_1,y_1)$ e $(x_2,y_2)$. Sugestão: Use a equação vetorial da reta: $$(x,y)=(x_1,y_1)+\lambda (x_2-x_1,y_2-y_1)$$

Estime a distância de um segmento de reta a:

1. Um ponto: edist_sp.
2. Outro segmento de reta: edist_ss.
3. Uma circunferência: edist_sc. Suponha que esta circunferência:
   1. Está definida por centro e raio.
   2. Está aproximada por um conjunto de pontos.

Exercício 9

A forma de representar as coordenadas dos pontos usada acima é muito «trapalhona».

Em vez de usar x1, y1 (ou outros indíces) use listas, P1 = [x1, y1], para representar pontos. Atualize todas as funções anteriores.

Por exemplo, x = dot(P, Q).

Exercício 10

Pode obter formas simples usando apenas conjuntos de pontos para definir o contorno do objeto gráfico.

Implemente:

1. A função join(A, B) em que A e B são listas de pontos e que devolve a lista que resulta de acrescentar os pontos de B a seguir aos pontos de A.

2. A função frame(A) que calcula os cantos superior esquerdo e inferior direito dos pontos em A, isto é, a moldura para os pontos de A.

3. A função min_circ(A) que calcula a menor circunferência que contém todos os pontos de A. Resolva em duas versões: uma que devolve o centro e o raio da circunferência e outra que devolve uma aproximação com $n$ pontos.

Exercício 11

Pode transformar pontos usando as operações da álgebra linear.

Implemente a função [x1, y1, z1] = dot_mv(a,b,c,d,e,f,g,h,i,x0,y0,z0) que calcula $$\left[\begin{array}{c}{x}_1\\ y_1\\ z_1\end{array}\right]=\left[\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right]\left[\begin{array}{c}{x}_0\\ y_0\\ z_0\end{array}\right].$$

Esta forma de representar matrizes e vetores é muito «trapalhona».

Represente os vetores por listas, v = [x, y, z], e as matrizes por listas de listas, A = [[a, b, c], [d, e, f], [g, h, i]]. Note que A[0] é a primeira linha de A.

Deve ficar com uma função X1 = dot_mv(A, X0).

Exercício 12

Implemente funções para gerar matrizes e calcular operações comuns.

1. A matriz zeros(n,m) tem $n$ linhas, $m$ colunas e todas as entradas são $0$.
2. Na matriz ones(n, m) tem $n$ linhas, $m$ colunas e todas as entradas são $1$.
3. A matriz eye(n) é a matriz identidade de ordem $n$.
4. A função t(A) é a matriz transposta de $A$.
5. A função sum_mm(A, B) soma as matrizes $A$ e $B$. Se as dimensões forem incompatíveis, devolve null.
6. A função dot_mm(A, B) multiplica as matrizes $A$ e $B$. Se as dimensões forem incompatíveis, devolve null.
7. A função translate(dx, dy) devolve a matriz da translação por $(dx,dy)$.
8. A função rotate(alpha) devolve a matriz da rotação por $\alpha$ radianos.
9. A função scale(sx, sy) devolve a matriz da escala por $(sx,sy)$.

Exercício 13

Use a biblioteca de funções que definiu acima para construir e transformar (aproximações) de circunferências e de segmentos.

Visualize as formas originais (a verde) e transformadas (a vermelho) nos sistemas C2D e SVG.

Exercício 14

Implemente a regra par-ímpar de enchimento de formas.

Suponha que F é um conjunto de pontos que aproxima uma figura 2D:

1. Defina a função sort_h(F) que devolve os pontos de F ordenados da esquerda para a direita (isto é, primeiro os pontos com menor coordenada x).
2. Defina a função strip_h(F, y0, e) que devolve os pontos de F que estão numa faixa horizontal, isto é os pontos de F cuja coordenada $y$ é tal que $\left|y-y_0\right|\le e$. Se não existirem pontos assim em F, devolve a lista vazia.
3. Defina a função first_left(F) que devolve o ponto mais à esquerda de F. Se F for uma lista vazia devolve null.
4. Defina a função next_right(F, x0) que devolve o ponto de F que, de todos os pontos de F com coordenada x maior que x0, é o que tem menor coordenada x. Se não existir tal ponto devolve null.
5. Use as funções sort_h, strip_h, first_left e next_right para definir a função fill_evenodd(F, ...​), que implementa a regra par-ímpar por faixas horizontais.
   • O resultado deve ser uma lista com os segmentos horizontais interiores, sendo cada segmento definido por dois pontos.
   • Considere ainda que argumentos são úteis e/ou necessário e como detetar e assinalar potenciais erros.

Exercício 15

Visualize o preenchimento de formas pela regra par-ímpar.

Use vermelho para a forma e verde para o interior. Resolva esta alínea para os sistemas C2D e SVG.

Exercício 16

Visualize o interior da forma usando os sistemas C2D e SVG com:

1. Um gradiente horizontal com várias cores (pelo menos 3).
2. Um gradiente vertical com várias cores (pelo menos 3).
3. Um padrão xadrez.

Modelação 2D

Exercício 17

Escreva um programa que use o C2D para desenhar um caminho entre os pontos de coordenadas $(0,0)$ e $(64,64)$ que tenha um arco de raio 16.

Exercício 18

Escreva um programa javascript para o C2D que desenhe um círculo amarelo no meio de um retângulo 100x100 azul. Defina a mesma imagem com um documento SVG.

Exercício 19

Procure na internet: Qual é o intervalo dos comprimentos de onda das cores visíveis?

Exercício 20

Marque os seguintes pontos num referencial cartesiano e num referencial de ecrã (desenhados numa folha de papel): (1, 3), (-2, 1.5), (0, -2), (0, 0), (2, 1), (-1.5, 1.5), (3, -0.5).

Exercício 21

Meia Lua	Yin-Yang

Escreva um programa para o C2D, e um documento SVG para desenhar:

1. Uma meia lua (ver acima).
2. Um quadrado centrado e rodado 45º.
3. Um tabuleiro de xadrez.
4. Um tabuleiro tri-colorido. Generalize para uma função que desenhe um tabuleiro $n$-colorido.
5. O símbolo oriental Yin-Yang (ver acima).
6. Um retângulo pintado com um gradiente radial acíclico.
7. Um retângulo pintado com um gradiente radial cíclico.
8. Um octógono. Generalize para um $n$-ágono.
9. Uma estrela de cinco pontas. Generalize para $n$ pontas.
10. Desenhe a bandeira da união europeia.

Exercício 23

Implemente uma função grafico(f, n, a, b) para ajudar a desenhar o gráfico de uma função matemática.

• Esta função devolve $n$ pontos $(x_i,f(x_i))$ do gráfico da função $f:\mathbb{R}\to \mathbb{R}$, com as abcissas $x_i$ igualmente espaçadas entre $a$ e $b$ (e $x_0=a,x_{n-1}=b$).
• Implemente funções para adaptar as listas $[(x_0,f(x_0)),\dots ,(x_{n-1},f(x_{n-1}))]$ a caminhos C2D e SVG.

Exercício 24

Implemente uma pequena biblioteca gráfica 2D.

Suponha que cada objeto gráfico é definido por:

• Um caminho, isto é uma lista de pontos x, y.
• Uma transformação com uma translação, uma rotação e uma escala.
• Propriedades de aspeto (stroke e fill).

Implemente uma função para desenhar estes objetos gráficos num C2D e para produzir um elemento SVG.

Exercícios 3D

Reveja a matéria de Álgebra Linear e de Geometria Analítica.

Geometria 3D

Exercício 1

Vetor Perpendicular 1

Dados dois vetores 3D $u=(u_x,u_y,u_z)$ e $v=(v_x,v_y,v_z)$, como é que encontra um terceiro vetor $w=(w_x,w_y,w_z)$ perpendicular a ambos?

Exercício 2

Vetor Perpendicular 2

Como é que adapta a resolução do exercício anterior para o caso em que, em vez de dois vetores, são dados três pontos 3D, $A=(A_x,A_y,A_z),B=(B_x,B_y,B_z)$ e $C=(C_x,C_y,C_z)$?

Programação 3D

Exercício 3

Distância

Implemente uma função dist(p, q) que calcula a distância entre dois pontos. Suponha que os pontos são definidos por objetos {x, y, z}.

Exercício 4

Produto Externo

Implemente a função outer(u, v) que calcula o produto externo entre dois vetores.

Supondo que $w=u\otimes v$, então as componentes de $w$ podem ser calculadas por $$w_x\mathbf{x}+w_y\mathbf{y}+w_z\mathbf{z}=\left|\begin{array}{ccc}\mathbf{x}& \mathbf{y}& \mathbf{z}\\ u_x& u_y& u_z\\ v_x& v_y& v_z\end{array}\right|$$

Exercício 5

Conjuntos de Pontos

1. Centro. Implemente a função center(points) que calcula o centro de um array de pontos.
2. Próximo. Implemente a função nearest(target, points) em que target é um ponto 3D e points é um array de pontos 3D e que encontra o elemento de points que está mais próximo de target.

• A sua função deve devolver um objeto com atributos {d, p} em que d é a distância e p o ponto mais próximo.

3. Afastado. Implemente a função farthest(target, points) em que target é um ponto 3D e points é um array de pontos 3D e que encontra o elemento de points que está mais afastado de target. Resolva de forma semelhante à alínea anterior.
4. «Mais Isolado». Implemente a função loneliest(points) em que points é um array de pontos 3D e que encontra o ponto «mais isolado» de um conjunto de pontos. O ponto «mais isolado» é o que está mais distante do centro.
5. «Mais Central». Implemente a função centralest(points) em que points é um array de pontos 3D e que encontra o ponto «mais central» de um conjunto de pontos. O ponto «mais central» é o que está mais perto do centro.
6. Canto Superior Direito Anterior. Implemente a função corner_trf(points) (trf: top right front) em que points é um array de pontos 3D e que encontra o «canto superior direito anterior» (SDA) de um conjunto de pontos. As coordenadas do SDA são os valores máximos nos eixos $x$, $y$ e $z$. Por exemplo:

   let points =  [
       {x: -1, y: 2, z: 0},
       {x: 20, y: 1, z: 3}
   ];
   
   {x: 20, y: 2, z: 3} === corner_trf(points);
   

7. Canto Inferior Esquerdo Posterior. Implemente a função corner_llb(points) (llb: lower left back) nos mesmos moldes do exercício anterior, substituindo o máximo pelo mínimo.
8. Pontos Mais Afastados. Implemente a função most_apart(points) em que points é um array de pontos 3D e que encontra os dois elementos de points que estão mais afastados um do outro. Isto é, se $p,q$ forem esses pontos então, dados quaisquer dois pontos $a$ e $b$ em points então dist(a,b) <= dist(p,q).
9. Pontos Menos Afastados. Implemente a função least_apart(points) em que points é um array de pontos 3D e que encontra os dois elementos distintos de points que estão menos afastados um do outro. Isto é, se $p,q$ forem esses pontos então, dados quaisquer dois pontos $a$ e $b$ em points então dist(a,b) >= dist(p,q).

Exercício 6

Processamento de Extrusões

Na construção de uma extrusão a secção percorre a espinha. Suponha que:

• A secção é definida por um array de pontos 2D {x, z} (note que é usado z e não y).
• A espinha é definida por um array de vetores 3D {x, y, z}.

Estes dois parâmetros definem os vértices da geometria obtida por extrusão.

Mais concretamente, cada ponto p:{x, z} da secção e cada vetor v:{x, y, z} da espinha definem o vértice q = {x: p.x + v.x, y: v.y, z: p.z + v.z} da extrusão.

Por exemplo, dados

const seccao = [
    {x: 0.0, z: 0.0},
    {x: 1.0, z: 0.0},
    {x: 0.0, z: 1.0} ];

const espinha = [
    {x: 0.0, y: 0.0, z: 0.0},
    {x: 0.0, y: 1.0, z: 0.0},
    {x: 1.0, y: 2.0, z: -1.0} ];

o ponto

seccao[2] === {x: 0.0, z: 1.0}

e o vetor

espinha[1] === {x: 0.0, y: 1.0, z: 0.0}

definem o vértice

{x: 0.0, y: 1.0, z: 1.0}

Escreva a função vertex(i, j, section, spine) que devolve as coordenadas xyz do vértice definido pelo i-ésimo ponto da secção e pelo j-ésimo passo da espinha.

• Por exemplo, usando as variáveis acima, vertex(1, 2, seccao, espinha) é o ponto 3D {x: 2.0, y: 2.0, z: -1.0}, que resulta do ponto {x: 1.0, z: 0.0} (com índíce i = 1) e do vetor {x: 1.0, y: 2.0, z: -1.0} (com indíce j = 2).
• Assegure-se que i e j são índices válidos. Se não o forem a função deve devolver null.

Exercício 7

Grelha de elevação em 3JS.

A biblioteca 3JS não tem um construtor «direto» equivalente à ElevationGrid do X3D.

Estude este elemento, determine três parâmetros que mais contribuem para esta geometria e faça uma implementação para o 3JS.

Modelação 3D

Resolva cada um destes exercícios usando as duas bibliotecas gráficas, X3D e 3JS.

Exercício 8

Desenhar um referencial.

Desenhe um referencial XYZ. Assegure-se que os eixos estão corretamente orientados e use o seguinte esquema de cores: X:red; Y:green; Z:blue.

Exercício 9

Desenhar uma pirâmide.

Desenhe uma pirâmide em wireframe.

Exercício 10

Desenhar um frustum.

Um frustum (veja também o artigo na wikipédia) é um poliedro (isto é, um sólido com todas as faces planas) com duas das faces quadradas paralelas (o topo e a base).

Desenhe em wireframe um frustum com altura 1, em que a base é um quadrado de lado 2 e o topo um quadrado de lado 1.

Exercício 11

Desenhar um octaedro.

Um octaedro é um dos cinco sólido platónicos (veja o artigo na wikipédia); tem oito faces triangulares e seis vértices:

$$(0,0,-1),(-1,0,0),(0,-1,0),(1,0,0),(0,1,0),(0,0,1)$$

Desenhem um octaedro em wireframe.

Exercício 12

Desenhar um icosaedro.

Um icosaedro é um dos cinco sólido platónicos (veja o ) e tem os vértices seguintes:

$$\begin{array}{rlrlrlr}& & (0,\varphi ,1)& & (0,\varphi ,-1)& & \\ & & (-\varphi ,1,0)& & (\varphi ,1,0)& & \\ (1,0,\varphi )& & (1,0,-\varphi )& & (-1,0,-\varphi )& & (-1,0,\varphi )\\ & & (-\varphi ,-1,0)& & (\varphi ,-1,0)& & \\ & & (0,-\varphi ,-1)& & (0,-\varphi ,1)& & \end{array}$$ onde $\varphi =\frac{\sqrt{5}+1}{2}$.

Desenhe um icosaedro em wireframe.

Exercício 13

Pintar uma pirâmide.

Desenhe uma pirâmide com as texturas de difusão, brilho e normais obtidas de imagens feitas ou encontradas por si. Seja realista.

Exercício 14

Pintar uma tenda.

Os vértices de uma tenda estão dados abaixo

$$\begin{array}{rlr}& (0.0,1.5,0.0)& \\ & & \\ (-.7,1.0,0.7)& & (0.7,1.0,0.7)\\ (0.7,1.0,-.7)& & (-.7,1.0,-.7)\\ & & \\ (-1.,0.0,1.0)& & (1.0,0.0,1.0)\\ (1.0,0.0,-1.)& & (-1.,0.0,-1.)\end{array}$$

Desenhe uma tenda pintada com texturas feitas (ou encontradas) por si. Seja realista.

Exercícios Animação

Exceto quando indicado o contrário, cada exercício é para ser resolvido em SVG, C2D, X3D e 3JS.

1. Percursos Lineares Uniformes. Desenhe uma forma simples (por exemplo, uma bola ou uma esfera azul) e desloque-a:

   1. 200 pixeis para a direita.
   2. Num retângulo com 200 pixeis de largura e 100 de altura.
   3. Num caminho poligonal com n pontos.

2. Percursos Curvos. Como é que representa percursos «curvos»? Por exemplo, percursos circulares ou em onda. Leve a forma do anterior a percorrer um percurso em forma de:

   • Círculo.
   • Seno (ondas).
   • Curva x^3.
   • Um caminho poligonal com n pontos, definido por uma equação paramétrica.

3. Percursos Compostos. Como é que representa percursos definidos por várias «partes”? Por exemplo, um percurso como ilustrado na figura seguinte:

4. Percursos Acelerados. Repita o exercício dos percursos compostos, mas a forma:

   1. Acelera no início de cada segmento e trava no fim.
   2. Acelera no início do percurso e trava no fim.

Recursos

Cábulas

Tutoriais

Bibliotecas

X3D

3JS

Tween.js

Outros