Practical Algorithms for
3D Computer Graphics		 pa3dcg_thumb.jpg (14098 bytes)

by R. Stuart Ferguson
published by A.K. Peters Ltd.
Last Updated 20 October 2006

This is the Web site for the book Practical Algorithms for 3D Computer Graphics by Stuart Ferguson
ISBN: 1-56881-154-3
List Price: $49 from A.K. Peters
552 pages. Paperback.

This web page contains information on the Book Contents and a List of Corrections

What is the Book About?
Taken as a whole, the topics covered in this book will enable you to create a complete suite of programs for three-dimensional computer animation, modeling and image synthesis. It is about practical algorithms for each stage in the creative process. The text takes you from the construction of polygonal models of objects (real or imaginary) through rigid body animation into hierarchical character animation and finally down the rendering pipeline for the synthesis of realistic images of the models you build.

The content of the book arises from a postgraduate course on computer graphics that I have given for many years and the experience of working on two comprehensive 3D animation and modeling application programs ( Envisage 3D and   SoftFX) for the personal computer in the 1990s. In that time the capabilities of both the hardware and software for creating computer graphics have increased almost unimaginably.

Until the appearance (in the 1980s) of the personal computer, experiments with 3D graphics were limited to the lucky few who had access to some very expensive equipment. Even then, the images produced were, well, somewhat rudimentary. Some of the first 3D graphics emerged from the Computer Aided Design (CAD) industry. Even on the newly emerging super-minicomputers the most one could hope to see appearing from the plotter was a wireframe drawing or, if you were very lucky, a slightly more solid look, achieved by a very slow hidden line algorithm. It wasn't until the work of Jim Blinn with his animated simulations of NASA's Voyager space probe that it began to dawn on the viewer that computers had the potential to generate moving pictures to rival real photographs!

All this seems a world away from the images that we almost take for granted today. Now it is almost impossible to tell a computer generated picture apart from a photograph. Very often the only visual clue is that it would be impossible to get such a shot with a real camera. Perhaps the most amazing fact is that these stunning images are produced, not on a $10m supercomputer, but on the machine sitting in the corner of most people's living rooms, the humble $1000 personal computer a piece of hardware that is mostly used for typing letters or playing games. Perhaps surprisingly, it is the games and multimedia PC businesses that forced 1980s supercomputer processing power onto everyone's laptop.

So, what does it take to turn the domestic typewriter or Internet terminal into a graphics workstation? It's the software of course, and all graphics software relies on basic mathematics and fairly simple algorithms.

Therefore:

It is the primary purpose of this book to present the key algorithms that lie at the heart of all three-dimensional computer graphics software packages.

I hope to be able to introduce these algorithms in such a way that they can readily be put into practice. I will try to describe them in a way that doesn't limit their application to any one particular family of computers. I will attempt to cover a spectrum of useful algorithms; from the simple act of transforming between coordinate systems to the sophisticated `Boolean' operation, Inverse Kinematics and beautiful surface textures. Where possible the algorithms are accompanied by practically useful computer codes. I hope that, by concentrating on algorithms, most of the content of the book will not be overtaken too rapidly by events such as the release of a new version of a particular operating system.

A quick look at the contents of the book
The book is divided into three parts. The first, Basic Principles, covers the key concepts of 3D computer graphics. After a brief introduction in Chapter 1, the focus moves to the fundamental mathematical ideas (Chapter 2) that lie at the heart of all the other algorithms discussed in the book. Personally, I find it very satisfying that in just a few pages we can set out all the maths you need to produce beautiful photorealistic pictures.

A computer generated image of a 3D universe requires that the objects which inhabit it are described using numbers and stored in some form of structured database. Chapter 3 discusses the pros and cons of 3D data organization and describes several algorithms that are useful in manipulating faceted models of the universe's inhabitants.

Chapters 4 and 5 cover the topic of rendering and take a step by step approach to the design of algorithms, from the fastest scanline Z buffer procedure to the high quality ray-traced approach. I have tried to include those little things that generally get overlooked in the grand theoretical texts but are of practical importance, for example how to optimize your 3D database for ray tracing.

A very active area in Computer Graphics software development today is animation, and character animation in particular. Chapter 6 outlines the basic principles of animation techniques and discusses some ideas for character animation and other effects that can be expressed procedurally rather than having to do it by hand. The principles of Inverse Kinematics are introduced and presented in a way specific to computer animation.

