Technical Report PHD-2020-08

Title: Symbolic algorithms for synthesis of freeform spline-based geometry
Authors: Boris Sosin
Supervisors: Gershon Elber
PDFCurrently accessibly only within the Technion network
Abstract: Automated tools and algorithms for synthesizing geometry have been ubiquitous in computer-aided design systems, since their very inception. Beyond the simple example of sketching tools for designers, algorithms for synthesizing geometry take many forms, such as design-by-constraints, optimization, and toolpath generation. In this thesis, we will present three problems in the field on geometry processing, and examine them both within the context of geometry synthesis, and in their broader applications.

The first problem we discuss is polynomial and rational constraint-solving using a subdivision-based solver, and how it can be improved by constraint system decomposition. Subdivision-based algorithms for globally finding all the solutions to constraint systems tend to scale inefficiently with the number of variables. We propose a framework for of decomposing, and efficiently solving piecewise polynomial constraint systems, with zero-dimensional or univariate solution spaces. We demonstrate these capabilities, and the performance improvement of our framework on problems such as generating geometry via design-by-constraints, kinematics over 2D and 3D geometry, and general algebraic equation systems.

The second problem we consider is functional composition of spline functions. Functional composition of B├ęzier and B-spline geometry has many applications in geometric design, such as deformation, reparametrization, fillet and microstructure synthesis, and multi-resolution design. However, the composition, G(H), of a tensor product B-spline function G with another B-spline function H is no longer a tensor product B-spline if H crosses a knot line in the domain of G in a non-isoparametric way. We propose two ways of constructing precise representations of G(H), either as trimmed geometry, or by applying an algorithm for converting trimmed geometry to a set of tensor-product patches. We present examples and discuss the properties of both methods.

The third problem we address is accessibility analysis and toolpath generation for line-cutting. Line-cutting is a class of subtractive manufacturing techniques in which a line-shaped cutting tool, such a heated wire, or a thin wire-shaped saw, moves tangentially along the reference geometry, removing parts of the workpiece, until the model is produced. From a geometric point of view, line-cutting brings a unique set of challenges in guaranteeing that the process is collision-free. We propose a conservative algorithm for finding globally unobstructed tangential cutting directions in the provided geometry. We demonstrate how, given paths for the line contacts on the surface of a model, line-accessibility analysis can be used for constructing gouging-free cutting toolpaths for line-cutting, whenever possible.

We conclude this work by discussing the results of our research, and suggest potential directions for future research, based on insights from our research and other recent developments in the study of geometry.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2020
To the main CS technical reports page

Computer science department, Technion