5.2 UNC and Toronto

UNC

Henry Fuchs arrived at the University of North Carolina at Chapel Hill in 1978, after completing his PhD at the University of Utah.^[1] His early work was in the area of binary space partitioning (BSP) trees for optimal determination of visibility in computer generated scenes, 3D data acquisition and construction, and moved to high performance architectures for graphics and hardware visualization techniques. He was appointed the Federico Gil Professor of Computer Science and adjunct professor of radiation oncology, after starting in computer graphics and image processing in 1969. Prof. Fuchs served on the editorial board of ACM Transactions on Graphics from 1983 to 1988, and was the guest editor of its first issue (January 1982). Fuchs received the 1992 Computer Graphics Achievement Award from ACM-SIGGRAPH and the 1992 National Computer Graphics Association Academic Award. He was also selected as an ACM Fellow.

In 1980, the faculty and students at the Graphics and Image Analysis Research center at UNC began exploring computer architectures for 3D graphics that were significantly faster than traditional architectures for applications that required high performance, such as medical visualization. The project that Fuchs started was called Pixel-Planes, and had an emphasis on scalability and real-time rendering.

The principle techniques used revolved around a plane of processors, each with a few bytes of its own memory, operating in unison. Each pixel (picture element) on the screen was associated with a unique processor. Since each processor knew its x and y screen coordinates, the system sent out the equation for a line and each processor computed which side of the line it was on. Sending the equations for three lines allowed for the computing of which processors were inside the lines and how far away from the viewer’s perspective each pixel was. The shading and texturing each of the pixels was done in a similar rapid manner.

The first machine built at UNC under the project was Pixel-Planes 2. Its screen resolution was 4×64 pixels, and only 16 bits of memory per pixel, and was only able to display a few polygons per second. Yet, even with those statistics, this early prototype showed the power of the concepts. Pixel-Planes 4 was a machine that had an array of 512×512 processors operating in synchrony. Each pixel processor had 72 bits of memory at its disposal. The video image was produced directly from what is stored in the memory, and a front-end processor based upon a Weitek chip set performed the initial geometry computations, the results of which were fed to the processor array. This machine could draw at the rate of about 40,000 triangles per second. Pixel-Planes 5 solved some of the problems of Pixel-Planes 4, such as the idleness of the processors when computing images comprised of small polygons.

Instead of a single 512×512 array, it had multiple 128×128 arrays (up to about 20 of them). Each of the processors had 208 bits of primary memory available, plus 4096 bits of secondary memory. In addition, instead of a single geometry processor, there were many (up to about 50) Intel i860 processors. Rather than generate the video image from the memory of the processor arrays, the data was sent to a separate frame buffer. This also allowed the use of multiple frame buffers of various types, including a high resolution (1280×1024) model. The net result of the system was a rendering rate of over 2 million triangles per second.

The next generation machine, PixelFlow (PxFl) used pairs of geometry processors and array processors working independently to create screen-sized images based on the subset of the triangles that they have. The partial images were then combined into one by performing a depth-wise sort using a special high-speed image composition network.

Besides Pixel-Planes, the UNC group worked on virtual environments and other related projects. Fred Brooks, who started the Computer Science Department at UNC in 1964 oversaw that work. Brooks’ contributions were broad, from computer architecture, to human computer interaction, to virtual environments. He was widely published (he was the author of the excellent book, The Mythical Man Month (1975)). He received many awards for his activities, including the National Medal of Technology, the A.M. Turing Award from ACM, John Von Neumann Medal from IEEE, and was both an ACM Fellow and an IEEE Fellow. Brooks’ research on real-time, three-dimensional computer graphics propelled that field forward, driven by the goal of creating tools that enabled scientists and engineers to tackle problems formerly beyond their reach.

The UNC team built the first molecular graphics system on which a new protein structure was solved. They also first proved that haptic displays augmenting visual displays could significantly improve a scientist’s understanding of data.

Brooks was assisted on the research for VR and haptics by Mary Whitton and others. They developed several systems, including Grip, Grope and Docker. They connected haptic feedback to the microscope, and extended it to passive haptics for determining feel such as standing on a ledge.

The ultrasound research group at UNC developed a prototype real-time augmented reality system based on an SGI Onyx workstation equipped with a real-time video capture unit. The camera captured both HMD camera video and ultrasound video. The camera video was displayed in the background; the ultrasound video images were transferred into texture memory and displayed on polygons emitted by the ultrasound probe inside a virtual opening within the scanned patient. This system was used to demonstrate the possibility of using augmented reality to enhance visualization for laparoscopic surgery.
 (Portions of the above text were taken from the UNC Computer Science research webpages.)

