Skip to main content
SpringerLink
Log in

3D medial axis point approximation using nearest neighbors and the normal field

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

Abstract

We present a novel method to approximate medial axis points given a set of points sampled from a surface and the normal vectors to the surface at those points. For each sample point, we find its maximal tangent ball containing no other sample points, by iteratively reducing its radius using nearest neighbor queries. We prove that the center of the ball constructed by our algorithm converges to a true medial axis point as the sampling density increases to infinity. We also propose a simple heuristic to handle noisy samples. By simple extensions, our method is applied to medial axis point simplification, local feature size estimation and feature-sensitive point decimation. Our algorithm is simple, easy to implement, and suitable for parallel computation using GPU because the iteration process for each sample point runs independently. Experimental results show that our method is efficient both in time and in space.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Amenta, N., Bern, M.W.: Surface reconstruction by Voronoi filtering. Discrete Comput. Geom. 22, 481–504 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  2. Amenta, N., Choi, S., Kolluri, R.K.: The power crust. In: Symposium on Solid Modeling and Applications, pp. 249–266 (2001)

    Google Scholar 

  3. Amenta, N., Choi, S., Kolluri, R.K.: The power crust, unions of balls, and the medial axis transform. Comput. Geom. Theory Appl. 19(2–3), 127–153 (2001)

    MATH  MathSciNet  Google Scholar 

  4. Attali, D., Boissonnat, J.-D., Edelsbrunner, H.: Stability and computation of medial axes—a state-of-the-art report. In: Mller, T., Hamann, B., Russell, B. (eds.) Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration. Springer, Berlin (2007)

    Google Scholar 

  5. Attali, D., Montanvert, A.: Computing and simplifying 2D and 3D continuous skeletons. Comput. Vis. Image Underst. 67(3), 261–273 (1997)

    Article  Google Scholar 

  6. Bentley, J.L.: K-d trees for semidynamic point sets. In: Proc. 6th ACM Symposium on Computational Geometry, pp. 187–197 (1990)

    Chapter  Google Scholar 

  7. Blum, H.: A transformation for extracting new descriptors of shape. In: Models for the Perception of Speech and Visual Form, pp. 362–380. MIT Press, Cambridge (1967)

    Google Scholar 

  8. Chang, M.-C., Kimia, B.B.: Regularizing 3D medial axis using medial scaffold transforms. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1–8. IEEE Computer Society, Los Alamitos (2008)

    Google Scholar 

  9. Chang, M.-C., Kimia, B.B.: Measuring 3d shape similarity by matching the medial scaffolds. In: Proceedings of the 3-D Digital Imaging and Modeling (3DIM), pp. 1473–1480. IEEE Computer Society, Los Alamitos (2009)

    Google Scholar 

  10. Choi, H.I., Choi, S.W., Moon, H.P.: Mathematical theory of medial axis transform. Pac. J. Math. 181(1), 57–88 (1997)

    Article  MathSciNet  Google Scholar 

  11. Choi, S., Amenta, N.: Delaunay triangulation programs on surface data. In: Proceedings of the 12th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 135–136 (2002)

    Google Scholar 

  12. Choset, H.: Incremental construction of the generalized Voronoi diagram, the generalized Voronoi graph, and the hierarchical generalized Voronoi graph. In: 1st CGC Workshop on Computational Geometry (1997)

    Google Scholar 

  13. Culver, T., Keyser, J., Manocha, D.: Exact computation of the medial axis of a polyhedron. Comput. Aided Geom. Des. 21, 65–98 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  14. Dey, T.K., Giesen, J., Hudson, J.: Decimating samples for mesh simplification. In: Proc. 13th Canadian Conference on Computational Geometry, pp. 85–98 (2001)

    Google Scholar 

  15. Dey, T.K., Zhao, W.: Approximate medial axis as a Voronoi subcomplex. In: Symposium on Solid Modeling and Application, pp. 356–366 (2002)

    Google Scholar 

  16. Dey, T.K., Zhao, W.: Approximating the medial axis from the Voronoi diagram with a convergence guarantee. Algorithmica 38(1), 179–200 (2003)

    Article  MathSciNet  Google Scholar 

  17. Etzion, M., Rappoport, A.: Computing the Voronoi diagram of a 3-D polyhedron by separate computation of its symbolic and geometric parts. In: Solid Modeling ’99 (1999)

    Google Scholar 

  18. Etzion, M., Rappoport, A.: Computing Voronoi skeletons of a 3D polyhedron by space subdivision. Technical report, Hebrew University (1999)

  19. Foskey, M., Lin, M., Manocha, D.: Efficient computation of a simplified medial axis. In: Proc. ACM Symposium on Solid Modeling and Applications, pp. 96–107 (2003)

    Chapter  Google Scholar 

  20. Friedman, J.H., Bentley, J.L., Findel, R.A.: An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw. 3(3), 209–226 (1977)

    Article  MATH  Google Scholar 

  21. Guibas, L., Holleman, R., Kavraki, L.E.: A probabilistic roadmap planner for flexible objects with a workspace medial-axis-based sampling approach. In: IEEE/RSJ Proc. of the Int. Conf. on Intelligent Robots and Systems (1999)

    Google Scholar 

  22. Gursoy, H.N., Patrikalakis, N.M.: Automated interrogation and adaptive subdivision of shape using medial axis transform. Adv. Eng. Softw. Workstn. 13(5/6), 287–302 (1991)

    Article  Google Scholar 

  23. Hoff, K.E., Keyser, J., Lin, M., Manocha, D., Culver, T.: Fast computation of generalized Voronoi diagrams using graphics hardware. Comput. Graph. 33, 277–286 (1999)

    Google Scholar 

  24. Holleman, C., Kavraki, L.E.: A framework for using the workspace medial axis in PRM planners. In: Proc. International Conference on Robotics and Automation, pp. 1408–1413 (1997)

    Google Scholar 

  25. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., Stuetzle, W.: Surface reconstruction from unorganized points. Comput. Graph. 26(2), 71–78 (1992)

    Article  Google Scholar 

  26. Lam, L., Lee, S.W., Chen, C.Y.: Thinning methodologies—a comprehensive survey. IEEE Trans. Pattern Anal. Mach. Intell. 14(9), 869–885 (1992)

    Article  Google Scholar 

  27. Leymarie, F.F., Kimia, B.B.: The medial scaffold of 3D unorganized point clouds. IEEE Trans. Pattern Anal. Mach. Intell. 29(2), 313–330 (2007)

    Article  Google Scholar 

  28. Ma, C., Sonka, M.: A fully parallel 3D thinning algorithm. Comput. Vis. Image Underst. 64(3), 420–433 (1996)

    Article  Google Scholar 

  29. Niblak, C., Gibbons, P., Capson, D.: Generating skeletons and centerlines from the distance transform. CVGIP, Graph. Models Image Process. 54(5), 420–437 (1992)

    Article  Google Scholar 

  30. Ogniewicz, R.L.: Skeleton-space: A multiscale shape description combining region and boundary information. In: Proceedings of Computer Vision and Pattern Recognition, pp. 746–751 (1994)

    Google Scholar 

  31. Pauly, M., Keiser, R., Gross, M.: Multi-scale feature extraction on point-sampled surfaces. Comput. Graph. Forum 22(3), 281–290 (2003)

    Article  Google Scholar 

  32. Reddy, J.M., Turkiyyah, G.M.: Computation of 3D skeletons using a generalized Delaunay triangulation technique. Comput. Aided Des. 27, 677–694 (1995)

    Article  MATH  Google Scholar 

  33. Shapira, L., Shamir, A., Cohen-Or, D.: Consistent mesh partitioning and skeletonization using the shape diameter function. Vis. Comput. 24(4), 249–259 (2008)

    Article  Google Scholar 

  34. Sheehy, D., Armstrong, C., Robinson, D.: Shape description by medial axis construction. IEEE Trans. Vis. Comput. Graph. 2, 62–72 (1996)

    Article  Google Scholar 

  35. Sheffer, A., Etzion, M., Rappoport, A., Bercovier, M.: Hexahedral mesh generation using the embedded Voronoi graph. Eng. Comput. 15(3), 248–262 (1999)

    Article  MATH  Google Scholar 

  36. Sherbrooke, E., Patrikalakis, N.M., Wolter, F.E.: Differential and topological properties of medial axis transforms. Graph. Models Image Process. 58(6), 574–592 (1996)

    Article  Google Scholar 

  37. Sherbrooke, E.C., Patrikalakis, N.M., Brisson, E.: Computation of the medial axis transform of 3D polyhedral. In: Symposium on Solid Modeling and Applications, pp. 187–200 (1995)

    Chapter  Google Scholar 

  38. Siddiqi, K., Pizer, S.: Medial Representations: Mathematics, Algorithms and Applications. Springer, Berlin (2008)

    MATH  Google Scholar 

  39. Vidal, S.F., Bardinet, E., Malandain, G., Damas, S., de la Blanca Capilla, N.P.: Object representation and comparison inferred from its medial axis. Proc. Int. Conf. Pattern Recognit. 1, 1712 (2000)

    Google Scholar 

  40. Vleugels, J., Overmars, M.: Approximating generalized Voronoi diagrams in any dimension. Int. J. Comput. Geom. Its Appl. 8, 201–221 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  41. Wilmarth, S.A., Amato, N.M., Stiller, P.F.: Motion planning for a rigid body using random networks on the medial axis of the free space. In: ACM Symp. on Computational Geometry, pp. 173–180 (1999)

    Google Scholar 

  42. Wolter, F.: Cut locus and medial axis in global shape interrogation and representation. Technical report, 1992, MIT Design Lab. Report 92-2, MIT sea grant report, MIT-T-93-002, US National Sea Grant Library (1993)

  43. Wolter, F.E., Friese, K.I.: Local and global geometric methods for analysis interrogation, reconstruction, modification and designs of shapes. In: Proc. of Computer Graphics International 2000, pp. 137–151. IEEE Computer Society, Los Alamitos (2000)

    Chapter  Google Scholar 

  44. Yang, Y., Brock, O., Moll, R.N.: Efficient and robust computation of an approximated medial axis. In: Proc. of the ACM Symposium on Solid Modeling and Applications, pp. 15–24 (2004)

    Google Scholar 

  45. Zhou, K., Hou, Q., Wang, R., Guo, B.: Real-time KD-tree construction on graphics hardware. ACM Trans. Graph. 27(5), 1–11 (2008)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. KAIST, Daejeon, South Korea

    Jaehwan Ma & Sunghee Choi

  2. Kyouggi University, Suwon, South Korea

    Sang Won Bae

Authors
  1. Jaehwan Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sang Won Bae
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sunghee Choi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sunghee Choi.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ma, J., Bae, S.W. & Choi, S. 3D medial axis point approximation using nearest neighbors and the normal field. Vis Comput 28, 7–19 (2012). https://doi.org/10.1007/s00371-011-0594-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00371-011-0594-7

Keywords

Search

Navigation