Salles Viana Gomes de Magalhães

Thesis

2017

Salles Viana Gomes de Magalhães. Exact and parallel intersection of 3D triangular meshes. PhD thesis, Rensselaer Polytechnic Institute, Troy, NY, USA, 2017.
[abstract▼] [details] [full text] [BibTeX▼]

This thesis presents an exact parallel algorithm for computing the intersection between two 3D triangular meshes, as used in CAD/CAM (Computer Aided Design/Computer Aided Manufacturing), CFD (Computational Fluid Dynamics), GIS (Geographical Information Science) and additive manufacturing (also known as 3D Printing). Geometric software packages occasionally fail to compute the correct result because of the algorithm implementation complexity (that usually needs to handle several special cases) and of precision problems caused by floating point arithmetic. A failure in an intersection computation algorithm may propagate to any software using the algorithm as a subroutine. As datasets get bigger (and the chances of failure in an inexact algorithm increase), exact algorithms become even more important. While other methods for exactly intersecting meshes exist, their performance makes them non-suitable for applications where the fast processing of big geometric models is important (such as interactive CAD systems). The key to obtain robustness and performance is a combination of 5 separate techniques: • Multiple precision rational numbers, to exactly represent the coordinates of the objects and completely eliminate roundoff errors during the computations. • Simulation of Simplicity, a symbolic perturbation technique, to ensure that all geometric degeneracies (special cases) are properly handled. • Simple data representations and local information, to simplify the correct processing of the data and make the algorithm more parallelizable. • A uniform grid, to efficiently index the data, and accelerate some of the steps of the algorithm such as testing pairs of triangles for intersection or locating points in the mesh. • Parallel programming, to accelerate the intersection process and explore better the ubiquitous parallel computing capability of current hardware. To evaluate our ideas, we have developed and implemented EPUG-Overlay (Exact Parallel Uniform Grid Overlay), an exact and efficient algorithm for overlaying 2D maps. EPUG-Overlay applies all the techniques mentioned above and, as a result, it was not only exact but also very efficient. Indeed, it was able to compute the intersection of a map containing 32 million edges with another map having 21 million edges in 264 elapsed seconds using 16 threads with dual 8-core processors. By comparison, GRASS (a Geographic Information System) took 5, 300 seconds to perform the same computation, partly because it is only single-threaded. We have also developed PinMesh (Point In Mesh), an exact and efficient method for locating points in 3D meshes. The point location problem is an important step we intend to use for computing the intersection of 3D meshes. PinMesh was carefully implemented to always handle point location queries correctly. The use of efficient data structures associated with parallel programming made PinMesh very fast. According to our experiments, PinMesh was up to 27 times faster than the RCT (Relative Closest Triangle) 3D point location algorithm (that was, to the best of our knowledge, the fastest point location algorithm available). Finally, we developed 3D-EPUG-Overlay, an algorithm for exactly computing the intersection of pairs of 3D meshes. 3D-EPUG-Overlay employs all the techniques mentioned above to ensure its correctness and efficiency. Experiments showed that it was up to 101 times faster than the algorithm available in LibiGL (the state of art algorithm for exact mesh intersection) and, also, it had a performance that was comparable to a parallel inexact algorithm that was specifically developed to be very fast. Besides being fast, 3D-EPUG-Overlay was more memory efficient than the other evaluated methods. Furthermore, in all test cases the result obtained by 3D-EPUG-Overlay matched the reference solution. All the software developed for this thesis is freely available for other researchers to use and extend.
```
@phdthesis{salles-phd,
    author = "de Magalh{\\textasciitilde {a}}es, Salles Viana Gomes",
    title = "Exact and parallel intersection of {3D} triangular meshes",
    school = "Rensselaer Polytechnic Institute, Troy, {NY, USA}",
    year = "2017",
    mykey = "salles-thesis theses"
}
```

Papers

2022

W. Randolph Franklin and Salles Viana Gomes de Magalhães. Implementing simulation of simplicity for geometric degeneracies. In 4th ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2022). 1 Nov 2022.
[abstract▼] [details] [full text] [BibTeX▼]

We describe how to implement Simulation of Simplicity (SoS). SoS removes geometric degeneracies in point-in-polygon queries, polyhedron intersection, map overlay, and other 2D and 3D geometric and spatial algorithms by determining the effect of adding non-Archimedian infinitesimals of different orders to the coordinates. Then it modifies the geometric predicates to emulate that, and evaluates them in the usual arithmetic. A geometric degeneracy is a coincidence, such as a vertex of one polygon on an edge of another polygon, that would have probability approaching zero if the objects were distributed i.i.d. uniformly. However, in real data, they can occur often. Especially in 3D, there are too many types of degeneracies to reliably enumerate. But, if they are not handled, then predicates evaluate wrong, and the output topology may be wrong. We describe the theory of SoS, and how several algorithms and programs were successfully modified, including volume of the union of many cubes, point location in a 3D mesh, and intersecting 3D meshes.
```
@inproceedings{implementing-sos-2022,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes",
    title = "Implementing Simulation of Simplicity for geometric degeneracies",
    year = "2022",
    month = "1 Nov",
    booktitle = "4th {ACM SIGSPATIAL} International Workshop on Spatial Gems ({SpatialGems} 2022)",
    location = "Seattle, Washington",
    href = "\bibhref{234-implementing-sos-2022}",
    mykey = "recent salles parallel overlay"
}
```
Marcelo de Matos Menezes, Salles Viana Gomes Magalhães, Matheus Aguilar de Oliveira, W. Randolph Franklin, and Rodrigo Eduardo de Oliveira Bauer Chichorro. Fast parallel evaluation of exact geometric predicates on GPUs. J. Computer Aided Design, September 2022. Special Issue: 28th International Meshing Roundtable: Mesh Modeling for Simulations and Visualization. URL: https://www.sciencedirect.com/science/article/abs/pii/S0010448522000616, doi:https://doi.org/10.1016/j.cad.2022.103285.
[abstract▼] [details] [full text] [BibTeX▼]

This paper presents a technique for employing high-performance computing for accelerating the exact evaluation of geometric predicates. Arithmetic filters are implemented using interval arithmetic to reduce the necessity of exact arithmetic while ensuring the results of the predicates are still exact. Furthermore, the computation with interval arithmetic is offloaded to a CUDA-enabled GPU. If the GPU detects that some results cannot be trusted, the corresponding predicates are re-evaluated in parallel on the CPU using arbitrary-precision rational numbers. As a case study, a red-blue 3D triangle intersection algorithm has been implemented. Since the intervals are implemented using floating-point numbers, the parallel computing power of GPUs for processing these numbers led to a speedup of up to 1936 times (when compared against a similar sequential implementation) in the evaluation of these predicates (and up to 414 times if the entire runnning-time of the algorithm is considered). The excellent performance associated to the exactness makes this technique suitable for accelerating geometric operations in fields such as CAD, GIS and 3D modeling.
```
@article{marcelo-gpu-predicates-2021,
    author = "de Matos Menezes, Marcelo and Magalhães, Salles Viana Gomes and de Oliveira, Matheus Aguilar and Franklin, W. Randolph and de Oliveira Bauer Chichorro, Rodrigo Eduardo",
    editor = "Peiro, Joaquim and Shontz, Suzanne and Viertel, Ryan",
    title = "Fast parallel evaluation of exact geometric predicates on {GPU}s",
    month = "September",
    year = "2022",
    number = "103285",
    note = "Special Issue: 28th International Meshing Roundtable: Mesh Modeling for Simulations and Visualization",
    journal = "J. Computer Aided Design",
    doi = "https://doi.org/10.1016/j.cad.2022.103285",
    href = "\bibhref{239-marcelo-gpu-predicates-2021}",
    mykey = "recent salles marcelo matheus rodrigo parallel topology",
    url = "https://www.sciencedirect.com/science/article/abs/pii/S0010448522000616"
}
```
Marcelo de Matos Menezes, Salles Viana Gomes de Magalhães, Matheus Aguilar, W. Randolph Franklin, and Bruno Coelho. Employing GPUs to accelerate exact geometric predicates for 3D geospatial processing. In John Krumm, Andreas Züfle, and Cyrus Shahabi, editors, Spatial Gems, volume 1, chapter 11. ACM, 2022. URL: https://www.spatialgems.net/.
[abstract▼] [details] [full text] [BibTeX▼]

This paper presents a technique to use GPUs to accelerate the computation of 3D geometric predicates. A common predicate is computing the orientation of four 3D points, which is a subproblem in applications such as intersecting two 3D meshes. Since the higher level application may require billions of evaluations, efficiency is important. Accuracy is required since floating roundoff errors can cause topological impossibilities. One solution is to compute with rational numbers, but that is difficult to implement on a GPU because rationals' sizes vary. Our solution is to compute on the GPU with interval arithmetic, but fall back to using rationals on the CPU if the interval computed on the GPU includes the origin; i.e., its sign is unknown. Our experiment with a dataset of hard rock mining drill holes show that this fallback to the CPU is rarely necessary; so that our technique gave a 17 times speedup compared to a sequential implementation.
```
@incollection{marcelo-employing-gem-2022,
    author = "de Matos Menezes, Marcelo and de Magalhães, Salles Viana Gomes and Aguilar, Matheus and Franklin, W. Randolph and Coelho, Bruno",
    editor = "Krumm, John and Züfle, Andreas and Shahabi, Cyrus",
    title = "Employing {GPU}s to accelerate exact geometric predicates for {3D} geospatial PROCESSING",
    booktitle = "Spatial Gems",
    publisher = "ACM",
    year = "2022",
    volume = "1",
    chapter = "11",
    mykey = "recent salles marcelo matheus bruno parallel topology",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{242-marcelo-employing-gem-2022}"
}
```
W. Randolph Franklin and Salles Viana Gomes de Magalhães. Minimal representations of polygons and polyhedra. In John Krumm, Andreas Züfle, and Cyrus Shahabi, editors, Spatial Gems, volume 1, chapter 5. ACM, 2022. URL: https://www.spatialgems.net/.
[abstract▼] [details] [full text] [BibTeX▼]

We present several simple representations of polygon and polyhedra that permit the efficient parallel computation of area and volume. They are particularly useful for computing the areas of the nonempty intersections between pairs of faces in two overlapping planar graphs in GIS, or the volumes of nonempty intersections between pairs of tetrahedra in two overlapping triangulations of a polyhedron in CAD. Both applications have been implemented on multicore Intel Xeons and tested on large datasets. The representations store the minimal types of information required for computation, and never need to store edge loops and face shells, or even most adjacency relations. The representations are sets of tuples or small fixed-size sets, and can be processed in parallel with map-reduce operations.
```
@incollection{minrep-gem-2022,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes",
    editor = "Krumm, John and Züfle, Andreas and Shahabi, Cyrus",
    title = "Minimal representations of polygons and polyhedra",
    booktitle = "Spatial Gems",
    publisher = "ACM",
    year = "2022",
    volume = "1",
    chapter = "5",
    mykey = "recent salles overlay topology",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{241-minrep-gem-2022}"
}
```

