Aprenda a Matéria

Computação Gráfica · Prova 2 · de Antialiasing a Superfícies Implícitas · leitura de ~40 minutos

1. O mapa da matéria 2 min

Toda a matéria responde a duas perguntas.

1. Como mostrar uma cena 3D numa tela 2D sem parecer feia? Aqui entram a projeção, que leva o 3D para o plano, e o antialiasing, que suaviza as bordas quando a imagem vira pixels.
2. Como guardar um objeto 3D no computador? Há quatro famílias de resposta, e cada uma troca precisão por memória e processamento de um jeito diferente:
   • Representações de sólidos: gerar o objeto juntando peças (sweep, CSG, voxels, fractal) ou organizar o espaço da cena (octree, BSP).
   • Malhas poligonais: aproximar a superfície por triângulos e quadriláteros.
   • Curvas e superfícies paramétricas: descrever a forma por equações de grau 3.
   • Superfícies implícitas: descrever a forma por uma função cujo sinal diz se o ponto está dentro ou fora.

2. Antialiasing 5 min

O problema: o mundo é contínuo, a tela não

Uma reta de verdade pode passar por qualquer ponto. A tela só tem pixels em posições inteiras. Desenhar é decidir, pixel a pixel, se ele recebe a cor do objeto. Quando essa decisão é tudo ou nada, a reta inclinada vira uma escada. Esse defeito é o aliasing: a distorção que aparece ao converter algo contínuo em discreto com amostragem insuficiente. Ele também apaga detalhes menores que um pixel.

Em forma de conta, todo método termina na mesma mistura:

• c (cobertura): quanto do pixel o objeto ocupa, de 0 (nada) a 1 (tudo). É o único valor que cada método calcula de um jeito diferente.
• C_objeto: a cor do objeto (por exemplo, preto = 0).
• C_fundo: a cor do fundo (por exemplo, branco = 255).
• C_final: a cor que o pixel recebe. Com c = 0,5, o pixel fica exatamente no meio do caminho entre as duas cores.

Os métodos só diferem no jeito de estimar c. São quatro.

1) Superamostragem: contar pontinhos

Cada pixel é dividido numa pequena grade de subpixels. A imagem é calculada nessa resolução maior e depois volta ao tamanho normal tirando a média, por isso se chama pós-filtragem. Em escala de cinza, basta contar quantos subpixels a primitiva cobre: c = subpixels cobertos ÷ total de subpixels.

• Vantagem: fácil de implementar e funciona para qualquer primitiva. É o mais popular.
• Desvantagem: é força bruta. A memória e o processamento se multiplicam pelo número de subpixels. A qualidade depende de quantos subpixels se usa: com 3×3 só existem 10 tons possíveis.
• Usar quando se quer algo simples e geral e há memória sobrando. Evitar com pouca memória ou tempo real apertado.

2) Amostragem por área: medir a área

Em vez de contar pontos, calcula-se exatamente a área do pixel que a primitiva ocupa, tratando a reta como um retângulo fino. Como o filtro é aplicado antes de definir o pixel, chama-se pré-filtragem. Aqui c = área ocupada pela primitiva ÷ área do pixel. Se a reta ocupa 35% do pixel, ele recebe 35% da cor dela.

• Vantagem: mais precisão, porque a cobertura é exata e não estimada.
• Desvantagem: o cálculo geométrico da interseção é complexo e caro.
• Usar quando a precisão da borda importa e as primitivas são simples. Evitar com formas complicadas.

3) Pesos ou máscaras: média com os vizinhos

O pixel vira uma média ponderada dele com os vizinhos, com pesos dados por uma máscara. Na máscara comum 3×3 (1 2 1 / 2 4 2 / 1 2 1) o centro pesa mais. A soma é dividida pelo total, 16, para não clarear nem escurecer a imagem.

Como ler a máscara: ela não é uma matriz que "multiplica" outra no sentido de álgebra linear. É uma tabela de pesos posicionada em cima do pixel: o número do meio (4) vale para o próprio pixel; os números 2, para os vizinhos de lado, de cima e de baixo; os números 1, para os vizinhos na diagonal. Cada vizinho é multiplicado pelo seu peso, tudo é somado, e a soma é dividida por 16. Os números da máscara são fixos; quem muda de pixel para pixel são as cores que eles multiplicam.

