Fakultät Informatik

GPU-Based Real-Time Discrete Euclidean Distance Transforms With Precise Error-Bounds

 Jens Schneider,  Martin Kraus, Rüdiger Westermann

Computer Graphics and Visualization Group,Technische Universität München, Germany


We present a discrete distance transform in style of the vector propagation algorithm by Danielsson. Like other vector propagation algorithms, the proposed method is close to exact, i.e., the error can be strictly bounded from above and is significantly smaller than one pixel. Our contribution is that the algorithm runs entirely on consumer class graphics hardware, thereby achieving a throughput of up to 96 Mpixels/s. This allows the proposed method to be used in a wide range of applications that rely both on high speed and high quality.

Selected Paper

Selected for publication in  Springer CCIS 68 as  extended version.


[.pptx, 5MB], (presented at  VISAPP 2009)


[divx .avi, 13MB] (as submitted for review)



- In collaboration with partners from industry, we have a number of thesis topics available in the area of point-based rendering, geo-localization using public data, scene fusion from different viewpoints. If you are interested, please contact  westermann(at)tum.de


- One PhD position on   Turbulence Visualization is available at the Computer Graphics & Visualization group.