Структуры данных и алгоритмы для адаптивной «однородной» сетки?

Question

мне нужна структура данных для хранения значений с плавающей запятой при равномерно отобранное 3D сетки:

х = х0 + IX * дх где 0 < = ие < пе

у = у0 + гу * д, где 0 < = Iy < пу

г = г0 + из- * дг где 0 = < < из- новозеландских

до сих пор я использовал свой Array, класс:

Array3D<float> A(nx, ny,nz); 
A(0,0,0) = 0.0f; // ix = iy = iz = 0 

Внутренне он хранит значения float как 1D-массив с элементами nx * ny * nz.

Однако теперь мне нужно представить сетку с большим количеством значений, чем у меня есть ОЗУ, например. nx = ny = nz = 2000.

Я думаю, что многие соседние узлы в такой сетке могут иметь одинаковые значения, поэтому я думал, был ли какой-то простой способ, чтобы я мог «грубить» сетку адаптивно.

Например, если узлы 8 (ix, iy, iz) из ячейки в этой сетке имеют значения, которые меньше 5% друг от друга; они «удаляются» и заменяются только одним значением; среднее из 8 значений.

Как я мог реализовать такую ​​структуру данных простым и эффективным способом?

EDIT: спасибо Ante за предложение сжатия с потерями. Я думаю, что это может работать следующим образом:

#define BLOCK_SIZE 64 
struct CompressedArray3D { 
    CompressedArray3D(int ni, int nj, int nk) { 
     NI = ni/BLOCK_SIZE + 1; 
     NJ = nj/BLOCK_SIZE + 1; 
     NK = nk/BLOCK_SIZE + 1; 

     blocks = new float*[NI*NJ*NK]; 
     compressedSize = new unsigned int[NI*NJ*NK]; 
    } 

    void setBlock(int I, int J, int K, float values[BLOCK_SIZE][BLOCK_SIZE][BLOCK_SIZE]) { 
     unsigned int csize; 
     blocks[I*NJ*NK + J*NK + K] = compress(values, csize); 
     compressedSize[I*NJ*NK + J*NK + K] = csize; 
    } 

    float getValue(int i, int j, int k) { 
     int I = i/BLOCK_SIZE; 
     int J = j/BLOCK_SIZE; 
     int K = k/BLOCK_SIZE; 

     int ii = i - I*BLOCK_SIZE; 
     int jj = j - J*BLOCK_SIZE; 
     int kk = k - K*BLOCK_SIZE; 

     float *compressedBlock = blocks[I*NJ*NK + J*NK + K]; 
     unsigned int csize = compressedSize[I*NJ*NK + J*NK + K]; 

     float values[BLOCK_SIZE][BLOCK_SIZE][BLOCK_SIZE]; 
     decompress(compressedBlock, csize, values); 
     return values[ii][jj][kk]; 
    } 

    // number of blocks: 
    int NI, NJ, NK; 

    // number of samples: 
    int ni, nj, nk; 

    float** blocks; 
    unsigned int* compressedSize; 
}; 

Для этого, чтобы быть полезным мне нужно сжатие с потерями, который:

• очень быстро, а также на небольших наборах данных (например, 64x64x64)
• компресс довольно сложно> 3 раза, неважно, если он потеряет совсем немного информации.

Любые хорошие кандидаты?

Answer 1

Похоже, вы ищете адаптивную сетку LOD (уровень детализации). Это повторяющаяся тема в видеоиграх и симуляции ландшафта.

Для местности, см. Здесь: http://vterrain.org/LOD/Papers/ - искать видео ROAM, которое является IIRC не только адаптивным по расстоянию, но и по направлению просмотра.

Для некоммерческих организаций существует огромное количество работ (вот один пример: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch05.html).

Answer 2

Я бы предложил использовать OctoMap для обработки больших трехмерных данных. И удлинить его, как показано на рисунке here для обработки геометрических свойств.