Usar o BSP no Doom é realmente uma jogada engenhosa?

O auge da tecnologia da época.

Em 1993, a id Software lançou o Doom , um jogo de tiro em primeira pessoa que rapidamente se transformou em fenômeno. Hoje acredita-se que este seja um dos jogos que tiveram o maior impacto na história.

Dez anos após o lançamento do Doom , em 2003, o jornalista David Kouchner publicou um livro da id Software chamado Masters of Doom , que desde então se tornou uma descrição canônica do processo de criação do Doom . Li Masters of Doom há alguns anos e não me lembro de quase nada, mas uma história de um livro sobre o programador John Carmack foi preservada em minha memória. Minha descrição não será totalmente precisa (veja abaixo para mais detalhes), mas, resumindo, no estágio inicial do desenvolvimento de Doom , Carmack percebeu que o renderizador em 3D que ele escreveu para o jogo começou a desacelerar ao renderizar certos níveis. Isso era inaceitável, porque Doom tinha que se tornar um jogo ativo e até frenético. Percebendo que o problema do renderizador era tão fundamental que ele precisaria procurar um algoritmo de renderização mais ideal, Carmack começou a ler artigos de pesquisa. Como resultado, ele implementou uma técnica chamada BSP (binary space particitioning), que nunca havia sido usada em videogames antes e, portanto, acelerou significativamente o mecanismo Doom .

Essa história de como Carmack aplicou pesquisas científicas de ponta em videogames sempre me impressionou. Na minha opinião, foi graças a isso que Carmack se tornou uma figura tão lendária. Ele merece ser conhecido como um programador de videogame arquetípico e brilhante por várias razões, mas como principal, sempre me lembro do episódio com a leitura de artigos científicos e a partição binária do espaço.

Obviamente, essa história é impressionante, porque o termo "partição binária do espaço" parece ser algo complicado não apenas para implementação, mas também para compreensão. Por um longo tempo, presumi que o Carmack deu um salto intelectual, mas como não sabia o que é uma partição binária de espaço, e quão nova era essa técnica quando Carmack decidiu usá-la, não tive muita certeza. Quão engenhosa foi a adição de uma partição de espaço binário ao Doom em uma escala de Homer Simpson a Albert Einstein?

Também me perguntei de onde o BSP veio e como a idéia chegou ao Carmack. Portanto, este post será dedicado não apenas a John Carmack e Doom , mas também ao histórico da estrutura de dados da "árvore de partição de espaço binário" (ou árvore BSP). Verificou-se que a árvore BSP, como muitos outros aspectos das ciências computacionais, se origina em pesquisas conduzidas pelos militares.

Sim, está certo: o E1M1, o primeiro nível de Doom , apareceu graças à Força Aérea dos EUA.

Tarefa VSD

A árvore BSP é uma solução para uma das tarefas mais difíceis em computação gráfica. Para renderizar uma cena tridimensional, o renderizador deve determinar o que é visível e o que não é visível a partir do ponto atual. Isso não é particularmente difícil se você tiver muito tempo, mas um mecanismo de jogo que se preze em tempo real deve determinar as partes visíveis e invisíveis do mundo pelo menos 30 vezes por segundo.

Essa tarefa geralmente é chamada de tarefa de determinação da superfície visível (VSD). O programador Michael Abrash, que trabalhou com Carmack no Quake (o próximo jogo de software após Doom ), escreveu sobre a tarefa VSD em seu famoso livro Graphics Programming Black Book :

Quero falar sobre a tarefa mais difícil, na minha opinião, de gráficos 3D: determinar superfícies visíveis (desenhar a superfície desejada em cada pixel) e seu parente próximo - a tarefa de seleção (o mais rápido possível, lançar polígonos invisíveis para acelerar a determinação de superfícies visíveis). Por uma questão de brevidade, denotarei pela abreviação VSD a definição de superfícies visíveis e o recorte.

