Written by an expert in the game industry, Christer Ericson’s new book is a comprehensive guide to the components of efficient real-time collision detection systems. The book provides the tools and know-how needed to implement industrial-strength collision detection for the highly detailed dynamic environments of applications such as 3D games, virtual reality applications, and physical simulators.

Of the many topics covered, a key focus is on spatial and object partitioning through a wide variety of grids, trees, and sorting methods. The author also presents a large collection of intersection and distance tests for both simple and complex geometric shapes. Sections on vector and matrix algebra provide the background for advanced topics such as Voronoi regions, Minkowski sums, and linear and quadratic programming.

Of utmost importance to programmers but rarely discussed in this much detail in other books are the chapters covering numerical and geometric robustness, both essential topics for collision detection systems. Also unique are the chapters discussing how graphics hardware can assist in collision detection computations and on advanced optimization for modern computer architectures. All in all, this comprehensive book will become the industry standard for years to come.

*Presents algorithms and data structures with wide applications to the fields of game development, virtual reality, physically based simulation, CAD/CAM, architectural and scientific visualization, molecular modeling, engineering simulation, GIS, ray tracing, and more.
*Describes tested, real-world methods, liberally illustrated by C & C++ code.
*Reviews necessary concepts from mathematics and computational geometry, and includes extensive references to other sources and research literature.

Book that every game programmer should read.

Book that every game programmer should read - it’s that simple. While it does focus on collision detection, this subject is so broad it touches multiple other vital areas like linear algebra, spatial partitioning, ray tracing, bounding volumes and more. It’s not just a list of equations and algorithms, rather a practical guide on how to implement them in an optimal way. More "general" chapters on numerical robustness and optimizations are pure gold.

The best resource on collision detection that I have encountered

This is an extremely well written text. The examples are clear, and it manages to cover a lot of ground. In my opinion, this book is far better than many of the other collision detection and game-development texts.

Nowhere else will you find as good a reference on shape intersection tests and closest point computations. Ericson covers these topics swiftly and efficiently within the early sections, a task which often occupies the entirety of many lesser books. The coverage of the Gilbert-Johnson-Keerthi algorithm is likewise top-notch.

My main gripe with the book is the chapter on GPU optimization. Its placement didn’t seem very logical, and the techniques it contains are quite out of date as of 2007. Fortunately, the rest of the book is so good that it can be easily forgiven.

Overall: Highly recommended.

Excellent explanations of collision detection algorithms and their optimization

The first half of this book explains the most popular collision detection functions. The collisions presented are mostly in 3D, but there are also some 2D versions. You can use Amazon’s "Search Inside" option and take a look at the content table, which shows a large variety of shape vs shape tests. Most of the functions are explained using advanced math, and that’s ok because there is no other way to show were the concepts of the book come from. There is an introductory chapter on the math used in the book, but it isn’t enough. In my opinion it would have been better to remove that chapter and add some more explanations and algorithms on dynamic collisions.

Most of the second half of the book deals with the different structures to optimize collision detection queries, showing pros and cons for all of them, so the developer can select the one that best fits it’s project. The last part of the book is on hardware optimizations.

I agree with other reviewers the CD doesn’t bring enough code, and no executable code at all. What one finds in the CD are the pieces of code exactly as they are printed in the sheets, sorted in files by chapter. In my opinion that presentation makes the author look like he is just adapting the algorithms from other papers. Having runnable code is not just a fancy feature, but a necessity for programmers. With compilable code one can see how it works, getting a better idea of how the algorithms are integrated in the actual graphical engine, and it’s also a proof the code has no bugs (otherwise reveals them). I’m removing 1 star only because of this reason, hoping a new edition will enhance the content.

This book saves a lot of research, time and money. Just compare this table of collision tests: http://www.realtimerendering.com/int/ with the book’s content. You will see that many of these tests are explained and included in the book (and there are some more not in that table). This book is a great compilation of those algorithms which are pretty dispersed in papers and books.

worth every dollar

Two things stand out about this author: 1) he drives every discussion toward performance issues, and 2) he provides just enough source code for a developer like me to lock in the concepts. That’s a great combo that makes this book a hands-down winner.

I’ve never worked in gaming. I’ve been doing CAD/CAE/CAM, mostly with Java and CATIA v4 / STEP data, for ten years. I’m currently involved in a robotics planning project, where I’ve been able to model all the kinematics of an 8-DOF robot system, but the scale of the collision detection challenges has overwhelmed me...until reading this book.

worth every dollar

Two things stand out about this author_ 1) he drives every discussion toward performance issues, and 2) he provides just enough source code for a developer like me to lock in the concepts. That’s a great combo that makes this book a hands-down winner.

I’ve never worked in gaming. I’ve been doing CAD/CAE/CAM, mostly with Java and CATIA v4 / STEP data, for ten years. I’m currently involved in a robotics planning project, where I’ve been able to model all the kinematics of an 8-DOF robot system, but the scale of the collision detection challenges has overwhelmed me...until reading this book.

Best collision book i’ve seen so far

I’ve read MANY collision detection books over the years and this is by far the best one i’ve seen to teach programmers how to LEARN collision detection from basic tests to highly advanced algorithms.

A comprehensive reference and tutorial on game geometry

This book does more than collision.



Don’t get me wrong -- it does all of the collision you’ll likely need in any kind of current game, in good detail, with derivation of why it works, including source code. However, it also serves as an excellent primer in game geometry for anyone who might not have an intuitive understanding of what a closed manifold mesh is, or why the separating axis theorem works, or why T junctions are a problem.



