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

Topological structure extraction for computing surface–surface intersection curves

  • Research
  • Published:
The Visual Computer Aims and scope Submit manuscript

Abstract

Surface–surface intersection curve computation is a fundamental problem in CAD and solid modeling. Extracting the structure of intersection curves accurately, especially when there are multiple overlapping curves, is a key challenge. Existing methods rely on densely sampled intersection points and proximity-based connections, which are time-consuming to obtain. In this paper, we propose a novel method based on Delaunay triangulation to accurately extract intersection curves, even with sparse intersection points. We also introduce an intersection curve optimization technique to enhance curve accuracy. Extensive experiments on various examples demonstrate the effectiveness of our method.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Algorithm 1
Fig. 5
Fig. 6
Algorithm 2
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Explore related subjects

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

References

  1. Bajaj, C., Xu, G.: Nurbs approximation of surface/surface intersection curves. Adv. Comput. Math. 2, 1–21 (2000)

    Article  MathSciNet  Google Scholar 

  2. Bajaj, C.L., Hoffmann, C.M., Lynch, R.E., Hopcroft, J.: Tracing surface intersections. Comput. Aided Geom. Des. 5(4), 285–307 (1988)

    Article  MathSciNet  Google Scholar 

  3. Bo, P., Luo, G., Wang, K.: A graph-based method for fitting planar B-spline curves with intersections. J. Comput. Des. Eng. 3, 14–23 (2016)

    Google Scholar 

  4. Cho, N.W., Kim, N.K., Kim, Y., Kang, S.H.: An evolutionary method for general surface–surface intersection problems. Comput. Ind. Eng. 33(3–4), 573–576 (1997)

    Article  Google Scholar 

  5. Ertugrul, E., Zhang, H., Zhu, F., Lu, P., Li, P., Sheng, B., Wu, E.: Embedding 3d models in offline physical environments. Comput. Anim. Virtual Worlds 31, e1959 (2020)

    Article  Google Scholar 

  6. Filip, D., Magedson, R., Markot, R.: Surface algorithms using bounds on derivatives. Comput. Aided Geom. Des. 3(4), 295–311 (1986)

    Article  MathSciNet  Google Scholar 

  7. Grandine, T.A., Iv, F.W.K.: A new approach to the surface intersection problem. Comput. Aided Geom. Des. 14(2), 111–134 (1997)

    Article  MathSciNet  Google Scholar 

  8. Heo, H.S., Hong, S.J., Seong, J.K., Kim, M.S., Elber, G.: The intersection of two ringed surfaces and some related problems. Graph. Models 63(4), 228–244 (2001)

    Article  Google Scholar 

  9. Hoffmann, C.M.: Geometric and Solid Modeling. Morgan Kaufmann, Burlington (1989)

    Google Scholar 

  10. Hoschek, J.: Fundamentals of Computer Aided Geometric Design. A. K. Peters, Ltd, Natick (1993)

    Google Scholar 

  11. Hur, S., Oh, M.J., Kim, T.W.: Approximation of surface-to-surface intersection curves within a prescribed error bound satisfying G2 continuity. Comput. Aided Des. 41(1), 37–46 (2009)

  12. Hur, S., Oh, M.J., Kim, T.W.: Classification and resolution of critical cases in Grandine and Klein’s topology determination using a perturbation method. Comput. Aided Geom. Des. 26(2), 243–258 (2009)

    Article  MathSciNet  Google Scholar 

  13. Jia, X., Li, K., Cheng, J.: Computing the intersection of two rational surfaces using matrix representations. Comput. Aided Des. 150, 150 (2022)

    Article  MathSciNet  Google Scholar 

  14. Jiang, J., Sheng, B., Li, P., Ma, L., Tong, X., Wu, E.: Real-time hair simulation with heptadiagonal decomposition on mass spring system. Graph. Models 111, 101077 (2020)

    Article  Google Scholar 

  15. Kriezis, G., Prakash, P., Patrikalakis, N.: Method for intersecting algebraic surfaces with rational polynomial patches. Comput. Aided Des. 22(10), 645–654 (1990)

    Article  Google Scholar 

  16. Lam, B.S.Y., Yan, H.: New curve-tracing algorithm based on a minimum-spanning-tree model and regularized fuzzy clustering. Opt. Eng. 45, 017201 (2006)

    Article  Google Scholar 

  17. Lee, K.Y., Cho, D.Y., Kim, T.W.: A tracing algorithm for surface-surface intersections on surface boundaries. J. Comput. Sci. Technol. 17(6), 843–850 (2002)

    Article  MathSciNet  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 implicit surfaces. Comput. Aided Geom. Des. 346(5), 593–598 (2009)

    Article  Google Scholar 

  19. Musin, O.: Properties of the Delaunay triangulation. In: Proceedings of the Annual Symposium on Computational Geometry (2004)

  20. Park, Y., Son, S.H., Kim, M.S., Elber, G.: Surface surface-intersection computation using a bounding volume hierarchy with osculating toroidal patches in the leaf nodes. Comput.-Aided Des. 127, 102866 (2020)

    Article  MathSciNet  Google Scholar 

  21. Patrikalakis, N.M., Maekawa, T., Ko, K.H., Mukundan, H.: Surface-to-surface intersections. IEEE Comput. Graph. Appl. 13(1–4), 449–457 (2004)

    Google Scholar 

  22. Patrikalakis, N.M., Maekawa, T.: Shape Interrogation for Computer Aided Design and Manufacturing, vol. 15. Springer, Berlin (2002)

  23. Qin, Y., Chi, X., Sheng, B., Lau, R.W.H.: Guiderender: large-scale scene navigation based on multi-modal view frustum movement prediction. Vis. Comput. 39(8), 3597–3607 (2023)

  24. Ramsey, S.D., Potter, K., Hansen, C.: Ray bilinear patch intersections. J. Graph. Tools 9(3), 41–47 (2004)

    Article  Google Scholar 

  25. Sederberg, T.W., Christiansen, H.N., Katz, S.: Improved test for closed loops in surface intersections. Comput. Aided Des. 21(8), 505–508 (1989)

    Article  Google Scholar 

  26. Sharma, R., Sha, O.P.: A tracing method for parametric Bezier triangular surface/plane intersection. Int. J. Comput. Appl. Technol. 28(4), 240–253 (2005)

    Article  Google Scholar 

  27. Sheng, B., Li, P., Fu, H., Ma, L., Wu, E.: Efficient non-incremental constructive solid geometry evaluation for triangular meshes. Graph. Models 97, 1–16 (2018)

    Article  MathSciNet  Google Scholar 

  28. Sheng, B., Liu, B., Li, P., Fu, H., Ma, L., Wu, E.: Accelerated robust Boolean operations based on hybrid representations. Comput. Aided Geom. Des. 62, 133–153 (2018)

    Article  MathSciNet  Google Scholar 

  29. Wang, W., Pottmann, H., Liu, Y.: Fitting B-spline curves to point clouds by curvature-based squared distance minimization. ACM Trans. Graph. (ToG) 25(2), 214–238 (2006)

    Article  Google Scholar 

  30. Zheng, W., Bo, P., Liu, Y., Wang, W.: Fast B-spline curve fitting by L-BFGS. Comput. Aided Geom. Des. 29(7), 448–462 (2012)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science and Technology, Harbin Institute of Technology, Weihai, China

    Pengbo Bo & Qingxiang Liu

  2. School of Software, Shandong University, Jinan, China

    Caiming Zhang

Authors
  1. Pengbo Bo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Qingxiang Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Caiming Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

PB conceptualized and designed the study, formulated the research framework, and played a key role in data analysis and manuscript writing. QL contributed to method implementation and conducted experiments. CZ reviewed and provided feedback on the manuscript.

Corresponding author

Correspondence to Pengbo Bo.

Ethics declarations

Conflict of interest

The authors declare no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supported by the National Natural Science Foundation of China (62072139) and the Joint Funds of the National Natural Science Foundation of China (U22A2033).

Supplementary Information

Below is the link to the electronic supplementary material.

Supplementary file 1 (zip 12248 KB)

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bo, P., Liu, Q. & Zhang, C. Topological structure extraction for computing surface–surface intersection curves. Vis Comput (2024). https://doi.org/10.1007/s00371-024-03616-8

Download citation

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00371-024-03616-8

Keywords