Computer Graphics and Virtual Environments: From Realism to Real-Time

Mel Slater, Anthony Steed, Yiorgos Chrysanthou

Notes to Instructors

Philosophy of this Book

Computer graphics is usually taught in a 'bottom up' approach, where basic concepts and algorithms from 2D graphics are taught first, followed by more advanced concepts from 3D, and eventually methods that include elements of global illumination at the end. For example, ray tracing is usually one of the last topics. Where 'top down' is mentioned at all, this is more to do with starting from applications rather than the order of the introduction of material - which remains in the usual bottom up sequence.

Through our own teaching we realised over several years that students are often impatient to get onto the 'interesting' 3D material early on in the course. Sometimes the more advanced material is rushed because of too much time spent on the earlier features. Also student projects, separately examined from the Computer Graphics course, often require the material that is taught at the end of the course to be known nearer the start of the course.

A few years ago we tried teaching the course in backwards order comparedto the traditional approach. We started with ray tracing. We ended with Bresenham's algorithm on how to rasterise a line in 2D. This was enormously successful, not just from the point of view of the students, who were producing excellent ray traced images within 2-3 weeks of the start of the course, but also it was more enjoyable to teach. We did not have to grapple with the question: who cares about how to draw a line, the system 'does it for you'. Instead, drawing a line was presented as an interesting subclass of the problem of how to trace a line (in any dimension) through a voxelised space (it became an issue in speeding up ray tracing).

This book is the current distilation of our experience with this approach. It might at first seem strange to be teaching 'hard' topics at the startof the course, but actually it makes things easier. Many of the fundamentalconcepts of graphics can be demonstrated very early on in a practical way,and from almost day one the students can be producing interesting images.Moreover, they can generate many of the ideas themselves with suitable questioning: why exactly is ray tracing comparatively slow, how can it be speeded up?Relax the global illumination and ray-based approaches one by one, and youend up with the classical graphics pipeline.

The book contains several different courses: A basic course on graphics,a basic course on graphics an virtual environments, a more advanced courseon graphics and virtual environments, an itnroductory course for advancedlevel graphics. We give an example of how the book may be used for a basiccourse of 10 weeks with 3 hours per week lectures.

A Basic Course on Graphics

This schedule assumes a typical course with 3 lectures (or 3 hours) per week, plus a discussion section (tutorial) and lab classes. The course is assumed to run over 10 weeks.

Week Topic
Book Chapters/Sections
Introduction to CG
  • Virtual Environments
  • Perceptual Issues
  • Math revision
Chapter 1 (Discussion Section topic - perception and graphics)
Chapter 2 (Discussion Section topic - math revision)

By the end of this week the students should be aware of importance of perceptual issues, know what math they need to revise, get the concept of pixels and display spaces.
Light and Colour
  • The Radiance Equation basics
  • Colour and displays
Chapter 3 (Concentrate on page 82, introduce notion of radiance and the radianceequation)
Chapter 4 (Concentrate around Section 4.8, introducing displays and pixels)

By the end of this week the students should  have a basic understanding of the radianceequation, realising that computer graphics rendering techniques are differenttypes of approximations for solving this equation.
Ray Casting and Illumination
  • Ray casting
  • Illumination models
  • reflection
  • transmission
  • recursive scheme
Chapter 5
Chapter 6, Sections 6.1 to 6.5
Chapter 6, Sections 6.6 to 6.11

By the end of this week the students should know how to do ray casting of spheres, and be able to ray trace sphere with diffuse and specular reflection models.OpenGL might be used forsetting colour values. Using spheres is only for convenience - the conceptsof ray tracing are independent of this. The camera position and orientationis in fixed position along the z-axis.
Viewing in and Scene Construction in 3D
  • camera parameters
  • polygons and planes
  • data structures
  • hierarchies
Chapter 7
Chapter 8
  • Generalise beyond spheres to polygons, explaining the plane equation.
  • Talk about Vertex-Face data structure (skip Winged Edge)
  • Introduce the object hierarchy

By the end of this week the students should understand how the camera isgeneralised to arbitrary position and view, and how thiscan be used withray tracing.Also the  fundamentals ofdescribing scenes with polygonsare covered.An exercise using VRML and a browser tocreate and display theirown sceneswould be useful.
  • Complete viewing parameters
  • perspective
  • clipping planes
  • the composite matrix
  • using OpenGL
Chapter 9, Sections 9.1 to 9.8

Show how the full projection system works.  Some of the details canbe skipped. None of these is mathematically hard, but you can leave the students to follow the derivations in the text without spending time on these in the lectures. Go over how viewing works in OpenGL, and a good teaching device is to concentrate on how the system presented here can be implemented using OpenGL.

By the end of this week the students should understand how to set up an arbitrary camera view, and use OpenGL to achieve this. They should have a good understanding of the idea of projection, and the pipeline that implements this.
  • clipping polygons in 2D
  • clipping in 3D
Chapter 10

Go through the 2D Sutherland-Hodgman clipping algorithm in detail.
Show how it generalises simply to 3D.
Discuss its problems.
Talk about the problem of external line segments, but not necessarily all the details of how to clip in homogeneous coordinates.

By the end of this week the students should understand why clipping is necessary, where it fits in to the pipeline, and how to do it in the case of polygons.
  • Rendering 2D polygons
  • z-buffer algorithm
  • smooth shading
Chapter 12
Chapter 13 (Sections 13.1 to 13.3)

The first lecture this week covers 2D polygon rendering. This is then extended in lectures 2 and 3 to cover z-buffer visibility and smooth shading.

