Modeling and visualization of changes of geometric models caused by small tools and erosion: technical report no. DCSE/TR-2013-01

Terrain modeling has been an important area of computer graphics and GIS for more than 20 years and despite this long history many problems still prevail. One of the important challenges is an interactive physics-based authoring and editing of large scale terrains. Most of published work use a regular grid to represent a terrain elevation data. Due to the simplicity of this representation, visualization and processes such as editing, thermal erosion, water erosion, etc. could be easily and efficiently implemented. However, such a regular structure cannot provide an adaptive level of detail. Moreover, as the resolution of the data structure is fixed, a smallest detail of the terrain is essentially defined and the mesh cannot capture any finer features which are clearly visible on close-ups (without enormous memory requirements). This problem could be solved by using irregular (or pseudo-irregular) structures such as a triangulation, quad-tree, etc. But it brings new problems and challenges. This work describes the state of the art of interactive terrain modeling. We will mostly focus on terrains covered by granular materials such as, e.g., sand. This work also contains description of our method for interactive modeling and editing of sand-covered terrains based on triangulated irregular network (TIN). First we describe basic data structures used for granular terrain representations in computer graphics, followed by a minimum geometry knowledge about the Delaunay triangulation and triangulations in general. Next, methods for interactive modeling of sand are described in detail. Then we concentrate on the state of the art of the terrain erosion modeling in computer graphics and state of the art of haptic visualization of the terrains. Then our improvements and published algorithms are presented