Scalable parallel algorithms for interactive visualization of curved surfaces

ABSTRACT

We present efficient parallel algorithms for interactive display of higher order surfaces on current graphics systems. At each frame, these algorithms approximate the surface by polygons and rasterize them over the graphics pipeline. The time for polygon generation for each surface primitive varies between successive frames and we address issues in distributing the load across processors for different environments. This includes algorithms to statically distribute the primitives to reduce dynamic load imbalance as well a distributed wait-free algorithm for machines on which re-distribution is efficient, e.g. shared memory machine. These algorithms have been implemented on different graphics systems and applied to interactive display of trimmed spline models. In practice, we are able to obtain almost linear speed-ups (as a function of number of processors). Moreover, the distributed wait-free algorithm is faster by 25-30% as compared to static and dynamic schemes.

REFERENCES

• 1: S. S. Abi-Ezzi and L. A. Shirman. Tessellation of curved surfaces under highly varying transformations. Proceedings of Eurographics, pages 385-397, 1991.
• 2: S. S. Abi-Ezzi and S. Subramaniam. Fast dynamic tessellation of trimmed nurbs surfaces. Computer Graphics Forum, 13(3):107-26, 1994. Proc. of Eurographics'94.
• 3: Kurt Akeley, Reality Engine graphics, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.109-116, September 1993 [doi>10.1145/166117.166131]
• 4: David Ellsworth , Howard Good , Brice Tebbs, Distributing display lists on a multicomputer, ACM SIGGRAPH Computer Graphics, v.24 n.2, p.147-154, Mar. 1990
• 5: Henry Fuchs , John Poulton , John Eyles , Trey Greer , Jack Goldfeather , David Ellsworth , Steve Molnar , Greg Turk , Brice Tebbs , Laura Israel, Pixel-planes 5: a heterogeneous multiprocessor graphics system using processor-enhanced memories, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.79-88, July 1989
• 6: G. Georgiannakis and C. Houstis et. al. Description of the adaptive resource management problem, cost functions and performance objectives. Technical Report TR 130, The Institute of Computer Science, Foundation for Research and Technology - Hellas, 1995.
• 7: Bruce Hendrickson , Robert Leland, A multilevel algorithm for partitioning graphs, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.28-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224228]
• 8: Maurice Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.745-770, Nov. 1993 [doi>10.1145/161468.161469]
• 9: G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Technical Report TR95-064, Department of Computer Science, University of Minnesota, 1995.
• 10: Reinhard Klein , Wolfgang Straber, Large mesh generation from boundary models with parametric face representation, Proceedings of the third ACM symposium on Solid modeling and applications, p.431-440, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218097]
• 11: S. Kumar, S. Krishnan, and D. Manocha. Interactive display of large solid models for walkthroughs. IEEE Computer Graphics and Applications, 16(2):9-11, 1996.
• 12: S. Kumar and D. Manocha. Efficient rendering of trimmed NURBS surfaces. Computer-Aided Design, 27(7):509-521, July 1995.
• 13: Subodh Kumar , Dinesh Manocha , Anselmo Lastra, Interactive display of large-scale NURBS models, Proceedings of the 1995 symposium on Interactive 3D graphics, p.51-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199413]
• 14: Leslie Lamport, A fast mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.1-11, Feb. 1987 [doi>10.1145/7351.7352]
• 15: W. L. Luken and Fuhua Cheng. Rendering trimmed NURB surfaces. Computer science research report 18669(81711), IBM Research Division, 1993.
• 16: Carl Mueller, The sort-first rendering architecture for high-performance graphics, Proceedings of the 1995 symposium on Interactive 3D graphics, p.75-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199417]
• 17: Thierry Priol and Kadi Bouatouch. Static load balancing for A parallel ray tracing on a MIMD hypercube. The Visual Computer, 5(1/2):109-119, March 1989.
• 18: D. Roble. A load balanced parallel scan-line z-buffer algorithm for the ipsc hypercube. In Pixim, pages 177-192, Paris, France, 1988.
• 19: Alyn Rockwood , Kurt Heaton , Tom Davis, Real-time rendering of trimmed surfaces, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.107-116, July 1989
• 20: Scott Whitman, Dynamic Load Balancing for Parallel Polygon Rendering, IEEE Computer Graphics and Applications, v.14 n.4, p.41-48, July 1994 [doi>10.1109/38.291530]
• 21: Jae-Heon Yang , James H. Anderson, Fast, scalable synchronization with minimal hardware support, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.171-182, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164072]
• 22: Y. Zheng , Darren J. Kerbyson , Graham R. Nudd, Efficient Load Balancing Techniques for Image Analysis on an M-SIMD Machine, University of Warwick, Coventry, UK, 1992

INDEX TERMS

Keywords:
Surface tessellation, Load balancing, Real-time rendering, Simulation-based Design, Splines