org.xith3d.utility.general
Class GridIndexedFileHeap

java.lang.Object
  extended by org.xith3d.utility.general.GridIndexedFileHeap

public class GridIndexedFileHeap
extends java.lang.Object

Generic utility class that indexes a random access file by a grid tree. It is extremely fast for grid style lookups and handles sparse data very well. The leafs can be an arbitrary sized data chunks. Manages an indexed file heap. For example if you have a granularity of 10, depth of 4 and leafSize of 20 you can index a grid of 10^4 * 20 by 10^4 * 20, or 200,000 x 200,2000 This means you can retrieve a data handle for the data stored at x,z = (0..n,0..n) where N is 200k with 4 key node retrievals. If there is no data at that leaf then it could require less actual key traversals since the key children might be null if that entire sub-tree is empty. In the above example each key node will be a 10x10 array of children pointers, where any pointer can be null, indicating there is no data below that part of the tree. The storage is most efficient for sparse data. In the pathalogical case of every possible leaf being stored, the indexing overhead would probably surpass the stored data, and since it could have been stored in a contiguous array with offsets being easily calculated, this results in possibly an extremely inefficient usage. Note for these cases it is far better to use a tree of depth one, so at least you can make use of the file heap and buffering, even if the indexing no longer buys you anything. An example of this would be terrain heightmaps. If some large percentage of the world is unknown, or is water, you will realize some nice saves in storage, while retaining the ability to load chunks of heightmaps quickly and with buffering. In the case of landscape details like trees and rocks, these can be fairly sparse and you can easily have You can also request all non-null children for a range of (x1,z1) .. (x2,z2) and expect extremely fast retrievals.


Method Summary
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait