org.xith3d.utility.general
Class GridIndexedFileHeap
java.lang.Object
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.
| Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |