Algorithms for manipulation with large geometric and graphic data: technical report no. DCSE/TR-2009-02

The theme of this work is manipulating large data in the field of computer graphics. Generally, large data appear in many scientific disciplines ranging from weather forecasting to marketing analyses. The computing power of modern computers still increases but so do the demands to process larger and larger data sets. The main memory is in principle insufficient to hold all the data at the same time so techniques are developed to handle the data in pieces. Random access is unacceptable in such cases so special, so called out-of-core, methods are used to process the data. Data stream algorithms are frequently used for efficient computations on large data. The algorithms are characterised by processing the data as a continuous stream in one or very few linear scans. Streaming algorithms were getting more attention in the last few years, however, they are not much used in computer graphics. This work first describes the state of the art concerning large data and data streams. An overview of clustering and a Delaunay triangulation follows. Next we propose a solution for manipulation with large geometric data. It is based on a clustering that identifies groups in the data. Each group is then replaced by a representative which reduces the data significantly. A data stream approach is used to cluster really huge data. A hierarchy of clusters is built which is then used by the dynamic hierarchical triangulation. It constructs a triangulation of the clustered data. By switching between clusters and their representatives, the level of detail can be changed in various parts of the data. Several more improvements are presented. The clustering algorithm was adapted. Both the clustering and the triangulation can use anisotropic metrics if suitable for any specific problem. A concept is presented how to modify the clustering to do space partitioning for ray tracing acceleration