Research Projects
4. Hardware-assisted Natural Neighbor Interpolation
Natural Neighbor Interpolation is (NNI) a popular interpolation method based on
Voronoi tessellation. However it suffers from being computationally expensive.
In this project, we explore the powerful ability of Graphic Processing Unit
(GPU) to speed up NNI. Unlike traditional softwre-based approaches that process
one query at a time, we develop a scheme that compute he entire scalar field
induced by NNI, at which point a query is a trivial array lookup, and range
queries over the field are easy to compute. We also present a simple scheme
that requires no advanced graphics capabilities and can process NNI queries
faster than existing software-based approaches. The precision loss caused
by the bounded size of graphics frame buffers is also considered.
Related Publications
