Partizione binaria dello spazio

Il partizionamento dello spazio binario ( partizionamento dello spazio binario o BSP ) è un sistema utilizzato per dividere lo spazio in aree convesse . Queste celle sono delimitate da iperpiani  ; nel caso di uno spazio bidimensionale (piano), le separazioni sono linee rette e le celle sono quadrilateri (spesso rettangoli ); nel caso di uno spazio tridimensionale, le separazioni sono piani e le celle sono poliedri (spesso parallelepipedi rettangolari ).

Le celle sono disposte in un albero binario chiamato albero BSP . Questa struttura di dati facilita alcune operazioni. È particolarmente interessante per il rendering 3d e viene quindi utilizzato per la gestione della grafica di alcuni videogiochi .

Storico

• 1969 Schumacker et al. pubblicare un rapporto che descriva come i piani accuratamente posizionati in un ambiente virtuale possono accelerare l'ordinamento dei poligoni . La tecnica utilizza la profondità di coerenza, una nozione che un poligono situato nel semipiano più lontano dallo spettatore non può mascherare un poligono situato nel semipiano più vicino. Questa nozione è utilizzata dai simulatori di volo sviluppati da General Electric e Evans & Sutherland . Tuttavia, la creazione della gerarchia dei poligoni viene eseguita manualmente dallo scenografo.

• 1975 Bentley della Stanford University propone la struttura di k -d alberi per la ricerca multidimensionale.

• 1980 Fuchs et al. estendere l'idea di alla rappresentazione di oggetti 3D virtuali, utilizzando i piani dei poligoni e partizionando lo spazio in modo ricorsivo. Creano così un algoritmo completamente automatizzato per la creazione di una struttura dati gerarchica per i poligoni, chiamato Binary Space Partitioning Tree (BSP Tree) . Questo processo avviene in una fase di pre-calcolo, prima della consegna all'utente finale. Durante l'esecuzione in tempo reale, l'ordinamento dei poligoni per determinare la visibilità viene effettuato attraversando l'albero.

• 1981 La tesi di dottorato di Naylor combina alberi BSP e teoria dei grafi per determinare la visibilità precalcolata. Sottolinea l'uso degli alberi BSP come struttura di ricerca indipendente dalla dimensione dello spazio, con applicazioni sulla visibilità delle superfici. Utilizzando il modello dello space shuttle , la tesi dimostra empiricamente che la dimensione dell'albero e il numero di nuovi poligoni creati sono ragionevoli.

• 1983 Fuchs et al. descrivere un codice albero BSP minimo su un sistema frame buffer Ikonas. Questa è la prima implementazione della determinazione della visibilità della superficie in tempo reale utilizzando alberi BSP.

• 1987 Thibault e Naylor descrivono come rappresentare i poliedri usando alberi BSP, in contrasto con il consueto metodo B-Rep (rappresentazione del confine) . Abbiamo una rappresentazione di solidi in contrapposizione a una rappresentazione di superfici (i confini dei solidi). Gli strumenti offerti per i poliedri consentono il rendering di solidi descritti da Constructive Solid Geometry (CSG) in tempo reale. È il precursore del metodo di progettazione dei livelli BSP che utilizza i pennelli , introdotto nell'editor Quake e riutilizzato nell'editor Unreal .

• 1990 Naylor, Amanatides e Thibault forniscono un algoritmo per unire due alberi BSP in uno. Ciò consente in particolare: di combinare oggetti in movimento, rappresentati da alberi BSP, con un ambiente statico rappresentato anch'esso da un albero BSP; eseguire operazioni booleane tra poliedri (CSG) in modo veloce; calcoli di collisione esatta in O (log n × log n )  ; e per ordinare correttamente le superfici trasparenti contenute negli oggetti compenetranti (utilizzato per effetto di visione a raggi X).

• 1990 Teller e Séquin propongono di determinare gli elementi potenzialmente visibili prima della consegna del software, per accelerare la determinazione delle superfici visibili in ambienti ortogonali 2D.

