Partizionamento binario dello spazio: Esplorazione del partizionamento binario dello spazio: fondamenti e applicazioni nella visione artificiale

Di Fouad Sabry

Che cos'è il partizionamento binario dello spazio

In informatica, il partizionamento binario dello spazio (BSP) è un metodo per il partizionamento dello spazio che suddivide ricorsivamente uno spazio euclideo in due insiemi convessi utilizzando iperpiani come partizioni. Questo processo di suddivisione dà origine a una rappresentazione degli oggetti all'interno dello spazio sotto forma di una struttura di dati ad albero nota come albero BSP.

Come trarrai vantaggio

(I) Approfondimenti e convalide sui seguenti argomenti:

Capitolo 1: Partizionamento dello spazio binario

Capitolo 2: Albero binario

Capitolo 3: Rendering (computer grafica)

Capitolo 4: Rendering scanline

Capitolo 5: Determinazione della superficie nascosta

Capitolo 6: Quadtree

Capitolo 7: Octree

Capitolo 8: Partizionamento dello spazio

Capitolo 9: Albero K-d

Capitolo 10: Ritaglio (computer grafica)

( II) Rispondere alle principali domande del pubblico sul partizionamento dello spazio binario.

(III) Esempi reali dell'utilizzo del partizionamento dello spazio binario in molti campi.

Chi è questo libro per

Professionisti, studenti universitari e laureati, appassionati, hobbisti e coloro che desiderano andare oltre le conoscenze o le informazioni di base per qualsiasi tipo di partizionamento dello spazio binario.

 

 

• Lingua: Italiano
• Editore: Un Miliardo Di Ben Informato [Italian]
• Data di uscita: 4 mag 2024

Anteprima del libro

Capitolo 1: Partizionamento dello spazio binario

Il partizionamento dello spazio binario (BSP) è un metodo per il partizionamento dello spazio in informatica che suddivide ricorsivamente uno spazio euclideo in due insiemi convessi usando iperpiani come partizioni. Questa procedura genera una rappresentazione degli oggetti all'interno dello spazio sotto forma di albero BSP, una struttura dati simile a un albero.

Il 1969 vide lo sviluppo del partizionamento binario dello spazio nel contesto della computer grafica 3D. Il rilevamento di collisioni nella robotica e nei videogiochi 3D, il ray tracing e altre applicazioni che comportano la manipolazione di situazioni spaziali complicate.

Il processo generico di separazione ricorsiva di una scena in due fino a quando il partizionamento non soddisfa uno o più requisiti è noto come partizionamento dello spazio binario. Può essere visto come una generalizzazione di altre strutture ad albero spaziali, come gli alberi k-d e i quadtree, in cui gli iperpiani che partizionano lo spazio non sono allineati con gli assi delle coordinate. Nella computer grafica, quando si esegue il rendering di scenari costituiti da poligoni planari, i piani di divisione vengono comunemente scelti in modo da coincidere con i piani definiti dai poligoni nella scena.

La selezione precisa del piano di partizionamento e i criteri per l'arresto del processo di partizionamento variano in base all'uso previsto dell'albero BSP. Nel rendering in computer grafica, ad esempio, la scena viene suddivisa fino a quando ogni nodo dell'albero BSP include solo poligoni che possono essere disegnati in qualsiasi sequenza. Quando viene utilizzato l'eliminazione della faccia posteriore, ogni nodo ha un insieme convesso di poligoni, tuttavia quando si esegue il rendering di poligoni a doppia faccia, ogni nodo dell'albero BSP contiene solo poligoni basati su piani. Nel rilevamento delle collisioni o nel ray tracing, una scena può essere partizionata in primitive per le quali i test di collisione o intersezione dei raggi sono semplici.

La computer grafica richiedeva il partizionamento dello spazio binario per renderizzare rapidamente scene tridimensionali fatte di poligoni. L'algoritmo del pittore produce poligoni in ordine di distanza dall'osservatore, da dietro a davanti, dipingendo sullo sfondo e poligoni precedenti con ogni oggetto che è più vicino allo spettatore. Questo metodo presenta due inconvenienti: il tempo necessario per ordinare i poligoni in ordine inverso e la probabilità di errori nei poligoni che si sovrappongono. Fuchs e co-autori hanno dimostrato che la costruzione di un albero BSP ha risolto entrambi questi problemi fornendo un metodo rapido di ordinamento dei poligoni rispetto a un dato punto di vista (lineare nel numero di poligoni nella scena) e suddividendo i poligoni sovrapposti per prevenire gli errori relativi all'algoritmo di Painter. Uno svantaggio del partizionamento dello spazio binario è il tempo necessario per generare un albero BSP. Prima del rendering o di altre operazioni in tempo reale su una scena, viene quindi in genere eseguita una sola volta sulla geometria statica come fase di pre-calcolo. Lo spostamento di oggetti direttamente in un albero è impegnativo e inefficiente a causa del costo di creazione di un albero BSP.

