Aula 03 — Mapeamento, Recorte e Rasterização

Objetivos

Ao final desta aula você deve ser capaz de:

• Distinguir modelo de imagem e nomear os três sistemas de coordenadas do processo de visualização 2D — SRO, SRU e SRD —, indicando o que cada um resolve.
• Aplicar as fórmulas de mapeamento SRU → SRD e SRD → SRU, e justificar por que a componente Y tem o sinal invertido em relação à componente X.
• Separar os papéis de gluOrtho2D (window: o que do mundo) e glViewport (viewport: onde na tela), e prever o efeito de alterar cada um deles isoladamente.
• Implementar zoom e pan alterando apenas a window, sem modificar a geometria da cena.
• Codificar um ponto em relação a uma janela de recorte segundo Cohen-Sutherland e decidir, a partir dos códigos dos dois extremos, se um segmento é trivialmente aceito, trivialmente rejeitado ou precisa de interseção.
• Percorrer uma implementação completa de Cohen-Sutherland e explicar por que os casos degenerados — segmentos verticais e horizontais — não exigem tratamento especial.
• Implementar o recorte de polígonos por Sutherland-Hodgman encadeando as quatro passagens, e identificar a aresta degenerada que o algoritmo pode produzir em polígonos côncavos.
• Comparar DDA e Bresenham quanto ao tipo de aritmética usada e ao resultado produzido, e explicar a origem do serrilhado.
• Descrever os algoritmos de preenchimento por varredura (scan-line) e por semente (boundary-fill), identificando de que informação cada um parte.
• Reconhecer, em um programa OpenGL, quais dessas etapas o pipeline executa sozinho e quais continuam sendo responsabilidade de quem escreve a aplicação.

---

Conteúdo

Retomando: o que muda em relação à Aula 02

Na Aula 02 aprendemos a emitir vértices e já usamos gluOrtho2D e glViewport — mas como uma receita: "chame estas duas funções no resizeGL e as formas não distorcem". Esta aula abre a caixa. O que acontece entre o glVertex2f e o pixel aceso na tela é um processo com etapas bem definidas, e todas elas têm nome:

Etapa	O que faz	Quem executa nos exemplos desta aula
Instanciamento	Coloca uma cópia do modelo na cena	Você, ao escrever as coordenadas
Transformação	Move, gira e redimensiona o modelo	Assunto da Aula 04
Recorte	Descarta o que está fora da window	O OpenGL — e você, em recorte2d.py e na Atividade 2
Mapeamento	Converte coordenadas do mundo em pixels	O OpenGL — e você, em mapeamento2d.py
Rasterização	Decide quais pixels acender	O OpenGL — e você, em raster_linhas.py

A coluna da direita é o programa da aula: refazer à mão o que a placa de vídeo faz sozinha, em uma escala pequena o bastante para caber na tela e ser observada.

Por que reimplementar algo que a GPU já faz?

Por três motivos. Primeiro, porque o resultado da GPU é uma caixa-preta: quando o desenho sai errado, saber qual etapa poderia produzir aquele erro é o que separa depurar de chutar. Segundo, porque nem tudo está pronto — seleção por clique, arrasto de objetos e ferramentas de recorte na própria aplicação exigem essas contas escritas por você. Terceiro, porque os mesmos algoritmos aparecem fora da computação gráfica: Bresenham é usado em impressoras 3D e em controle de motores de passo, e recorte por códigos de região aparece em detecção de colisão.

---

O Processo de Visualização 2D

Um modelo é a representação computacional de um objeto: a lista de vértices e a informação de como ligá-los. Uma imagem é uma matriz de pixels. O processo de visualização 2D é o conjunto de técnicas que transforma o primeiro na segunda.

A diferença importa porque o modelo permite perguntas que a imagem não permite: este ponto pertence ao objeto?, qual é a área dele?, o que acontece se eu girá-lo 30°?. Depois de rasterizada, a figura é só um conjunto de pixels — as propriedades geométricas se perderam.

Entre o modelo e a imagem existem três sistemas de coordenadas:

O modelo é criado uma vez no seu próprio sistema, instanciado várias vezes no mundo e só então convertido em pixels.

• O SRO (Sistema de Referência do Objeto) é onde o modelo é definido. Uma casa é desenhada com a origem no seu canto, um círculo com a origem no seu centro — o que for mais conveniente para escrever as coordenadas.
• O SRU (Sistema de Referência do Universo) é onde a cena é montada. Cada instância do modelo é uma cópia posicionada no mundo. As informações do modelo e de suas cópias referem-se à aplicação, e não ao dispositivo.
• O SRD (Sistema de Referência do Dispositivo) é a tela, em pixels. É o único dos três que tem resolução finita, e o único em que o eixo Y tradicionalmente cresce para baixo.

Os três sistemas desta aula são planares: um ponto é um par (x, y). O mesmo raciocínio vale para o sistema espacial, em que o ponto é uma tripla (x, y, z) — a cadeia SRO → SRU → SRD é a mesma, e ganha uma etapa a mais, a projeção, que é o assunto da Aula 05.

O modelo é criado independente do dispositivo — de propósito. É isso que permite que o mesmo programa desenhe em uma janela de 640×480 e em outra de 3840×2160 sem alterar um único vértice. O preço é que, para exibir, é preciso converter: é o mapeamento.

---

Mapeamento: window e viewport

A conversão do SRU para o SRD é definida por dois retângulos.

A janela de seleção (window) é uma região do SRU: a área do universo que interessa naquele momento. Reduzi-la é o processo de zoom; deslocá-la é o pan. No OpenGL 2D ela é declarada por:

void gluOrtho2D(GLdouble left, GLdouble right, GLdouble bottom, GLdouble top)

A janela de exibição (viewport) é uma região do SRD: a área da tela onde o conteúdo da window será desenhado. Ela é declarada por:

void glViewport(GLint x, GLint y, GLsizei width, GLsizei height)

O par (window, viewport) define o mapeamento inteiro: um diz o que se olha, o outro diz onde o resultado aparece.

Uma frase resume a distinção e vale memorizar: gluOrtho2D responde "o quê", glViewport responde "onde".

Efetuando a conversão

Toma-se um ponto $P_u = (X_u, Y_u)$ no SRU e obtém-se $P_d = (X_d, Y_d)$ no SRD. A conta é a mesma em cada eixo: descobrir que fração do intervalo o ponto ocupa e aplicar essa fração ao intervalo de destino.

$$\frac{X_d - X_{d\,min}}{X_{d\,max} - X_{d\,min}} = \frac{X_u - X_{u\,min}}{X_{u\,max} - X_{u\,min}}$$

Isolando $X_d$:

$$X_d = \frac{X_{d\,max} - X_{d\,min}}{X_{u\,max} - X_{u\,min}}\,(X_u - X_{u\,min}) + X_{d\,min}$$

Em Y a conta é a mesma, com uma diferença: os eixos crescem em sentidos opostos nos dois sistemas. A relação fica invertida, e a fórmula final usa $Y_{d\,min} - Y_{d\,max}$ no numerador e soma $Y_{d\,max}$ no fim:

$$Y_d = \frac{Y_{d\,min} - Y_{d\,max}}{Y_{u\,max} - Y_{u\,min}}\,(Y_u - Y_{u\,min}) + Y_{d\,max}$$

O sinal invertido é o erro clássico

Trocar $Y_{d\,min} - Y_{d\,max}$ por $Y_{d\,max} - Y_{d\,min}$ produz um programa que funciona — e desenha tudo espelhado verticalmente. Como a maioria das cenas de teste é aproximadamente simétrica, o defeito costuma passar despercebido até alguém clicar perto do topo da janela. É a mesma inversão da conversão y_opengl = altura - y_qt vista na Aula 02.

Exemplo 1 — a mesma cena, quatro pares (window, viewport)

Saída de janela_viewport.py. A mesma geometria é desenhada quatro vezes; o que muda é o par window/viewport de cada quadrante.

📥 Baixe o arquivo completo: janela_viewport.py

O programa divide a área de desenho em quatro quadrantes e desenha a mesma lista de vértices nos quatro. Só a projeção muda:

Quadrante	Borda	Window	O que se vê
Superior esquerdo	verde	ajustada ao aspecto do viewport	referência: sem distorção
Superior direito	âmbar	quadrada, sem ajuste	a mesma cena esticada
Inferior esquerdo	azul	reduzida pela metade	zoom
Inferior direito	vermelho	reduzida e deslocada	pan

janela_viewport.py (trecho principal)

def paintGL(self) -> None:
    # glClear NÃO obedece ao viewport: ele varre o framebuffer inteiro.
    # Quem o restringiria é o teste de tesoura (glScissor), não usado aqui.
    glClear(GL_COLOR_BUFFER_BIT)

    # 1) window ajustada ao aspecto do viewport
    largura, altura = self._quadrante(0, 1)
    self._window_ajustada(largura, altura, 1.0, 0.0, 0.0)
    desenhar_cena()

    # 2) window quadrada em viewport retangular: a cena estica
    largura, altura = self._quadrante(1, 1)
    glMatrixMode(GL_PROJECTION)
    glLoadIdentity()
    gluOrtho2D(-MUNDO, MUNDO, -MUNDO, MUNDO)
    glMatrixMode(GL_MODELVIEW)
    desenhar_cena()

O que observar. A correção de aspect ratio da Aula 02 usava a proporção da janela; aqui ela usa a proporção do viewport. É esta a versão correta — a janela do sistema operacional só entra na conta quando o viewport por acaso ocupa a janela inteira, que era o caso de todos os exemplos da aula anterior.

glClear não respeita o glViewport

É uma confusão frequente, inclusive em material publicado. glClear varre o framebuffer inteiro, qualquer que seja o retângulo corrente; quem restringe a limpeza a uma região é o teste de tesoura (glScissor + glEnable(GL_SCISSOR_TEST)). Por isso uma única chamada de glClear no início do paintGL serve aos quatro quadrantes.

Exemplo 2 — as fórmulas escritas à mão

Saída de mapeamento2d.py. O clique no canvas é convertido de SRD para SRU e depois reconvertido para SRD, verificando se as fórmulas são inversas.

📥 Baixe o arquivo completo: mapeamento2d.py

mapeamento2d.py (trecho principal)

def sru_para_srd(xu, yu, window, viewport):
    xu_min, xu_max, yu_min, yu_max = window
    xd_min, xd_max, yd_min, yd_max = viewport   # yd_min no TOPO da tela

    xd = (xd_max - xd_min) / (xu_max - xu_min) * (xu - xu_min) + xd_min
    yd = (yd_min - yd_max) / (yu_max - yu_min) * (yu - yu_min) + yd_max
    return xd, yd


def srd_para_sru(xd, yd, window, viewport):
    xu_min, xu_max, yu_min, yu_max = window
    xd_min, xd_max, yd_min, yd_max = viewport

    xu = (xu_max - xu_min) / (xd_max - xd_min) * (xd - xd_min) + xu_min
    yu = (yu_max - yu_min) / (yd_min - yd_max) * (yd - yd_max) + yu_min
    return xu, yu

Clicando no canvas, a barra de status mostra a mesma posição nas três convenções — pixel do Qt, pixel do OpenGL e ponto do mundo — e o resultado de reconverter o ponto do mundo de volta para pixel. Essa ida e volta é o teste mais barato de que as duas fórmulas são realmente inversas: se o pixel de volta não for o pixel de partida, há um erro de sinal em algum lugar.

A conversão SRD → SRU é a que resolve o problema prático mais comum de qualquer aplicação gráfica interativa: descobrir em que ponto do mundo o usuário clicou. O OpenGL faz o caminho SRU → SRD sozinho, mas não devolve o caminho inverso de graça.

A GLU oferece gluUnProject, que faz essa conversão a partir das matrizes correntes. Ele é a escolha certa em produção — e sobretudo em 3D, onde a conta à mão deixa de ser trivial. Aqui a fórmula é escrita explicitamente porque o objetivo é justamente ver a conta; usar a função pronta antes de entender o que ela faz devolve o mapeamento à condição de mágica.

Exemplo 3 — zoom e pan

Saída de zoom_pan.py. O retângulo tracejado permanece fixo no mundo: o que muda com zoom e pan é a window corrente.

📥 Baixe o arquivo completo: zoom_pan.py

As teclas + e - dão zoom, as setas fazem pan, G liga e desliga a grade e R volta à window inicial. O título da janela mostra os quatro limites correntes, e o retângulo tracejado marca, no mundo, onde a window estava no início — ele não acompanha a câmera.