2021

W. Randolph Franklin, Salles Viana Gomes de Magalhães, and Eric N Landis. Fast 3-D Euclidean connected components. In John Krumm, editor, 3rd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2021). ACM, 2 Nov 2021. URL: https://www.spatialgems.net/.
[abstract▼] [details] [full text] [BibTeX▼]

We present an efficient algorithm, with implementations, for computing the connected components within a 3-D cube of voxels, also known as the Euclidean union-find problem. There may be over $10^9$ voxels. The components may be 8-connected or 26-connected. Computing connected components has applications ranging from material failure in concrete under increasing stress to electrical conductivity in complex metal objects to elasticity in 3D printed parts. On key to efficiency is representing voxels by 1-D \emphruns of adjacent voxels. As a special case, 2-D connected components of images may easily be computed.
```
@incollection{connect-gem-2021,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes and Landis, Eric N",
    editor = "Krumm, John",
    title = "Fast {3-D} {Euclidean} connected components",
    booktitle = "3rd {ACM SIGSPATIAL} International Workshop on Spatial Gems (SpatialGems 2021)",
    publisher = "ACM",
    year = "2021",
    month = "2 Nov",
    location = "Beijing, China (virtual)",
    mykey = "recent salles landis connect topology 2021",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{240-connect-gem-2021}"
}
```

2020

Marcelo de Matos Menezes, Salles Viana Gomes de Magalhães, Matheus Aguilar, W. Randolph Franklin, and Bruno Coelho. Employing GPUs to accelerate exact geometric predicates for 3D geospatial processing. In John Krumm, editor, 2nd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2020). ACM, Nov 2020. URL: https://www.spatialgems.net/.
[abstract▼] [details] [full text] [BibTeX▼]

This paper presents a technique to use GPUs to accelerate the computation of 3D geometric predicates. A common predicate is computing the orientation of four 3D points, which is a subproblem in applications such as intersecting two 3D meshes. Since the higher level application may require billions of evaluations, efficiency is important. Accuracy is required since floating roundoff errors can cause topological impossibilities. One solution is to compute with rational numbers, but that is difficult to implement on a GPU because rationals' sizes vary. Our solution is to compute on the GPU with interval arithmetic, but fall back to using rationals on the CPU if the interval computed on the GPU includes the origin; i.e., its sign is unknown. Our experiment with a dataset of hard rock mining drill holes show that this fallback to the CPU is rarely necessary; so that our technique gave a 17 times speedup compared to a sequential implementation.
```
@incollection{marcelo-employing-gem-2020,
    author = "de Matos Menezes, Marcelo and de Magalhães, Salles Viana Gomes and Aguilar, Matheus and Franklin, W. Randolph and Coelho, Bruno",
    editor = "Krumm, John",
    title = "Employing {GPU}s to accelerate exact geometric predicates for {3D} geospatial PROCESSING",
    booktitle = "2nd {ACM SIGSPATIAL} International Workshop on Spatial Gems (SpatialGems 2020)",
    publisher = "ACM",
    year = "2020",
    month = "Nov",
    mykey = "salles marcelo matheus bruno parallel topology",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{238-marcelo-employing-gem-2020}",
    note = "Best paper award."
}
```
W. Randolph Franklin, Salles Viana Gomes de Magalhães, and Wenli Li. Siting thousands of radio transmitter towers on terrains with billions of points. 2020. arXiv 2006.16783. arXiv:2006.16783.
[abstract▼] [details] [full text] [BibTeX▼]

This paper presents a system that sites (finds optimal locations for) thousands of radio transmitter towers on terrains of up to two billion elevation posts. Applications include cellphone towers, camera systems, or even mitigating environmental visual nuisances. The transmitters and receivers may be situated above the terrain. The system has been parallelized with OpenMP to run on a multicore CPU.
```
@misc{siting-thousands-2020,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes and Li, Wenli",
    title = "Siting thousands of radio transmitter towers on terrains with billions of points",
    year = "2020",
    eprint = "2006.16783",
    archivePrefix = "arXiv",
    primaryClass = "eess.SP",
    note = "arXiv 2006.16783",
    href = "\bibhref{237-siting-thousands-2020}",
    mykey = "recent salles parallel visibility visviewshedsiting wenlili"
}
```
Salles V. G. de Magalhães, W. Randolph Franklin, and Marcus V. A. Andrade. An efficient and exact parallel algorithm for intersecting large 3-d triangular meshes using arithmetic filters. J. Computer Aided Design, March 2020. online 2019-12-19. doi:https://doi.org/10.1016/j.cad.2019.102801.
[abstract▼] [details] [full text] [BibTeX▼]

We present 3D-EPUG-OVERLAY, a fast, exact, parallel, memory-efficient, algorithm for computing the intersection between two large 3-D triangular meshes with geometric degeneracies. Applications include CAD/CAM, CFD, GIS, and additive manufacturing. 3D-EPUG-OVERLAY combines 5 techniques: multiple precision rational numbers to eliminate roundoff errors during the computations; Simulation of Simplicity to properly handle geometric degeneracies; simple data representations and only local topological information to simplify the correct processing of the data and make the algorithm more parallelizable; a uniform grid to efficiently index the data, and accelerate testing pairs of triangles for intersection or locating points in the mesh; and parallel programming to exploit current hardware. 3D-EPUG-OVERLAY is up to 101 times faster than LibiGL, and comparable to QuickCSG, a parallel inexact algorithm. 3D-EPUG-OVERLAY is also more memory efficient. In all test cases, 3D-EPUG-OVERLAY's result matched the reference solution. It is freely available for nonprofit research and education at https://github.com/sallesviana/MeshIntersection.
```
@article{salles-exact-cad-2019,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A.",
    title = "An efficient and exact parallel algorithm for intersecting large 3-D triangular meshes using arithmetic filters",
    journal = "J. Computer Aided Design",
    note = "online 2019-12-19",
    year = "2020",
    month = "March",
    volume = "120",
    doi = "https://doi.org/10.1016/j.cad.2019.102801",
    href = "\bibhref{232-salles-exact-cad-2019}",
    mykey = "recent marcus salles parallel overlay"
}
```

2019

W. Randolph Franklin and Salles Viana Gomes de Magalhães. Minimal representations of polygons and polyhedra. In John Krumm, editor, 1st ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2019). ACM, Nov 2019. URL: https://www.spatialgems.net/.
[abstract▼] [details] [full text] [BibTeX▼]

We present several simple representations of polygon and polyhedra that permit the efficient parallel computation of area and volume. They are particularly useful for computing the areas of the nonempty intersections between pairs of faces in two overlapping planar graphs in GIS, or the volumes of nonempty intersections between pairs of tetrahedra in two overlapping triangulations of a polyhedron in CAD. Both applications have been implemented on multicore Intel Xeons and tested on large datasets. The representations store the minimal types of information required for computation, and never need to store edge loops and face shells, or even most adjacency relations. The representations are sets of tuples or small fixed-size sets, and can be processed in parallel with map-reduce operations.
```
@incollection{minrep-gem-2019,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes",
    editor = "Krumm, John",
    title = "Minimal representations of polygons and polyhedra",
    booktitle = "1st {ACM SIGSPATIAL} International Workshop on Spatial Gems (SpatialGems 2019)",
    publisher = "ACM",
    year = "2019",
    month = "Nov",
    mykey = "recent salles overlay topology",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{236-minrep-gem-2019}"
}
```
Marcelo de Matos Menezes, Salles Viana Gomes Magalhães, W. Randolph Franklin, Matheus Aguilar de Oliveira, and Rodrigo E. O. Bauer Chichorro. Accelerating the exact evaluation of geometric predicates with GPUs. In Suzanne Shontz, Joaquim Peiró, and Ryan Viertel, editors, 28th International Meshing Roundtable. Buffalo, NY, USA, 16 Oct 2019. doi:10.5281/zenodo.3653101.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

This paper presents a technique for employing high-performance computing for accelerating the exact evaluation of geometric predicates. Arithmetic filters are implemented using interval arithmetic to reduce the necessity of exact arithmetic while ensuring the results of the predicates are still exact. Furthermore, the computation with interval arithmetic is offloaded to a CUDA-enabled GPU. If the GPU detects that some results cannot be trusted, the corresponding predicates are re-evaluated in parallel on the CPU using arbitrary-precision rational numbers. As a case study, a red-blue segment intersection algorithm has been implemented. Since the intervals are implemented using floating-point numbers, the parallel computing power of GPUs for processing these numbers led to a speedup of up to 289 times (when compared against a similar sequential implementation) in the evaluation of these predicates (and up to 40 times if the entire running-time of the algorithm is considered). The excellent performance associated to the exactness makes this technique suitable for accelerating geometric operations in fields such as CAD, GIS, VLSI design and meshing.
```
@inproceedings{marcelo-gpu-geometry-imr-2019,
    author = "de Matos Menezes, Marcelo and Magalhães, Salles Viana Gomes and Franklin, W. Randolph and de Oliveira, Matheus Aguilar and Chichorro, Rodrigo E. O. Bauer",
    editor = "Shontz, Suzanne and Peiró, Joaquim and Viertel, Ryan",
    title = "Accelerating the exact evaluation of geometric predicates with {GPU}s",
    booktitle = "28th International Meshing Roundtable",
    month = "16 Oct",
    address = "Buffalo, NY, USA",
    year = "2019",
    isbn = "978-1-7334890-0-3",
    doi = "10.5281/zenodo.3653101",
    href = "\bibhrefpt{235-marcelo-gpu-geometry-imr-2019}{235-marcelo-gpu-geometry-imr-2019-talk.pdf}",
    mykey = "recent salles parallel",
    customlinkslides = "https://wrfranklin.org/p/235-marcelo-gpu-geometry-imr-2019-talk.pdf"
}
```
W. Randolph Franklin and Salles V. G. de Magalhães. Computing intersection areas of overlaid 2d meshes. In IGS2019 International Geometry Summit Posters' proceedings. Vancouver, Canada, 17–21 June 2019. Solid Modeling Association.
[abstract▼] [details] [full text] [poster] [fastforward] [BibTeX▼]

