Doctoral theses.

2017

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

  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.

  BibTeX

  @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

• Wenli Li. GPU-accelerated terrain processing. PhD thesis, Rensselaer Polytechnic Institute, 2016.
  [details] [full text]
  Abstract

  This thesis extends Overdetermined Laplacian Partial Differential Equations (ODETLAP) for spatial data approximation and compression and parallelizes multiple observer siting on terrain, using General-Purpose Computing on Graphics Processing Units (GPGPU). Both ODETLAP compression and multiple observer siting use greedy algorithms that are parallelizable within iterations but sequential between iterations. They also demonstrate terrain-related research and applications that benefit from GPU acceleration and showcase the achievable speedups. ODETLAP approximation approximates a spatial dataset from scattered data points on a regular grid by solving an overdetermined system of linear equations that minimizes the absolute Laplacian of the approximation and the value errors of the data points. We show that ODETLAP approximation is a linear operator and is comparable in accuracy with natural neighbor interpolation and the multiquadric-biharmonic method. Using ODETLAP approximation to approximate spatial datasets, ODETLAP compression compresses a dataset as a set of known points and their values and decompresses it as an approximation from the known points. We implement ODETLAP approximation and compression using the CUSP library and the speedup is 8 times on a GPU. We design multiple algorithms to improve the accuracy of ODETLAP compression using a limited number of known points and use them to compress 2D terrain datasets and 3D MRI datasets. The results show that ODETLAP compression is 30% to 50% better in minimizing the maximum absolute error than JPEG 2000 for the terrain datasets and 40% to 60% better than JP3D for the MRI datasets. To further increase speed, we design a segmented ODETLAP compression algorithm and use it to compress larger 3D atmospheric and MRI datasets. The results show that the compressed size of the dataset is 60% that of JP3D for the same maximum absolute error. Multiple observer siting places multiple observer points above a terrain to maximize the total area visible from at least one observer. The algorithm first selects a set of highly visible points as tentative observers, and then iteratively selects observers to maximize the cumulative viewshed. We improve the time and space complexities of the algorithm and parallelize it using CUDA on a GPU and using OpenMP on multi-core CPUs. The speedup is up to 60 times on the GPU and 16 times on two CPUs with 16 cores.

  BibTeX

  @phdthesis{wenli-phd,
      author = "Li, Wenli",
      title = "{GPU}-accelerated terrain processing",
      school = "Rensselaer Polytechnic Institute",
      mykey = "wenlili visviewshedsiting gpusiting parallel theses",
      year = "2016"
  }
  

2012

• Tsz-Yam Lau. Two-step ODETLAP and induced terrain for improved geographical data reconstruction. PhD thesis, Rensselaer Polytechnic Institute, 2012.
  [details] [full text]
  BibTeX

  @phdthesis{lau-phd,
      author = "Lau, Tsz-Yam",
      title = "Two-step {ODETLAP} and induced terrain for improved geographical data reconstruction",
      school = "Rensselaer Polytechnic Institute",
      mykey = "odetlap hydro lau theses bathy",
      year = "2012"
  }
  

• Chris Stuetzle. Representation and generation of terrain using mathematical modeling. PhD thesis, Rensselaer Polytechnic Institute, 2012.
  [details] [full text]
  BibTeX

  @phdthesis{stuetzle-phd,
      author = "Stuetzle, Chris",
      title = "Representation and generation of terrain using mathematical modeling",
      school = "Rensselaer Polytechnic Institute",
      mykey = "odetlap theses",
      year = "2012"
  }
  

2011

• You Li. CUDA-accelerated HD-ODETLAP: a high dimensional geospatial data compression framework. PhD thesis, Rensselaer Polytechnic Institute, 2011.
  [details] [full text]
  BibTeX

  @phdthesis{li-phd,
      author = "Li, You",
      title = "{CUDA}-accelerated {HD-ODETLAP}: a high dimensional geospatial data compression framework",
      school = "Rensselaer Polytechnic Institute",
      mykey = "odetlap youli theses",
      year = "2011"
  }
  

2009

• Daniel M. Tracy. Path Planning and Slope Representation on Compressed Terrain. PhD thesis, Rensselaer Polytechnic Institute, 2009.
  [details] [full text]
  BibTeX

  @phdthesis{tracy-phd,
      author = "Tracy, Daniel M.",
      title = "Path Planning and Slope Representation on Compressed Terrain",
      school = "Rensselaer Polytechnic Institute",
      mykey = "odetlap theses tracy",
      year = "2009"
  }
  

2008

• Metin Inanc. Compressing Terrain Elevation Datasets. PhD thesis, Rensselaer Polytechnic Institute, 2008.
  [details] [full text]
  BibTeX

  @phdthesis{inanc-phd,
      author = "Inanc, Metin",
      title = "Compressing Terrain Elevation Datasets",
      school = "Rensselaer Polytechnic Institute",
      mykey = "theses odetlap inanc",
      year = "2008"
  }
  

2000

• Hélio Pedrini. An Adaptive Method for Terrain Approximation based on Triangular Meshes. PhD thesis, Rensselaer Polytechnic Institute, Electrical, Computer, and Systems Engineering Dept, 2000.
  [details]
  BibTeX

  @phdthesis{pedrini-phd,
      author = "Pedrini, H{\'e}lio",
      title = "An Adaptive Method for Terrain Approximation based on Triangular Meshes",
      school = "Rensselaer Polytechnic Institute, Electrical, Computer, and Systems Engineering Dept",
      mykey = "theses",
      year = "2000"
  }
  

1998

