Department of Electronics and Systems, University of A Coruña
E--15071 A Coruña, Spain.
E--mail: {emilioj, margamor, doallo}@des.fi.udc.es
*Department of Electronic and Computer Eng., University of Santiago de Compostela
E--15782 Santiago de Compostela, Spain.
E--mail: mboo@dec.usc.es
Surface subdivision in real time is highly desirable for computer graphics, geometric modeling, and scientific visualization. In this paper we present a parallelization of the Modified Butterfly algorithm based on the subdivision of the original mesh into small groups. The groups are sorted in decreasing order of number of triangles per group, and the sorted groups are cyclically distributed on the processors in order to balance the load. So as to avoid cracking effects among groups a slight modification of the Modified Butterfly algorithm is used. Finally, we evaluate the algorithm on a SGI Origin 2000 system.
Keywords: surface subdivision, distributed memory multiprocessor, grouping algorithm, parallel implementation, Modified Butterfly