We present a fast linear time algorithm that uses a block-cut tree for identifying upstream features from a set of starting points in a network. Our implementation has been parallelized and it can process a dataset with 32 million features in less than 8 seconds on a 8-core workstation. This problem is the 2018 ACM SIGSPATIAL CUP challenge and presents several applications mainly on the field of utility networks. Our code is freely available for nonprofit research and education at https://github.com/sallesviana/FastUpstream

We present an algorithm to compute the intersection of two 3D triangulated meshes. It has applications in GIS, CAD and Additive Manufacturing, and was developed to process big datasets quickly and correctly. The speed comes from simple regular data structures that parallelize very well. The correctness comes from using multiple-precision rational arithmetic to prevent roundoff errors and the resulting topological inconsistencies, and symbolic perturbation (simulation of simplicity) to handle special cases (geometric degeneracies). To simplify the symbolic perturbation, the algorithm employs only orientation predicates. This paper focuses on the challenges and solutions of the implementing symbolic perturbation. Our preliminary implementation has intersected two objects totalling 8M triangles in 11 elapsed seconds on a dual 8-core Xeon. The competing LibiGL took 248 seconds and CGAL took 2726 seconds. Our software is freely available for nonprofit research.

This paper presents the optimization and parallelization of the multiple observer siting program, originally developed by Franklin and Vogt. Siting is a compute-intensive application with a large amount of inherent parallelism. The advantage of parallelization is not only a faster program but also the ability to solve bigger problems. We have parallelized the program using two different techniques: OpenMP, using multi-core CPUs, and CUDA, using a general purpose graphics processing unit (GPGPU). Experiment results show that both techniques are very effective. Using the OpenMP program, we are able to site tens of thousands of observers on a 16385 × 16385 terrain in less than 2 minutes, on our workstation with two CPUs and one GPU. The CUDA program achieves the same in about 30 seconds.

We present Grid-Gen, an efficient heuristic for map simplification. Grid-Gen deals with a variation of the generalization problem where the idea is to simplify the polylines of a map without changing the topological relationships between these polylines or between the lines and control points. Grid-Gen uses a uniform grid to accelerate the simplification process and can handle a map with more than 3 million polyline points and 10 million control points in 9 seconds in a Lenovo T430s laptop.

We present a better algorithm and implementation for external memory viewshed computation. It is about four times faster than the most recent and most efficient published methods. Ours is also much simpler. Since processing large datasets can take hours, this improvement is significant. To reduce the total number of I/O operations, our method is based on subdividing the terrain into blocks which are stored in a special data structure managed as a cache memory.

Levee overtopping can lead to failure and cause catastrophic damage, as was the case during Hurricane Katrina. We present a computer simulation of erosion to study the development of the rills and gullies that form along an earthen embankment during overtopping. We have coupled 3D Smoothed Particle Hydrodynamics with an erodibility model to produce our simulation. Through comparison between simulations and between simulation and analogous laboratory experiments, we provide quantitative and qualitative results, evaluating the accuracy of our simulation.

This paper presents an heuristic method to give an approximated solution to the observer siting problem on high resolution terrains that are too large to be processed in the internal memory. Informally, the problem is to determine an optimal positioning of as few as possible observers for being able to observe as many target points as possible. Tests have shown that the proposed heuristic can solve this problem using, on average, fifteen percent fewer observers than another heuristic described in the literature. This will permit more efficient positioning of facilities such as mobile phone towers, fire observation towers, and vigilance systems.

High quality, artifact-free fitting a bathymetry (sea-floor) surface to very unevenly spaced depth data from ship tracklines is possible with ODETLAP (Overdetermined Laplacian Partial Differential Equation). The problem is that many data points, but with imprecise values, can be collected along and near the ships, e.g., with Multibeam Bathymetry, but there are no data between the tracklines, which may be a considerable distance apart. The numerous artifacts of previous surface fitting algorithms were so totally unacceptable that even Photoshop has been used to smooth them. In contrast, the implementation of this version of ODETLAP generates surfaces that do not exhibit artifacts even when displayed with techniques that highlight minor slope irregularities, which is, in the authors' opinion, the most appropriate evaluation metric. Since the data is imprecise, ODETLAP's surface approximates, rather than interpolates, the data. ODETLAP can trade off smoothness and accuracy to capture the small features that are not artifacts. This extension to ODETLAP is a variable smoothness parameter so that points distant from a known depth are smoothed differently from points close to a known depth. The broader implication is that ODETLAP is a very powerful algorithm with many applications. The Matlab implementation is freely available for nonprofit research and education.

