KDTree Splitting

Question

Attualmente sto scrivendo un KDTree per un motore fisico (progetto Hobby).

Il KDTree non contiene punti. Invece contiene le caselle di delimitazione Alge allineate che legano i diversi oggetti nell'ambiente.

Il mio problema è decidere come suddividere i nodi KDTree quando si riempiono. Sto provando 2 metodi:

Metodo 1: dividere sempre il nodo esattamente a metà sull'asse maggiore.

• Questo ha il vantaggio di un albero abbastanza uniformemente distanziato.
• Grande svantaggio: se gli oggetti sono concentrati in una piccola area del nodo, verranno create sottodivisioni ridondanti. Questo perché tutti i volumi sono divisi esattamente a metà.

Metodo 2: trova l'area del nodo che contiene oggetti. Dividi il nodo sul piano che divide quell'area a metà del suo asse maggiore. Esempio: se tutti gli oggetti sono concentrati sul fondo del nodo, questo si divide in lunghezza, dividendo così il fondo in due.

• Questo risolve il problema con il metodo sopra
• Quando indicizzazione qualcosa che esiste sullo stesso piano (terreno per esempio), crea nodi lunghe e strette. Se devo aggiungere successivamente altri oggetti che non si trovano sullo stesso piano, questi nodi allungati forniscono indicizzazione molto scarsa.

Quindi quello che sto cercando qui è un modo migliore per dividere il mio nodo KD-Tree. Considerando che questo sarà un motore fisico, la decisione deve essere abbastanza semplice da essere eseguita in tempo reale.

Answer 1

La "superficie euristica" (SAH) è considerata il miglior metodo di divisione per la costruzione di alberi kd, almeno all'interno della comunità di raytracing. L'idea è di aggiungere il piano in modo che le aree di superficie dei due spazi figli, ponderate per il numero di oggetti in ogni bambino, siano uguali.

Un buon riferimento al tema è Ingo Wald's thesis, in particolare il capitolo 7.3, "Costruzione BSP di alta qualità", che spiega SAH meglio di me.

Al momento non riesco a trovare un buon collegamento, ma dovresti cercare documenti su SAH "a catena", che è un'approssimazione al vero SAH ma molto più veloce.

Tutto ciò detto, le gerarchie del volume di delimitazione (BVH) a.k.a. AABB alberi, sembrano essere molto più popolari di alberi kd in questi giorni. Anche in questo caso, Ingo Wald's publication page è un buon punto di partenza, probabilmente con la carta "Su costruzione veloce di gerarchie di volume di Bounding Bounding basato su SAH", anche se è passato un po 'di tempo da quando l'ho letto.

Il OMPF forums è anche un buon posto per discutere di questo genere di cose.

Spero che questo aiuti. In bocca al lupo!

Answer 2

Certamente per un motore fisico in cui la premessa è molto geometrica, una bvh è probabilmente la scelta migliore, non si attraversano abbastanza velocemente ma sono molto più veloci da costruire e sono molto più facili da rimontare/ristrutturare su un frame per frame, e offen non hanno bisogno di una ricostruzione completa, ogni frame (qualcosa che può essere fatto in parallelo su una serie di frame mentre il refl bvh è sufficiente nel frattempo, ancora una volta, si riferisce a wald).

Un'eccezione a questo in fisica potrebbe essere quando si ha a che fare con entità che non hanno volume come particelle o fotoni, la costruzione dell'albero kd è semplificata dal fatto che non è necessario risolvere i limiti del singolo primitivo. Dipende davvero dall'applicazione. Un buon motore di fisica dovrebbe utilizzare una combinazione bilanciata di strutture di accelerazione spaziale, è pratica comune risolvere un partizionamento di fase più ampio con un ocra superficiale quindi estendere i nodi foglia con un altro schema che si adatta meglio alla natura di ciò che si sta facendo, i BSP sono ideali per la geometria statica, specialmente in 2D e quando la struttura non cambia, la cosa migliore da fare è sperimentare tanti schemi e strutture differenti e avere un'idea di come e quando funzionano meglio.