Por que considero o VSD a tarefa 3D mais difícil? Embora problemas de rasterização, como o mapeamento de textura, também sejam tarefas surpreendentes e importantes, são tarefas de uma escala bastante finita, cuja solução é alterada para a aparência de aceleradores 3D nos equipamentos; além disso, eles só aumentam quando a resolução da tela é aumentada, o que é bastante suportável.

Por outro lado, o VSD é uma tarefa ilimitada e agora dezenas de soluções são usadas para resolvê-lo. Ainda mais importante, o desempenho ingênuo do VSD é dimensionado diretamente com a complexidade da cena, que geralmente aumenta como uma função quadrada ou cúbica, tornando-se rapidamente o fator limitante na renderização de mundos realistas.

Abrash escreveu sobre a complexidade do problema de VSD no final dos anos 90, alguns anos depois que o Doom provou que as pessoas comuns querem poder jogar jogos graficamente pesados ​​em seus computadores domésticos. No início dos anos 90, quando a id Software estava apenas começando a publicar jogos, eles tiveram que trabalhar efetivamente em computadores inadequados: as máquinas domésticas foram projetadas para trabalhar com texto, planilhas e outros aplicativos similares. Para atingir esse objetivo, a empresa teve que se aproximar da ficção, especialmente no caso de vários jogos em 3D publicados pela id Software antes do Doom . Nesses jogos, o design de todos os níveis era limitado de maneira a simplificar a solução do problema de VSD.

Por exemplo, no Wolfenstein 3D , o jogo que a id Software lançou pouco antes do Doom , cada nível consistia em paredes alinhadas ao longo dos eixos. Em outras palavras, no universo Wolfenstein poderia haver paredes norte / sul ou paredes leste / oeste, e nenhuma outra. Além disso, as paredes podem ser colocadas a distâncias fixas na grade - todos os corredores têm uma largura de uma célula da grade, ou duas, etc., mas nunca 2,5 células. Embora isso significasse que a equipe da id Software poderia criar níveis quase iguais, essa restrição tornou muito fácil para Carmack escrever um renderizador para Wolfenstein .

O renderizador Wolfenstein resolveu o problema do VSD movendo raios (marchas de raios) para o mundo virtual a partir da tela. Normalmente, renderizadores renderizados em raio são renderizadores de emissão de raios - eles geralmente são lentos porque a solução do problema VSD no raycaster exige encontrar a primeira interseção entre o raio e algum objeto no mundo, o que exige muita computação. Mas como todas as paredes de Wolfenstein estão alinhadas com uma grade, os únicos lugares onde uma viga pode atravessar a parede serão as linhas de grade. Portanto, é suficiente para o renderizador verificar cada um desses pontos de interseção. Se o renderizador começar verificando o ponto de interseção mais próximo do ponto de vista do jogador, depois verificar o segundo em proximidade, e assim por diante, e terminar quando encontrar a primeira parede, o problema do VSD será resolvido da maneira mais trivial. O feixe simplesmente avançou de cada pixel até encontrar algo, o que é muito barato em termos de velocidade do clock do processador. E como todas as paredes têm a mesma altura, basta emitirmos raios para cada coluna de pixels.

Essa simplificação da renderização tornou Wolfenstein rápido o suficiente para trabalhar em computadores domésticos fracos da época, quando não havia placas gráficas especializadas. Mas essa abordagem não funcionaria no Doom , porque a equipe de identificação decidiu que em seu novo jogo haveria elementos novos como paredes diagonais, escadas e tetos com diferentes alturas. A marcha dos raios não era mais adequada, então Carmack escreveu um tipo diferente de renderizador. O renderizador Wolfenstein , onde o feixe foi usado para cada coluna de pixels, foi repelido da imagem, e o renderizador Doom deveria ser repelido de objetos. Isso significava que, em vez de percorrer os pixels da tela e determinar sua cor, o renderizador do Doom precisava iterar sobre os objetos na cena e projetar cada um deles na tela.