We introduce a parallel approximation of an Over-determined Laplacian Partial Differential Equation solver (ODETLAP) applied to the compression and restoration of terrain data used for Geographical Information Systems (GIS). ODETLAP can be used to reconstruct a compressed elevation map, or to generate a dense regular grid from airborne Light Detection and Ranging (LIDAR) point cloud data. With previous methods, the time to execute ODETLAP does not scale well with the size of the input elevation map, resulting in running times that are prohibitively long for large data sets. Our algorithm divides the data set into patches, runs ODETLAP on each patch, and then merges the patches together. This method gives two distinct speed improvements. First, we provide scalability by reducing the complexity such that the execution time grows almost linearly with the size of the input, even when run on a single processor. Second, we are able to calculate ODETLAP on the patches concurrently in a parallel or distributed environment. Our new patch-based implementation takes 2 seconds to run ODETLAP on an 800 x 800 elevation map using 128 processors, while the original version of ODETLAP takes nearly 10 minutes on a single processor (271 times longer). We demonstrate the effectiveness of the new algorithm by running it on data sets as large as 16000 x 16000 on a cluster of computers. We also discuss our preliminary results from running on an IBM Blue Gene/L system with 32,768 processors.

We present a better algorithm for path planning on complex terrain in the presence of observers and define several metrics related to path planning to evaluate the quality of various terrain compression strategies.

We present the GeoStar project at RPI, which researches various terrain (i.e., elevation) representations and operations thereon. This work is motivated by the large amounts of hi-res data now available. The purpose of each representation is to lossily compress terrain while maintaining important properties. Our ODETLAP representation generalizes a Laplacian partial differential equation by using two inconsistent equations for each known point in the grid, as well as one equation for each unknown point. The surface is reconstructed from a carefully-chosen small set of known points. Our second representation segments the terrain into a set of regions, each of which is simply described. Our third representation has the most long term potential: scooping, which forms the terrain by emulating surface water erosion.Siting hundreds of observers, such as border guards, so that their viewsheds jointly cover the maximum terrain is our first operation. This process allows both observer and target to be above the local terrain, and the observer to have a finite radius of interest. Planning a path so that a smuggler may get from point A to point B while maximally avoiding the border guards is our second operation. The path metric includes path length, distance traveled uphill, and amount of time visible to a guard.The quality of our representations is determined, not only by their RMS elevation error, but by how accurately they support these operations.

We present a technique for creating a digital elevation model (DEM) from grid-based contour data. The method computes new, intermediate contours in between existing isolines. These are found by finding the shortest line segment that connects points on two neighboring contours with differing elevations. The midpoint of the line segment becomes a point on the intermediate contour. The contours are completed by connecting individual points. The new contours are then used as data for successive iterations, until an initial surface is formed. Peaks are computed by Hermite splines that follow the slope trend. Gaussian smoothing is applied to the entire surface or only to newly computed elevations, yielding an approximated or interpolated surface, respectively. The DEMs are tested with quantitative methods, and are shown to compare favorably to well established algorithms.

A method is described for the extraction of morphological information from images approximated by triangular meshes. Topographic features such as peaks, pits, ridges, valleys, and planar regions are considered the basic descriptive surface elements and are defined in terms of the local organization of the triangles in the mesh. The approach is suitable for image analysis tasks, simplifying object recognition and scene interpretation. Several images have been used to demonstrate the performance of the proposed method.

A parallel object-space hidden surface removal algorithm for polyhedral scenes is presented. The uniform grid technique is used to achieve parallelism for the hidden line removal. A conflict-detection and back-off strategy is then used to obtain parallelism for the visible region reconstruction from the visible segments. The algorithm has been implemented on a Sequent Balance 21000 shared-memory parallel computer. An average speedup of 10 has been obtained using 15 processors.

Cartographic map overlay is the process of superimposing two maps into one to convey information in spatial correlation. A map refers to one in vector representation: a two‐dimensional spatial data structure of nodes, chains, and polygons. We present a map overlay system developed in Prolog. The system adopts a relational approach to data structuring. We represent geometric entities and their relationships as facts, and encode geometry algorithms in the rules. Set‐based operations perform data processing. To speed up the search for chain intersections, a uniform rectangular grid is imposed over the object space for spatial sorting by distribution. We sort out potentially intersecting edge segments to those occupying some common grid cell. Each bucket, if non‐empty, is implemented as a Prolog fact identifying the grid cell for random access. Geometric intersections are calculated using exact rational arithmetic implemented in Prolog. Numerical accuracy is preserved and we can identify all the special cases of tangent conditions. We can then guarantee topological consistency, and stability in the process of map overlay is therefore achieved.

