{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T12:33:08Z","timestamp":1753878788239,"version":"3.41.2"},"reference-count":54,"publisher":"ASME International","issue":"4","license":[{"start":{"date-parts":[[2021,12,13]],"date-time":"2021-12-13T00:00:00Z","timestamp":1639353600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.asme.org\/publications-submissions\/publishing-information\/legal-policies"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI:1644441","OAC-1750865"],"award-info":[{"award-number":["CMMI:1644441","OAC-1750865"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,8,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Distance field representation of objects in 3D space has several applications such as shape manipulation, graphics rendering, path planning, etc. Distance transforms (DTs) are discrete representations of distance fields in a regular voxel grid. The two main limitations of using distance transforms are that they are compute-intensive, and there are errors introduced while representing the object using DTs. In this work, we develop a hybrid graphics processing unit (GPU)-accelerated marching wavefront method for computing DTs of models composed of trimmed non-uniform rational B-splines (NURBS) surfaces with theoretical bounds. Our hybrid marching approach eliminates the error due to calculating approximate distances by marching. We also calculate the bounds on the error introduced due to the tessellation of the trimmed NURBS surfaces and calculate the propagation of these bounds in computing the DT. Finally, we present computation times for both 2D and 3D GPU DTs of test objects. We show that our GPU-accelerated approach is significantly faster than existing CPU-based methods.<\/jats:p>","DOI":"10.1115\/1.4053202","type":"journal-article","created":{"date-parts":[[2021,12,13]],"date-time":"2021-12-13T02:36:15Z","timestamp":1639362975000},"update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":2,"title":["HyBoDT: Hybrid Bounded Distance Transforms of Trimmed NURBS Models"],"prefix":"10.1115","volume":"22","author":[{"given":"Aditya","family":"Balu","sequence":"first","affiliation":[{"name":"Iowa State University Department of Mechanical Engineering, , Ames, IA 50011"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sambit","family":"Ghadai","sequence":"additional","affiliation":[{"name":"Iowa State University Department of Mechanical Engineering, , Ames, IA 50014"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Onur","family":"Rauf Bingol","sequence":"additional","affiliation":[{"name":"Iowa State University Department of Mechanical Engineering, , Ames, IA 50011"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adarsh","family":"Krishnamurthy","sequence":"additional","affiliation":[{"name":"Iowa State University Department of Mechanical Engineering, , Ames, IA 50011"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2022,2,11]]},"reference":[{"issue":"1","key":"2023021101054136400_CIT0001","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1109\/38.135885","article-title":"Distance Field Manipulation of Surface Models","volume":"12","author":"Payne","year":"1992","journal-title":"IEEE Comput. Graph. Appl."},{"key":"2023021101054136400_CIT0002","first-page":"249","article-title":"\u201cAdaptively Sampled Distance Fields: A General Representation of Shape for Computer Graphics","volume-title":"Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques","author":"Frisken","year":"2000"},{"key":"2023021101054136400_CIT0003","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1145\/1185657.1185675","volume-title":"ACM SIGGRAPH 2006 Courses","author":"Frisken","year":"2006"},{"key":"2023021101054136400_CIT0004","first-page":"37","volume-title":"Proceedings of the 19th Annual Conference of Eurographics (UK Chapter)","author":"Jones","year":"2001"},{"key":"2023021101054136400_CIT0005","first-page":"1","article-title":"\u201cSigned Distance Fields: A Natural Representation for Both Mapping and Planning","volume-title":"RSS 2016 Workshop: Geometry and Beyond-Representations, Physics, and Scene Understanding for Robotics","author":"Oleynikova","year":"2016"},{"key":"2023021101054136400_CIT0006","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1145\/1730804.1730813","article-title":"\u201cReal-time Multi-Agent Path Planning on Arbitrary Surfaces","volume-title":"Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games","author":"Torchelsen","year":"2010"},{"issue":"1","key":"2023021101054136400_CIT0007","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1109\/MCG.2006.17","article-title":"Hierarchical Spherical Distance Fields for Collision Detection","volume":"26","author":"Funfzig","year":"2006","journal-title":"IEEE Comput. Graph. Appl."},{"key":"2023021101054136400_CIT0008","first-page":"58","volume-title":"Proceedings of GraphiCon 2003","author":"Fuhrmann","year":"2003"},{"issue":"1","key":"2023021101054136400_CIT0009","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1111\/j.1467-8659.2005.00829.x","article-title":"Collision Detection for Deformable Objects","volume":"24","author":"Teschner","year":"2005","journal-title":"Comput. Graph. Forum"},{"issue":"1","key":"2023021101054136400_CIT0010","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s12541-009-0009-0","article-title":"Three-dimensional Morphing of Similar Shapes Using a Template Mesh","volume":"10","author":"Yoo","year":"2009","journal-title":"Int. J. Precis. Eng. Manuf."},{"issue":"4","key":"2023021101054136400_CIT0011","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","year":"2006","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"issue":"2","key":"2023021101054136400_CIT0012","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1109\/TASE.2010.2066563","article-title":"Fast Intersection-Free Offset Surface Generation From Freeform Models Wwith Triangular Meshes","volume":"8","author":"Liu","year":"2010","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"issue":"2","key":"2023021101054136400_CIT0013","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/j.cad.2012.10.015","article-title":"GPU-based Offset Surface Computation Using Point Samples","volume":"45","author":"Wang","year":"2013","journal-title":"Comput.-Aided Des."},{"volume-title":"Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science","year":"1999","author":"Sethian","key":"2023021101054136400_CIT0014"},{"issue":"3","key":"2023021101054136400_CIT0015","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1111\/j.1467-8659.2004.00787.x","article-title":"DiFi: Fast 3D Distance Field Computation Using Graphics Hardware","volume":"23","author":"Sud","year":"2004","journal-title":"Comput. Graph. Forum"},{"year":"2016","author":"Jacobson","key":"2023021101054136400_CIT0016"},{"key":"2023021101054136400_CIT0017","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1109\/HPCS.2017.123","article-title":"\u201cA Fast CUDA-Based Implementation for the Euclidean Distance Transform","volume-title":"2017 International Conference on High Performance Computing & Simulation (HPCS)","author":"Zampirolli","year":"2017"},{"key":"2023021101054136400_CIT0018","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/0-306-47025-X_36","volume-title":"Mathematical Morphology and its applications to image and signal processing","author":"Meijster","year":"2002"},{"key":"2023021101054136400_CIT0019","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1145\/1111411.1111431","article-title":"\u201cJump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform","volume-title":"Proceedings of the 2006 Symposium on Interactive 3D Graphics and Games","author":"Rong","year":"2006"},{"issue":"2","key":"2023021101054136400_CIT0020","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1016\/j.cad.2012.10.037","article-title":"Filling Trim Cracks on GPU-Rendered Solid Models","volume":"45","author":"Pavanaskar","year":"2013","journal-title":"Comput.-Aided Des."},{"key":"2023021101054136400_CIT0021","doi-asserted-by":"publisher","first-page":"051008","DOI":"10.1115\/1.4047427","article-title":"Reconstruction of Trimmed NURBS Surfaces for Gap-Free Intersections","volume":"20","author":"Urick","year":"2020","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"key":"2023021101054136400_CIT0022","first-page":"263","volume-title":"Computer Graphics Forum","author":"Claux","year":"2014"},{"issue":"4","key":"2023021101054136400_CIT0023","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1145\/321356.321357","article-title":"Sequential Operations in Digital Picture Processing","volume":"13","author":"Rosenfeld","year":"1966","journal-title":"J. ACM"},{"issue":"3","key":"2023021101054136400_CIT0024","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0146-664X(80)90054-4","article-title":"Euclidean Distance Mapping","volume":"14","author":"Danielsson","year":"1980","journal-title":"Comput. Graph. Image Process."},{"key":"2023021101054136400_CIT0025","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/B978-0-444-86325-6.50010-2","volume-title":"Progress in Pattern Recognition","author":"Toriwaki","year":"1981"},{"issue":"4","key":"2023021101054136400_CIT0026","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1109\/34.277600","article-title":"A Euclidean Distance Transform Using Grayscale Morphology Decomposition","volume":"16","author":"Huang","year":"1994","journal-title":"IEEE. Trans. Pattern. Anal. Mach. Intell."},{"issue":"3","key":"2023021101054136400_CIT0027","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1006\/cviu.1996.0065","article-title":"On Digital Distance Transforms in Three Dimensions","volume":"64","author":"Borgefors","year":"1996","journal-title":"Comput. Vis. Image Underst."},{"issue":"1","key":"2023021101054136400_CIT0028","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/cviu.2002.0976","article-title":"Digital Distance Transforms in 3D Images Using Information From Neighbourhoods Up to 5 \u00d7 5 \u00d7 5","volume":"88","author":"Svensson","year":"2002","journal-title":"Comput. Vis. Image Underst."},{"issue":"10","key":"2023021101054136400_CIT0029","doi-asserted-by":"publisher","first-page":"1477","DOI":"10.1109\/83.718487","article-title":"Optimum Design of Chamfer Distance Transforms","volume":"7","author":"Butt","year":"1998","journal-title":"IEEE Trans. Image Process."},{"key":"2023021101054136400_CIT0030","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1117\/12.131088","volume-title":"Visualization in Biomedical Computing\u201992","author":"Zuiderveld","year":"1992"},{"issue":"3","key":"2023021101054136400_CIT0031","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/cviu.2001.0915","article-title":"Vector-City Vector Distance Transform","volume":"82","author":"Satherley","year":"2001","journal-title":"Comput. Vis. Image Underst."},{"key":"2023021101054136400_CIT0032","first-page":"247","article-title":"\u201cA Complete Distance Field Representation","volume-title":"Proceedings of the Conference on Visualization\u201901","author":"Huang","year":"2001"},{"key":"2023021101054136400_CIT0033","first-page":"35","article-title":"\u201cSigned Distance Fields for Polygon Soup Meshes","volume-title":"Proceedings of Graphics Interface 2014","author":"Xu","year":"2014"},{"year":"2016","author":"Coeurjolly","key":"2023021101054136400_CIT0034"},{"key":"2023021101054136400_CIT0035","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.cad.2017.01.002","article-title":"Coherent Spherical Range-Search for Dynamic Points on GPUs","volume":"86","author":"Xing","year":"2017","journal-title":"Comput.-Aided Des."},{"issue":"3","key":"2023021101054136400_CIT0036","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s41095-015-0022-4","article-title":"A Unified Framework for Isotropic Meshing Based on Narrow-Band Euclidean Distance Transformation","volume":"1","author":"Leung","year":"2015","journal-title":"Comput. Visual Media"},{"key":"2023021101054136400_CIT0037","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/1730804.1730818","article-title":"\u201cParallel Banding Algorithm to Compute Exact Distance Transform with the GPU","volume-title":"Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games","author":"Cao","year":"2010"},{"key":"2023021101054136400_CIT0038","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1109\/SMI.2008.4547967","volume-title":"2008 IEEE International Conference on Shape Modeling and Applications","author":"Bastos","year":"2008"},{"key":"2023021101054136400_CIT0039","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1109\/ICNC.2011.19","volume-title":"2011 Second International Conference on Networking and Computing","author":"Man","year":"2011"},{"issue":"11","key":"2023021101054136400_CIT0040","doi-asserted-by":"publisher","first-page":"5322","DOI":"10.1109\/TIP.2019.2916741","article-title":"A Work Efficient Parallel Algorithm for Exact Euclidean Distance Transform","volume":"28","author":"Manduhu","year":"2019","journal-title":"IEEE Trans. Image Process."},{"key":"2023021101054136400_CIT0041","first-page":"435","article-title":"\u201cGPU-Based Real-Time Discrete Euclidean Distance Transforms With Precise Error Bounds","volume-title":"VISAPP","author":"Schneider","year":"2009"},{"key":"2023021101054136400_CIT0042","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2312\/egs.20071042","article-title":"\u201cFast Hierarchical 3D Distance Transforms on the GPU","volume-title":"EG Short Papers","author":"Cuntz","year":"2007"},{"issue":"4","key":"2023021101054136400_CIT0043","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3197517.3201337","article-title":"Fast Winding Numbers for Soups and Clouds","volume":"37","author":"Barill","year":"2018","journal-title":"ACM Trans. Graph. (TOG)"},{"issue":"18","key":"2023021101054136400_CIT0044","first-page":"8","article-title":"NVIDIA CUDA C Programming Guide","volume":"120","author":"Nvidia","year":"2011","journal-title":"Nvidia Corporation"},{"issue":"1","key":"2023021101054136400_CIT0045","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/0010-4485(95)90749-6","article-title":"Tessellating Trimmed NURBS Surfaces","volume":"27","author":"Piegl","year":"1995","journal-title":"Comput.-Aided Des."},{"issue":"1","key":"2023021101054136400_CIT0046","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/S0010-4485(97)00047-X","article-title":"Geometry-Based Triangulation of Trimmed NURBS Surfaces","volume":"30","author":"Piegl","year":"1998","journal-title":"Comput.-Aided Des."},{"issue":"3","key":"2023021101054136400_CIT0047","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0925-7721(01)00012-8","article-title":"The Point in Polygon Problem for Arbitrary Polygons","volume":"20","author":"Hormann","year":"2001","journal-title":"Comput. Geometry"},{"issue":"6","key":"2023021101054136400_CIT0048","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1109\/TVCG.2010.114","article-title":"GPU-Accelerated Minimum Distance and Clearance Queries","volume":"17","author":"Krishnamurthy","year":"2011","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"year":"1995","author":"Rossum","key":"2023021101054136400_CIT0049"},{"year":"2017","author":"Jakob","key":"2023021101054136400_CIT0050"},{"key":"2023021101054136400_CIT0051","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/2833157.2833162","article-title":"\u201cNumba: A llvm-Based Python JIT Compiler","volume-title":"Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC","author":"Lam","year":"2015"},{"key":"2023021101054136400_CIT0052","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.cag.2018.07.003","article-title":"GPU-Accelerated Generation and Rendering of Multi-level Voxel Representations of Solid Models","volume":"75","author":"Young","year":"2018","journal-title":"Comput. Graph."},{"first-page":"261","year":"2020","author":"Virtanen","key":"2023021101054136400_CIT0053"},{"issue":"4","key":"2023021101054136400_CIT0054","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/2461912.2461916","article-title":"Robust Inside-outside Segmentation Using Generalized Winding Numbers","volume":"32","author":"Jacobson","year":"2013","journal-title":"ACM Trans. Graph. (TOG)"}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/22\/4\/041008\/6843469\/jcise_22_4_041008.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/22\/4\/041008\/6843469\/jcise_22_4_041008.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,11]],"date-time":"2023-02-11T01:06:10Z","timestamp":1676077570000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/22\/4\/041008\/1129232\/HyBoDT-Hybrid-Bounded-Distance-Transforms-of"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,11]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.4053202","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"type":"print","value":"1530-9827"},{"type":"electronic","value":"1944-7078"}],"subject":[],"published":{"date-parts":[[2022,2,11]]},"article-number":"041008"}}