Clustering a Large Number of Faces for 2-Dimensional Mesh Generation

This paper presents an automated face clustering method used as a preprocess of mesh generation for finite element analysis. Hundreds or thousands of faces are often contained in a CAD model designed in detail, and many of them are smaller than a single mesh element. This complexity of a CAD model makes a meshing process difficult both in quality and in speed. Our clustering method decomposes a CAD model into several regions, each of which is geometrically proper for a meshing process. In the algorithm, we start from the state where every single face makes its own region, and then repeat selecting a pair of adjacent regions and merging them into one region until there remains no mergeable pair of regions. The selection of the most suitable pair and the mergeability test are done based on several geometric indices about a pair of regions. The validity of the method is demonstrated with results of clustering and mesh generation on a real-scale CAD model.