This paper presents an implementation of Franklin's object space hidden surface algorithm for polyhedral scenes.4 It is known that if the faces are independently and identically distributed this algorithm performs in time linear in the number of faces, and in particular is not affected by the depth complexity. The algorithm overlays a grid on the scene with fineness depending on the statistics of the edges and the faces. It then preprocesses the edges and the faces in a grid data structure so that distant edges and faces will not be compared. The implementation of the algorithm on a Prime 750 using Ratfor shows that it is indeed very fast for random and structured scenes alike.

Calculating properties of polyhedra given only the set of the locations and neighborhoods of the vertices is easy. Possible properties include volume, surface area, and point containment testing. No global topological information at all is explicitly needed (although the complete global topology could be recovered). The neighborhood of the vertex means the directions of the edges and faces on it but not their extents. These vertex-based formulae are dual to the usual formulae that use the faces. They have been implemented and the stability against inconsistent data tested. Alternative data structures and formulae for polyhedron calculation are important since special cases are a function partly of the data structure, and because different methods have different numerical accuracy and error detection properties.

Abstract An efficient algorithm, HALO, is given to compute haloed line drawings of wire frame objects. Haloed line drawings are described by Appel et al.1 HALO has two parts: CUT and DRAW. CUT uses an adaptive grid to find all edge intersections. It overlays a square grid, whose fineness is a function of the number and length of the edges, on the Scene. It determines the cells that each edge passes through, sorts these by cell to obtain the edges in each cell, and then, in each cell, tests each pair of edges in that cell for intersection. For broad classes of input this takes time linear in the number of edges plus the number of intersections. CUT writes a file containing all the locations where each edge is crossed in front by another. Given a halo width, DRAW reads this file edge by edge. For each edge, it subtracts and adds the halo width to each intersection to get the locations where the edge becomes invisible and visible. It sorts these along the edge, and then traverses the edge, plotting those portions where the number of “Visible” transitions is equal to the number of “invisible” transitions. DRAW takes time hear in the number of edge segments. Dividing HALO into two parts means that redrawing a plot with a different halo width is fast, since only DRAW need to be rerun. CR Categories and Subject Descriptions: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling ‐ geometric algorithm, languages, and systems; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerid Algorithms and Problems ‐geometrical problem and computations General Terms: Algorithms, design.

This paper presents a more efficient method for iterated rotation in three dimensions where multiple points are being rotated by multiple angles about the same axis, as would he done in robotic simulation or computer graphic animation. General axes that do not necessarily pass through the origin and multiple composed rotations are also handled. The algorithm is numerically well conditioned for all axis directions.

This Paper presents a new hidden surface algorithm. Its output is the set of the visible pieces of edges and faces, and is as accurate as the arithmetic precision of the computer. Thus calculating the hidden surfaces for a higher resolution device takes no more time. If the faces are independently and identically distributed, then the execution time is linear in the number of faces. In particular, the execution time does not increase with the depth complexity. This algorithm overlays a grid on the screen whose fineness depends on the number and size of the faces. Edges and faces are sorted into grid cells. Only objects in the same cell can intersect or hide each other. Also, if a face completely covers a cell then nothing behind it in the cell is relevant. Three programs have tested this algorithm. The first verified the variable grid concept on 50,000 intersecting edges. The second verified the linear time, fast speed, and irrelevance of depth complexity for hidden lines on 10,000 spheres. This also tested depth complexities up to 30, and showed that perspective scenes with the farther objects smaller are even faster to calculate. The third verified this for hidden surfaces on 3,000 squares.

An efficient algorithm for displaying 3-D scenes showing a discrete spatially varying surface is described. Given a 2-D map or planar graph composed of polygons where each polygon has a positive real number attribute, a prism is erected on each polygon with height proportional to that attribute. The resulting 3-D scene is plotted with shading and hidden lines removed. Thus the spatial variation of the attribute may be quickly and intuitively grasped by the nontechnical observer. This has applications to areas such as geography if the map is a cartographic map, or to physics if the map diagrams the periodic table. The algorithm takes time O(N*log(N)) where N is the number of edges in the map. Most of the calculations can be done without knowing the prism heights so extra plots with different attributes for the prisms can be produced quickly. This algorithm has been implemented and tested on maps of up to 12000 edges.