real Time Collision Detection.pdf

发布时间：2022-06-30 发布人：admin 分类：说明书资料大小：3.15M 资料格式：pdf 举报版权申诉

1285a8b1-e308-40b9-9549-514355406b2b.pdf-第1页.png

第1页 / 共633页

1285a8b1-e308-40b9-9549-514355406b2b.pdf-第2页.png

第2页 / 共633页

1285a8b1-e308-40b9-9549-514355406b2b.pdf-第3页.png

第3页 / 共633页

1285a8b1-e308-40b9-9549-514355406b2b.pdf-第4页.png

第4页 / 共633页

1285a8b1-e308-40b9-9549-514355406b2b.pdf-第5页.png

第5页 / 共633页

1285a8b1-e308-40b9-9549-514355406b2b.pdf-第6页.png

第6页 / 共633页

1285a8b1-e308-40b9-9549-514355406b2b.pdf-第7页.png

第7页 / 共633页

1285a8b1-e308-40b9-9549-514355406b2b.pdf-第8页.png

第8页 / 共633页

Front Cover

Real-Time Collision Detection

Contents

List of Figures

Preface

Chapter 1. Introduction

1.1 Content Overview

1.2 About the Code

Chapter 2. Collision Detection Design Issues

2.1 Collision Algorithm Design Factors

2.2 Application Domain Representation

2.3 Types of Queries

2.4 Environment Simulation Parameters

2.5 Performance

2.6 Robustness

2.7 Ease of Implementation and Use

2.8 Summary

Chapter 3. A Math and Geometry Primer

3.1 Matrices

3.2 Coordinate Systems and Points

3.3 Vectors

3.4 Barycentric Coordinates

3.5 Lines, Rays, and Segments

3.6 Planes and Halfspaces

3.7 Polygons

3.8 Polyhedra

3.9 Computing Convex Hulls

3.10 Voronoi Regions

3.11 Minkowski Sum and Difference

3.12 Summary

Chapter 4. Bounding Volumes

4.1 Desirable BV Characteristics

4.2 Axis-aligned Bounding Boxes (AABBs)

4.3 Spheres

4.4 Oriented Bounding Boxes (OBBs)

4.5 Sphere-sweptVolumes

4.6 Halfspace IntersectionVolumes

4.7 Other BoundingVolumes

4.8 Summary

Chapter 5. Basic Primitive Tests

5.1 Closest-point Computations

5.2 Testing Primitives

5.3 Intersecting Lines, Rays, and (Directed) Segments

5.4 Additional Tests

5.5 Dynamic Intersection Tests

5.6 Summary

Chapter 6. Bounding Volume Hierarchies

6.1 Hierarchy Design Issues

6.2 Building Strategies for Hierarchy Construction

6.3 Hierarchy Traversal

6.4 Sample BoundingVolume Hierarchies

6.5 Merging BoundingVolumes

6.6 Efficient Tree Representation and Traversal

6.7 Improved Queries Through Caching

6.8 Summary

Chapter 7. Spatial Partitioning

7.1 Uniform Grids

7.2 Hierarchical Grids

7.3 Trees

7.4 Ray and Directed Line Segment Traversals

7.5 Sort and Sweep Methods

7.6 Cells and Portals

7.7 Avoiding Retesting

7.8 Summary

Chapter 8. BSP Tree Hierarchies

8.1 BSP Trees

8.2 Types of BSP Trees

8.3 Building the BSP Tree

8.4 Using the BSP Tree

8.5 Summary

Chapter 9. Convexity-based Methods

9.1 Boundary-based Collision Detection

9.2 Closest-features Algorithms

9.3 Hierarchical Polyhedron Representations

9.4 Linear and Quadratic Programming

9.5 The Gilbert–Johnson–Keerthi Algorithm

9.6 The Chung–Wang Separating-vector Algorithm

9.7 Summary

Chapter 10. GPU-assisted Collision Detection

10.1 Interfacing with the GPU

10.2 Testing Convex Objects

10.3 Testing Concave Objects

10.4 GPU-based Collision Filtering

10.5 Summary

Chapter 11. Numerical Robustness

11.1 Robustness Problem Types

11.2 Representing Real Numbers

11.3 Robust Floating-point Usage

11.4 Interval Arithmetic

11.5 Exact and Semi-exact Computation

11.6 Further Suggestions for Improving Robustness

11.7 Summary

Chapter 12. Geometrical Robustness

12.1 Vertex Welding

12.2 Computing Adjacency Information

12.3 Holes, Cracks, Gaps and T-Junctions

12.4 Merging Co-planar Faces

12.5 Triangulation and Convex Partitioning

12.6 Consistency Testing Using Euler’s Formula

12.7 Summary

Chapter 13. Optimization

13.1 CPU Caches

13.2 Instruction Cache Optimizations

13.3 Data Cache Optimizations

13.4 Cache-aware Data Structures and Algorithms

13.5 Software Caching

13.6 Aliasing

13.7 Parallelism Through SIMD Optimizations

13.8 Branching

13.9 Summary

References

Index

About the CD ROM

RELATED TITLES FROM THE MORGAN KAUFMANN SERIES IN INTERACTIVE 3D TECHNOLOGY

