R. Stuart Ferguson - Practical Algorithms for 3D Computer Graphics

PRACTICAL ALGORITHMS FOR 3D COMPUTER GRAPHICS S E C O N D E D I T I O N K18939_FM.indd 1 11/15/13 1:51 PM This page intentionally left blank PRACTICAL ALGORITHMS FOR 3D COMPUTER GRAPHICS S E C O N D E D I T I O N R. STUART FERGUSONTHE QUEENS UINVERSITY OF BELFASTUK Boca Raton London New York CRC Press is an imprint of the Taylor & Francis Group, an informa business A N A K P E T E R S B O O K K18939_FM.indd 3 11/15/13 1:51 PM CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 2014 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Version Date: 20131112 International Standard Book Number-13: 978-1-4665-8253-8 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site athttp://www.taylorandfrancis.comand the CRC Press Web site athttp://www.crcpress.com Contents Preface ix I Basic principles Introduction 1.1 A note on mathematics for 3D computer graphics........ 1.2 Getting up to speed and following up............... 1.3 Assumed knowledge........................ 1.4 Computer graphics and computer games............. 1.5 The full spectrum.......................... 1.5 The full spectrum..........................

Basic theory and mathematical results 2.1 Coordinate systems......................... 2.2 Vectors............................... 2.3 Homogeneous coordinates..................... 2.4 The line in vector form....................... 2.5 The plane.............................. 2.7 Closest distance of a point from a line.............. 2.8 Closest distance of approach between two lines......... 2.9 Reflection in a plane........................ 2.10 Refraction at a plane ....................... 2.11 Intersection of a line with primitive shapes............ 2.12 Transformations.......................... 2.13 Parametric curves ......................... 2.14 Interpolation............................ 2.15 Bzier curves............................ 2.16 Splines ............................... 2.17 Parametric surfaces ........................ 2.18 Angular interpolation (quaternions)............... v vi CONTENTS Data structures for 3D graphics 3.1 Integer coordinates ........................ 3.2 Vertices and polygons....................... 3.3 Algorithms for editing arrays of structures ........... 3.4 Making an edge list from a list of polygonal faces ....... 3.5 Finding adjacent polygons .................... 3.6 Finding polygons adjacent to edges ............... 3.6 Finding polygons adjacent to edges ...............

Basic visualization 4.1 The rendering pipeline....................... 4.2 Hidden surface drawing and rasterization............ 4.3 Anti-aliasing ............................ 4.4 Lighting and shading........................ 4.5 Materials and shaders....................... 4.7 Perlin noise............................. 4.8 Pseudo shadows .......................... 4.9 Line drawing............................ 4.10 Tricks and tips........................... 4.10 Tricks and tips...........................

Realistic visualization 5.1 Radiometric lighting and shading ................ 5.2 Ray tracing............................. 5.3 Ray tracing optimization...................... 5.4 Multi-threading and parallel processing............. Computer animation 6.1 Keyframes (tweening)....................... 6.3 Character animation........................ 6.4 Inverse kinematics......................... 6.5 Physics............................... 6.6 Animating cloth and hair..................... 6.7 Particle modeling ......................... 6.7 Particle modeling .........................

II Practical 3D graphics Real-time 3D: OpenGL 7.1 The basics ............................. 7.2 Native programming........................ 7.3 The GL shading language..................... 7.4 The P-buffer and framebuffer objects............... 7.5 Rendering a particle system using OpenGL........... CONTENTS vii 7.6 Summing up ............................

Mobile 3D: OpenGLES 8.1 OpenGLES............................. 8.2 3D on iOS.............................. 8.3 3D on Android........................... 8.4 Summing up ............................ The complete package: OpenFX 9.1 Using OpenFX........................... 9.3 Coordinate system and units................... 9.4 User interface implementation .................. 9.5 The Animation module ...................... 9.6 The Designer module........................ 9.7 The Renderer module....................... 9.8 Adding to the software....................... 9.9 Continuing to dissect OpenFX.................. 9.9 Continuing to dissect OpenFX..................

III Practical algorithms for modeling and procedural textures 10 Modeling with polygonal datasets 10.1 Triangulating polygons ...................... 10.2 Triangulating polygons with holes ................ 10.3 Subdividing polygonal facets................... 10.4 Lofting................................ 10.5 Surfaces of revolution....................... 10.7 Orienting surface normals..................... 10.8 Delaunay triangulation ...................... 10.9 Boolean modeling ......................... 10.10Metaball modeling and marching cubes............. 10.11Texture coordinate generation................... 10.12Building polygonal primitives................... 11 Algorithms for procedural textures 11.1 A standard interface........................ 11.2 CPU textures............................ 11.3 GPU textures ........................... 11.4 Fur and short hair......................... 11.4 Fur and short hair.........................

Bibliography Index This page intentionally left blank Preface 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 first edition of the book, published in 2001, arose from my experience of working on two comprehensive commercial 3D animation and mod eling 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 increased almost unimaginably. Back in 2001 it was hard to envisage how radically the graphics scene would change again as the special purpose graphics processors (GPUs) rolled out, with ever increasing capabilities.