• Michael B Gousie. Contours to digital elevation models: grid-based surface reconstruction methods. PhD thesis, Electrical, Computer, and Systems Engineering Dept., Rensselaer Polytechnic Institute, 1998.
  [details]
  BibTeX

  @phdthesis{gousie-phd,
      author = "Gousie, Michael B",
      title = "Contours to digital elevation models: grid-based surface reconstruction methods",
      school = "Electrical, Computer, and Systems Engineering Dept., Rensselaer Polytechnic Institute",
      mykey = "odetlap theses",
      year = "1998"
  }
  

1994

• Clark K. Ray. Representing Visibility for Siting Problems. PhD thesis, Rensselaer Polytechnic Institute, May 1994.
  [details] [full text]
  BibTeX

  @phdthesis{ray-phd,
      author = "Ray, Clark K.",
      title = "Representing Visibility for Siting Problems",
      school = "Rensselaer Polytechnic Institute",
      year = "1994",
      mykey = "theses",
      month = "May"
  }
  

1991

• Chandrasekhar Narayanaswami. Parallel Processing for Geometric Applications. PhD thesis, Electrical, Computer, and Systems Engineering Dept., Rensselaer Polytechnic Institute, 1991. UMI no. 92-02201.
  [details]
  BibTeX

  @phdthesis{chandra-phd,
      Author = "Narayanaswami, Chandrasekhar",
      Title = "Parallel Processing for Geometric Applications",
      School = "Electrical, Computer, and Systems Engineering Dept., Rensselaer Polytechnic Institute",
      Year = "1991",
      mykey = "theses chandra",
      note = "UMI no. 92-02201",
      Wrfnote = "WRF has"
  }
  

1990

• Mohan Kankanhalli. Techniques for Parallel Geometric Computations. PhD thesis, Electrical, Computer, and Systems Engineering Dept., Rensselaer Polytechnic Institute, October 1990.
  [details]
  BibTeX

  @phdthesis{mohan-phd,
      Author = "Kankanhalli, Mohan",
      Title = "Techniques for Parallel Geometric Computations",
      School = "Electrical, Computer, and Systems Engineering Dept., Rensselaer Polytechnic Institute",
      Year = "1990",
      Month = "October",
      mykey = "theses kankanhalli",
      Wrfnote = "WRF has"
  }
  

1987

• Peter Yick Fai Wu. Polygon Overlay in Prolog. PhD thesis, Electrical, Computer, and Systems Engineering Dept., Rensselaer Polytechnic Institute, 1987.
  [details]
  BibTeX

  @phdthesis{wu-phd,
      author = "Wu, Peter Yick Fai",
      title = "Polygon Overlay in Prolog",
      school = "Electrical, Computer, and Systems Engineering Dept., Rensselaer Polytechnic Institute",
      mykey = "theses over",
      year = "1987"
  }
  

• William S. Yerazunis. DIS: an Architecture for fast LISP execution. PhD thesis, Rensselaer Polytechnic Institute, ECSE Dept., May 1987. UMI abstract no. 87-29,340.
  [details]
  BibTeX

  @phdthesis{yerazunis-phd,
      author = "Yerazunis, William S.",
      title = "DIS: an Architecture for fast LISP execution",
      school = "Rensselaer Polytechnic Institute, ECSE Dept.",
      year = "1987",
      month = "May",
      mykey = "theses",
      note = "UMI abstract no. 87-29,340"
  }
  

1985

• Varol Akman. Shortest paths avoiding polyhedral obstacles in 3-dimensional euclidean space. PhD thesis, Electrical, Computer, and Systems Engineering Dept., Rensselaer Polytechnic Institute, 1985. UMI abstract no. 85-28,651.
  [details]
  Abstract

  Algebraic and geometric algorithms are presented to solve the general and some specific instances of the following problem which is known as FINDPATH in artificial intelligence: "Given a set of polyhedra and two external points (source and goal), calculate the shortest path between these points under the Euclidean metric, constrained to avoid intersections with the given polyhedra." The shortest path is a polygonal path connecting the source and the goal, possibly bending at some edges of the given polyhedra while subtending equal entry and exit angles. The general problem can then be solved exactly using symbolic algebra and is based upon finding the real roots of a system of non-linear equations (stating the angular equality conditions) by elimination. If approximate solutions are acceptable this can also be done using numerical methods such as continuation, or using optimization methods to minimize a sum of square roots (expressing the length of the shortest path). In addition, two special cases are solved where there exists a single convex polyhedron, and the source and the goal are on its boundary or exterior. These solutions make use of planar developments of polyhedra and polyhedral visibility. Two Voronoi-based locus methods are also introduced to solve FINDPATH. These methods use preprocessing to speed up subsequent searches for a shortest path. The first method partitions the boundary of a convex polyhedron given only the source on it so that, for a later goal on the boundary, the shortest path is found efficiently. It makes use of standard point location algorithms for a straight-edge planar subdivision once the partitioning is done. The second method, currently more of a descriptive nature than algorithmic, is based on W. R. Franklin's "Partitioning the Plane to Calculate Minimal Paths to any Goal around Obstructions" Tech. Rep., ECSE Dept., Rensselaer Polytechnic Inst., Troy, NY, Nov. 1982 , and for a given source, partitions the free space around polyhedra into regions (bounded by high-order surfaces) so that the shortest paths for all goals in a given region follow the same sequence of edges of the given polyhedra. This method makes use of a recent spatial point location algorithm for arbitrary algebraic varieties. Finally, an overview of a workbench (called SP) which implements some of the above and thus allows experimentation with shortest paths is given.

  BibTeX

  @phdthesis{akman-phd,
      author = "Akman, Varol",
      title = "Shortest paths avoiding polyhedral obstacles in 3-dimensional euclidean space",
      school = "Electrical, Computer, and Systems Engineering Dept., Rensselaer Polytechnic Institute",
      year = "1985",
      mykey = "akman theses",
      note = "{UMI} abstract no. 85-28,651"
  }