A higher dimensional formulation for robust and interactive distance queries

ABSTRACT

We present an efficient and robust algorithm for computing the minimum distance between a point and freeform curve or surface by lifting the problem into a higher dimension. This higher dimensional formulation solves for all query points in the domain simultaneously, therefore providing opportunities to speed computation by applying coherency techniques. In this framework, minimum distance between a point and planar curve is solved using a single polynomial equation in three variables (two variables for a position of the point and one for the curve). This formulation yields two-manifold surfaces as a zero-set in a 3D parameter space. Given a particular query point, the solution space's remaining degrees-of-freedom are fixed and we can numerically compute the minimum distance in a very efficient way. We further recast the problem of analyzing the topological structure of the solution space to that of solving two polynomial equations in three variables. This topological information provides an elegant way to efficiently find a global minimum distance solution for spatially coherent queries. Additionally, we extend this approach to a 3D case. We formulate the problem for the surface case using two polynomial equations in five variables. The effectiveness of our approach is demonstrated with several experimental results.

References

1. Baraff, D. 1990. Curved surfaces and coherence for non-penatrating rigid body simulation. Computer Graphics 24, 4, 19--28.
2. Breen, D., Mauch, S., and Whitaker, R. 1998. 3d scan conversion of csg models into distance volumes. In Proceedings of the 1998 Symposium on Volume Visualization, ACM SIGGRAPH, 7--14.
3. Bruce, J., and Giblin, P. 1992. Curves and Singularities. Cam-bridge University Press.
4. Dokken, T. 1985. Finding intersections of b-spline represented geometries using recursive subdivision techniques. Computer Aided Geometric Design 2, 1, 189--195.
5. Ehmann, S. A., and Lin, M. C. 2001. Accurate and fast proximity queries between polyhedra using convex surface decomposition. Eurographics (EG) 2001 Proceedings 20, 500--510.
6. Elber, G., and Kim, M. S. 2005. Geometric constraint solver using multivariate rational spline functions. In Proc. of International Conference on Shape Modeling and Applications, MIT, USA, 216--225.
7. Elber, G., Kim, M. S., and Heo, H. 2001. The convex hull of rational plane curves. Graphical Models 63, 151--162.
8. Elber, G. 1992. Free Form Surface Analysis using a Hybrid of Symbolic and Numeric Computation. PhD thesis, Department of Computer Science, University of Utah.
9. Elber, G., 2000. Irit 9.0 user's manual. http://www.cs.technion.ac.il/~irit, October.
10. Frisken, S., Perry, R., Rockwood, A., and Jones, T. 2000. Adaptively sampled distance fields: A general representation of shape for computer graphics. In Proc. of SIGGRAPH 2000, 249--254.
11. Grandine, T., Craciun, B., Heitmann, N., Ingalls, B., Gia, Q., Ou, M., and Tsai, Y. 2000. The bivariate contouring problem. IMA Bebruary 2000 Preprint Series.
12. II, T. T., Johnson, D., and Cohen, E. 1997. Direct haptic rendering of sculptured models. In Proc. of 1997 Symposium on Interactive 3D Graphics, 167--176.
13. Johnson, D., and Cohen, E. 2001. Spatialized normal cone hierarchies. In ACM SIGGRAPH Symposium on Interactive 3D Graphics (I3D), 129--134.
14. Johnson, D., and Cohen, E. 2005. Distance extrema for spline models using tangent cones. In Graphics Interface.
15. Johnson, D. 2005. Minimum distance queries for haptic rendering. PhD Thesis.
16. Kim, M. S., and Elber, G. 2000. Problem reduction to parameter space. In The Mathematics of Surface IX (Proc. of the Ninth IMA Conference), London, 82--98.
17. Larsen, E., Gottschalk, S., Lin, M., and Manocha, D. 2000. Fast distance queries with rectangular swept sphere volumes. In IEEE International Conference on Robotics and Automation (ICRA), 24--48.
18. Mortensen, M. 1985. Geometric Modeling. John Wiley & Sons, New York.
19. Museth, K., Breen, D., Whitaker, R., Mauch, S., and Johnson, D. 2005. Algorithms for interactive editing of level set models. Computer Graphics Forum 24, 4, 1--22.
20. Patrikalakis, N., and Maekawa, T. 2002. Shape Interrogation for Computer Aided Design and Manufacturing. Springer Verlag.
21. Pottmann, H., Leopoldseder, S., and Zhao, H. 2003. The d2-tree: A hierarchical representation of the squared distance function. In Technical Report No. 101, Institut fur Geometrie, TU Wien.
22. Quinlan, S. 1994. Efficient distance computation between non-cnovex objects. In IEEE Int. Conference on Robotics and Automation, 3324--3329.
23. Seong, J., Elber, G., Johnstone, J., and Kim, M. 2004. The convex hull of freeform surfaces. Computing 72, 1, 171--183.
24. Seong, J., Kim, K., Kim, M., Elber, G., and Martin, R. 2005. Intersecting a freeform surfaces with a general swept surface. Computer-Aided Design 37, 5, 473--483.
25. Sherbrooke, E., and Patrikalakis, N. 1993. Computation of the solutions of nonlinear polynomial systems. Comput-erAided Geometric Design 10, 5, 379--405.
26. Sigg, C., Peikert, R., and Gross, M. 2003. Signed distance transform using graphics hardware. In Proc of IEEE VIS.
27. Snyder, J. 1993. Interval analysis for computer graphics. Computer Graphics 26, 2, 121--130.
28. Snyder, J. 1993. Interval methods for multi-point colilisions between time-dependent curved surfaces. Computer Graphics 27, 2, 321--334.
29. Sud, A., Otaduy, M., and Manocha, D. 2004. Difi: Fast 3d distance field computation using graphics hardware. Computer Graphics Forum 23, 3, 557--566.
30. Wang, H., Kearney, J., and Atkinson, K. 2002. Robust and efficient computation of the closest point on a spline curve. In Proceedings of the 5th International Conference on Curves and Surfaces, San Malo, France, 397--406.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

• Mathematics of computing

  • Probability and statistics

    • Probabilistic representations

      • Nonparametric representations

        • Spline models

• Theory of computation

  • Randomness, geometry and discrete structures