Algorithms for manipulating large geometric data by Jiri Skala.
Abstract:
This thesis deals with manipulating huge geometric data in the field of computer graphics. The proposed approach uses a data stream technique to allow processing gigantic datasets that by far exceed the size of the main memory. The amount of data is hierarchically reduced by clustering and replacing each cluster by a representative. The input data is organised into a hierarchical structure which is stored on the hard disk. Particular clusters from various levels of the hierarchy can be loaded on demand. Such a multiresolution model provides an efficient access to the data in various resolutions. The Delaunay triangulation (either 2D or 3D) can be constructed to introduce additional structure into the data. The triangulation of the top level of the hierarchy (the lowest resolution) constitutes a coarse model of the whole dataset. The level of detail can be locally increased in selected parts by loading data from lower levels of the hierarchy. This can be done interactively in real time. Such a dynamic triangulation is a versatile tool for visualisation and maintenance of large geometric models. Further applications include local computations, such as height field interpolation, gradient estimation, and mesh smoothing. The algorithms can take advantage of a high local detail and a coarse context around. The method was tested on large digital elevation maps (digital terrain models) and on large laser scanned 3D objects, up to half a billion points. The data stream clustering processes roughly 4 million points per minute, which is rather slow, but it is done only once as a preprocessing. The dynamic triangulation works interactively in real time.
The touchstone for this paper is a scan of David which contains 468.6 million vertices.
Visualization isn’t traditional graph processing but then traditional graph traversal isn’t the only way to process a graph.
Perhaps future graph structures will avoid being hard coded for particular graph processing models.