{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T12:43:50Z","timestamp":1753879430025,"version":"3.41.2"},"reference-count":34,"publisher":"ASME International","issue":"2","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2010,6,1]]},"abstract":"<jats:p>This paper considers the problem of inferring the geometry of an object from values of the signed distance sampled on a uniform grid. The problem is motivated by the desire to effectively and efficiently model objects obtained by 3D imaging technology such as magnetic resonance, computed tomography, and positron emission tomography. Techniques recently developed for automated segmentation convert intensity to signed distance, and the voxel structure imposes the uniform sampling grid. The specification of the signed distance function (SDF) throughout the ambient space would provide an implicit and function-based representation (f-rep) model that uniquely specifies the object, and we refer to this particular f-rep as the signed distance function representation (SDF-rep). However, a set of uniformly sampled signed distance values may uniquely determine neither the distance function nor the shape of the object. Here, we employ essential properties of the signed distance to construct the upper and lower bounds on the allowed variation in signed distance, which combine to produce interval-valued extensions of the signed distance function. We employ an interval extension of the signed distance function as an interval SDF-rep that defines the range of object geometries that are consistent with the sampled SDF data. The particular interval extensions considered include a tight global extension and more computationally efficient local extensions that provide useful criteria for root exclusion\/isolation. To illustrate a useful application of the interval bounds, we present a reliable approach to top-down octree membership classification for uniform samplings of signed distance functions.<\/jats:p>","DOI":"10.1115\/1.3428736","type":"journal-article","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T22:22:04Z","timestamp":1276035724000},"update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":2,"title":["Interval Extensions of Signed Distance Functions: iSDF-reps and Reliable Membership Classification"],"prefix":"10.1115","volume":"10","author":[{"given":"Duane","family":"Storti","sequence":"first","affiliation":[{"name":"Department of Mechanical Engineering, University of Washington, Seattle, WA 98195-2600"}]},{"given":"Chris","family":"Finley","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engineering, University of Washington, Seattle, WA 98195-2600"}]},{"given":"Mark","family":"Ganter","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engineering, University of Washington, Seattle, WA 98195-2600"}]}],"member":"33","published-online":{"date-parts":[[2010,6,8]]},"reference":[{"first-page":"279","volume-title":"Computer Vision","author":"Shapiro","key":"2019100513021014100_c1"},{"author":"Bulu","key":"2019100513021014100_c2","article-title":"Comparison of 3D Segmentation Algorithms for Medical Imaging"},{"volume-title":"Geometric and Solid Modeling: An Introduction","author":"Hoffmann","key":"2019100513021014100_c3"},{"volume-title":"Principles of CAD\/CAM\/CAE Systems","author":"Lee","key":"2019100513021014100_c4"},{"key":"2019100513021014100_c5","first-page":"29","article-title":"Volume Modeling","volume-title":"Volume Graphics","author":"Nielsen"},{"volume-title":"Introduction to Implicit Surfaces","author":"Bloomenthal","key":"2019100513021014100_c6"},{"key":"2019100513021014100_c7","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0167-8396(94)90030-2","article-title":"Real Functions for Representation of Rigid Solids","volume":"11","author":"Shapiro","journal-title":"Comput. Aided Geom. Des.","ISSN":"https:\/\/id.crossref.org\/issn\/0167-8396","issn-type":"print"},{"issue":"2","key":"2019100513021014100_c8","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1093\/comjnl\/16.2.157","article-title":"A Constructive Geometry for Computer Graphics","volume":"16","author":"Ricci","journal-title":"Comput. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-4620","issn-type":"print"},{"issue":"5\u20136","key":"2019100513021014100_c9","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1142\/S0218195998000266","article-title":"Implicit Methods for Geometry Creation","volume":"8","author":"Ensz","journal-title":"Int. J. Comput. Geom. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0218-1959","issn-type":"print"},{"key":"2019100513021014100_c10","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/BF02464333","article-title":"Function Representation in Geometric Modeling: Concepts, Implementation and Applications","volume":"11","author":"Pasko","journal-title":"Image Vis. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0262-8856","issn-type":"print"},{"article-title":"Artifact vs. Anatomy: Dealing With Conflict of Geometric Modeling Descriptions","author":"Storti","key":"2019100513021014100_c11","doi-asserted-by":"crossref","DOI":"10.4271\/2007-01-2450"},{"article-title":"Wavelet SDF-Reps: Solid Modeling With Volumetric Scans","author":"Storti","key":"2019100513021014100_c12","doi-asserted-by":"crossref","DOI":"10.1115\/DETC2007-34703"},{"key":"2019100513021014100_c13","first-page":"133","article-title":"Image Segmentation and Registration for the Analysis of Joint Motion From 3D MRI","volume":"6141","author":"Hu","journal-title":"Proc. SPIE","ISSN":"https:\/\/id.crossref.org\/issn\/0277-786X","issn-type":"print"},{"edition":"2nd ed.","volume-title":"Level Set Methods and Fast Marching Methods","author":"Sethian","key":"2019100513021014100_c14"},{"volume-title":"Level Set Methods and Dynamic Implicit Surfaces","author":"Osher","key":"2019100513021014100_c15","doi-asserted-by":"crossref","DOI":"10.1007\/b98879"},{"volume-title":"Wavelets","author":"Daubechies","key":"2019100513021014100_c16"},{"volume-title":"Wavelet Analysis: The Scalable Structure of Information","author":"Resnikoff","key":"2019100513021014100_c17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0593-7"},{"volume-title":"Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS","author":"Samet","key":"2019100513021014100_c18"},{"key":"2019100513021014100_c19","doi-asserted-by":"crossref","DOI":"10.1016\/B978-0-08-050754-5.50049-9","article-title":"Quadtree\/Octree-to-Boundary Conversion","volume-title":"Graphics Gems II","author":"Montani"},{"key":"2019100513021014100_c20","first-page":"199","article-title":"Distance Field Compression","volume":"1-3","author":"Jones","journal-title":"Journal of WSCG"},{"issue":"2","key":"2019100513021014100_c21","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.cad.2005.06.004","article-title":"Field Modeling With Sampled Distances","volume":"38","author":"Freytag","journal-title":"Comput.-Aided Des.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-4485","issn-type":"print"},{"first-page":"249","article-title":"Adaptively Sampled Distance Fields: A General Representation of Shape for Computer Graphics","author":"Frisken","key":"2019100513021014100_c22"},{"first-page":"51","volume-title":"Implicit Objects in Computer Graphics","author":"Velho","key":"2019100513021014100_c23"},{"issue":"3","key":"2019100513021014100_c24","doi-asserted-by":"publisher","first-page":"545","DOI":"10.2307\/1969908","article-title":"Elementary Structure of Real Algebraic Varieties","volume":"66","author":"Whitney","journal-title":"Ann. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"key":"2019100513021014100_c25","first-page":"362","article-title":"A Transformation for Extracting New Descriptors of Shape","volume-title":"Models for the Perception of Speech and Visual Form","author":"Blum"},{"key":"2019100513021014100_c26","unstructured":"Wolter, F. -E. , 1995, \u201cCut Locus and Medial Axis in Global Shape Interrogation and Representation,\u201d MIT, Department of Ocean Engineering, Design Laboratory Memorandum 92-2."},{"first-page":"141","article-title":"Skeleton-Based Modeling Operations on Solids","author":"Storti","key":"2019100513021014100_c27"},{"issue":"4","key":"2019100513021014100_c28","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1109\/TVCG.2006.56","article-title":"3D Distance Fields: A Survey of Techniques and Applications","volume":"12","author":"Jones","journal-title":"IEEE Trans. Vis. Comput. Graph.","ISSN":"https:\/\/id.crossref.org\/issn\/1077-2626","issn-type":"print"},{"article-title":"Interval Method for Interrogation of Implicit Solid Models","author":"Chang","key":"2019100513021014100_c29","doi-asserted-by":"crossref","DOI":"10.1115\/DETC2000\/DAC-14290"},{"volume-title":"Methods and Applications of Interval Analysis","author":"Moore","key":"2019100513021014100_c30","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970906"},{"volume-title":"Global Optimization Using Interval Arithmetic","author":"Hansen","key":"2019100513021014100_c31"},{"key":"2019100513021014100_c32","unstructured":"Kahan, W. M. , 1968, \u201cA More Complete Interval Arithmetic,\u201d Lecture Notes for an Engineering Summer Course in Numerical Analysis, University of Michigan."},{"issue":"1","key":"2019100513021014100_c33","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/S0010-4485(96)00036-X","article-title":"An Accelerated Triangulation Method for Computing the Skeletons of Free-Form Solid Models","volume":"29","author":"Turkiyyah","journal-title":"Comput.-Aided Des.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-4485","issn-type":"print"},{"article-title":"Interval Extensions of Signed Distance Functions: Uniform Samplings and the Range of Associated Implicit Objects","author":"Storti","key":"2019100513021014100_c34","doi-asserted-by":"crossref","DOI":"10.1115\/DETC2008-49604"}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.3428736\/5775894\/021012_1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.3428736\/5775894\/021012_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T13:34:47Z","timestamp":1685626487000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/doi\/10.1115\/1.3428736\/465744\/Interval-Extensions-of-Signed-Distance-Functions"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,1]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,6,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.3428736","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"type":"print","value":"1530-9827"},{"type":"electronic","value":"1944-7078"}],"subject":[],"published":{"date-parts":[[2010,6,1]]},"article-number":"021012"}}