zoom_pan.py (trecho principal)

def _calcular_window(self) -> None:
    """Só faz contas e atualiza o título — nenhuma chamada gl*."""
    w, h = self._largura, self._altura
    cx, cy = self.centro
    if w <= h:
        meia_x, meia_y = self.escala, self.escala * h / w
    else:
        meia_x, meia_y = self.escala * w / h, self.escala

    self.window_sru = (cx - meia_x, cx + meia_x, cy - meia_y, cy + meia_y)

def paintGL(self) -> None:
    self._calcular_window()
    glMatrixMode(GL_PROJECTION)
    glLoadIdentity()
    gluOrtho2D(*self.window_sru)
    glMatrixMode(GL_MODELVIEW)
    glLoadIdentity()
    ...

O que observar. Nenhum vértice da cena é tocado: os círculos continuam nas mesmas coordenadas do mundo do começo ao fim. Quem se move é a window — a mesma ideia que, em 3D, vira o conceito de câmera.

Quando a projeção sai do resizeGL

A Aula 02 estabeleceu que a projeção mora no resizeGL. A regra continua valendo, mas agora dá para enunciá-la corretamente: a projeção deve ser recalculada quando algo de que ela depende muda. Se ela só depende do tamanho da janela, resizeGL é o lugar. Se depende de estado que o usuário controla — como aqui — ou muda de viewport para viewport — como no Exemplo 1 —, ela pertence ao paintGL.

O que continua proibido é chamar gluOrtho2D de dentro de um tratador de teclado ou de um slot: ali o contexto OpenGL não está garantidamente ativo. Por isso _calcular_window só faz contas, e quem chama gluOrtho2D é o paintGL.

---

Recorte (clipping)

Recorte é o processo de retirar do desenho tudo o que não está dentro da janela de seleção. Objetos totalmente fora são descartados; objetos parcialmente fora são cortados na borda.

Recortar antes de rasterizar não é uma questão de estética — é de custo. Rasterizar um segmento de um quilômetro para depois descobrir que só três pixels dele aparecem na tela desperdiça o trabalho inteiro. E, em memória matricial de tamanho fixo, escrever fora dos limites é um erro, não apenas um desperdício.

O recorte se aplica a quatro tipos de elemento:

• Pontos — o caso trivial. O ponto é visível se $X_{min} \le X \le X_{max}$ e $Y_{min} \le Y \le Y_{max}$. Caso contrário, é descartado.
• Retas — o caso central, tratado a seguir por Cohen-Sutherland.
• Polígonos — um problema diferente do anterior, porque o resultado precisa continuar sendo uma área fechada; é o assunto de Sutherland-Hodgman, uma borda por vez.
• Caracteres — o texto pode ser recortado caractere a caractere (tratando cada um como indivisível e testando o retângulo que o envolve), ou a string inteira pode ser tratada como indivisível, ou ainda cada segmento do desenho do caractere pode ser recortado individualmente. As três estratégias trocam precisão por velocidade, nessa ordem.

O algoritmo de Cohen-Sutherland

A ideia central não é geométrica, é combinatória: prolongar as quatro bordas da window divide o plano em nove regiões, e cada região recebe um código de 4 bits. Comparar os códigos dos dois extremos de um segmento resolve, com duas operações de bit, a grande maioria dos casos — sem calcular nenhuma interseção. É daí que vem o ganho. Quanto ele vale na prática depende da cena: quanto mais objetos houver fora da window, mais segmentos caem nos testes triviais. Em cenas típicas de aplicações interativas, a literatura reporta que a maior parte dos segmentos é resolvida sem nenhum cálculo de interseção — mas um conjunto pequeno e escolhido a dedo, como o dos exemplos desta aula, pode ficar bem abaixo disso.

As nove regiões e seus códigos. O código de um ponto é o OU dos bits das faixas em que ele cai.

Cada bit responde a uma pergunta, e um ponto pode acender no máximo dois deles — nunca "à esquerda e à direita" ao mesmo tempo. O algoritmo tem três passos.

A ordem dos bits é convenção, não lei

A Figura 6 lê os bits da esquerda para a direita do código escrito: acima, abaixo, à direita, à esquerda. Outros textos — inclusive o material impresso desta disciplina — numeram os bits pelo peso, e nessa contagem o bit 1 é o menos significativo, isto é, "à esquerda". As duas convenções descrevem a mesma coisa. O que importa é usar uma só dentro do mesmo programa.

1o. Passo — codificar os extremos. Calcule o código de $P_1$ e o de $P_2$.

2o. Passo — tentar as duas decisões triviais.

Teste	Significa	Ação
$c_1 \mathbin{\vert} c_2 = 0000$	nenhum bit ligado em nenhum extremo: os dois estão dentro	aceitação trivial — exibe sem recorte
$c_1 \mathbin{\&} c_2 \ne 0000$	um mesmo bit ligado nos dois extremos: ambos do mesmo lado de uma mesma borda	rejeição trivial — descarta o segmento inteiro

3o. Passo — o caso geral. Nenhum dos testes decidiu. Escolha um extremo que esteja fora (código diferente de zero), descubra pelo código dele qual borda cruzar primeiro, calcule a interseção da reta com essa borda e substitua o extremo pela interseção. Recalcule o código e volte ao 2o. passo.

Cada volta do laço elimina uma borda, e há quatro — o laço termina.

O teste do AND não prova visibilidade

c1 & c2 != 0 prova que o segmento está fora, mas o contrário não vale: um segmento pode ter AND igual a zero e ainda assim não cruzar a window. É o caso de um segmento que vai da região 1000 (acima) para a 0010 (à direita) cortando a região do canto superior direito — o AND é 0000, mas o segmento pode passar inteiramente ao largo da window. Por isso o algoritmo precisa do 3o. passo: quando os testes triviais falham, é preciso calcular de fato.

Exemplo 4 — Cohen-Sutherland completo

Saída de recorte2d.py. Os segmentos cinza são os originais; os trechos vermelhos são as porções aceitas pelo recorte de Cohen-Sutherland.

📥 Baixe o arquivo completo: recorte2d.py

recorte2d.py (trecho principal)

ACIMA, ABAIXO, DIREITA, ESQUERDA = 0b1000, 0b0100, 0b0010, 0b0001

