{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T10:15:09Z","timestamp":1775729709380,"version":"3.50.1"},"reference-count":49,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2022,7,13]],"date-time":"2022-07-13T00:00:00Z","timestamp":1657670400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In analysis of problems with parametric spline boundaries that are immersed or inserted into an underlying domain, the discretization on the underlying domain usually does not conform to the inserted boundaries. While the fixed underlying discretization is of great convenience as the immersed boundaries evolve, the field approximations near the inserted boundaries require refinement in the underlying domain, as do the quadrature cells. In this paper, a kd-tree data structure together with a sign-based and\/or distance-based refinement strategy is proposed for local refinement near the inserted boundaries as well as for adaptive quadrature near the boundaries. The developed algorithms construct and utilize implicit forms of parametric Non-Uniform Rational B-Spline (NURBS) surfaces to algebraically (and non-iteratively) estimate distance as well as sign relative to the inserted boundary. The kd-tree local refinement is demonstrated to produce fewer sub-cells for the same accuracy of solution as compared to the classical quad\/oct tree-based subdivision. Consistent with the kd-tree data structure, we describe a new a priori refinement algorithm based on the signed and unsigned distance from the inserted boundary. We first demonstrate the local refinement strategy coupled with the the kd-tree data structure by constructing Truncated Hierarchical B-spline (THB-spline) \u201cmeshes\u201d. We next demonstrate the accuracy and efficiency of the developed local refinement strategy through adaptive quadrature near NURBS boundaries inserted within volumetric three-dimensional NURBS discretizations.<\/jats:p>","DOI":"10.3390\/a15070245","type":"journal-article","created":{"date-parts":[[2022,7,13]],"date-time":"2022-07-13T22:06:00Z","timestamp":1657749960000},"page":"245","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Local Refinement near Parametric Boundaries Using kd-Tree Data Structure and Algebraic Level Sets"],"prefix":"10.3390","volume":"15","author":[{"given":"Tao","family":"Song","sequence":"first","affiliation":[{"name":"School of Mechanical Engineering, Purdue University, West Lafayette, IN 47907, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huanyu","family":"Liao","sequence":"additional","affiliation":[{"name":"School of Mechanical Engineering, Purdue University, West Lafayette, IN 47907, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0462-1130","authenticated-orcid":false,"given":"Ganesh","family":"Subbarayan","sequence":"additional","affiliation":[{"name":"School of Mechanical Engineering, Purdue University, West Lafayette, IN 47907, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,7,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"4135","DOI":"10.1016\/j.cma.2004.10.008","article-title":"Isogeometric analysis: CAD, finite elements, NURBS, exact geometry and mesh refinement","volume":"194","author":"Hughes","year":"2005","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1016\/S0010-4485(03)00129-5","article-title":"Constructive solid analysis: A hierarchical, geometry-based meshless analysis procedure for integrated design and analysis","volume":"36","author":"Natekar","year":"2004","journal-title":"Comput.-Aided Des."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1055","DOI":"10.1007\/s00466-014-1059-4","article-title":"Fluid\u2013structure interaction analysis of bioprosthetic heart valves: Significance of arterial wall deformation","volume":"54","author":"Hsu","year":"2014","journal-title":"Comput. Mech."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/j.compfluid.2015.08.027","article-title":"The tetrahedral finite cell method for fluids: Immersogeometric analysis of turbulent flow around complex geometries","volume":"141","author":"Xu","year":"2016","journal-title":"Comput. Fluids"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1209","DOI":"10.1002\/nme.468","article-title":"A hybrid extended finite element\/level set method for modeling phase transformations","volume":"54","author":"Ji","year":"2002","journal-title":"Int. J. Numer. Methods Eng."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1959","DOI":"10.1002\/nme.386","article-title":"The extended finite element method (XFEM) for solidification problems","volume":"53","author":"Chessa","year":"2002","journal-title":"Int. J. Numer. Methods Eng."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"4333","DOI":"10.1016\/j.cma.2008.05.003","article-title":"Isogeometric analysis of the Cahn\u2013Hilliard phase-field model","volume":"197","author":"Calo","year":"2008","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1016\/j.cma.2014.10.013","article-title":"A sharp interface isogeometric solution to the Stefan problem","volume":"284","author":"Song","year":"2015","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/S0168-874X(00)00035-4","article-title":"Discontinuous enrichment in finite elements with a partition of unity method","volume":"36","author":"Dolbow","year":"2000","journal-title":"Finite Elem. Anal. Des."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.cma.2012.06.006","article-title":"Isogeometric enriched field approximations","volume":"245","author":"Tambat","year":"2012","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1016\/j.engfracmech.2015.04.034","article-title":"Simulations of arbitrary crack path deflection at a material interface in layered structures","volume":"141","author":"Tambat","year":"2015","journal-title":"Eng. Fract. Mech."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1016\/0010-4485(78)90110-0","article-title":"Recursively generated B-spline surfaces on arbitrary topological meshes","volume":"10","author":"Catmull","year":"1978","journal-title":"Comput.-Aided Des."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"806","DOI":"10.1108\/02644409710188736","article-title":"Iterative mesh generation for FE-computations on free form surfaces","volume":"14","author":"Kobbelt","year":"1997","journal-title":"Eng. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2039","DOI":"10.1002\/(SICI)1097-0207(20000430)47:12<2039::AID-NME872>3.0.CO;2-1","article-title":"Subdivision surfaces: A new paradigm for thin-shell finite-element analysis","volume":"47","author":"Cirak","year":"2000","journal-title":"Int. J. Numer. Methods Eng."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Piegl, L., and Tiller, W. (1997). The NURBS Book, Springer. [2nd ed.].","DOI":"10.1007\/978-3-642-59223-2"},{"key":"ref_16","first-page":"1","article-title":"Anisotropic NURBS approximation in isogeometric analysis","volume":"209","author":"Cho","year":"2012","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1145\/378456.378512","article-title":"Hierarchical B-spline refinement","volume":"22","author":"Forsey","year":"1988","journal-title":"ACM Siggraph Comput. Graph."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1145\/882262.882295","article-title":"T-splines and T-NURCCs","volume":"22","author":"Sederberg","year":"2003","journal-title":"ACM Trans. Graph. (TOG)"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1145\/1015706.1015715","article-title":"T-spline simplification and local refinement","volume":"23","author":"Sederberg","year":"2004","journal-title":"Acm Trans. Graph."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.cagd.2012.03.025","article-title":"THB-splines: The truncated basis for hierarchical splines","volume":"29","author":"Giannelli","year":"2012","journal-title":"Comput. Aided Geom. Des."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/j.cma.2009.02.036","article-title":"Isogeometric analysis using T-splines","volume":"199","author":"Bazilevs","year":"2010","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"3554","DOI":"10.1016\/j.cma.2011.09.004","article-title":"A hierarchical approach to adaptive local refinement in isogeometric analysis","volume":"200","author":"Vuong","year":"2011","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/j.cma.2008.12.004","article-title":"Efficient quadrature for NURBS-based isogeometric analysis","volume":"199","author":"Hughes","year":"2010","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1391","DOI":"10.1016\/S0045-7825(00)00168-7","article-title":"NURBS-based solutions to inverse boundary problems in droplet shape prediction","volume":"190","author":"Renken","year":"2000","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"2130","DOI":"10.1016\/j.cma.2006.11.008","article-title":"A meshless, compositional approach to shape optimal design","volume":"196","author":"Zhang","year":"2007","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1452","DOI":"10.1002\/nme.2046","article-title":"CAD inspired hierarchical partition of unity constructions for NURBS-based, meshless design, analysis and optimization","volume":"72","author":"Rayasam","year":"2007","journal-title":"Int. J. Numer. Methods Eng."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"3768","DOI":"10.1016\/j.cma.2008.02.036","article-title":"The finite cell method for three-dimensional problems of solid mechanics","volume":"197","author":"Parvizian","year":"2008","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"2982","DOI":"10.1016\/j.cma.2009.05.004","article-title":"Isogeometric analysis for trimmed CAD surfaces","volume":"198","author":"Kim","year":"2009","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"2796","DOI":"10.1016\/j.cma.2010.04.015","article-title":"Isogeometric analysis with trimming technique for problems of arbitrary complex topology","volume":"199","author":"Kim","year":"2010","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1016\/j.cma.2012.03.017","article-title":"An isogeometric design-through-analysis methodology based on adaptive hierarchical refinement of NURBS, immersed boundary methods, and T-spline CAD surfaces","volume":"249","author":"Schillinger","year":"2012","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1002\/fld.3864","article-title":"A fixed-grid b-spline finite element technique for fluid\u2013structure interaction","volume":"74","author":"Cirak","year":"2014","journal-title":"Int. J. Numer. Methods Fluids"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1002\/nme.2768","article-title":"Higher-order XFEM for curved strong and weak discontinuities","volume":"82","author":"Cheng","year":"2010","journal-title":"Int. J. Numer. Methods Eng."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s40323-015-0031-y","article-title":"Efficient and accurate numerical quadrature for immersed boundary methods","volume":"2","author":"Kudela","year":"2015","journal-title":"Adv. Model. Simul. Eng. Sci."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.cma.2014.07.012","article-title":"Algebraic distance estimations for enriched isogeometric analysis","volume":"280","author":"Upreti","year":"2014","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/j.cad.2016.09.006","article-title":"Signed algebraic level sets on NURBS surfaces and implicit Boolean compositions for isogeometric CAD\u2013CAE integration","volume":"82","author":"Upreti","year":"2017","journal-title":"Comput.-Aided Des."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"De Berg, M., Van Kreveld, M., Overmars, M., and Schwarzkopf, O. (2000). Computational Geometry, Springer.","DOI":"10.1007\/978-3-662-04245-8"},{"key":"ref_37","unstructured":"Karras, T. (2012, January 25\u201327). Maximizing parallelism in the construction of BVHs, octrees, and k-d trees. Proceedings of the Fourth ACM SIGGRAPH\/Eurographics conference on High-Performance Graphics, Paris, France."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Hu, L., Nooshabadi, S., and Ahmadi, M. (2015, January 24\u201327). Massively parallel KD-tree construction and nearest neighbor search algorithms. Proceedings of the 2015 IEEE International Symposium on Circuits and Systems (ISCAS), Lisbon, Portugal.","DOI":"10.1109\/ISCAS.2015.7169256"},{"key":"ref_39","unstructured":"Kiss, G., Giannelli, C., and J\u00fcttler, B. (2014). Algorithms and Data Structures for Truncated Hierarchical B\u2013splines. Mathematical Methods for Curves and Surfaces: Proceedings of the 8th International Conference, MMCS 2012, Oslo, Norway, 28 June\u20133 July 2012, Springer. Revised Selected Papers."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/j.cma.2015.11.002","article-title":"THB-splines: An effective mathematical technology for adaptive refinement in geometric design and isogeometric analysis","volume":"299","author":"Giannelli","year":"2016","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Liao, H., Vaitheeswaran, P.K., Song, T., and Subbarayan, G. (2020). Algebraic point projection for immersed boundary analysis on low degree NURBS curves and surfaces. Algorithms, 13.","DOI":"10.3390\/a13040082"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"103004","DOI":"10.1016\/j.cad.2021.103004","article-title":"Improved Dixon Resultant for Generating Signed Algebraic Level Sets and Algebraic Boolean Operations on Closed Parametric Surfaces","volume":"135","author":"Vaitheeswaran","year":"2021","journal-title":"Comput.-Aided Des."},{"key":"ref_43","unstructured":"Sederberg, T. (1983). Implicit and Parametric Curves and Surfaces for Computer Aided Geometric Design. [Ph.D. Thesis, Purdue University]."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.gmod.2004.01.003","article-title":"Approximate distance fields with non-vanishing gradients","volume":"66","author":"Biswas","year":"2004","journal-title":"Graph. Model."},{"key":"ref_45","first-page":"765","article-title":"On the analytical description of some geometric objects","volume":"153","author":"Rvachev","year":"1963","journal-title":"Rep. Ukr. Acad. Sci."},{"key":"ref_46","unstructured":"Shapiro, V. (1991). Theory of R-Functions and Applications: A Primer, Department of Computer Science, Cornell University. Technical Report TR91-1219."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1137\/0715049","article-title":"Error estimates for adaptive finite element computations","volume":"15","author":"Rheinboldt","year":"1978","journal-title":"SIAM J. Numer. Anal."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0045-7825(96)01107-3","article-title":"A posteriori error estimation in finite element analysis","volume":"142","author":"Ainsworth","year":"1997","journal-title":"Comput. Methods Appl. Mech. Eng."},{"key":"ref_49","unstructured":"Jaeger, J.C., Cook, N.G., and Zimmerman, R. (2009). Fundamentals of Rock Mechanics, John Wiley & Sons."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/7\/245\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:49:47Z","timestamp":1760140187000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/7\/245"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,13]]},"references-count":49,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2022,7]]}},"alternative-id":["a15070245"],"URL":"https:\/\/doi.org\/10.3390\/a15070245","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,13]]}}}