• Vantagem: a suavização é controlável; a aplicação escolhe os pesos.
• Desvantagem: pode borrar detalhes. O ideal seria variar os pesos ao longo da primitiva, mas isso aumenta o custo.
• Usar para um efeito uniforme e ajustável. Evitar quando detalhes finos precisam ficar nítidos.

4) Pixel phasing: mover o feixe

Aqui quem trabalha é o hardware. O dispositivo de saída desloca o feixe ou acende áreas de tamanhos variados, chegando mais perto da posição contínua real. A cor não muda; muda onde o ponto é aceso.

• Vantagem: suaviza sem multiplicar amostras.
• Desvantagem: depende de hardware, então tem pouca portabilidade.

3. Projeções 8 min

Projetar é representar algo de uma dimensão maior numa menor. Os objetos 3D, guardados com significado na estrutura de dados (forma, profundidade, faces), viram uma imagem 2D na tela. A ideia física é simples: saem raios de um centro de projeção, que é o olho ou a câmera, até a cena. Onde cada raio corta o plano de visualização (a "tela"), nasce o ponto da imagem.

O que é preciso para calcular uma projeção

1. Posição e orientação (ângulo) do observador ou câmera.
2. Posições dos planos frontal, posterior e de visualização. O frontal e o posterior recortam a profundidade: só o que está entre eles aparece.
3. O tipo de projeção.
4. A posição dos objetos na cena.

Os tipos: depende de como os raios se comportam

Paralela. Os raios são paralelos entre si, como se o centro de projeção estivesse no infinito (pense na sombra feita pelo Sol). O volume visível é um paralelepípedo. Como a distância não muda o tamanho, ela preserva as dimensões, e por isso serve para medir e comparar. Exemplo: dimensionar uma lesão numa tomografia. Ela tem dois subtipos:

• Ortogonal: os raios cortam o plano a 90°. O cálculo é trivial: P(x, y, z) → P'(x, y), ou seja, joga-se z fora. Com uma face visível, dá as vistas de topo, frontal e lateral (planta baixa, modelagem). Com o objeto girado, mostra três faces: é a isométrica dos jogos, que parece 3D mas continua paralela.
• Oblíqua: os raios cortam o plano com ângulo diferente de 90°. O ponto "escorrega" no plano por uma distância que depende da profundidade, calculada pelo triângulo entre o raio e o plano:

• x, y, z: coordenadas do ponto no espaço; z é a profundidade (distância até o plano).
• xp, yp: onde o ponto cai no plano de visualização (o "p" é de "projetado").
• α (alfa): ângulo entre o raio e o plano. 90° é a ortogonal; quanto menor, mais inclinado.
• L: quanto o ponto "escorrega" no plano em relação à posição ortogonal (x, y).
• θ (teta): a direção, dentro do plano, para onde ele escorrega. cos θ e sen θ dividem L entre o eixo x e o eixo y.

Em palavras: quanto mais fundo o ponto (z maior), mais ele desloca. Quanto mais inclinado o raio (α menor), mais ele desloca. Com α = 90°, tan α é infinita, L = 0, e a oblíqua vira ortogonal.

Perspectiva. Os raios convergem para o centro de projeção, como uma lanterna ou o olho humano. O volume visível é um frustum: uma pirâmide de visão sem a ponta, limitada pelos planos frontal e posterior. Objetos iguais mais distantes ficam menores. Por isso as dimensões não se preservam, mas surge a noção de profundidade. Retas paralelas da cena parecem se encontrar nos pontos de fuga (1, 2 ou 3).

A lógica do cálculo: triângulos semelhantes

• X, Y, Z (maiúsculas): o ponto real na cena. X e Y são as posições lateral e vertical; Z é a profundidade, a distância do centro de projeção até o ponto.
• x, y (minúsculas): onde esse ponto aparece na imagem, sobre o plano de visualização.
• f: distância do centro de projeção até o plano de visualização (a "distância focal", como numa câmera).

