Exact Geometric Computations on the GPU
PR, BA
Description
Geometric algorithms are generally designed for machine models with exact real arithmetics, i.e. they assume exact computation with real numbers. Common hardware supports only integer, floating-point or fixed-point data types with finite size. A simple substitution of real numbers with these types can cause geometric computations to exhibit inaccuracies or make them fail.
The exact computation of geometric quantities has a long history in both theoretical and applied computer science and several libraries were developed to provide such functionality (e.g. CGAL, LEDA). However, exact computations are slower by several orders of magnitude when compared with their (inexact) floating-point counterparts. In this project we want to examine the potential of GPUs to speed up exact computations.
Tasks
- Familiarize yourself with the literature on the robustness of geometric computations.
- Analyze the approaches of current state-of-the-art (e.g. LEDA, CGAL,...).
- Analyze the potential for parallelizing chosen geometric computations.
- Adapt robust arithmetics to the GPU architecture.
- Adapt chosen geometric computations to the GPU architecture.
Requirements
- Knowledge of geometric computations (2D/3D geometry, convex hull, ...). Knowledge of the LEDA and/or CGAL library beneficial.
- Knowledge of the GPU computing model (e.g. CUDA).
- Familiarity with C++ and template programming (to understand LEDA and CGAL).
Literature
Primer on geometric computation problems: Classroom Examples
Primer on LEDA and CGAL: Geometric Computing with CGAL and LEDA
Primer on Core 2: The Design of Core 2
Contact
Email: thomas.auzinger@cg.tuwien.ac.at
Homepage: Thomas Auzinger
Phone: +43 1 58801-18683
