×

Fast reconstruction of Delaunay triangulations. (English) Zbl 1115.68158

Summary: We present a new linear time algorithm to compute a good order for the point set of a Delaunay triangulation in the plane. Such a good order makes reconstruction in linear time with a simple algorithm possible. Similarly to the algorithm of Snoeyink and van Kreveld [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459-471], our algorithm constructs such orders in O(logn) phases by repeatedly removing a constant fraction of vertices from the current triangulation. Compared to [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459-471] we improve the guarantee on the number of removed vertices in each such phase. If we restrict the degree of the points (at the time they are removed) to 6, our algorithm removes at least 1/3 of the points while the algorithm from [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459-471] gives a guarantee of 1/10. We achieve this improvement by removing the points sequentially using a breadth first search (BFS) based procedure that-in contrast to [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459-471]-does not (necessarily) remove an independent set.
Besides speeding up the algorithm, removing more points in a single phase has the advantage that two consecutive points in the computed order are usually closer to each other. For this reason, we believe that our approach is better suited for vertex coordinate compression.
We implemented prototypes of both algorithms and compared their running time on point sets uniformly distributed in the unit cube. Our algorithm is slightly faster. To compare the vertex coordinate compression capabilities of both algorithms we round the resulting sequences of vertex coordinates to 16-bit integers and compress them with a simple variable length code. Our algorithm achieves about 14% better vertex data compression than the algorithm from [Proceedings of 5th European Symposium on Algorithms (ESA), 1997, pp. 459-471].

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52B55 Computational aspects related to convexity
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry

Software:

Edgebreaker
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alliez, P.; Desbrun, M., Progressive encoding for lossless transmission of 3D meshes, (ACM SIGGRAPH’01 Conference Proceedings (2001)), 198-205
[2] Alliez, P.; Desbrun, M., Valence-driven connectivity encoding for 3D meshes, (Eurographics’01 Conference Proceedings (2001)), 480-489
[3] Bajaj, C.; Pascucci, V.; Zhuang, G., Single resolution compression of arbitrary triangular meshes with properties, (Data Compression Conference’99 Proceedings (1999)), 247-256
[4] Boissonnat, J.-D.; Teillaud, M., On the randomized construction of the Delaunay tree, Theoret. Comput. Sci., 112, 339-354 (1993) · Zbl 0780.68110
[5] Cohen-Or, D.; Levin, D.; Remez, O., Progressive compression of arbitrary triangular meshes, (IEEE Visualization’99 Conference Proceedings (1999)), 67-72
[6] Deering, M., Geometry compression, (ACM SIGGRAPH’95 Conference Proceedings (1995)), 13-20
[7] Devillers, O.; Gandoin, P.-M., Geometric compression for interactive transmission, (IEEE Visualization’00 Conference Proceedings (2000)), 319-326
[8] Denny, M.; Sohler, C., Encoding a triangulation as a permutation of its point set, (9th Canadian Conference on Computational Geometry (1997))
[9] Guéziec, A.; Bossen, F.; Taubin, G.; Silva, C., Efficient compression of non-manifold polygonal meshes, (Visualization’99 Conference Proceedings (1999)), 73-80
[10] Guibas, L. J.; Knuth, D. E.; Sharir, M., Randomized incremental construction of Delaunay and Voronoi diagrams, Algorithmica, 7, 381-413 (1992) · Zbl 0743.68128
[11] Gumhold, S.; Strasser, W., Real time compression of triangle mesh connectivity, (ACM SIGGRAPH’98 Conference Proceedings (1998)), 133-140
[12] Ho, J.; Lee, K.; Kriegman, D., Compressing large polygonal models, (Visualization’01 Conference Proceedings (2001)), 357-362
[13] Hoppe, H., Progressive meshes, (ACM SIGGRAPH’96 Conference Proceedings (1996)), 99-108
[14] Isenburg, M.; Alliez, P., Compressing polygon mesh geometry with parallelogram prediction, (Visualization’02 Conference Proceedings (2002)), 35-42
[15] Isenburg, M.; Snoeyink, J., FaceFixer: Compressing polygon meshes with properties, (ACM SIGGRAPH’00 Conference Proceedings (2000)), 263-270
[16] Isenburg, M., Compressing polygon mesh connectivity with degree duality prediction, (Graphics Interface’02 Conference Proceedings (2002)), 161-170
[17] Karni, Z.; Gotsman, C., Spectral compression of mesh geometry, (ACM SIGGRAPH’00 Conference Proceedings (2000)), 279-286
[18] Khodakovski, A.; Alliez, P.; Desbrun, M.; Schröder, P., Near-optimal connectivity encoding of 2-manifold polygon meshes, Graphical Models, 64, 3-4, 147-168 (2002) · Zbl 1038.68133
[19] Khodakovski, A.; Schröder, P.; Sweldens, W., Progressive geometry compression, (ACM SIGGRAPH’00 Conference Proceedings (2000)), 271-278
[20] King, D.; Rossignac, J., Guaranteed 3.67v bit encoding of planar triangle graphs, (Proceedings of the 11th Canadian Conference on Computational Geometry (1999)), 146-149
[21] King, D.; Rossignac, J., Optimal bit allocation in 3D compression, Computational Geometry, 14, 91-118 (1999) · Zbl 0953.68618
[22] Kronrod, B.; Gotsman, C., Optimized compression of triangle mesh geometry using prediction trees, (International Symposium on 3D Data Processing Visualization and Transmission (2002)), 602-608
[23] Li, J.; Kuo, C., A dual graph approach to 3D triangular mesh compression, (Proceedings of ICIP’98 (1998)), 891-894
[24] Pajarola, R.; Rossignac, J., Compressed progressive meshes, IEEE Trans. Visualization and Computer Graphics, 6, 1, 79-93 (2000)
[25] Rossignac, J., Edgebreaker: Connectivity compression for triangle meshes, IEEE Trans. Visualization and Computer Graphics, 5, 1, 47-61 (1999)
[26] Rossignac, J.; Szymczak, A., WrapZip decompression of the connectivity of triangle meshes compressed with Edgebreaker, Computational Geometry, 14, 119-135 (1999) · Zbl 0956.68547
[27] Snoeyink, J.; van Kreveld, M., Linear-time reconstruction of Delaunay triangulations with applications, (Proceedings of 5th European Symposium on Algorithms (ESA) (1997)), 459-471 · Zbl 1477.68493
[28] Taubin, G.; Guéziec, A.; Horn, W.; Lazarus, F., Progressive forest split compression, (ACM SIGGRAPH’98 Conference Proceedings (1998)), 123-132
[29] Taubin, G.; Rossignac, J., Geometric compression through topological surgery, ACM Trans. Graphics, 17, 2, 84-115 (1998)
[30] Touma, C.; Gotsman, C., Triangle mesh compression, (Graphics Interface’98 Conference Proceedings (1998)), 26-34
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.