External Sorting of Point Clouds

Information

• Publication Type: Bachelor Thesis
• Workgroup(s)/Project(s):
  • TERAPOINTS - High Quality Visualization and Interaction with Gigantic Point Data Sets
• Date: September 2013
• Matrikelnummer: 0825842
• First Supervisor: Claus Scheiblauer
• Keywords: Point Clouds, Sorting, Out-of-Core algorithms

Abstract

In recent years, points have seen increased use as a rendering primitive. This Bachelor Thesis presents and compares a number of sorting algorithms used for sorting points in a preprocessing step. This is done in order to decrease the time needed to create a point cloud model that can be rendered by the GPU in real time. Points are compared either by their position along the longest axis or by Morton order and sorted using heap sort or radix sort. An external merge sort algorithm is used for large datasets that do not completely fit into memory. The speed of the sorting process is furthermore increased by making use of parallel processing.

Additional Files and Images

Weblinks

No further information available.

BibTeX

@bachelorsthesis{leimer-2013-esopc,
  title =      "External Sorting of Point Clouds",
  author =     "Kurt Leimer",
  year =       "2013",
  abstract =   "In recent years, points have seen increased use as a
               rendering primitive. This Bachelor Thesis presents and
               compares a number of sorting algorithms used for sorting
               points in a preprocessing step. This is done in order to
               decrease the time needed to create a point cloud model that
               can be rendered by the GPU in real time. Points are compared
               either by their position along the longest axis or by Morton
               order and sorted using heap sort or radix sort. An external
               merge sort algorithm is used for large datasets that do not
               completely fit into memory. The speed of the sorting process
               is furthermore increased by making use of parallel
               processing.",
  month =      sep,
  address =    "Favoritenstrasse 9-11/E193-02, A-1040 Vienna, Austria",
  school =     "Institute of Computer Graphics and Algorithms, Vienna
               University of Technology ",
  keywords =   "Point Clouds, Sorting, Out-of-Core algorithms",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2013/leimer-2013-esopc/",
}