Parover2 is a parallel algorithm and preliminary implementation to compute the area of every nonempty intersection of any face of one 2D mesh with any face from another mesh over an overlapping domain. This is the hard part of cross-interpolating data from one mesh to another, for when the faces one mesh have an attribute that would be useful for the faces of the other mesh. Parover2, implemented using a map-reduce paradigm in Thrust, can quickly process millions of faces. The expected execution time is linear in the number of intersections, which is usually linear in the number of input faces. A uniform grid quickly determines the pairs of input edges that might intersect. Local topological formulae compute the areas of the output faces from the sets of their (vertex, edge) adjacencies w/o needing to compute the faces' global topologies.
```
@inproceedings{parover2-vancouver-2019,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G.",
    title = "Computing intersection areas of overlaid 2D meshes",
    booktitle = "{IGS2019} International Geometry Summit Posters' proceedings",
    month = "17--21 June",
    address = "Vancouver, Canada",
    year = "2019",
    publisher = "{Solid Modeling Association}",
    href = "\bibhrefpp{231-parover2-vancouver-2019}{231-parover2-vancouver-2019-poster.pdf}",
    puburl = "\url{https://igs2019.org/IGS2019-POSTER-PROCEEDINGS-LR.pdf}",
    mykey = "recent parallel salles overlay",
    customlinkposter = "https://wrfranklin.org/p/231-parover2-vancouver-2019-poster.pdf",
    customlinkfastforward = "https://wrfranklin.org/p/231-parover2-vancouver-2019-ff.mp4"
}
```

2018

Salles Viana Gomes de Magalhães, W. Randolph Franklin, and Ricardo dos Santos Ferreira. Fast analysis of upstream features on spatial networks (GIS Cup). In Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL '18, 622–625. New York, NY, USA, 2018. ACM. Winner (1st place). doi:https://doi.org/10.1145/3274895.3276474.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

@inproceedings{salles-giscup-2018,
    author = "de Magalhães, Salles Viana Gomes and Franklin, W. Randolph and dos Santos Ferreira, Ricardo",
    title = "Fast Analysis of Upstream Features on Spatial Networks {(GIS Cup)}",
    note = "Winner (1st place)",
    booktitle = "Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems",
    series = "SIGSPATIAL '18",
    year = "2018",
    isbn = "978-1-4503-5889-7",
    location = "Seattle, Washington",
    pages = "622--625",
    numpages = "4",
    acmid = "3276474",
    publisher = "ACM",
    address = "New York, NY, USA",
    keywords = "GISCUP, graph algorithms, parallel programming, spatial networks",
    href = "\bibhrefpt{228-salles-giscup-2018}{228-salles-giscup-2018-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/228-salles-giscup-2018-talk.pdf",
    mykey = "recent salles parallel sallesgiscup2018",
    doi = "https://doi.org/10.1145/3274895.3276474"
}

W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. Data structures for parallel spatial algorithms on large datasets (vision paper). In Proceedings of BigSpatial'18: 7th ACM SIGSPATIAL Workshop on Analytics for Big Geospatial Data. Seattle, USA, 6 Nov 2018.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

This paper describes data structures and algorithms for efficient implementation of GIS operations for large datasets on multicore Intel CPUs and on NVIDA GPUs. Typical operations are boolean combinations of polygons and map overlay. Efficient parallelization prefers simple regular data structures, such as structures of arrays of plain old datatypes. Warps of 32 threads are required to execute the same instruction (or be idle). Ideally, the data used by adjacent threads is adjacent in memory. Minimizing storage is important, as is accessing it in a regular pattern. That disparages pointers, linked lists, and trees. That implies that explicitly representing global topology is bad. If using only local topological formulae is sufficient, then it will be much faster. E.g., for many operations on a 2-D map (aka planar graph), the set of oriented edges suffices. Each edge knows the locations of its endpoints and the ids of its adjacent polygons. Any mass operation, such as area computation or point location, can be implemented as a map-reduce. All these techniques also apply in 3D to CAD/CAM and additive manufacturing. Indeed they are more important there.
```
@inproceedings{par-ds-bigspatial-2018,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "Data Structures for Parallel Spatial Algorithms on Large Datasets (Vision paper)",
    address = "Seattle, {USA}",
    month = "6 Nov",
    booktitle = "Proceedings of {BigSpatial'18}: 7th {ACM SIGSPATIAL} Workshop on Analytics for Big Geospatial Data",
    year = "2018",
    href = "\bibhrefpt{227-par-ds-bigspatial-2018}{227-par-ds-bigspatial-2018-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/227-par-ds-bigspatial-2018-talk.pdf",
    mykey = "recent marcus salles topology parallel"
}
```
W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. Exact fast parallel intersection of large 3-D triangular meshes (extended abstract). In 28th Annual Fall Workshop on Computational Geometry. Queens College, CUNY, New York City, 26–27 Oct 2018.
[abstract▼] [details] [full text] [BibTeX▼]

We present 3D-EPUG-Overlay, a fast, exact, parallel, memory-efficient, algorithm for computing the intersection between two large 3-D triangular meshes with geometric degeneracies. Applications include CAD/CAM, CFD, GIS, and additive manufacturing. 3D-EPUG-Overlay combines 5 separate techniques: multiple precision rational numbers to eliminate roundoff errors during the computations; Simulation of Simplicity to properly handle geometric degeneracies; simple data representations and only local topological information to simplify the correct processing of the data and make the algorithm more parallelizable; a uniform grid to efficiently index the data, and accelerate testing pairs of triangles for intersection or locating points in the mesh; and parallel programming to exploit current hardware. 3D-EPUG-Overlay is up to 101 times faster than LibiGL, and comparable to QuickCSG, a parallel inexact algorithm. 3D-EPUG-Overlay is also more memory efficient. In all test cases 3D-EPUG-Overlay's result matched the reference solution. It is freely available for nonprofit research and education at https://github.com/sallesviana/MeshIntersection . The full version of this paper is being presented at the 2018 International Meshing Roundtable; it is currently online at https://project.inria.fr/imr27/files/2018/09/1035.pdf.
```
@inproceedings{exact-fast-parallel-fwcg-2018,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "Exact fast parallel intersection of large 3-{D} triangular meshes (extended abstract)",
    booktitle = "28th Annual Fall Workshop on Computational Geometry",
    address = "Queens College, {CUNY}, New York City",
    year = "2018",
    month = "26--27 Oct",
    href = "\bibhref{229-exact-fast-parallel-fwcg-2018}",
    mykey = "recent marcus salles overlay parallel topology"
}
```
W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. Exact fast parallel intersection of large 3-D triangular meshes. In 27th International Meshing Roundtable. Alberqueque, New Mexico, 2 Oct 2018.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

We present 3D-EPUG-Overlay, a fast, exact, parallel, memory-efficient, algorithm for computing the intersection between two large 3-D triangular meshes with geometric degeneracies. Applications include CAD/CAM, CFD, GIS, and additive manufacturing. 3D-EPUG-Overlay combines 5 separate techniques: multiple precision rational numbers to eliminate roundoff errors during the computations; Simulation of Simplicity to properly handle geometric degeneracies; simple data representations and only local topological information to simplify the correct processing of the data and make the algorithm more parallelizable; a uniform grid to efficiently index the data, and accelerate testing pairs of triangles for intersection or locating points in the mesh; and parallel programming to exploit current hardware. 3D-EPUG-Overlay is up to 101 times faster than LibiGL, and comparable to QuickCSG, a parallel inexact algorithm. 3D-EPUG-Overlay is also more memory efficient. In all test cases 3D-EPUG-Overlay's result matched the reference solution. It is freely available for nonprofit research and education.
```
@inproceedings{exact-fast-parallel-imr-2018,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "Exact fast parallel intersection of large 3-{D} triangular meshes",
    booktitle = "27th International Meshing Roundtable",
    address = "Alberqueque, New Mexico",
    year = "2018",
    month = "2 Oct",
    href = "\bibhrefpt{222-exact-fast-parallel-imr-2018}{222-exact-fast-parallel-imr-2018-talk.pdf}",
    mykey = "recent marcus salles overlay parallel",
    customlinkslides = "https://wrfranklin.org/p/222-exact-fast-parallel-imr-2018-talk.pdf"
}
```

2017

W. Randolph Franklin and Salles V. G. de Magalhães. Parallel intersection detection in massive sets of cubes. In 27th Fall Workshop on Computational Geometry. Stony Brook University, New York, USA, 3–4 Nov 2017. (talk).
[abstract▼] [details] [slides] [BibTeX▼]

We present ParCube, a very fast parallel algorithm and implementation for finding the pairwise intersections in a set of millions of congruent cubes. This operation is required when computing boolean combinations of meshes or polyhedra in CAD/CAM and additive manufacturing, and in determining close points in a 3D set. ParCube expresses a 3D uniform grid using functional programming concepts in Nvidia Thrust. The underlying HW can be either regular single-threaded C++, an Nvidia GPU with CUDA, or a multicore Intel Xeon with OpenMP or TBB. ParCube can intersect 10M i.i.d. cubes with 6M intersections in 0.32 elapsed seconds, which is 131x faster than CGAL. Even running single threaded on the CPU, ParCube ran this case three times as fast as CGAL. ParCube can also find bipartite intersections without expensive preprocessing.
```
@inproceedings{parcube-fwcg-2017,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G.",
    title = "Parallel intersection detection in massive sets of cubes",
    booktitle = "27th Fall Workshop on Computational Geometry",
    year = "2017",
    month = "3--4 Nov",
    address = "{Stony Brook University, New York, USA}",
    note = "(talk)",
    href = "\bibhrefat{225-parcube-fwcg-2017-abs}{225-parcube-fwcg-2017-talk.pdf}",
    mykey = "salles parcube parallel",
    customlinkslides = "https://wrfranklin.org/p/225-parcube-fwcg-2017-talk.pdf"
}
```
W. Randolph Franklin and Salles V. G. de Magalhães. Parallel intersection detection in massive sets of cubes. In Proceedings of BigSpatial'17: 6th ACM SIGSPATIAL Workshop on Analytics for Big Geospatial Data. Los Angeles Area, CA, USA, 7-10 Nov 2017. doi:https://doi.org/10.1145/3150919.3150921.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