• 1991 Gordon e Chen descrivono un metodo efficiente per eseguire il rendering fronte-retro da un albero BSP, invece del solito approccio fronte-retro. Usano una struttura dati dedicata per registrare, in modo potente, le parti dello schermo che sono già state disegnate e quelle che non sono state ancora disegnate. Questo algoritmo è stato utilizzato da John Carmack per creare il videogioco Doom .

• 1992 La tesi di dottorato di Teller descrive un metodo efficiente per determinare insiemi potenzialmente visibili, in una fase di pre-elaborazione, che consente di accelerare la determinazione delle superfici visibili in tempo reale in un ambiente 3D formato da poligoni. Questo metodo è stato utilizzato in Quake e ha contribuito in modo significativo alle prestazioni del gioco.

• 1993 Naylor determina cosa caratterizza un albero BPS "buono". Misura matematicamente il costo della ricerca di un albero e lo applica alla costruzione di alberi "buoni", in base a casi probabili piuttosto che a un'analisi del caso peggiore. Intuitivamente, gli alberi giusti rappresentano oggetti a diversi livelli di risoluzione (albero delle approssimazioni). Questo metodo ha somiglianze con la codifica di Huffman e gli alberi di ricerca di permutazioni casuali .

• 1993 La tesi di dottorato di Hayder Radha descrive un metodo di rappresentazione (naturale) dell'immagine utilizzando alberi BSP. Ciò include lo sviluppo di una struttura di costruzione ad albero BSP ottimale per un'immagine arbitraria. Questa struttura si basa su una nuova trasformazione dell'immagine, la trasformazione mediante una linea di partizione ottenuta mediante regressione dei minimi quadrati (trasformata della linea di partizione dell'errore minimo quadrato) . La tesi di Radha sviluppa anche una struttura di compressione delle immagini con un tasso di distorsione ottimale e un approccio di manipolazione delle immagini utilizzando alberi BSP.

Definizione

Descrizione

Da un punto di vista geometrico, gli alberi BSP sono la versione generica dei platani per il partizionamento dello spazio. Gli alberi k -d sono casi speciali di alberi BSP, in cui i piani sono allineati con gli assi e i cui nodi contengono un solo punto. Gli alberi BSP sono strutture più generali in cui i piani possono avere qualsiasi orientamento - sono generalmente piani generati da poligoni - e i cui nodi possono contenere qualsiasi tipo di oggetto geometrico - in generale forme “primitive” (forme geometriche semplici: poligoni, cubi, sfere , cilindri, ecc.).

Il primo nodo dell'albero è lo spazio, contiene un piano che divide lo spazio in due. I suoi due nodi figli sono semispazi, essi stessi contengono piani che dividono questi sottospazi in due. I nodi terminali dell'albero non contengono più piani e sono chiamati "foglie".

Il “livello di dettaglio” - dove ci fermiamo nella costruzione dell'albero, cosa contengono i nodi - dipende dal campo di applicazione. Per esempio :

• per le immagini sintetiche con rendering 3d, i nodi contengono un insieme di poligoni che possono essere disegnati in un ordine arbitrario,
  • se ci sono selezioni back-face , un nodo contiene un insieme di poligoni convessi,
  • se si possono vedere entrambe le facce di un poligono (a seconda del punto di vista), un nodo contiene solo poligoni complanari;
• nel calcolo delle collisioni o nel ray tracing , un nodo contiene una porzione di spazio in cui i test di intercettazione sono diretti.

Costruzione

La costruzione di un albero BSP può contare su tecniche molto diverse.

È molto semplice quando si desidera utilizzarlo solo come struttura di archiviazione poligonale. I motori di fisica spesso utilizzano BSP rudimentali per memorizzare la geometria statica (di solito k -d alberi ), la loro costruzione viene eseguita molto rapidamente.

