Bruxaria Matemática em 1993: Como John Carmack Usou Divisão Binária para Fazer Doom Rodar Sem Placa de Vídeo

No dia 10 de dezembro de 1993, um arquivo executável comprimido foi compartilhado nos servidores universitários dos Estados Unidos. Em poucas horas, as redes de dados de instituições acadêmicas e corporações de grande porte travaram sob o peso de milhares de downloads simultâneos. A id Software acabava de liberar a versão shareware de Doom.

Para compreender o choque sísmico que o jogo causou no mundo da tecnologia, é preciso resgatar a realidade da computação doméstica no início dos anos 90. Naquela época, o computador de ponta era um Intel 486 DX2 rodando a 66 megahertz com 4 ou 8 megabytes de memória RAM. Placas aceleradoras 3D dedicadas simplesmente não existiam no mercado doméstico. Toda e qualquer operação visual precisava ser calculada milissegundo a milissegundo pela CPU principal.

O Gargalo Matemático da Terceira Dimensão

Desenhar um ambiente tridimensional em um monitor exige que o computador calcule a posição geométrica de cada parede, chão e inimigo, determine a profundidade de cada objeto e pinte os pixels corretos na tela. Se dois objetos estão na mesma linha de visão, o processador precisa saber qual está na frente para não desperdiçar preciosos ciclos desenhando algo que ficará encoberto.

Nos anos 90, os computadores eram terrivelmente lentos para executar essa checagem poligonal (o famoso Z-buffering) em tempo real. Se o motor de Doom tentasse desenhar o mapa do início ao fim usando força bruta, o jogo rodaria a humilhantes 3 ou 4 frames por segundo.

Foi aí que o gênio recluso da programação, John Carmack, recorreu à literatura matemática acadêmica e resgatou um conceito criado originalmente na década de 1960 para a simulação de radares militares: as Árvores de Particionamento Binário do Espaço (conhecidas pela sigla BSP — Binary Space Partitioning).

O Algoritmo do Pintor Invertido

A sacada revolucionária de Carmack foi perceber que o ambiente estático do mapa (as paredes e corredores das bases espaciais de Phobos) não mudava de lugar durante a partida. Portanto, esses dados podiam ser pré-processados e organizados geometricamente antes mesmo do jogador dar o primeiro tiro.

Ao compilar o mapa de uma fase, o utilitário cortava todo o cenário em uma árvore de decisões binárias:

• O mapa era fatiado em setores convexos simples.
• Cada nó da árvore determinava se um pedaço de parede estava à frente ou atrás de uma linha divisória.
• Durante o jogo, bastava a CPU checar a coordenada atual do jogador para saber instantaneamente a ordem exata de desenho das paredes, da mais próxima para a mais distante (front-to-back).

Esse método inverteu a clássica lógica do pintor. Em vez de pintar o fundo e depois jogar os objetos da frente por cima, a Doom Engine pintava primeiro as paredes mais próximas do campo de visão do jogador. Cada coluna vertical de pixels da tela que já havia sido preenchida era travada e ignorada pela CPU. Se havia uma sala inteira com trinta demônios atrás daquela parede de metal, o processador gastava zero ciclos de cálculo tentando renderizá-la.

A Mágica dos 35 Quadros por Segundo

O resultado dessa arquitetura matemática beirava o milagre. Doom não era um jogo totalmente 3D no sentido moderno de polígonos poligonais livres — você não podia olhar livremente para cima ou para baixo, e salas não podiam ficar diretamente em cima de outras salas no mesmo plano (razão pela qual o formato ficou conhecido como 2.5D).

No entanto, a velocidade da ilusão era perfeita. O jogo rodava cravado no limite interno de 35 frames por segundo com texturas detalhadas em tetos e pisos, iluminação dinâmica oscilante e dezenas de inimigos disparando bolas de fogo na tela simultaneamente.

Com um único compilador e uma profunda compreensão matemática, John Carmack não apenas revolucionou os jogos de tiro, mas acelerou em pelo menos uma década toda a indústria de placas gráficas e computação visual do mundo moderno.