{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:55:52Z","timestamp":1760144152138,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2024,3,27]],"date-time":"2024-03-27T00:00:00Z","timestamp":1711497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Croatian National Recovery and Resilience Plan (NPOO)","award":["NPOO.C1.6.R1-I2.01.","101103592"],"award-info":[{"award-number":["NPOO.C1.6.R1-I2.01.","101103592"]}]},{"name":"European Defence Fund (EDF)","award":["NPOO.C1.6.R1-I2.01.","101103592"],"award-info":[{"award-number":["NPOO.C1.6.R1-I2.01.","101103592"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Recently, there has been renewed interest in signed distance bound representations due to their unique properties for 3D shape modelling. This is especially the case for deep learning-based bounds. However, it is beneficial to work with polygons in most computer graphics applications. Thus, in this paper, we introduce and investigate an asymptotically fast method for transforming signed distance bounds into polygon meshes. This is achieved by combining the principles of sphere tracing (or ray marching) with traditional polygonization techniques, such as marching cubes. We provide theoretical and experimental evidence that this approach is of the O(N2logN) computational complexity for a polygonization grid with N3 cells. The algorithm is tested on both a set of primitive shapes and signed distance bounds generated from point clouds by machine learning (and represented as neural networks). Given its speed, implementation simplicity, and portability, we argue that it could prove useful during the modelling stage as well as in shape compression for storage.<\/jats:p>","DOI":"10.3390\/a17040137","type":"journal-article","created":{"date-parts":[[2024,3,27]],"date-time":"2024-03-27T12:41:57Z","timestamp":1711543317000},"page":"137","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Theoretical and Empirical Analysis of a Fast Algorithm for Extracting Polygons from Signed Distance Bounds"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4689-0956","authenticated-orcid":false,"given":"Nenad","family":"Marku\u0161","sequence":"first","affiliation":[{"name":"Faculty of Electrical Engineering and Computing, University of Zagreb, Unska 3, 10000 Zagreb, Croatia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0334-8179","authenticated-orcid":false,"given":"Mirko","family":"Su\u017enjevi\u0107","sequence":"additional","affiliation":[{"name":"Faculty of Electrical Engineering and Computing, University of Zagreb, Unska 3, 10000 Zagreb, Croatia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,3,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/s003710050084","article-title":"Sphere Tracing: A Geometric Method for the Antialiased Ray Tracing of Implicit Surfaces","volume":"12","author":"Hart","year":"1994","journal-title":"Vis. Comput."},{"key":"ref_2","unstructured":"Hart, J.C., Sandin, D.J., and Kauffman, L.H. (1989). ACM SIGGRAPH Computer Graphics, Association for Computing Machinery."},{"key":"ref_3","unstructured":"Davies, T., Nowrouzezahrai, D., and Jacobson, A. (2020). Overfit Neural Networks as a Compact Shape Representation. arXiv."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Chen, Z., and Zhang, H. (2019, January 15\u201320). Learning Implicit Fields for Generative Shape Modeling. Proceedings of the CVPR, Long Beach, CA, USA.","DOI":"10.1109\/CVPR.2019.00609"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Park, J.J., Florence, P., Straub, J., Newcombe, R., and Lovegrove, S. (2019, January 15\u201320). DeepSDF: Learning Continuous Signed Distance Functionsfor Shape Representation. Proceedings of the CVPR, Long Beach, CA, USA.","DOI":"10.1109\/CVPR.2019.00025"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Li, L., Sung, M., Dubrovina, A., Yi, L., and Guibas, L. (2019, January 15\u201320). Supervised Fitting of Geometric Primitives to 3D Point Clouds. Proceedings of the CVPR, Long Beach, CA, USA.","DOI":"10.1109\/CVPR.2019.00276"},{"key":"ref_7","unstructured":"Duggal, S., Wang, Z., Ma, W.C., Manivasagam, S., Liang, J., Wang, S., and Urtasun, R. (2021). Secrets of 3D Implicit Object Shape Reconstruction in the Wild. arXiv."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Hao, Z., Averbuch-Elor, H., Snavely, N., and Belongie, S. (2020, January 15\u201320). DualSDF: Semantic Shape Manipulation using a Two-Level Representation. Proceedings of the CVPR, Long Beach, CA, USA.","DOI":"10.1109\/CVPR42600.2020.00765"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/j.gmod.2014.04.011","article-title":"A double layer method for constructing signed distance fields from triangle meshes","volume":"76","author":"Wu","year":"2014","journal-title":"Graph. Model."},{"key":"ref_10","unstructured":"Lorensen, W.E., and Cline, H.E. (1987). ACM SIGGRAPH Computer Graphics, Association for Computing Machinery."},{"key":"ref_11","unstructured":"Bloomenthal, J. (1997). Introduction to Implicit Surfaces, Morgan-Kaufmann."},{"key":"ref_12","unstructured":"Olah, C. (2024, February 26). Manipulation of Implicit Functions with an Eye on CAD, 2011. Available online: https:\/\/christopherolah.wordpress.com\/2011\/11\/06\/manipulation-of-implicit-functions-with-an-eye-on-cad\/."},{"key":"ref_13","unstructured":"Olah, C. (2024, February 26). ImplicitCAD, 2011. Available online: https:\/\/github.com\/Haskell-Things\/ImplicitCAD."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/130881.130882","article-title":"Octrees for faster isosurface generation","volume":"11","author":"Wilhelms","year":"1992","journal-title":"Trans. Graph."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1109\/2945.597798","article-title":"Speeding Up Isosurface Extraction Using Interval Trees","volume":"3","author":"Cigoni","year":"1997","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1109\/2945.489388","article-title":"A Near Optimal Isosurface Extraction Algorithm Using the Span Space","volume":"2","author":"Livnat","year":"1996","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_17","unstructured":"Gao, J., Shen, T., Wang, Z., Chen, W., Yin, K., Li, D., Litany, O., Gojcic, Z., and Fidler, S. (December, January 28). GET3D: A Generative Model of High Quality 3D Textured Shapes Learned from Images. Proceedings of the Advances in Neural Information Processing Systems, New Orleans, LA, USA."},{"key":"ref_18","unstructured":"Alliegro, A., Siddiqui, Y., Tommasi, T., and Nie\u00dfner, M. (2023). PolyDiff: Generating 3D Polygonal Meshes with Diffusion Models. arXiv."},{"key":"ref_19","unstructured":"Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. (2015, January 6\u201311). Deep Unsupervised Learning using Nonequilibrium Thermodynamics. Proceedings of the ICML, Lille, France."},{"key":"ref_20","unstructured":"Ho, J., Jain, A., and Abbeel, P. (2020). Denoising Diffusion Probabilistic Models. arXiv."},{"key":"ref_21","unstructured":"Siddiqui, Y., Alliegro, A., Artemov, A., Tommasi, T., Sirigatti, D., Rosov, V., Dai, A., and Nie\u00dfner, M. (2023). MeshGPT: Generating Triangle Meshes with Decoder-Only Transformers. arXiv."},{"key":"ref_22","unstructured":"Weisstein, E.W. (2024, February 26). Point-Plane Distance. From MathWorld\u2014A Wolfram Web Resource. Available online: https:\/\/mathworld.wolfram.com\/Point-PlaneDistance.html."},{"key":"ref_23","unstructured":"Weisstein, E.W. (2024, February 26). Harmonic Series. From MathWorld\u2014A Wolfram Web Resource. Available online: https:\/\/mathworld.wolfram.com\/HarmonicSeries.html."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Yao, S., Yang, F., Cheng, Y., and Mozerov, M.G. (2021, January 11\u201317). 3D Shapes Local Geometry Codes Learning with SDF. Proceedings of the ICCV Workshops, Montreal, BC, Canada.","DOI":"10.1109\/ICCVW54120.2021.00239"},{"key":"ref_25","unstructured":"Yifan, W., Rahmann, L., and Sorkine-Hornung, O. (2021). Geometry-Consistent Neural Shape Representation with Implicit Displacement Fields. arXiv."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Mu, J., Qiu, W., Kortylewski, A., Yuille, A., Vasconcelos, N., and Wang, X. (2021). A-SDF: Learning Disentangled Signed Distance Functions for Articulated Shape Representation. arXiv.","DOI":"10.1109\/ICCV48922.2021.01276"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Takikawa, T., Litalien, J., Yin, K., Kreis, K., Loop, C., Nowrouzezahrai, D., Jacobson, A., McGuire, M., and Fidler, S. (2021, January 20\u201325). Neural Geometric Level of Detail: Real-time Rendering with Implicit 3D Shapes. Proceedings of the CVPR, Nashville, TN, USA.","DOI":"10.1109\/CVPR46437.2021.01120"},{"key":"ref_28","unstructured":"Zhou, Q., and Jacobson, A. (2016). Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/4\/137\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:19:21Z","timestamp":1760105961000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/4\/137"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,27]]},"references-count":28,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2024,4]]}},"alternative-id":["a17040137"],"URL":"https:\/\/doi.org\/10.3390\/a17040137","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,3,27]]}}}