I motori dei videogiochi utilizzano sistemi di costruzione molto più complessi perché il BSP deve coincidere con una struttura di tipo settore/portale per eseguire calcoli di occlusione. Per avere la struttura più pulita possibile, gli alberi sono solitamente costruiti non da una mesh poligonale, ma utilizzando un incastro di solidi convessi, come fanno id Tech e Unreal Engine . L' id Tech si limita ad aggiungere solidi convessi, l' Unreal Engine introduce lo scavo booleano per ottimizzare ulteriormente la geometria degli alberi.

Una volta costruito l'albero BSP, viene convertito in una struttura di tipo settore/portale, una struttura su cui poggerà l'occlusione. Nel motore id Tech , i portali vengono generati automaticamente da un algoritmo di clipping , quindi l'occlusione viene precalcolata in maschere di bit chiamate insiemi potenzialmente visibili . In Unreal Engine , dalla versione 2, avviene il processo inverso: i portali vengono costruiti a mano dal progettista, e vengono aggiunti alla geometria dell'albero BSP. L'occlusione viene calcolata in tempo reale grazie ai portali.

Poiché questo processo di creazione di mappe BSP è molto lungo e costoso da sviluppare, gli studi di creazione di videogiochi generalmente preferiscono utilizzare gli standard id Tech o Unreal .

Esempio di costruzione

Considera un renderer 3D nel caso in cui sia probabile che entrambe le facce dei poligoni siano visibili. Possiamo applicare il seguente algoritmo di costruzione ricorsivo:

1. Scegli un poligono P dall'elenco.
2. Crea un nodo N nell'albero BSP e inserisci P nell'elenco dei poligoni di questo nodo.
3. Per ogni poligono nell'elenco:
   1. Se questo poligono è interamente davanti al piano contenente P, posizionalo nell'elenco dei poligoni davanti a P.
   2. Se questo poligono è interamente dietro il piano contenente P, posizionalo nell'elenco dei poligoni dietro P.
   3. Se il piano contenente P è secante con il poligono, dividere il poligono in due per il piano di P e posizionare ciascuno dei mezzi poligoni nell'elenco appropriato (davanti a P, dietro P).
   4. Se il poligono è complanare con P, aggiungilo all'elenco dei poligoni per il nodo N.
4. Applica questo algoritmo alla lista dei poligoni davanti a P.
5. Applicare questo algoritmo all'elenco dei poligoni dietro P.

Possiamo così ordinare i poligoni dal più lontano al più vicino al punto di vista, e quindi sapere in quale ordine disegnare i poligoni per tenere conto degli effetti di mascheramento.

Più concretamente, prendiamo l'esempio di un piano (spazio bidimensionale) in cui gli oggetti geometrici sono segmenti di linea . Ogni segmento ha un orientamento, quindi ha un "lato anteriore" e un "lato posteriore", definiti durante la creazione del segmento.

	Lo spazio contiene quattro segmenti di linea {A, B, C, D}; se fosse un problema di rendering 3D, sarebbero poligoni che formano una "scena". Nell'albero, i nodi dell'albero sono in cerchi e gli elenchi di oggetti davanti o dietro sono in rettangoli arrotondati. Il lato anteriore di ogni segmento è indicato da una freccia