We present ParCube, which finds the pairwise intersections in a set of millions of congruent cubes. This operation is required when computing boolean combinations of meshes or polyhedra in CAD/CAM and additive manufacturing, and in determining close points in a 3D set. ParCube is very compact because it is uses a uniform grid with a functional programming API. ParCube is very fast; even single threaded it usually beats CGAL's elapsed time, sometimes by a factor of 3. Also because it is FP, ParCube parallelizes very well. On an Nvidia GPU, processing 10M cubes to find 6M intersections, it took 0.33 elapsed seconds, beating CGAL by a factor of 131. ParCube is independent of the specific parallel architecture, whether shared memory multicore Intel Xeon using either OpenMP or TBB, or Nvidia GPUs with thousands of cores. We expect the principles used in ParCube to apply to other computational geometry problems. Efficiently finding all bipartite intersections would be an easy extension.
```
@inproceedings{parcube-bigspatial-2017,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G.",
    title = "Parallel intersection detection in massive sets of cubes",
    booktitle = "Proceedings of {BigSpatial'17}: 6th {ACM SIGSPATIAL} Workshop on Analytics for Big Geospatial Data",
    year = "2017",
    month = "7-10 Nov",
    address = "{Los Angeles Area, CA, USA}",
    doi = "https://doi.org/10.1145/3150919.3150921",
    href = "\bibhrefpt{224-parcube-bigspatial-2017}{224-parcube-bigspatial-2017-talk.pdf}",
    mykey = "parcube salles parallel",
    customlinkslides = "https://wrfranklin.org/p/224-parcube-bigspatial-2017-talk.pdf"
}
```
Salles V. G. de Magalhães, W. Randolph Franklin, and Marcus V. A. Andrade. Fast exact parallel 3D mesh intersection algorithm using only orientation predicates. In 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017). Los Angeles Area, CA, USA, 7–10 Nov 2017.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

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.
```
@inproceedings{salles-parallel-mesh-sigspatial-2017,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A.",
    title = "Fast exact parallel {3D} mesh intersection algorithm using only orientation predicates",
    year = "2017",
    month = "7--10 Nov",
    booktitle = "25th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems {(ACM SIGSPATIAL 2017)}",
    address = "{Los Angeles Area, CA, USA}",
    href = "\bibhrefpt{223-salles-parallel-mesh-sigspatial-2017}{223-salles-parallel-mesh-sigspatial-2017-talk.pdf}",
    mykey = "salles marcus parallel",
    customlinkslides = "https://wrfranklin.org/p/223-salles-parallel-mesh-sigspatial-2017-talk.pdf"
}
```
W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. 3D-EPUG-Overlay: intersecting very large 3D triangulations in parallel. In 2017 SIAM conference on industrial and applied geometry. Pittsburgh PA USA, 10–12 July 2017. (talk).
[abstract▼] [details] [slides] [BibTeX▼]

We present 3D-EPUG-Overlay, an algorithm and preliminary implementation for intersecting (aka overlaying) two 3D triangulations. This operation is important in processing large geometry datasets in additive manufacturing. Much of our algorithm is a sequence of map-reduce operations, and so is easily parallelizable. We completely avoid roundoff errors and the associated topological problems by computing with rational numbers. We will handle geometric degeneracies with Simulation of Simplicity (SoS). Our target architecture is an inexpensive workstation. We have a complete 2D implementation, which has overlaid two 2D maps maps, with a total of 54,000,000 vertices and 739,000 faces, in only 322 elapsed seconds (excluding I/O) on a dual 8-core 3.4GHz Intel Xeon workstation. That time is using 16 cores, and is 11x faster than using one core. Our 3D implementation is complete except for SoS. It processes two 3D objects with a total of 6,000,000 face triangles and 3,000,000 tetrahedra in 180 elapsed seconds on 16 cores. The parallel speedup for 16 cores is a factor of 13. The execution time is almost linear in the data size, and could process much larger datasets, perhaps billions of triangles. We anticipate being able to process much larger datasets than competing SW can, and for datasets small enough for others to process, that we will be much faster and more robust on special cases.
```
@inproceedings{x3d-epug-siam-2017,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "{3D-EPUG-Overlay}: Intersecting very large {3D} triangulations in parallel",
    booktitle = "2017 {SIAM} conference on industrial and applied geometry",
    year = "2017",
    month = "10--12 July",
    address = "Pittsburgh PA USA",
    note = "(talk)",
    href = "\bibhrefat{219-3d-epug-siam-2017-abs}{219-3d-epug-siam-2017.pdf}",
    mykey = "overlay parallel marcus salles epug-overlay",
    customlinkslides = "https://wrfranklin.org/p/219-3d-epug-siam-2017.pdf"
}
```
W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. An exact and efficient 3D mesh intersection algorithm using only orientation predicates. In S3PM-2017: International Convention on Shape, Solid, Structure, & Physical Modeling, Shape Modeling International (SMI-2017) Symposium. Berkeley, California, USA, 19–23 June 2017. (poster).
[abstract▼] [details] [poster] [BibTeX▼]

We present an algorithm to compute the intersection of two 3D triangulated meshes. It has applications in CAD and Additive Manufacturing, and was developed to process the largest 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.
```
@inproceedings{mesh-orientation-s3pm-2017,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "An exact and efficient {3D} mesh intersection algorithm using only orientation predicates",
    booktitle = "{S3PM-2017}: International Convention on Shape, Solid, Structure, \\& Physical Modeling, Shape Modeling International {(SMI-2017)} Symposium",
    month = "19--23 June",
    address = "Berkeley, California, USA",
    host = "International Computer Science Institute",
    year = "2017",
    note = "(poster)",
    href = "\bibhrefap{}{220-mesh-orientation-s3pm-2017.pdf}",
    mykey = "parallel marcus salles overlay epug-overlay",
    customlinkposter = "https://wrfranklin.org/p/220-mesh-orientation-s3pm-2017.pdf"
}
```
Salles Viana Gomes de Magalhães. Exact and parallel intersection of 3D triangular meshes. PhD thesis, Rensselaer Polytechnic Institute, Troy, NY, USA, 2017.
[abstract▼] [details] [full text] [BibTeX▼]

This thesis presents an exact parallel algorithm for computing the intersection between two 3D triangular meshes, as used in CAD/CAM (Computer Aided Design/Computer Aided Manufacturing), CFD (Computational Fluid Dynamics), GIS (Geographical Information Science) and additive manufacturing (also known as 3D Printing). Geometric software packages occasionally fail to compute the correct result because of the algorithm implementation complexity (that usually needs to handle several special cases) and of precision problems caused by floating point arithmetic. A failure in an intersection computation algorithm may propagate to any software using the algorithm as a subroutine. As datasets get bigger (and the chances of failure in an inexact algorithm increase), exact algorithms become even more important. While other methods for exactly intersecting meshes exist, their performance makes them non-suitable for applications where the fast processing of big geometric models is important (such as interactive CAD systems). The key to obtain robustness and performance is a combination of 5 separate techniques: • Multiple precision rational numbers, to exactly represent the coordinates of the objects and completely eliminate roundoff errors during the computations. • Simulation of Simplicity, a symbolic perturbation technique, to ensure that all geometric degeneracies (special cases) are properly handled. • Simple data representations and local information, to simplify the correct processing of the data and make the algorithm more parallelizable. • A uniform grid, to efficiently index the data, and accelerate some of the steps of the algorithm such as testing pairs of triangles for intersection or locating points in the mesh. • Parallel programming, to accelerate the intersection process and explore better the ubiquitous parallel computing capability of current hardware. To evaluate our ideas, we have developed and implemented EPUG-Overlay (Exact Parallel Uniform Grid Overlay), an exact and efficient algorithm for overlaying 2D maps. EPUG-Overlay applies all the techniques mentioned above and, as a result, it was not only exact but also very efficient. Indeed, it was able to compute the intersection of a map containing 32 million edges with another map having 21 million edges in 264 elapsed seconds using 16 threads with dual 8-core processors. By comparison, GRASS (a Geographic Information System) took 5, 300 seconds to perform the same computation, partly because it is only single-threaded. We have also developed PinMesh (Point In Mesh), an exact and efficient method for locating points in 3D meshes. The point location problem is an important step we intend to use for computing the intersection of 3D meshes. PinMesh was carefully implemented to always handle point location queries correctly. The use of efficient data structures associated with parallel programming made PinMesh very fast. According to our experiments, PinMesh was up to 27 times faster than the RCT (Relative Closest Triangle) 3D point location algorithm (that was, to the best of our knowledge, the fastest point location algorithm available). Finally, we developed 3D-EPUG-Overlay, an algorithm for exactly computing the intersection of pairs of 3D meshes. 3D-EPUG-Overlay employs all the techniques mentioned above to ensure its correctness and efficiency. Experiments showed that it was up to 101 times faster than the algorithm available in LibiGL (the state of art algorithm for exact mesh intersection) and, also, it had a performance that was comparable to a parallel inexact algorithm that was specifically developed to be very fast. Besides being fast, 3D-EPUG-Overlay was more memory efficient than the other evaluated methods. Furthermore, in all test cases the result obtained by 3D-EPUG-Overlay matched the reference solution. All the software developed for this thesis is freely available for other researchers to use and extend.
```
@phdthesis{salles-phd,
    author = "de Magalh{\\textasciitilde {a}}es, Salles Viana Gomes",
    title = "Exact and parallel intersection of {3D} triangular meshes",
    school = "Rensselaer Polytechnic Institute, Troy, {NY, USA}",
    year = "2017",
    mykey = "salles-thesis theses"
}
```

2016

Maurício Gouvêa Gruppi, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. Using rational numbers and parallel computing to efficiently avoid round-off errors on map simplification. RBC. Revista Brasileira de Cartografia (Online), 68:1221–1230, 2016. online at \url http://www.lsie.unb.br/rbc/index.php/rbc/article/view/1857.
[abstract▼] [details] [full text] [BibTeX▼]

This paper presents EPLSimp, an algorithm for map generalization that avoids the creation of topological inconsistencies. EPLSimp is based on Visvalingam-Whyatt's (VW) algorithm on which least “important” points are removed first. Unlike VW's algorithm, when a point is deleted a verification is performed in order to check if this deletion would create topological inconsistencies. This was done by using arbitrary precision rational numbers to completely avoid errors caused by floating-point arithmetic. EPLSimp was carefully implemented to be efficient, although using rational numbers adds an overhead to the computation. This efficiency was achieved by using a uniform grid for indexing the geometric data and parallel computing to speed up the process. As result, simplified models completely free of topologically inconsistent results and round-off errors due to the use of multiple precision rational numbers. In addition, there was a considerable speedup arising from the use of parallel computing.
```
@article{mauricio-rational-rbc-2016,
    author = "Gruppi, Maurício Gouvêa and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "Using Rational Numbers and Parallel Computing to Efficiently Avoid Round-Off Errors on Map Simplification",
    journal = "RBC. Revista Brasileira de Cartografia (Online)",
    year = "2016",
    volume = "68",
    pages = "1221-1230",
    note = "online at \url{http://www.lsie.unb.br/rbc/index.php/rbc/article/view/1857}",
    href = "\bibhref{221-mauricio-rational-rbc-2016}",
    mykey = "wenlili marcus salles parallel"
}
```
Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, Wenli Li, and Maurício Gouvêa Gruppi. Exact intersection of 3D geometric models. In Geoinfo 2016, XVII Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, November 2016. Instituto Nacional de Pesquisas Espaciais (Brasil).
[abstract▼] [details] [full text] [slides] [BibTeX▼]