Toda a "relação das distâncias" sai dessa única fórmula:

• Z dobra, a imagem cai pela metade. Um objeto muito longe tende a um ponto, o ponto de fuga.
• Objeto exatamente no plano (Z = f): sai do tamanho real.
• f maior, imagem maior e ângulo de visão mais fechado, como um zoom. f menor abre o ângulo e deforma mais.
• Com o centro muito longe, os raios ficam quase paralelos, e a perspectiva se aproxima da paralela.

Como ler as matrizes de projeção

Na computação gráfica, um ponto é escrito como uma coluna de 4 números, [x, y, z, 1]. O 1 extra é a coordenada homogênea, um truque para que todas as transformações virem uma única multiplicação de matriz. A matriz 4×4 multiplica essa coluna e devolve outra coluna, o ponto transformado.

A regra de leitura é: cada linha da matriz produz uma coordenada do resultado. Os números da linha dizem quanto de x, de y, de z e de 1 entram naquela coordenada. Eles são fixos: não "recebem" valores. Quem muda é o ponto que entra.

• O 1 na diagonal significa "copie esta coordenada como está".
• O 0 significa "não use esta coordenada aqui".
• Uma linha inteira de zeros zera aquela coordenada. Na ortogonal, é isso que joga a profundidade fora: P(x, y, z) → P'(x, y).
• x, y, z: o ponto do objeto, que entra. x', y', z' (com apóstrofo, "linha"): o mesmo ponto depois da projeção, que sai. O apóstrofo só quer dizer "transformado".
• w: a 4ª coordenada do resultado (homogênea). Se w = 1, o ponto já está pronto; se não, divide-se x', y', z' por w.

Aqui o ponto que entra está em maiúsculas, [X, Y, Z, 1], porque é o ponto real da cena; o resultado final, depois da divisão, é o x, y minúsculo da imagem. Ou seja, a matriz copia o ponto e guarda "Z dividido por f" na quarta coordenada. O único número que depende da câmera é o 1/f da última linha. A divisão final por w é o que faz o objeto distante (Z grande) encolher. A matriz não calcula a imagem sozinha: ela prepara o ponto, e a divisão por w completa a perspectiva.

4. Representação de sólidos 8 min

Há seis técnicas, em dois grupos. As de geração criam a forma: sweep, CSG, voxels e fractal. As de armazenamento fazem a organização e manipulação da cena: quadtree/octree e BSP. Estas não criam nada; organizam o espaço que os objetos ocupam para responder rápido "o que está visível?", "o que colide?", "o que está na frente?".

Sweep (varredura)

Pegue uma figura 2D e mova-a pelo espaço com uma transformação geométrica. O sólido é tudo por onde ela passou. Com translação, um anel arrastado vira um tubo. Com rotação, um perfil girado 360° em torno de um eixo vira um sólido de revolução, como um vaso, uma taça ou uma ampulheta (é o torno do oleiro).

Vantagem: com muito pouca informação, uma figura e um movimento, sai o sólido inteiro. Desvantagem: descobrir qual figura e qual transformação geram o objeto desejado. Para formas sem simetria, é difícil.

CSG (Constructive Solid Geometry)

É montar objetos como numa oficina: parte de sólidos básicos de equação conhecida (cubo/paralelepípedo, esfera, cilindro, cone, pirâmide, prisma) e os combina com três operações.

• União (A ∪ B): junta os dois.
• Interseção (A ∩ B): fica só a parte comum.
• Diferença (A − B): remove de A o pedaço ocupado por B. Atenção: A − B ≠ B − A.

O objeto é guardado como uma árvore: as folhas são as primitivas, os nós são as operações e a raiz é o objeto final. É preciso guardar o histórico da sequência, porque a ordem muda o resultado e porque, com a árvore, dá para calcular colisões e deformações depois. Para saber se um ponto está dentro do objeto, testa-se o ponto em cada primitiva e combinam-se as respostas pela árvore.

Vantagem do CSG: é simples e tem baixo custo. Desvantagem: escolher as primitivas iniciais e a sequência certa.

Voxels