Movie 5.7 Pixel Planes

Pixel Planes 4 was one in a series of graphics systems developed at the University of North Carolina in the 1980s.
https://www.youtube.com/watch?v=7mzpZ861wEw

University of Toronto

The University of Toronto Dynamics Graphics Project (dgp) was founded in 1967 by Professor Leslie Mezei. He was joined by Professor Ron Baecker in 1972, who coined the name Dynamic Graphics Project in 1974, when they got their first stand-alone machine, a PDP11/45 with a highly-interactive display informally called the Graphic Wonder. Baecker had completed his PhD in 1969 at MIT, working on the GENESYS animation system.

The dgp lab’s name was intended to imply the spirit of the place, and to encompass both Computer Graphics and Dynamic Interaction Techniques, which was subsumed by the new field of Human Computer Interaction in the early 1980’s. Under the leadership of Baecker, Alain Fournier, Bill Buxton, and Eugene Fiume, dgp became a world academic leader in both computer graphics and human-computer interaction. The lab’s alumni are now on faculty at top universities throughout the world and at major industrial research labs, and have also won academy awards for their groundbreaking work.

Other early work included the Smalltalk animation system SHAZAM. An early animated film done by Baecker called Sorting Out Sorting showed the value of animation in teaching complex concepts.

The dgp at Toronto was very closely tied to the development efforts at Alias, headquartered in Toronto (see more about Alias in Chapter 8.) As was stated in the document referenced at the beginning of this section:

“The dgp‐Alias partnership began in 1992. Alias was recovering from a financial downturn with renewed investments in R&D for computational tools for design and entertainment. Computational power had by then reached the stage where high‐quality interactive graphics was within reach, but a great deal of basic research was still needed. Alias collaborated with various universities on mathematical techniques for modeling surfaces, and on animating and rendering geometric models. However, the modeling of natural phenomena such as smoke, fire, clouds and water was embryonic research. By 1994, Eugene Fiume and his then student Jos Stam demonstrated a new way to model “gaseous and fluid phenomena” that was then licensed by Alias. Stam and Fiume worked with engineers from Alias to integrate these techniques into the Alias design product with astonishing success: the enhanced product drew considerable attention from film animators, and the (now) world‐ renowned animator, Chris Landreth, while working at Alias, used this technology often in completely unexpected ways to create an Academy Award nominated film called “the end”. Dozens of film productions used this work in short order, routinely including Landreth himself, who ten years later won an Academy Award in 2005 for his beautiful film “Ryan”. This film incidentally also involved members of dgp. Jos Stam joined Alias and continued a string of innovations that make him among the most highly cited researchers in computer graphics. His efforts were recognized in a “Computer Graphics Achievement Award” presented by the premier organization in the field, ACM SIGGRAPH. After more years of enhancement, Stam and his colleagues at Alias won a Technical Academy Award for their fluid simulation software. The story has come around full circle, as Stam is now an Adjunct Professor in the Department of Computer Science at the University of Toronto, working with several students in dgp.

Likewise, in the early 1990s, Gord Kurtenbach developed an innovative user interface dialogue technique called “Marking Menus” as part of his Ph.D. work in dgp under the supervision of Bill Buxton. This technology was also transferred to Alias and became central to distinguishing the workflow and user interface of Alias from its competitors. Both Buxton and Kurtenbach then joined Alias, forming the core of a new research group at Alias. This was among the first groups in industry to focus on fundamental research on human‐computer interfaces and on usability engineering. The group, strengthened by more dgp graduates such as George Fitzmaurice and Russell Owen, quickly established an international reputation in HCI, publishing a series of highly cited papers. Bill Buxton went on to become a Chief Scientist of the company.

Fiume joined Alias for several years starting in 1995, going on to establish broadly based Research and Usability Engineering department. This set the stage for a similar growth in computer graphics research as Buxton spearheaded in HCI: Karan Singh and Jos Stam joined the research group, developing new techniques in geometric modeling, deformations, and the modeling of natural phenomena. When Fiume returned to the University of Toronto to chair the Department of Computer Science in 1998, Kurtenbach took over as Director of Research, and both Kurtenbach and Fitzmaurice became Adjunct Professors in the department. By then the Alias Research group was a world leader in both HCI and computer graphics.”

Movie 5.8 Sorting Out Sorting (Excerpt)

“Sorting Out Sorting” was developed to visualize the processes used in different data sorting algorithms.
https://www.youtube.com/watch?v=gv0JUEqaAXo