Nesse renderizador, uma maneira simples de resolver o problema do VSD é usar um buffer z. Cada vez que projetamos um objeto na tela, uma verificação é realizada para cada pixel que queremos desenhar. Se a parte do objeto a ser desenhado estiver mais próxima do player do que o objeto já desenhado no pixel, poderemos reescrever suas informações. Caso contrário, você precisará deixar o pixel inalterado. Essa abordagem é simples, mas o buffer z requer muita memória, e o renderizador ainda pode gastar vários relógios do processador em projetar geometria de nível que o player não verá.

No início dos anos 90, a solução z-buffer teve mais uma desvantagem: em PCs compatíveis com IBM, usando um sistema de adaptador de vídeo chamado VGA, gravar no buffer do quadro de saída era uma operação dispendiosa. Portanto, o tempo gasto na renderização de pixels, que serão substituídos simplesmente, reduziu bastante o desempenho do renderizador.

Como a gravação no buffer de quadros era tão cara, o renderizador ideal era começar desenhando os objetos mais próximos do player, depois os objetos imediatamente atrás deles, e assim por diante, até a gravação em cada pixel da tela. Nesse estágio, o renderizador deveria ter entendido que era hora de parar, economizando o tempo que passava explorando objetos distantes que o jogador não via. Mas encomendar objetos de cena dessa maneira, do mais próximo ao mais distante, é o mesmo que resolver o problema de VSD. A questão novamente se coloca diante de nós: o que um jogador pode ver?


Inicialmente, Carmack tentou resolver esse problema, contando com o esquema de níveis de Doom . Seu renderizador começou desenhando as paredes da sala em que o jogador está localizado e depois despejou-se nas salas vizinhas para desenhar paredes nessas salas, que podiam ser visíveis na sala atual. Se cada sala fosse convexa, isso resolveria o problema de VSD. As salas não convexas podem ser divididas em "setores" convexos. Você pode ver como essa técnica de renderização pode parecer uma forte desaceleração no vídeo acima , onde um usuário do YouTuber com o apelido Bisqwit demonstra seu próprio renderizador que funciona de acordo com o mesmo algoritmo geral. Esse algoritmo foi usado com sucesso no jogo 3D Duke Nukem, lançado três anos após o Doom , quando os processadores se tornaram mais poderosos. Mas em 1993, na época, o renderizador Doom que usava esse algoritmo teve problemas com níveis complexos. Isso foi especialmente óbvio quando os setores foram incorporados um ao outro, e essa foi a única maneira de criar, por exemplo, escadas circulares. Escadas circulares exigiam várias descidas recursivas para o setor já desenhado, reduzindo drasticamente a velocidade do motor.

Na mesma época, quando a equipe de identificação percebeu que o mecanismo Doom poderia estar muito lento, foi solicitado à id Software que portasse o Wolfenstein 3D para a Super Nintendo. O SNES era ainda menos poderoso do que os PCs compatíveis com a IBM da época, e o renderizador Wolfenstein com tecnologia de marcação de raios, apesar de sua simplicidade, não era executado nos equipamentos da Super Nintendo com velocidade suficiente. Portanto, Carmack começou a procurar um algoritmo melhor. De fato, foi para a porta Super Nintendo de Wolfenstein que Carmack primeiro explorou e implementou o particionamento de espaço binário. Em Wolfenstein , era bem simples, porque todas as paredes eram paralelas aos eixos; Doom torna mais difícil. Mas Carmack percebeu que as árvores BSP também resolveriam problemas de velocidade no Doom .

Divisão de espaço binário

O particionamento de espaço binário simplifica a solução para o problema de VSD, dividindo previamente a cena 3D. Por enquanto, basta você entender por que a partição é útil: se você desenhar uma linha (que na verdade é um avião em 3D) durante toda a cena, sabendo em que lado da linha o player ou a câmera está, então também saberemos que nada é o outro lado da linha não poderá obstruir os objetos da linha em que a câmera está localizada. Se você repetir o processo várias vezes, obteremos uma cena 3D, dividida em várias seções. Isso não será uma melhoria em relação à cena original, exceto que agora sabemos mais sobre como diferentes partes da cena podem se sobrepor.