O voxel (volume element) é o "pixel 3D": a menor unidade de volume, indivisível, com um único atributo (cheio/vazio, densidade, cor). O espaço vira uma grade regular de cubinhos. Como o interior também está guardado, fica fácil cortar o objeto, mostrar só um intervalo (o osso e não a pele numa tomografia) ou alternar entre ver a superfície e ver por dentro, como num motor ou num órgão.

O preço é a memória, que cresce com o cubo da resolução: com n voxels por lado, são n×n×n voxels; dobrar n multiplica a memória por 8. As superfícies curvas também ficam em degraus, um aliasing que pode ser suavizado.

Fractal (modelo Mandelbrot)

Formas naturais (samambaia, montanha, litoral) não são bem descritas por equações "bem-comportadas". O fractal parte de um modelo-base e aplica repetidamente uma função geradora. Por exemplo: um triângulo como base e um segmento com um "dente" como gerador. Na 1ª iteração, cada aresta vira o desenho do gerador (cada aresta gera 3). Na 2ª, faz-se o mesmo com cada aresta nova, e assim por diante. Cada repetição é uma iteração; se cada aresta gera k novas, depois de n iterações cada aresta original virou kⁿ. O resultado é autossimilar: a parte repete o todo. Vantagem: uma regra pequena gera uma forma muito complexa. Desvantagem: o custo cresce a cada iteração.

Quadtree e octree

Imagine guardar um mapa: onde é tudo igual (oceano), basta dizer "oceano"; só a costa precisa de detalhe. A quadtree faz isso. Divide a região em 4 (quadtree, 2D) ou em 8 (octree, 3D). Cada parte que é homogênea (toda cheia ou toda vazia) vira folha. A que é heterogênea (mista) vira nó intermediário e é dividida de novo.

Os nós intermediários guardam a média das folhas abaixo deles. Isso permite uma prévia rápida ou o desenho de objetos distantes sem descer até as folhas: cada nível da árvore é uma versão do objeto em resolução diferente. O ponto fraco é que a divisão é sempre ao meio. Se a borda do objeto não se alinha a essas divisões, quase tudo fica heterogêneo, e a árvore pode gastar mais memória e tempo que os voxels puros.

BSP (Binary Space Partitioning)

A BSP divide o espaço em duas regiões de cada vez, com um plano em qualquer posição e orientação. Cada plano tem uma normal (N⃗) que diz qual lado é "depois" e qual é "antes" (O⃗, o sentido oposto). Cada região pode ser dividida de novo, até cada uma ter um objeto. O resultado é uma árvore binária: nó = plano, ramo = lado, folha = objeto.

Para que serve: percorrendo a árvore a partir de onde está o observador, obtém-se a ordem dos objetos de trás para frente. Isso resolve sobreposição, visibilidade, colisões e quais áreas um raio intercepta ou ilumina, usando o produto entre o raio e as normais. Os jogos de corredores dos anos 90 desenhavam os mapas assim. Ponto fraco: escolher onde pôr os planos exige analisar a cena antes.

5. Malhas poligonais 3 min

A malha descreve só a superfície, como um papercraft: pontos → arestas → polígonos → objeto. Guarda-se uma lista de vértices (as coordenadas) e uma lista de faces (quais vértices formam cada polígono). Se os pontos vieram de um scanner 3D, o trabalho é decidir como agrupá-los. Ao montar a malha, é preciso responder a quatro perguntas:

1. Quais pontos formam cada aresta, e quais arestas formam cada polígono?
2. Vale subdividir um elemento? Por qual critério: textura, iluminação ou topologia?
3. Até que nível subdividir sem estourar memória e desempenho?
4. Que polígono usar: triângulo ou quadrilátero?

Triângulo × quadrilátero

O triângulo é sempre plano e se encaixa em qualquer forma, buraco ou curva: tem mais flexibilidade topológica. Por isso é o preferido em regiões com detalhe e deformações frequentes. O preço é a memória, porque é preciso mais triângulos para cobrir a mesma área. O quadrilátero forma grades regulares e econômicas, ideais em regiões retilíneas e estáveis. Na prática se usa a malha híbrida: quadriláteros onde a superfície é regular e triângulos onde ela é complexa (rosto, articulações, borda de um furo). Na fronteira, os vértices são compartilhados para não abrir fendas.