This paper presents 3D-EPUG-OVERLAY , an exact and parallel algorithm for computing the intersection of 3D triangulated meshes, a problem with applications in several fields such as GIS and CAD. 3D-EPUG-OVERLAY presents several innovations: it employs exact arithmetic and, thus, the computations are completely exact, which avoids topological impossibilities that are often created by floating point arithmetic. Also, it uses a uniform grid to index the geometric data and was designed to be easily parallelizable. Furthermore, we propose the use of Simulation of Simplicity to effectively ensure that all the special cases are properly handled by the algorithm.
```
@inproceedings{salles-xsect-3d-geoinfo-2016,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli and Gruppi, Maurício Gouvêa",
    title = "Exact intersection of {3D} geometric models",
    booktitle = "Geoinfo 2016, {XVII Brazilian} Symposium on GeoInformatics",
    year = "2016",
    month = "November",
    address = "Campos do Jordão, SP, Brazil",
    puburl = "\url{http://www.geoinfo.info/geoinfo\_series.htm}",
    publisher = "Instituto Nacional de Pesquisas Espaciais (Brasil)",
    mykey = "wenlili marcus salles parallel overlay epug-overlay",
    href = "\bibhrefpt{217-salles-xsect-3d-geoinfo-2016}{217-salles-xsect-3d-geoinfo-2016-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/217-salles-xsect-3d-geoinfo-2016-talk.pdf"
}
```

Wenli Li, W. Randolph Franklin, and Salles V. G. de Magalhães. Computing approximate horizons on a GPU. In 26th Fall Workshop on Computational Geometry. CUNY Graduate Center, New York, USA, 27-28 Oct 2016. (extended abstract).
[abstract▼] [details] [full text] [slides] [BibTeX▼]

@inproceedings{wenli-gpu-horizons-fwcg-2016,
    author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G.",
    title = "Computing approximate horizons on a {GPU}",
    booktitle = "26th Fall Workshop on Computational Geometry",
    year = "2016",
    month = "27-28 Oct",
    address = "{CUNY} Graduate Center, New York, USA",
    note = "(extended abstract)",
    href = "\bibhrefpt{216-wenli-gpu-horizons-fwcg-2016}{216-wenli-gpu-horizons-fwcg-2016-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/216-wenli-gpu-horizons-fwcg-2016-talk.pdf",
    mykey = "visviewshedsiting wenlili salles"
}

Salles Viana Gomes de Magalhães, W. Randolph Franklin, Wenli Li, and Marcus Vinicius Alvim Andrade. An efficient map-reduce algorithm for spatio-temporal analysis using spark (GIS Cup). In 5th GIS-focused algorithm competition, GISCup 2016, co-located with ACM SIGSPATIAL GIS. 2016. Winner (2nd place).
[abstract▼] [details] [full text] [slides] [BibTeX▼]

We present an efficient parallel algorithm for performing spatio-temporal analysis in a Spark cluster. It divides the spatio-temporal cube into partitions and uses these partitions as the elements of the Spark Resilient Distributed Datasets (RDDs). As a result, data presents a better locality and the overheads are smaller than the overheads observed when single cells are used as elements of the RDDs. When used to find hotspots in the NYC Yellowcab data, our algorithm is up to 52 times faster than algorithms using single cells RDDs.
```
@inproceedings{salles-giscup-2016,
    author = "de Magalhães, Salles Viana Gomes and Franklin, W. Randolph and Li, Wenli and Andrade, Marcus Vinicius Alvim",
    title = "An efficient map-reduce algorithm for spatio-temporal analysis using Spark ({GIS Cup})",
    note = "Winner (2nd place)",
    booktitle = "5th {GIS}-focused algorithm competition, {GISCup} 2016, co-located with {ACM SIGSPATIAL GIS}",
    year = "2016",
    href = "\bibhrefpt{215-salles-giscup-2016}{215-salles-giscup-2016-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/215-salles-giscup-2016-talk.pdf",
    mykey = "marcus wenlili salles parallel sallesgiscup2016"
}
```
Wenli Li, W. Randolph Franklin, Salles V. G. de Magalhães, Marcus V. A. Andrade, and David L. Hedin. 3D segmented ODETLAP compression. 2016.
[abstract▼] [details] [full text] [BibTeX▼]

We propose a segmented ODETLAP compression algorithm to increase speed, and show that it is usually better in the maximum absolute error than JP3D for 3D datasets. Overdetermined Laplacian partial differential equations (ODETLAP) is a spatial approximation and data compression method. We use the CUSP library to accelerate ODETLAP approximation and the speedup is about 7 times on a GPU over a CPU core. Segmented ODETLAP compression is faster and uses less memory than unsegmented ODETLAP compression. We use the algorithm to compress several atmospheric datasets and an MRI dataset. For evaluation, we also compress the datasets using JPEG 2000 Part 10 JP3D. The results show that the compressed size of the algorithm is about 60\% that of JP3D for the same maximum absolute error.
```
@misc{wenli-odetlap-2016,
    author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Hedin, David L.",
    title = "{3D} Segmented {ODETLAP} Compression",
    booktitle = "(unpublished)",
    year = "2016",
    href = "\bibhref{212-wenli-odetlap-2016}",
    mykey = "wenlili marcus salles odetlap"
}
```
Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. PinMesh – Fast and exact 3D point location queries using a uniform grid. Computer & Graphics Journal, special issue on Shape Modeling International 2016, 58:1–11, August 2016. (online 17 May). Awarded a reproducibility stamp, \url http://www.reproducibilitystamp.com/. URL: http://www.sciencedirect.com/science/article/pii/S0097849316300607, doi:https://doi.org/10.1016/j.cag.2016.05.017.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

This paper presents PinMesh, a very fast algorithm with implementation to preprocess a polyhedral mesh, also known as a multimaterial mesh, in order to perform 3D point location queries. PinMesh combines several innovative components to efficiently handle the largest available meshes. Because of a 2-level uniform grid, the expected preprocessing time is linear in the input size, and the code parallelizes well on a shared memory machine. Querying time is almost independent of the dataset size. PinMesh uses exact arithmetic with rational numbers to prevent roundoff errors, and symbolic perturbation with Simulation of Simplicity (SoS) to handle geometric degeneracies or special cases. PinMesh is intended to be a subroutine in more complex algorithms. It can preprocess a dataset and perform 1 million queries up to 27 times faster than RCT (Relative Closest Triangle), the current fastest algorithm. Preprocessing a sample dataset with 50 million triangles took only 14 elapsed seconds on a 16-core Xeon processor. The mean query time was 0.6 microseconds.
```
@article{salles-pinmesh-smi-2016,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "{PinMesh} -- {Fast} and exact {3D} point location queries using a uniform grid",
    journal = "{Computer \\& Graphics Journal}, special issue on {Shape Modeling International} 2016",
    year = "2016",
    volume = "58",
    pages = "1--11",
    month = "August",
    doi = "https://doi.org/10.1016/j.cag.2016.05.017",
    url = "http://www.sciencedirect.com/science/article/pii/S0097849316300607",
    href = "\bibhrefpt{209-salles-smi-pinmesh-2016}{209-salles-smi-pinmesh-2016-talk.pptx}",
    note = "(online 17 May). Awarded a reproducibility stamp, \url{http://www.reproducibilitystamp.com/}.",
    customlinkslides = "https://wrfranklin.org/p/209-salles-smi-pinmesh-2016-talk.pptx",
    mykey = "salles marcus wenlili pinmesh parallel sallespinmeshsmi2016"
}
```
Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. de Magalhães, and W. Randolph Franklin. An efficient external memory algorithm for terrain viewshed computation. ACM Trans. on Spatial Algorithms and Systems, 2016. doi:https://doi.org/10.1145/2903206.
[abstract▼] [details] [full text] [BibTeX▼]

This paper presents TiledVS, a fast external algorithm and implementation for computing viewsheds. TiledVS is intended for terrains that are too large for internal memory, even over 100 000 × 100 000 points. It subdivides the terrain into tiles that are stored compressed on disk and then paged into memory with a custom cache data structure and LRU algorithm. If there is sufficient available memory to store a whole row of tiles, which is easy, then this specialized data management is faster than relying on the operating system's virtual memory management. Applications of viewshed computation include siting radio transmitters, surveillance, and visual environmental impact measurement. TiledVS runs a rotating line of sight from the observer to points on the region boundary. For each boundary point, it computes the visibility of all the terrain points close to the line of sight. The running time is linear in the number of points. No terrain tile is read more than twice. TiledVS is very fast, for instance, processing a 104000 x 104000 terrain on a modest computer with only 512MB of RAM took only 1 2 1 hours. On large datasets, TiledVS was several times faster than competing algorithms such as the ones included in GRASS. The source code of TiledVS is freely available for nonprofit researchers to study, use, and extend. A preliminary version of this algorithm appeared in a 4-page ACM SIGSPATIAL GIS 2012 conference paper “More efficient terrain viewshed computation on massive datasets using external memory”. This more detailed version adds the fast lossless compression stage that reduces the time by 30\% to 40\%, and many more experiments and comparisons.
```
@article{chaulio-tiledvs-tsas-2016,
    author = "Ferreira, Chaulio R. and Andrade, Marcus V. A. and de Magalhães, Salles V. G. and Franklin, W. Randolph",
    title = "An efficient external memory algorithm for terrain viewshed computation",
    href = "\bibhref{197-chaulio-tiledvs-tsas-2016}",
    journal = "{ACM} Trans. on Spatial Algorithms and Systems",
    year = "2016",
    volume = "2",
    number = "2",
    doi = "https://doi.org/10.1145/2903206",
    mykey = "salles marcus visviewshedsiting tiledvs visibility"
}
```

W. Randolph Franklin and Salles Viana Gomes de Magalhães. Local topology and parallel overlaying large planar graphs. 15 Feb 2016. Talk at Georgia Tech, School of Interactive Computing. Also given at IBM Haifa, Microsoft Haifa, Ben Gurion U, and Tel Aviv U in Dec 2015.
[details] [slides] [BibTeX▼]

@misc{local-talk-gatech-2016,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes",
    title = "Local topology and parallel overlaying large planar graphs",
    note = "Talk at Georgia Tech, School of Interactive Computing. Also given at IBM Haifa, Microsoft Haifa, Ben Gurion U, and Tel Aviv U in Dec 2015",
    month = "15 Feb",
    year = "2016",
    href = "\bibhreft{208-local-talk-gatech-2016.pdf}",
    customlinkslides = "https://wrfranklin.org/p/208-local-talk-gatech-2016.pdf",
    mykey = "salles overlay topology parallel"
}

2015

