O veterano de programação gráfica tridimensional Michael Abrash, usando o exemplo do desenvolvimento do primeiro Quake, fala sobre a necessidade de pensamento criativo em programação.Há muitos anos, trabalhei na agora extinta empresa de adaptadores de vídeo Video Seven. Lá eu ajudei a desenvolver um clone VGA. Meu colega Tom Wilson, que trabalhou por muitos meses 24 horas para desenvolver o chip Video Seven VGA, tentou tornar o VGA o mais rápido possível e tinha certeza de que seu desempenho foi otimizado quase ao máximo. No entanto, quando Tom já estava dando os retoques finais no design do chip, ouvimos rumores de que nosso concorrente Paradise havia conseguido um desempenho ainda maior em seu clone de desenvolvimento ao adicionar FIFO a ele.
Este foi o fim dos rumores - não sabíamos o que era o FIFO, nem quanto ele ajudou, nada mais. No entanto, Tom, geralmente uma pessoa amigável e descontraída, se transformou em um fanático ativo e obcecado com muita cafeína no sangue. Com base nessas informações, ele tentou descobrir o que o Paradise era capaz de fazer. No final, ele chegou à conclusão de que o Paradise provavelmente inseriu um buffer de gravação FIFO entre o barramento do sistema e o VGA, de modo que, quando a CPU estivesse gravando na memória de vídeo, os dados gravados fossem imediatamente para o FIFO, e isso permitiria que a CPU continuasse processando em vez de ficar ociosa toda vez quando ele estava escrevendo na memória do visor.
Tom não tinha elementos lógicos, nem tempo suficiente para implementar um FIFO completo, mas conseguiu implementar o FIFO com uma única profundidade de operação, o que permitiu ao processador ultrapassar o chip VGA por uma operação de gravação. Tom não tinha certeza de que isso daria bons resultados, mas era a única coisa que ele poderia fazer, então implementou esse sistema e transferiu o chip para a produção.
Verificou-se que o FIFO de uma operação funciona incrivelmente legal: naquela época, os sete chips VGA Video Seven eram os mais rápidos do mercado; eles se tornaram evidência da genialidade de Tom e do que o criador é capaz sob a pressão das circunstâncias. No entanto, o melhor dessa história é que o projeto FIFO do Paradise não teve nada a ver com o design do Tom, e
não funcionou . A Paradise inseriu um buffer FIFO de
leitura entre a memória do monitor e o estágio de saída de vídeo do chip VGA, o que possibilitou a leitura antecipada da saída de vídeo para que, quando a CPU precisasse acessar a memória do monitor, os pixels pudessem ser retirados do FIFO e o comando da CPU fosse executado instantaneamente. Isso realmente melhorou o desempenho, mas não tanto quanto o buffer de gravação FIFO de Tom.
E esse caso pode ser considerado uma boa parábola sobre a própria natureza do processo criativo que uma pessoa pode alcançar. Recortes de notícias sobre o chip Paradise quase não continham informações factuais, mas forçaram Tom a ir além dos limites que ele subconscientemente estabeleceu, desenvolvendo o design inicial do chip. Acredito que este é o elemento mais importante de qualquer design engenhoso, seja no campo de hardware, software ou em qualquer outra esfera criativa, e foi ele quem nasceu nas notícias de Tom sobre Paradise: a capacidade de detectar os limites que você construiu no processo de trabalhar no projeto e superá-los fronteiras.
O problema, é claro, é como superar as fronteiras, cuja existência você nem conhece. Não existe uma fórmula para o sucesso, mas dois princípios podem servir bem a esse propósito: primeiro, simplifique; depois, tente constantemente algo novo.
Normalmente, quando você sente que o código está ficando complicado, você começa a fazer pequenas alterações na estrutura congelada e há uma alta probabilidade de aumentar a produtividade e reduzir a quantidade de código inventando o design novamente. Uma estrutura realmente boa deve trazer um momento de profunda satisfação quando tudo se encaixa, e você fica surpreso com o quão pequena é a quantidade de código necessária e com o desempenho de todos os casos de fronteira.
No processo de revisão da estrutura, é importante estudar todas as idéias que vêm à mente, não importa quão loucas elas possam parecer. Muitas das grandes idéias que ouvi a princípio pareciam absurdas porque não se encaixavam na minha imagem atual do mundo. Muitas vezes, essas idéias são realmente loucas, mas, assim como as notícias sobre os chips da Paradise estimularam a imaginação de Tom, a exploração agressiva de idéias aparentemente ilusórias pode abrir novas possibilidades para você.
Boa ilustração: a evolução do mecanismo gráfico Quake 3D.
A tarefa de gráficos 3D mais complexa do mundo
Passei os últimos sete meses trabalhando no Quake, herdeiro da id Software pela DOOM, e presumo que mais três meses depois, quando você ler este artigo, o Quake será lançado como shareware.
Em termos de gráficos, Quake será para o DOOM o que o DOOM era para o seu antecessor, Wolfenstein 3D. Quake adiciona 3D arbitrário real (o jogador pode olhar para cima e para baixo, inclinar-se para os lados e até cair para um lado), iluminação e sombras detalhadas, monstros e personagens em 3D em vez de sprites DOOM. Em breve vou falar sobre tudo isso com mais detalhes, mas este mês quero falar sobre o problema, que em meu livro chamo de mais difícil em gráficos tridimensionais: determinar superfícies visíveis (desenhar a superfície correspondente para cada pixel) e sobre uma tarefa muito próxima - sobre recorte (o mais rápido possível, descartando polígonos invisíveis como forma de acelerar a determinação de superfícies visíveis). Por uma questão de brevidade, usarei a abreviação VSD para denotar a definição de determinação e seleção visível da superfície.
Por que considero o VSD a tarefa mais difícil dos gráficos 3D? Embora as tarefas de rasterização, por exemplo, mapeamento de textura, sejam igualmente surpreendentes e importantes, elas têm um escopo bastante limitado e, após o advento dos aceleradores 3D, sua solução será transferida para o hardware; além disso, sua escala depende apenas da resolução da tela, ou seja, são bastante modestas.
Por outro lado, o VSD é uma tarefa ilimitada e dezenas de abordagens estão sendo usadas para resolvê-lo. Mais importante, porém, o desempenho do VSD em uma solução ingênua varia de acordo com a complexidade da cena, que geralmente aumenta como uma função quadrática ou cúbica e, portanto, rapidamente se torna o fator limitante na criação de mundos realistas. Acredito que nos próximos anos, o VSD se tornará um problema cada vez mais dominante nos gráficos 3D em tempo real para PCs, porque os detalhes dos mundos 3D aumentarão constantemente. Atualmente, um nível de tamanho sólido do Quake pode conter cerca de 10.000 polígonos, ou seja, quase três vezes mais do que um nível comparável de DOOM.
Estrutura de nível de terremoto
Antes de investigar o VSD, deixe-me mencionar que cada nível do Quake é armazenado como uma enorme árvore tridimensional do BSP. Essa árvore do BSP, como qualquer outro BSP, divide o espaço, neste caso, ao longo dos planos dos polígonos. No entanto, diferentemente da árvore do BSP que demonstrei anteriormente, a árvore do Quake BSP não armazena polígonos nos nós da árvore como parte dos planos de divisão, mas em folhas vazias (não preenchidas), como mostra a Figura 1 na vista superior.
Figura 1. No Quake, os polígonos são armazenados em folhas vazias. Áreas escuras são folhas cheias (volumes cheios, como o interior das paredes)A ordem correta de renderização pode ser obtida renderizando as folhas na ordem BSP “frente para trás” ou “trás para frente”. Além disso, como as folhas do BSP são sempre convexas e os polígonos são os limites das folhas do BSP voltadas para dentro, os polígonos de qualquer folha nunca podem se sobrepor e podem ser desenhados em qualquer ordem. (Esta é uma propriedade geral do poliedro convexo.)
Recorte e definição de superfícies visíveis
Idealmente, o processo VSD deve funcionar da seguinte maneira: primeiro, você precisa descartar todos os polígonos que estão fora da pirâmide de visibilidade e também cortar todas as partes invisíveis dos polígonos que estão parcialmente visíveis. Em seguida, você precisa desenhar apenas os pixels de cada polígono que são realmente visíveis do ponto de vista atual, como mostra a Figura 2 na vista superior, sem perder tempo redesenhando repetidamente os pixels; observe quantos polígonos na Figura 2 você precisa desenhar. E, finalmente, em um mundo ideal, verificar a visibilidade de partes dos polígonos deve ser barato e o tempo de processamento deve ser o mesmo para todos os pontos de vista possíveis, para que o jogo funcione sem problemas.
Figura 2. A arquitetura VSD ideal renderiza apenas as partes visíveis dos polígonos visíveis.No processo de realização dessa tarefa, é fácil determinar quais polígonos estão completamente fora do escopo da pirâmide de visibilidade ou parcialmente cortados, e é bem possível descobrir exatamente quais pixels desenhar. Infelizmente, o mundo está longe de ser o ideal e todas essas verificações são caras, portanto, o truque é acelerar ou pular verificações diferentes, criando o resultado necessário.
Como expliquei em detalhes em artigos anteriores, com um BSP, você pode percorrer o mundo com facilidade e baixo custo, em ordem de frente para trás ou de trás para frente. A solução VSD mais simples é simplesmente atravessar a árvore de trás para a frente, truncar cada polígono com uma pirâmide de visibilidade e desenhá-la se seu rosto estiver direcionado para a câmera e não cortado completamente (algoritmo do artista). Mas isso é uma solução adequada?
Para mundos relativamente simples, é bastante aplicável. No entanto, ele não escala bem. Um dos problemas é que, quando novos polígonos são adicionados ao mundo para eliminar polígonos invisíveis, são necessárias mais e mais transformações e verificações; após um certo limite, isso começará a diminuir significativamente o desempenho.
Felizmente, esse problema específico tem uma boa solução alternativa. Como mencionado acima, cada folha na árvore do BSP descreve um subespaço convexo, e os nós conectados à folha limitam o espaço. Menos óbvio é que cada nó na árvore do BSP também descreve um subespaço - um subespaço que consiste em todos os filhos do nó, como mostra a Figura 3. É possível assim: cada nó divide em duas partes o subespaço criado pelos nós localizados acima em árvore e os elementos filhos do nó, enquadrando ainda mais esse subespaço em todas as folhas provenientes do nó.
Figura 3: O nó E descreve um subespaço escuro que contém as folhas 5, 6, 7 e o nó F.Como o subespaço do nó é limitado e convexo, podemos verificar se ele está completamente fora da pirâmide de visibilidade. Nesse caso,
todos os filhos do nó serão definitivamente cortados completamente e poderão ser descartados sem processamento adicional. Como a parte principal do mundo geralmente está localizada fora da pirâmide de visibilidade, muitos polígonos do mundo podem ser cortados quase sem custo por enormes fragmentos de subespaços de nós. A execução de uma verificação ideal para subespaços de recorte é bastante dispendiosa, portanto, geralmente para cada nó, paralelogramos ou esferas restritos são usados para verificações de recorte.
Ou seja, cortar ao longo da pirâmide de visibilidade não é um problema e você pode usar o BSP para retroceder. Então qual é o problema?
Redesenhar
O problema que o principal autor das tecnologias DOOM e Quake que John Carmack enfrentou ao desenvolver o Quake foi que, em um mundo complexo, muitas cenas na pirâmide de visibilidade possuem um grande número de polígonos. A maioria desses polígonos é parcial ou completamente sobreposta por outros polígonos, mas o algoritmo do artista descrito acima requer desenhar cada pixel de cada polígono na pirâmide de visibilidade. No entanto, eles geralmente são renderizados apenas para serem redesenhados por outros. No nível de 10.000 polígonos do Quake, é fácil obter o pior caso de redesenho quando os pixels são desenhados 10 ou mais vezes; isto é, em alguns quadros, cada pixel, em média, será desenhado 10 ou mais vezes. Nenhum rasterizador é rápido o suficiente para compensar a ordem de magnitude necessária para renderizar uma cena; pior, o algoritmo do artista cria enormes diferenças de desempenho entre os melhores e os piores casos, o que leva a uma mudança significativa na taxa de quadros ao mover o visualizador.
Portanto, John enfrentou o problema de reduzir a quantidade de redesenho para níveis aceitáveis. Idealmente, cada pixel deve ser desenhado apenas uma vez, mas no máximo duas ou três vezes. Quanto a cortar a pirâmide de visibilidade, idealmente, era necessário que todos os polígonos invisíveis na pirâmide fossem cortados com quase nenhum custo extra. Uma vantagem seria também que seria possível desenhar apenas as partes visíveis dos polígonos parcialmente visíveis, mas, ao mesmo tempo, um equilíbrio deve ser mantido: a operação deve gastar menos que redesenhar.
Quando cheguei à identificação no início de março, John já tinha um protótipo do mecanismo e um plano geral, por isso assumi que nosso trabalho seria simplesmente concluir e otimizar esse mecanismo. No entanto, se eu conhecesse a história do id, poderia descobrir o que era. John criou não apenas DOOM, mas também mecanismos para o Wolf 3D e vários outros jogos anteriores, e durante o processo de desenvolvimento, ele criou várias versões diferentes de cada mecanismo (uma vez que ele criou quatro mecanismos em quatro semanas), ou seja, em quatro anos ele escreveu cerca de 20 mecanismos . O desejo incansável de John por mais e mais tecnologias novas e de alta qualidade do mecanismo Quake terminará somente após o lançamento do jogo.
Três meses após minha chegada, apenas um elemento da estrutura VSD original permaneceu no mecanismo, e o desejo de John de "tentar coisas novas" foi tão longe que eu nunca tinha visto uma coisa dessas antes.
Bando de árvore
No projeto Quake original de John, a renderização foi feita da frente para trás usando uma segunda árvore do BSP que rastreia partes da tela já desenhadas e ainda vazias que precisavam ser preenchidas com os polígonos restantes. Logicamente, essa árvore do BSP pode ser considerada uma área bidimensional que descreve as partes preenchidas e vazias da tela, como mostra a Figura 4, mas, na verdade, é uma árvore tridimensional, conhecida como “árvore de vigas”. Uma árvore de vigas é um conjunto de setores 3D (cachos) delimitados por planos projetados a partir de algum ponto central (no nosso caso, o ponto de vista), como mostra a Figura 5.
Figura 4. A árvore de vigas do Quake efetivamente divide a tela em uma área 2DFigura 5. A árvore de vigas do Quake consiste em setores ou vigas 3D projetados do ponto de vista até as bordas dos polígonos.No projeto de John, uma árvore de feixe consiste inicialmente em um único feixe descrevendo a pirâmide de visibilidade; tudo fora deste pacote é considerado preenchido (ou seja, não há necessidade de desenhar nada lá) e tudo dentro do pacote é considerado vazio. Ao atingir um novo polígono percorrendo a árvore BSP do mundo de frente para trás, esse polígono foi transformado em uma viga desenhando planos de suas bordas através do ponto de vista, e todas as partes da viga que cruzavam vigas vazias na viga foram consideradas desenhadas e adicionadas à viga como uma viga cheia. Isso continuou, até os polígonos terminarem ou até a árvore de feixes ficar completamente cheia. Depois que a árvore de vigas foi concluída, as partes visíveis dos polígonos presos na árvore de vigas foram desenhadas.
A vantagem de trabalhar com uma árvore de feixes tridimensional em vez da região 2D foi que, para determinar em qual lado do plano de feixes está o vértice do polígono, basta verificar o sinal do produto vetorial do raio para o vértice e o normal para o plano, porque todos os planos de feixes passam pelo início coordenadas (ponto de vista). Além disso, como o plano do feixe é completamente descrito por uma única normal, para gerar um feixe a partir da borda do polígono, apenas o produto escalar da borda e o feixe dessa borda até o ponto de vista são suficientes. Finalmente, para o recorte de grupo pela pirâmide de visibilidade descrita acima, pode-se usar as esferas delimitadoras dos nós do BSP.
Inicialmente, a propriedade da árvore de pacote configurável (que termina quando a árvore de pacote configurável fica cheia) parecia atraente porque parecia limitar o desempenho nos piores casos. Infelizmente, ainda eram possíveis cenas nas quais era possível ver tudo até o céu ou a parede traseira do mundo; portanto, na pior das hipóteses, você ainda tinha que verificar todos os polígonos na pirâmide de visibilidade em relação à árvore.
Problemas semelhantes também podem ocorrer com pequenas rachaduras devido a limitações na precisão numérica. É gasto muito tempo cortando a árvore de feixes e, em cenas com alta visibilidade, por exemplo, quando vistas de cima, o custo total do processamento dos feixes reduziu a taxa de quadros do Quake às velocidades das tartarugas. Ou seja, no final, verificou-se que a solução com árvores de feixes sofre quase as mesmas doenças que o algoritmo do artista: o pior caso é muito pior que o caso médio e não escala bem com a crescente complexidade do nível.Novo mecanismo 3D todos os dias
Depois que a árvore de vigas começou a funcionar, John trabalhou incansavelmente para acelerar o mecanismo 3D, tentando constantemente melhorar sua estrutura, em vez de fazer alterações na implementação. Pelo menos uma vez por semana, e muitas vezes todos os dias, ele foi ao meu escritório e disse: “Ontem à noite eu não conseguia dormir, então era isso que eu pensava ...”, e eu sabia que ele estava novamente pressionando meu cérebro levemente. John tentou várias maneiras de melhorar o bun tree e obteve algum sucesso, mas muito mais interessante foi a abundância de abordagens completamente diferentes que ele gerou. Alguns deles foram pouco mencionados, enquanto outros foram implementados da noite para o dia ou em um fim de semana de intensa codificação. Nos dois casos, foram descartados ou evoluíram como resultado até começarem a atender aos critérios necessários. Aqui estão alguns exemplos de tais abordagens. Vou falar sobre eles em mínimos detalhes,esperando que eles despertem sua imaginação, assim como o buffer FIFO do Paradise despertou a imaginação de Tom Wilson.Subdivisão de radiodifusão : os raios são liberados em uma tela dividida em uma grade 8x8; essa é uma operação muito eficiente, porque a primeira interseção com a superfície pode ser encontrada simplesmente restringindo o feixe à árvore BSP, começando do ponto de vista, até que a folha cheia seja alcançada. Se os raios vizinhos não caírem na mesma superfície, um raio será emitido no meio entre eles, e isso continuará até que todos os raios vizinhos caiam em uma superfície ou em pixels vizinhos; então, um bloco é desenhado em torno de cada raio do polígono em que o raio caiu. Essa abordagem é muito bem dimensionada e é limitada pelo número de pixels, e o redesenho não ocorre. Seu problema está caindo: há uma alta probabilidade de que pequenos polígonos apareçam entre os raios e desapareçam.Superfícies sem pico: O mundo é representado como um conjunto de planos de superfície. Os polígonos aparecem indiretamente nas interseções dos planos e são removidos dos planos no último estágio antes da renderização. Isso fornece recorte rápido e uma quantidade muito pequena de dados (em comparação com polígonos, os planos são descritos de maneira muito mais compacta), mas leva muito tempo para extrair polígonos dos planos.Buffer de desenho: é semelhante ao buffer z, mas com apenas um bit por pixel, indicando se o pixel já foi desenhado. Isso elimina o redesenho, mas, ao custo de verificar o loop interno no buffer, operações adicionais de gravação e falhas de cache, e o pior de tudo, a complexidade do código aumenta significativamente. Opções para essa abordagem: verificar o buffer de renderização um byte de cada vez e ignorar completamente bytes completamente sobrepostos ou ramificar cada byte do buffer de renderização em um dos 256 loops internos implantados para renderizar de 0 a 8 pixels; nesse processo, você pode, teoricamente, tirar proveito da capacidade dos processadores x86 de executar divisão fracionária de perspectiva paralela ao processar 8 pixels.Renderização de intervalo: Os polígonos são rasterizados em intervalos, que são adicionados à lista global de intervalos e são cortados dessa lista para que somente o intervalo mais próximo permaneça em cada pixel. É necessária uma pequena classificação indo da frente para trás, porque se houver interseções, o intervalo já na lista é mais próximo. Isso elimina a necessidade de redesenho, mas à custa de intervalos aritméticos de cálculo; além disso, cada polígono ainda deve ser convertido em intervalos.Portais: são rastreados orifícios nos quais não há polígonos nas superfícies, porque a faixa de visibilidade só pode ser expandida através desses portais. A renderização é realizada de frente para trás e, quando um portal é detectado, os polígonos e portais atrás dele são limitados a seus limites até que não haja polígonos e portais visíveis. Com a aplicação recursiva desse princípio, ele permite desenhar apenas as partes visíveis dos polígonos visíveis, mas ao custo de uma quantidade significativa de recorte nos portais.Avanço
No final, John decidiu que a árvore em vigas é uma estrutura de segunda ordem que reflete as informações já indiretamente contidas na árvore BSP do mundo; portanto, ele resolveu o problema de extrair informações de visibilidade diretamente da árvore BSP do mundo. Ele passou uma semana nisso, criando uma arquitetura de visibilidade DOOM (2D) ideal na qual uma única passagem linear da árvore DOOM BSP cria visibilidade 2D redesenhada. No entanto, resolver o mesmo problema para o 3D acabou sendo um problema muito mais complicado e, no final da semana, John já estava perdendo a paciência com a crescente complexidade e as constantes falhas no código de visibilidade. Embora a solução com processamento direto do BSP já estivesse próxima da versão de trabalho, exigia cada vez mais refinamento, e a arquitetura simples e clara não era de todo. Quando saí do trabalho uma sexta-feiraJohn estava se preparando para colocar a solução de processamento BSP direto em funcionamento no fim de semana.Na segunda-feira de manhã, John parecia um homem invadindo um mundo diferente e também como um homem que não dormia muito. Durante todo o fim de semana, ele trabalhou em uma solução com processamento direto do BSP, obteve um trabalho satisfatório e também anotou como finalizá-lo. Às 3:30 da manhã de segunda-feira, quando John estava deitado na cama e pensando em portais, ele pensou que você pode pré-calcular e salvar em cada folha uma lista de todas as folhas visíveis nesta folha e depois desenhar apenas as visíveis durante a execução do programa sai de trás para frente, dependendo da folha em que o ponto de vista está, ignorando completamente todas as outras folhas.A complexidade era de tamanho: o conjunto inicialmente descompactado de conjunto potencialmente visível (PVS) ocupava vários megabytes. No entanto, o PVS pode ser armazenado como um vetor de bit com 1 bit por folha. É muito fácil compactar essa estrutura com uma compactação simples de zero bytes. John também sugeriu alterar a heurística do BSP para gerar menos folhas. Isso foi o oposto do que propus há vários meses, a saber, a escolha do próximo separador de polígonos, separando o menor número de outros polígonos e, de acordo com os dados mais recentes, ele se mostrou a melhor heurística. A abordagem de John permitiu limitar o espaço fora do nível, para que o manipulador do BSP pudesse remover superfícies externas que o jogador nunca veria,como resultado, reduzindo o tamanho do PVS para um nível suficientemente grande para 20 kilobytes.Em troca desses 20 kilobytes, o recorte de folhas fora do escopo da pirâmide de visibilidade é acelerado (porque apenas as folhas no PVS são levadas em consideração) e, para recorte dentro da pirâmide de visibilidade, você só precisa de um pequeno redesenho (o PVS da folha contém todas as folhas visíveis de qualquer lugar da folha, portanto um pequeno redesenho, geralmente da ordem de 50%, mas capaz de atingir até 150%). Melhor ainda, a pré-computação do PVS resulta em uma equalização de desempenho; o pior caso agora não é muito pior do que o melhor, porque você não precisa mais de processamento VSD adicional, apenas mais polígonos e talvez um pouco de redesenho extra no caso de cenas complexas. Quando John me mostrou seu protótipo de trabalho, lancei especialmente a cena mais difícil - o local em que a taxa de quadros diminuiu para números de um dígito e funcionou sem problemas,sem lentidão perceptível.John disse que o cálculo preliminar do PVS era um desenvolvimento lógico das abordagens que ele estava considerando, e não houve momento de "eureka". No entanto, essa foi a descoberta de um design totalmente novo e qualitativamente melhor, que, juntamente com um rasterizador com arestas de classificação que elimina completamente o redesenho, está muito próximo dos requisitos “ideais” que selecionamos desde o início.Simplifique e tente algo novo
O que isso significa?
Exatamente o que eu disse no começo: simplifique e tente algo novo. PVSs pré-computados são mais simples do que qualquer outro esquema que analisamos anteriormente (embora pré-computar PVSs seja uma tarefa interessante que discutiremos em outro momento). Em essência, PVSs pré-calculados são apenas uma versão limitada do algoritmo do artista durante a execução do programa. Isso significa que essa abordagem não é particularmente profunda?Nem um pouco.
Todas as estruturas verdadeiramente excelentes parecem simples e até óbvias, mas somente depois que são inventadas. Mas o próprio processo de invenção requer incrível perseverança e vontade de experimentar muitas idéias diferentes até encontrar a correta, como aconteceu neste caso.Meu amigo Chris Hecker tem uma teoria de que todas as abordagens se resumem a uma, porque todas elas refletem o mesmo estado e funcionalidade internos. Do ponto de vista das teorias subjacentes, isso é verdade: não importa como você calcule o mapeamento de textura em perspectiva - usando divisão ou cálculos hiperbólicos incrementais, os números executam a mesma tarefa. No entanto, quando se trata de implementação, uma enorme diferença pode ser feita com uma simples mudança da solução no tempo ou com uma melhoria na otimização dos recursos de hardware ou do cache. Meu amigo Terje Mathisen gosta de repetir que "quase toda a programação pode ser vista como exercícios de armazenamento em cache"; Foi exatamente isso que João fez. Não importa o quão rápido ele faça seus cálculos de VSD, eles nunca se tornarão tão rápidos quanto pré-computar e procurar visibilidade.Sua atitude mais inteligente foi afastar-se da mentalidade de “aceleração de código” e perceber que, de fato, é possível pré-calcular (essencialmente, armazenar em cache) o PVS e procurá-los.A coisa mais difícil do mundo é se afastar da solução usual e razoavelmente boa para um problema complexo e tentar encontrar outra solução melhor. Parece-me que, para isso, é melhor tentar novas idéias malucas e sempre, sempre tentar simplificar. Um dos objetivos de John era ter menos código em cada jogo 3D subsequente do que no anterior; ele acreditava que, se aprender mais, poderá resolver problemas com mais eficiência em uma quantidade menor de código.E enquanto esse sistema está funcionando muito bem para ele.Aprenda agora, pague antecipadamente
Há mais uma coisa que gostaria de mencionar no final do artigo. Quanto me lembro, Dr. O Dobb's Journal sempre disse que compartilhar informações de programação é uma bênção. Conheço muitos programadores que deram um salto em seu desenvolvimento graças a Tiny C Hendrix, ou D-Flat Stevens, ou simplesmente por ler o fichário anual do DDJ . (Entre eles, por exemplo, eu sou.) Muitas empresas consideram compreensivelmente a troca de informações de uma maneira completamente diferente - como uma potencial perda de lucro, e é isso que torna o DDJ tão valioso para a comunidade de programadores.Graças a essa filosofia, a id Software me permitiu contar neste artigo como o Quake funciona antes mesmo de ser lançado. E foi por isso que a id postou o código fonte completo da Wolfenstein 3D em ftp.idsoftware.com/idstuff/source [aprox. tradução: agora os códigos-fonte são definidos no github ] ; você não pode recompilar o código e vendê-lo, mas pode descobrir como um jogo de sucesso em larga escala funciona; examine o arquivo wolfsrc.txt no diretório acima para obter detalhes sobre como o código pode ser usado.Portanto, lembre-se: quando é legal, a longo prazo, a troca de informações beneficia todos nós. Você pode pagar a dívida pelas informações recebidas aqui e em outros lugares, compartilhando tudo o que pode escrevendo um artigo ou um livro ou publicando conhecimento na Web. Nenhum de nós aprende no vácuo; todos estamos nos ombros de gigantes - Wirth, Knut e milhares de outros. Substitua seus ombros para construir o futuro!Referências
Foley, James D. et al. , Computer Graphics: Principles and Practice , Addison Wesley, 1990, ISBN 0-201-12110-7 (pacotes, árvores BSP, VSD).Teller, Seth, Computações de visibilidade em ambientes poliédricos densamente ocultos (dissertação), está disponível em http://theory.lcs.mit.edu/~seth/, juntamente com outros artigos sobre a definição de visibilidade.Teller, Seth, pré-processamento de visibilidade para orientações interativas , procedimentos SIGGRAPH 91, pp. 61-69.