Determining the manufacturabilities of proposed 3D designs with a given set of manufacturing operations is an essential reasoning problem for integrating CAD and CAM systems. In this thesis, we present results on finding feasible directions that are needed for numerically controlled (NC) machining, assembly planning, layered manufacturing, and mould design. A unified formulation is introduced for solving these problems using Gaussian sphere.
The machinability problem arises in NC machining. Using Gaussian mapping, various machinability problems are formulated as the problem of finding a domain that can contain a set of points on the sphere. The domain is drawn the machining environments such as machine type, cutter type, assumptions on the cutter engagement, and so on. The typical domain types for NC machining are the disk, band, and section that are circularly-bounded regions on the sphere. The set of points on the sphere is mapped from the normal vectors of faces approximating a given free-form surface. Three types of containment problems are considered; checking the feasibility, finding an optimal domain, and computing all feasible domains. We also show that the containment problem is equivalent to the intersection problem of multiple domains derived from the manufacturing environments.
For checking the feasibility for a hemisphere domain, we present an O(n) algorithm by employing the central projection and the linear sparability of two sets of points, where n is the number of points. An optimal disk domain is obtained in O(n) time by locating the smallest disk enclosing the set of points. We also construct all feasible domains in O(nlogn) time, using the duality of two spherical polygons. We solve the three types of problems for a great band domain in the same time complexity as the disk domain. We also propose an O(nlogn) algorithm for determining an optimal small band by searching the boundary of all solutions. For checking the feasibility and computing all solutions, the great band algorithms can be extended into the problems of small band domains.
We introduce the notion of monotonicities of polyhedrons, and relate them with the problems of finding feasible directions in layered manufacturing, mould design, and assembly planning. The strong monotonicity of a polyhedron is formulated as finding great circles separating a set of spherical polygons that are derived from the convex deficiencies of the polyhedron. All strongly monotone directions are obtained in O(mklogk) time by computing all such great circles [CCW93b], where m is the total number of vertices and k is the number of deficiencies. We suggest a similar formulation for the separable monotonicity of a limited class of polyhedrons, that is, the polyhedrons with monotone pockets. All weakly monotone directions of the constrained polyhedron are obtained by finding great circles intersecting a set of polygons on the sphere. We also suggest a heuristic O(m) algorithm for finding a solution for this problem.
