Minimum Bounding Boxes and Volume Decomposition of CAD Models

This dissertation, "Minimum Bounding Boxes and Volume Decomposition of CAD Models" by Chi-keung, Chan, 陳志強, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled "Minimum bounding boxes and volume decomposition of CAD models" Submitted by Chan, Chi Keung for the degree of Doctor of Philosophy at The University of Hong Kong in February 2003 The prototyping of a large-sized model is essential in the manufacture of household appliances and automobile parts. However, most of the available layered prototyping methods, such as STL (Stereolithography), SLS (Selective Laser Sintering), FDM (Fused Deposit Modeling) and LOM (Laminated object Manufacturing), are limited by the building chamber size of the machines. Decomposing a large model into smaller constituent components and subsequently assemble them provides a way to overcome this limitation. A full-scale physical prototype of a large design can then be produced from a relatively small prototyping machine. In this research, several algorithms relevant to the decomposition process are developed. They provide either new or alternative solutions to the corresponding problems. These algorithms are for determining the 'minimum bounding box of a solid model', 'putting a model into a cylindrical bounded volume' and 'assembly feature generation'. To accelerate the computational process for complex models, an algorithm for 'determining the extreme points in a large 3D point set' is presented. Integration of the above algorithms gives the final proposed decomposition algorithm. The algorithm for minimum bounding box determination is based on successive reorientation of the model in the 3D space in a specific sequence. An iteration technique is employed to accelerate the computation process. By integrating the proposed algorithm with current algorithms, a higher efficiency can be achieved. In the algorithm for testing whether a model can be put into a cylindrical bounded volume, the possibleorientations of the model are studied and some methods are proposed to reduce these testing orientations. It also involves an iterative technique to accelerate the computational process. The algorithm is extended to solve the 'fitness' problem for rectangular bounded volume. By further modification, it can also determine the minimum diameter/height cylinder of a 3D point set. The proposed algorithm provides a single solution to these problems. In the two algorithms stated above, a lot of rotations of the model are required and it is computationally expensive for a complex model. An algorithm for extreme point determination is developed to accelerate the computation process. It is based on an idea of a cylindrical grid approximation which can reduce the computational effort significantly comparing to current algorithms. To enhance the assembly of the subdivided components after decomposition, assembly features are attached onto the subdivided components by a new approach. The generation of assembly features is based on spatial cells construction and feature mapping of these cells. For the decomposition of a solid model, the proposed algorithm involves the generation of split tool surfaces, which is based on some regular patterns or feature groups extraction. Several decomposition tools are presented and their integration forms the final proposed decomposition process. The proposed algorithm ensures that the subdivided components are producible in terms of size. This is a new criterion for volume decomposition. DOI: 10.5353/th_b2994734 Subjects: Algorithms Computer-aided design Large sc