Streaming computation of Delaunay triangulations

ABSTRACT

We show how to greatly accelerate algorithms that compute Delaunay triangulations of huge, well-distributed point sets in 2D and 3D by exploiting the natural spatial coherence in a stream of points. We achieve large performance gains by introducing spatial finalization into point streams: we partition space into regions, and augment a stream of input points with finalization tags that indicate when a point is the last in its region. By extending an incremental algorithm for Delaunay triangulation to use finalization tags and produce streaming mesh output, we compute a billion-triangle terrain representation for the Neuse River system from 11.2 GB of LIDAR data in 48 minutes using only 70 MB of memory on a laptop with two hard drives. This is a factor of twelve faster than the previous fastest out-of-core Delaunay triangulation software.

REFERENCES

• 1: Agarwal, P. K., Arge, L., and Yi, K. 2005. I/O-efficient construction of constrained Delaunay triangulations. In Proceedings of the Thirteenth European Symposium on Algorithms, 355--366.
• 2: Nina Amenta , Sunghee Choi , Günter Rote, Incremental constructions con BRIO, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777824]
• 3: Blandford, D. K., Blelloch, G. E., Cardoze, D. E., and Kadow, C. 2005. Compact representations of simplicial meshes in two and three dimensions. International Journal of Computational Geometry and Applications 15, 1 (Feb.), 3--24.
• 4: Blelloch, G. E., Hardwick, J. C., Miller, G. L., and Talmor, D. 1999. Design and implementation of a practical parallel Delaunay algorithm. Algorithmica 24, 3--4 (Aug.), 243--269.
• 5: Bowyer, A. 1981. Computing Dirichlet tessellations. Computer Journal 24, 2, 162--166.
• 6: Buchin, K. 2005. Constructing Delaunay triangulations along space-filling curves. In Second Symposium on Voronoi Diagrams, 184--195.
• 7: Cignoni, P., Montani, C., and Scopigno, R. 1998. DeWall: A fast divide and conquer Delaunay triangulation algorithm in Ed. Computer-Aided Design 30, 5 (Apr.), 333--341.
• 8: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989
• 9: Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
• 10: Fortune, S. 1992. Voronoi diagrams and Delaunay triangulations. In Computing in Euclidean Geometry, D.-Z. Du and F. Hwang, Eds., vol. 1 of Lecture Notes Series on Computing. World Scientific, Singapore, 193--233.
• 11: Frederick, C. O., Wong, Y. C., and Edge, F. W. 1970. Two-dimensional automatic mesh generation for structural analysis. International Journal for Numerical Methods in Engineering 2, 133--144.
• 12: Martin Isenburg , Stefan Gumhold, Out-of-core compression for gigantic polygon meshes, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 13: Isenburg, M., and Lindstrom, P. 2005. Streaming meshes. In Visualization '05 Proceedings, 231--238.
• 14: Martin Isenburg , Peter Lindstrom , Stefan Gumhold , Jack Snoeyink, Large Mesh Simplification using Processing Sequences, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.61, October 22-24, 2003 [doi>10.1109/VISUAL.2003.1250408]
• 15: Richard M. Karp, On-Line Algorithms Versus Off-Line Algorithms: How Much is it Worth to Know the Future?, Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture - Information Processing '92, Volume 1, p.416-429, September 07-11, 1992
• 16: Katajainen, J., and Koppinen, M. 1988. Constructing Delaunay triangulations by merging buckets in quadtree order. Fundamenta Informaticae XI, 11, 275--288.
• 17: Kumar, P. 2003. Cache oblivious algorithms. In Algorithms for Memory Hierarchies, LNCS 2625, U. Meyer, P. Sanders, and J. Sibeyn, Eds. Springer-Verlag, 193--212.
• 18: Lawson, C. L. 1977. Software for C1 surface interpolation. In Mathematical Software III, J. R. Rice, Ed. Academic Press, New York, 161--194.
• 19: Liu, Y., and Snoeyink, J. 2005. A comparison of five implementations of 3D Delaunay tessellation. In Combinatorial and Computational Geometry, vol. 52 of MSRI Publications. Cambridge, 435--453.
• 20: Okabe, A., Boots, B., Sugihara, K., and Chiu, S. N. 2000. Spatial tessellations: Concepts and applications of Voronoi diagrams, 2nd ed. Wiley, New York.
• 21: Pajarola, R. 2005. Stream-processing points. In Visualization '05 Proc., 239--246.
• 22: Quillin, M., 2002. Flood plain maps better, but late---years late, March 11. Raleigh News & Observer.
• 23: Clifford A. Shaffer, Fast circle-rectangle intersection checking, Graphics gems, Academic Press Professional, Inc., San Diego, CA, 1990
• 24: Shamos, M. I., and Hoey, D. 1975. Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science, IEEE Press, 151--162.
• 25: Jonathan Richard Shewchuk, Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.203-222, May 27-28, 1996
• 26: Shewchuk, J. R. 1997. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18, 3 (Oct.), 305--363.
• 27: Jonathan Richard Shewchuk, Tetrahedral mesh generation by Delaunay refinement, Proceedings of the fourteenth annual symposium on Computational geometry, p.86-95, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276894]
• 28: Peter Su , Robert L. Scot Drysdale, A comparison of sequential Delaunay triangulation algorithms, Proceedings of the eleventh annual symposium on Computational geometry, p.61-70, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220286]
• 29: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 30: Watson, D. F. 1981. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. Computer Journal 24, 2, 167--172.
• 31: Sung-Eui Yoon , Peter Lindstrom , Valerio Pascucci , Dinesh Manocha, Cache-oblivious mesh layouts, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Theory

Keywords:
Delaunay triangulation, TIN terrain model, geometry processing, spatial finalization, stream processing