Tech blog September 24, 2013
Computational geometry engines are central to both emerging and ubiquitous technologies. From online mapping to digital chip manufacturing, computational geometry algorithms reduce enormous sets of data into visualizable results that enable engineers and casual users to make informed decisions.
The plane sweep algorithm open_in_new, although widely used in computational geometry, does not parallelize efficiently, rendering it incapable of benefiting from recent trends in multicore CPUs and general-purpose GPUs. Instead of the plane sweep, some researchers have proposed a uniform grid as a foundation for parallel algorithms of computational geometry open_in_new. However, long-standing robustness and performance issues have deterred its wider adoption, at least in the case of overlay analysis. To remedy this, we have developed previously unknown, unique methods to perform snap rounding and compute efficiently the winding number of overlay faces on a uniform grid. We have implemented them as part of an extensible geometry engine to perform polygon overlay with OpenMP on CPUs and CUDA on GPUs. As previously announced, we have released a software product, called “Geometric Performance Primitives (GPP),” based on this implementation. The overall algorithm works on any polygon configuration, either degenerate, overlapping, self-overlapping, disjoint, or with holes. With typical data, it features time and space complexities of O(N + K), where N is the number of edges and K the number of intersections. Its single-threaded performance not only rivals the plane sweep, it achieves a parallel efficiency of 0.9 on our quad-core CPU, with an additional speedup factor of over 4 on our GPU. These performance results should extrapolate to distributed computing and other geometric operations.
To obtain baseline performance, we compared GPP against equivalent functionality found in the following commonly used GIS software tools: ArcGIS 10.1 for Desktop, GRASS 6.4.2, OpenJUMP 1.6.3 (with JTS 1.13 as backend), and QGIS 1.8.0 (with GEOS 3.3.2 as backend), whose algorithms execute on a single thread only and may or may not exploit the plane sweep. Nevertheless, note that their rich set of features may create additional overhead not yet present in GPP. With each of them, we applied a dissolve (merge) operation and a geometric intersection (boolean AND) of two pairs of layers taken from real-world datasets and listed the resulting execution performance. Its overall performance fared well against the existing solutions, reaching an average speed up of 16 x on CPU alone against ArcGIS, the fastest currently available software application we found.
Performance of ArcGIS versus GPP on real-world datasets. Please refer to the paper for more technical details.
At this year’s ACM SIGSPATIAL open_in_new, our technical paper was selected out of over 200 very competitive entries. Please refer to the paper for more technical details. The SIGSPATIAL section of the ACM covers a broad range of innovative designs and implementations, with special attention paid to emerging trends in geospatial information systems (GIS).
So, what’s our next step? GPP has already gained some success in the Electronic Design Automation (EDA) industry. Our next target is object-relational database engines. Computational geometry processing is a necessary component of spatially aware systems, including database management systems (DBMS) such as Oracle Spatial and Graph, and PostGIS for PostgreSQL. For database management systems, spatially-aware extensions provide native support for storage and retrieval of geometric objects that are commonly quite large and complex. This turns a standard DBMS into a location-aware engine that can drive business and technology applications referencing complex, layered, and/or geographical data into an intuitive and visualizable form. In addition to generalized spatial queries for their databases, Oracle’s solution, for example, provides explicit support for geo-referenced images, topologies, 3D data types, including triangulated irregular networks (TINs), and point clouds with native support for LIDAR data. PostGIS, on the other hand, provides native support and algorithms for ESRI shapefiles, raster map algebra, and spatial reprojection. When combined with GPP’s highly-parallelized computational geometry engine, these functions can processes the large, multi-layered data sets necessary to perform automated emergency route generation, natural resource management, insurance analysis, petroleum exploration, and financial queries 10 times or more faster than conventional algorithms.
We are excited to attend SIGSPATIAL 2013 in November and look forward to discussing the opportunities for geospatial processing that GPP provides with developers and researchers from around the world. See you in Florida!