Os primeiros a escrever sobre essa divisão da cena 3D foram os pesquisadores que tentaram descobrir para a Força Aérea dos EUA se os gráficos de computador são progressivos o suficiente para serem usados ​​em simuladores de vôo. Eles publicaram suas descobertas em um relatório de 1969 intitulado "Pesquisa sobre o uso de imagens geradas por computador na simulação visual". O relatório concluiu que a computação gráfica pode ser usada para treinar pilotos; Ao mesmo tempo, os pesquisadores alertaram que a implementação do sistema seria complicada pela tarefa do VSD:

Uma das tarefas mais importantes que precisarão ser resolvidas ao calcular imagens em tempo real é a tarefa prioritária ou linhas ocultas. Em nossa percepção visual cotidiana do mundo à nossa volta, a própria natureza resolve esse problema com simplicidade trivial; o ponto de um objeto opaco se sobrepõe a todos os outros pontos que estão ao longo da mesma linha de visão e estão mais distantes. No caso de um computador, essa tarefa é muito difícil. A quantidade de computação necessária para determinar a prioridade, no caso geral, cresce exponencialmente com o aumento da complexidade do ambiente e logo excede a carga computacional associada à pesquisa de imagens de objetos levando em consideração a perspectiva.

Uma solução mencionada por esses pesquisadores, que eles disseram ter sido usada anteriormente em um projeto da NASA, baseia-se na criação do que chamarei de "matriz de sobreposição". Os pesquisadores apontam que um avião que divide uma cena em duas partes pode ser usado para resolver "qualquer conflito de prioridades" entre objetos em lados opostos do avião. No caso geral, pode ser necessário adicionar esses planos à cena explicitamente, mas para uma certa estrutura geométrica, você pode confiar nas faces existentes dos objetos. Pesquisadores demonstram o exemplo abaixo, onde p1 , p2 e p3 estão dividindo superfícies. Se o ponto de vista da câmera estiver na frente ou no lado "verdadeiro" de um desses planos, então pi será 1. A matriz mostra a relação entre os três objetos, dependendo dos três planos de separação e da localização do ponto de vista da câmera - se o objeto ai sobrepuser o objeto aj , então o elemento aij da matriz será igual a 1.


Os pesquisadores propuseram implementar essa matriz em hardware e recalculá-la em cada quadro. De fato, a matriz deve atuar como um comutador grande ou como um tipo de z-buffer embutido. Ao renderizar o objeto atual, o vídeo não é exibido para partes do objeto quando 1 está na coluna do objeto, mas o objeto de linha correspondente é desenhado.

Uma desvantagem séria dessa abordagem é que é necessária uma matriz de tamanho n ² para descrever uma cena com n objetos. Portanto, os pesquisadores decidiram verificar se é possível apresentar a matriz de sobreposição na forma de uma “lista de prioridades”, que terá um tamanho de apenas n e especificar a ordem em que os objetos devem ser desenhados. Eles imediatamente perceberam que em certas cenas, por exemplo, na mostrada acima, é impossível concluir a ordenação (uma vez que existe um ciclo de sobreposição), por isso dedicaram muito tempo à definição matemática de cenas “certas” e “erradas”. No final, eles chegaram à conclusão de que, pelo menos para as cenas “certas” (e o designer da cena pode facilmente evitar os casos “errados”), uma lista de prioridades pode ser gerada. Mas eles deixaram a geração da lista como um exercício para o leitor. Parece que a principal contribuição deste trabalho de 1969 é indicar que pelo menos teoricamente deveria haver a possibilidade de usar planos de divisão para organizar objetos na cena.

E somente em um artigo de 1980 intitulado "Na geração visível de superfícies por estruturas de árvores prioritárias" foi demonstrado um algoritmo específico para isso. Neste artigo, escrito por Henry Fuchs, Zvi Kedem e Bruce Naylor, a árvore do BSP foi descrita pela primeira vez. Os autores afirmam que sua nova estrutura de dados é "uma solução, uma abordagem alternativa, usada pela primeira vez há dez anos, mas devido a algumas dificuldades não tão difundidas" - e, portanto, respondem à decisão escolhida no trabalho da Força Aérea dos EUA em 1969. Após a construção de uma árvore BSP, ela pode ser facilmente usada para organizar objetos com prioridade na cena.

Fuchs, Kedem e Naylor forneceram uma descrição bastante clara da operação da árvore do BSP, mas tentarei fornecer uma descrição menos formal, mas breve.

Começamos selecionando um polígono na cena e fazemos do plano no qual o polígono se encontra um plano divisor. Esse polígono único também se torna o nó raiz da árvore. Os polígonos restantes da cena estarão em um ou no outro lado do plano de divisão da raiz. Polígonos no lado "frontal" ou no meio espaço "frontal" do plano aparecem na subárvore esquerda do nó raiz e polígonos no lado "traseiro" ou no meio espaço "traseiro" do plano aparecem na subárvore direita. Em seguida, repetimos recursivamente esse processo, selecionando polígonos das subárvores esquerda e direita como as novas superfícies divisórias para seus próprios meios-espaços, que geram mais meios-espaços e subárvores. O processo termina quando os polígonos terminam.

Digamos que queremos renderizar a geometria da cena de trás para a frente.(Isso é chamado de "algoritmo do artista" porque significa que os polígonos mais distantes da câmera serão preenchidos com polígonos mais próximos da câmera, criando a renderização correta.) Para realizar isso, basta percorrer nossa árvore BSP em ordem; a decisão sobre se a subárvore esquerda ou direita deve ser desenhada é tomada com base no local do ponto de vista da câmera - no meio espaço frontal ou traseiro em relação ao plano de divisão associado a este nó. Ou seja, em cada nó da árvore, primeiro renderizamos todos os polígonos no lado "distante" do plano, depois o polígono no plano de separação e, em seguida, os polígonos no lado "próximo" do plano. Os polígonos "Próximo" e "Distante" são definidos em relação ao ponto de vista da câmera. Isso resolve o problema de VSD porque, como aprendemos alguns parágrafos atrás,os polígonos do lado oposto do plano de separação não podem se sobrepor a nada no lado frontal.

O diagrama abaixo mostra a construção e a travessia de uma árvore BSP que descreve uma cena 2D simples. Em 2D, linhas divisórias são usadas em vez de dividir planos, mas a ideia básica permanece a mesma.




Um recurso muito conveniente da árvore do BSP que Fuchs, Kedem e Naylor enfatizam várias vezes é que ele precisa ser construído apenas uma vez. Isso parece surpreendente, mas uma árvore BSP pode ser usada para renderizar a cena, independentemente do ponto de vista da câmera. A árvore do BSP permanece utilizável até que os polígonos da cena se movam. É por isso que a árvore do BSP é tão útil para renderização em tempo real - todo o trabalho complexo de construir uma árvore pode ser feito antecipadamente, e não no momento da renderização.

Fuchs, Kedem e Naylor relatam que novas pesquisas requerem a criação de uma "boa" árvore de BSP. A qualidade da árvore do BSP depende de quais polígonos você escolhe para definir os planos de separação. Anteriormente, pulei esse ponto, mas se você usar um plano que cruza outros polígonos ao dividir, para que o algoritmo BSP funcione, é necessário dividir os polígonos cruzados em dois, de modo que uma metade se refira a um meio espaço e a outra à outra. Se isso acontecer com frequência, a construção de uma árvore BSP aumenta significativamente o número de polígonos na cena.

Bruce Naylor, um dos autores de um artigo de 1980, escreveu mais tarde sobre esse assunto em seu artigo de 1993, Construindo boas árvores de particionamento. De acordo com o colega de Carmack e co-fundador da id Software, John Romero, este artigo foi um dos trabalhos que Carmack leu quando tentou implementar árvores BSP no Doom .

Árvores BSP no Doom

Lembre-se de que, no primeiro rascunho do renderizador Doom , Carmack tentou definir a ordem de renderização da geometria de nível, preenchendo o renderizador da sala onde o jogador está nas salas vizinhas. As árvores do BSP eram uma maneira mais conveniente de determinar essa ordem, porque evitavam o problema do renderizador ter que visitar repetidamente uma sala (ou setor), desperdiçando ciclos do processador.

