{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:11:28Z","timestamp":1778040688205,"version":"3.51.4"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["OAC-2411349"],"award-info":[{"award-number":["OAC-2411349"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["IIS-2313156"],"award-info":[{"award-number":["IIS-2313156"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2025,8,1]]},"abstract":"<jats:p>Many problems in computer graphics can be formulated as finding the global minimum of a function subject to a set of non-linear constraints (Minimize), or finding all solutions of a system of non-linear constraints (Solve). We introduce MiSo, a domain-specific language and compiler for generating efficient C++ code for low-dimensional Minimize and Solve problems, that uses interval methods to guarantee conservative results while using floating point arithmetic. We demonstrate that MiSo-generated code shows competitive performance compared to hand-optimized codes for several computer graphics problems, including high-order collision detection with non-linear trajectories, surface-surface intersection, and geometrical validity checks for finite element simulation.<\/jats:p>","DOI":"10.1145\/3731207","type":"journal-article","created":{"date-parts":[[2025,7,27]],"date-time":"2025-07-27T04:02:22Z","timestamp":1753588942000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["MiSo: A DSL for Robust and Efficient Solve and MInimize Problems"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2805-306X","authenticated-orcid":false,"given":"Federico","family":"Sichetti","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Genova, Genova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9780-5283","authenticated-orcid":false,"given":"Enrico","family":"Puppo","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Genova, Genova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-6529-4694","authenticated-orcid":false,"given":"Zizhou","family":"Huang","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9012-7245","authenticated-orcid":false,"given":"Marco","family":"Attene","sequence":"additional","affiliation":[{"name":"CNR IMATI, Genova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7733-5501","authenticated-orcid":false,"given":"Denis","family":"Zorin","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1183-2454","authenticated-orcid":false,"given":"Daniele","family":"Panozzo","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,7,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523447"},{"key":"e_1_2_2_2_1","unstructured":"M. Aanjaneya J.P. Lim and S. Nagarakatte. 2024. The RLIBM Project. https:\/\/github.com\/rutgers-apl\/The-RLIBM-Project"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"T. Akenine-M\u00f6ller E. Haines N. Hoffman A. Pesce M. Iwanicki and S. Hillaire. 2018. Real-Time Rendering 4th Edition. A.K. Peters\/CRC Press Boca Raton FL USA.","DOI":"10.1201\/b22086"},{"key":"e_1_2_2_4_1","unstructured":"T. Akenine-M\u00f6ller E. Haines N. Hoffman A. Pesce M. Iwanicki and S. Hillaire. 2024. Real-Time Rendering - Ray Tracing Resources Page. https:\/\/www.realtimerendering.com\/intersections.html"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195908002647"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2020.102856"},{"key":"e_1_2_2_7_1","unstructured":"M. Attene. 2025. NFG - Numbers For Geometry. https:\/\/github.com\/MarcoAttene\/NFG"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2005.49"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2010.04.004"},{"key":"e_1_2_2_10_1","article-title":"Why New Programming Languages for Simulation","volume":"35","author":"Louis Bernstein G.","year":"2016","unstructured":"G. Louis Bernstein and F. Kjolstad. 2016. Why New Programming Languages for Simulation? ACM Trans. Graph. 35, 2, Article 20e (May 2016), 3 pages.","journal-title":"ACM Trans. Graph."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185592"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCB.2005.850172"},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"X. Chen C. Yu X. Ni M. Chu B. Wang and B. Chen. 2024. A Time-Dependent Inclusion-Based Method for Continuous Collision Detection between Parametric Surfaces. ACM SIGGRAPH Computer Graphics 43 6 (2024).","DOI":"10.1145\/3687960"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00236"},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the third ACM symposium on Symbolic and algebraic computation - SYMSAC '76 (SYMSAC '76)","author":"Collins G.E.","unstructured":"G.E. Collins and A.G. Akritas. 1976. Polynomial real root isolation using Descarte's rule of signs. In Proceedings of the third ACM symposium on Symbolic and algebraic computation - SYMSAC '76 (SYMSAC '76). ACM Press, 272\u2013275."},{"key":"e_1_2_2_16_1","volume-title":"CVX: Matlab Software for Disciplined Convex Programming, version 2.0. https:\/\/cvxr.com\/cvx.","author":"Research CVX","year":"2012","unstructured":"CVX Research, Inc. 2012. CVX: Matlab Software for Disciplined Convex Programming, version 2.0. https:\/\/cvxr.com\/cvx."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.011"},{"key":"e_1_2_2_18_1","unstructured":"Etienne De Klerk Monique Laurent and Zhao Sun. 2014. An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution. http:\/\/arxiv.org\/abs\/1407.2108 arXiv:1407.2108 [math]."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-016-1023-7"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459802"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(03)00422-9"},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","unstructured":"M. Grant and S. Boyd. 2008. Graph implementations for nonsmooth convex programs. In Recent Advances in Learning and Control V. Blondel S. Boyd and H. Kimura (Eds.). Springer-Verlag Limited 95\u2013110.","DOI":"10.1007\/978-1-84800-155-8_7"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.910820"},{"key":"e_1_2_2_24_1","volume-title":"ACM SIGGRAPH 2004 Course Notes","author":"Hadap S.","unstructured":"S. Hadap, D. Eberle, P. Volino, M.C. Lin, S. Redon, and C. Ericson. 2004. Collision detection and proximity queries. In ACM SIGGRAPH 2004 Course Notes (Los Angeles, CA) (SIGGRAPH '04). ACM, New York, NY, USA, 15\u2013es."},{"key":"e_1_2_2_25_1","first-page":"2","article-title":"An interval Newton method","volume":"12","author":"Hansen E.R.","year":"1983","unstructured":"E.R. Hansen and R.I. Greenberg. 1983. An interval Newton method. Appl. Math. Comput. 12, 2\u20133 (May 1983), 89\u201398.","journal-title":"Appl. Math. Comput."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3520484"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation (Virtual Event, Russian Federation) (ISSAC '21)","author":"Hormann K.","unstructured":"K. Hormann, L. Kania, and C. Yap. 2021. Novel Range Functions via Taylor Expansions and Recursive Lagrange Interpolation with Application to Real Root Isolation. In Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation (Virtual Event, Russian Federation) (ISSAC '21). ACM, New York, NY, USA, 193\u2013200."},{"key":"e_1_2_2_28_1","volume-title":"Range Functions of Any Convergence Order and Their Amortized Complexity Analysis. In Computer Algebra in Scientific Computing: 25th International Workshop, CASC 2023 (Havana, Cuba). Springer-Verlag","author":"Hormann K.","unstructured":"K. Hormann, C. Yap, and Y.S. Zhang. 2023. Range Functions of Any Convergence Order and Their Amortized Complexity Analysis. In Computer Algebra in Scientific Computing: 25th International Workshop, CASC 2023 (Havana, Cuba). Springer-Verlag, Berlin, Heidelberg, 162\u2013182."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356506"},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the 41st IEEE Conference on Decision and Control","volume":"4","author":"Jaulin L.","year":"2002","unstructured":"L. Jaulin, I. Braems, and E. Walter. 2002. Interval methods for nonlinear identification and robust control. In Proceedings of the 41st IEEE Conference on Decision and Control, 2002., Vol. 4. IEEE, Las Vegas, NV, USA, 4676\u20134681."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2012.08.051"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2633467.2633565"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2006.56"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2019.03.014"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2012.10.010"},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of the ACM on Programming Languages 1, OOPSLA","author":"Kjolstad F.","year":"2017","unstructured":"F. Kjolstad, S. Kamil, S. Chou, D. Lugato, and S. Amarasinghe. 2017. The tensor algebra compiler. Proceedings of the ACM on Programming Languages 1, OOPSLA (2017), 1\u201329."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2866569"},{"key":"e_1_2_2_38_1","first-page":"63","article-title":"Reducing pessimism in Interval Analysis using B-splines Properties: Application to Robotics","volume":"27","author":"Lengagne S.","year":"2020","unstructured":"S. Lengagne, R. Kalawoun, F. Bouchon, and Y. Mezouar. 2020. Reducing pessimism in Interval Analysis using B-splines Properties: Application to Robotics. Reliable Computing 27 (2020), 63\u201387.","journal-title":"Reliable Computing"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2015.10.004"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459767"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3662181"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3478513.3480506"},{"key":"e_1_2_2_43_1","volume-title":"Proc. ACM Program. Lang. 6, POPL, Article 3 (Jan.","author":"Lim J.P.","year":"2022","unstructured":"J.P. Lim and S. Nagarakatte. 2022. One polynomial approximation to produce correctly rounded results of an elementary function for multiple representations and rounding modes. Proc. ACM Program. Lang. 6, POPL, Article 3 (Jan. 2022), 28 pages."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14074"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14074"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3478513.3480551"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14743-2_13"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.7717\/peerj-cs.103"},{"key":"e_1_2_2_49_1","volume-title":"FPG: A code generator for fast and certified geometric predicates. In Real numbers and computers. 47\u201360.","author":"Meyer A.","year":"2008","unstructured":"A. Meyer and S. Pion. 2008. FPG: A code generator for fast and certified geometric predicates. In Real numbers and computers. 47\u201360."},{"key":"e_1_2_2_50_1","unstructured":"M.B. Monagan K.O. Geddes K. M. Heal G. Labahn S.M. Vorkoetter J. McCarron and P. DeMarco. 2005. Maple 10 Programming Guide. Maplesoft Waterloo ON Canada."},{"key":"e_1_2_2_51_1","unstructured":"J. Nocedal and S.J. Wright. 2006. Numerical Optimization. Springer New York."},{"key":"e_1_2_2_52_1","first-page":"3","article-title":"Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates","volume":"18","author":"Shewchuk J. R.","year":"1997","unstructured":"J. R. Shewchuk. 1997. Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. Discrete & Computational Geometry 18, 3 (Oct. 1997), 305\u2013363.","journal-title":"Discrete & Computational Geometry"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766947"},{"key":"e_1_2_2_54_1","unstructured":"J.M.Snyder. 1991. Generative Modeling: An Approach to High Level Shape Design for Computer Graphics and CAD. Ph.D. Dissertation."},{"key":"e_1_2_2_55_1","volume-title":"Interval Analysis For Computer Graphics. ACM SIGGRAPH","author":"Snyder J","year":"1992","unstructured":"J Snyder. 1992. Interval Analysis For Computer Graphics. ACM SIGGRAPH (1992), 121\u2013130."},{"key":"e_1_2_2_56_1","doi-asserted-by":"crossref","unstructured":"J. Snyder A.R. Woodbury K. Fleischer B. Currin and A.H. Barr. 1993. Interval Methods for Multi-Point Collisions between Time-Dependent Curved Surfaces. In ACM SIGGRAPH. ACM.","DOI":"10.1145\/166117.166158"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2021.101967"},{"key":"e_1_2_2_58_1","unstructured":"V. Stahl. 1995. Interval Methods for Bounding the Range of Polynomials and Solving Systems of Nonlinear Equations. Ph.D. Dissertation."},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661237"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14080"},{"key":"e_1_2_2_61_1","doi-asserted-by":"crossref","unstructured":"B. Wang . Ferguson X. Jiang M. Attene D. Panozzo and T. Schneider. 2022. Fast and Exact Root Parity for Continuous Collision Detection. Computer Graphics Forum (Proceedings of Eurographics) 41 2 (2022) 9 pages.","DOI":"10.1111\/cgf.14479"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460775"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601114"},{"key":"e_1_2_2_64_1","unstructured":"Wolfram Research Inc. 2023. Mathematica Version 13.3. https:\/\/www.wolfram.com\/mathematica Champaign IL."},{"key":"e_1_2_2_65_1","volume-title":"Sum-of-Squares Collision Detection for Curved Shapes and Paths. In ACM SIGGRAPH 2023 Conference Proceedings","author":"Zhang P.","unstructured":"P. Zhang, Z. Marschner, J. Solomon, and R. Tamstorf. 2023. Sum-of-Squares Collision Detection for Curved Shapes and Paths. In ACM SIGGRAPH 2023 Conference Proceedings (Los Angeles, CA, USA). ACM, New York, NY, USA, Article 76, 11 pages."},{"key":"e_1_2_2_66_1","unstructured":"Z. Zhang Y.-J. Chiang and C. Yap. 2024. Theory and Explicit Design of a Path Planner for an SE(3) Robot. arXiv:2407.05135 [cs.RO] https:\/\/arxiv.org\/abs\/2407.05135"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14395"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3731207","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T17:55:04Z","timestamp":1774634104000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3731207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,27]]},"references-count":67,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,1]]}},"alternative-id":["10.1145\/3731207"],"URL":"https:\/\/doi.org\/10.1145\/3731207","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,27]]},"assertion":[{"value":"2025-07-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}