{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T04:59:22Z","timestamp":1768453162789,"version":"3.49.0"},"reference-count":36,"publisher":"ASME International","issue":"4","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2003,12,1]]},"abstract":"<jats:p>The computation and application of the medial axis have been limited because of its instability and algebraic complexity. In this paper, we use a simplification of the medial axis, the \u03b8-SMA, that is parameterized by a separation angle formed by the vectors connecting a point on the medial axis to the closest points on the boundary. We formally characterize the degree of simplification of the \u03b8-SMA as a function of \u03b8. We present a fast algorithm to compute an approximation of the \u03b8-SMA. It relies on computation of the distance field and its gradient using graphics hardware. The complexity of the algorithm varies based on resolution of the volume discretization and is a linear function of the input size. We have applied this algorithm to approximate the SMA of complex models composed of tens or hundreds of thousands of triangles. On a 2-GHz PC, its running time varies from a few seconds, for a model consisting of hundreds of triangles, to minutes for highly complex models.<\/jats:p>","DOI":"10.1115\/1.1631582","type":"journal-article","created":{"date-parts":[[2003,12,24]],"date-time":"2003-12-24T23:00:38Z","timestamp":1072306838000},"page":"274-284","update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":43,"title":["Efficient Computation of A Simplified Medial Axis"],"prefix":"10.1115","volume":"3","author":[{"given":"Mark","family":"Foskey","sequence":"first","affiliation":[{"name":"Department of Radiology, University of North Carolina at Chapel Hill, Chapel Hill, NC\u200927599-7515"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ming C.","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC\u200927599-7515"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dinesh","family":"Manocha","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC\u200927599-7515"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2003,12,24]]},"reference":[{"key":"2019100520131878700_r1","unstructured":"Blum, H., 1967, \u201cA Transformation for Extracting New Descriptors of Shape,\u201d Models for the Perception of Speech and Visual Form, W. Wathen-Dunn, Ed. MIT Press, pp. 362\u2013380."},{"key":"2019100520131878700_r2","doi-asserted-by":"crossref","unstructured":"Amenta, N., Choi, S., and Kolluri, R., 2001, \u201cThe Power Crust,\u201d Proc. ACM Symposium on Solid Modeling and Applications, pp. 249\u2013260.","DOI":"10.1145\/376957.376986"},{"key":"2019100520131878700_r3","doi-asserted-by":"crossref","unstructured":"Dey, T. K., and Zhao, W., 2002, \u201cApproximate Medial Axis as a Voronoi Subcomplex,\u201d Proc. ACM Symposium on Solid Modeling and Applications, pp. 356\u2013366.","DOI":"10.1145\/566282.566333"},{"key":"2019100520131878700_r4","doi-asserted-by":"crossref","unstructured":"Storti, D. W., Turkiyyah, G. M., Ganter, M. A., Lim, C. T., and Stal, D. M., 1997, \u201cSkeleton-Based Modeling Operations on Solids,\u201d Proc. ACM Symposium on Solid Modeling and Applications, pp. 141\u2013154.","DOI":"10.1145\/267734.267771"},{"key":"2019100520131878700_r5","doi-asserted-by":"crossref","unstructured":"Lam, L., Lee, S.-W., and Chen, C. Y., 1992, \u201cThinning Methodologies\u2014A Comprehensive Survey,\u201d IEEE Trans. Pattern Anal. Mach. Intell., 14(9), pp. 869\u2013885.","DOI":"10.1109\/34.161346"},{"key":"2019100520131878700_r6","doi-asserted-by":"crossref","unstructured":"Zhang, Y. Y., and Wang, P. S. P., 1993, \u201cAnalytical Comparison of Thinning Algorithms,\u201d Int. J. Pattern Recognit. Artif. Intell., 7, pp. 1227\u20131246.","DOI":"10.1142\/S0218001493000601"},{"key":"2019100520131878700_r7","doi-asserted-by":"crossref","unstructured":"Danielsson, P. E.\n          , 1980, \u201cEuclidean Distance Mapping,\u201d Computer Graphics and Image Processing, 14, pp. 227\u2013248.","DOI":"10.1016\/0146-664X(80)90054-4"},{"key":"2019100520131878700_r8","doi-asserted-by":"crossref","unstructured":"Ragnemalm, I.\n          , 1993, \u201cThe Euclidean Distance Transformation in Arbitrary Dimensions,\u201d Pattern Recogn. Lett., 14, pp. 883\u2013888.","DOI":"10.1016\/0167-8655(93)90152-4"},{"key":"2019100520131878700_r9","unstructured":"Vleugels, J., and Overmars, M., 1995, Approximating generalized Voronoi diagrams in any dimension, Tech. Rep. UU-CS-1995-14, Department of Computer Science, Utrecht University."},{"key":"2019100520131878700_r10","doi-asserted-by":"crossref","unstructured":"Hoff, K., Culver, T., Keyser, J., Lin, M., and Manocha, D., 1999, \u201cFast Computation of Generalized Voronoi Diagrams Using Graphics Hardware,\u201d Proc. ACM SIGGRAPH, pp. 277\u2013286.","DOI":"10.1145\/311535.311567"},{"key":"2019100520131878700_r11","doi-asserted-by":"crossref","unstructured":"Siddiqi, K., Bouix, S., Tannenbaum, A., and Zucker, S. W., 1999, \u201cThe Hamilton-Jacobi Skeleton,\u201d International Conference on Computer Vision, pp. 828\u2013834.","DOI":"10.1109\/ICCV.1999.790307"},{"key":"2019100520131878700_r12","doi-asserted-by":"crossref","unstructured":"Etzion, M., and Rappoport, A., 1999, \u201cComputing the Voronoi Diagram of a 3-D Polyhedron by Separate Computation of its Symbolic and Geometric Parts,\u201d Proc. ACM Symposium on Solid Modeling and Applications, pp. 167\u2013178.","DOI":"10.1145\/304012.304029"},{"key":"2019100520131878700_r13","unstructured":"Milenkovic, V., 1993, \u201cRobust Construction of the Voronoi Diagram of a Polyhedron,\u201d Proc. 5th Canad. Conf. Comput. Geom., pp. 473\u2013478."},{"key":"2019100520131878700_r14","doi-asserted-by":"crossref","unstructured":"Reddy, J., and Turkiyyah, G., 1995, \u201cComputation of 3D Skeletons Using a Generalized Delaunay Triangulation Technique,\u201d Comput.-Aided Des., 27, pp. 677\u2013694.","DOI":"10.1016\/0010-4485(94)00025-9"},{"key":"2019100520131878700_r15","unstructured":"Chiang, C.-S., 1992, \u201cThe Euclidean distance transform,\u201d Ph.D. Thesis, Dept. Comput. Sci., Purdue Univ., West Lafayette, IN, Aug, Report CSD-TR 92-050."},{"key":"2019100520131878700_r16","doi-asserted-by":"crossref","unstructured":"Sherbrooke, E. C., Patrikalakis, N. M., and Brisson, E., 1995, \u201cComputation of the Medial Axis Transform of 3-D Polyhedra,\u201d Proc. ACM Symposium on Solid Modeling and Applications, pp. 187\u2013199.","DOI":"10.1145\/218013.218059"},{"key":"2019100520131878700_r17","doi-asserted-by":"crossref","unstructured":"Culver, T. Keyser, J., and Manocha, D., 1999, \u201cAccurate Computation of the Medial Axis of a Polyhedron,\u201d Proc. ACM Symposium on Solid Modeling and Applications, pp. 179\u2013190.","DOI":"10.1145\/304012.304030"},{"key":"2019100520131878700_r18","doi-asserted-by":"crossref","unstructured":"Dutta, D., and Hoffmann, C. M., 1990, \u201cA Geometric Investigation of the Skeleton of CSG Objects,\u201d Proc. ASME Conf. Design Automation.","DOI":"10.21236\/ADA229292"},{"key":"2019100520131878700_r19","unstructured":"Hoffmann, C. M., 1990, \u201cHow to Construct the Skeleton of CSG Objects,\u201d Proc. 4th IMA Conf. on the Mathematics of Surfaces, Oxford University Press."},{"key":"2019100520131878700_r20","doi-asserted-by":"crossref","unstructured":"Boissonnat, J.-D.\n          , 1984, \u201cGeometric Structures for Three-Dimensional Shape Representation,\u201d ACM Trans. Graphics, 3(4), pp. 266\u2013286.","DOI":"10.1145\/357346.357349"},{"key":"2019100520131878700_r21","doi-asserted-by":"crossref","unstructured":"Dey, T. K., and Zhao, W., 2002, \u201cApproximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee,\u201d European Symposium on Algorithms, pp. 387\u2013398.","DOI":"10.1007\/3-540-45749-6_36"},{"key":"2019100520131878700_r22","doi-asserted-by":"crossref","unstructured":"Turkiyyah, G. M., Storti, D. W., Ganter, M., Chen, H., and Vimawala, M., 1997, \u201cAn Accelerated Triangulation Method for Computing the Skeletons of Free-Form Solid Models,\u201d Comput.-Aided Des., 29(1), pp. 5\u201319.","DOI":"10.1016\/S0010-4485(96)00036-X"},{"key":"2019100520131878700_r23","doi-asserted-by":"crossref","unstructured":"Attali, D., and Boissonnat, J., 2002, \u201cA Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces,\u201d Proc. ACM Symposium on Solid Modeling and Applications, pp. 139\u2013146.","DOI":"10.1145\/566282.566304"},{"key":"2019100520131878700_r24","doi-asserted-by":"crossref","unstructured":"August, J., Tannenbaum, A., and Zucker, S., 1999, \u201cOn the Evolution of the Skeleton,\u201d Proc. of Int. Conf. on Computer Vision.","DOI":"10.1109\/ICCV.1999.791236"},{"key":"2019100520131878700_r25","doi-asserted-by":"crossref","unstructured":"Attali, D., and Montanvert, A., 1997, \u201cComputing and Simplifying 2D and 3D Continuous Skeletons,\u201d Comput. Vis. Image Underst., 67(3), pp. 261\u2013273.","DOI":"10.1006\/cviu.1997.0536"},{"key":"2019100520131878700_r26","doi-asserted-by":"crossref","unstructured":"Boissonnat, J.-D., and Cazals, F., 2000, \u201cSmooth Surface Reconstruction Via Natural Neighbor Interpolation of Distance Functions,\u201d Proc. ACM Symposium on Computational Geometry, pp. 223\u2013232.","DOI":"10.1145\/336154.336208"},{"key":"2019100520131878700_r27","doi-asserted-by":"crossref","unstructured":"Styner, M., Gerig, G., Joshi, S., and Pizer, S., 2003, \u201cAutomatic and Robust Computation of 3D Medial Models Incorporating Object Variability,\u201d Int. J. Comput. Vis. 55, pp. 107\u2013122.","DOI":"10.1023\/A:1026378916288"},{"key":"2019100520131878700_r28","doi-asserted-by":"crossref","unstructured":"Choi, S. W., and Seidel, H.-P., 2002, \u201cLinear Onesided Stability of MAT for Weakly Injective 3D Domain,\u201d Proc. ACM Symposium on Solid Modeling and Applications, pp. 344\u2013355.","DOI":"10.1145\/566282.566332"},{"key":"2019100520131878700_r29","unstructured":"Larsen, E., Gottschalk, S., Lin, M., and Manocha, D., 1999, \u201cFast Proximity Queries with Swept Sphere Volumes,\u201d Tech. Rep. TR99-018, Department of Computer Science, University of North Carolina. 32 pages."},{"key":"2019100520131878700_r30","doi-asserted-by":"crossref","unstructured":"Taubin, G., 1995, \u201cA Signal Processing Approach to Fair Surface Design,\u201d Proc. ACM SIGGRAPH, pp. 351\u2013358.","DOI":"10.1145\/218380.218473"},{"key":"2019100520131878700_r31","doi-asserted-by":"crossref","unstructured":"Wilmarth, S. A., Amato, N. M., and Stiller, P. F., 1999, \u201cMotion Planning for a Rigid Body Using Random Networks on the Medial Axis of the Free Space,\u201d Proc. ACM Symposium on Computational Geometry, pp. 173\u2013180.","DOI":"10.1145\/304893.304967"},{"key":"2019100520131878700_r32","doi-asserted-by":"crossref","unstructured":"Choi, H. I., Choi, S. W., and Moon, H. P., 1997, \u201cMathematical Theory of Medial Axis Transform,\u201d Pac. J. Math., 181(1), pp. 56\u201388.","DOI":"10.2140\/pjm.1997.181.57"},{"key":"2019100520131878700_r33","unstructured":"Donaghy, R. J., McCune, W., Bridgett, S. J., Armstrong, C. G., Robinson, D. J., and McKeag, R. M., 1996, \u201cDimensional Reduction of Analysis Models,\u201d 5th International Meshing Roundtable, pp. 307\u2013320."},{"key":"2019100520131878700_r34","doi-asserted-by":"crossref","unstructured":"Suresh, K., 2003, \u201cAutomating the CAD\/CAE Dimensional Reduction Process,\u201d Proc. ACM Symposium on Solid Modeling and Applications, pp. 76\u201385.","DOI":"10.1145\/781606.781621"},{"key":"2019100520131878700_r35","unstructured":"Armstrong, C. G., Robinson, D. J., McKeag, R. M., Li, T. S., Bridgett, S. J., Donaghy, R. J., and McGleenan, C. A., 1995, \u201cMedials for Meshing and More,\u201d 4th International Meshing Roundtable, pp. 277\u2013288."},{"key":"2019100520131878700_r36","unstructured":"Quadros, W. R., Ramaswami, K., Prinz, F. B., and Gurumoorthy, B., 2000, \u201cLayTracks: A New Approach to Automated Quadrilateral Mesh Generation using MAT,\u201d 9th International Meshing Roundtable, pp. 239\u2013250."}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/3\/4\/274\/5525436\/274_1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/3\/4\/274\/5525436\/274_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,6]],"date-time":"2019-10-06T00:13:34Z","timestamp":1570320814000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/3\/4\/274\/445322\/Efficient-Computation-of-A-Simplified-Medial-Axis"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,12,1]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2003,12,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.1631582","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"value":"1530-9827","type":"print"},{"value":"1944-7078","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,12,1]]}}}