Game Physics Engine Development
How to Build a Robust Commercial-Grade Physics Engine for your Game
Second Edition
Ian Millington
Morgan Kaufmann Publishers is an imprint of Elsevier.
30 Corporate Drive, Suite 400, Burlington, MA 01803, USA
This book is printed on acid-free paper.
Copyright 2010 Elsevier Inc. All rights reserved.
No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or any information storage and retrieval system, without permission in writing from the publisher. Details on how to seek permission, further information about the Publishers permissions policies and our arrangements with organizations such as the Copyright Clearance Center and the Copyright Licensing Agency, can be found at our website: www.elsevier.com/permissions.
This book and the individual contributions contained in it are protected under copyright by the Publisher (other than as may be noted herein).
Notices
Knowledge and best practice in this field are constantly changing. As new research and experience broaden our understanding, changes in research methods, professional practices, or medical treatment may become necessary.
Practitioners and researchers must always rely on their own experience and knowledge in evaluating and using any information, methods, compounds, or experiments described herein. In using such information or methods they should be mindful of their own safety and the safety of others, including parties for whom they have a professional responsibility.
To the fullest extent of the law, neither the Publisher nor the authors, contributors, or editors, assume any liability for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions, or ideas contained in the material herein.
Library of Congress Cataloging-in-Publication Data
Millington, Ian.
Game physics engine development : how to build a robust commercial-grade physics engine for your game / Ian Millington. 2nd ed.
p. cm.
Includes index.
ISBN 978-0-12-381976-5 (pbk. : alk. paper)
1. Computer gamesProgramming. 2. PhysicsData processing. I. Title.
QA76.76.C672M55 2010
794.81526dc22
2010014533
British Library Cataloguing-in-Publication Data
A catalogue record for this book is available from the British Library.
ISBN: 978-0-12-381976-5
For information on all Morgan Kaufmann publications visit our Website at www.mkp.com or www.elsevierdirect.com
Typeset by: diacriTech, India
Printed in the United States of America
10 11 12 13 5 4 3 2 1
For Richard
List of Figures
1.1 | Trigonometry and coordinate geometry | 9 |
2.1 | 3D coordinates | 19 |
2.2 | Left- and right-handed axes | 22 |
2.3 | A vector as a movement in space | 23 |
2.4 | The geometry of scalar-vector multiplication | 26 |
2.5 | The geometry of vector addition | 27 |
2.6 | Geometric interpretation of the scalar product | 33 |
2.7 | Geometric interpretation of the vector product | 36 |
2.8 | Same average velocity, different instantaneous velocity | 39 |
4.1 | Screenshot of the ballistic demo | 63 |
4.2 | Screenshot of the bigballistic demo | 65 |
4.3 | Screenshot of the fireworks demo | 66 |
6.1 | The games camera attached to a spring | 92 |
6.2 | A rope bridge held up by springs | 95 |
6.3 | A buoyant block submerged and partially submerged | 98 |
6.4 | A non-stiff spring over time | 102 |
6.5 | A stiff spring over time | 103 |
6.6 | The rest length and the equilibrium position | 108 |
7.1 | Contact normal is different from the vector between objects in contact | 117 |
7.2 | Interpenetrating objects | 122 |
7.3 | Interpenetration and reality | 124 |
7.4 | Vibration on resting contact | 127 |
7.5 | Resolving one contact may resolve another automatically | 131 |
8.1 | Screenshot of the bridge demo | 151 |
8.2 | Screenshot of the platform demo | 152 |
9.1 | Angle that an object is facing | 158 |
9.2 | The circle of orientation vectors | 160 |
9.3 | The relative position of a car component | 161 |
9.4 | The car is rotated | 162 |
9.5 | Aircraft rotation axes | 166 |
9.6 | A matrix basis is changed | 198 |
10.1 | A force generating no torque | 212 |
10.2 | The moment of inertia is local to an object | 217 |
11.1 | Screenshot of the flightsim demo | 241 |
11.2 | Different centers of buoyancy | 243 |
11.3 | Screenshot of the sailboat demo | 247 |
12.1 | The collision detection pipeline | 255 |
12.2 | A three-stage collision detection pipeline | 256 |
12.3 | A spherical bounding volume | 257 |
12.4 | A spherical bounding volume hierarchy | 260 |
12.5 | Bottom-up hierarchy building in action | 267 |
12.6 | Top-down hierarchy building in action | 268 |
12.7 | Insertion hierarchy building in action | 269 |
12.8 | Working out a parent bounding sphere | 272 |
12.9 | Removing an object from a hierarchy | 273 |
12.10 | A subobject bounding volume hierarchy | 275 |
12.11 | A BSP for level geometry | 280 |
12.12 | Identifying an objects location in a quad-tree | 282 |
12.13 | A quad-tree forms a grid | 284 |
12.14 | An object may occupy up to four same-sized grid cells | 287 |
13.1 | An object approximated by an assembly of primitives | 293 |
13.2 | Collision detection and contact generation | 295 |
13.3 | 3D cases of contact | 296 |
13.4 | Ignoring a vertexvertex contact | 297 |
13.5 | The relationship among the collision point, collision normal, and penetration depth | 299 |
13.6 | The vertexface contact data | |