The second part of the book is intended for the professional `plugin' or game engine developer and provides (hopefully) a rich collection of algorithms covering such diverse topics as polygonal modeling procedures (Chapter 7), pseudo three-dimensional video transition effects (Chapter 8) and procedural textures for use with a photorealistic Z buffer or ray tracing renderer (Chapter 9).

The final part of the book is devoted to example programs produced with widely available 3D graphics libraries. I have concentrated on examples for Microsoft's Windows operating system primarily executing on PC platforms using the Intel microprocessor. I have chosen to explore two graphics libraries because their Application Programming Interfaces (APIs) are so different. One has wide acceptance and the other growing popularity. OpenGL has an established history and is now available for all versions of Windows. In 1996 Microsoft introduced a system called Direct3D that has growing popularity, particularly among 3D game developers. Chapters 10 and 11 exemplify the use of these APIs by showing the step by step development of programs that draw (in real time) views of 3D objects such as those produced by 3DS Max, SoftImage etc. Chapter 12 shows you how to develop a Windows program that bypasses all the bottlenecks imposed by the system when you want to play animated image sequences (movies) so that they occupy the full screen and run at maximum speed.

Target readership
I hope that this book will be useful for anyone embarking on a graphics research program, starting work on a new 3D computer game, beginning a career in an industry associated with computer graphics or just wanting a reference to a range of useful algorithms.

I would also hope that the algorithms presented in Part 2 might prove useful for more experienced professional software developers, typically any of you who wish to write plug-in modules for any 3D application program or games engine commercially available today.

Assumed Knowledge
I make the assumption that the reader is familiar with the concepts of the Vector and has a basic knowledge of Coordinate Geometry. Some experience of using 3D graphics application software would also be an advantage, at least enough to know the significance of the terms, Vertex, Triangular Facet/Polygon and Pixel. For the programming sections, a knowledge of the C programming language would be a decided advantage and to make full use of the Windows examples it would help if the reader has used Visual~C++ or the Windows Software Development Kit.

 

Detailed Contents List

The book consists of 12 chapters with accompanying code and examples on CD-ROM

The book is presented in three parts:

Contents list:

Part 1 Basics

Part 2 Practical Algorithms: Modelling Video Processing and Procedural Textures

Part 3 Real Time  3D Graphics for Windows 95/98/NT

Appendices

What is on the CD:

Algorithm_code
This folder contains a number of files with the C++ (which are C compatible too) codes for many of the algorithms discussed in the text, particularly the code for the algorithmic textures and video effects. The name of each file reflects its function or the chapter it is associated with. For example the file named "Chap7_1.cpp" holds the code for the algorithm that fills (or caps) a non-convex polygonal outline. The files are liberally populated with detailed comments that describe the data structures used in the code. Hopefully reading these files will enhance the explanations given in the book.

Direct3D_programs
This folder contains a number of subfolders in which you will find all the project files at five stages in the development of the Direct 3D example introduced in Chapter 11. The final project may be built by opening the Visual C++ workspace in /Direct3d_programs/d3d_5/d3d.mdp. You will need to have Microsoft Visual C++ version 4.0 or greater. VC5 or VC6 can convert the VC4 workspace file to their specific format. You will also need to have DirectX 3 or greater. At the time of preparation the latest DX release is DirectX 8. Since some of the Direct X libraries are required you may have to set some of the VC settings to make sure that your DX SDK is in the path for both header files and library files and BEFORE the standard 'includes' that Visual C++ uses.

OpenGL_programs
This folder contains a number of subfolders in which you will find all the project files at six stages in the development of the OpenGL example introduced in Chapter 10. As with the Direct3D examples you will need MSVC version 4 or greater and the *.mdp project files can again be used with MSVC versions 4, 5, or 6. This time MSVC has all the required OGL libraries so you shouldn't need a separate SDK. The folder /OpenGL_programs/gl3d contains a working version of a program that can be used to view polygon models build with the commercial applications 3DStudio and SoftFX. The Final version of the GL3D application GL3d_6 is a multi-document application and the folder GL3D_SDI is the single document equivalent.

DirectDraw_player
This folder contains the code to build the Animation player that used the DirectDraw API as described in Chapter 12. This program does not use the MFC classes as used in Chapters 10 & 11, instead it is a minimal C language application. As a result it must be built from the CLI (DOS box). Again it is designed to be built with MSVC, but this time, using the NMAKE utility. To build the application open the CLI and after making sure the PATH variable is set correctly for your compiler issue the command 'NMAKE' the application should build to the DDPLAY.EXE. Here again you will need to make sure that the DirectDraw SDK libraries & header files are visible on your paths.

Inverse_kinematics
This is a folder containing some 'experiment code' that implements the algorithms of Inverse Kinematics discussed in Chapter 6. Have a look at it, read the comments, and follow the implementation of Jacobians, iteration, etc. in comparison with the pure 'math implementation' in the text.'

Texture_images
The texture images that appear in Chapter 9 are include here in JPEG file format, just because they look great in colour.

Images
Some images that illustrate various aspects of topics covered in the book are included here for illustrative purposed. Hi-res versions of the colour plates and lens flares along with hires images of the Video Camera illustrating image mapping and bump and reflection mapping are also here.
The images named raytrace_xxx.jpg illustrate how a scene full of mirrors, lenses and refractive fluids appears with and without raytracing in effect.

Animations
We include here some animations that illustrate various aspects of the topics covered in the book. (They also take up a lot of space - I hate to see a CD that appears almost empty - so this one is quite full). They can also be used to test the DirectDraw player and you will find 3 player programs in this folder also, however the .AVI movie format can readily be viewed with the standard MS Media player and a host of others too, the .FLC format (which is very good for high-speed playing) is not usually supported by these players.
Three of the animations need special mention as they were produced by students taking my course in 3D graphics, they illustrate some interesting effects.

  1. The 'submersible' movie by Colin Murray' illustrates how one 'texture' namely an undulating wave can be used on a surface to give the illusion of another effect. In this case a 'bump map' representing ripples on a liquid surface is used to give the appearance of the 'caustics' that one seen on the sea bed or bottom of a swimming pool. Without this trick the same effect would require the use of a very time consuming ray-tracing technique. This animation also illustrates the use of a simple 'morph' between two shapes, in this case the swimming shark has two polygonal forms and as it swims along a path the model changes back and forth between its two alternative forms.
  2. The 'monastery' animation by Kate Devlin is an excellent illustration of how an irregular shape modelled fairly coarsely ( 156 vertices & 320 polygons), namely the Celtic cross, can be richly embellished with a fairly low resolution image map to give a highly realistic result. (See also the book spine).
  3. The 'audio track' MPEG movie by David McVeigh is included because I think it is one of the nicest pieces of work that includes a synchronised sound track to a piece of fairly simple animation work involving the the concept of character animation using an embedded skeleton.

Please remember that these students were engineers/programmers and not skilled artists and they only had their own personal computers to work on!

The other animations on the disk illustrate other algorithms discussed in the book. I'll leave it up to you to decide what features I am attempting to illustrate.

 

Corrections:

Page ix line end of line 4: One too many 's', it should read   'objects' not 'objectss'
Page 16 Four lines up: At the end of the sentance both the symbols P1 and P2 should be in Bold typeface i.e. vectors.
Page 18 Equation 2.1: The '-' sign on the left hand side should be a '+'
Page 20: There is a mix up amongst the ALPHAs and BETAs. Line 5 should read "Snell's law gives a value for ALPHA which..."  The equation on line 7 should have ALPHA on the left hand side i.e. ALPHA = ni/nr.
At the end of Line 8 again it should read "...a quadratic in BETA:"  and on line 13 it should read "...a meaningful value of BETA is substituted..."
Many thanks to Dr Karen McMenemy who diligently worked through the algebra and spotted this nasty little goof!
Page 30: Fig 2.15: The Rotations around the Z axis are not as indicated by PI/2 they are by PI/4 (45 degrees) Thanks again to Karen for pointing this error out.
Page 47 Line 9:  (the expression for K0x) should read on the RHS Xi (S subscript i) (not X dash sub i). Thanks to Matthew Boelter for this.
Page 47 Equation 2.26: The fractional component should NOT be 3/2 it shouls be 1/2, again thanks to Matthew Boelter.
Page 48 Equation 2.29: There is a misplaced parenthesis in equation 2.29. The first 'right parenthesis' should be after the 'Si' and not after the 'hi' . I'm grateful to Scott Schuff for this correction.
Page 116  Line 1: The triangle that is removed is not BCD as indicated but of course BDE. Thanks to Connor Moore for getting this one.
Page 125 bottom line equation for COS (THETA):  The vector (p - PL) should be normalised. (Divide by |p-PL|). Thanks to Dave Beveridge for spotting this.
Page 126 8 lines up - the first equation for 'b': Both sides of the terms on the right had side should be negative.  Thanks again to Dave Beveridge for spotting this.

Page 127 4th line, equation Is = with the alpha/2:  There should NOT be a factor of 1/2 multiplying the alpha. The RHS should read: (2 cos alpha - 1) to power m. Thanks to Dave Beveridge for spotting this.
Page 279 line 2: Insert the word 'to' between 'as' and 'what'
Page 284 Figure 7.44: The identities of vertices V2 and V3 should be swapped. Thanks to Darrell Plank for spotting this one.
Page 483: line 3: Insert the word 'the' between 'with' and 'following'

 

Hit Counter Visits since 01-Sept-2001