Low poly × high poly

Quanto menor o polígono, mais próximo do contínuo, e mais caro. Low poly (jogos, construção civil) tem melhor desempenho e serve para cálculos em tempo real, com qualidade inferior tolerável. High poly (filmes de animação, avatar em destaque) é processado antes e tem qualidade superior, para um público com baixa tolerância a defeitos. É comum usar os dois no mesmo objeto, conforme a distância: são os níveis de detalhe.

Subdivisão

Depois, as posições são suavizadas por pesos que somam 1 (subdivisão de Loop). Nova posição = soma de (posição de cada vértice envolvido × seu peso).

• Vértice novo (ímpar), no meio de uma aresta: 3/8 para cada uma das 2 pontas da aresta e 1/8 para cada um dos 2 vértices opostos (dos dois triângulos que dividem a aresta). 3/8 + 3/8 + 1/8 + 1/8 = 1.
• Vértice antigo (par): k é quantos vizinhos ele tem; cada vizinho recebe um peso pequeno β (beta), e o próprio vértice fica com o que sobra, 1 − k·β. Somando: (1 − kβ) + k·β = 1.
• Na borda da malha: o novo fica no meio (1/2 e 1/2); o antigo usa 1/8, 3/4, 1/8 (vizinho, ele, vizinho).

Repetindo o processo, cada triângulo vira 4 a cada passo (1 → 4 → 16 → 64), e a malha converge para uma superfície lisa: um icosaedro vira quase uma esfera.

6. Curvas paramétricas 11 min

Para descrever uma superfície lisa, usa-se uma rede de curvas. Cada pedaço de curva é um polinômio de grau 3 num parâmetro u que vai de 0 (início) a 1 (fim), um para cada eixo:

• u: o parâmetro, como um "relógio" que anda de 0 a 1. u = 0 é o começo do pedaço de curva; u = 1 é o fim; u = 0,5 é o meio do percurso (não necessariamente o meio do comprimento).
• p(u): o ponto da curva naquele instante u. Na prática há uma equação para cada eixo, x(u), y(u) e z(u), todas com a mesma forma.
• e, d, b, a: os coeficientes, os números que dão a forma da curva. e multiplica 1, d multiplica u, b multiplica u², a multiplica u³. São as incógnitas: cada modelo de curva é só uma regra diferente para calculá-los. (Também aparecem escritos como c₀, c₁, c₂, c₃.)
• P0, P1, P2, P3: os pontos que o usuário informa (pontos de controle).
• p'(u): a derivada, ou seja, a tangente: para onde e com que "velocidade" a curva está indo no instante u.

Por que grau 3? É o menor grau que permite fixar quatro condições: a posição e a direção (tangente) nas duas pontas. Isso basta para emendar pedaços sem quina e para fazer um "S". Grau maior custa mais e oscila. É um equilíbrio de custo e benefício.

Continuidade e suavidade nas emendas

• Contínua: o fim de uma curva é o começo da outra, P_C0(1) = P_C1(0).
• Suave: além disso, as tangentes coincidem, P'_C0(1) = P'_C1(0).

Sem as duas, a soma dos pedaços não parece um objeto único.

Antes de tudo: como ler uma conta com matriz

Uma matriz vezes uma coluna é só um jeito compacto de escrever várias equações de uma vez. Cada linha da matriz gera uma equação: multiplica-se o 1º número da linha pelo 1º item da coluna, o 2º pelo 2º, e assim por diante, e soma-se tudo.

• À esquerda ficam os valores que você conhece (aqui, os pontos por onde a curva passa).
• A matriz do meio é fixa: os números são as potências de u (1, u, u², u³) para o u de cada condição. O 1 da primeira coluna está sempre lá porque e é multiplicado por u⁰ = 1. Na primeira linha, u = 0, então só sobra o 1: p(0) = e. Na última, u = 1 e todas as potências valem 1: p(1) = e + d + b + a. Esses números nunca "recebem valor": são sempre os mesmos para esse tipo de curva.
• À direita ficam as incógnitas, os coeficientes.
• Os tamanhos encaixam assim: (4×4) · (4×1) = (4×1). São 4 condições e 4 incógnitas: um sistema de 4 equações.

