Print (PDF) | On-Screen (PDF) | Slides (PDF) |
---|---|---|
WSCG05 (2.4 MB) | WSCG05 (2.4 MB) | WSCG05 (4.1 MB) |
First, pairs of points from one point set are constructed, bracketing the intersection with the other surface. Second, an interpolation search along shortest paths in the graph is performed. Third, the solutions are refined. For the first and third step, randomized sampling is utilized.
We show that the number of evaluations of the implicit function and the overall runtime is in O( log log N) in the average case, where N is the point cloud size. The storage is bounded by O(N).
Our measurements show that we achieve a speedup by an order of magnitude compared to a recently proposed randomized sampling technique for point cloud collision detection.
@INPROCEEDINGS{Zach05 , author = "Jan Klein and Gabriel Zachmann" , title = "Interpolation Search for Point Cloud Intersection" , booktitle = "Proc. of WSCG 2005" , pages = "163--170" , month = jan # "31 -- " # feb # "7" , year = 2005 , address = "University of West Bohemia, Plzen, Czech Republic" , url = "http://www.gabrielzachmann.org/" , ISBN = "80-903100-7-9" }