Mauricio G. Gruppi, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. An efficient and topologically correct map generalization heuristic. In Proceedings of the 17th International Conference on Enterprise Information Systems (ICEIS), 516–525, paper 236. 2015. URL: http://www.iceis.org/Abstracts/2015/ICEIS_2015_Abstracts.htm, doi:https://doi.org/10.5220/0005398105160525.
[abstract▼] [details] [full text] [BibTeX▼]

We present TopoVW, an efficient heuristic for map simplification that 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. This process is important for maintaining clarity of cartographic data, avoiding situations such as high density of map features, inappropriate intersections. In practice, high density of features may be represented by cities condensed into a small space on the map, inappropriate intersections may produce intersections between roads, rivers, and buildings. TopoVW is a strategy based on the Visvalingam-Whyatt algorithm to create simplified geometries with shapes similar to the original map, preserving topological consistency between features in the output. It uses a point ranking strategy, in which line points are ranked by their effective area, a metric that determines the impact a point will cause to the geometry if removed from the line. Points with inferior effective area are eliminated from the original line. The method was able to process a map with 4 million line points and 10 million control points in less than 2 minutes on a Intel Core 2 Duo processor.
```
@inproceedings{mauricio-iceis-2015,
    author = "Gruppi, Mauricio G. and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "An Efficient and Topologically Correct Map Generalization Heuristic",
    booktitle = "Proceedings of the 17th International Conference on Enterprise Information Systems (ICEIS)",
    year = "2015",
    pages = "516-525, paper 236",
    doi = "https://doi.org/10.5220/0005398105160525",
    isbn = "978-989-758-096-3",
    mykey = "wenlili marcus salles",
    href = "\bibhref{214-mauricio-iceis-2015}",
    url = "http://www.iceis.org/Abstracts/2015/ICEIS\_2015\_Abstracts.htm"
}
```

W. Randolph Franklin and Salles Viana Gomes de Magalhães. Global properties from local topology. 10 Nov 2015. Talk at UC Santa Barbara, Center for Spatial Studies.
[details] [slides] [BibTeX▼]

@misc{local-talk-ucsb-2015,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes",
    title = "Global properties from local topology",
    note = "Talk at {UC Santa Barbara}, Center for Spatial Studies",
    month = "10 Nov",
    year = "2015",
    mykey = "salles topology",
    href = "\bibhreft{207-local-talk-ucsb-2015.pdf}",
    customlinkslides = "https://wrfranklin.org/p/207-local-talk-ucsb-2015.pdf"
}

Maurício Gouvêa Gruppi, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. Using rational numbers and parallel computing to efficiently avoid round-off errors on map simplification. In Geoinfo 2015, XVI Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, 29 Nov – 2 Dec 2015.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

This paper presents EPLSimp, an algorithm for map generalization that avoids the creation of topological inconsistencies. EPLSimp is based on Visvalingam-Whyatt's (VW) algorithm on which least “important” points are removed first. Unlike VW's algorithm, when a point is deleted a verification is performed in order to check if this deletion would create topological inconsistencies. This was done by using arbitrary precision rational numbers to completely avoid errors caused by floating-point arithmetic. EPLSimp was carefully implemented to be efficient, although using rational numbers adds an overhead to the computation. This efficiency was achieved by using a uniform grid for indexing the geometric data and parallel computing to speedup the process.
```
@inproceedings{mauricio-rational-geoinfo-2015,
    author = "Gruppi, Maurício Gouvêa and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "Using Rational Numbers and Parallel Computing to Efficiently Avoid Round-Off Errors on Map Simplification",
    booktitle = "Geoinfo 2015, {XVI Brazilian} Symposium on GeoInformatics",
    year = "2015",
    month = "29 Nov -- 2 Dec",
    address = "Campos do Jordão, SP, Brazil",
    mykey = "marcus wenlili salles visviewshedsiting",
    href = "\bibhrefpt{198-mauricio-rational-geoinfo-2015}{198-mauricio-rational-geoinfo-2015-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/198-mauricio-rational-geoinfo-2015-talk.pdf"
}
```

Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. Fast path planning under polygonal obstacle constraints. In 4th GIS-focused algorithm competition, GISCUP 2015, co-located with ACM SIGSPATIAL GIS. Bellevue WA USA, 4 Nov 2015. Winner (2nd place).
[details] [full text] [BibTeX▼]

@inproceedings{salles-giscup-2015,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "Fast path planning under polygonal obstacle constraints",
    booktitle = "4th {GIS}-focused algorithm competition, {GISCUP} 2015, co-located with {ACM SIGSPATIAL GIS}",
    year = "2015",
    month = "4 Nov",
    address = "Bellevue WA USA",
    note = "Winner (2nd place)",
    mykey = "wenlili marcus salles pathplan sallesgiscup2015 uplan",
    href = "\bibhref{203-salles-giscup-2015}"
}

Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li. Fast exact parallel map overlay using a two-level uniform grid. In 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial). Bellevue WA USA, 3 Nov 2015. doi:https://doi.org/10.1145/2835185.2835188.
[abstract▼] [details] [full text] [BibTeX▼]

We present EPUG-Overlay (Exact Parallel Uniform Grid Overlay), an algorithm to overlay two maps that is fast and parallel, has no roundoff errors, and is freely available. EPUG-Overlay combines several novel aspects. It represents coordinates with rational numbers, thereby ensuring exact computations with no roundoff errors and the ensuing sliver problems and topological impossibilities. For efficiency, EPUG-Overlay performs the map overlay in parallel, thereby utilizing the ubiquitous multicore architecture. Our application goes beyond merely using existing packages, which are inefficient when used in parallel on large problems. Indeed, overlaying two maps with 53,000,000 edges and 730,000 faces took only 322 elapsed seconds (plus 116 seconds for I/O) on a dual 8-core 3.1 GHz Intel Xeon E5-2687 workstation. In contrast, GRASS, executing sequentially and generating roundoff errors, takes 5300 seconds. The overlay operation combines two input maps (planar graphs) containing faces (polygons) separated by polyline edges (chains), into a new map, each of whose faces is the intersection of one face from each input map. Floating point roundoff errors can cause an edge intersection to be missed or the computed intersection point be in a wrong face, leading to a topological inconsistency. Thus, a program might fail to compute a valid output map at all, using any amount of time. This gets worse when the inputs are bigger or have slivers. Heuristics can ameliorate this problem, but only to an extent. By representing each coordinate as a vulgar fraction, with multiprecision numerator and denominator, the computation is exact. EPUG-Overlay also executes various useful subproblems very quickly, such as locating a set of points in a planar graph and finding all the intersections among a large set of small edges. EPUG-Overlay is built on our earlier sequential floating-point algorithm that found the areas of the overlay polygons, without finding the polygons themselves.
```
@inproceedings{salles-overlay-bigspatial-2015,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
    title = "Fast exact parallel map overlay using a two-level uniform grid",
    booktitle = "4th {ACM SIGSPATIAL} International Workshop on Analytics for Big Geospatial Data (BigSpatial)",
    year = "2015",
    month = "3 Nov",
    address = "Bellevue WA USA",
    href = "\bibhref{196-salles-overlay-bigspatial-2015}",
    doi = "https://doi.org/10.1145/2835185.2835188",
    mykey = "wenlili marcus salles overlay parallel"
}
```

Wenli Li, W. Randolph Franklin, and Salles V. G. de Magalhães. Segmented ODETLAP compression. In 25th Fall Workshop on Computational Geometry. U. Buffalo, New York, USA, 23-24 Oct 2015. (extended abstract).
[details] [full text] [BibTeX▼]

@inproceedings{wenli-segment-fwcg-2015,
    author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G.",
    title = "Segmented {ODETLAP} Compression",
    booktitle = "25th Fall Workshop on Computational Geometry",
    year = "2015",
    month = "23-24 Oct",
    address = "U. Buffalo, New York, USA",
    note = "(extended abstract)",
    mykey = "wenlili salles odetlap",
    href = "\bibhref{202-wenli-segment-fwcg-2015}"
}

Salles V. G. de Magalhães, W. Randolph Franklin, Marcus V. A. Andrade, and Wenli Li. An efficient algorithm for computing the exact overlay of triangulations. In 25th Fall Workshop on Computational Geometry. U. Buffalo, New York, USA, 23-24 Oct 2015. (extended abstract).
[details] [full text] [BibTeX▼]

@inproceedings{salles-overlay-fwcg-2015,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A. and Li, Wenli",
    title = "An efficient algorithm for computing the exact overlay of triangulations",
    booktitle = "25th Fall Workshop on Computational Geometry",
    year = "2015",
    month = "23-24 Oct",
    address = "U. Buffalo, New York, USA",
    note = "(extended abstract)",
    mykey = "wenlili marcus salles overlay",
    href = "\bibhref{201-salles-overlay-fwcg-2015}"
}

W. Randolph Franklin, Marcus Andrade, Wenli Li, and Salles de Magalhães. Changing problems, databases, and tools in spatial search. 24 Aug 2015. Talk at U. Zürich, Dept of Geography.
[details] [slides] [BibTeX▼]

@misc{changing-talk-zurich-2015,
    author = "Franklin, W. Randolph and Andrade, Marcus and Li, Wenli and de Magalhães, Salles",
    title = "Changing problems, databases, and tools in spatial search",
    note = "Talk at {U. Zürich}, {Dept} of {Geography}",
    month = "24 Aug",
    year = "2015",
    href = "\bibhreft{204-changing-talk-zurich-2015.pdf}",
    customlinkslides = "https://wrfranklin.org/p/204-changing-talk-zurich-2015.pdf",
    mykey = "wenlili marcus salles parallel"
}

Marcus Andrade, Salles de Magalhães, W. Randolph Franklin, and Wenli Li. Research topics in GIS. Talk at CCNY, 15 April 2015.
[details] [slides] [BibTeX▼]

@misc{salles-ccny-2015,
    author = "Andrade, Marcus and de Magalhães, Salles and Franklin, W. Randolph and Li, Wenli",
    title = "Research topics in {GIS}",
    howpublished = "Talk at CCNY",
    month = "15 April",
    year = "2015",
    href = "\bibhreft{194-salles-ccny-2015.pdf}",
    customlinkslides = "https://wrfranklin.org/p/194-salles-ccny-2015.pdf",
    mykey = "marcus wenlili salles parallel"
}

Wenli Li, W. Randolph Franklin, Marcus Andrade, and Salles de Magalhães. Research summary: siting and ODETLAP. Talk at CCNY, 15 April 2015.
[details] [slides] [BibTeX▼]

