Information

  • Publication Type: Bachelor Thesis
  • Workgroup(s)/Project(s):
  • Date: September 2022
  • Date (to): 15. October 2022
  • Matrikelnummer: 11808210
  • First Supervisor: Michael Wimmer

Abstract

As the accessibility of high-quality 3D scans increases, processing the scanned data becomes more challenging. 3D scanners obtain very large, unstructured sets of points, so called point clouds. To be able to use the data in a meaningful way it is necessary to reconstruct the surface of the scanned object from the point cloud, resulting in a 3D model. This is called the problem of 3D surface reconstruction. Processing very large point clouds (in a reasonable time) is necessary in order to keep up with ever increasing scanning technology. In this thesis, we construct, implement and evaluate a distributed surface reconstruction algorithm called DistributedBallFilter. It is a distributed-memory parallel version of the recently developed BallFilter algorithm [Ohr22]. Firstly, the input point cloud is subdivided into chunks called tiles using a 3D grid. To ensure the correctness of the results, tiles are slightly overlapping on their borders. After splitting the input, each tile can be processed independently from each other. The tiles are assigned and distributed to a number of p processes. The assignment of tiles to processes is calculated using longest-processing-time-first list scheduling. Then all processes reconstruct the 3D surface of all their assigned tiles in parallel. After all tiles are processed, the result is merged back together into a single 3D model, containing the reconstructed surface of the entire input point cloud. The asymptotic run time complexity is O(n log n) in the worst case (same as BallFilter) and O(n + n log n p ) in the best case, depending on the distribution of points within the input data. Furthermore, we implemented the algorithm in C++. The input splitting is run on a GPU using CUDA and discussed thoroughly in its dedicated paper [Bru22]. For each tile a single file is output, which is communicated to each process via a distributed file system. The MPI standard is used for sending all local results to a single process, which is also responsible for merging and outputting the final 3D model. Finally we executed the algorithm on the VSC3+ cluster, a high-performance cluster based in Vienna. It was run against several test data sets. We visualize the results and analysed the behavior of the running time when scaling the number of processes as well as the input size. In our tests, DistributedBallFilter managed to be up to around five times faster than BallFilter depending on the number of nodes used and the input size. The largest observed speedup was by a factor of 5.89 compared to BallFilter.

Additional Files and Images

Additional images and videos

Additional files

Weblinks

No further information available.

BibTeX

@bachelorsthesis{Komon2022,
  title =      "Distributed Surface Reconstruction",
  author =     "Patrick Michael Komon",
  year =       "2022",
  abstract =   "As the accessibility of high-quality 3D scans increases,
               processing the scanned data becomes more challenging. 3D
               scanners obtain very large, unstructured sets of points, so
               called point clouds. To be able to use the data in a
               meaningful way it is necessary to reconstruct the surface of
               the scanned object from the point cloud, resulting in a 3D
               model. This is called the problem of 3D surface 
               reconstruction. Processing very large point clouds (in a
               reasonable time) is necessary in order to keep up with ever
               increasing scanning technology. In this thesis, we
               construct, implement and evaluate a distributed surface
               reconstruction algorithm called DistributedBallFilter. It is
               a distributed-memory parallel version of the recently
               developed BallFilter algorithm [Ohr22]. Firstly, the input
               point cloud is subdivided into chunks called tiles using a
               3D grid. To ensure the correctness of the results, tiles are
               slightly overlapping on their borders. After splitting the
               input, each tile can be processed independently from each
               other. The tiles are assigned and distributed to a number of
               p processes. The assignment of tiles to processes is
               calculated using longest-processing-time-first list
               scheduling. Then all processes reconstruct the 3D surface of
               all their assigned tiles in parallel. After all tiles are
               processed, the result is merged back together into a single
               3D model, containing the reconstructed surface of the entire
               input point cloud. The asymptotic run time complexity is O(n
               log n) in the worst case (same as BallFilter) and O(n + n
               log n p ) in the best case, depending on the distribution of
               points within the input data. Furthermore, we implemented
               the algorithm in C++. The input splitting is run on a GPU
               using CUDA and discussed thoroughly in its dedicated paper
               [Bru22]. For each tile a single file is output, which is
               communicated to each process via a distributed file system.
               The MPI standard is used for sending all local results to a
               single process, which is also responsible for merging and
               outputting the final 3D model. Finally we executed the
               algorithm on the VSC3+ cluster, a high-performance cluster
               based in Vienna. It was run against several test data sets.
               We visualize the results and analysed the behavior of the
               running time when scaling the number of processes as well as
               the input size. In our tests, DistributedBallFilter managed
               to be up to around five times faster than BallFilter
               depending on the number of nodes used and the input size.
               The largest observed speedup was by a factor of 5.89
               compared to BallFilter.",
  month =      sep,
  address =    "Favoritenstrasse 9-11/E193-02, A-1040 Vienna, Austria",
  school =     "Research Unit of Computer Graphics, Institute of Visual
               Computing and Human-Centered Technology, Faculty of
               Informatics, TU Wien ",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2022/Komon2022/",
}