Accurate and efﬁcient collision detection in complex environments is one of the foundations of today’s cutting-edge computer games. Yet collision detection is notoriously difﬁcult to implement robustly and takes up an increasingly large fraction of compute cycles in current game engines as increasingly detailed environments are becoming the norm. Real-time Collision Detection is a comprehensive reference on this topic, covering it with both breadth and depth. Not only are the fundamental algorithms explained clearly and in detail, but Ericson’s book covers crucial implementation issues, including geometric and numeric robustness and cache-efﬁcient implementations of the algorithms. Together, these make this book a “must have”practical reference for anyone interested in developing interactive applications with complex environments. Christer Ericson’s Real-time Collision Detection is an excellent resource that covers the fundamentals as well as a broad array of techniques applicable to game development. –Matt Pharr, Senior Software Developer, NVIDIA –Jay Stelly, Senior Engineer,Valve Christer Ericson provides a practical and very accessible treatment of real-time collision detection. This includes a comprehensive set of C++ implementations of a very large number of routines necessary to build such applications in a context which is much broader than just game programming. The programs are well-thought out and the accompanying discussion reveals a deep understanding of the graphics, algorithms, and ease of implementation issues. It will ﬁnd a welcome home on any graphics programmer’s bookshelf although it will most likely not stay there long as others will be constantly borrowing it. –Hanan Samet, Professor of Computer Science, University of Maryland Real-Time Collision Detection is an excellent resource that every serious engine programmer should have on his bookshelf. Christer Ericson covers an impressive range of techniques and presents them using concise mathematics, insightful ﬁgures, and practical code. –Eric Lengyel, Senior Programmer, Naughty Dog If you think you already know everything about collision detection, you’re in for a surprise! This book not only does an excellent job at presenting all the collision detection methods known to date, it also goes way beyond the standard material thanks to a plethora of juicy, down-to-earth, hard-learned implementation tips and tricks. This produces a perfect blend between theory and practice, illustrated by the right amount of source code in appropriate places. Basically the book just oozes with experience. Christer doesn’t forget all the alternative topics that, despite not directly related to collision detection, can ruin your implementation if you don’t include them in your design. The chapters on robustness and optimization are priceless in this respect. Its carefully crafted compact kd-tree implementation beautifully concludes a unique book full of luminous gems. –Pierre Terdiman, Principal Software Engineer, NovodeX AG (author of the OPCODE collision detection library)

This Page Intentionally Left Blank

Real-Time Collision Detection

The Morgan Kaufmann Series in Interactive 3D Technology Series Editor: David H. Eberly, Magic Software, Inc. The game industry is a powerful and driving force in the evolution of computer technology. As the capabilities of personal computers, peripheral hardware, and game consoles have grown, so has the demand for quality information about the algorithms, tools, and descriptions needed to take advantage of this new technology. To satisfy this demand and establish a new level of professional reference for the game developer, we created the Morgan Kaufmann Series in Interactive 3D Technology. Books in the series are written for developers by leading industry professionals and academic researchers, and cover the state of the art in real-time 3D. The series emphasizes practical, working solutions and solid software-engineering principles. The goal is for the developer to be able to implement real systems from the fundamental ideas, whether it be for games or other applications. Real-Time Collision Detection Christer Ericson 3D Game Engine Architecture: Engineering Real-Time Applications with Wild Magic David H. Eberly Physically Based Rendering: From Theory to Implementation Matt Pharr and Greg Humphreys Essential Mathematics for Game and Interactive Applications: A Programmer’s Guide James M. Van Verth and Lars M. Bishop Game Physics David H. Eberly Collision Detection in Interactive 3D Environments Gino van den Bergen 3D Game Engine Design: A Practical Approach to Real-Time Computer Graphics David H. Eberly Forthcoming Artiﬁcial Intelligence for Computer Games Ian Millington Visualizing Quaternions Andrew J. Hanson Better Video Game Characters by Design: Using Psychology to Make Better Games Katherine Isbister

Real-Time Collision Detection Christer Ericson Sony Computer Entertainment America AMSTERDAM • BOSTON • HEIDELBERG • LONDON NEW YORK • OXFORD • PARIS • SAN DIEGO SAN FRANCISCO • SINGAPORE • SYDNEY • TOKYO Morgan Kaufmann Publishers is an imprint of Elsevier

Senior Editor Publishing Services Manager Senior Project Manager Assistant Editor Cover Design Cover Image Text Design Composition Technical Illustration Copyeditor Proofreader Indexer Interior Printer Cover Printer Tim Cox Simon Crump Angela Dooley Richard Camp Chen Design Associates CEPHA Dartmouth Publishing, Inc. Betty Pessagno Phyllis Coyne et al. Northwind Editorial The Maple-Vail Book Manufacturing Group Phoenix Color, Inc. 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. © 2005 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 transmitted in any form or by any means—electronic, mechanical, photocopying, scanning, or otherwise—without prior written permission of the publisher. Permissions may be sought directly from Elsevier’s Science & Technology Rights Department in Oxford, UK: phone: (+44) 1865 843830, fax: (+44) 1865 853333, e-mail: permissions@elsevier. com.uk.You may also complete your request on-line via the Elsevier homepage (http://elsevier.com) by selecting “Customer Support”and then “Obtaining Permissions.” Library of Congress Cataloging-in-Publication Data Application submitted ISBN: 1-55860-732-3 For information on all Morgan Kaufmann publications, visit our Web site at www.mkp.com Printed in the United States of America 08 07 06 05 04 5 4 3 2 1

To mom

分享到：

赞收藏

资料库

real Time Collision Detection.pdf

相关推荐

游戏开发

热门标签

最新资料