Solving piecewise polynomial constraint systems with decomposition and a subdivision-based solver. (September 2017)

• Record Type: Journal Article
• Authors: van Sosin, Boris; Elber, Gershon
• Is Part Of: Computer aided design. Volume 90(2017)
• Page Start: 37
• Page End: 47
• Publication Date: 2017-09
• Subjects: Underconstrained problems -- Inequality constraints -- B-spline representation -- Multivariate composition; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2017.05.023
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: Piecewise polynomial constraint systems are common in numerous problems in computational geometry, such as constraint programming, modeling, and kinematics. We propose a framework that is capable of decomposing, and efficiently solving a wide variety of complex piecewise polynomial constraint systems, that include both zero constraints and inequality constraints, with zero-dimensional or univariate solution spaces. Our framework combines a subdivision-based polynomial solver with a decomposition algorithm in order to handle large and complex systems. We demonstrate the capabilities of our framework on several types of problems and show its performance improvement over a state-of-the-art solver. Graphical abstract: Highlights: A framework for decomposing constraint systems, with a total DoF of zero or one. Combines a univariate solver with a constraint system decomposition algorithm. Functional composition of B-spline multivariates for propagating partial solutions. Capable of globally finding all the solutions to a constraint problem. Demonstrated on problems such as static geometry, kinematics, algebraic problems.