Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Efficient construction of the medial axis for a CAD model using parallel computing

  • Original Article
  • Published:
Engineering with Computers Aims and scope Submit manuscript

Abstract

As a simplified representation of a geometric model, the medial axis (MA) has been used in a wide range of engineering applications. While obtaining the true MA of a complicated CAD model is known to be a difficult task, current research is predominantly focused on computing its approximate MA instead. To improve its quality, this work develops a novel and efficient method for obtaining a high-quality MA composed of MA faces for a CAD model. Specifically, an MA point is computed using a dual-normal-tracing algorithm for each sample point. This algorithm can be implemented through GPU-enabled parallel computing and be executed in an iterative manner until MA points have been found for all sample points. After the iteration is completed, the MA points generated are then converted into the resultant MA by evaluating the topological connectivities of their corresponding sample points. Finally, the resultant MA is converted into MA faces using the information of boundary CAD faces. The proposed method is evaluated by analyzing its complexity and robustness, discussing its applicability and testing its performance in a couple of computational experiments. As shown in the evaluation, this method is easy to implement through exploiting parallel computing and can support effective and high-quality MA generation for a CAD model.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16

Similar content being viewed by others

References

  1. Blum H (1976) A transformation for extracting new descriptors of shape. In: Wathen-Dunn W (ed) Models for the perception of speech and visual form. MIT Press, Cambridge, pp 362–380

  2. Zhang XL, Xia Y, Wang JY et al (2015) Medial axis tree—an internal supporting structure for 3D printing. Comput Aided Geometr Des 35–36:149–162

    Google Scholar 

  3. Cameron S (1990) Collision detection by 4-dimensional intersection testing. IEEE Trans Robot Autom 6(3):291–302

    Article  Google Scholar 

  4. Attali D. (1998) r-Regular shape reconstruction from unorganized points. Comput Geom: Theory Appl 10(4):239–247

    Article  MathSciNet  MATH  Google Scholar 

  5. https://en.wikipedia.org/wiki/Medial_axis

  6. Zhu HS, Liu YS, Bai J et al (2015) Constructive generation of the medial axis for solid models. Comput Aided Des 62:98–111

    Article  Google Scholar 

  7. Zhu HS, Liu YS, Zhao JJ et al (2015) Calculating the medial axis of a CAD model by multi-CPU based parallel computation. Adv Eng Softw 85:96–107

    Article  Google Scholar 

  8. Zhu HS, Liu YS, Zhao JJ (2016) Generation of hierarchical multi-resolution medial axis for CAD models. Adv Eng Softw 94:20–31

    Article  Google Scholar 

  9. Foskey M, Lin MC, Manocha D (2003) Efficient computation of a simplified medial axis. In: Proceedings of the eighth ACM symposium on solid modeling and applications, pp 96–107

  10. Ma J, Bae SW, Cho S (2012) 3D medial axis point approximation using nearest neighbors and the normal field. Vis Comput 28(1):7–19

    Article  Google Scholar 

  11. Ramanathan M, Gurumoorthy B (2010) Interior medial axis computation of 3D objects bound by free-form surfaces. Comput Aided Des 42(12):1217–1231

    Article  Google Scholar 

  12. Attali D, Boissonnat JD, Edelsbrunner H (2009) Stability and computation of the medial axes—a state-of-the-art report. In: Möller T, Hamann B, Russell RD (eds) Mathematical foundations of scientific visualization, computer graphics, and massive data exploration, mathematics and vizualization. Springer, Berlin, pp 109–125

  13. Siddiqi K, Pizer SM (2008) Medial representations: mathematics, algorithms and applications. Springer, Berlin

    Book  MATH  Google Scholar 

  14. Biasotti S, Attali D, Boissonnat JD et al (2008) Keletal structures, shape analysis and structuring, In: De Floriani L, Spagnuolo M (eds) Shape analysis and structuring. Mathematics and visualization. Springer, Berlin, Heidelberg, pp 145–183

  15. Elber G, Cohen E, Drake S (2005) MATHSM: medial axis transform toward high speed machining of pockets. Comput-Aided Des 37(2):241–250

    Article  Google Scholar 

  16. Hanniel I, Elber G (2009) Computing the Voronoi cells of planes, spheres and cylinders in R2. Comput Aided Geom Des 26(6):695–710

    Article  MATH  Google Scholar 

  17. Ma J, Choi S (2014) Kinematic skeleton extraction from 3D articulated models. Comput-Aided Des 46(1):221–226

    Article  Google Scholar 

  18. Tanase M, Veltkamp RC (2004) A straight skeleton approximating the medial axis. In: ESA, pp 809–821

  19. Au C (2013) A simple algorithm for medial axis transform computation. Eng Comput 29:139–149

    Article  Google Scholar 

  20. Chen ZC, Fu Q (2014) An efficient, accurate approach to medial axis transforms of pockets with closed free-form boundaries. Eng Comput 30(1):111–123

    Article  MathSciNet  Google Scholar 

  21. Dey TK, Zhao W (2004) Approximate medial axis as a Voronoi subcomplex. Comput-Aided Des 36(2):195–202

    Article  Google Scholar 

  22. Choi HI, Choi SW, Moon HP (1997) Mathematical theory of medial axis transform. Pac J Math 181(1):57–88

    Article  MathSciNet  MATH  Google Scholar 

  23. Lakshmi JK, Punithavalli M (2009) A survey on skeletons in digital image processing. In: International conference on digital image processing, Bangkok, Thailand, March 2007

  24. Lam L, Lee SW, Suen CY (1992) Thinning methodologies—a comprehensive survey. IEEE Trans Pattern Anal Mach Intell 14(9):869–885

    Article  Google Scholar 

  25. Nackman LR (1982) Curvature relations in three-dimensional symmetric axes. Comput Gr Image Process 20:43–57

    Article  MATH  Google Scholar 

  26. Scott GL, Turner SC, Zisserman A (1989) Using a mixed wave diffusion process to elicit the symmetry set. Image Vis Comput 7(1):63–70

    Article  Google Scholar 

  27. Siddiqi K, Bouix S, Tannenbaum A et al (1999) The Hamilton–Jacobi skeleton. In: International conference on computer vision (ICCV), pp 828–834

  28. Vleugels J, Overmars M (1995) Approximating generalized Voronoi diagrams in any dimension. Technical report UU-CS-95-14. Department of Computer Science, Utrecht University

  29. Borgefors G, Nyström I, Sanniti di Baja G. (1999) Computing skeletons in three dimensions. Pattern Recognit 32(7):1225–1236

    Article  Google Scholar 

  30. Borgefors G (1996) On digital distance transforms in three dimensions. Comput Vis Image Underst 64(3):368–376

    Article  Google Scholar 

  31. Viswanathan GK, Murugesan A. Nallaperumal K (2013) A parallel thinning algorithm for contour extraction and medial axis transform. In: 2013 IEEE international conference on emerging trends in computing, communication and nanotechnology, ICE-CCN

  32. Stolpner S, Kry P, Siddiqi K (2012) Medial spheres for shape approximation. IEEE Trans Pattern Anal Mach Intell 34(6):1234–1240

    Article  Google Scholar 

  33. Cao TT, Tang K, Mohamed A et al (2010) Parallel Banding Algorithm to compute exact distance transform with the GPU. In: ACM SIGGRAPH symposium on interactive 3D graphics and games, pp 83–90

  34. Jalba AC, Kustra J (2013) A. C. Telea. Surface and curve skeletonization of large 3D models on the GPU. IEEE Trans Pattern Anal Mach Intell 35(6):1495–1508

    Article  Google Scholar 

  35. Ramanathan M, Gurumoorthy B (2005) Constructing medial axis transform of extruded and revolved 3D objects with free-form boundaries. Comput Aided Des 37(13):1370–1387

    Article  Google Scholar 

  36. Chang YC, Kao JH, Pinilla JM, Dong J, Prinz FB (1998) Medial axis transform (MAT) of general 2D shapes and 3D polyhedra for engineering applications. In: The 6th IFIP working conference on geometric modeling: fundamentals and applications, 7–9 Dec 1998, Tokyo, Japan

  37. Sherbrooke EC, Patrikalakis NM, Brisson E (1995) Computation of MA transform of 3-D polyhedral. In: ACM solid modeling, pp 187–199

  38. Aichholzer O, Aigner W, Aurenhammer F et al (2009) Medial axis computation for planar free_form shapes. Comput Aided Des 41:339–349

    Article  Google Scholar 

  39. Meijster A, Roerdin JBTM, Hesselink WH (2000) A general algorithm for computing distance transforms in linear time. In: Goutsias J, Vincent L, Bloomberg DS (eds) Mathematical morphology and its applications to image and signal processing. Computational imaging and vision, vol 18. Springer, Boston, pp 331–340

  40. Hirata T (1996) A unified linear-time algorithm for computing distance maps. Inf Process Lett 58(3):129–133

    Article  MathSciNet  MATH  Google Scholar 

  41. Ramamurthy R, Farouki T (1999) Voronoi diagram and medial axis algorithm for planar domains with curved boundaries I: theoretical foundations. J Comput Appl Math 102:119–141

    Article  MathSciNet  MATH  Google Scholar 

  42. Chaussard J, Couprie M, Talbot H (2011) Robust skeletonization using the discrete λ-medial axis. Pattern Recognit Lett 32(9):1384–1394

    Article  Google Scholar 

  43. Miklos B, Giesen J, Pauly M (2010) Discrete scale axis representations for 3D geometry. ACM Trans Gr 29:1–10

    Article  Google Scholar 

  44. Sun F, Choi YK, Yu Y et al (2016) Medial meshes—a compact and accurate representation of medial axis transform. IEEE Trans Visual Comput Gr 22(3):1278–1290

    Article  Google Scholar 

  45. Pan L, Bin W, Feng S et al (2015) Q-MAT: computing medial axis transform by quadratic error minimization. ACM Trans Gr 35(1):8

    MathSciNet  Google Scholar 

  46. Piegl LA, Wayne T (1998) Geometry based triangulation of trimmed NURBS surfaces. Comput Aided Des 30(1):11–18

    Article  Google Scholar 

  47. https://en.wikipedia.org/wiki/Quartic_function

  48. Gao W, Gao SM, Liu SM,YS et al (2006) Multiresolutional similarity assessment andretrieval of solid models based on DBMS. Comput Aided Des 38(9):985–1001

    Article  Google Scholar 