io.	Applichiamo l'algoritmo presentato sopra: Scegliamo arbitrariamente un segmento, qui la A. Creiamo il nodo radice contenente A. I segmenti intersecanti con la linea che porta A vengono tagliati; quindi abbiamo nuovi segmenti, {B1, B2, C1, C2, D1, D2}. Alcuni si trovano davanti ad A, {B2, C2, D2} e altri si trovano dietro, {B1, C1, D1}. Elaboriamo, in modo ricorsivo, prima i segmenti posti davanti ad A (stadi ii – v), poi quelli posti dietro (stadi vi – vii).
ii.	Consideriamo i segmenti posti davanti ad A, {B2, C2, D2}. Creiamo un nodo figlio, scegliamo un segmento arbitrario, B2, e lo aggiungiamo a questo nodo. Tagliamo il segmento secante con la linea portante B2, che crea due nuovi segmenti, {D2, D3}. Separiamo i segmenti situati davanti a B2, {D2} e quelli situati dietro, {C2, D3}.
ii.	Consideriamo i segmenti situati davanti a B2. C'è un solo segmento, D2, quindi creiamo un nodo figlio di B2 che lo contiene, è una foglia dell'albero.
IV.	Consideriamo ora i segmenti dietro B2, {C2, D3}. Scegliamo arbitrariamente un segmento, C2, e lo aggiungiamo al nodo figlio di B2 che creiamo. L'elenco dei segmenti davanti a C2 è {D3}, l'elenco dei segmenti dietro è vuoto.
v.	Consideriamo l'elenco dei segmenti davanti a C2. L'unico segmento che contiene, D3, viene aggiunto al nodo figlio di C2 che creiamo.
vi.	Abbiamo elaborato tutti i segmenti posti davanti ad A; ora abbiamo a che fare con coloro che ci stanno dietro. Scegliamo un segmento arbitrario, B1, che inseriamo nel nodo figlio di A che creiamo. Separiamo i segmenti in due elenchi: i segmenti situati davanti a B1, {D1} e quelli situati dietro, {C1}.
vii.	Elaboriamo i segmenti situati davanti a B1. C'è solo un segmento, D1, quindi creiamo un nodo figlio di B1 per metterlo lì.
viii.	Elaboriamo i segmenti dietro B1. C'è solo un segmento, C1, quindi creiamo un nodo figlio di B1 per metterlo lì. L'albero BSP è completo.

Fori BSP e HOM

Un buco BSP, o buco BSP , è un problema comune riscontrato durante la visualizzazione di un grafico memorizzato come albero BSP. Questo si manifesta con un foro nell'oggetto rappresentato, che può essere nero, o far vedere cosa c'è dietro; in questo caso si parla di "palazzo di ghiaccio", o HOM (per sala dello specchio ), ma possiamo avere un HOM senza che ci sia un buco BSP.

Alcuni buchi BSP sono casuali: compaiono solo da certi punti di vista. Altri sono permanenti: l'oggetto è assente qualunque sia il punto di vista; questo di solito è un errore di modifica. Potrebbe esserci anche un effetto di collisione contro un ostacolo invisibile (ICH, invisibile collisione scafo ): il motore rileva una collisione e impedisce al giocatore di avanzare, ma non viene visualizzato alcun oggetto.

Il foro BSP si incontra solitamente quando la geometria è troppo dettagliata. Il suo taglio può portare a una scala troppo piccola che genera errori relativi all'approssimazione dei numeri ( errore di arrotondamento ). Per evitare questi problemi, i programmi di codifica BSP distruggono la geometria dove la scala diventa troppo piccola, causando buchi nell'albero.

Per evitare questi fori, la geometria deve essere semplificata. Ecco perché le parti dettagliate di una mappa devono essere realizzate con elementi che non fanno parte del BSP: quadpatch , trimesh , modelli ed entità per il motore id Tech , terreni e mesh statiche per l' Unreal Engine .

Un HOM si verifica quando il motore grafico non ha nulla da visualizzare (il che non significa che ci sia un buco BSP); per risparmiare risorse, il motore disegna semplicemente sulla vecchia immagine e non la cancella, quindi vediamo gli elementi dell'immagine visualizzati uno sopra l'altro come quando ci sono due specchi uno di fronte all'altro, da cui il nome "palazzo di ghiaccio". HOM si incontra spesso negli  sparatutto in prima persona : il punto di vista del giocatore è pensato per essere in un'area limitata. Ma questo presupposto può essere violato se il giocatore utilizza una modalità "fotocamera virtuale" (modalità noclip ); la porzione visualizzata dell'albero BSP è quindi incompleta e contiene buchi BSP, che rivelano elementi della vecchia immagine.

Percorso

Il percorso di un albero BSP è lineare nel tempo , O ( n ). L'algoritmo del percorso dipende dall'obiettivo perseguito.

