Title | ||
---|---|---|
GPU-accelerated Hausdorff distance computation between dynamic deformable NURBS surfaces |
Abstract | ||
---|---|---|
We present a parallel GPU-accelerated algorithm for computing the directed Hausdorff distance from one NURBS surface to another, within a bound. We make use of axis-aligned bounding-box hierarchies that bound the NURBS surfaces to accelerate the computations. We dynamically construct as well as traverse the bounding-box hierarchies for the NURBS surfaces using operations that are optimized for the GPU. To compute the Hausdorff distance, we traverse this hierarchy after culling bounding-box pairs that do not contribute to the Hausdorff distance. Our contribution includes two-sided culling tests that can be performed in parallel using the GPU. The culling, based on the minimum and maximum distance ranges between the bounding boxes, eliminates bounding-box pairs from both surfaces that do not contribute to the Hausdorff distance simultaneously. We calculate accuracy bounds for our computed Hausdorff distance based on the curvature of the surfaces. Our algorithm runs in real-time with very small guaranteed error bounds for complex NURBS surfaces. Since we dynamically construct our bounding-box hierarchy, our algorithm can be used to interactively compute the Hausdorff distance for models made of dynamic deformable surfaces. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1016/j.cad.2011.08.022 | Computer-Aided Design |
Keywords | Field | DocType |
axis-aligned bounding-box hierarchy,maximum distance range,bounding-box hierarchy,hausdorff distance,nurbs surface,gpu-accelerated hausdorff distance computation,parallel gpu-accelerated algorithm,computed hausdorff distance,bounding-box pair,dynamic deformable,complex nurbs surface,accuracy bound,nurbs,real time | Topology,Tree traversal,Curvature,Hausdorff distance,Interactive computation,Mathematics,Traverse,Bounding overwatch,Computation | Journal |
Volume | Issue | ISSN |
43 | 11 | 0010-4485 |
Citations | PageRank | References |
10 | 0.51 | 16 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Adarsh Krishnamurthy | 1 | 107 | 12.51 |
Sara McMains | 2 | 293 | 32.31 |
Iddo Hanniel | 3 | 197 | 12.98 |