Automatic decomposition of discretized surfaces for parallel processing

Abstract

In this paper, a generic surface decomposition algorithm is presented which could subdivide a general open or closed discretized surface into n pieces following any specified geometrical criteria. The cut lines are formed by taking unique lines (edges) on the discretized surface, so that only topological operations are involved, and hence individual partitioned surfaces could be processed independently before being put back together to recover the original surface. A surface marching process is proposed to balance the specified geometrical quantities of the cut surfaces following a distance map readily determined from the element adjacency relationship. The cut line can be further refined by a backward marching procedure within a potential cutting zone, so that other geometrical quantities such as sharp dihedral angles and deviation angles, etc. can also be taken into account. The time complexity of the surface decomposition process is basically linear as only the element adjacency relationship and the system of unique lines are referred to in all the steps for surface decomposition.