Download references

Acknowledgements

The authors appreciate the support from the National Key Technology Support Program (Grant no. 2014BAD04B00), the National Science Foundation of China (Grant nos. 61702074, 61572427 and 61672247), the China Postdoctoral Science Foundation Funded Project (Grant no. 2017M621123) and the Fundamental Research Funds for the Central Universities (Grant nos. 3132017117).

Author information

Authors and Affiliations

  1. Information Science and Technology College, Dalian Maritime University, Dalian, 116026, People’s Republic of China

    Housheng Zhu

  2. State Key Laboratory of CAD&CG, Zhejiang University, Hangzhou, 310027, People’s Republic of China

    Yusheng Liu

  3. School of Engineering, University of Portsmouth, Portsmouth, PO1 3DJ, UK

    Hongwei Wang

  4. School of Mechanical Science and Engineering, HUST, Wuhan, 430074, People’s Republic of China

    Jianjun Zhao

Authors
  1. Housheng Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yusheng Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hongwei Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jianjun Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Yusheng Liu or Jianjun Zhao.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhu, H., Liu, Y., Wang, H. et al. Efficient construction of the medial axis for a CAD model using parallel computing. Engineering with Computers 34, 413–429 (2018). https://doi.org/10.1007/s00366-017-0549-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00366-017-0549-3

Keywords

Search

Navigation