Ph.D Thesis

Ph.D StudentMizrahi Yonathan
SubjectSubdivision based Solvers: Solutions with Topological
Guarantee of Algebraic Constraints with
DepartmentDepartment of Applied Mathematics
Supervisor PROF. Gershon Elber


Algebraic (non-linear) constraint solving, is a challenge arising in various domains in science and engineering. Focusing on the real roots, we define the algebraic constraint solving problem, as the search for points that are simultaneous zeros of one or more real valued functions of n variables. In this thesis, we present a collection of three papers addressing research problems in the field of subdivision based solvers for algebraic constraints. Under proper assumptions, the subdivision approach is capable of providing a global solution for the constraint solving problem, in the given domain. The method (typically) operates on B-spline represented constraints that well facilitate the recursive subdivision paradigm, as well as other advantages such as numeric stability and intuitive geometric modelling capabilities. In the first paper )Chapter 2) we describe a subdivision based solver for problems with two DOF (Degrees Of Freedom), namely: the problem is under-constrained, with two more unknowns than equality constraints. Building upon subdivision termination criteria for problems with zero and one DOF, we provide topologically guaranteed termination criteria for the two DOF case. To guarantee the unknown solution in the tested sub-domain has the topology of a two dimensional disc, we first solve the problem on the sub-domain’s boundary, and consider the number of polyline loops obtained. Then, we formulate a tractable algorithm to test if the solution can be projected into a two dimensional plane, in a one-to-one manner.

We show that if the one-to-one projection is possible, it implies either an empty solution (if the boundary solution is empty), or disc-topology (if the boundary solution comprises exactly a single loop). Then, a numeric reconstruction procedure for the solution in the sub-domain’s interior is presented, constructing a polygonal mesh approximation of the solution, agreeing on the boundary polyline with the single loop detected. In the second paper, presented in Chapter 3, we utilize the two DOF solver from Chapter 2, as a first step in computing the Minkowski sum of freeform surfaces: we search for the boundary surface of the (typically a volume) Minkowski sum of two surfaces. A known necessary condition for a point in the Minkowski sum to belong to the boundary we seek, is its realization as the sum of two points in the input surfaces, with parallel tangent planes (parallel or anti-parallel normal directions). This condition is formulated as an under-constrained system, yielding a superset of the required boundary. Then, a purging algorithm to eliminate the redundant solution patches is executed: coarse filtering of entire triangles, followed

by a refinement step, applied to the undecided triangles, further trimming them. The third paper, presented in Chapter 4, provides a subdivision based method for detecting critical points of algebraic equations. An alternative algebraic system is formulated, searching for locations of non-maximal rank differential of the input system. The resulting system is over-constrained, and is approached as a minimization problem, after further reformulation, mapping it to an equation solving problem of size

n x n. Finally, we conclude this work in Chapter 5.