Reddit reviews Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology)
We found 24 Reddit comments about Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology). Here are the top ones, ranked by their Reddit score.
Used Book in Good Condition
Check out the book Real Time Collision Detection. It's fairly old, but the material is still very relevant.
"Because any one object can potentially collide with any other object, a simulation with n objects requires (n−1)+(n−2)+...+1 = n(n−1)/2 = O( n^2 ) pairwise tests, worst case. Due to the quadratic time complexity, naively testing every object pair for collision quickly becomes too expensive even for moderate values of n. Reducing the cost associated with the pairwise test will only linearly affect runtime. To really speed up the process, the number of pairs tested must be reduced. This reduction is performed by separating the collision handling of multiple objects into two phases: the broad phase and the narrow phase. The broad phase identifies smaller groups of objects that may be colliding and quickly excludes those that definitely are not. The narrow phase constitutes the pairwise tests within subgroups."
Ericson, Christer. Real-Time Collision Detection (Page 14). Taylor and Francis CRC ebook account. Kindle Edition.
I know a good bit about this... engine programming specifically.
I have a physics degree and a standing offer to work at Naughty Dog. A good friend of mine from undergrad also has a physics degree, and is an engine developer at Naughty Dog. He is currently rewriting the companion AI for The Last of Us 2. And because it is only 7pm on a Saturday, I do mean currently. He is cited in the definitive text Game Engine Architecture. We talk often, and he even comes to me for help with especially tricky problems. I also have a copy of the 100+ pages of notes he used to study for the Naughty Dog interview... PM me your email for a copy.
This is what I suggest:
Step 1: Read Game Engine Architecture.
Step 2: Read Game Engine Architecture again, but slower this time.
Step 3: Learn 3D math. (There are other resources too, but one way or another you should know literally all the content in that book, because you will be asked 3d math questions during the interview, and if you're not you should keep interviewing.)
Learn how your computer works, from the ground up. Learn how to write extremely performant C++. This includes bitbashing, SIMD, caches, concurrency, etc. Not theory; real world experience. Learn how the GPU works. Learn computer graphics. Learn computer graphics for real. Learn collision detection.
Make a large number of small demos quickly. Decreasing development time is extremely important in the games industry. Make A*, a raytracer, a fibers threading engine, a shadow mapper, a FSM engine, etc.
Here is a recent question my friend asked me (as a brain teaser; he had already solved it):
> quickly check whether a
uint64_t x
is equal to any of 16 unique otheruint64_t
s>
bool f(uint64_t x, uint64_t a[16]);
> it will be called with the same
a[16]
every time, but varyingx
Hint: you expect >99% of calls to this function to return
false
. Post your answer and I'll tell you what's wrong with it. The obvious solution is incorrect. Same is true for anyone else, by the way.He recently came to me with a different problem: using all the time and compute in the world, encode a unit quaternion into 32 bits such that decode on the GPU is extremely fast, and minimize the max error possible. We managed to improve on the state of the art in both respects. No hints here, but I know some people you should talk to if you can show me a better solution. :)
Study games. Play games. Critique games. Love and breathe games. Because that industry will eat you up and chew you out, so you better be prepared to love every single second of crunch time. If you love it, you can do it, but it will torture you if you don't.
It is hard, but if you love it, and not just the idea of it, you can do it. However, as you can probably guess by my breakdown engine developers tend to be very experienced. My friend is an extreme anomaly at being as young as he is and an engine developer. It is more the type of thing you start trying to interview for with ~decade of experience.
Seconded, Game Engine Architecture is the best book for an overall view on engine development. I've also found these books useful for implementing engine subsystems:
Actually, it's a bit of both.
Problems / Criticism of GoF
1. The GoF was written in the era of "OOP is a silver bullet" and single-threaded programs by academics who were generally clueless about the importance of understanding data transforms, data caches, instruction caches, and minimizing cache misses. See: Pitfalls of Object Oriented Programming of how you get massive speedups just by understanding cache usage and re-arranging the data.
2. One of the problem with the GoF methodology is when people turn it into a religion. People start trying to apply design patterns to everything even when it isn't needed and you end up with this over-engineered, bloated, slow, clusterfuck of code.
3. Programmers who focus on performance have also been pretty vocal about "cargo cult programming" and design patterns:
> The “Design Patterns” book is one of the worst programming books ever. Yes, really. I’m 100% dead serious when I say that I think it has set (and will continue to set) the progress of software development back by decades. Why?! Let me offer up a parable; I will call it “The Plank.”
> "Design patterns are spoonfed material for brainless programmers incapable of independent thought, who will be resolved to producing code as mediocre as the design patterns they use to create it with."
4. While abstraction can be a nice way to solve a problem there are ALWAYS trade-offs. The flexibility of abstraction is that you generally tend to lose efficiency. Blinding applying a design pattern means you aren't thinking about the performance issues. In today's age of multi-core software this is a huge disadvantage compared to your competitors.
And while Ericson and Acton tend to throw the baby out with the bathwater they are speaking from years of experience of writing fast, simple code. This ISN'T an appeal to authority as they aren't just some armchair academics -- they have demonstrated they have understand HOW to write FAST code. Their experience also matches what I've seen.
5. Another problem is that changing the hardware changes the problem. GoF doesn't take this into account.
6. Very rarely does OOP "perfectly" model the problem. GoF ignores this.
7. Another part of the problem is that OOP is NOT scalable. OOP has a design fallacy that "one is the common case." This is almost never the case. The common case is usually you have multiple objects. Again GoF ignores for the most part. They take a stab at it with the
Flyweight Design Pattern
but that isn't scale when you REALLY do have many, mutable objects such as the particles of a particle system.And while I am not as adamant as Ericson or Acton about being "anti-design-patterns" they DO have a point -- not understanding the strengths AND weaknesses of an algorithm makes for a poor programmer IMHO. Remember, there are THREE ways to optimize:
O(n)
algorithmGo ahead and use design patterns for your tools. But for engine/games DoD will usually solve the problem simple and faster then misapplying and blindly applying a design pattern.
Solution
Lastly the problem of complexity was summarized by Fred Brooks in The Mythical Man-Month
> "Show me your flowcharts (source code), and conceal your tables (domain model), and I shall continue to be mystified;
> show me your tables (domain model) and I won't usually need your flowcharts (source code): they'll be obvious."
A more modern colloquialism would read:
> Show me your code and I'll have to see your data,
> Show me your data and I won't have to see your code.
The secret to high performance is NOT the algorithm but to focuse on HOW the data is transformed. i.e. The first rule of optimization is:
Know Thy Data
I highly recommend Real-Time Collision Detection.
This next book might not apply to your field directly, but I believe it is a good idea to be at the very least aware of what it discusses, and it is a very excellent book on its subject: The Art of Game Design: A Book of Lenses
I recommend this book as more of a reference than a tutorial; it will allow you to quickly brush up on those areas of math and physics which you will need while writing (or perhaps working with) a physics engine. I don't recommend attempting to learn the subjects through this book alone though. Game Physics
Reading 3D Math primer for Graphics and Game Development is how I learned linear algebra, although I plan on studying the subject from a textbook when I get the opportunity. I keep the book close for easy reference of the math related to 3D rendering (such as the projection and view matrices), although if you get this book you will want to read the errata document on its website. There may be better books to teach this stuff now, so please don't jump on it too hastily.
A couple books I do not own, but plan to correct that as soon as I can:
Game Physics Pearls and Real-Time Shadows
If I think of any others, I will edit this comment.
I few game dev friends of mine like to wax poetic about this book:
http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323/
Also, cannot recommend Real Time Collision Detection enough.
May I recommend to the OP and everyone else interested in but inexperienced with game physics engines, get this book and read it front to back: http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323
The bible of collision detection is Real Time Collision Detection if you ask me. Helped me a lot whenever I need to look something up regarding collisions
I bought the book after I figured the internet was impossible to get any answers on
Well.. Given that most every 3d game has some sort of physics and stuff isn't supposed to go through each other...
This maybe could be considered covering counter-strike... But then you need real time networking as well...
https://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323
This is the best beginning resource along with http://www.amazon.com/gp/aw/d/1558607323 but as stephanimal said, my basic Newtonian knowledge comprised maybe 20 lines of code in my first physics engine, and about 100 if rotation was considered, but I don't remember if I learned to solve for inertia tensors in my first physics course or not. Good luck and if you need help PM me!
For OpenGL stuff, check out Anton Gerdelan's tutorials and open.gl.
For some general game design books, I may recommend:
If you want to know specifically about Doom, then you want to read this and this
For collision detection in general, Real Time Collision Detection really is a great book and covers all of the data structures I mentioned. (Note about the upcoming 2nd edition)
https://www.gamedev.net/forums/forum/7-math-and-physics/ should have accumulated some good information over the years.
Personally, I focus on dense grids for constrained situations and AABB-trees for general solutions.
For example, a 2D game with a reasonable max level size can be handled easily with a dense grid. Just pick a bucket (grid square) size and make a big ole 2D array of linked lists pointers to collision nodes that touch each grid square. That sounds like a lot of memory. But, if you do the math, it's not much on modern machines. Linked lists are bad for cache, but you can make that better by having each node store 7 pointers to collisions + 1 pointer to the next node. At 8 bytes each, 8 pointers is 64 bytes which is 1 cache line. Don't malloc the nodes individually. Pre-alloc an array of them and keep the free nodes in a linked list using the node.next attribute.
For more flexible situations, having a hierarchy of axis-aligned bounding boxes tends to work as well as any other solution. By stuffing 4 or 8 boxes in each tree node you not only gain efficient use of cache lines, you also have the opportunity to arrange the data to make SSE SIMD intrinsics work out.
A fun trick is to separate static vs dynamic objects into their own trees, but then hook them back to together at the top. So, you can pre-bake a slow, carefully balanced tree for the static geo. But, leave one free slot in the top-most node of that tree. During the game, maintaining a dynamic tree is hard, so make compromises for update speed in the dynamic tree. But, once you have the dynamic tree, you can point the static tree's spare pointer at the dynamic tree and BAM, one unified tree!
You can also do stuff like this where you pre-calc a good BVH for each object individually, then insert those small, static trees into an overarching dynamic tree as the objects move around.
The first tutorial series i linked is about ridge body physics. The last one goes into some of the formula affecting them: link
No idea about a book on water sim but for collision detection there is this book. Its well written. I've been reading through parts of it.
I just found this video of a college lecture on how rigid bodies work. link
A book called Real Time Collision Detection is well respected
https://www.amazon.ca/Real-Time-Collision-Detection-Christer-Ericson/dp/1558607323
I wrote a blog post here too
http://www.00jknight.com/blog/unity-character-controller
Game Engine Architecture provides an excellent overview of how game engines work, from the ground up, in a way that's fairly accessible—that is, I understood most of what I was reading despite not having any experience programming at that level.
Also good:
Real Time Rendering
Real Time Collision Detection
Real-time collision detection by Christer Ericson (https://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323) is pretty much the "go to reference", even for those of us who have written a fair bit of collision detection code.
It's pretty expensive in hardback form, but it's well worth the investment.
Real Time Collision Detection is the bible for all your 3D game math needs.
THE book.
Real-Time Collision Detection
http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323
It has 3D stuff in it to, but 2D as well. You can get more stuff obviously, but you need this one.
You need to do some kind of spatial partitioning, to escape quadratic complexity of exhaustive pairwise testing. Real-Time Collision Detection by Christer Ericson covers the topic pretty well.
YouTube for anything drawing. OpenGL can be applied to any other library and tutorials are everywhere.
This book for the basics of everything else.
Fair warning: 3D math and physics are hard. You won’t be bouncing a ball anytime soon.
https://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323
Anyone interested in collision detection should probably purchase this book at some point.
As general advice:
2.a. Feel free to experiment with different languages/APIs/etc., but try and stay at least somewhat focused
But above all, have fun! Make sure you balance learning more advanced things with just playing around with pet projects - that way you get a good balance of theoretical knowledge with practical experience. =]
Hi,
You've chosen a pretty interesting and intricate topic for your thesis - good decision getting started early! :-)
You've probably already stumbled upon this, but Unity uses Collider components for collision detection and Rigidbody components to generate a physical response to a collision. The Unity manual on Colliders is probably a good place to start.
Beyond Unity, our studio frequently references this book for the majority of our collision detection needs. Collision detection and response is a fairly broad topic and I imagine you'll uncover a lot over the next two years. Best of luck to you. :-)