Geometric methods in computer-aided design and manufacturing.

摘要

Efficient algorithms for manipulating geometric objects, such as points, lines, polyhedra and free-form solids, are gaining increasing importance in the computer-aided design and manufacture (CAD/CAM) of geometrically-complex parts. These techniques fall within the scope of a discipline known as Computational Geometry (CG). At present, many aspects of the manufacturing processes and their ensuing geometric problems are tackled by relying on heuristics, in trial-and-error fashion, which necessitates a great deal of human intervention. Thus, there is an urgent need for computer algorithms that can automate these processes. In this thesis we design, implement and evaluate efficient algorithms for several geometric problems in CAD/CAM by taking advantage of advanced techniques from CG.; An emerging area of CAD/CAM that could benefit considerably from CG is layered manufacturing (LM). This technology makes it possible to build a physical prototype of a complex 3D object directly from a (virtual) CAD model by orienting and slicing the model with parallel planes and then manufacturing the slices one by one, each on top of the previous one. We have designed efficient algorithms for several geometric optimization problems arising in LM. These include minimizing the so-called stair-step error on the surfaces of the manufactured object, minimizing the volume of certain support structures used, and minimizing the contact area between the supports and the manufactured object--all of which affect the speed and accuracy of the process. We have also designed efficient algorithms for optimizing various combinations of the above criteria under different formulations. Some of these algorithms have been implemented and tested on real-world models obtained from industry. The geometric techniques used include construction and searching of certain arrangements on the unit sphere, 3D convex hulls, Voronoi diagrams, point location, hierarchical representations, visibility methods, duality, and constrained optimization. Using similar ideas we also solve an important geometric problem which arises in the design of molds for processes such as casting and injection molding.