Quando utilizzare il partizionamento dello spazio binario, Quadtree, Octree?

Question

Recentemente ho appreso degli alberi di partizionamento dello spazio binario e della loro applicazione alla grafica 3D e al rilevamento delle collisioni.Ho anche esaminato brevemente il materiale relativo ai quadtree e agli ottre.Quando utilizzeresti i quadtree sugli alberi bsp o viceversa?Sono intercambiabili?Sarei soddisfatto se avessi abbastanza informazioni per compilare una tabella come questa:

            | BSP | Quadtree | Octree
------------+----------------+-------
Situation A |  X  |          |
Situation B |     |     X    |
Situation C |     |          |   X

Cosa sono A, B e C?

Answer 1

Non esiste una risposta chiara alla tua domanda.Dipende interamente da come sono organizzati i tuoi dati.

Qualcosa da tenere a mente:

I Quadtree funzionano meglio per i dati che sono per lo più bidimensionali come il rendering delle mappe nei sistemi di navigazione.In questo caso è più veloce di octree perché si adatta meglio alla geometria e mantiene piccole le strutture dei nodi.

Octrees e BVH (Bounding Volume Hierarchies) traggono vantaggio se i dati sono tridimensionali.Funziona molto bene anche se le tue entità geometriche sono raggruppate nello spazio 3D.(Vedere Octree contro BVH)

Il vantaggio di Oc- e Quadtrees è che puoi interrompere la generazione di alberi in qualsiasi momento lo desideri.Se desideri eseguire il rendering della grafica utilizzando un acceleratore grafico, puoi semplicemente generare alberi a livello di oggetto e inviare ciascun oggetto in una singola chiamata di disegno all'API grafica.Questo funziona tanto meglio che inviare singoli triangoli (qualcosa che devi fare se usi BSP-Trees al massimo).

Gli alberi BSP sono davvero un caso speciale.Funzionano molto bene in 2D e 3D, ma generare buoni alberi BSP è una forma d'arte a sé stante.Gli alberi BSP hanno lo svantaggio di dover dividere la geometria in pezzi più piccoli.Ciò può aumentare il numero complessivo di poligoni del tuo set di dati.Sono utili per il rendering, ma sono molto migliori per il rilevamento delle collisioni e il ray-tracing.

Una proprietà interessante degli alberi BSP è che decompongono una zuppa di poligoni in una struttura che può essere perfettamente renderizzata da dietro in avanti (e viceversa) da qualsiasi posizione della telecamera senza eseguire un vero e proprio ordinamento.L'ordine da ciascun punto di vista fa parte della struttura dei dati e viene eseguito durante la compilazione del BSP-Tree.

Questo, tra l'altro, è il motivo per cui erano così popolari 10 anni fa.Quake li ha utilizzati perché consentivano al motore grafico/rasterizzatore del software di non utilizzare un costoso z-buffer.

Tutti gli alberi menzionati sono solo famiglie di alberi.Ci sono octre sciolti, alberi ibridi kd-tree e molte altre strutture correlate.

Answer 2

La più grande differenza pratica tra gli alberi BSP e altri tipi di alberi 3D è che gli alberi BSP possono essere più ottimali ma funzionano solo su statico geometria.Questo perché gli alberi BSP sono generalmente molto lenti da costruire, spesso impiegando ore o giorni per un tipico livello di gioco urbano statico.

I due motivi principali per cui i BSP-Tree richiedono più tempo per essere costruiti sono (a) utilizzano piani di divisione non allineati agli assi, che richiedono più tempo per essere trovati in modo ottimale, e (b) suddividono la geometria sui confini degli assi, garantendo che nessun oggetto attraversi i piani di divisione.

Altri tipi di alberi 3D (Octrees, Quadtrees, kd-tree, Bounding-Volume-Hierarchy) utilizzano volumi di delimitazione allineati agli assi e i volumi possono (facoltativamente) sovrapporsi, quindi gli oggetti contenuti non devono essere tagliati sul volume confini.Entrambi rendono gli alberi meno ottimali degli alberi BSP, ma più veloci da costruire e più facili da modificare per gli oggetti dinamici.

Estrapolando questi fattori in situazioni...

Le aree esterne utilizzano in genere rappresentazioni del terreno basate sui campi di altezza, semplici mappe di altezza o tecniche di mappatura geo-mip più complesse come ROAM.Il terreno in sé non partecipa alla suddivisione dello spazio 3D, ma solo gli oggetti posizionati sul terreno.

Mondi con molti esempi di geometrie più semplici e simili (case, alberi, asteroidi, ecc.) useranno spesso un albero non BSP (come un BVH), perché inserire la geometria in un albero BSP significherebbe duplicare e dividere l'albero geometria di dettaglio per ogni istanza.

Al contrario, una mesh statica personalizzata di grandi dimensioni senza istanze, come una scena urbana o un ambiente interno complesso, utilizzerà in genere un BSP-Tree per migliorare le prestazioni di runtime.Il fatto che l'albero BSP divida la geometria sui confini dei nodi è utile per le prestazioni di rendering, poiché i nodi BSP possono essere utilizzati come batch di rendering di triangoli pre-organizzati.Il BSP-Tree può anche essere ottimizzato per l'occlusione, evitando la necessità di disegnare parti del BSP-Tree che sono note per trovarsi dietro ad altre geometrie.

Guarda anche: Octree contro BVH, Tutorial sulla gerarchia dei volumi delimitati, Esercitazione sull'BSP.

Answer 3

Un BSP è la soluzione migliore per gli ambienti urbani.

Un Quadtree è la soluzione migliore quando si utilizza una mappa dell'altezza per il terreno, ecc.

Un Octree è la soluzione migliore quando sono presenti grumi di geometria nello spazio 3D, come un sistema solare.

Answer 4

I BSP sono una buona opzione per accelerare il rilevamento delle collisioni, a seconda del gusto utilizzato.Sono particolarmente veloci nei test punto e linea o raggio, un po' meno veloci e un po' più complicati per cose con volume.

Per quanto riguarda il loro utilizzo nella grafica, i BSP sono praticamente obsoleti.Gli octre funzionano bene per cose come l'abbattimento della visibilità grossolana, così come gli alberi AABB.

Answer 5

Non ho molta esperienza con i BSP, ma posso dire che dovresti usare gli octree sui quadtree quando la scena che stai renderizzando è alta.Cioè, l'altezza è più della metà della larghezza e della profondità: una piccola regola pratica.In generale, gli octree non comportano costi enormi rispetto ai quadtree e hanno il potenziale per accelerare un po' le cose.YMMV.

Answer 6

Di solito queste cose non hanno una risposta chiara.Suggerirei che A, B e C siano il risultato di una funzione della dimensione del tuo spazio e della quantità di cose che stai differenziando.

Answer 7

Un BSP è migliore per uno spazio più piccolo e semplice con cui vuoi eseguire solo l'occlusione.Se desideri tutte le intersezioni per un dato raggio, dovrai passare a un quad/octree.

Per quanto riguarda quadtree vs.ottree: a quante dimensioni tieni molto?Due dimensioni significano un quadtree, quattro un otttree.Come affermato, poiché quadtree può funzionare in tre spazi, ma se si desidera che ogni dimensione riceva un trattamento adeguato, un ottree è la strada da percorrere.