@misc{wenli-ccny-2015,
    author = "Li, Wenli and Franklin, W. Randolph and Andrade, Marcus and de Magalhães, Salles",
    title = "Research Summary: Siting and {ODETLAP}",
    howpublished = "Talk at CCNY",
    month = "15 April",
    year = "2015",
    mykey = "wenlili marcus salles odetlap",
    customlinkslides = "https://wrfranklin.org/p/193-wenli-ccny-2015.pdf",
    href = "\bibhreft{193-wenli-ccny-2015.pdf}"
}

Thiago L. Gomes, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. Efficiently computing the drainage network on massive terrains with an external memory flooding process. Geoinformatica, April 2015. \url http://link.springer.com/article/10.1007/s10707-015-0225-y. doi:https://doi.org/10.1007/s10707-015-0225-y.
[details] [full text] [BibTeX▼]

@article{gomes-emflow-2015,
    author = "Gomes, Thiago L. and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
    title = "Efficiently computing the drainage network on massive terrains with an external memory flooding process",
    href = "\bibhref{163-gomes-emflow-2015}",
    journal = "Geoinformatica",
    doi = "https://doi.org/10.1007/s10707-015-0225-y",
    note = "\url{http://link.springer.com/article/10.1007/s10707-015-0225-y}",
    mykey = "marcus salles hydro emflow",
    month = "April",
    year = "2015"
}

2014

Salles V. G. de Magalhães, W. Randolph Franklin, Wenli Li, and Marcus V. A. Andrade. Fast map generalization heuristic with a uniform grid. In 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2014). Dallas, Texas, USA, 4–7 Nov 2014.
[details] [full text] [poster] [slides] [BibTeX▼]

@inproceedings{giscup-2014,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Li, Wenli and Andrade, Marcus V. A.",
    title = "Fast map generalization heuristic with a uniform grid",
    booktitle = "22nd {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems {(ACM SIGSPATIAL 2014)}",
    year = "2014",
    month = "4--7 Nov",
    address = "Dallas, Texas, USA",
    href = "\bibhrefptp{185-acmgis2014-cup}{185-acmgis2014-cup-talk.ppt}{185-acmgis2014-cup-poster.pdf}",
    customlinkposter = "https://wrfranklin.org/p/185-acmgis2014-cup-poster.pdf",
    customlinkslides = "https://wrfranklin.org/p/185-acmgis2014-cup-talk.ppt",
    mykey = "wenlili marcus salles gridgen"
}

Wenli Li, W. Randolph Franklin, Daniel N. Benedetti, and Salles V. G. de Magalhães. Parallel multiple observer siting on terrain. In 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2014). Dallas, Texas, USA, 4–7 Nov 2014.
[abstract▼] [details] [full text] [poster] [BibTeX▼]

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.
```
@inproceedings{li-acmgis-2014,
    author = "Li, Wenli and Franklin, W. Randolph and Benedetti, Daniel N. and de Magalhães, Salles V. G.",
    title = "Parallel Multiple Observer Siting on Terrain",
    booktitle = "22nd {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems {(ACM SIGSPATIAL 2014)}",
    year = "2014",
    month = "4--7 Nov",
    href = "\bibhrefpp{182-acmgis2014-par-siting}{182-acmgis2014-par-siting-poster.pdf}",
    address = "Dallas, Texas, USA",
    customlinkposter = "https://wrfranklin.org/p/182-acmgis2014-par-siting-poster.pdf",
    mykey = "benedetti salles wenlili visviewshedsiting gpusiting parallelsiting parallel"
}
```
Guilherme Pena, Salles de Magalhães, Marcus Andrade, Randolph Franklin, Chaulio Ferreira, Wenli Li, and Daniel Benedetti. An efficient GPU multiple-observer siting method based on sparse-matrix multiplication. In 3rd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial) 2014. Dallas TX USA, 4 Nov 2014.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

This paper proposes an efficient parallel heuristic for siting observers on raster terrains. More specifically, the goal is to choose the smallest set of points on a terrain such that observers located in these points are able to visualize at least a given percentage of the terrain. This problem is NP-Hard and has several applications such as determining the best places to position (site) communication or monitoring towers on a terrain. Since siting observers is a massive operation, its solution requires a huge amount of processing time even to obtain an approximate solution using a heuristic. This is still more evident when processing high resolution terrains that have become available due to modern data acquiring technologies such as LIDAR and IFSAR. Our new implementation uses dynamic programming and CUDA to accelerate the swap local search heuristic, which was proposed in previous works. Also, to efficiently use the parallel computing resources of GPUs, we adapted some techniques previously developed for sparse-dense matrix multiplication. We compared this new method with previous parallel implementations and the new method is much more efficient than the previous ones. It can process much larger terrains (the older methods are restrictive about terrain size) and it is faster.
```
@inproceedings{bigspatial-2014,
    author = "Pena, Guilherme and de Magalhães, Salles and Andrade, Marcus and Franklin, Randolph and Ferreira, Chaulio and Li, Wenli and Benedetti, Daniel",
    title = "An efficient {GPU} multiple-observer siting method based on sparse-matrix multiplication",
    booktitle = "3rd {ACM SIGSPATIAL} International Workshop on Analytics for Big Geospatial Data (BigSpatial) 2014",
    year = "2014",
    month = "4 Nov",
    address = "Dallas TX USA",
    href = "\bibhrefpt{191-bigspatial-sparse-siting-2014}{191-bigspatial-sparse-siting-2014-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/191-bigspatial-sparse-siting-2014-talk.pdf",
    mykey = "visviewshedsiting benedetti marcus wenlili salles parallel"
}
```

Salles V. G. de Magalhães, W. Randolph Franklin, Marcus V. A. Andrade, and Wenli Li. An efficient map generalization heuristic based on the Visvalingam–Whyatt algorithm. In 24th Fall Workshop on Computational Geometry. U. Connecticut, Storrs CT, USA, 31 Oct – 1 Nov 2014. (extended abstract).
[details] [full text] [slides] [BibTeX▼]

@inproceedings{salles-fwcg-2014,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A. and Li, Wenli",
    title = "An efficient map generalization heuristic based on the {V}isvalingam--{Whyatt} algorithm",
    booktitle = "24th Fall Workshop on Computational Geometry",
    year = "2014",
    month = "31 Oct -- 1 Nov",
    address = "U. Connecticut, Storrs CT, USA",
    note = "(extended abstract)",
    mykey = "wenlili marcus salles",
    customlinkslides = "https://wrfranklin.org/p/188-fwcg2014-salles-mapgen-talk.pdf",
    href = "\bibhrefpt{188-fwcg2014-salles-mapgen}{188-fwcg2014-salles-mapgen-talk.pdf}"
}

Wenli Li, W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. Restricted bathymetric tracklines interpolation. In 24th Fall Workshop on Computational Geometry. U. Connecticut, Storrs CT, USA, 31 Oct – 1 Nov 2014. (extended abstract).
[abstract▼] [details] [full text] [slides] [BibTeX▼]

In this paper, we propose a method to interpolate a small bathymetry with long and thin sand bars as distinctive features. Underwater terrain, or bathymetry, is measured by a single beam or multibeam echosounder attached under a boat. Measurement points are distributed along the a track of the boat and their positions and values constitute a trackline. Although full coverage is possible in multibeam surveys, tracklines are often sparse and thin, especially in single beam surveys, and it is expected to interpolate the bathymetry from tracklines. There are dozens of existing spatial interpolation methods with their strengths and weaknesses, and some are more widely used than others. One of the methods, overdetermined laplacian partial differentiation equations (ODETLAP), has been successfully used in bathymetry data interpolation and shown to be better than some of the popular methods. However, it is more suited for large-scale bathymetry without significant linear or continuous features.
```
@inproceedings{li-fwcg-2014,
    author = "Li, Wenli and Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "Restricted Bathymetric Tracklines Interpolation",
    booktitle = "24th Fall Workshop on Computational Geometry",
    year = "2014",
    month = "31 Oct -- 1 Nov",
    address = "U. Connecticut, Storrs CT, USA",
    note = "(extended abstract)",
    mykey = "marcus wenlili salles bathy",
    customlinkslides = "https://wrfranklin.org/p/187-fwcg2014-li-bathy-talk.pdf",
    href = "\bibhrefpt{187-fwcg2014-li-bathy}{187-fwcg2014-li-bathy-talk.pdf}"
}
```

Salles V. G. de Magalhães and W. Randolph Franklin. Exactly computing map overlays using rational numbers. In Autocarto 2014. Pittsburgh PA, 5–7 Oct 2014. Cartography and Geographic Information Society. (abstract only).
[details] [full text] [slides] [BibTeX▼]

@inproceedings{autocarto-ratover-2014,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph",
    title = "Exactly computing map overlays using rational numbers",
    month = "5--7 Oct",
    year = "2014",
    booktitle = "Autocarto 2014",
    organization = "Cartography and Geographic Information Society",
    address = "Pittsburgh PA",
    note = "(abstract only)",
    customlinkslides = "https://wrfranklin.org/p/178-autocarto-ratover-2014-talk.pdf",
    href = "\bibhrefpt{178-autocarto-ratover-2014}{178-autocarto-ratover-2014-talk.pdf}",
    mykey = "salles overlay"
}

Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. de Magalhães, W. R. Franklin, and Guilherme C. Pena. A parallel algorithm for viewshed computation on grid terrains. Journal of information and data management, 2014. invited.
[abstract▼] [details] [full text] [BibTeX▼]

Viewshed (or visibility map) computation is an important component in many GIScience applications and, as nowadays there are huge volume of terrain data available at high resolutions, it is important to develop efficient algorithms to process these data. Since the main improvements on modern processors come from multi-core architectures, parallel programming provides a promising means for developing faster algorithms. In this paper, we describe a new parallel algorithm based on the model proposed by Van Kreveld. Our algorithm uses the shared memory model, which is relatively cheap and supported by most current processors. Experiments have shown that, with 16 parallel cores,was up to 12 times faster than the serial implementation, and up to 3.9 times using four parallel cores, which isalmost optimal speedup.
```
@article{chaulio-jidm-2014,
    author = "Ferreira, Chaulio R. and Andrade, Marcus V. A. and de Magalhães, Salles V. G. and Franklin, W. R. and Pena, Guilherme C.",
    title = "A parallel algorithm for viewshed computation on grid terrains",
    journal = "Journal of information and data management",
    year = "2014",
    volume = "5",
    number = "1",
    note = "invited",
    href = "\bibhref{180-jidm2014-chaulio-parallel-viewshed}",
    mykey = "visviewshedsiting marcus salles parallel"
}
```

Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. A linear time algorithm to compute the drainage network on grid terrains. J. Hydroinformatics, 16(6):1227–1234, 2014. Update of the winner of the Best Paper Award (2nd place) at AGILE 2012. doi:https://doi.org/10.2166/hydro.2013.068.
[details] [full text] [BibTeX▼]

