Come gestire i voxel 3D in modo efficiente?

Question

Ho una nuvola di punti 3D con milioni di punti. Voglio memorizzare questi punti nello spazio voxel 3D. Il numero di voxle lungo l'asse delle coordinate è superiore a 3000 (x), 4000 (y), 1500 (z), per un totale di 3000 * 4000 * 1500 voxel. Ho bisogno di conservare in un voxel; numero massimo di punti, altezza minima, altezza massima e centorid. Tuttavia, il 90% dei voxel è vuoto. Quindi ci vuole molta memoria per memorizzare questo. In realtà, voglio cercare 26 voxel vicini di ciascun voxel in seguito. Quindi qual è il modo migliore per archiviare questi dati nello spazio voxel e ottenere l'accesso a questo in modo efficiente?

Creare un array multidimensionale, non è la soluzione migliore, in termini di prestazioni ... per favore qualche suggerimento?

Answer 1

Un approccio potrebbe essere il backup dei dati effettivi con i dati di una raccolta.

Facciamo un esempio:

struct t_voxel { 
    size_t nPoints, minHeight, maxHeight, centorid; 
}; 

struct t_voxel_id { 
    uint16_t index; 
}; 

// one dimension 
class t_voxel_collection { 
    // the actual voxel data needed for the indices represented by the collection of voxelId 
    std::vector<t_voxel> d_voxel; 
    // here, empty voxel is designated by t_voxel.index = 0 
    // this collection is your primary array representation 
    // these elements just refer to a unique or shared index in this->d_voxel 
    std::vector<t_voxel_id> d_voxelId; 
public: 
    // >> the interface to access and set, which abstracts the backing collection. 
    // and prohibits the client from accessing the actual data. 

    t_voxel get(const size_t& idx) const { 
    return this->d_voxel[this->d_voxelId[idx].index]; 
    } 
    // ... 
}; 

è possibile ottenere un forte calo nel consumo di memoria in questo modo (supponendo che si vede il senso questo sta andando).

Questa non è una risposta completa, ma potrebbe aiutare in questo scenario.

Esistono diversi modi per ottimizzare ulteriormente e condividere i dati voxel in questa raccolta, a seconda dell'utilizzo.

Answer 2

Se sono davvero "solo" milioni di punti, molto più del 90% dei voxel si svuoterà. Proverei un multimap hash (std::unordered_multimap in C++ 11) dalle coordinate voxel ai punti. Questo ti dà la ricerca O (1), come un array. Tuttavia, presenta un sovraccarico, ma è probabilmente il miglior compromesso.

L'unica cosa di cui hai bisogno per questo funzionamento è un confronto di uguaglianza nella classe voxel e una specializzazione del modello std::hash<voxel>. Non otterrai il "numero massimo di punti" implementato in alcun modo automatico, ma è davvero utile?

Answer 3

Strutture dati classiche per questo tipo di dati sono kd-Trees e octrees..

Inoltre, si consiglia di dare un'occhiata alle strutture di dati spatial searching and sorting implementate in CGAL.

Answer 4

Stai per sbloccarti qualunque cosa tu faccia, anche se trovi un layout di memoria perfetto per la tua griglia sparsa - è ancora troppa memoria richiesta. Il vero problema è riuscire a memorizzarlo in modo efficiente su disco e memorizzare in modo intelligente le regioni di interesse.

Per fortuna Field3D è stato sviluppato proprio per questo.