MiSo: A DSL for Robust and Efficient Solve and MInimize Problems
Open Access
- 27 July 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 44 (4) , 1-18
Abstract
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.Keywords
Funding Information
- NSF (OAC-2411349)
- NSF (IIS-2313156)
This publication has 40 references indexed in Scilit:
- Precise Hausdorff distance computation for freeform surfaces based on computations with osculating toroidal patchesComputer Aided Geometric Design, 2021
- Indirect Predicates for Geometric ConstructionsComputer-Aided Design, 2020
- Fast and robust computation of the Hausdorff distance between triangle mesh and quad mesh for near-zero casesComputers & Graphics, 2019
- On the convergence rate of grid search for polynomial optimization over the simplexOptimization Letters, 2016
- Robustness and efficiency of geometric programs: The Predicate Construction Kit (PCK)Computer-Aided Design, 2016
- Efficient Hausdorff Distance computation for freeform geometric models in close proximityComputer-Aided Design, 2013
- Geometrical validity of curvilinear finite elementsJournal of Computational Physics, 2013
- Precise Hausdorff distance computation between polygonal meshesComputer Aided Geometric Design, 2010
- Interval Analysis and Robotics2010
- Graph Implementations for Nonsmooth Convex Programs2007