Introduction

Date: 2015-10-07; view: 512.

Unit 9. Texts for extracurricular work

Task 10. Translate the text. Mind the sentence structure and style

Text 1. Streaming Computation of Delaunay Triangulations (fragment 3)(1200 characters)

Martin Isenburg, Yuanxin Liu, Jonathan Shewchuk, Jack Snoeyink

New instruments have made huge geometric data sets common in terrain modeling (LIDAR, synthetic aperture radar), medical image analysis (magnetic resonance imaging, tomography), and computer-aided engineering (laser range scanning, finite element methods). These data sets are often many times larger than the memories of commodity computers, and overwhelm the algorithms and data formats used to manage and analyze them. Our expanding capacity to collect geometric data has inspired a recent burst of research on streaming representations of large-scale geometry [Isenburget al. 2003; Isenburg and Lindstrom 2005; Pajarola 2005].We detail here how we use streaming computation to construct a billion-triangle Delaunay triangulation of a planar point set in 48 minutes with an off-the-shelf laptop computer plus a firewire drive, using 70 MB of memory to produce a 16.9 GB triangulation. This is about a factor of twelve faster than the previous best out-of-core for demo software & source code see triangulator, by Agarwal, Arge, and Yi [2005]; see Section6. We also construct a nine-billion-triangle, 152 GB triangulation in under seven hours using 166 MB of main memory.

A streaming computation makes a small number of sequential passes over a data file (ideally, one pass), and processes the data using a memory buffer whose size is a fraction of the stream length. We have implemented two- and three-dimensional triangulators that read streams of points as input, and produce Delaunay triangulation in streaming mesh formats. The memory footprint of the 2D triangulator is typically less than 0.5% of the output mesh size (sometimes much less). The memory footprint of the 3D triangulator is typically less than 10% of the output mesh size when the points are roughly uniformly distributed in a volume. The main new idea in our streaming Delaunay triangulators is spatial finalization (which differs from the topological finalization of mesh entities like points and triangles in previous papers). We partition space into regions, and include finalization tags in the stream that indicate when no more points in the stream will fall in specified regions. Our triangulators certify triangles or tetrahedral as Delaunay when the finalization tags show it is safe to do so. This make it possible to write them out early, freeing up memory to read more from the input stream. Because only the unfinalized parts of a triangulation are resident in memory, the memory footprint remains small. We created our triangulators by making modest changes to existing incremental Delaunay triangulation implementations ‑ no new triangulation algorithm was needed. Streaming algorithms can succeed only if streams have sufficient spatial coherence ‑ a correlation between the proximity in space of geometric entities and the proximity of their representations in the stream. We present evidence in Section 3 that huge real-world data sets often do have sufficient spatial coherence. This is not surprising; if they didn't, the programs that created them would have bogged down due to thrashing. Moreover, we can add more spatial coherence to a stream by chunking ‑ reordering points (in memory, without resorting to an external sort) so that all the points in a region appear consecutively. Many external memory algorithms sort the geometry as a first step. One of our contributions is the observation that spatial coherence often enables us to triangulate a large point set in the time it takes just to sort it. (See Section 6.) With these ideas and a laptop, we can process the 11.2 GB of bare-earth LIDAR data for the Neuse River Basin, comprising over 500 million points (double-precision x, y, and height coordinates). This data comes from the NC Floodplain Mapping project1, begun after Hurricane Floyd in 1999. North Carolina was the first state to use LIDAR (Light Detection and Ranging, an airborne laser scanning technology) and capture elevation points to assess flood risks, set insurance premiums, and create disaster plans for an entire state. The sheer enormity of the models has hindered their processing, delaying the project's completion from 2002 to 2007 [Quillin 2002]. Faced with a half billion points, a typical in-core algorithm, with perhaps a gigabyte at its disposal, must resort to virtual memory. Then computations like following pointers through linked lists or triangulation data structures, maintaining priority queues, and allocating and freeing objects produce memory access patterns that cause thrashing ‑ excessive paging ‑ slowing execution to a crawl. We triangulate huge point sets with two concurrent programs depicted in Figure 2. The finalizer reads a stream of raw points three times from disk. During the first pass it finds the bounding box, on which we overlay a grid of rectangular regions. During the second pass it counts the number of points in each region. During the third pass it inserts spatial finalization tags, reorders the points, and writes a spatially finalized point stream to a pipe. Two finalizer components reorder points during the third pass: the chunker delays points so that the points in each region are contiguous, which improves spatial coherence, and the sprinkler promotes representative points (sampled during the second pass) to earlier positions in the stream, which averts the risk of quadratic running time. The triangulator reads the finalized point stream from the pipe and triangulates it with an incremental Delaunay algorithm, writing a finalized mesh stream while still reading the finalized point stream. The two programs triangulate the 11.2 GB Neuse River Basin point stream, producing a 16.9 GB mesh, in 48 minutes using 70 MB of memory. The finalizer occupies 60 MB of memory (used mainly to reorder points), and the triangulator occupies 10 MB ‑ less than 0.1% of the size of the mesh. If the triangulator can read an already-finalized point stream from disk, there is no need for the finalizer, and the triangulator runs in 35 minutes. The triangulation may be piped directly to another application ‑ for instance, software for mesh simplification, or for extracting contour lines or drainage networks from terrain. Because stream processing modules typically have small memory footprints, we run chains of them concurrently and stream gigabytes through them. A major benefit of streaming (without sorting the points as a first step) is quick feedback: For example, a user can pipe the triangulator's output to our streaming isocontour extraction module, whose output is piped to a visualization module. Isocontours begin to appear within minutes (or seconds), as our processes produce output hile still consuming input. If they look wrong, the user can abort the pipeline and restart all the streaming components with different parameters. With other methods, users must wait hours for the triangulator to finish before glimpsing the results. We advocate that applications that create huge geometric data sets, such as scientific simulations, should strive to write their output in the form of spatially coherent, spatially finalized, streaming geometry. The effort needed to do so is often small, and the reward is the ability to perform large-scale computations normally thought to be the exclusive domain of parallel supercomputers. Unfortunately, our streaming triangulators do not enjoy the same out-of-core performance for surface point clouds in 3D as they do for terrains and volume-filling point clouds. The difficulty is caused by the many large circumspheres in the Delaunay triangulations of surface point clouds, which thwart spatial finalization from certifying tetrahedra. We believe a more sophisticated finalization technique can overcome this hurdle. See the Conclusions for details.

Text 2. Streaming Computation of Delaunay Triangulations (fragment 4)(1170 characters)

Martin Isenburg, Yuanxin Liu, Jonathan Shewchuk, Jack Snoeyink