The Taub Faculty of Computer Science Events and Talks

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 discuss 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, 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 by discussing the results of our research, and suggest potential directions for future research, based on insights from our research and other recent development in the study of geometry.