Search

Haptic devices are nowadays often used in non-hitech applications due to their increasing availability. These special input/output devices provide native 3D manipulation and, additionally, unlike mouse or keyboard, a control with a force. We present a low-level haptic visualization method which is able to simulate material on a surface and which works natively with the triangulated irregular network terrain models (TIN). Our method allows to model and visualize several materials, such as sand, concrete, wood, etc. New materials could be created by setting five parameters and, optionally, by the creation of a material relief. In our framework we use the TIN terrain model together with real-time erosion and interactive haptic editing using a set of virtual tools. We have performed a user study which is also included in the paper. Unlike existing methods, we use a general shape of the tool; our solution is capable of geometric editing of the TIN model, and it allows a simulation of several materials.

Finding which triangle in a planar triangle mesh contains a query point is one of the most frequent tasks in computational geometry. Usually, a large number of point locations has to be performed, and so there is a need for fast algorithms resistant to changes in triangulation and having minimal additional memory requirements. The so-called walking algorithms offer low complexity, easy implementation and negligible additional memory requirements, which makes them suitable for such applications. In this paper, we propose a walking algorithm which significantly improves the current barycentric approach and propose how to effectively combine this algorithm with a suitable hierarchical structure in order to improve its computational complexity. The hierarchical data structure used in our solution is easy to implement and requires low additional memory while providing a significant acceleration thanks to the logarithmic computational complexity of the search process.

A pseudo-triangulation is a planar subdivision into pseudo triangles - polygons with three convex vertices, used mainly in motion planning problems in robotics. As it is a rather new concept, not too many algorithms to construct it exist. In this paper, we propose an online version of incremental insertion, with generalized flips to improve the shape of pseudo-triangles. This algorithmic paradigm is often used for Delaunay triangulations, but for pseudo-triangulations it has been used only in an off-line version (for sorted input points). We also experimented with several optimization criteria for the flips and show their influence on the shape of pseudo-triangles.

We propose a new algorithm for the detection of all intersections between a set of balls and a general query object. The proposed algorithm does not impose any restrictive condition on the set of balls and utilises power diagrams to minimize the amount of intersection tests. The price for this is power diagram computation in a preprocessing step.

Representation of the digital image by a triangulation does not bring a high compression but enables geometric transformations and is very simple. In this paper we will show that it is also possible to choose the triangulation vertices randomly, then their [x, y] position does not need to be stored as it can be easily reconstructed during decoding. We show how such a choice behaves in comparison and in combination with the vertices selected from the edges of the digital image.

We describe the current methodology used in the air traffic control and show how the kinetic Delaunay triangulation may be used to predict potentially dangerous situations of two aircrafts on a crash course. We use a real data obtained from the radar readings of the air space of the Czech Republic and process this data in order to create and manage the triangulation. We also show how the alternation of certain application-specific parameters may change the overall performance of the triangulation.

This chapter surveys existing research and main achievements of simulated annealing and genetic algorithms for triangulation based problems, such as generation of an optimal triangulation, improvement of a shape of triangles or tetrahedra and positions of their vertices, the use of triangulations for digital image representation, registration of 3D models and their textures, etc. Main features of the methods, their results and typical problems are pointed out.

Applications such as video games or movies often contain deforming meshes. The most-commonly used representation of these types of meshes consists in dense polygonal models. Such a large amount of geometry can be efficiently managed by applying level-of-detail techniques and specific solutions have been developed in this field. However, these solutions do not offer a high performance in real-time applications. We thus introduce a multiresolution scheme for deforming meshes. It enables us to obtain different approximations over all the frames of an animation. Moreover, we provide an efficient connectivity coding by means of triangle strips as well as a flexible framework adapted to the GPU pipeline. Our approach enables real-time performance and, at the same time, provides accurate approximations.

Surface reconstruction is a common problem in computer graphics. Given a set of points sampled from some surface, a triangle mesh interpolating or approximating the points is to be obtained. One of very often used techniques for solving this problem is the selection of surface triangles from the set of Delaunay tetrahedronization faces. In the case of large data, it is difficult to obtain the tetrahedronization due to its huge memory requirements. One of possible solutions is to use distributed computing. Here, we describe the newly developed VSM (Virtual Shared Memory) distributed toolkit and its utilization for the task of surface reconstruction. By our approach, we were able to process dataset having 1.4M points on 4xP4 interconnected via 100Mb Ethernet in 6 hours. About 5GB of memory was consumed during the reconstruction.

We demonstrate a connection between a regular triangulation and a constrained Delaunay triangulation in 2D. We propose an algorithm for edge enforcement in the constrained Delaunay triangulation based on the use of regular triangulation. As far as we know, such a connection has not been presented yet in the literature and there is no algorithm based on this idea, too. This work also serves as a spring-board to higher dimensions.

One of the methods for 3D data model acquisition is the real object digitization followed by the surface reconstruction. Many algorithms have been developed during past years, each of them with its own advantages and disadvantages. We use for the reconstruction a CRUST algorithm by Nina Amenta, which selects surface triangles from the Delaunay tetrahedronization using information from the dual Voronoi diagram. Unfortunately, these candidate surface triangles do not form a manifold, so it is necessary to perform some other steps for manifold extraction. In this paper we present some improvements and observations for this step.

Given a finite point set in R3 scanned by special devices from the object surface, a surface model interpolating or approximating the points set has to be obtained. We use for the reconstruction a CRUST algorithm by Nina Amenta, which selects surface triangles from the Delaunay tetrahedronization using information from the dual Voronoi diagram. This set of candidate surface triangles does not form a manifold, so the manifold extraction step is necessary. We present two improvements for this step, the former is limited to the used algorithm and the latter can be used with any other reconstruction algorithm.

Automatic computation of contour lines on a triangulation is a difficult problem because due to input data digitization and the type of triangulation used, some triangles can be a source of a strange behaviour of the contour lines. In this paper, we show what problems can appear in contour lines when Delaunay or greedy triangulations are used and how the contour lines can be improved using constraints in the triangulation. We improved contour lines by manually imposing constraints in a triangulation editing program. Automation of this process is a next step of our work.

The paper describes a modification of DAG-based location for incremental insertion Delaunay triangulation algorithm in E2 and E3. Instead of the whole simplices, only their separating faces are stored and tested. The proposed technique allows full reuse of results obtained on previous DAG levels. This enables to reduce time for point location and memory requirements. Asymptotic memory and time complexity is not changed.