Fast Approximation of High Order Voronoi Diagrams and Distance Transforms on the GPU

DSpace/Manakin Repository

Fast Approximation of High Order Voronoi Diagrams and Distance Transforms on the GPU

Citable link to this page

 

 
Title: Fast Approximation of High Order Voronoi Diagrams and Distance Transforms on the GPU
Author: Fischer, Ian; Gotsman, Craig

Note: Order does not necessarily reflect citation order of authors.

Citation: Fischer, Ian and Craig Gotsman. 2005. Fast Approximation of High Order Voronoi Diagrams and Distance Transforms on the GPU. Harvard Computer Science Group Technical Report TR-07-05.
Full Text & Related Files:
Abstract: We present an implementation of the tangent-plane algorithm for computing the kth-order Voronoi diagram of a set of sites in image space. Correct and efficient implementation of this algorithm using graphics hardware is possible only with the use of an appropriate shader program on the GPU. This is achieved by rendering in k passes the parallel projection of the top k levels of an arrangement of planes tangent to the paraboloid z = x^2+y^2. Each level of the arrangement corresponds to the so-called kth-nearest point diagram, which is interesting in its own right. Composition of the images of the k top levels results in the kth-order Voronoi diagram. The diagram facilitates efficient computation of the k nearest neighbors of an arbitrary query point. We describe our implementation of the algorithm in OpenGL and Cg, and its optimizations. We also show how to efficiently compute the distance transform of the given sites using the GPU, based on the first-order Voronoi diagram.
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:24019793
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters