Complexity Analysis of a Parallel Implementation of the Marching-Cubes Algorithm

摘要

This paper presents a load-balanced parallelization of the well known Marching-Cubes algorithm, that aims at constructing an iso-surface in a 3D image. We first derive a modelization for the computation time as a function of the generated surface complexity. The workload associated to each slice of the input data is evaluated by counting the number of vertices that will be generated on that slice. The slices are then locally redistributed to ensure a balanced workload. We give an upper bound on the number of polygons of the triangulation, and present a family of surfaces whose number of triangles tends to this bound. This analysis allows us to foresee (and thus to allocate) the memory size needed for the data structures and to assign to each vertex a unique global reference. Experiments done on an Intel Paragon machine are given both for synthetic and medical images. They show the usefulness of our dynamic data redistribution scheme.