Really big 3D array

Newbie & Debugging Questions
#1

Hi,

I came accross an idea and I’m dealing with metaballs right now. I manage to implement the marshing cube algorithme and the mesh look fine. But now I want a more accurate mesh and I have to do some optimization.

So now I end up with a really big 3D array of cube objects, but the array is almost empty (95% of null value if not more). And It uses far too mush memory.
I was wondering if there is an allready made class to deal with it ?
If not, what do you suggest to start with for my class ? Hashtable ? Arraylist ? (There is a round 40000 cubes)

#2

Lots of choices. Probably the most straight forward is an octree if you’ve never walked this path before. Do some searching on space partitioning.

#3 

import java.util.TreeMap;

/**
 *
 * @author BonbonChan
 */
public class Big3DArray<T>
{
  protected TreeMap<Integer,TreeMap<Integer,TreeMap<Integer,T>>> datas;

  public Big3DArray()
  {
    datas = new TreeMap<Integer,TreeMap<Integer,TreeMap<Integer,T>>>();
  }
    
  public void put(int x,int y,int z,T value)
  {      
    TreeMap<Integer,TreeMap<Integer,T>> treeY = datas.get(x);
    
    if (treeY == null)
    {
      treeY = new TreeMap<Integer,TreeMap<Integer,T>>();
      datas.put(x, treeY);
    }
    
    TreeMap<Integer,T> treeZ = treeY.get(y);
    
    if (treeZ == null)
    {
      treeZ = new TreeMap<Integer,T>();
      treeY.put(y, treeZ);
    }
      
    treeZ.put(z, value);
  }
  
  public T get(int x,int y,int z)
  {
    TreeMap<Integer,TreeMap<Integer,T>> treeY = datas.get(x);
    
    if (treeY == null)
    {
      return null;
    }
    
    TreeMap<Integer,T> treeZ = treeY.get(y);
    
    if (treeZ == null)
    {
      return null;
    }
     
 
    return treeZ.get(z);
  }
}

Anyone, a better idea ?

#4

Look at the storage of “hollow matrices” (“matrices creuses” in French).

#5

I guess hollow is the direct translation. Usually called “sparse matrices” in English.

Actually, for 40000 cubes why not just keep x,y,z coordinates for each. Look for some of Riven’s posts on mashing them into one big byte array to be cache friendly.