def codigo_regiao(x, y, janela):
    x_min, x_max, y_min, y_max = janela
    codigo = 0
    if x < x_min:                 # `elif`, e não `if`: um ponto não pode
        codigo |= ESQUERDA        # estar à esquerda E à direita
    elif x > x_max:
        codigo |= DIREITA
    if y < y_min:
        codigo |= ABAIXO
    elif y > y_max:
        codigo |= ACIMA
    return codigo


def recortar(p1, p2, janela):
    x1, y1 = p1
    x2, y2 = p2
    x_min, x_max, y_min, y_max = janela
    c1, c2 = codigo_regiao(x1, y1, janela), codigo_regiao(x2, y2, janela)

    while True:
        if c1 | c2 == 0:          # aceitação trivial
            return (x1, y1), (x2, y2)
        if c1 & c2 != 0:          # rejeição trivial
            return None

        fora = c1 if c1 != 0 else c2
        if fora & ACIMA:
            x, y = x1 + (x2 - x1) * (y_max - y1) / (y2 - y1), y_max
        elif fora & ABAIXO:
            x, y = x1 + (x2 - x1) * (y_min - y1) / (y2 - y1), y_min
        elif fora & DIREITA:
            x, y = x_max, y1 + (y2 - y1) * (x_max - x1) / (x2 - x1)
        else:
            x, y = x_min, y1 + (y2 - y1) * (x_min - x1) / (x2 - x1)

        if fora == c1:
            x1, y1, c1 = x, y, codigo_regiao(x, y, janela)
        else:
            x2, y2, c2 = x, y, codigo_regiao(x, y, janela)

A tecla K imprime no terminal os códigos de cada extremo e a decisão tomada para cada um dos sete segmentos de teste — vale rodar antes de ler o código.

Divisão por zero: por que não acontece

As quatro expressões de interseção dividem por $y_2 - y_1$ ou por $x_2 - x_1$, e é natural desconfiar de um segmento vertical ou horizontal. Não há problema: em um segmento vertical, $x_1 = x_2$, logo os bits DIREITA e ESQUERDA ou estão ligados nos dois extremos — e a rejeição trivial já devolveu None — ou em nenhum, e o ramo que divide por $x_2 - x_1$ nunca é escolhido. Por simetria, o mesmo vale para o horizontal.

Outros algoritmos de recorte

Cohen-Sutherland recorta retas. Recortar polígonos é um problema diferente, porque o resultado precisa continuar sendo um polígono fechado — recortar cada aresta isoladamente produz um conjunto de segmentos soltos, e não uma área preenchível.

Algoritmo	Recorta	Observação
Cohen-Sutherland	retas	o mais difundido para segmentos; os três abaixo atacam um problema diferente
Sutherland-Hodgman	polígonos	processa a window uma borda por vez; em polígonos côncavos pode gerar arestas degeneradas — trechos que percorrem a borda da window ligando duas partes que deveriam estar separadas
Weiler-Atherton	polígonos	trata corretamente polígonos côncavos e com furos
Vatti	polígonos	caso geral, inclusive polígonos com autointerseção

Sutherland-Hodgman, uma borda por vez

A ideia é reduzir um problema difícil — recortar contra um retângulo — a quatro instâncias de um problema fácil: recortar contra uma reta infinita. O polígono é recortado contra a borda direita; o resultado disso é recortado contra a superior; e assim por diante. A saída de uma passagem é a entrada da seguinte, e depois de quatro passagens sobra o que estava dentro.

Cada passagem percorre as arestas do polígono, uma a uma, sempre olhando o par (vértice anterior, vértice corrente). Só há quatro situações possíveis:

Vértice anterior	Vértice corrente	O que a passagem emite
dentro	dentro	o vértice corrente
dentro	fora	a interseção com a borda
fora	dentro	a interseção com a borda e depois o vértice corrente
fora	fora	nada

"Dentro", aqui, é em relação àquela borda, e não à window inteira — um ponto pode estar dentro em relação à borda direita e fora em relação à superior. É essa decomposição que faz o algoritmo caber em quatro casos.

A interseção sai da equação paramétrica da reta. Contra uma borda horizontal, o $y$ é conhecido e falta o $x$:

$$x = x_1 + (x_2 - x_1)\,\frac{y - y_1}{y_2 - y_1}$$

e, contra uma borda vertical, o $x$ é conhecido e falta o $y$:

$$y = y_1 + (y_2 - y_1)\,\frac{x - x_1}{x_2 - x_1}$$

Nenhuma das duas precisa de proteção contra divisão por zero, e vale entender por quê: elas só são chamadas quando um extremo está dentro e o outro fora em relação àquela borda — o que exclui, por construção, o segmento paralelo a ela.

As quatro passagens do Sutherland-Hodgman. O que sobra no fim está inteiramente dentro da window — mas nem sempre é o polígono que se queria.

O último painel mostra o preço do algoritmo. O polígono da figura tem os dois braços ligados por uma espinha que fica fora da window: ao recortá-la, as duas partes visíveis ficam sem ligação, e o algoritmo as costura com lados que correm rente à borda. São as arestas degeneradas — na figura, dois trechos sobrepostos ao longo da borda direita. O contorno continua fechado e todos os vértices continuam dentro — mas, se o polígono for preenchido, a região entre os braços, que deveria ficar vazia, é pintada.

Weiler-Atherton e Vatti existem para resolver exatamente isso, ao custo de percorrer a fronteira dos dois polígonos em vez de fazer quatro passagens independentes.

---

Rasterização

Rasterização é a conversão de uma representação vetorial — vértices e equações — em uma representação matricial — uma grade de pixels. É a última etapa do processo, e a única irreversível: depois dela, a informação geométrica não existe mais.

A etapa se divide em dois problemas: desenhar linhas e preencher polígonos.

Desenho de linhas

A abordagem ingênua parte da equação da reta. Calculam-se os coeficientes a partir de $P_1$ e $P_2$, e para cada $x$ inteiro no intervalo obtém-se $y = m x + b$, acendendo o pixel $(x, \text{round}(y))$.

Funciona, mas tem dois defeitos graves:

• A inclinação quebra o algoritmo. Se $|m| > 1$, a reta anda mais em Y do que em X, e percorrer $x$ de um em um deixa buracos — a linha sai pontilhada. Seria preciso trocar o papel dos eixos.
• É lento. Uma multiplicação, uma soma e um arredondamento em ponto flutuante por pixel, em uma época em que ponto flutuante era caro — e ainda hoje, multiplicado por milhões de pixels por quadro.

