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 the performance of real-time terrain rendering?

4. Discuss the shortcomings of VRML 2.0 in this context. In particular, propose further additions and argue their utility.

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. You should clearly describe the class of problems to which the algorithm applies.

2. Explain how this algorithm could be parallelized. In doing so, sketch briefly the context (hardware/software) that you have in mind.

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

4. Why is this significant in 3-D rendering?