L'individuazione di un punto è l'operazione più semplice e viene eseguita in un piccolo ciclo, senza la necessità di una funzione ricorsiva. Testiamo su quale lato del piano radice è il punto, quindi ricominciamo dal figlio corrispondente e eseguiamo un ciclo finché non cadiamo nel foglio che contiene il punto.

Nel caso di un albero che rappresenta i poligoni da visualizzare, il percorso dell'albero può essere utilizzato per determinare l'ordine in cui devono essere visualizzati i poligoni ( algoritmo del pittore ). A tale scopo viene utilizzato il seguente algoritmo di visualizzazione ricorsivo:

1. Se il nodo corrente è una foglia, visualizza i poligoni contenuti nel nodo corrente.
2. Altrimenti, se il punto di vista V è davanti al nodo corrente:
   1. Visualizza il ramo figlio contenente i poligoni situati dietro il nodo corrente.
   2. Visualizza i poligoni contenuti nel nodo corrente.
   3. Visualizza il ramo figlio contenente i poligoni che si trova davanti al nodo corrente.
3. Altrimenti, se il punto di vista V è dietro il nodo corrente:
   1. Visualizza il ramo figlio contenente i poligoni che si trova davanti al nodo corrente.
   2. Visualizza i poligoni contenuti nel nodo corrente.
   3. Visualizza il ramo figlio contenente i poligoni situati dietro il nodo corrente.
4. Altrimenti il ​​punto di vista V è esattamente nel piano associato al nodo corrente. Pertanto :
   1. Visualizza il ramo figlio contenente i poligoni che si trova davanti al nodo corrente.
   2. Visualizza il ramo figlio contenente i poligoni situati dietro il nodo corrente.

Applichiamo questo algoritmo all'esempio precedente:

• Partiamo dalla radice, il nodo A. V è davanti al nodo (il fronte è indicato dalla freccia), quindi applichiamo l'algoritmo in modo ricorsivo ai nodi posti dietro, cioè il ramo B1.
  • Il nodo corrente è B1. V è dietro B1, quindi applichiamo l'algoritmo in modo ricorsivo ai nodi che si trovano davanti, cioè il ramo D1.
    • Il nodo corrente è D1. È una foglia, quindi visualizziamo D1 .
  • Quindi visualizziamo B1 .
  • Quindi applichiamo l'algoritmo in modo ricorsivo ai nodi situati dietro B1, cioè il ramo C1.
    • Il nodo corrente è C1. È una foglia, quindi visualizziamo C1 .
• Quindi visualizza A .
• Quindi applichiamo l'algoritmo in modo ricorsivo ai nodi posti davanti ad A, cioè al ramo B2.
  • Il nodo corrente è B2. V è dietro B2, quindi applichiamo l'algoritmo in modo ricorsivo ai nodi che si trovano davanti, cioè il ramo D2.
    • Il nodo corrente è D2. È una foglia, quindi visualizziamo D2 .
  • Quindi visualizziamo B2 .
  • Quindi applichiamo l'algoritmo in modo ricorsivo ai nodi situati dietro B2, cioè il ramo C2.
    • Il nodo corrente è C2. V è davanti a C2, quindi applichiamo l'algoritmo in modo ricorsivo ai nodi dietro di esso.
      • Non c'è nessun nodo.
    • Quindi visualizziamo C2 .
    • Quindi l'algoritmo viene applicato ricorsivamente ai nodi posti davanti a C2, cioè il ramo D3.
      • Il nodo corrente è D3. È una foglia, quindi visualizziamo D3 .

Il nodo viene percorso linearmente nel tempo e i poligoni vengono visualizzati in ordine dal più lontano al più vicino (D1, B1, C1, A, D2, B2, C2, D3) come richiesto dall'algoritmo del pittore.

Utilizzare nei videogiochi

Nei videogiochi, alcuni oggetti o soggetti sono mobili. La costruzione dell'albero BSP deve quindi essere eseguita ogni volta che l'immagine viene aggiornata. È un passaggio precalcolatore.