Os algoritmos usados de fato eliminam ou reduzem as operações com números reais, explorando coerência espacial: pixels vizinhos têm valores parecidos, então o próximo pode ser obtido do anterior por incremento.

Algoritmo	Aritmética	Característica
DDA (Digital Differential Analyzer)	ponto flutuante	avança em passos constantes no eixo de maior variação e arredonda o outro
Bresenham	inteira	acumula um termo de erro; só soma, subtrai e desloca
Xiaolin Wu	ponto flutuante	produz linhas suavizadas (antialiasing), acendendo pixels com intensidades parciais

A reta ideal não passa pelo centro de quase nenhum pixel: rasterizar é escolher o pixel mais próximo, e a escada é o resultado dessa escolha.

Exemplo 5 — DDA e Bresenham lado a lado

Saída de raster_linhas.py no modo DDA × Bresenham. Os pixels âmbar coincidem nos dois algoritmos; os vermelhos expõem os empates resolvidos de maneiras diferentes.

📥 Baixe o arquivo completo: raster_linhas.py

O exemplo usa uma grade grossa de pixels: gluOrtho2D(0, COLUNAS, 0, LINHAS) faz com que uma unidade do mundo seja um pixel de um dispositivo imaginário de 32×24. O pixel $(i, j)$ tem centro em $(i + 0{,}5,\ j + 0{,}5)$, e "acender um pixel" é um GL_POINTS nesse centro com glPointSize do tamanho da célula.

raster_linhas.py (trecho principal)

def dda(x0, y0, x1, y1):
    dx, dy = x1 - x0, y1 - y0
    passos = max(abs(dx), abs(dy))        # o eixo de maior variação manda
    if passos == 0:
        return [(x0, y0)]

    incremento_x, incremento_y = dx / passos, dy / passos
    pixels = []
    x, y = float(x0), float(y0)
    for _ in range(passos + 1):
        pixels.append((round(x), round(y)))
        x += incremento_x
        y += incremento_y
    return pixels


def bresenham(x0, y0, x1, y1):
    dx, dy = abs(x1 - x0), abs(y1 - y0)
    passo_x = 1 if x0 < x1 else -1
    passo_y = 1 if y0 < y1 else -1
    erro = dx - dy                        # tudo inteiro, do começo ao fim

    pixels = []
    x, y = x0, y0
    while True:
        pixels.append((x, y))
        if x == x1 and y == y1:
            return pixels
        erro_dobrado = 2 * erro
        if erro_dobrado > -dy:
            erro -= dy
            x += passo_x
        if erro_dobrado < dx:
            erro += dx
            y += passo_y

A Figura 9 mostra o resultado: a reta ideal quase não passa pelo centro de nenhum pixel, e a escada é a consequência de escolher, para cada coluna, o pixel mais próximo.

O que observar. Tomar passos = max(|dx|, |dy|) é o que conserta o defeito da abordagem ingênua: o DDA sempre avança pelo eixo de maior variação, então nunca deixa buracos. E os dois algoritmos produzem quase o mesmo conjunto de pixels: divergem apenas nos empates, em que a reta ideal passa a meia distância entre dois centros de pixel e cada um desempata do seu jeito.

O segmento que o arquivo traz de saída é o pior caso de propósito: de (3, 4) a (29, 17), a inclinação é exatamente 1/2, então todo passo ímpar é um empate — a tecla 3 acende 12 pixels vermelhos contra 15 âmbar. Clique em outro ponto e a discordância costuma cair a zero.

A diferença entre eles, portanto, não é de resultado: é de custo. Bresenham chega ao mesmo lugar usando apenas aritmética inteira.

Preenchimento de polígonos

Determinar quais pixels estão "dentro" de um polígono admite dois caminhos opostos.

Scan-line parte da geometria. Para cada linha horizontal de pixels, calcula onde ela cruza as arestas do polígono, ordena as interseções da esquerda para a direita e preenche entre pares: da 1ª à 2ª, da 3ª à 4ª, e assim por diante. O número de interseções é sempre par — se der ímpar, há um erro de tratamento de vértice.

Em um polígono côncavo, uma mesma linha de varredura pode produzir quatro interseções — e o vão do meio fica de fora.

A Figura 11 mostra por que a regra é "entre pares" e não "do primeiro ao último": no entalhe do polígono côncavo, o trecho entre a segunda e a terceira interseção está fora da figura.

Boundary-fill parte de um ponto interno. A partir da semente, espalha-se para os vizinhos, pintando, até encontrar a cor da borda. Não olha a geometria: olha a imagem já rasterizada. A variante flood-fill é a mesma ideia com outro critério de parada — espalha enquanto encontrar a cor original, em vez de parar na cor da borda.

	Scan-line	Boundary-fill
Parte de	vértices e arestas	uma semente e a imagem
Precisa de	equações das arestas	nada além dos pixels
Falha quando	uma linha de varredura passa exatamente por um vértice e a regra de contagem não é aplicada	a borda tem um furo — o preenchimento vaza
Uso típico	pipeline gráfico	balde de tinta de editor de imagem

Exemplo 6 — scan-line e boundary-fill passo a passo

Saída de raster_poligonos.py. O scan-line avança uma fileira por vez: a linha âmbar mostra a varredura corrente, os pontos marcam as interseções e o azul mostra o que já foi preenchido.

📥 Baixe o arquivo completo: raster_poligonos.py

raster_poligonos.py (trecho principal)

def intersecoes_da_linha(poligono, y):
    """Onde a linha horizontal `y` cruza as arestas."""
    xs = []
    for k in range(len(poligono)):
        x0, y0 = poligono[k]
        x1, y1 = poligono[(k + 1) % len(poligono)]
        if y0 == y1:
            continue                          # aresta horizontal: ignorada
        # `min <= y < max` conta cada vértice UMA vez: sem isso, uma linha
        # que passa por um vértice geraria duas interseções no mesmo ponto
        # e o pareamento sairia trocado dali em diante.
        if min(y0, y1) <= y < max(y0, y1):
            xs.append(x0 + (y - y0) * (x1 - x0) / (y1 - y0))
    return sorted(xs)


