Rapid production of optimal-quality reduced-resolution representations of very large databases

A computer-implemented process for producing view space representation data in real time from a world space database representing spatial data, comprising:

• (a) preprocessing the world space database, comprising the steps of:
• (b) forming a database having one element for each spatial region corresponding to a finest selected level of detail,
• (c) forming a multiresolution database by merging elements at the finest level of detail and subsequent intermediate levels of detail to define a hierarchy of element resolutions until a coarsest selected resolution is obtained,
• (d) computing a strict error metric for each element at each level of detail that is independent of parameters defining the view space and that is approximately monotonic to associate with the elements forming the multiresolution database, and
• (e) storing the multiresolution database and associated error metrics;
• and
• (f) processing the multiresolution database and associated strict error metrics in real time, comprising the steps of:
• (g) selecting view parameters for a view volume comprising a view location and field of view,
• (h) choosing elements with the coarsest resolution to form roots of subtrees of a tree for an initial representation data set,
• (i) performing a view volume test to select first elements from the initial representation data set that are at least partially within the view volume,
• (j) converting the strict view-independent error metric using the view parameters to a strict view-dependent error metric,
• (k) placing the first elements in a split queue ordered by the value of the strict view-dependent error metric where a first element having the largest error metric is placed at the head of the queue,
• (l) making a determination whether the number of first elements in the queue meet or exceed a predetermined number of elements or whether the largest error metric is less than or equal to a selected upper error metric bound,
• (m) if the determination in step (l) is negative,force splitting the element at the head of the queue, including:
• removing the element from the split queue and the representation,
• splitting the element into its children,
• testing the children against the view volume if the parent was only partially in the view volume,
• adding the children to the tree as children of the elements from which they were split, constituting new leaf elements,
• inserting the children that are at least partially within the view volume into the split queue,
• (n) designating the children in the queue as first elements and repeat steps (l)-(m) until the determination is positive to form a set of second elements in the split queue as the representation data set, and
• (o) outputting the set of second elements as reduced resolution view space data representing the terrain features.