[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Continuous point projection to planar freeform curves using spiral curves

  • Original Article
  • Published:
The Visual Computer Aims and scope Submit manuscript

Abstract

We present an efficient algorithm for projecting a continuously moving query point to a family of planar freeform curves. The algorithm is based on the one-sided Hausdorff distance from the trajectory curve (of the query point) to the planar curves. Using a bounding volume hierarchy (BVH) of the planar curves, we estimate an upper bound \(\overline{h}\) of the one-sided Hausdorff distance and eliminate redundant curve segments when they are more than distance \(\overline{h}\) away from the trajectory curve. Recursively subdividing the trajectory curve and repeating the same elimination procedure to the BVH of the remaining curves, we can efficiently determine where to project the moving query point. The explicit continuous point projection is then interpreted as a curve reparameterization problem, for which we propose a few simple approximation techniques. Using several experimental results, we demonstrate the effectiveness of the proposed approach.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Barton, M., Elber, G.: Spiral fat arcs—bounding regions with cubic convergence. Graph. Models, 73(2), 50–57 (2011)

    Article  Google Scholar 

  2. Barton, M., Hanniel, I., Elber, G., Kim, M.-S.: Precise Hausdorff distance computation between polygonal meshes. Comput. Aided Geom. Des. 28(8), 580–591 (2010)

    Article  MathSciNet  Google Scholar 

  3. Beckmann, N., Kriegel, H.-P., Schneider, R., Seeger, B.: The R∗-tree: an efficient and robust access method for points and rectangles. In: ACM SIGMOD Conf. on the Management of Data, pp. 322–331 (1990)

    Google Scholar 

  4. Chen, X.-D., Yong, J.-H., Wang, G., Paul, J.-C., Xu, G.: Computing minimum distance between a point and a NURBS curve. Comput. Aided Des. 40(10–11), 1051–1054 (2008)

    Article  Google Scholar 

  5. do Carmo, M.: Differential Geometry of Curves and Surfaces. Prentice-Hall, New York (1976)

    MATH  Google Scholar 

  6. Elber, G., Kim, M.-S.: Geometric constraint solver using multivariate rational spline functions. In: Proc. of the sixth ACM Symposium on Solid Modeling and Applications, pp. 1–10 (2001)

    Chapter  Google Scholar 

  7. Hu, S.-M., Wallner, J.: A second order algorithm for orthogonal projection onto curves and surfaces. Comput. Aided Geom. Des. 22(3), 251–260 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  8. Gilbert, E., Johnson, D., Keerthi, S.: A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE Trans. Robot. Autom. 4, 193–203 (1988)

    Article  Google Scholar 

  9. IRIT 10.0 User’s Manual, Technion. http://www.cs.technion.ac.il/~irit

  10. Johnson, D.: Minimum distance queries for haptic rendering. PhD thesis, Computer Science Department, University of Utah (2005)

  11. Johnson, D., Cohen, E.: A framework for efficient minimum distance computations. In: IEEE Conf. on Robotics and Automation, pp. 3678–3683 (1998)

    Google Scholar 

  12. Kim, Y.-J., Oh, Y.-T., Yoon, S.-H., Kim, M.-S., Elber, G.: Precise Hausdorff distance computation for planar freeform curves using biarcs and depth buffer. Vis. Comput. 26(6–8), 1007–1016 (2010)

    Article  Google Scholar 

  13. Larsen, E., Gottschalk, S., Lin, M.C., Manocha, D.: Fast distance queries using rectangular swept sphere volumes. In: IEEE Int’l Conf. on Robotics and Automation (2000)

    Google Scholar 

  14. Lee, I.-K., Kim, M.-S., Elber, G.: Polynomial/rational approximation of Minkowski sum boundary curves. CVGIP, Graph. Models Image Process. 60(2), 136–165 (1998)

    Article  Google Scholar 

  15. Lin, M.C., Canny, J.: A fast algorithm for incremental distance calculation. In: IEEE Int. Conf. Robot. Automat., Sacramento, CA, pp. 1008–1014 (1991)

    Google Scholar 

  16. Lin, M.C., Gottschalk, S.: Collision detection between geometric models: a survey. In: Proc. of IMA Conference on Mathematics of Surfaces, pp. 37–56 (1998)

    Google Scholar 

  17. Lin, M.C., Manocha, D.: Collision and proximity queries. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 787–807. Chapman & Hall/CRC, New York (2004)

    Google Scholar 

  18. Liu, X.-M., Yang, L., Yong, J.-H., Gu, H.-J., Sun, J.-G.: A torus patch approximation approach for point projection on surfaces. Comput. Aided Geom. Des. 26(5), 593–598 (2009)

    Article  MathSciNet  Google Scholar 

  19. Ma, Y.L., Hewitt, W.: Point inversion and projection for NURBS curve and surface: control polygon approach. Comput. Aided Geom. Des. 20(2), 79–99 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  20. Oh, Y.-T., Kim, Y.-J., Lee, J., Kim, M.-S., Elber, G.: Efficient point projection to freeform curves and surfaces. Comput. Aided Geom. Des., 28 (2011, to appear)

  21. Peternell, M.: Geometric properties of bisector surfaces. Graph. Models 62(3), 202–236 (2000)

    Article  Google Scholar 

  22. Selimovic, I.: Improved algorithms for the projection of points on NURBS curves and surfaces. Comput. Aided Geom. Des. 23(5), 439–445 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  23. Seong, J.-K., Johnson, D., Cohen, E.: A higher dimensional formulation for robust and interactive distance queries. In: SPM’06: Proc. of the 2006 ACM Symp. on Solid and Physical Modeling, Cardiff Univ., Wales, UK, June 6–8, 2006, pp. 197–205 (2006)

    Chapter  Google Scholar 

  24. Tang, M., Lee, M., Kim, Y.J.: Interactive Hausdorff distance computation for general polygonal models. ACM Trans. Graph. (SIGGRAPH ’09), 28(3) (2009)

Download references

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, Seoul National University, Seoul, 151-744, Korea

    Young-Taek Oh, Yong-Joon Kim & Myung-Soo Kim

  2. School of Computer Engineering, Chosun University, Gwangju, 501-759, Korea

    Jieun Lee

  3. Computer Science Department, Technion, Haifa, 32000, Israel

    Gershon Elber

Authors
  1. Young-Taek Oh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yong-Joon Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jieun Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Myung-Soo Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Gershon Elber
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Myung-Soo Kim.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Oh, YT., Kim, YJ., Lee, J. et al. Continuous point projection to planar freeform curves using spiral curves. Vis Comput 28, 111–123 (2012). https://doi.org/10.1007/s00371-011-0632-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00371-011-0632-5

Keywords

Search

Navigation