A receita que vale para todas as curvas

Cada modelo é só uma regra diferente para descobrir os 4 coeficientes (e, d, b, a). A lógica é sempre a mesma:

• [condições]: o que você informa (pontos e/ou tangentes).
• [A]: matriz constante. Cada linha diz como uma condição depende dos coeficientes.
• [coef]: o que se quer descobrir.
• Como não se "divide" por matriz, multiplica-se pela inversa, porque A⁻¹·A = I, a identidade.
• [M] = [A⁻¹] é a matriz característica do modelo. Ela não depende dos pontos: é calculada uma vez e serve para qualquer curva daquele tipo, em x, y e z.
• [I], a identidade, tem 1 na diagonal e 0 no resto. Multiplicar por ela não muda nada, como multiplicar um número por 1. É por isso que ela "some" da conta.

O que a matriz característica calcula. Ela multiplica a coluna das condições (os pontos que você deu) e devolve a coluna dos coeficientes. Cada linha diz como montar um coeficiente, e cada número é o peso de um ponto nesse coeficiente. Os pontos entram separadamente para cada eixo: primeiro todos os x, depois todos os y.

Depois que os coeficientes saem, desenhar é multiplicar uma linha por eles: p(u) = [1 u u² u³] · [coef]. Juntando tudo: p(u) = [1 u u² u³] · [M] · [pontos]. O produto [1 u u² u³]·[M] dá, para cada u, quatro pesos que dizem quanto cada ponto "puxa" a curva naquele instante. São as funções de mistura.

Curva interpolada: passar por todos os pontos

As condições são passar pelos 4 pontos informados, nos parâmetros u = 0, 1/3, 2/3 e 1. A matriz [A] é exatamente a do exemplo acima. Invertendo-a, sai a M_I:

Leitura: cada linha monta um coeficiente como mistura dos 4 pontos. A 1ª linha (1 0 0 0) diz "e é o próprio P0": a curva começa em P0. Os números grandes e de sinais alternados nas outras linhas são o que faz a interpolada "se esforçar" para passar por todos os pontos, e o que a faz oscilar.

• Vantagem: passa exatamente onde você quer e é o modelo mais fácil de implementar.
• Desvantagem: obrigada a passar por todos os pontos, ela pode oscilar, e a suavidade sofre. Nas emendas, só garante continuidade.

Curvas aproximadas: os pontos só "puxam"

Hermite. Em vez de 4 pontos, informam-se as 2 pontas e as 2 tangentes: p(0), p(1), p'(0) e p'(1). Derivando a curva, p'(u) = d + 2b·u + 3a·u², em que e some porque é constante. Então as linhas das tangentes em [A] são os números que multiplicam e, d, b e a nessa derivada:

Repare na ordem das colunas de M_H: elas correspondem a p(0), p(1), p'(0) e p'(1), nessa ordem. Por isso a 2ª linha (0 0 1 0) pega só a 3ª condição: d = p'(0).

Vantagem: garante continuidade e suavidade nas emendas (é só repetir o ponto e a tangente). Desvantagem: o usuário raramente sabe as tangentes, o que não favorece o uso comercial.

Bézier. É a Hermite com uma troca esperta: as tangentes são estimadas por dois pontos intermediários, P1 e P2. Considerando P1 em u = 1/3, a inclinação de P0 até P1 é a variação de posição sobre a variação de u:

Substituindo isso na Hermite, sai a matriz da Bézier, que já recebe os 4 pontos de controle direto:

Os zeros têm significado: na 2ª linha, P2 e P3 não entram, porque a tangente do começo depende só de P0 e P1.

Funções de mistura da Bézier (Bernstein). Fazendo [1 u u² u³]·M_Bz, saem os pesos de cada ponto no instante u:

• p(u) = (1−u)³·P0 + 3u(1−u)²·P1 + 3u²(1−u)·P2 + u³·P3.
• (1−u)³ é o peso de P0, 3u(1−u)² o de P1, 3u²(1−u) o de P2 e u³ o de P3.
• Em u = 0 só P0 pesa (peso 1): a curva começa em P0. Em u = 1 só P3 pesa.
• Os pesos são sempre ≥ 0 e somam 1. É daí que vem a envoltória convexa.

