The Taub Faculty of Computer Science Events and Talks

Algebraic constraints arise in various applications, across domains in science and engineering. Polynomial and piece-wise polynomial (B-Spline) constraints are an important class, frequently arising in geometric modeling, computer graphics and computer aided design, due to the useful NURBs representation of the involved geometries. Subdivision based solvers use properties of the NURBs representation, enabling, under proper assumptions, to solve non-linear, multi-variate algebraic constraints - globally in a given domain, while focusing on the real roots. In this talk, we present three research results addressing problems in the field of subdivision based solvers.

The first presents a topologically guaranteed solver for algebraic problems with two degrees of freedom. The main contribution of this work is a topologically guaranteed subdivision termination criterion, enabling to terminate the subdivision process when the (yet unknown) solution in the tested sub-domain is homeomorphic to a two dimensional disk. Sufficient conditions for the disk-topology are tested via inspection of the univariate solution curve(s) on the sub-domain’s boundary, together with a condition for the injective projection on a two dimensional plane, based on the underlying implicit function and its gradients.

The second result provides a subdivision based method for detecting critical points of a given algebraic system. To find critical points, we formulate an additional algebraic system, with the semantics of searching for locations where the gradients of the input problem are linearly dependent. We formulate the new problem using function valued determinants, representing the maximal minors of the input problem’s Jacobian matrix, searching for locations where they simultaneously vanish. Consequently, an over-constrained system is obtained, involving only the original parameters. The over-constrained system is then solved as a minimization problem, such that all constrains are accounted for in a balanced manner.

The third result applies the subdivision method to the specific problem of Minkowski sum computation of free-form surfaces. As a first step, a two-DOF algebraic system is formulated, searching for parameter locations that correspond to parallel (or anti-parallel) normal vectors on the input surfaces. Only such locations can contribute to the Minkowski sum envelope surface – which is the required representation for the (typically) volumetric object given by the Minkowski sum. A purging algorithm is then executed, to further refine redundant solution locations: surface patches that admit matched normal directions, but cannot contribute to the envelope.

The talk summarizes the research towards PhD in applied mathematics, under supervision of Prof. Gershon Elber.