Inside Quake: sempre considere alternativas

O programador Michael Abrash, convidado por John Carmack para trabalhar no motor do primeiro terremoto em meados dos anos 90, escreveu uma série de artigos durante o processo de desenvolvimento. Esta é a segunda coluna desta série. A tradução do primeiro está aqui .

Devo admitir: cansei do rock clássico. A última vez que fiquei feliz em ouvir algo de Cars ou Boston por um longo tempo, cerca de 20 anos atrás. Além disso, nunca fui particularmente atraído por Bob Seager e Queen, sem mencionar Elvis, tão pouco mudou. Mas percebi que algo mudou quando eu queria mudar o rádio quando ouvi Allman Brothers, Steely Dan, Pink Floyd ou, Deus, me perdoe, os Beatles (mas apenas em coisas como "Olá, adeus" e "Vou Em vez disso, chore, não ingresso para passeio ou Um dia na vida; ainda não cheguei tão longe). Não demorou muito tempo para encontrar as razões para isso; Ouvi as mesmas músicas por um quarto de século e me cansei delas.

Conto tudo dessa maneira porque, quando minha filha e eu saímos do café uma noite, a estação de rádio “Não há alternativa” foi ligada pela primeira vez no carro.

Estamos falando de uma menina de dez anos que cresceu com uma dieta constante de sucessos antigos. Ela gosta de melodias, músicas cativantes e bons cantores. Você não encontrará nada disso ao ouvir uma estação de rock alternativa. Portanto, não é de surpreender que, quando liguei o rádio, ela primeiro disse: "Fu!"

Mas eis o que me surpreendeu: depois de ouvir um pouco, ela disse: "Sabe pai, mas isso é realmente interessante".

Isso não apenas sugeriu para mim sobre que tipo de música ressoaria por toda a casa quando ela se tornasse adolescente. Sua rápida adoção do rock alternativo (em comparação com o meu fascínio pela música de minha própria juventude com duração de dez anos) me lembrou algo que é facilmente esquecido quando você envelhece e o estilo de vida se estabelece. Isso me lembrou que era necessário manter a mente aberta e estar preparado - além disso, esforçar-se - para tentar coisas novas. Os programadores tendem a se apegar a abordagens familiares e tendem a usá-las se lidarem adequadamente com as tarefas. Mas sempre existem alternativas à programação, e acho que elas valem a pena ser exploradas com frequência.

Mas, dada a natureza sempre mutável do Quake , eu realmente não deveria precisar de um lembrete assim.

Fluxo do criativo

Em janeiro, descrevi um fluxo criativo que levou John Carmack a decidir usar polígonos pré-computados de conjunto potencialmente visível (PVS) para todos os pontos de vista possíveis no Quake (um jogo que estamos desenvolvendo em conjunto na id Software). O cálculo preliminar do PVS significa que, em vez de gastar muito tempo pesquisando no banco de dados de polígonos visíveis do ponto de vista atual no banco de dados mundial, podemos simplesmente desenhar todos os polígonos no PVS de volta para frente (pegando a ordem da árvore BSP do mundo; discussão sobre BSP- veja árvores em nossas colunas em maio, julho e novembro de 1995) e obtenha a cena renderizada corretamente completamente sem pesquisar, permitindo que a renderização reversa complete a última etapa da remoção da superfície oculta (HSR). Foi uma ideia incrível, mas para a arquitetura do Quake o caminho ainda não foi concluído.

Desenhando objetos em movimento

Por exemplo, ainda há uma pergunta sobre como classificar e desenhar corretamente objetos em movimento; de fato, essa pergunta após a coluna de janeiro foi feita acima de tudo, portanto, darei tempo a ela. O principal problema é que um modelo em movimento pode cair em várias folhas do BSP e, quando o modelo se move, essas folhas mudam; juntamente com a possibilidade de encontrar vários modelos em uma folha, isso significa que não há uma maneira fácil de usar a ordem BSP para desenhar modelos em uma ordem classificada corretamente. Quando escrevi a coluna de janeiro, desenhamos sprites (como explosões), modelos móveis de BSP (como portas) e modelos poligonais (como monstros), truncando cada um deles com as folhas que tocavam e desenhando as partes correspondentes quando cada folha de BSP atingia sua vez de dar a volta de trás para frente. No entanto, isso não resolveu o problema de classificar vários modelos móveis em uma folha em relação uma à outra e também deixou problemas desagradáveis ​​com modelos poligonais complexos.

John resolveu o problema de classificação de modelos de sprites e polígonos de uma maneira surpreendentemente baixa em tecnologia: agora os escrevemos no buffer z. (Ou seja, antes de desenhar cada pixel, comparamos a distância a ele, ou z, com o valor z do pixel que já está na tela. Um novo pixel é desenhado apenas se estiver mais próximo do que o existente.) Primeiro, desenhamos o mundo principal - paredes, tetos e assim por diante. assim. Nesse estágio, nenhum teste do z-buffer é usado (como veremos em breve, a definição das superfícies visíveis do mundo é realizada de outra maneira); no entanto, preenchemos o buffer z com valores z (na verdade, valores 1 / z, conforme descrito abaixo) para todos os pixels do mundo. Preencher um buffer Z é um processo muito mais rápido do que o buffer z seria o mundo inteiro, porque não há leitura, comparação ou apenas valor z. Depois de concluir o desenho e preencher o buffer z do mundo, podemos simplesmente desenhar sprites e modelos poligonais usando o buffer z e obter a classificação perfeita.

Ao usar o buffer z, surgem inevitavelmente perguntas: como isso afeta a memória e o desempenho ocupados? Com uma resolução de 320x200, requer 128 KB de memória, o que não é trivial, mas não tanto para um jogo que requer 8 MB para funcionar. Impacto no desempenho: cerca de 10% ao preencher o buffer z do mundo e cerca de 20% (os indicadores variam bastante) ao renderizar sprites e modelos poligonais. Em troca, temos um mundo perfeitamente classificado, bem como a capacidade de criar efeitos adicionais, por exemplo, explosões e fumaça de partículas, porque o buffer z permite que você classifique esses efeitos facilmente no mundo. Em geral, o uso do z-buffer aumentou significativamente a qualidade visual e a flexibilidade do mecanismo Quake, além de simplificar significativamente o código, ao custo de custos e desempenho razoáveis ​​da memória.

Nivelamento e aumento da produtividade

Como eu disse acima, a arquitetura do Quake primeiro desenha o mundo em si, sem ler ou comparar o buffer z, apenas preenchendo o buffer z com os valores dos polígonos do mundo em z. Depois disso, objetos em movimento são desenhados no topo do mundo usando o z-buffer completo. Até agora, só falei sobre como desenhar objetos em movimento. No restante da coluna, falarei sobre outra parte da equação de renderização - desenhar o próprio mundo, quando o mundo inteiro é armazenado como uma árvore BSP e nunca se move.

Como você pode se lembrar da coluna de janeiro, estávamos preocupados com o desempenho bruto e sua média. Ou seja, queríamos que o código de renderização fosse executado o mais rápido possível, mas ao mesmo tempo, para que a diferença entre a velocidade de renderização da cena intermediária e a mais lenta na renderização da cena fosse a menor possível. Não há nada de bom na média de 30 quadros por segundo, se 10% das cenas forem desenhadas a 5 qps, porque o movimento dessas cenas será extremamente perceptível em comparação com a cena média. É melhor calcular a frequência com 15 quadros por segundo em 100% dos casos, mesmo que a velocidade média de renderização seja metade da mesma.

PVSs pré-calculados foram um passo importante em direção a um desempenho mais alto e mais equilibrado, porque eliminaram a necessidade de determinar polígonos visíveis - um estágio bastante lento que se manifestou pior nas cenas mais complexas. No entanto, em alguns locais com níveis reais de jogo, os PVS pré-computados contêm cinco vezes mais polígonos do que realmente é visto; em conjunto com a remoção da superfície oculta para trás (HSR), isso criou “zonas quentes” nas quais a taxa de quadros foi notavelmente reduzida. Centenas de polígonos foram atraídos de volta para a frente e a maioria deles foi imediatamente redesenhada por polígonos mais próximos. O desempenho bruto como um todo também diminuiu em média 50% do redesenho causado pela renderização de tudo no PVS. Portanto, embora a renderização de conjuntos PVS reversos funcionasse como o último estágio do HSR e fosse uma melhoria em relação à arquitetura anterior, não era o ideal. John achou que provavelmente havia uma maneira melhor de usar o PVS do que desenhar da frente para trás.

E ele realmente foi encontrado.

Intervalos classificados

O último estágio ideal do HSR para o Quake foi descartar todos os polígonos no PVS que realmente eram invisíveis e desenhar apenas os pixels visíveis dos polígonos restantes sem redesenhar. Ou seja, cada pixel seria desenhado exatamente uma vez e sem perda de desempenho, é claro. Uma solução (exigindo, no entanto, custos) é desenhar da frente para trás, salvar a área que descreve as partes atualmente sobrepostas da tela e truncar cada polígono com as bordas dessa área antes da renderização. Parece promissor, mas na verdade é uma reminiscência da solução de árvore de pacotes configuráveis ​​que descrevi na coluna de janeiro. Como descobrimos, essa abordagem requer um desperdício de recursos extras e tem sérios problemas com o balanceamento de carga.

Você pode fazer muito melhor se mover a última etapa do HSR do nível do polígono para o nível do intervalo e usar a solução com intervalos classificados. Em essência, essa abordagem consiste em transformar cada polígono em um conjunto de intervalos, como mostrado na Figura 1, seguido por classificar e truncar os intervalos entre si até que apenas partes visíveis dos intervalos visíveis permaneçam para renderização, como mostra a Figura 2. Isso pode parecer muito semelhante ao z-buffer (que, como eu disse acima, é muito lento para ser usado na renderização do mundo, embora seja adequado para objetos em movimento menores), mas existem diferenças importantes. Ao contrário do buffer z, apenas as partes visíveis dos intervalos visíveis são digitalizadas pixel por pixel (embora todas as arestas dos polígonos ainda precisem ser rasterizadas). Melhor ainda, a classificação realizada pelo buffer z para cada pixel se torna uma operação de intervalo com intervalos classificados e, como uma propriedade integral da lista de intervalos é conectividade, cada borda é classificada apenas em relação a alguns intervalos na mesma linha e é truncada apenas por alguns intervalos quando sobreposição horizontal. Embora cenas complexas ainda demorem mais para serem processadas do que cenas simples, os piores casos não eram tão ruins quanto ao usar árvores com vigas ou ao classificar de trás para frente, porque não há redesenho e varredura de pixels ocultos, a complexidade é limitada pela resolução de pixels e a conectividade por intervalo limita a classificação dos piores casos em qualquer área da tela. Como bônus, a saída dos intervalos classificados está exatamente na forma que um rasterizador de baixo nível precisa: no formato de um conjunto de descritores de intervalo, cada um dos quais consiste em uma coordenada do início e do comprimento.



Geração de intervalo

Em suma, a solução com intervalos ordenados está muito próxima dos nossos critérios originais; embora não economize custos, eles ainda não são totalmente terríveis. Elimina completamente o redesenho e a digitalização de pixels das partes sobrepostas dos polígonos e é propenso a igualar o desempenho nos piores casos. Não confiaríamos apenas em intervalos classificados como um mecanismo para eliminar superfícies ocultas, mas o PVS pré-calculado reduz o número de polígonos a um nível que os intervalos classificados lidam bem o suficiente.

Então, encontramos a abordagem de que precisamos; resta apenas escrever o código e isso acabou, certo? Sim e não A abordagem conceitual com intervalos ordenados é simples, mas surpreendentemente difícil de implementar: você precisa tomar algumas decisões importantes no projeto, é preciso um pouco de matemática e existem armadilhas astutas. Vamos examinar primeiro as soluções de design.

Costelas vs. Intervalos

A primeira decisão é escolher o que classificar: intervalos ou arestas (ambos os conceitos pertencem à categoria geral de "intervalos classificados"). Embora os resultados em ambos os casos sejam os mesmos (uma lista de intervalos que precisam ser desenhados sem redesenhar), as implementações e implicações de desempenho são muito diferentes, pois a classificação e o truncamento são executados por estruturas de dados muito diferentes.

Ao classificar intervalos, esses intervalos são armazenados em segmentos de memória classificados por x listas vinculadas, geralmente um segmento por linha raster. Cada polígono, por sua vez, é rasterizado em intervalos, conforme mostrado na Figura 1. Cada intervalo é classificado e truncado no segmento de memória da linha raster na qual o intervalo está localizado, conforme mostrado na Figura 2, para que, a qualquer momento, cada segmento contenha os intervalos mais próximos encontrados. , sempre sem sobreposições. Com essa abordagem, é necessário gerar todos os intervalos para cada polígono por vez, e cada intervalo é imediatamente classificado, truncado e adicionado ao segmento de memória correspondente.



Figura 2: os intervalos do polígono A da Figura 1 são classificados e truncados em intervalos do polígono B, enquanto o polígono A está a uma distância constante de 100 ao longo do eixo Z, e o polígono B está a uma distância constante de 50 ao longo do eixo Z (o polígono B está mais próximo da câmera )

Ao classificar arestas, essas arestas são armazenadas em segmentos de memória classificados por x listas vinculadas de acordo com sua linha de varredura inicial. Cada polígono, por sua vez, é dividido em arestas, criando juntos uma lista de todas as arestas da cena. Quando todas as arestas de todos os polígonos na pirâmide de visibilidade são adicionadas à lista de arestas, a lista inteira é digitalizada em uma passagem de cima para baixo, da esquerda para a direita. Uma lista da lista de arestas ativas (AEL) é salva. Em cada etapa de uma nova linha raster, as arestas que aparecem nessa linha raster são removidas da AEL, as arestas ativas vão para suas novas coordenadas x, as arestas iniciadas na nova linha raster são adicionadas à AEL e as arestas são classificadas pela coordenada x atual.

Para cada linha de varredura, uma lista de polígonos ativos (APL) classificada por z é armazenada. Ele vai na ordem classificada por x AEL. Ao reunir-se com cada nova aresta (ou seja, quando cada polígono inicia ou termina ao mover da esquerda para a direita), o polígono associado a ele é ativado e classificado na APL (no caso de uma aresta inicial), como mostra a Figura 3, ou desativado e excluído da APL ( no caso de uma aresta à direita), como mostrado na Figura 4. Se o polígono mais próximo mudou (ou seja, o mais próximo é um novo polígono ou o polígono mais próximo terminou), para o polígono que deixou de ser o mais próximo, é criado um intervalo a partir do ponto em que o polígono não está vym porque é o mais próximo e terminando coordenada x das bordas atuais e os atuais coordenada x é gravado no aterro, que agora é o mais próximo. Essa coordenada armazenada é usada mais tarde como o início do intervalo criado quando o novo polígono mais próximo deixa de estar na frente.



Figura 3: ativação do polígono quando uma aresta inicial é detectada no AEL.



Figura 4: desativação de polígono quando uma borda posterior é detectada no AEL.

Não se preocupe se você não entender completamente o que foi dito acima; Esta é apenas uma rápida visão geral das arestas de classificação, para que o restante da coluna fique mais claro. Uma explicação detalhada estará na próxima coluna.

Os intervalos gerados pela classificação das arestas parecem ser exatamente os mesmos que resultariam da classificação dos intervalos; a diferença está nas estruturas de dados intermediárias usadas para classificar os intervalos na cena. Ao classificar arestas, os intervalos são armazenados dentro das arestas até que o conjunto final de intervalos visíveis seja gerado; portanto, os intervalos de classificação, corte e criação são executados quando cada aresta adiciona ou remove um polígono, com base no estado do intervalo definido pela aresta e no conjunto de polígonos ativos. Ao classificar os intervalos, os intervalos instantaneamente se tornam aparentes quando cada polígono é rasterizado, e esses intervalos intermediários são classificados e truncados em relação aos intervalos na linha raster para criar os intervalos finais; portanto, os estados dos intervalos são constantemente definidos explicitamente e todo o trabalho é executado diretamente em intervalos.

A classificação por intervalos e a classificação por arestas funcionam bem; elas foram usadas com sucesso em projetos comerciais. Para o Quake, escolhemos a classificação de arestas, em parte porque parece ser mais eficiente e possui excelente conectividade horizontal que fornece o tempo mínimo de classificação, em contraste com a classificação potencialmente cara em listas vinculadas, que pode ser necessária ao classificar intervalos.No entanto, um motivo mais importante foi que, ao classificar as arestas, podemos dividir as arestas entre polígonos adjacentes, o que reduz a classificação, o corte e a rasterização de arestas pela metade, além de reduzir significativamente o banco de dados mundial devido ao fato de as arestas se tornarem comuns.

E a última vantagem da classificação de arestas é que ela não distingue entre polígonos convexos e côncavos. Para a maioria dos mecanismos gráficos, esse não é um aspecto muito importante, mas no Quake, aparar, transformar, projetar e classificar arestas se tornou o principal gargalo, por isso estamos fazendo todo o possível para reduzir o número de polígonos e arestas, e os polígonos côncavos são muito úteis nesse sentido. Embora polígonos côncavos também possam ser processados ​​por intervalos de classificação, isso implica uma diminuição significativa no desempenho.

No entanto, não há resposta definitiva sobre a melhor abordagem. No final, os intervalos de classificação e as arestas de classificação desempenham uma função, e escolher entre eles é uma questão de usabilidade. Na próxima coluna, falarei mais sobre a classificação de arestas com sua implementação completa. No restante desta coluna, estabelecerei as bases para a próxima, falando sobre as chaves de classificação e o cálculo de 1 / z. No processo, farei várias referências aos aspectos das arestas de classificação, que ainda não foram discutidas em detalhes; Peço desculpas, mas isso é inevitável, e tudo ficará claro apenas no final da próxima coluna.

Teclas de classificação de nervuras

Agora que sabemos que vamos selecionar a classificação das arestas e usá-la para criar os intervalos dos polígonos mais próximos do espectador, surge a pergunta: como você sabe se esses polígonos são os mais próximos? Idealmente, simplesmente armazenaríamos a chave de classificação de cada polígono e, quando uma nova aresta aparecer, compararíamos a chave de sua superfície com as chaves de outros polígonos ativos atuais, a fim de determinar facilmente qual dos polígonos está mais próximo.

Parece bom demais, mas é possível. Se, por exemplo, seu banco de dados mundial estiver armazenado como uma árvore do BSP e todos os polígonos forem truncados nas folhas do BSP, a ordem de passagem do BSP será a ordem de renderização correta. Portanto, por exemplo, se você percorre o BSP da frente para trás, atribuindo a cada polígono um valor de chave incrementalmente maior quando o atinge, os polígonos com valores de chave mais altos garantem que estão na frente dos polígonos com chaves menores. Essa abordagem foi usada no Quake há algum tempo, mas agora uma solução diferente está sendo aplicada por razões que explicarei em breve.

Se você não possui um BSP ou uma estrutura de dados semelhante, ou se possui muitos polígonos móveis (o BSP não processa polígonos móveis com muita eficiência), outra maneira de alcançar objetivos é classificar todos os polígonos entre si antes de renderizar a cena e atribuir as chaves correspondentes de acordo com seu espaço. relacionamentos na janela de visualização. Infelizmente, no caso geral, essa é uma tarefa extremamente lenta, porque cada polígono precisa ser comparado. Existem técnicas para melhorar o desempenho dos polígonos de classificação, mas não conheço ninguém que faça a classificação geral de polígonos em um PC em tempo real.

Uma alternativa é classificar pela distância z do visualizador no espaço da tela; Essa solução se encaixa bem com a conectividade espacial superior das arestas de classificação. Ao encontrar cada nova aresta na linha de varredura, é possível calcular a distância z do polígono correspondente e comparar com as distâncias de outros polígonos, após as quais o polígono pode ser salvo na APL.

No entanto, obter distâncias ao longo de z pode ser uma tarefa difícil. Não se esqueça de que precisamos calcular z em qualquer ponto arbitrário do polígono, pois pode ocorrer uma aresta e fazer com que o polígono seja classificado na APL em qualquer lugar da tela. Podemos calcular z diretamente das coordenadas da tela x e y e das equações do plano do polígono, mas, infelizmente, isso não pode ser feito muito rapidamente, porque z para o plano não muda linearmente no espaço da tela; no entanto, 1 / z varia linearmente, por isso usamos esse valor. (Para uma discussão sobre linearidade no espaço da tela e gradientes para 1 / z, consulte a série de Chris Hecker sobre mapeamento de texturas na revista Game Developer no ano passado.) Outra vantagem do uso de 1 / z é que a resolução aumenta com a distância decrescente, ou seja, com 1 / z sempre teremos a melhor resolução de profundidade para objetos próximos mais importantes.

Uma maneira óbvia de obter o valor de 1 / z em qualquer ponto arbitrário do polígono é calcular 1 / z nos vértices, interpolar-los sobre as duas arestas do polígono e interpolar-se entre as arestas para obter o valor no ponto desejado. Infelizmente, isso exige muito trabalho a ser feito ao longo de cada costela; pior, isso requer divisão para calcular a etapa de 1 / z por pixel em cada intervalo.

Seria melhor calcular 1 / z diretamente da equação do plano e da tela x e y do pixel de seu interesse. A equação tem a seguinte forma:

$$

$$1/z = (a/d)x' - (b/d)y' + c/d$$

onde z é a coordenada no espaço z do ponto no plano que é projetado nas coordenadas da tela (x ', y') (a origem das coordenadas para esses cálculos é o centro da projeção, o ponto na tela bem em frente ao ponto de vista), [abc] é normal ao plano na viewport ed é a distância da origem da viewport ao plano ao longo da normal. A divisão é realizada apenas uma vez para cada plano, porque a, b, c e d são constantes para os planos.

Um cálculo 1 / z completo requer duas multiplicações e duas adições, e cada operação deve ser executada com um ponto flutuante para evitar erros de intervalo. Esse volume de cálculos de ponto flutuante parece caro, mas na verdade não é, especialmente nos processadores Pentium, onde o valor do plano 1 / z em qualquer ponto pode ser calculado na linguagem assembly em apenas seis ciclos.

Se você estiver interessado, aqui está uma derivação rápida da equação 1 / z. A equação do plano para o plano tem a seguinte forma:

$$

$$ax + by + cz - d = 0$$

onde x e y são as coordenadas do espaço da vista, a, b, c, d e z são definidos acima. Se fizermos a substituição$$$x=x'z$ e $$$y=-y'z$(a partir da definição de projeção em perspectiva; y muda de sinal porque aumenta na janela de exibição, mas no espaço da tela). Realizando uma permutação, obtemos:

$$

$$z = d / (ax' - by' + c)$$

Invertendo e expandindo a equação, obtemos:

$$

$$1/z = ax'/d - by'/d + c/d$$

Mais tarde mostrarei a classificação 1 / z em ação.

Quake e classificar por z

Mencionei acima que o Quake não usa mais a ordem BSP como uma chave de classificação; de fato, 1 / z agora é aplicado como a chave. Apesar da elegância dos gradientes, calcular 1 / z deles é obviamente mais lento do que apenas comparar com a chave de ordem do BSP, então por que passamos a usar 1 / z no Quake?

O principal motivo é a diminuição do número de polígonos. Para renderizar em ordem BSP, é necessário seguir certas regras, incluindo polígonos quando a interseção com planos BSP deve ser dividida. Essa separação aumenta significativamente o número de polígonos e arestas. Graças à classificação por 1 / z, podemos deixar os polígonos não divididos, mas ainda assim obter a ordem de desenho correta, portanto, precisamos processar muito menos arestas; enquanto a renderização geralmente é acelerada, apesar do custo adicional da classificação em 1 / z.

Outra vantagem da classificação 1 / z é que ela resolve os problemas de classificação mencionados no início deste artigo: modelos em movimento, que são árvores de BSP pequenas. A classificação na ordem mundial do BSP não funcionará aqui, porque esses modelos são BSPs separados e não há maneiras fáceis de incorporá-los na ordem seqüencial do mundo do BSP. Não queremos usar o buffer z para esses modelos, porque geralmente são objetos grandes (por exemplo, portas) e não queremos perder os benefícios de reduzir o redesenho que as portas fechadas fornecem ao renderizar na lista de arestas. Ao usar intervalos classificados, as arestas dos modelos de BSP em movimento são simplesmente colocadas na lista de arestas (primeiro truncando os polígonos para que não se cruzem com superfícies sólidas do mundo para evitar complexidade,relacionados à penetração mútua) em vez de todas as extremidades do mundo, e o restante é classificado por 1 / z.

Seguindo em frente

O artigo, sem dúvida, apresenta uma enorme quantidade de informações e muita coisa ainda não foi colocada na sua cabeça. O código e a explicação do próximo artigo ajudarão; se você quiser dar uma olhada com antecedência, quando ler este artigo, o código deverá estar disponível em ftp.idsoftware.com/mikeab/ddjsort.zip. Também vale a pena dar uma olhada em Foley e Van Dam, da Computer Graphics , ou em Elementos processuais para Rogers, da Computer Graphics .

Não está claro no momento como o resultado do Quakedeve classificar as arestas - na ordem BSP ou 1 / z. De fato, não há garantia de que intervalos classificados de qualquer forma sejam a solução final. Às vezes parece que mudamos os mecanismos gráficos com a mesma frequência que colocam Elvis nas estações de rádio dedicadas aos hits dos anos 50 (mas, esperançosamente, com resultados muito mais esteticamente agradáveis!), E sem dúvida consideraremos alternativas até a data de lançamento os jogos.