A curva fica sempre dentro da envoltória convexa, o polígono formado pelos pontos de controle. O motivo: cada ponto da curva é uma média ponderada dos 4 pontos, com pesos positivos que somam 1, e uma média nunca sai do "envelope" dos pontos. É o modelo mais usado comercialmente: a ferramenta "caneta" dos editores, as trajetórias de câmera em jogos e as fontes. Nas emendas, garante continuidade; a suavidade exige alinhar P2, P3 e o próximo P1.

B-Spline. Usa as mesmas condições da Bézier e acrescenta duas coisas: duplicar pontos, o que funciona como um peso que puxa a curva para o ponto repetido, e a derivada de 2ª ordem, que deixa a curvatura também contínua nas emendas. Fica mais suave e mais flexível, mas custa mais (cerca de 3× em curvas e 9× em superfícies). Com os mesmos pontos, gera curvas diferentes. Cada segmento usa 4 pontos seguidos, mas só é desenhado entre os 2 do meio; o próximo segmento desliza um ponto.

A matriz da B-Spline, M_S, tem todos os números multiplicados por 1/6. Ela multiplica a coluna [P0, P1, P2, P3] e devolve [e, d, b, a]:

• Linha 1 → 1 4 1 0 ⇒ e = (P0 + 4·P1 + P2)/6. A curva começa numa média com peso maior em P1, e não em P0: por isso não passa pelos pontos.
• Linha 2 → −3 0 3 0 ⇒ d = (P2 − P0)/2.
• Linha 3 → 3 −6 3 0 ⇒ b = (P0 − 2·P1 + P2)/2.
• Linha 4 → −1 3 −3 1 ⇒ a = (−P0 + 3·P1 − 3·P2 + P3)/6.

NURBS (Non-Uniform Rational B-Spline). É uma B-Spline racional: um polinômio dividido por outro, p(u)/q(u), com um peso w em cada ponto. Em p(u)/q(u), o numerador p(u) soma cada ponto multiplicado pelo seu peso w e pela sua função de mistura, e o denominador q(u) soma só os pesos multiplicados pelas funções de mistura. Com todos os w = 1, q(u) = 1 e volta a ser uma B-Spline comum. A divisão funciona como uma média ponderada. Aumentar o peso puxa a curva para o ponto. Por ser uma fração, representa cônicas exatas, inclusive o círculo: com 3 pontos, o peso do meio decide se a curva é hipérbole (w > 1), parábola (w = 1) ou elipse (w < 1). É o padrão em modelagem e CAD, pela manipulação na tela. O ponto fraco: cálculos de colisão ficam caros a ponto de serem inviáveis.

Converter uma curva em outra

Duas descrições representam a mesma curva se dão os mesmos coeficientes. É só igualar e isolar:

• [cond₁]: as condições que você já tem, no modelo 1 (a origem). Exemplo: os 4 pontos da interpolada.
• [cond₂]: as condições equivalentes no modelo 2 (o destino), que se quer descobrir. Exemplo: os 4 pontos de controle da Bézier.
• [M₁], [M₂]: as matrizes características de cada modelo.
• [M₂⁻¹]: a inversa do destino. Ela "desfaz" M₂ e deixa [cond₂] sozinho: M₂⁻¹·M₂ = I.

O que a matriz de conversão faz: ela multiplica a coluna de condições da origem e devolve a coluna de condições do destino. Cada linha monta um ponto novo como mistura dos pontos antigos. Na conversão interpolada → Bézier, a 1ª linha é 1 0 0 0 (o novo P0 é o antigo P0) e a 4ª é 0 0 0 1 (o novo P3 é o antigo P3). As linhas do meio, −5/6 3 −3/2 1/3 e 1/3 −3/2 3 −5/6, misturam os quatro pontos para achar o P1 e o P2 da Bézier.

7. Superfícies implícitas 3 min

Aqui o objeto não é desenhado ponto a ponto: ele é uma função f(x, y, z), normalmente um polinômio, e a superfície é onde ela vale zero. O sinal diz onde está qualquer ponto:

