Primo albero
[...] these two trees can take up to 1~2 gigabytes of memory, which is
very undesirable.
Quello che mi raccomando qui sembrerà strano e stupido, ma sta giocando alle costanti più che alla scalabilità. Ho battuto alberi K-D scritti professionalmente con questo stupido approccio in C ++ per decine di milioni di vertici, ma solo per questo strano caso di trovare punti duplicati.
Per il primo albero (trovando gli indici dei vertici associati a una faccia), crea una griglia NxNxN, ad esempio 100x100x100. Ciò porterà a 1.000.000 di celle della griglia che suonano astronomiche ...
... ad eccezione di ogni cella della griglia memorizza solo un singolo indice: 4 megabyte - phew!
// Don't actually use a class here (wasteful), using it for clarity.
class GridCell
{
// Index to head node.
int head;
}
Ogni cella memorizza un puntatore (indice) su un nodo della griglia. Un nodo della griglia è simile a questo:
// Don't actually use a class here (wasteful), using it for clarity.
class GridNode
{
// Index to source vertex.
int vertex;
// Index to next node.
int next;
}
Significa un sovraccarico di 8 byte per vertice. A 10 mil vertici, che esce a 80 megabyte. Stiamo praticamente modellando un elenco collegato singolarmente per cella usando solo indici.
Quindi la tua griglia attuale ha questo aspetto:
class Grid
{
// 1,000,000 cells = 4 megabytes
// Set these initially to -1 to indicate the end of the list.
private int[][][] cells = new int[100][100][100];
// 10,000,000 vertices = 40*2 = 80 megabytes
private int[][] nodes = new int[num_verts][2];
// Can use this to try inserting a new vertex.
private int vertex_count = 0;
// Grid extents (AABB)
private float[] bmin = new float[3];
private float[] bmax = new float[3];
}
E questo è tutto, 80 megabyte per 10 mil di vertici più 4 megabyte per un milione di celle più 24 byte per il riquadro di delimitazione (più una banale quantità di memoria per i metadati di oggetti Java e possibili padding per l'allineamento). Il totale è poco più di 84 megabyte.
Ora inizia includendo un riquadro di delimitazione per tutti i vertici che hai. Non ero sicuro se avessi le posizioni dei vertici con i vertici in aggiunta, o solo i dati del viso. In entrambi i casi, esegui il ciclo di uno di questi e calcola un'estensione del riquadro di delimitazione che si adatta a tutto e inizializza la griglia.
Quindi, inizia a inserire ciascun vertice nella griglia della cella a cui appartiene. Puoi trovare l'indice della cella per una dimensione in questo modo:
int grid_cell_x(float point_x)
{
// Unit size of grid (bbox size divided by grid dimension).
float grid_unit_x = (bmax[0] - bmin[0]) / 100.0f;
// Return point position on grid (truncated to integer: floored).
return (int)((point_x - bmin[0]) / grid_unit_x);
}
... qualcosa di simile (e speriamo non duplicato per tutte le 3 dimensioni, e con alcuni valori pre-calcolati, se necessario, per evitare la divisione e roba - può eseguire la micro-sintonia se necessario).
Quando inserisci il vertice, per prima cosa cerca in questo elenco collegato singolarmente per vedere se c'è un vertice nella stessa posizione. In tal caso, salta e, eventualmente, restituisci l'indice per il vertice esistente. Se il vertice con le stesse coordinate non esiste, è possibile inserirlo nell'elenco: è sufficiente impostare l'indice successivo del nodo della griglia per il vertice all'indice della cella della griglia, quindi impostare l'indice della testina della griglia sul indice del nodo della griglia (solo inserimenti di elenchi collegati singolarmente mediante indici).
Pseudocodice:
int grid_pos[3] = grid_index(vertex.position)
for each node in cell(grid_pos), n:
if vertices[n.vertex].position == vertex.position:
return n.vertex
add new node -- get node_index
node.next = flat_index(grid_pos)
node.vertex = vertex_index
cell(grid_pos).head = node_index
Ci scusiamo, questo è un esempio davvero grossolano che lascia molto a riempire le linee. Ma spero sia sufficiente per completare il resto. In pratica, stiamo solo cercando attraverso una lista collegata singolarmente per la cella della griglia in cui un vertice atterra alla ricerca di vertici duplicati. Ottiene solo una rotatoria perché utilizziamo indici per evitare l'overhead degli oggetti e anche una dimensione a 32 bit.
E tada: hai una griglia di milioni di celle che richiede solo 84 megabyte per 10 milioni di vertici. Ho trovato che funziona meglio di octrees e k-d alberi, compresi quelli che non ho scritto io stesso. Ha impressionato talmente tanto la gente che abbiamo finito per sostituire un'implementazione di un albero k-d con questa soluzione apparentemente stupida in un software commerciale. Si adatta anche a casi limite in cui si potrebbe pensare che non lo faranno, come una mesh con densità molto irregolare (anche se potrebbe esserci un caso veramente patologico in cui queste altre strutture di indicizzazione spaziale potrebbero andare meglio, come un milione di vertici tutti quasi coincidenti con un vertice a rovescio per rovinare l'intera faccenda in cui quasi sicuramente andrebbe molto peggio).
Puoi anche regolare la dimensione della griglia e non deve essere uniforme. 100x100x100 è un buon punto di partenza, e dovrebbe essere abbastanza veloce anche per decine di milioni di vertici (cosa che spesso cerco in giro). La soluzione che utilizzo è un po 'più complessa di quella che regola il conteggio delle celle della griglia in base alla densità della mesh e alle dimensioni del riquadro di delimitazione, ma è comunque piuttosto semplice.
Soprattutto, è molto prevedibile - ricerche di hash concatenate tridimensionali a tempo costante, grande vecchio array per rendere più semplice la quantità di memoria utilizzata (e usare pochissimo anche con così tante celle).
Quindi suggerirei questo. Altrimenti, k-d tree o octree funziona abbastanza bene, ma è necessario sintonizzarli (soprattutto gli octree) e imporre limiti di profondità massimi e tali da impedirgli di utilizzare la memoria esplosiva come l'albero che si sta utilizzando attualmente.
Secondo albero
Per il secondo albero, una soluzione considerevolmente migliore è semplice. Non utilizzare affatto un albero per ordinare. Basta usare un grande array vecchio e ordinarlo e quindi eseguire un passaggio lineare controllando gli elementi successivi per facce duplicate consecutive. Una BST bilanciata è molto dispendiosa se tutto ciò che si intende usare è ordinare i dati una volta e smaltirli.
Comunque, spero che questo aiuti un po '. Ho nascosto alcuni dettagli per brevità, ma dovrebbe essere abbastanza facile da capire.