“Adicionar árvores BSP ao Doom ” na prática significava adicionar um gerador de árvores BSP ao editor de nível do Doom . Depois de concluir a criação do nível Doomuma árvore BSP foi gerada a partir da geometria do nível. Segundo Fabien Sanglar, o processo de geração pode levar até oito segundos para um nível e 11 minutos para todos os níveis do primeiro Doom . O processo de geração foi tão demorado em parte devido ao fato de que o algoritmo de geração Carmack BSP está tentando encontrar uma árvore "boa" do BSP usando várias heurísticas. Um atraso de oito segundos seria imperdoável durante o jogo, mas após a geração preliminar parecia bastante aceitável, dado o aumento no desempenho que as árvores do BSP forneceram ao renderizador. A árvore BSP gerada de um nível individual foi salva como parte dos dados do nível carregados no jogo quando foi lançado.

Carmack fez uma mudança importante no algoritmo de árvore BSP descrito em um artigo de 1980: após o lançamento do Doome lendo a árvore BSP do nível atual na memória, o renderizador usa essa árvore para desenhar objetos não de frente para frente, mas de frente para trás. Em um artigo de 1980, Fuchs, Kedem e Naylor demonstraram como uma árvore BSP pode ser usada para implementar o algoritmo de um artista com renderização consecutiva, mas uma grande quantidade de repinturas ocorre no algoritmo do artista, o que pode ser caro em PCs compatíveis com IBM. Portanto, o renderizador do Doom começa com uma geometria mais próxima do jogador e, em seguida, desenha o mais distante. Essa ordem inversa é fácil de implementar usando uma árvore BSP, porque você pode simplesmente tomar uma decisão de retorno em cada nó da árvore. Para impedir que geometria mais distante seja desenhada em cima, o renderizador Doomusa um tipo de buffer z implícito, que fornece muitos dos benefícios de um buffer z regular, enquanto consome muito menos memória. Há uma matriz que rastreia a sobreposição na dimensão horizontal e outras duas matrizes que rastreiam a sobreposição na direção vertical acima e abaixo da tela. O renderizador do Doom poderia ficar sem usar um buffer z verdadeiro, porque o Doom , estritamente falando, não era um jogo completamente tridimensional. Estruturas de dados menos caras funcionavam porque alguns elementos não eram possíveis no Doom : a matriz de sobreposição horizontal funcionava porque não havia paredes inclinadas e as matrizes de sobreposição vertical funcionavam porque não havia paredes nas quais, por exemplo, havia duas localizadas um acima das outras janelas.


Doom II , tão complexo quanto seu antecessor.


Mas ninguém reclamou da repetição de sangue.


Uma nova palavra nas tecnologias Quake A

única tarefa complicada que resta é como integrar os caracteres móveis do Doom na geometria estática dos níveis desenhados usando a árvore BSP. Os inimigos no Doom não podiam fazer parte da árvore do BSP porque estavam se movendo; A árvore BSP funciona apenas com geometria fixa. Portanto, o renderizador Doomprimeiro desenha a geometria estática do nível, rastreando (usando outra estrutura de dados com eficiência de memória) os segmentos da tela em que o desenho foi executado. Em seguida, ele desenha os inimigos de trás para frente, truncando-os ao longo dos segmentos da tela que os sobrepõem. Esse processo não é tão ideal quanto a renderização com uma árvore BSP, mas como geralmente há menos inimigos que a geometria, a velocidade não é um problema aqui.

Usar árvores BSP no Doom foi uma grande vitória. Obviamente, Carmack foi perspicaz o suficiente para perceber que as árvores BSP seriam a solução ideal. Mas essa decisão foi engenhosa ?