A causa della complessità della creazione di alberi BSP adatti ai motori di gioco, molte aziende non sviluppano il proprio formato di mappa ma utilizzano motori esistenti, in particolare gli standard Unreal e id Tech ( Quake ) . Ad esempio, il motore Half-Life è basato sul motore Quake 1 . Lo standard attuale è l' Unreal Engine . L' id Tech , oltre la community open source , è diventato il formato standard utilizzato dagli sviluppi BSP amatoriali o indipendenti.

Le varie osservazioni che seguono si basano quindi essenzialmente sullo studio di questi due formati standard.

Occlusione / collisioni / proiezioni di ombre

Queste sono le funzioni principali degli alberi BSP: ottimizzare i calcoli di collisione, occlusione e ombre.

Il motore di Doom ha calcolato l'occlusione in tempo reale, direttamente nella routine di visualizzazione, ritagliando le facce ordinate utilizzando il BSP. Il motore di Quake ei suoi derivati ​​precalcolano l'occlusione in elenchi di gruppi di fogli che possono essere visti tra loro ( insieme potenzialmente visibile ) . Nei motori più moderni l'occlusione è basata su gate e anti-gate, il BSP perde la sua funzione occlusiva ma funge comunque da struttura di stoccaggio per gli interni .

Nei motori più vecchi, i calcoli delle collisioni si basavano direttamente sulle spazzole (solidi convessi) utilizzate per costruire l'albero. Nel motore di Doom , questi pennelli sono stati costruiti dall'albero stesso. Nei motori più recenti, le collisioni si basano su un motore fisico, la cui mappa delle collisioni può essere completamente indipendente dalla struttura dell'albero.

Le ombre proiettate sono state introdotte in Unreal Engine o Doom 3 . Doom 3 utilizza un algoritmo molto simile a quello utilizzato dalla telecamera per renderizzare i volti, interamente basato sul BSP (vedi Carmack's Reverse ).

Evoluzione matematica nei videogiochi classici

BSP è stato utilizzato in quasi tutti i giochi 3D da Doom , Unreal , Quake e Half-Life .

Il motore di Doom costruiva BSP da settori poligonali. Il motore di Quake / Half-Life costruisce BSP da solidi convessi. Il sistema di modellazione ad albero BSP utilizzato dall'Unreal Engine chiamato geometria solida costruttiva introduce la nozione di scavo booleano  : vengono utilizzati solidi "invertiti", che rendono più efficiente la costruzione di BSP, questo sistema ha il vantaggio di ridurre il rischio di HOM o Foro BSP (vedi sopra ), errori di progettazione comuni a tutti i motori.

Evoluzione visiva

Utilizzato per la prima volta in due dimensioni per tutti i livelli sotto Doom , il BSP 2d originariamente non permetteva di creare pezzi sovrapposti sull'asse Z (asse dell'altezza). Tuttavia, questo era un limite intrinseco del motore, il Doom Engine , che, rivoluzionario per l'epoca, ora sembra estremamente limitato.

È con la sua variazione in 3d nel motore di Quake e dei suoi successori Quake II o Quake III , e dei suoi concorrenti Unreal , o poco dopo Half-Life che il BSP raggiunge il suo massimo utilizzo, le decorazioni si arricchiscono grazie alla moltiplicazione di la potenza dei motori ma anche della velocità di elaborazione e della potenza di calcolo dei microprocessori , e la comparsa di schede grafiche sempre più potenti. Il BSP ha quindi costituito la parte più ampia dell'architettura complessiva dei livelli in 3D. Fu in questo periodo che cominciarono ad apparire gli attori delle decorazioni, non formati da BSP, ma pochi di numero e di ardua creazione. I sistemi prefabbricati consentono di creare strutture complesse, di salvarle indipendentemente dal livello attuale e di riutilizzarle in seguito all'infinito. Questi “Prefabbricati” sono poi preferiti agli attori delle decorazioni, ma essendo costituiti da BSP, hanno tutti gli svantaggi.

Combinazione di BSP con strutture di visualizzazione dettagliate

Il BSP ha lo svantaggio di essere adatto per architetture con basso numero di poligoni (basso poligono) , è necessario aggiungere elementi non BSP per i dettagli.

Nei giochi recenti (dagli anni 2000 circa), il BSP tende ad essere accoppiato, per dettagli architettonici e decorazioni complesse, a sistemi meglio ottimizzati.

L'esempio più eloquente è senza dubbio quello delle mesh statiche  (en) e dei terreni dell'Unreal Engine , apparso con la seconda versione del motore nel 2002, nel gioco Unreal II . Questi oggetti sono l'evoluzione dei giocatori di decorazione non BSP che tendono ad occupare la maggior parte delle funzioni precedentemente assegnate al BSP: oggetti mobili, dettagli architettonici e, sempre più, grandi forme generali di stanze.

L' id Tech 3 ha introdotto quadpatch (curve) e mesh qualsiasi. Sistemi vicini ai terreni/ staticmesh di Unreal , tuttavia meno ottimizzati.

I motivi di questa sostituzione sono semplici: le mesh statiche (e i loro equivalenti sotto altri motori) sono insensibili a tutti i problemi legati al BSP: HOM, "fantasmi solidi" (sotto Half-Life ), ecc. Migliorano anche la velocità dei livelli di carico: è possibile istanziare una mesh statica . Ciò significa che il motore deve caricare l'oggetto solo una volta e quindi duplicarlo tutte le volte necessarie con le modifiche appropriate applicate.

Ciò, d'altro canto, non migliora la velocità di visualizzazione: ogni oggetto così “clonato” deve comunque essere visualizzato singolarmente. Tuttavia, la riduzione del numero di accessi ai dischi rigidi può comunque migliorare le prestazioni su alcuni giochi.

I livelli esterni

I livelli esterni utilizzano pochissimo BSP e preferiscono strutture più adattate come piazzole e octree .

Poiché i sistemi di terreno BSP richiedono grandi quantità di BSP fortemente deformati causando sempre più problemi ed errori , i generatori di terreno sono stati introdotti contemporaneamente alle mesh statiche , al fine di creare parti di grandi dimensioni con geometrie molto elevate ottimizzate per questi tipi di rendering. L'uso combinato di mesh statiche e generatori di terreno sempre più potenti porta alla creazione di livelli comprendenti a volte un numero irrisorio di oggetti BSP: in Unreal Tournament 2004 , questi sistemi consentono di creare livelli composti da due grandi cubi vuoti, uno contenente il terreno e l'altro mesh statiche e l'altro è uno Skybox . Giochi come Unreal e Half-Life utilizzavano il terreno BSP, che era molto spigoloso e difficile da ottimizzare.

Illuminazione di superficie

L'illuminazione delle superfici BSP ha attraversato tre fasi principali. La prima è stata la semplice illuminazione statica utilizzata in Doom e Doom II: Hell on Earth  : diversi livelli di illuminazione definiti consentono di illuminare il livello in modo quasi uniforme.

I giochi di nuova generazione consentivano atmosfere molto vivaci grazie a luci dinamiche e contrastanti come certi livelli di Unreal , Unreal Tournament , Half-Life . In Quake 3, puoi scegliere tra questo sistema di illuminazione dinamico o un sistema Lightmap  : trame colorate applicate per trasparenza alla geometria del livello per simulare le differenze di luce. Questo processo vieta qualsiasi luce dinamica, ma consente ombre molto precise e marcate. Sotto UT2003 e il suo diretto successore UT2004 , le Lightmap costituiscono quasi tutta l'illuminazione del BSP. Alcuni sistemi di illuminazione dinamica persistono, ma sono molto costosi in termini di risorse, costringendo il motore ad aggiornare le Lightmap in ogni momento. Inoltre, le luci non possono proiettare ombre realistiche e dettagliate come le luci statiche.

I giochi più recenti come Doom 3 sono altamente ottimizzati e i loro sistemi di illuminazione, sia dettagliati che dinamici, ti consentono di proiettare ombre molto ben gestite sul BSP, ma anche sugli attori della decorazione.