• x, y, z: as coordenadas de um ponto qualquer do espaço que você quer testar.
• f(x, y, z): um número que se calcula para esse ponto. Não é uma posição; é como um "termômetro" cujo sinal diz o lado.
• Na esfera f = x² + y² + z² − r², r é o raio. x² + y² + z² é o quadrado da distância do ponto ao centro. Se ela é menor que r², f dá negativo (dentro); igual, zero (na superfície); maior, positivo (fora).

Objetos complexos saem combinando funções simples: f_R = f₁ op f₂ op … f_N. Aqui f₁ … f_N são as funções simples (cada esfera, por exemplo), op é uma operação entre elas (união, interseção, diferença, soma) e f_R é a função Resultante, que representa o objeto inteiro. A grande vantagem é que testar colisão ou interseção vira só "calcular o sinal". A desvantagem é desenhar, porque é preciso procurar onde f = 0.

Há cinco formas de obter f_R:

• Algébrica: definem-se as equações, as operações e a sequência. As mais comuns são as quádricas (esfera, elipsoide, toro). Exemplo, o elipsoide: (x/rₓ)² + (y/r_y)² + (z/r_z)² − 1 = 0, em que (x, y, z) é o ponto testado e rₓ, r_y, r_z são os "raios" em cada eixo (meia largura, meia altura, meia profundidade); se os três forem iguais, é uma esfera. O problema: a função pode se estender ao infinito, é difícil "podar" o pedaço desejado, e o grau cresce depressa.
• Blobby: f₁…f_N são só esferas de centros e raios variados, cada uma um "campo" que enfraquece com a distância. Um campo comum é D(r) = a·e^(−b·r²): D(r) é a força do campo num ponto, r é a distância desse ponto ao centro do blob, a é a força no centro, b diz quão rápido o campo enfraquece, e e ≈ 2,718 é o número de Euler. Somam-se os campos, e a superfície é onde a soma passa de um limiar (um valor escolhido). Dois blobs próximos se fundem suavemente, como gotas, e com mais blobs há mais detalhe.
• Esqueletos (bones): o campo envolve segmentos (ossos, tendões) como uma pele. Nas junções, os campos se somam e criam uma protuberância indesejada.
• Procedural: f é o resultado de um algoritmo, como o conjunto de Mandelbrot.
• Amostragem: valores de f guardados numa grade (voxels, como numa tomografia). A superfície passa entre os valores positivos e os negativos.

Por que é assim? O Blobby guarda poucos centros e raios, em vez de milhões de cubos, e por isso usa pouca memória. Em compensação, cada ponto exige somar todas as esferas, o que custa processamento. O voxel é só ler e escrever numa matriz: barato, mas faz degraus em curvas.

8. As 15 frases para lembrar 1 min

1. Antialiasing dá à borda um valor intermediário; reduz, mas não zera, o aliasing.
2. Superamostragem estima contando subpixels; amostragem por área calcula a área exata.
3. Paralela preserva dimensões; perspectiva dá profundidade e encolhe o que está longe.
4. Perspectiva: y = f·Y/Z, por triângulos semelhantes; Z dobra, a imagem cai pela metade.
5. Ortogonal descarta z; oblíqua desloca o ponto em L = z/tan α.
6. Sweep = figura 2D + translação ou rotação.
7. CSG = primitivas + ∪, ∩, −, numa árvore; a ordem importa.
8. Voxels guardam o interior, mas custam memória.
9. Octree e BSP organizam e manipulam a cena; não geram forma.
10. Octree: folha = área homogênea; nó intermediário = área heterogênea.
11. Malha triangular é flexível; quadrangular é econômica; na prática, híbrida.
12. Toda curva: [coef] = [A⁻¹]·[condições]; A⁻¹ é a matriz característica, constante.
13. Interpolada passa por tudo; Hermite exige tangentes; Bézier fica na envoltória convexa.
14. Conversão entre curvas = inversa do destino × matriz da origem.
15. Implícita: f = 0 na superfície, < 0 dentro, > 0 fora; Blobby arredonda com pouca memória.