# Rasterização 2D

Algoritmo do ponto médio para linhas e preenchimento de regiões por varrimento.

Página: https://resumos.rgo.pt/cadeiras/cg/rasterizacao-2d/

No fim da [pipeline](https://resumos.rgo.pt/cadeiras/cg/rasterizacao-2d/pipeline-visualizacao/), a geometria já está achatada no plano do ecrã e falta a última conversão: decidir que píxeis acendem. A **rasterização** faz exatamente isto, com aritmética inteira rápida em vez de equações caras. É o fecho da abordagem de cima para baixo da cadeira: do 3D até ao píxel.

## Linhas pelo ponto médio

Desenhar o segmento de $(0, 0)$ a $(5, 2)$ parece pedir a reta $y = 0{,}4x$ com arredondamentos, mas o algoritmo do **ponto médio** (variante de Bresenham) decide cada píxel com somas inteiras. Para declive entre $0$ e $1$, avança uma coluna de cada vez e escolhe entre o píxel leste (E) e o nordeste (NE), consoante o ponto médio entre eles fica acima ou abaixo da reta. A variável de decisão começa em $d = 2\Delta y - \Delta x$ e atualiza-se com $+2\Delta y$ após E e $+2(\Delta y - \Delta x)$ após NE.

Aqui $\Delta x = 5$ e $\Delta y = 2$, logo $d$ começa em $2 \times 2 - 5 = -1$. Segue os passos a partir de $(0, 0)$:

| $x$ | $d$ antes | Escolha | Píxel | $d$ depois |
| --- | --- | --- | --- | --- |
| 1 | $-1$ | E | $(1, 0)$ | $-1 + 4 = 3$ |
| 2 | $3$ | NE | $(2, 1)$ | $3 - 6 = -3$ |
| 3 | $-3$ | E | $(3, 1)$ | $-3 + 4 = 1$ |
| 4 | $1$ | NE | $(4, 2)$ | $1 - 6 = -5$ |
| 5 | $-5$ | E | $(5, 2)$ | $-5 + 4 = -1$ |

Os píxeis acesos são $(0, 0)$, $(1, 0)$, $(2, 1)$, $(3, 1)$, $(4, 2)$ e $(5, 2)$. Confirma com a reta: em $x = 2$, $y = 0{,}8$ arredonda para $1$; em $x = 4$, $y = 1{,}6$ arredonda para $2$. O algoritmo nunca calculou $0{,}8$ nem $1{,}6$: seguiu o sinal de $d$ com inteiros. Para outros octantes troca-se o eixo de avanço ou o sinal, mas a estrutura é a mesma.

A grelha mostra os seis píxeis acesos com a escolha que os acendeu. Compara cada coluna com a linha da tabela: $E$ mantém a linha, $NE$ sobe uma.

![Grelha de 6 colunas por 3 linhas com seis píxeis pintados: (0,0) e (1,0) por E, (2,1) por NE, (3,1) por E, (4,2) por NE e (5,2) por E.](https://resumos.rgo.pt/cadeiras/cg/rasterizacao-2d/figura-1.svg)

Corre o algoritmo e confirma a tabela linha a linha. Muda o ponto final para $(5, 4)$ e observa como a sequência de escolhas muda.

```javascript
const x0 = 0, y0 = 0, x1 = 5, y1 = 2;
const dx = x1 - x0, dy = y1 - y0;
let d = 2 * dy - dx, y = y0;
const pixeis = [[x0, y0]];
for (let x = x0 + 1; x <= x1; x++) {
  if (d >= 0) { y++; d += 2 * (dy - dx); }
  else { d += 2 * dy; }
  pixeis.push([x, y]);
}
console.log("d inicial:", 2 * dy - dx);
console.log("píxeis:", JSON.stringify(pixeis));
```

[Vídeo: Bresenham's Line Algorithm - Demystified Step by Step](https://www.youtube.com/watch?v=CceepU1vIKo)

A miniatura vem do YouTube. O vídeo só carrega quando clicas. [Abrir no YouTube](https://www.youtube.com/watch?v=CceepU1vIKo)

## Os outros octantes

O caso acima é um octante; os outros sete trocam o eixo de avanço, o sentido ou ambos. A estrutura (decisão inteira, dois incrementos) é sempre a mesma.

O caso desta página, de $(0, 0)$ a $(5, 2)$. Avança em $x$ e escolhe entre E e NE. Incrementos $+2\Delta y$ e $+2(\Delta y - \Delta x)$, com $d$ a começar em $2\Delta y - \Delta x$.

Reta íngreme, como de $(0, 0)$ a $(2, 5)$. Troca os papéis: avança em $y$ e escolhe entre N e NE. Os incrementos usam $\Delta x$ e $\Delta y$ trocados, com $d$ a começar em $2\Delta x - \Delta y$.

Reta a descer, como de $(0, 2)$ a $(5, 0)$. Avança em $x$ mas escolhe entre E e SE, com os sinais dos incrementos em $y$ trocados. Na dúvida, espelha o segmento para o primeiro octante, corre a tabela e desfaz o espelho nos píxeis.

## Regiões por varrimento

Preencher um polígono faz-se por **varrimento** (_scanline_): para cada linha horizontal, interseta a linha com as arestas, ordena as interseções e preenche entre pares. A regra dos pares garante que buracos e concavidades saem certos sem casos especiais.

Toma o triângulo de vértices $(1, 1)$, $(5, 1)$ e $(3, 4)$ e a linha $y = 2$. A aresta esquerda vai de $(1, 1)$ a $(3, 4)$ com declive $\Delta x / \Delta y = 2/3$, logo cruza $y = 2$ em $x = 1 + 2/3 \approx 1{,}67$. A aresta direita vai de $(5, 1)$ a $(3, 4)$ com declive $-2/3$ e cruza em $x = 5 - 2/3 \approx 4{,}33$. Preenchem-se os píxeis inteiros entre elas: $x = 2$, $3$ e $4$. Repete para cada linha e o triângulo fica sólido. As extremidades partilhadas entre arestas tratam-se com uma convenção fixa (por exemplo, contar o mínimo e excluir o máximo) para não pintar nem falhar a fronteira duas vezes.

Como cai em teste

O enunciado típico dá dois pontos e pede a tabela do ponto médio, ou dá um polígono pequeno e uma linha de varrimento com as interseções. Nos dois casos o método é mecânico: monta a tabela passo a passo em vez de tentares adivinhar os píxeis a olho. A tabela é a resposta.