Triangulations and tetrahedronizations

I.Kolingerová, 2001

Internal members of the research team:

I.Kolingerová, P.Maur, J.Kohout

students of the Selected algorithmic methods 1998-2000

External cooperation:

· Dr.B.Žalik, Department of Computer Science, University of Electrical Engineering and Computer Science, University of Maribor, Slovenia,

· RNDr.A.Ferko,CSc., Department of Computer Graphics and Image Processing, Faculty of Mathematics and Physics, Comenius University, Slovakia

Our research in planar triangulations is focused mainly on efficient algorithms of unstructured triangle meshes, both serial and parallel. Survey of existing methods of planar triangulations can be found in [Kol99b].

For implementation of Delaunay triangulation in MVE and for further research, we chose the incremental insertion algorithm. This algorithm is not worst-case optimal as it achieves O(n^2) time complexity, however, its expected behaviour is much better – in average, O(nlogn) time complexity is achieved. It is robust, simple, elegant. It can be modified for constrained Delaunay triangulation (CDT) (see Fig.1) or for different metrics (see Fig.2). We developed some improvements of incremental insertion algorithm for Delaunay triangulation in 2D. The first proposed modification speeds up the algorithm to about one half of the original time. Another simple modification can save about 28 per cent of memory requirements for the penalty of about 9 per cent slow-down. Both proposed techniques can be used together or independently. The first proposed modification was also implemented in the MVE module DTlib. An example of a triangulation computed with this implementation see in Fig.3, 4.

[Work in progress]

An example of CDT

Fig.1

An example with more metrics in one triangulation

Fig.2

An example of Delaunay triangulation computed in our implementation and shaded in MVE

Fig.3

Another example of Delaunay triangulation

Fig.4

For good expected behaviour of the incremental algorithm in 2D, the most important point is an effective location of triangles containing inserted points. In order to achieve a logarithmic time per point, special data structures or algorithms are necessary. Usually, DAG with history of insertion is used for this purpose. However, it needs some amount of memory; savings can be obtained with uniform grid. It is our first amendment to the incremental insertions.

Details of the proposed improvements will hopefully be available soon (submitted papers).

Our attention is also devoted to possibilities of parallelization of Delaunay triangulation. Much work has already been given to this topic all over the world; existing parallelizations are usually based on divide and conquer type of method or on an incremental construction. As far as we know, our algorithm is the first one based on incremental insertion. Unlike existing methods, it was developed for workstations with several processors which are nowadays more and more often. It is very simple. We derived three versions of the algorithm, the so called pessimistic, optimistic and optimistic burglary parallel Delaunay triangulations. The proposed methods were tested up to 8 processors. Results can be found in [Kol00b] and [Koh01].

In 2D, Delaunay triangulation has been proved to provide the most equiangular triangles of all methods. Properties in 3D are not so persuading, although still good enough to use Delaunay methods as a basis for other approaches. Therefore, we worked also on improvement of tetrahedra shapes by post-optimization of Delaunay meshes. Results were presented in [Mau00a, Mau00b, Mau00c]. An example of the Delaunay tetrahedronization see in Fig.5.

An example of Delaunay tetrahedronization

Fig.5

Besides these ‘practical’ triangulations, our research concerned also with more theoretical parts of the triangulation topic, namely with the minimum weight triangulation (MWT) and its heuristics. Although we developed some heuristics for this problem, based on locally minimum triangulations [Kol97], look-ahead search [Kol99a] and genetic approach [Kol98a, Kol98b], we are still far from practically usable solution because the proposed approaches provide approximate solutions for hundreds of points and it is still too low amount for practical applications. However, with genetic approach, we are able to optimize not only weight but also complicated combinations of criteria. We called such triangulations multi-criteria optimized triangulations, see Fig. 6 [Kol01, Kol98c, Kol00a]. The problem is time of computation and uncertainty of results (recall that genetic optimization is a probabilistic method and quality of its results is very variable).

An example of possibilities of multi-criteria optimized triangulation, obtained by genetic approach (left part optimized on maximum weight, right on minimum weight). (This is only theoretical example showing broad possibilities of the proposed approach, the criterium of maximum weight is not usable in practices as it leads to very bad shapes of triangles.)

Fig.6

References

[Kol97] Kolingerová I., Magová I., Ferko A., Niepel L. : Better Subgraph of Minimum Weight Triangulation, in : Proceedings of Spring Conference on Computer Graphics, Budmerice, Slovakia, 1997, pp.49-56

[Kol98a] Kolingerová I.: Genetic Approach to the Minimum Weight Triangulation, in : WSCG'98 Conference Proceedings, Volume II, Pilsen, Czech Republic, 1998, pp.184-191

[Kol98b] Kolingerová I.: Genetic Optimization of the Triangulation Weight, in: 3IA´98 International Conference Proceedings, Limoges, France, 1998, pp.23-34

[Kol98c] Kolingerová I.: Genetic Approach to Data Dependent Triangulations, in : SCCG'99 Conference Proceedings, Budmerice, 1999, pp.229-238

[Kol99a] Kolingerová I.: Greedy Triangulation Improvement over Lookahead Search, Computer Engineering and Informatics CE&I ´99 Conference Proceedings, pp. 34-39, STU Košice, Herlany, 1999

[Kol99b] Kolingerová I.: Rovinné triangulace, habilitation thesis, University of West Bohemia, Plzeň, Czech Republic, 1999

[Kol00a] Kolingerová I.: Genetic Approach to Triangulations, in : 3IA 2000 Conference Proceedings, Limoges, France, 2000, pp.11-23

[Kol00b] Kolingerová I., Kohout J.: Pessimistic Threaded Delaunay Triangulation by Randomized Incremental Insertion, Graphicon conference, Moscow, Russia, 2000

[Mau00a] Maur P.: Generování tetrahedronových sítí z rozptýlených dat, diploma thesis, University of West Bohemia, Plzeň, Czech Republic 2000 (supervisor I.Kolingerová)

[Mau00b] Maur P., Kolingerová I.: Properties of Delaunay tetrahedra, Computer Engineering and Informatics CE&I ´00 Conference Proceedings STU Košice, Herlany, Slovak Republic, 2000

[Mau00c] Maur P., Kolingerová I.: Post-optimization of Delaunay Tetrahedrization, in : Proceedings of Spring Conference on Computer Graphics, Budmerice, Slovak Republic, 2001, MFF UK Bratislava, 2001, pp.76-85 and IEEE, Los Alamitos, USA, pp.31-38

[Koh01] Kohout J.: Parallel Delaunay Triangulation, in: Proceedings of the CESCG conference, Budmerice, Slovakia, pp.85-94

[Kol01] Kolingerová I., Ferko A.: Multicriteria-optimized Triangulations, The Visual Computer, Springer Verlag, Vol. 17, No. 6, 2001, s.380-395. The original publication is available on LINK at http://link.springer.de/ .