Qualifying Exam for Alvin Leung

Paul Coddington
November 14, 1996

Thesis committee members:
Paul Coddington
Geoffrey Fox
Ernest Sibert

Problem 1

1. Briefly describe the different tasks that are involved for a 3D polygon-based rendering algorithm, and the parallelism available for each task.

2. Choose one of these tasks and write some pseudo-code indicating how the parallelism would be implemented using MPI.

3. What are the potential bottlenecks in implementing a parallel rendering algorithm?

Problem 2

1. Describe how 3D terrain can be modeled using VRML 1.0.

2. Indicate how VRML could be used to add objects such as buildings onto the terrain.

3. What additional elements in the VRML 2.0 standard can be used to improve ther performance of real-time terrain rendering using VRML?

4. What useful elements are still lacking in VRML 2.0?

5. Give a rough estimate of the minimum bandwidth required for real-time rendering of a scene containing 2000 polygons, using:
   • VRML
   • an ideal client/server rendering algorithm, which may use compression algorithms
   • an algorithm which sends rendered 512x512 images for each frame, with and without image compression

Problem 3

1. Give one example of a numerical algorithm for solving a matrix equation of the form Ax = b.

2. Explain how this algorithm could be parallelized.

3. What factors would cause less than perfect speedup for the parallel algorithm?