Re: Two proposals for using ElevationGrids in VRML

[Martin Reddy <reddy>]

Hi Heiko,

Some really good suggestions here. I think that both are valid for some
further investigation. The binary format helps storage and transmission
rates, and the dynamic tessellation helps the run-time frame rate (assuming
it can be done efficiently). Some comments:

1. Binary format. I like the idea of having a heightUrl field as an
alternative to the height array. You bring up good points with regard to
8-bit versus 16-bit precision. I think that 16-bit support is mandatory, but
we can probably support 8-bit also, particularly if we have a scale and
offset capability. For example, the binary file that is pointed to could have
a simple format like: 

  Byte Range    Type          Description
  ----------    ----          -----------
  0-3           float         scale to be applied to all height values
  4-7           float         offset to be applied to all height values
  8-9           short         8 or 16 to define bytesize of each height value
  10...         short or int  the actual height values

Of course, we could add lots more info, such as the dimensions of the grid
but these are specified in the fields of the GeoElevationGrid node and the
KISS principle is pretty compelling. The main point is that by supporting a
scale and offset pair, you can use 8- or 16-bit ints to get a wide range of
height scales and also support precisions to a number of decimal points. This
is essentially what we do right now with the binary terrain data for our
TerraVision system. 

(An interesting aside, maybe we can arrange the height values in some order
that enables progressive updating of the geometry - i.e. we can stream in the
binary file and instantly create a single polygon and refine this as we read
in more of the file. Just a thought.)

2. Dynamic tessellation. The main issues here are whether we can implement
this efficiently in something like Java, and also what perceptual artifacts
this might introduce. There has of course been some interesting work in this
area in the past that may be applicable, e.g.

David Luebke, Carl Erikson.  View-Dependent Simplification Of
   Arbitrary Polygonal Environments. Proceedings of SIGGRAPH 97, ACM
   Press (August 1997).

Hughes Hoppe.  View-Dependent Refinement of Progressive Meshes.
   Proceedings of SIGGRAPH 97, ACM Press (August 1997).

Peter Lindstrom, David Koller, William Ribarsky, Larry Hodges, Nick
   Faust, and Gregory Turner.  Real-Time, Continuous Level of Detail
   Rendering of Height Fields. Report GIT-GVU-96-02, Computer Graphics
   (SIGGRAPH '96), pp. 109-118 (August, 1996).

Approaches like Luebke's are rather nice in that they have support for things
like silhouette preservation built in to the view-dependent algorithm. We
would need to choose an appropriate method and implement it in a language
supported by VRML, i.e. Java. 


So where to go from here? Well, the GeoElevationGrid source code, and all of
the underlying coordinate transform code, is of course Open Source. I
strongly encourage any group of people interested in trying to put together
an implementation of this to download the sources and give it a go! There are
plenty of good things that we could do for the next version of GeoVRML, and
this is definitely up there and I think would turn some heads.

Cheers,

Martin.


> during the last days, I've been experimenting with ElevationGrids in VRML.
> Two problems come up again and again. These are:
> 
> 1) Content is too large for small-bandwidth download to work. Sometimes
> even high-bandwidth isn't enough...
> 2) ElevationGrids of reasonable size lead to very large triangle counts, in
> turn leading to very bad performance in the browser.
> 
> GeoVRML currently deals (amongst other things) mainly with the first
> problem by putting ElevationGrid data into tiles, which are loaded only
> when actually needed. I would like to make two additional proposals and
> hear what people have to say about it.
> 
> 1) Binary encoding for EG-data.
> Instead of proposing yet another binary format for geometries, I would
> propose to use one of the existing 2D compressed image formats. I've tested
> 8bit PNG format and got a factor of 2 decrease in filesize. This is
> compared against gzipped content of course. Since many DEM's cannot be
> encoded losslessly in 8bit and 1m accuracy, there are two solutions.
>      1a) use smaller tiles, thus decreasing the probability of high
> altidude variations within the EG. This solves the problem only partly,
> because of large         altitude variations within small distances.
>      1b) Use 16 bit formats. 16 bit is more than enough for height data
> accuracy of 1m.
> An additional advantage of this method could be, that browsers have
> decoders for these graphical formats already build in. Once we could access
> these decoders, theres no need to add special decoders as is needed for
> other binary geometry. Additionally, taking a look at the various (wavelet
> based) JPEG 2000 proposals for a new JPEG format, I expect the compression
> rates to increase dramatically also for DEM-data.
> 
> 2) Triangularization using the accuracy of the data.
> Currently, within the ElevationGrid as well as the GeoElevationGrid node,
> there is no possibility to store the vertical accuracy of the data. This
> value could be used by the renderer to do some mesh reduction. I've done
> some preliminary experiments with TIN generation and found, that although
> it can take quite a bit of CPU time and memory, it generally reduces
> triangle count by up to a factor of 10 while keeping accuracy. The
> requirements for CPU-time and memory can be reduced quite a bit, if the
> grid-size would be small enough.
> 
> Note, that both proposals require modification of the current
> GeoElevationGrid node. The first would need an URL instead of the height
> values, whereas the second would need at least an SFFloat providing the
> vertical accuracy of the data.
> 
> 
> Regards
> 
> Heiko Grussbach
> Heiko.Grussbach@crpht.lu
> 
> 

---------------------------------------------------------------------------
Martin Reddy                                   SRI International, AI Center
                                               Menlo Park, CA 94025-3493
reddy@ai.sri.com                               Tel : (650) 859-6468
http://www.ai.sri.com/~reddy                   Fax : (650) 859-3735