Altre applicazioni

In genere, le strutture ad albero vengono utilizzate per molti algoritmi. Ad esempio, possiamo utilizzare una partizione binaria per trovare i vicini più prossimi di un punto o la ricerca per intervallo  : la costruzione dell'albero richiede molte risorse, ma il suo percorso è molto più veloce di una scansione sistematica di tutti i punti. L' albero k -d è interessante in questo senso perché gli algoritmi di partizione consentono di costruire alberi approssimativamente bilanciati con poche celle vuote e una dimensione grande/piccola della cella favorevole alla ricerca.

Abbandono del BSP nelle moderne pipeline grafiche

Il BSP è stato utilizzato per molto tempo nei motori dei videogiochi come le vecchie versioni di Quake o Unreal, perché aveva due vantaggi: ordinare i volti nel momento in cui il 3d non veniva renderizzato dalla gpu e generare automaticamente un Grafico molto fine di celle e portali che ha permesso di calcolare un'occlusione al poligono più vicino.

Tuttavia, la struttura BSP aveva lo svantaggio di generare molti bug: "buchi", "perdite", "distorsioni", "foglie piatte", e alberi mal ottimizzati a causa dei molti piani quasi confusi.

Nei moderni motori 3d l'occlusione avviene oggetto per oggetto ("chunk" o "batch"), quindi vengono utilizzate celle più grossolane, che possono essere modellate manualmente (cry engine), o addirittura cubi generati automaticamente (unreal 4 , libreria umbra usata da unità e id tech 6). Utilizziamo quindi strutture di memorizzazione derivate dal bsp (octree e kd-tree, basate su piani ortogonali, quindi normali non approssimate) che hanno il vantaggio di essere stabili e di non produrre bug durante la loro costruzione. .

Il BSP, invece, rimane utilizzato come strumento di modellazione per accelerare la "geometria solida costruttiva", costruzione di solidi complessi da solidi semplici.

Note e riferimenti

1. (in) Robert A. Schumacker , Brigitta Brand , Maurice G. Gilliland e Werner H. Sharp , Studio per l'applicazione di immagini generate al computer alla simulazione visiva , Laboratorio delle risorse umane dell'aeronautica statunitense,1969, 142  pag..
2. (in) Jon Louis Bentley , "  Alberi di ricerca binaria multidimensionali utilizzati per la ricerca associativa  " , Comunicazioni dell'ACM , vol.  18, n °  9,1975, pag.  509-517 ( DOI  10.1145 / 361002.361007 ).
3. (en) Henry Fuchs , Zvi M. Kedem e Bruce F Naylor , "  On Visible Surface Generation by A Priori Tree Structures  " , SIGGRAPH '80 Atti della 7a conferenza annuale sulla computer grafica e le tecniche interattive , New York, ACM,1980, pag.  124–133 ( DOI  10.1145/965105.807481 ).
4. (in) William C. Thibault e Bruce F. Naylor , "  Le operazioni sugli insiemi sono poliedri che utilizzano alberi di partizione dello spazio binario  " , SIGGRAPH '87 Atti della 14a conferenza annuale sulla computer grafica e la tecnologia interattiva , New York, ACM,1987, pag.  153–162 ( DOI  10.1145 / 37402.37421 ).
5. (in) S. Chen e D. Gordon , "Visualizzazione  fronte-retro di alberi BSP  " , IEEE Computer Graphics & Algorithms ,settembre 1991, pag.  79–85 ( leggi online [PDF] ).
6. vedi ad esempio l'uso di un albero k -d per questo scopo: (en) “  Re: Pairwise distance of a huge number of points  ” , su utenti Scilab - Archivio Mailing Lists , 29 agosto 2014, 16:38
7. in particolare con il metodo di partizione del punto medio scorrevole

Articoli Correlati

• Algoritmo del pittore
• Octree
• Quadtree
• File mappa compilato per Valve Hammer Editor ( Half-Life , Counter-Strike ...) o Doom e Quake .