By the end of this week students will know how to implement a 2D polygonalgorithm,and how to (trivially) extend this to cover z-buffer visibility processing and smooth shading. This essentially completes the graphics pipeline,by showing what happens in the 'last instance' as pixels are processed. Issues such asaliasing could be considered in discussion sections.
Texturing and Shadows
  • Texture Mapping
  • Shadows for point sources
  • Introduction to area sources.

Chapter 13 (Sections 13.4)
Chapter 14 (Sections 14.1-14.2)

By the end of this week students will understand the importance of texture mapping, and how it fits in to the rendering pipeline. Students will be able to implement shadows based on z-buffering and BSP trees, for point light sources. Students will understand the issues involved in computation and rendering of shadows for area sources.
  • Radiosity equations
  • form-factors
  • progressive refinementh
Chapter 14 (Sections 15.1 to 15.5, 15.7 to 15.8)

This week reintroduces global illumination in the context of radiosity. The radiosity equations can be illustrated simply as an expansion of (EQ 3.20) without necessarily deriving all the components and starting from the full radiance equation. Eg, (EQ 15.11) is essentially 'obvious' and can be 'derived' from common sense arguments. The hemi-cube, progressive refinement and ray-casting approaches should be covered.

By the end of this week the students will understand and have some reasonable idea how to implement progressive refinement radiosity with the use of ahemi-cube or with ray casting. They will understand how the Gouraud smoothshading,introduced last week can be used for rendering.
Faster ray tracing
  • optimising ray-intersections
  • clipping lines
  • rasterising lines
  • tracing lines through subdivided space
Chapter 16
Chapter 17 (Sections 17.1 to 17.3)

The course returns full circle to ray tracing, and there is a motivationchapter that considers in outline how ray tracing intersection calculationsmightbe speeded up. This serves as motivation for further work on lines:clippingand rasterisation. Line clipping algorithms are discussed (one shouldbe discussed in detail such as Cohen-Sutherland) and of course Bresenham'salgorithm in detail.

By the end of this week the students should know a number of strategies for speeding up ray tracing. The will also know how to clip lines in 2D and in 3D, and how to rasterise a line in 2D - realising that a generalisation of this to 3D and to subdivided spaces is possible.

From the Preface

This book is aimed at senior year undergraduates (typically final year BSc Computer Science students) or postgraduates studying computer graphics or the visual aspects of virtual environments. It can be used for an approximately full semester (30-45 hours) course. The aim of the book is to give students practical knowledge of the fundamentals of the graphics rendering pipeline, modern techniques to maximize the frame rate, and also some in-depth information about rendering photo-realistic images. The major focus of the book, in terms of motivation, is virtual environments. We therefore take care not simply to present algorithms for computer graphics, but put these in the context of VEs and some of the basic underlying perceptual issues in these areas.

One path through the book for an undergraduate course might be as follows: Start the lectures with Chapter 5, which introduces ray casting in the context of a simple scene made of spheres. The purpose of this is that from day one the students are involved in the actual process of building a system that will (very soon) allow them to generate globally illuminated scenes withray tracing. Meanwhile devote discussion sections and tutorials to Chapters1through 4, which cover perceptual issues (do the simple perceptual experimentsdescribed in that chapter, they can be a great deal of fun as well as beingeducational), check over the mathematics in Chapter 2 (not everyone willbefamiliar with all the concepts described in that chapter) then cruciallydevoteresources to Chapter 3 on the general problem of lighting and theradianceequation.Almost certainly one or two lectures as well as discussiongroupsshould bedevoted to this, since the radiance equation is essentiallywhatcomputer graphicsrendering is all about, and the rendering equationactsas a unifying principlefor all the chapters on rendering. Then continuetodiscuss color perception(Chapter 4). Meanwhile the lectures can moveon toray tracing, and the studentsgiven ray tracing programming assignmentstocarry out (just for simple scenescontaining spheres). Within about threeweeks the students will be generatingray traced images (a great boost toconfidence) and know something about thecentral equation of graphics rendering- the radiance equation.

Chapters 7 through 13, which show how to build a real-time system can bemotivated by asking a few questions. Why is ray tracing so slow? How canwe represent scenes with objects other than spheres? How can we render froman arbitrary virtual camera position? If we lose the global illuminationcharacteristics of ray tracing, how can we shade anything? If each pointwithin each object has to be shaded, how is it possible to have real-timerendering? If we lose the automatic visibility computations of ray tracing,how can we compute visibility in general scenes? By the end of Chapter 13the readers should have a very good idea of how to build a complete 3D graphicssystem, starting from one single primitive function: how to set a pixel toa specific color. So although our approach is ‘top down’ in thelast instance it is also ‘bottom up’, since that is the ultimatepoint of Chapters 7 through 13 - how to build such a system from the bottomup.

A certain type of undergraduate course can then move straight to Chapter15, and sample how radiosity solutions are achieved. Then round things outwith a return to ray tracing in Chapter 16 - how to speed this up. Finallycomplete the course by studying Chapter 17 - the most basic of graphics algorithms, how to clip and render lines (remember that the motivation for these operations would have been given in the faster ray tracing chapter 17).

Now a more in-depth course would have followed Chapters 7 through 13 with a close look at how shadows can be generated in real-time (Chapter 14) before studying radiosity and then faster ray tracing. The chapters on constructive solid geometry and curves and surfaces for computer aided geometric design are stand-alone. Such a more in-depth course could then move to Chapters22 and 23 which discuss more advanced issues in global illumination and real-time rendering.

If the reader is also interested in interaction within virtual environments, and common problems within real-time interaction systems such as collision detection, then it is a good idea to take a break from rendering and study Chapters 20 and 21 at this point.