Fast cell-based decomposition and applications to solid modeling

As opposed to constructing a complex solid model by adding simple primitives, maximal volume decomposition is the method to decompose a solid model into simpler volumes whose union is the solid model itself. A maximal volume of a solid model is the large and simple volume that does not have a concave edge and that is not contained by any other such volume. In spite of the usefulness in solid modeling such as recognition of intersecting machining features, the scalability of the method has been a problem for practical applications. The two issues in the problem-the global effect of face extension and the heavy computational load for cell collection-should be addressed. In this paper. a volume decomposition method that handles these two issues effectively is presented. This method called fast volume decomposition decomposes a solid model significantly fast with the localized face extension and the cell collection using the seed cell. (C) 2003 Elsevier Science Ltd. All rights reserved.