On the detection of over-constrained subparts of configurations when deforming free-form curves

Abstract

Today, designers use CAD modelers to define and modify NURBS surfaces involved in the design of complex shapes like car bodies or turbine blades. The generated shapes often result from the use of variational modeling techniques where user-specified constraints define the shapes. However, for free-form curve/surfaces, if too much constraints are added to subparts of a configuration, the system will not be solvable even if it is globally well-/under-constrained. When this happens, it is useful to identify locally unsatisfiable subparts of configurations and provide the user feedback for adjustment. Currently, in the domain of geometric constraint solving, techniques are mainly developed for Euler geometries rather than parametric entities like free-form curves/surfaces. In this paper, we apply the Dulmage-Mendelsohn decomposition method to isolate structural over-constrained subparts of configurations. Since structural over-constraints do not necessarily mean unsatisfiable, a Jacobian matrix analysis approach is taken to further detect the inconsistent constraints. Indeed, these numerical methods can be generalized to detect overconstraints on free-form curves. We illustrate our approach on different examples where results show that Gauss elimination, though restricted to linear cases, is more relevant in our context than Dulmage-Mendelsohn decomposition.