def varrer_linha(poligono, j):
    y = j + 0.5                               # centro da fileira de pixels
    xs = intersecoes_da_linha(poligono, y)
    pixels = []
    for k in range(0, len(xs) - 1, 2):        # entre PARES de interseções
        inicio = math.ceil(xs[k] - 0.5)
        fim = math.floor(xs[k + 1] - 0.5)
        pixels.extend((i, j)
                      for i in range(max(0, inicio), min(COLUNAS - 1, fim) + 1))
    return pixels

O que observar. Com a tecla Espaço, o scan-line avança uma linha por vez e o boundary-fill esvazia uma rodada da pilha. Ao final, os dois preenchem quase o mesmo conjunto — mas não exatamente: um punhado de pixels alcançados pelo scan-line fica inacessível ao boundary-fill. A causa é a vizinhança 4-conectada: o preenchimento só se espalha para cima, para baixo, para a esquerda e para a direita, nunca na diagonal. Onde a borda rasterizada faz um degrau, os dois pixels do degrau se tocam apenas pelo canto, e o preenchimento não passa. Trocar para vizinhança 8-conectada resolveria — e criaria o problema oposto, de vazar por um degrau da borda. É uma diferença real de comportamento entre um algoritmo que conhece a geometria e um que só enxerga a imagem.

A recursão do livro não sobrevive à prática

A versão clássica do boundary-fill é recursiva: pinta o pixel e chama a si mesma para os quatro vizinhos. Em uma região de mil por mil pixels, isso são até um milhão de níveis de recursão — pilha estourada. O exemplo troca a recursão por uma pilha explícita, que é o que toda implementação real faz.

---

O processo completo

Reunindo as etapas na ordem em que acontecem:

O caminho de um modelo até a imagem. As duas caixas de especificação são o que a aplicação controla; o resto é maquinário.

Em um programa OpenGL, esse diagrama inteiro é executado a cada paintGL. A sua parte é pequena e está toda à esquerda: escrever os vértices, escolher a window com gluOrtho2D e o viewport com glViewport. O recorte, o mapeamento e a rasterização acontecem sozinhos — e é por isso que vale a pena saber o que são.

---

Atividades de Laboratório

Aquecimento

Antes das atividades, use os exemplos da aula para experimentar:

1. Em janela_viewport.py, redimensione a janela lentamente e compare os quadrantes verde e âmbar. Em que proporção de janela os dois coincidem? Por quê?
2. Em zoom_pan.py, dê zoom para dentro até o círculo central preencher a tela. A espessura do traço mudou? Explique usando a distinção entre grandezas do mundo e grandezas de rasterização vista na Aula 02.
3. Em mapeamento2d.py, clique exatamente no canto superior esquerdo do canvas e depois no inferior direito. Que valores de mundo você esperava? Confira.
4. Em recorte2d.py, pressione K e explique, para cada segmento, por que a decisão foi a que foi. Depois acrescente um segmento que tenha AND igual a zero e mesmo assim não cruze a window.
5. Em raster_linhas.py, pressione 3 e clique em vários pontos para mover $P_2$. Em que inclinações DDA e Bresenham divergem, e em quais coincidem sempre?
6. Em raster_poligonos.py, mova um vértice de POLIGONO até o contorno se autointerseccionar. O que cada um dos dois algoritmos faz?
7. Em poligono2d_base.py, antes de escrever qualquer código, use a tabela dos quatro casos para prever, no papel, as coordenadas que saem da primeira passagem sobre o polígono do arquivo — recortado só contra a borda direita. Guarde a previsão: o Passo 1 da Atividade 2 parte dela.

---

As duas atividades

São duas atividades independentes, cada uma com seu próprio arquivo de ponto de partida. Ambas usam Python com PySide6 e PyOpenGL, no pipeline fixed-function. Regras que valem para as duas:

• Trabalhe a partir do arquivo de ponto de partida; não comece do zero nem cole código pronto de outra fonte.
• Todo TODO do arquivo corresponde a um passo do roteiro.
• Comente as decisões não óbvias no próprio código.

---

Atividade 1 — Aros Olímpicos

Alvo visual da Atividade 1. As proporções são indicativas; as coordenadas ficam por sua conta.

Objetivo. Reproduzir os cinco aros da Figura 14 usando exclusivamente primitivas de linha e sem nenhuma transformação geométrica — o deslocamento de cada aro entra na conta dos vértices.

Ponto de partida. O programa já abre a janela e configura a projeção; o paintGL está vazio.

📥 Baixe o arquivo completo: aros2d_base.py

Por que sem transformações?

Esta é a versão "na força bruta" da atividade, e é assim de propósito. Na Aula 04 os mesmos aros serão refeitos com glPushMatrix, glTranslatef e glPopMatrix — desenhando um aro na origem e deixando a matriz posicionar as cinco cópias. Guarde o seu arquivo: a comparação entre as duas soluções é o argumento de existência das transformações geométricas.

Roteiro

Passo 1 — Entenda o espaço antes de desenhar. Leia o resizeGL do arquivo base e determine, no papel, qual faixa de coordenadas está visível em uma janela de 760×480. Dimensione os aros a partir disso: escolha o raio e a distância entre os centros de modo que os cinco caibam com folga — inclusive se a janela for redimensionada para o formato retrato.

Passo 2 — Estabeleça o fundo. O TODO 2 está no initializeGL. O símbolo tem um aro preto: sobre o fundo escuro dos outros exemplos do módulo, ele simplesmente não existe. Escolha o fundo e justifique a escolha em um comentário.

Passo 3 — Escreva a função que desenha um aro. A assinatura sugerida é _desenhar_aro(cx, cy, raio, cor). Ela deve emitir os vértices de uma circunferência de centro (cx, cy) — repare que o centro é parâmetro, e é isso que permite reaproveitá-la cinco vezes.

Escolha a primitiva que liga os vértices em sequência e fecha o contorno sozinho; consulte a tabela de primitivas da Aula 02.

Antes de rodar: quantos vértices você vai emitir? Escreva sua estimativa, rode com esse número e depois divida-o por quatro. A partir de quantos lados o polígono deixa de parecer um polígono?

Passo 4 — Ajuste a espessura. glLineWidth é estado corrente e vale para todos os aros. Onde ele deve ser chamado: dentro da função do aro, ou uma vez só no paintGL? As duas funcionam — escolha e justifique.

