TY - GEN
T1 - Hardware-assisted natural neighbor interpolation
AU - Fan, Quanfu
AU - Efrat, Alon
AU - Koltun, Vladlen
AU - Krishnan, Shankar
AU - Venkatasubramanian, Suresh
PY - 2005
Y1 - 2005
N2 - Natural neighbor interpolation is a weighted average interpolation method that is based on Voronoi tessellation. In this paper, we present and implement an algorithm for performing natural neighbor interpolation using graphics hardware. Unlike traditional software-based approaches that process one query at a time, we develop a scheme that computes the entire scalar field induced by natural neighbor interpolation, at which point a query is a trivial array lookup, arid range queries over the field are easy to perform. Our approach is faster than the best known software implementations and makes use of general purpose stream programming capabilities of current graphics cards. We also present a simple scheme that requires no advanced graphics capabilities and can process natural neighbor queries faster than existing software-based approaches. Finally, recognizing the limitation incurred by the bounded size of graphics frame buffers, we propose a sub-division approach that allows performing queries locally in a subdivision of the input domain. This approach can reduce to a negligibly small degree (< 1%) the loss of precision caused by the naive scaling method while still processing queries faster than the software-based approaches when the number of sites is large.
AB - Natural neighbor interpolation is a weighted average interpolation method that is based on Voronoi tessellation. In this paper, we present and implement an algorithm for performing natural neighbor interpolation using graphics hardware. Unlike traditional software-based approaches that process one query at a time, we develop a scheme that computes the entire scalar field induced by natural neighbor interpolation, at which point a query is a trivial array lookup, arid range queries over the field are easy to perform. Our approach is faster than the best known software implementations and makes use of general purpose stream programming capabilities of current graphics cards. We also present a simple scheme that requires no advanced graphics capabilities and can process natural neighbor queries faster than existing software-based approaches. Finally, recognizing the limitation incurred by the bounded size of graphics frame buffers, we propose a sub-division approach that allows performing queries locally in a subdivision of the input domain. This approach can reduce to a negligibly small degree (< 1%) the loss of precision caused by the naive scaling method while still processing queries faster than the software-based approaches when the number of sites is large.
UR - http://www.scopus.com/inward/record.url?scp=32144460834&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=32144460834&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:32144460834
SN - 0898715962
SN - 9780898715965
T3 - Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics
SP - 111
EP - 120
BT - Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics
A2 - Demetrescu, C.
A2 - Sedgewick, R.
A2 - Tamassia, R.
T2 - Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics
Y2 - 22 January 2005 through 22 January 2005
ER -