A function to populate an array with maps

Question

I'm pretty new to C++ so I'm not sure I'm going about this problem in the right way. I'm dealing with a 3D array of voxel data and I would like to create a parallel data structure to store isosurface normal vectors. Memory efficiency is an issue so I thought to use a 2D array of maps, which are indexed by an integer and contain a 3D vector.

The idea being the 2D array indexes every x and y coordinate and the maps index only the z coordinates containing a value (typically between 0 and 3 values dispersed along each row of the z axis).

Question 1: how do I create a 2D array of maps like std::map<int, Vector3f> surfaceNormals; ?

Question 2: My idea is declare the 2D array global then to populate it with a function which deals with it by pointer and creates a map for each array cell, is the code below on the right track? the ?????'s indicate where i'm not sure what to put given my uncertainty about Question 1.

In particular am I managing pointers/references/values correctly such as to actually end up storing all the data I need?

????? isoSurfaces1 [256][100];

????? *extractIS(float Threshold, ????? *pointy){

   ????? *surfacePointer = pointy;

   for loop over x and y {

      std::map<int, Vector3f> surfaceNormals;

      for loop over z {

         [ ... find surface voxels and their normal vectors ... ]

         Vector3f newNormalVector(x,y,z);

         surfaceNormals[zi] = newNormalVector;
      }           

      surfacePointer[x][y] = surfaceNormals;
   }

   return surfacePointer;
}

extractIS(0.45, isoSurfaces1);

Answer 1

If i understood you correctly, you want to use the coordinate as a std::map key?

You could just create 1 dimensional std::map, and convert the XYZ coordinates into 1 dimensional coordinate system:

int pos1d = z*max_x*max_y+y*max_x+x;

and then just put that to the map key.

Edit: or you could just use a struct with x,y,z as integers as Space_C0wb0y showed, but that will of course take 3x more memory per std::map key, also note that the example i showed will have the maximum cube size: 1625x1625x1625 (if unsigned int), so if you need longer coordinates then use a struct, but note that with structs you have to write comparisor function for the std::map key datatype.

Edit3: I think this is what you are looking for, as i noticed you used max 256 coordinate value, here is what i came up with:

// NOTE: max 256x256x256 cube coordinates with this struct. change unsigned char to short or int etc if you need larger values.
// also note that if you change to something else than unsigned char, you cant use nor compare the union: v1.Pos > v2.Pos anymore. 
// (unless you use unsigned short for each coordinate, and unsigned __int64 for the union Pos value)

union PosXYZ {
    struct {
        unsigned char x, y, z, padding; // use full 32bits for better performance
    };
    unsigned __int32 Pos; // assure its 32bit even on 64bit machines

    PosXYZ(unsigned char x, unsigned char y, unsigned char z) : x(x), y(y), z(z), padding(0) {} // initializer list, also set padding to zero so Pos can be compared correctly.
};   


inline bool operator>(const PosXYZ &v1, const PosXYZ &v2){
    return v1.Pos > v2.Pos;
}


typedef map<PosXYZ, Vector3f, greater<PosXYZ> > MyMap;


void extractIS(float Threshold, MyMap &surfacePointer){
    for loop over x and y {
        for loop over z {
            // [ ... find surface voxels and their normal vectors ... ]
            Vector3f newNormalVector(x,y,z);

            surfacePointer[PosXYZ(x,y,z)] = newNormalVector;
        }           
    }
}


MyMap isoSurfaces1;

extractIS(0.45, isoSurfaces1);

Another way to do this std::map key struct is to just use plain integer value, which you would generate via your own function similar to: ((x << 16) | (y << 8) | z), this will simplify things a little since you dont need the comparisor function for std::map anymore.

#define PosXYZ(x,y,z) (((x) << 16) | ((y) << 8) | (z)) // generates the std::map key for 256x256x256 max cube coords.

typedef map<unsigned __int32, Vector3f, greater<unsigned __int32> > MyMap;


void extractIS(float Threshold, MyMap &surfacePointer){
    for loop over x and y {
        for loop over z {
            // [ ... find surface voxels and their normal vectors ... ]
            Vector3f newNormalVector(x,y,z);

            surfacePointer[PosXYZ(x,y,z)] = newNormalVector;
        }           
    }
}


MyMap isoSurfaces1;

extractIS(0.45, isoSurfaces1);

Answer 2

First off, a map has a higher memory overhead than a vector. This brings up the question, how many elements are there? Is it feasible to have vectors that are partly empty? Consider the following implementation:

struct 3dvec {
    3dvec(int x, int y, int z) : x(x), y(y), z(z) {}

    int x;
    int y;
    int z;
};
std::vector<3dvec> empty_z_vector(4, 3dvec(0, 0, 0));
std::vector< std::vector<3dvec> > data(width*height, empty_z_vector);

You simply keep all values in memory, based on the assumption that only a few of them will be empty, and there will never be more than 4 z-values. You can access the 3dvec at position X, Y, Z like this:

data[X + Y*width][Z]

This is making a lot of assumptions, but in the end, you will have to compare possible solution, because the feasibility depends on the data.