Passo 5 — Desenhe os cinco aros. Três em cima, dois embaixo, deslocados na horizontal para caírem nos vãos. As cores oficiais já estão no topo do arquivo.

Ao rodar: os aros de baixo estão passando por cima dos de cima ou por baixo? O que na ordem do seu código determina isso? Inverta e confirme.

Passo 6 — Confronte com a referência. Compare a sua janela com a Figura 14. Os aros vizinhos da fileira de cima devem se tocar, e os de baixo devem cruzar os de cima. Se não estiverem, o problema é o raio ou a distância entre centros — descubra qual.

Passo 7 — Teste o redimensionamento. Estique a janela na horizontal e depois na vertical. Os aros continuam circulares? Continuam inteiramente visíveis? Se algum sair da tela no formato retrato, corrija — e explique em um comentário qual trecho do programa determina o que fica visível.

Checklist de conclusão

• Os cinco aros aparecem, nas cinco cores corretas.
• Cada aro é apenas um contorno, sem preenchimento.
• Os aros da fileira de cima se tocam; os de baixo cruzam os de cima.
• Nenhuma função de transformação geométrica foi usada.
• Redimensionar a janela não deforma os aros nem os corta.
• Nenhuma chamada inválida entre glBegin e glEnd.

Para responder

Registre as respostas em um comentário no topo do arquivo:

1. Quantos vértices o seu programa emite ao todo, por quadro? Se você quisesse dobrar a suavidade dos aros, esse número mudaria como?
2. Suponha que o enunciado passasse a pedir 500 aros, em posições e tamanhos sorteados. O que no seu programa passaria a incomodar? Aponte a linha exata. (Guarde a resposta: é o argumento de abertura da Aula 04.)
3. Se a janela fosse redimensionada para 200×900, o que aconteceria com o desenho? A correção de aspect ratio resolve esse caso?

---

Atividade 2 — Recorte de Polígonos

Alvo visual da Atividade 2: nenhum trecho do traço grosso sai do retângulo tracejado — e o lado direito dele não existia no polígono original.

Objetivo. Implementar o algoritmo de Sutherland-Hodgman e recortar um polígono côncavo contra a window.

Ponto de partida. O programa já roda e desenha a window de recorte e o polígono original em cinza. As quatro funções do algoritmo estão pela metade — enquanto elas não funcionarem, nenhum contorno vermelho aparece.

📥 Baixe o arquivo completo: poligono2d_base.py

As teclas 0 a 4 mostram o resultado após aquele número de passagens: são a sua principal ferramenta de depuração, porque isolam qual borda quebrou. O esconde o polígono original, V marca os vértices do resultado e P preenche o resultado com GL_POLYGON.

Roteiro

Passo 1 — Leia o algoritmo antes de escrever. Retome a previsão que você fez no item 7 do aquecimento: a tabela dos quatro casos aplicada ao polígono do arquivo, recortado contra a borda direita apenas. Anote as coordenadas dos vértices que você espera na saída, não só quantos são — para este polígono a contagem não muda, e um checkpoint que não distingue certo de errado não serve para nada.

Passo 2 — Complete dentro. Quatro comparações, uma por borda; a da esquerda já está pronta como modelo. Cuidado com o sentido de cada desigualdade — trocar um >= por um <= produz um polígono que some inteiro, e é difícil descobrir qual das quatro foi.

Não procure conferência na tela: o return [] provisório de recortar_poligono continua no caminho, e o primeiro contorno vermelho só aparece no Passo 5. Confira no interpretador: dentro((0, 0), b, JANELA) deve dar True para as quatro bordas, e dentro((32, -24), "direita", JANELA) deve dar False.

Passo 3 — Complete intersecao. Para uma borda vertical você conhece o x e falta descobrir o y; para uma horizontal, o contrário. As duas fórmulas estão na seção Sutherland-Hodgman, uma borda por vez.

Antes de escrever, responda a pergunta que está no comentário do TODO 3: esta função pode ser chamada com um segmento paralelo à borda? Vá ler quem a chama antes de responder. A resposta decide se você precisa de um if protegendo a divisão — e escrever um if desnecessário é tão revelador quanto esquecer um necessário.

Passo 4 — Complete recortar_borda: os quatro casos. É o coração do algoritmo. Duas armadilhas, as duas comuns:

• o vértice que se emite é sempre o corrente, nunca o anterior;
• em um dos quatro casos saem dois pontos, e a ordem entre eles importa: emitir o vértice antes da interseção inverte um pedaço do contorno.

Confira no interpretador, sem depender da tela: recortar_borda(POLIGONO, "direita", JANELA) deve devolver exatamente as coordenadas que você anotou no Passo 1 — a conferência visual pela tecla 1 só passa a funcionar depois do Passo 5.

Passo 5 — Complete recortar_poligono: encadeie as passagens. A saída de uma passagem é a entrada da seguinte. Apague o return [] provisório. Percorra 0, 1, 2, 3 e 4 e observe o contorno encolhendo uma borda por vez.

Se o resultado final estiver certo mas algum intermediário parecer estranho, não conserte ainda: compare com a Figura 8. Alguns intermediários são estranhos — parte do polígono já foi cortada em um eixo e ainda não no outro.

Passo 6 — Descubra a aresta degenerada. Com o resultado pronto, pressione P para preencher o polígono. A figura preenchida não corresponde ao contorno que você vê com P desligado. Duas coisas diferentes estão acontecendo ao mesmo tempo, e você precisa separá-las:

1. o algoritmo produziu um lado que não existia no polígono original;
2. GL_POLYGON está sendo usado fora do que ele garante.

Identifique cada uma, aponte no código onde a primeira nasce e explique a segunda com o que você aprendeu na Aula 02.

Passo 7 — Confronte com a referência. Compare a sua janela com a Figura 15. Nenhum trecho do contorno vermelho pode sair do retângulo de recorte, nem por um pixel. Estique a janela na horizontal e na vertical: o resultado do recorte não pode mudar — ele é calculado no mundo, não em pixels.

Checklist de conclusão

• Todos os vértices do resultado estão dentro da window de recorte.
• As teclas 0 a 4 mostram cinco estágios, todos diferentes entre si para o polígono do arquivo.
• O contorno resultante é fechado: não há pontas soltas.
• Redimensionar a janela não altera o polígono recortado.
• Nenhuma função gl* é chamada fora de initializeGL, resizeGL ou paintGL.

