[GRASS-dev] Raster format idea

[Cedric Shock]

Glynn,

> 2. Tiled storage would handle sparse maps better than row storage. How
> it compared to quadtrees would depend upon the typical cluster size.

Here's an absolutely wacky idea for a storage mechanism. (I love it when I 
shove together words or ideas that I don't completely understand).

Here's what it is:

Take the raster data. Split it up into tiles (Glynn is happy).
Make a new set of raster data in which each pixel is the mean of 4 pixels in 
the original map (Joel is happy). Split it up into tiles (Cedric is happy). 
Lather rinse repeat until you have a raster map of a single tile. The big 
kicker is make sure that one tile in a more general map exactly covers four 
tiles in the more specific map. Include null data (so entire tiles can be 
null and not exist).

A generic sparse matrix might be better for some datasets depending on how 
it's clustered, just like Glynn said. I propose that those datasets are 
better served by vector data formats.

It has a few benefits that I've already thought of:

Quick rendering at any resolution. A dataset of approximately the same 
resolution already exists unless the desired dataset is many fewer pixels 
than the size of a tile.

Possibility of unbelievably quick rendering in low viewing angle 3d views. 
Amount of data needed to cover the screen is virtually invariant with respect 
to view. You just need enough tiles to fill in the parts of the screen at the 
resolution they are at. A tile cache doesn't need to know anything about the 
geometry of the tiles (just remember whichever ones are "used the most"). 
Moving around locally on the screen shouldn't greatly change the tiles needed 
on the horizons.

Actually, there's no reason except convenience that the resolution of a map 
must be the same everywhere.

Here's a really ill-conceived data type (hard to read and write to files 
because of the pointer):

struct quadtile {
	tilepixels * pixels;
	tilenulls * nulls;
	quadtile quads[4];
}

Actually, the problem of pointers in files should be solvable with an in-file 
heap. It should be possible (even routine?) to map a file to memory without 
actually loading it, right? 

Now the question of an interface to these files is a bit trickyer. All the 
current access methods would need to be implemented on top of a tile cache 
for extra fun specialness. Many algorithms would prefer the direct tile or 
quadtree or quadtree tile access.

Drawbacks:

Dataset size is as big as a quadtree.

--Cedric