On an uniform mesh of positions in space $\ (x_i,y_j,z_k)$:

$$\ x_i = x_0 + i\Delta x,\quad i=0,\ldots,n_x$$ $$\ y_j = y_0 + j\Delta y,\quad j=0,\ldots,n_y$$ $$\ z_k = z_0 + k\Delta z,\quad k=0,\ldots,n_z$$

I have a velocity function: $V(x_i,y_j,z_k)$.

Given a start position $(x_s,y_s,z_s)$ I can calculate the time it takes to reach all points in space: $T(x_i,y_j,z_k)$ by the Fast Marching Method (FMM).

However, I would like to do this on a mesh larger than can fit in RAM, e.g. $n_x=n_y=n_z=2000$.

FMM needs access to ALL velocity data. It is NOT possible to run it on only a part of the mesh and then later combine results somehow.

The data structure storing the velocity data can, however, be sparse. As long as the FMM can ask for the value at any $(x_i,y_j,z_k)$ it does not care how it is stored internally.

I imagine setting blocks of values at a time:

struct SparseArray3D {
    SparseArray3D(int nx, int ny, int nz);
    void setBlock(int i0, int j0, int k0, float block[64][64][64]); // i0 <= i < i0 + 64, j0 <= j < j0 + 64, k0 <= k < k0 + 64  
    float& operator()(int i, int j, int k); // needed by FMM

Do you have any tips on which data structure I could use?

(As you probably already have guessed) I am programming in C/C++.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.