A Rapid Convex Decomposition Technique for Shape Simplification

In this paper we address the problem of decomposing a polyhedral surface into convex patches. We describe a modified convex patch definition and based on that definition we develop a convex decomposition algorithm that decomposes a given surface model into "exact convex" or "approximate convex" patches according to a user defined angle threshold. The resulting patches provide similar benefits as former surface convex decompositions and takes less processing time. The proposed decomposition technique takes few seconds to decompose complex models such as Armadillo model. In order to show the effectiveness of the proposed technique, we use it along with edge collapse technique and develop a shape simplification algorithm. The proposed simplification algorithm decomposes the model first into convex patches, categorizes them into large and small convex patches and then applies a simplification scheme only to the large ones, thus maintaining important geometrical and topological information of original model. The proposed simplification technique is faster than the general decimation approach. The details of the proposed techniques along with experimental results are discussed in this paper.