Para responder

Registre as respostas em um comentário no topo do arquivo:

1. Quantos vértices tem o polígono original e quantos tem o resultado? Um recorte pode aumentar o número de vértices? Construa um polígono de quatro vértices cujo recorte tenha mais que quatro, e explique.
2. Troque a ordem das bordas em BORDAS — por exemplo, comece pela inferior. O resultado final mudou? E os intermediários? O que isso diz sobre a ordem ser ou não parte do algoritmo?
3. A aresta degenerada do Passo 6 aparece porque uma parte do polígono que ligava as duas metades ficava fora da window. Desenhe (no papel, com coordenadas) um polígono côncavo que não produza aresta degenerada nenhuma ao ser recortado, e diga qual propriedade ele tem que o do arquivo não tem.

---

Exercícios

Questões dissertativas

Q1

Explique a diferença entre modelo e imagem, e diga por que a rasterização é a etapa irreversível do processo de visualização 2D.

Q2

Qual é a diferença de papel entre gluOrtho2D e glViewport? Descreva o que se vê na tela ao alterar apenas um deles.

Q3

Por que a fórmula de mapeamento da componente Y tem o numerador invertido em relação à da componente X? O que acontece se essa inversão for esquecida?

Q4Difícil

No algoritmo de Cohen-Sutherland, os testes de aceitação e de rejeição trivial não são simétricos: um deles é uma equivalência e o outro é apenas uma implicação. Explique.

Q5

DDA e Bresenham produzem praticamente o mesmo conjunto de pixels. Por que Bresenham é o algoritmo que se ensina e se usa?

Q6

Compare scan-line e boundary-fill quanto ao que cada um precisa saber para funcionar, e dê uma situação em que apenas um dos dois é aplicável.

Questões objetivas

Quiz7 questões

1. A window vai de (0, 0) a (1000, 1500) no SRU e o viewport ocupa a área inteira de uma tela de 640×480, com a origem no canto superior esquerdo. Para que pixel é mapeado o ponto do mundo (500, 1125)?

• a)(320, 240)
• b)(320, 360)
• c)(500, 750)
• d)(160, 240)
• e)(320, 120)

2. Um programa desenha uma cena correta e, em seguida, apenas troca glViewport(0, 0, 800, 600) por glViewport(0, 0, 400, 600), sem mexer no gluOrtho2D. O que se vê?

• a)A cena inteira, ocupando a metade esquerda da tela e comprimida na horizontal
• b)A metade esquerda da cena, no tamanho original
• c)A cena inteira, no tamanho original, com a metade direita da tela em branco
• d)A cena inteira, ocupando a metade esquerda da tela e sem distorção
• e)Nada: o viewport ficou incompatível com a window

3. Uma window de recorte tem os cantos (−25, −18) e (25, 18). Qual é o código de região de Cohen-Sutherland do ponto (40, −30), na convenção acima/abaixo/direita/esquerda?

• a)1010
• b)0110
• c)0010
• d)0101
• e)1001

4. Dois extremos de um segmento têm códigos c1 = 1000 e c2 = 0010. O que o algoritmo de Cohen-Sutherland conclui nos testes triviais?

• a)Aceitação trivial: o segmento está inteiramente dentro
• b)Rejeição trivial: o segmento está inteiramente fora
• c)Nada: OU é diferente de zero e E é zero, então é preciso calcular a interseção
• d)Erro: essa combinação de códigos é impossível
• e)Rejeição trivial, porque nenhum dos extremos está dentro

5. Um triângulo de vértices A(0, 0), B(40, 0) e C(0, 30), nessa ordem, passa por UMA passagem do Sutherland-Hodgman contra a borda direita de uma window que vai de x = −25 a x = 25. Quantos vértices tem o polígono que sai dessa passagem?

• a)3 — o recorte nunca acrescenta vértices
• b)2
• c)4
• d)5
• e)0 — o triângulo é descartado por ter um vértice fora

6. Uma linha de varredura cruza as arestas de um polígono côncavo nos pontos x = 4, 11, 19 e 27, nessa ordem. Que intervalos são preenchidos?

• a)De 4 a 27, sem interrupção
• b)De 4 a 11 e de 19 a 27
• c)De 11 a 19 apenas
• d)De 4 a 11, de 11 a 19 e de 19 a 27
• e)Nenhum: quatro interseções indicam erro no polígono

7. Em qual situação o boundary-fill funciona e o scan-line não é aplicável?

• a)Quando o polígono é côncavo
• b)Quando o polígono tem arestas horizontais
• c)Quando existe apenas a imagem rasterizada, sem a lista de vértices
• d)Quando a região a preencher é muito grande
• e)Quando a borda do polígono tem um furo de um pixel

---

Referências

Principais (essenciais)

• AZEVEDO, E.; CONCI, A.; LETA, F. R. Computação Gráfica. Rio de Janeiro: Elsevier, 2003–2008. 2 v. (004.92 A994c)
• FOLEY, J. D. et al. Computer Graphics: Principles and Practice. 3. ed. Addison-Wesley, 2013. (004.92 C738)
• HEARN, D.; BAKER, M. P.; CARITHERS, W. R. Computer Graphics with OpenGL. 4. ed. Pearson Prentice Hall, 2011. (004.92 H436co)
• The Khronos Group. OpenGL 2.1 Reference Pages — glViewport. Disponível em: registry.khronos.org/OpenGL-Refpages/gl2.1

Aprofundamento (opcionais)

• COHEN, M.; MANSSOUR, I. H. OpenGL: uma abordagem prática e objetiva. São Paulo: Novatec, 2006. (004.92 C678o)
• HETEM JUNIOR, A. Computação gráfica. Rio de Janeiro: LTC, 2006. (004.92 H589c)
• BRESENHAM, J. E. Algorithm for computer control of a digital plotter. IBM Systems Journal, v. 4, n. 1, p. 25–30, 1965.
• Wikipedia. Cohen–Sutherland algorithm. Disponível em: en.wikipedia.org/wiki/Cohen–Sutherland_algorithm
• Wikipedia. Scan line fill e Flood fill. Disponível em: en.wikipedia.org/wiki/Scanline_rendering e en.wikipedia.org/wiki/Flood_fill