Gli alberi BSP sono spesso utilizzati nei videogiochi 3D, in particolare negli sparatutto in prima persona e nei titoli con ambientazioni interne. Doom (id Tech 1), Quake (variante id Tech 2), GoldSrc e Source sono motori di gioco che utilizzano alberi BSP. In essi, gli alberi BSP che contengono la geometria statica della scena sono spesso utilizzati in combinazione con un buffer Z per fondere correttamente elementi mobili come porte e personaggi nella scena di sfondo. Mentre il partizionamento dello spazio binario facilita l'archiviazione e il recupero di informazioni spaziali sui poligoni di una scena, non risolve il problema della determinazione della superficie visibile.

L'applicazione standard di un albero BSP è quella di eseguire il rendering di poligoni a doppia faccia senza l'eliminazione della faccia posteriore utilizzando il metodo del pittore. Ogni poligono ha un lato anteriore e un lato posteriore che possono essere scelti liberamente e hanno un impatto solo sulla struttura dell'albero, non sul risultato desiderato.

Selezionare un poligono dall'elenco P.

Aggiungere P all'elenco dei poligoni in corrispondenza del nodo N nell'albero BSP.

Per ogni poligono aggiuntivo nell'elenco:

Se il poligono si trova interamente davanti al piano che contiene P, aggiungilo all'elenco dei nodi davanti a P.

Se questo poligono si trova completamente dietro il piano che contiene P, aggiungilo all'elenco dei nodi dietro P.

Se il poligono è attraversato dal piano contenente P, dividilo in due poligoni e aggiungili rispettivamente alle liste di poligoni dietro e davanti a P.

Aggiungi questo poligono all'elenco dei poligoni nel nodo N se giace nel piano contenente P.

Applicare questa procedura all'elenco di poligoni che precede P.

Applicando questo metodo all'elenco dei poligoni dietro P.

Questo diagramma illustra come questo approccio può essere utilizzato per trasformare un elenco di linee o poligoni in un albero BSP. A ciascuno degli otto passaggi (i.-viii), il metodo precedente viene applicato all'elenco di righe e viene aggiunto un nuovo nodo all'albero.

Poiché le linee o i poligoni che attraversano il piano di partizione devono essere divisi in due, il numero finale di poligoni o linee in un albero è spesso maggiore (e talvolta considerevolmente maggiore) rispetto all'elenco iniziale. È preferibile limitare questa crescita preservando un giusto equilibrio nell'albero finale. La decisione di quale poligono o linea utilizzare come piano di partizionamento (nel passaggio 1 del metodo) è fondamentale per la creazione efficace di un albero BSP.

Un albero BSP viene attraversato in tempo lineare, in un ordine dato dalla funzione specifica dell'albero. Per creare in modo appropriato il poligono P, usando l'esempio del rendering di poligoni a doppia faccia usando la tecnica del pittore, tutti i poligoni dietro il piano in cui si trova P devono essere disegnati per primi, seguiti dal poligono P e infine dai poligoni davanti a P. Se tutti i poligoni di una scena rispettano questo ordine di disegno, il rendering della scena verrà eseguito nell'ordine corretto. Utilizzando l'algoritmo seguente, questa procedura può essere implementata attraversando in modo iterativo un albero BSP. Da un dato punto di vista V, eseguire il rendering di un albero BSP, se il nodo corrente è un nodo foglia, disegnare i poligoni del nodo corrente.

Se il sito di visualizzazione V si trova di fronte al nodo corrente, l'algoritmo continua:

Eseguire il rendering dell'albero BSP figlio contenente poligoni dietro il nodo corrente.

Eseguire il rendering dei poligoni che si trovano nel nodo corrente

Eseguire il rendering dell'albero BSP figlio contenente poligoni davanti al nodo corrente.

Se la posizione di visualizzazione V si trova dietro il nodo attuale:

Eseguire il rendering dell'albero BSP figlio contenente poligoni davanti al nodo corrente.

Eseguire il rendering dei poligoni che si trovano nel nodo corrente

Eseguire il rendering dell'albero BSP figlio contenente poligoni dietro il nodo corrente.

In caso contrario, la posizione di visualizzazione V deve trovarsi esattamente sul piano collegato con il nodo corrente. Allora:

Eseguire il rendering dell'albero BSP figlio contenente poligoni davanti al nodo corrente.

Eseguire il rendering dell'albero BSP figlio contenente poligoni dietro il nodo corrente.

Le seguenti