Interactive 3D Motion Graphics with Large Data Bases [Thesis]
Stephen Levine, USDOE Office of Science (SC) · 1975
A graphic data organization was designed that allows for fast access to an arbitrarily large data base .The graphic data is organized by clustering into successively larger spheres .The derived tree structure provides for multilevel descriptions of objects that allow for display of only the amount of detail that can be resolved on the display, in addition to rapid determination of data in the field of view .An algorithm was developed to search for the minimum volume sphere enclosing a set of points in three dimensions .A heuristic was used to speed the search for the minimum volume sphere gaining several orders of magnitude improvement over a non-heuristic-search .In support of the minimum volume sphere heuristic, an algorithm to calculate the convex hull of a set of points in more than two dimensions was constructed .For the three-dimensional data sets tested, an order of magnitude improvement over an existing algorithm was found .To facilitate display of a simulation of a user moving through space containing a large number of objects, a fast hidden-line algorithm was developed .It allows for display of linearly separable three-dimensional convex solids, two-dimensional concave planes, and three-dimensional wire frame objects .A complex picture consisting of 16 objects (192 edges) requires only 130 milliseconds on a third generation large scale computer .Extensive tests of the algorithms were made using a variety of data sets .The results are summarized in a series of graphical presentations .