3D Game Engine Design
A Practical Approach to Real-Time
Computer Graphics
Second Edition
David H. Eberly
Geometric Tools, Inc.
AMSTERDAM • BOSTON • HEIDELBERG • LONDON
NEW YORK • OXFORD • PARIS • SAN DIEGO
SAN FRANCISCO • SINGAPORE • SYDNEY • TOKYO
Morgan Kaufmann is an imprint of Elsevier
Senior Editor Tim Cox
Publishing Services Manager George Morrison
Senior Production Editor Brandy Lilly
Project Management Elisabeth Beller
Cover Design Chen Design Associates, San Francisco
Text Design Rebecca Evans
Composition Windfall Software, using ZzTEX
Technical Illustration Dartmouth Publishing
Copyeditor Yonie Overton
Proofreader
Indexer
Interior and Cover Printer Hing Yip Printers, Ltd.
Jennifer McClain
Steve Rath
Morgan Kaufmann Publishers is an imprint of Elsevier.
500 Sansome Street, Suite 400, San Francisco, CA 94111
This book is printed on acid-free paper.
© 2007 by Elsevier Inc. All rights reserved.
Designations used by companies to distinguish their products are often claimed as
trademarks or registered trademarks. In all instances in which Morgan Kaufmann
Publishers is aware of a claim, the product names appear in initial capital or all
capital letters. Readers, however, should contact the appropriate companies for more
complete information regarding trademarks and registration.
No part of this publication may be reproduced, stored in a retrieval system, or trans-
mitted in any form or by any means—electronic, mechanical, photocopying, scan-
ning, or otherwise—without prior written permission of the publisher.
Permissions may be sought directly from Elsevier’s Science & Technology Rights De-
partment in Oxford, UK: phone: (+44) 1865 843830, fax: (+44) 1865 853333, e-mail:
permissions@elsevier.com. You may also complete your request online via the Elsevier
homepage (http://elsevier.com), by selecting “Support & Contact” then “Copyright
and Permission” and then “Obtaining Permissions.”
Library of Congress Cataloging-in-Publication Data: Application submitted
ISBN 13: 978-0-12-229063-3
ISBN 10: 0-12-229063-1
For information on all Morgan Kaufmann publications, visit our Web site
at www.mkp.com or www.books.elsevier.com.
Printed in the United States of America
10 09 08 07 06
5 4 3 2 1
Trademarks
The following trademarks, mentioned in this book and the accompanying CD-ROM,
are the property of the following organizations:
AltiVec is a trademark of Freescale Semiconductor.
DirectX, Direct3D, Visual C++, Windows, Xbox, and Xbox 360 are trademarks
of Microsoft Corporation.
GameCube is a trademark of Nintendo.
GeForce, Riva TNT, and the Cg Language are trademarks of NVIDIA Corpora-
tion.
Java 3D is a trademark of Sun Microsystems.
Macintosh is a trademark of Apple Corporation.
Morrowind and The Elder Scrolls are trademarks of Bethesda Softworks, LLC.
NetImmerse and Gamebryo are trademarks of Emergent Game Technologies.
OpenGL is a trademark of Silicon Graphics, Inc.
Pentium and Streaming SIMD Extensions (SSE) are trademarks of Intel Corpo-
ration.
PhysX is a trademark of Ageia Technologies, Inc.
Playstation 2 and Playstation 3 are trademarks of Sony Corporation.
PowerPC is a trademark of IBM.
Prince of Persia 3D is a trademark of Brøderbund Software, Inc.
3DNow! is a trademark of Advanced Micro Devices.
3D Studio Max is a trademark of Autodesk, Inc.
v
About the Author
Dave Eberly is the president of Geometric Tools, Inc. (www.geometrictools.com), a
company that specializes in software development for computer graphics, image
analysis, and numerical methods. Previously, he was the director of engineering at
Numerical Design Ltd. (NDL), the company responsible for the real-time 3D game
engine, NetImmerse. He also worked for NDL on Gamebryo, which was the next-
generation engine after NetImmerse. His background includes a BA degree in math-
ematics from Bloomsburg University, MS and PhD degrees in mathematics from the
University of Colorado at Boulder, and MS and PhD degrees in computer science
from the University of North Carolina at Chapel Hill. He is the author of Game
Physics (2004) and 3D Game Engine Architecture (2005) and coauthor with Philip
Schneider of Geometric Tools for Computer Graphics (2003), all published by Morgan
Kaufmann. As a mathematician, Dave did research in the mathematics of combus-
tion, signal and image processing, and length-biased distributions in statistics. He
was an associate professor at the University of Texas at San Antonio with an adjunct
appointment in radiology at the U.T. Health Science Center at San Antonio. In 1991,
he gave up his tenured position to retrain in computer science at the University of
North Carolina. After graduating in 1994, he remained for one year as a research
associate professor in computer science with a joint appointment in the Depart-
ment of Neurosurgery, working in medical image analysis. His next stop was the SAS
Institute, working for a year on SAS/Insight, a statistical graphics package. Finally,
deciding that computer graphics and geometry were his real calling, Dave went to
work for NDL (which is now Emergent Game Technologies), then to Magic Software,
Inc., which later became Geometric Tools, Inc. Dave’s participation in the newsgroup
comp.graphics.algorithms and his desire to make 3D graphics technology available to
all are what has led to the creation of his company’s Web site and his books.
vi
CONTENTS
CONTENTS
CONTENTS
CONTENTS
..............................................................
Preface
..............................................................xxixxixxixxi
Preface
..............................................................
Preface..............................................................
Preface
Introduction
1111 Introduction
......................................................1
Introduction
......................................................1
Introduction......................................................1
......................................................1
o
o
o
1.1 The Evolution of Graphics Hardware and Games
1.2 The Evolution of This Book and Its Software
1.3 A Summary of the Chapters
Graphics
2222 TheTheTheThe Graphics
Graphics
Graphics System
SystemSystemSystem.......................................7
.......................................7
.......................................7
.......................................7
o
2.1 The Foundation
�
�
�
2.1.1 Coordinate Systems
2.1.2 Handedness and Cross Products
2.1.3 Points and Vectors
o
2.2 Transformations
�
�
2.2.1 Linear Transformations
2.2.2 Affine Transformations
vii
�
�
�
2.2.3 Projective Transformations
2.2.4 Properties of Perspective Projection
2.2.5 Homogeneous Points and Matrices
o
2.3 Cameras
�
�
�
�
�
�
�
2.3.1 The Perspective Camera Model
2.3.2 Model or Object Space
2.3.3 World Space
2.3.4 View, Camera, or Eye Space
2.3.5 Clip, Projection, or Homogeneous Space
2.3.6 Window Space
2.3.7 Putting Them All Together
o
2.4 Culling and Clipping
�
�
�
2.4.1 Object Culling
2.4.2 Back Face Culling
2.4.3 Clipping to the View Frustum
o
2.5 Rasterizing
�
�
�
�
2.5.1 Line Segments
2.5.2 Circles
2.5.3 Ellipses
2.5.4 Triangles
�
2.6 Vertex Attributes
2.6.1 Colors
2.6.2 Lighting and Materials
2.6.3 Textures
�
�
o
viii
�
�
�
�
2.6.4 Transparency and Opacity
2.6.5 Fog
2.6.6 And Many More
2.6.7 Rasterizing Attributes
o
2.7 Issues of Software, Hardware, and APIs
�
�
2.7.1 A General Discussion
2.7.2 Portability versus Performance
o
2.8 API Conventions
�
�
�
�
�
�
�
2.8.1 Matrix Representation and Storage
2.8.2 Matrix Composition
2.8.3 View Matrices
2.8.4 Projection Matrices
2.8.5 Window Handedness
2.8.6 Rotations
2.8.7 Fast Computations using the Graphics API
Renderers
3333 Renderers
......................................................147
Renderers
......................................................147
Renderers......................................................147
......................................................147
o
o
o
o
o
3.1 Software Rendering
3.2 Hardware Rendering
3.3 The Fixed-Function Pipeline
3.4 Vertex and Pixel Shaders
3.5 An Abstract Rendering API
ix