O particionamento do espaço binário ( particionamento do espaço binário ou BSP ) é um sistema usado para dividir o espaço em áreas convexas . Essas células são delimitadas por hiperplanos ; no caso de um espaço bidimensional (plano), as separações são linhas retas e as células são quadriláteros (geralmente retângulos ); no caso de um espaço tridimensional, as separações são planos e as células são poliedros (frequentemente paralelepípedos retangulares ).
As células são organizadas em uma árvore binária chamada árvore BSP . Essa estrutura de dados facilita certas operações. É particularmente interessante para renderização em 3D e, portanto, é usado para gerenciar os gráficos de certos videogames .
Do ponto de vista geométrico, as árvores BSP são a versão genérica das árvores planas para particionar o espaço. As árvores k -d são casos especiais de árvores BSP, nas quais os planos estão alinhados com os eixos e cujos nós contêm apenas um ponto. As árvores BSP são estruturas mais gerais nas quais os planos podem ter qualquer orientação - geralmente são planos gerados a partir de polígonos - e cujos nós podem conter qualquer tipo de objeto geométrico - em geral formas “primitivas” (formas geométricas simples: polígonos, cubos, esferas , cilindros, etc.).
O primeiro nó da árvore é o espaço, ele contém um plano que divide o espaço em dois. Seus dois nós filhos são meios-espaços, eles próprios contêm planos que dividem esses subespaços em dois. Os nós terminais da árvore não contêm mais nenhum plano e são chamados de "folhas".
O “nível de detalhe” - onde paramos na construção da árvore, o que os nós contêm - depende do campo de aplicação. Por exemplo :
A construção de uma árvore BSP pode contar com técnicas muito diferentes.
É muito simples quando você deseja apenas usá-lo como uma estrutura de armazenamento de polígono. Os motores de física geralmente usam BSPs rudimentares para armazenar geometria estática (geralmente árvores k -d ), sua construção é feita muito rapidamente.
Os mecanismos de videogame usam sistemas de construção muito mais complexos porque o BSP deve coincidir com uma estrutura do tipo setor / portal para realizar cálculos de oclusão. Para ter a estrutura mais limpa possível, as árvores geralmente não são construídas a partir de uma malha poligonal, mas usando um entrelaçamento de sólidos convexos, como fazem o id Tech e Unreal Engine . A id Tech apenas adiciona sólidos convexos, o Unreal Engine apresenta a escavação booleana para otimizar ainda mais a geometria das árvores.
Uma vez que a árvore BSP é construída, ela é convertida em uma estrutura do tipo setor / portal, uma estrutura na qual a oclusão se apoiará. No mecanismo id Tech , os portais são gerados automaticamente por um algoritmo de recorte e , em seguida, a oclusão é pré - computada em uma máscara de bits chamada de conjuntos potencialmente visíveis . No Unreal Engine , a partir da versão 2, é o processo inverso: os portais são construídos à mão pelo designer, e são adicionados à geometria da árvore BSP. A oclusão é calculada em tempo real graças aos portais.
Como esse processo de construção de mapas BSP é muito longo e caro para desenvolver, os estúdios de criação de videogame geralmente preferem usar os padrões id Tech ou Unreal .
Exemplo de construçãoConsidere um renderizador 3D no caso em que ambas as faces dos polígonos podem ser vistas. Podemos aplicar o seguinte algoritmo de construção recursiva:
Podemos assim ordenar os polígonos do mais distante para o mais próximo do ponto de vista e, portanto, saber em que ordem desenhar os polígonos para levar em conta os efeitos de mascaramento.
Mais concretamente, tomemos o exemplo de um plano (espaço bidimensional) no qual os objetos geométricos são segmentos de linha . Cada segmento possui uma orientação, portanto, possui uma “frente” e um “verso”, definidos na hora de criar o segmento.
Furos BSP e HOMsUm furo BSP, ou furo BSP , é um problema comum encontrado ao visualizar um gráfico armazenado como uma árvore BSP. Isso se manifesta por um buraco no objeto representado, que pode ser preto, ou deixar mostrar o que está por trás dele; neste caso, falamos de "palácio de gelo", ou HOM (para hall do espelho ), mas podemos ter um HOM sem que haja um buraco BSP.
Alguns buracos BSP são aleatórios: eles aparecem apenas de certos pontos de vista. Outros são permanentes: o objeto está ausente seja qual for o ponto de vista; isso geralmente é um erro de edição. Também pode haver um efeito de colisão contra obstáculo invisível (ICH, casco de colisão invisível ): o motor detecta uma colisão e evita que o jogador avance, mas nenhum objeto é exibido.
O furo BSP geralmente é encontrado quando a geometria é muito detalhada. Seu corte pode levar a uma escala muito pequena o que gera erros de aproximação dos números ( erro de arredondamento ). Para evitar esses problemas, os programas codificadores BSP destroem a geometria onde a escala se torna muito pequena, causando buracos na árvore.
Para evitar esses furos, a geometria deve ser simplificada. É por isso que as partes detalhadas de um mapa devem ser feitas com elementos que não fazem parte do BSP: quadpatch , trimesh , modelos e entidades para o motor id Tech , terrenos e malhas estáticas para o motor Unreal .
Um HOM ocorre quando o mecanismo gráfico não tem nada para exibir (o que não significa que haja uma falha no BSP); para poupar recursos, o motor apenas desenha sobre a imagem antiga e não apaga, por isso vemos os elementos da imagem dispostos um em cima do outro como quando há dois espelhos frente a frente, daí o nome “palácio de gelo”. O HOM é freqüentemente encontrado em jogos de tiro em primeira pessoa - o ponto de vista do jogador deve ser feito em uma área limitada. Mas essa suposição pode ser violada se o jogador usar um modo de “câmera virtual” (modo noclip ); a parte exibida da árvore BSP fica então incompleta e contém buracos BSP, que revelam elementos da imagem antiga.
O caminho de uma árvore BSP é linear no tempo , O ( n ). O algoritmo da rota depende do objetivo perseguido.
Localizar um ponto é a operação mais simples e é feito em um pequeno loop, sem a necessidade de uma função recursiva. Testamos em que lado do plano raiz está o ponto, então começamos novamente no filho correspondente e fazemos um loop até cair na folha que contém o ponto.
No caso de uma árvore representando polígonos a serem exibidos, o caminho da árvore pode ser usado para determinar a ordem em que os polígonos devem ser exibidos ( algoritmo do pintor ). O seguinte algoritmo de exibição recursiva é usado para isso:
Vamos aplicar este algoritmo ao exemplo anterior:
O nó é percorrido linearmente no tempo e os polígonos são exibidos em ordem do mais distante ao mais próximo (D1, B1, C1, A, D2, B2, C2, D3) conforme exigido pelo algoritmo do pintor.
Em videogames, certos objetos ou assuntos são móveis. A construção da árvore BSP deve, portanto, ser feita toda vez que a imagem for atualizada. É uma etapa pré-cálculo.
Devido à complexidade de construir árvores BSP adequadas para motores de jogo, muitas empresas não desenvolvem seu próprio formato de mapa, mas usam os motores existentes, notadamente os padrões Unreal e id Tech ( Quake ) . Por exemplo, o mecanismo Half-Life é baseado no mecanismo Quake 1 . O padrão atual é o Unreal Engine . A id Tech , além do código aberto da comunidade , tornou-se o formato padrão usado por desenvolvimentos BSP amadores ou independentes.
As várias observações abaixo são, portanto, essencialmente baseadas no estudo desses dois formatos padrão.
Estas são as principais funções das árvores BSP: otimizar os cálculos de colisão, oclusão e sombras.
O mecanismo Doom calculou a oclusão em tempo real, diretamente na rotina de exibição, recortando as faces ordenadas usando o BSP. O mecanismo Quake e seus derivados pré-calculam a oclusão em listas de grupos de folhas que podem ser vistas umas com as outras ( conjunto potencialmente visível ) . Nos motores mais modernos a oclusão é baseada em portões e anti-portões, o BSP perde sua função oclusiva, mas ainda serve como estrutura de armazenamento para o interior .
Em motores mais antigos, os cálculos de colisão eram baseados diretamente nas escovas (sólidos convexos) usadas para construir o eixo. No motor de Doom , essas escovas foram construídas pela própria árvore. Em motores mais recentes, as colisões são baseadas em um motor de física, cujo mapa de colisão pode ser completamente independente da estrutura da árvore.
As sombras projetadas foram introduzidas no Unreal Engine ou no Doom 3 . Doom 3 usa um algoritmo muito semelhante ao usado pela câmera para renderizar faces, inteiramente baseado no BSP (veja o verso de Carmack ).
O BSP tem sido usado em quase todos os jogos 3D desde Doom , Unreal , Quake e Half-Life .
O motor de Doom construiu BSPs de setores poligonais. O motor do Quake / Half-Life constrói BSPs a partir de sólidos convexos. O sistema de modelagem de árvore BSP usado pelo Unreal Engine denominado geometria sólida construtiva introduz a noção de escavação booleana : sólidos "invertidos" são usados, o que torna a construção de BSPs mais eficiente, este sistema tem a vantagem de reduzir o risco de HOM ou Furo BSP (veja acima ), erros de projeto comuns a todos os motores.
Usado pela primeira vez em duas dimensões para todos os níveis em Doom , o BSP 2d originalmente não permitia a criação de peças sobrepostas no eixo Z (eixo de altura). No entanto, essa era uma limitação inerente ao motor, o Doom Engine , que, revolucionário para a época, agora parece extremamente limitado.
É com sua variação em 3d no motor de Quake e seus sucessores Quake II ou Quake III , e seus concorrentes Unreal , ou um pouco mais tarde Half-Life que o BSP atinge seu máximo aproveitamento, as decorações são enriquecedoras graças à multiplicação de a potência dos motores, mas também a velocidade de processamento e a potência computacional dos microprocessadores , e a aparência das placas gráficas cada vez mais potentes. O BSP constituiu então a maior parte da arquitetura geral dos níveis em 3D. Foi nessa época que começaram a aparecer os atores de decorações, não compostos de BSP, mas poucos em número e de árdua criação. Os sistemas pré-fabricados permitem criar estruturas complexas, salvá-las independentemente do nível atual e reutilizá-las indefinidamente mais tarde. Esses “pré-fabricados” são então preferidos aos atores de decoração, mas sendo compostos de BSP, eles têm todas as desvantagens.
O BSP tem a desvantagem de ser adequado para arquitetura com baixa contagem de polígonos (baixo polígono) , sendo necessário adicionar elementos não BSP para detalhes.
Nos jogos recentes (por volta dos anos 2000), o BSP tende a ser acoplado, para detalhes arquitetônicos e decorações complexas, a sistemas melhor otimizados.
O exemplo mais revelador é, sem dúvida, o das malhas estáticas (en) e os terrenos do Unreal Engine , que apareceu com a segunda versão do motor em 2002, no jogo Unreal II . Esses objetos são a evolução de jogadores de decoração não-BSP que tendem a ocupar a maioria das funções anteriormente atribuídas ao BSP: objetos móveis, detalhes arquitetônicos e, cada vez mais, grandes formas gerais de quartos.
A id Tech 3 introduziu quadpatch (curvas) e malhas qualquer. Sistemas próximos aos terrenos / malha estática do Unreal , porém menos otimizados.
As razões para esta substituição são simples: as malhas estáticas (e seus equivalentes em outros motores) são insensíveis a todos os problemas ligados ao BSP: HOM, “phantoms sólidos” (em Half-Life ), etc. Eles também melhoram a velocidade dos níveis de carregamento: uma malha estática pode ser instanciada. Isso significa que o mecanismo só precisa carregar o objeto uma vez e, em seguida, duplicá-lo quantas vezes forem necessárias com as alterações apropriadas aplicadas a ele.
Por outro lado, isso não melhora a velocidade de exibição: cada objeto assim “clonado” ainda deve ser exibido individualmente. No entanto, reduzir o número de acessos aos discos rígidos ainda pode melhorar o desempenho em alguns jogos.
Os níveis externos usam muito pouco BSP e preferem estruturas mais adaptadas, como arremessos e octrees .
Como os sistemas de terreno BSP requerem grandes quantidades de BSPs fortemente deformados, causando cada vez mais problemas e erros , os geradores de terreno foram introduzidos ao mesmo tempo que as malhas estáticas , a fim de criar peças grandes com geometrias muito altas, otimizado para esses tipos de renderizações. O uso combinado de malhas estáticas e geradores de terreno cada vez mais poderosos leva à criação de níveis, por vezes, compreendendo um número irrisório de objetos BSP: no Unreal Tournament 2004 , esses sistemas permitem que você crie níveis compreendendo dois grandes cubos vazios, um contendo o terreno e o malhas estáticas , e a outra sendo uma Skybox . Jogos como Unreal e Half-Life usavam terreno BSP, que era muito angular e difícil de otimizar.
A iluminação das superfícies BSP passou por três etapas principais. Primeiro foi a iluminação simples e estática usada em Doom e Doom II: Inferno na Terra : vários níveis de iluminação definidos permitem que o nível seja iluminado quase uniformemente.
Os jogos da próxima geração permitiram atmosferas muito vivas graças à iluminação dinâmica e contrastante, como certos níveis de Unreal , Unreal Tournament , Half-Life . No Quake 3, você pode escolher entre este sistema de iluminação dinâmico ou um sistema Lightmap : texturas coloridas aplicadas por transparência à geometria do nível para simular as diferenças de luz. Este processo proíbe qualquer luz dinâmica, mas permite sombras muito precisas e marcadas. Sob UT2003 e seu sucessor direto UT2004 , os Lightmaps constituem quase toda a iluminação do BSP. Alguns sistemas de iluminação dinâmicos persistem, mas são muito caros em recursos, forçando o motor a atualizar os Lightmaps a cada momento. Além disso, as luzes não podem projetar sombras tão realistas e detalhadas quanto as luzes estáticas.
Jogos mais novos como Doom 3 são altamente otimizados e seus sistemas de iluminação, detalhados e dinâmicos, permitem que você lance sombras muito bem gerenciadas no BSP, mas também nos atores da decoração.
Geralmente, as estruturas de árvore são usadas para muitos algoritmos. Por exemplo, podemos usar uma partição binária para encontrar os vizinhos mais próximos de um ponto ou a busca por intervalo : a construção da árvore consome muitos recursos, mas seu caminho é muito mais rápido do que uma varredura sistemática de todos os pontos. A árvore k -d é interessante a esse respeito porque os algoritmos de partição tornam possível construir árvores balanceadas com poucas células vazias e uma dimensão de grande / pequena célula favorável à pesquisa.
O BSP foi usado por muito tempo em motores de videogame como as versões antigas de Quake ou Unreal, porque tinha duas vantagens: classificar os rostos no momento em que o 3D não era renderizado pela gpu e gerar automaticamente um Gráfico muito fino de células e portais que permitiu calcular uma oclusão para o polígono mais próximo.
No entanto, a estrutura do BSP tinha a desvantagem de gerar muitos bugs: "buracos", "vazamentos", "distorções", "folhas planas" e árvores mal otimizadas devido aos muitos planos quase confusos.
Nos motores 3D modernos a oclusão é feita objeto a objeto ("chunk" ou "batch"), portanto são utilizadas células mais grosseiras, que podem ser modeladas manualmente (cry engine), ou mesmo cubos gerados automaticamente (irreal 4, biblioteca umbra usada por unidade e id tech 6). Em seguida, utilizamos estruturas de armazenamento derivadas dos bsp (octrees e kd-trees, baseadas em planos ortogonais, portanto normais não aproximados) que têm a vantagem de serem estáveis e de não produzirem bugs durante sua construção.
O BSP, por outro lado, continua sendo usado como ferramenta de modelagem para acelerar a "geometria sólida construtiva", construção de sólidos complexos a partir de sólidos simples.