@article{salles-hydroinformatics-2014,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
    title = "A linear time algorithm to compute the drainage network on grid terrains",
    journal = "J. Hydroinformatics",
    year = "2014",
    volume = "16",
    number = "6",
    pages = "1227--1234",
    href = "\bibhref{166-hydroinformatics-maghalaes-rwflood}",
    doi = "https://doi.org/10.2166/hydro.2013.068",
    note = "Update of the winner of the Best Paper Award (2nd place) at AGILE 2012",
    mykey = "marcus salles rwflood hydro sallesagile2012"
}

Guilherme C. Pena, Marcus V.A. Andrade, Salles V.G. de Magalhães, W. R. Franklin, and Chaulio R. Ferreira. An improved parallel algorithm using GPU for siting observers on terrain. In 16th International Conference on Enterprise Information Systems (ICEIS 2014), 367–375. Lisbon, 27–30 April 2014. doi:https://doi.org/10.5220/0004884303670375.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

This paper presents an efficient method to determine a set of observers (that is, where to site them) such that a given percentage of a terrain is visually covered. Our method extends the method proposed in (Franklin, 2002) including a local search heuristic efficiently implemented using dynamic programming and GPU parallel programming. This local search strategy allows to achieve a higher coverage using the same number of observers as the original method and thus it is possible to obtain a given coverage using a smaller number of observers. It can be an important improvement since an observer can represent an expensive facility such as a telecommunication tower. The proposed method performance was compared with that of other methods and the tests showed that it can be more than 1200 times faster than the sequential implementation (with no use of dynamic programming and no GPU parallel programmming) and, also, more than 20 times faster than a previous parallel method presented in (de Magalhaes et al., 2011).
```
@inproceedings{iceis-2014,
    author = "Pena, Guilherme C. and Andrade, Marcus V.A. and de Magalhães, Salles V.G. and Franklin, W. R. and Ferreira, Chaulio R.",
    title = "An Improved Parallel Algorithm using {GPU} for Siting Observers on Terrain",
    booktitle = "16th International Conference on Enterprise Information Systems ({ICEIS} 2014)",
    year = "2014",
    month = "27--30 April",
    address = "Lisbon",
    pages = "367--375",
    doi = "https://doi.org/10.5220/0004884303670375",
    href = "\bibhrefpt{177-ICEIS2014-pena-site-gpu}{177-ICEIS2014-pena-site-gpu-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/177-ICEIS2014-pena-site-gpu-talk.pdf",
    mykey = "visviewshedsiting gpusiting marcus salles parallel"
}
```

2013

Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. de Magalhães, W. R. Franklin, and Guilherme C. Pena. A parallel sweep line algorithm for visibility computation. In Geoinfo 2013, XIV Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, 24–27 Nov 2013. Winner of best paper award, \url http://www.geoinfo.info/geoinfo2013/index.php.
[abstract▼] [details] [full text] [BibTeX▼]

This paper describes a new parallel raster terrain visibility (or viewshed) algorithm, based on the sweep-line model of [Van Kreveld 1996]. Computing the terrain visible from a given observer is required for many GIS applications, with applications ranging from radio tower siting to aesthetics. Processing the newly available higher resolution terrain data requires faster architectures and algorithms. Since the main improvements on modern processors come from multi-core architectures, parallel programming provides a promising means for developing faster algorithms. Our algorithm uses the economical and widely available shared memory model with OpenMP. Experimentally, our parallel speedup is almost linear. On 16 parallel processors, our algorithm is up to 12 times faster than the serial implementation.
```
@inproceedings{chaulio-geoinfo-2013,
    author = "Ferreira, Chaulio R. and Andrade, Marcus V. A. and de Magalhães, Salles V. G. and Franklin, W. R. and Pena, Guilherme C.",
    title = "A Parallel Sweep Line Algorithm for Visibility Computation",
    booktitle = "Geoinfo 2013, {XIV Brazilian} Symposium on GeoInformatics",
    year = "2013",
    month = "24--27 Nov",
    address = "Campos do Jordão, SP, Brazil",
    href = "\bibhref{174-geoinfo2013-chaulio-sweep}",
    note = "Winner of best paper award, \url{http://www.geoinfo.info/geoinfo2013/index.php}",
    mykey = "marcus salles visviewshedsiting parallel chauliogeoinfo2013"
}
```

2012

Thiago L. Gomes, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. Computing the drainage network on huge grid terrains. In 1st ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial-2012). Redondo Beach, CA, 6 Nov 2012.
[details] [full text] [slides] [BibTeX▼]

@inproceedings{gomes-acmgis-2012,
    author = "Gomes, Thiago L. and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
    title = "Computing the drainage network on huge grid terrains",
    address = "Redondo Beach, CA",
    month = "6 Nov",
    customlinkslides = "https://wrfranklin.org/p/162-bigspatial2012-drainage-talk.pdf",
    href = "\bibhrefpt{162-bigspatial2012-drainage}{162-bigspatial2012-drainage-talk.pdf}",
    booktitle = "1st {ACM SIGSPATIAL} International Workshop on Analytics for Big Geospatial Data {(BigSpatial-2012)}",
    mykey = "marcus salles hydro emflow",
    year = "2012"
}

Chaulio R. Ferreira, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and André M. Pompermayer. More efficient terrain viewshed computation on massive datasets using external memory. In 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2012). Redondo Beach, CA, 6–9 Nov 2012.
[abstract▼] [details] [full text] [poster] [BibTeX▼]

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. The viewshed is that region of the terrain that is visible by a fixed observer, who may be on or above the terrain. Its applications range from visual nuisance abatement to radio transmitter siting and surveillance.
```
@inproceedings{ferreira-acmgis-2012,
    author = "Ferreira, Chaulio R. and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pompermayer, André M.",
    title = "More efficient terrain viewshed computation on massive datasets using external memory",
    booktitle = "20th {ACM} {SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM SIGSPATIAL GIS} 2012)",
    year = "2012",
    address = "Redondo Beach, CA",
    month = "6--9 Nov",
    href = "\bibhrefpp{159-acmgis2012-viewshed}{159-acmgis2012-viewshed-poster.pdf}",
    customlinkposter = "https://wrfranklin.org/p/159-acmgis2012-viewshed-poster.pdf",
    mykey = "visviewshedsiting marcus salles"
}
```

Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. A new method for computing the drainage network based on raising the level of an ocean surrounding the terrain. In Jérome Gensel, Didier Josselin, and Danny Vandenbroucke, editors, Bridging the Geographic Information Sciences: International AGILE'2012 Conference, pages 391–407. Springer, Avignon (France), 24–27 April 2012. URL: http://agile2012.imag.fr/.
[details] [full text] [slides] [BibTeX▼]

@incollection{salles-agile-2012,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.",
    editor = "Gensel, Jérome and Josselin, Didier and Vandenbroucke, Danny",
    title = "A new method for computing the drainage network based on raising the level of an ocean surrounding the terrain",
    booktitle = "Bridging the Geographic Information Sciences: International {AGILE'2012} Conference",
    publisher = "Springer",
    pages = "391--407",
    isbn = "978-3-642-29062-6",
    year = "2012",
    address = "Avignon (France)",
    month = "24--27 April",
    note = "Winner of the Best Paper Award (2nd place)",
    url = "http://agile2012.imag.fr/",
    customlinkslides = "https://wrfranklin.org/p/151-agile2012-rwflood-talk.pdf",
    href = "\bibhrefpt{151-agile2012-rwflood}{151-agile2012-rwflood-talk.pdf}",
    mykey = "salles marcus hydro rwflood sallesagile2012"
}

2011

Salles V. G. de Magalhães, Marcus V. A. Andrade, and W. Randolph Franklin. Multiple observer siting in huge terrains stored in external memory. International Journal of Computer Information Systems and Industrial Management (IJCISIM), 2011.
[abstract▼] [details] [full text] [BibTeX▼]

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.
```
@article{magalhaes-ijcisim-2011,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph",
    title = "Multiple Observer Siting in Huge Terrains Stored in External Memory",
    journal = "International Journal of Computer Information Systems and Industrial Management (IJCISIM)",
    year = "2011",
    volume = "3",
    issn = "2150-7988",
    href = "\bibhref{148-ijcisim11-emsite-magalhaes}",
    mykey = "visviewshedsiting marcus salles"
}
```

2010

Salles V. G. de Magalhães, Marcus V. A. Andrade, and W. Randolph Franklin. An optimization heuristic for siting observers in huge terrains stored in external memory. In 10th International Conference on Hybrid Intelligent Systems (HIS 2010). Atlanta USA, 23–25 Aug 2010.
[details] [full text] [BibTeX▼]

@inproceedings{magalhaes-his-2010,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph",
    title = "An optimization heuristic for siting observers in huge terrains stored in external memory",
    booktitle = "10th International Conference on Hybrid Intelligent Systems ({HIS} 2010)",
    address = "Atlanta USA",
    month = "23--25 Aug",
    year = "2010",
    href = "\bibhref{132-atlanta-his10-emsite-magalhaes}",
    mykey = "marcus salles"
}

Marcus V. A. Andrade, Salles V. G. de Magalhães, Mirella A. de Magalhães, W. Randolph Franklin, and Barbara M. Cutler. Efficient viewshed computation on terrain in external memory. Geoinformatica, 2010. (online 26 Nov 2009). URL: http://www.springerlink.com/content/p1783648185g1252/, doi:https://doi.org/10.1007/s10707-009-0100-9.
[abstract▼] [details] [full text] [BibTeX▼]

The recent availability of detailed geographic data permits terrain applications to process large areas at high resolution. However the required massive data processing presents significant challenges, demanding algorithms optimized for bothdata movement and computation. One such application is viewshed computation,that is, to determine all the points visible from a given point p. In this paper, we present an efficient algorithm to compute viewsheds on terrain stored in external memory. In the usual case where the observer's radius of interest is smaller than the terrain size, the algorithm complexity is θ(scan(n2)) where n2 is the number of points in an n×n DEM and scan(n2)is the minimum number of I/O operations required to read n2 contiguous items from external memory. This is much faster than existing published algorithms.
```
@article{andrade-geoinfo-ext-viewshed-2008,
    author = "Andrade, Marcus V. A. and de Magalhães, Salles V. G. and de Magalhães, Mirella A. and Franklin, W. Randolph and Cutler, Barbara M.",
    title = "Efficient viewshed computation on terrain in external memory",
    journal = "Geoinformatica",
    year = "2010",
    href = "\bibhref{126-andrade-geoinfo-ext-viewshed-2008}",
    URL = "http://www.springerlink.com/content/p1783648185g1252/",
    DOI = "https://doi.org/10.1007/s10707-009-0100-9",
    mykey = "visviewshedsiting marcus salles",
    note = "(online 26 Nov 2009)"
}
```