Em seu excelente livro sobre o mecanismo de jogo DoomFabien Sanglar cita John Romero, que disse que o artigo de Bruce Naylor, “Construindo boas árvores de particionamento”, era principalmente sobre o uso de árvores BSP para aparar as faces traseiras de modelos 3D. De acordo com Romero, Carmack achou que o algoritmo ainda poderia ser útil para o Doom , então ele o implementou. Isso é bastante louvável para Carmack, porque ele implica que ele viu a utilidade das árvores BSP em videogames em tempo real, mesmo quando outras pessoas ainda usavam essa técnica para renderizar cenas estáticas. A mesma história lisonjeira está em Masters of Doom: Kouchner sugeriu que Carmack leu o artigo de Naylor e se perguntou: "e se você puder usar a árvore BSP para criar não apenas uma imagem 3D, mas um mundo virtual inteiro?"

Essas descobertas ignoram a história da árvore BSP. Quando os pesquisadores da Força Aérea dos EUA perceberam que dividir uma cena poderia ajudar a acelerar a renderização, eles estavam interessados na aceleração da renderização em tempo real, porque no final eles tentaram criar um simulador de vôo. O exemplo do simulador de vôo é mencionado novamente em um artigo de 1980. Fuchs, Kedem e Naylor escrevem que a árvore BSP pode ser útil em um simulador de vôo que os pilotos usam para fazer vários pousos no mesmo aeroporto. Como a geometria do aeroporto nunca muda, uma árvore BSP pode ser gerada apenas uma vez. Obviamente, eles estavam pensando em simulação em tempo real. Na introdução do artigo, eles até explicam suas pesquisas testando a possibilidade de usar um sistema gráfico em tempo real para criar imagens em não mais que 1/30 segundo.

Ou seja, Carmack não foi o primeiro a pensar em usar árvores BSP em simulação gráfica em tempo real. Obviamente, prever que as árvores BSP podem ser usadas dessa maneira e implementar isso são coisas completamente diferentes. Mas mesmo com a implementação, o Carmack poderia ter mais informações básicas do que se pensa. O artigo do WSP sobre árvores do BSP sugere que Carmack se referiu ao artigo de 1991 de Chen e Gordon, bem como ao livro de 1990 Computer Graphics: Principles and Practice . Embora essa declaração não seja suportada por uma citação, ela pode ser verdadeira. Um artigo de 1991 de Chen e Gordon descreve a renderização de frente para trás usando árvores BSP, que é essencialmente a mesma solução usada pelo Doom, até a estrutura de dados "buffer z implícito", que não permite desenhar polígonos distantes sobre os vizinhos. O artigo fornece uma excelente visão geral das árvores BSP, bem como o pseudocódigo para construir e exibir uma árvore. (Graças à maravilhosa biblioteca da minha universidade, eu pude percorrer a edição de 1990.) O livro Computação Gráfica: Princípios e Prática é um trabalho clássico sobre computação gráfica, para que Carmack também possa ter um.


Nível E1M1 do subsetor: Hangar.

Seja como for, Carmack enfrentou uma nova tarefa - “Como posso criar um jogo de tiro em primeira pessoa que seja executado em um computador com um processador que nem sequer é capaz de executar operações de ponto flutuante?” - conduziu sua própria pesquisa e provou que as árvores BSP são Essa é uma estrutura de dados útil para videogames em tempo real. Ainda acho que esse é um resultado impressionante, mesmo que a árvore do BSP tenha sido inventada dez anos antes e tenha sido estudada teoricamente em detalhes suficientes no momento em que Carmack leu sobre isso. Talvez a principal conquista que devemos elogiar seja o mecanismo Doom como um todo, que se tornou um ótimo exemplo de código. Eu já falei sobre isso uma vez, mas repito que o livro de Fabien Sanglar sobre o mecanismo de jogoDoom ( Livro Negro do Game Engine: DOOM ) é uma excelente visão geral de todos os componentes importantes do mecanismo do jogo e sua interação. Não devemos esquecer que a tarefa VSD foi apenas uma das muitas tarefas que Carmack teve que resolver para que o mecanismo Doom funcionasse . E que ele foi capaz de, além de tudo, ler sobre a complexa estrutura de dados desconhecida pela maioria dos programadores e implementá-la. Isso diz muito sobre o nível de seu conhecimento técnico e compromisso com o ideal.