I’m pretty well versed in the field, and I use this book as a comprehensive reference, and I love it. But even if you’re a newcomer, you need this book, because it contains everything you need to know! And, conversely, if you don’t know what’s in this book, you won’t have the success you want.

A comprehensive reference and tutorial on game geometry

This book does more than collision.

Don’t get me wrong -- it does all of the collision you’ll likely need in any kind of current game, in good detail, with derivation of why it works, including source code. However, it also serves as an excellent primer in game geometry for anyone who might not have an intuitive understanding of what a closed manifold mesh is, or why the separating axis theorem works, or why T junctions are a problem.

I’m pretty well versed in the field, and I use this book as a comprehensive reference, and I love it. But even if you’re a newcomer, you need this book, because it contains everything you need to know! And, conversely, if you don’t know what’s in this book, you won’t have the success you want.

Best of its class

For such difficult topics, this book is surprisingly readable, accessible, and has plenty of source code to get you started. It also has one of the best sections I have ever seen about floating point accuracy and numerical stability. In addition, it has some of the best coverage of BSP trees, KDE trees, and other spatial organization. That alone makes it worth the price of the book.

Also, the book has a great bibliography that directs you to more advanced papers should you need something specialized. And finally, you do not have to be a genius to work through the algorithms. Anyone with a basic knowledge of vector algebra and a little linear algebra can work through the algorithms, if you are diligent and persistent. As a professional 3D programmer new to my field, I find it a great plus whenever I come across a resource that can save time in such an in-depth field.

The essential guide to interactive collision detection

Solid theory coupled with the author’s own practical experience makes this book an excellent choice for practitioners in the field. In addition to describing a wide range of relevant algorithms, the author also discusses optimization, numerical precision, robustness, and other topics critical in creating a workable interactive system.

As far as code goes, (a) there are a lot of libraries out there already (see the "Real-Time Rendering" site for links), and (b) it’s probably better to write your own if you’re poor, and thereby know its strengths and weaknesses, or license Havok’s if you’re rich. This is the book that will help you write your own. I love Schneider and Eberly’s "Geometric Tools", but this book is more focused and more readable.

surprising amount of depth in this field

The physics in the book is simple. Elementary kinematics. Something often taught at the first year undergraduate level. But the book goes far further into its specialised need than you are likely to see in a physics text. Many computer games that rely on real time feedback need fast ways to see if two or three dimensional objects collide. Because then, some involved interaction must occur.

In essence, the book deals with simulations of moving bodies, where you time step Newton’s equations. Much of the book becomes an excursion into linear algebra, as we seek to find if various geometric objects intersect. There are important special cases, like when a moving sphere hits another sphere.

The numerical computations, or, more specifically, the efficiency with which they can be found, is also important and discussed.

Many other topics are also studied. There is a surprising amount of depth in this field.

A Vectorized Approach

This book has great depth and breadth. It covers narrow phase, broad phase, and optimization. It has more coverage of broad phase and optimization than I have seen in any other book. Also, the bibliography is quite extensive, with many entries containing links to pdf files.

What I really appreciate about this book is the vectorized approach. Many algorithms are derived and implemented in a vectorized form. This not only improves readability, but also makes them efficient for modern SIMD architectures.

I have found this book to be invaluable in my day to day work. I highly recommend this book.

Not Just for Game Programmers!

Let me state in the most emphatic terms--this book contains the very best discussion on spatial indexing and querying ever written. If you have an algorithm which is spending too much time querying in quad trees, then you need to buy this book and read it until you become one with it.

It should be pointed out that this book will be useful not just for game programmers but also for other programmers who do a lot of computational geometry. EDA programmers, VLSI, CAD programmers, etc, rejoice.

I disagree with a previous reviewer who is complaining about lack of source code, etc. The author provides good C++ implementations of his algorithms and provides very clear descriptions of them. The author is holding up his end of the bargan--if you arn’t a computational Jedi knight of space and time after reading this book, the fault isn’t in the efforts of the author, its in the efforts of the reader.

Don’t worry about how expensive the book is. I’ve used it on the job and it has already paid for itself many times over.

Coulda Been a Contenda

On the whole I would agree with Mr. Waits and his review. The book is quite thorough - maybe the most thorough book aside from Eberly’s "Geometric Tools for Computer Graphics" and, ironically, the very reason I am only giving this book 3 stars may be its biggest advantage over the previously mentioned book - source code.
There is source code included (unlike Eberly’s 50lb tome), mind you, in the form of a 56K zip file on a CD. That’s it...nothing else - a single 56K zip file on a 700MB CD that has source code excerpted in a plain text file, sorted by chapter. Looks like it was created as an afterthought using a perl script in the 11th hour.
As much as I truly enjoy the content of this book, there really needs to be more thought and care put into the release of source code for books such as these. Given that I plunked down $70 for this beast, I would only hope that I could be given the source organized into a) a reasonably well constructed collision detection class framework, or b) organized C files with some test harnesses thrown in for good measure.
Having said all that, if you don’t share the same passion for proper source code packaging that I do and only want a great reference on CD, well, this is your book.

The only book you’ll need on the topic..

Christer has done an amazing job of completely covering a large topic. Anyone writing collision detection systems for games (or other real-time apps) needn’t look any further than this book.

It’s also full of things even non CD System writers will find handy, such as optimal intersection tests (Chapter 5)

And, in the end (Chapter 13), he includes a number of great optimization techniques.

Overall, this is great as both educational and reference. It’s got a permanent spot on my bookshelf.

Highly recommended!