Massively Parallel Approximation of Irregular Triangular Meshes with G 1 Parametric Surfaces

Abstract. A new data-parallel algorithm for reconstructing smooth surfaces defined by arbitrary 3D triangular meshes is presented. The obtained surfaces are composed of triangular patches that join with first order geometric continuity. Every patch is generated by a parametric function that approximates the vertices of each control triangle of the mesh. A coarse granularity implementation of those functions, in which each triangular patch is generated on a separate processor, yields the best performances when no communication among processors occurs. The data distribution to attain such an independent task-farm topology is studied. The algorithm has been implemented on a Connection Machine CM-200 system, achieving linear scaling in the number of processors. The simplicity and inherent parallelism of this technique allow its implementation on a wide variety of other parallel and vector architectures.