Reddit 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.

Arts & Photography
Books
Other Art Media
Digital Art
Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology)
Used Book in Good Condition
Check price on Amazon

24 Reddit comments about Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology):

u/LithiumToast · 45 pointsr/gamedev

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.

u/csp256 · 21 pointsr/cscareerquestions

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 other uint64_ts

> bool f(uint64_t x, uint64_t a[16]);

> it will be called with the same a[16] every time, but varying x

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.

u/Jephir · 10 pointsr/gamedev

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:

u/mysticreddit · 9 pointsr/gamedev

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:

  • Christer Ericson who wrote the phenomenal Real Time Collisision Detection had this to say about 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.”

  • Mike Acton, the father of "Data Orientated Design" also agrees when he quoted Eric at a C++ convention:

    > "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:

  • Micro-optimizations, aka Bit Twiddling Hacks
  • Algorithms -- using a better O(n) algorithm
  • Macro-optimization, aka Data-Orientated Design -- minimizing cache misses.

    Go 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

u/InvisibleMan5 · 9 pointsr/gamedev

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.

u/petajc · 7 pointsr/gamedev

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/

u/DOOMReboot · 6 pointsr/gamedev

Also, cannot recommend Real Time Collision Detection enough.

u/esdin · 5 pointsr/gamedev

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

u/TheCanadianVending · 5 pointsr/gamedev

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

u/BrFrancis · 4 pointsr/IllegalLifeProTips

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

u/tough_guy · 3 pointsr/gamedev

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!

u/corysama · 3 pointsr/gamedev

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.

u/phantomfromnowhere · 3 pointsr/gamedev

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

u/00jknight · 3 pointsr/gamedev

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

u/DragoonDM · 3 pointsr/cscareerquestions

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

u/intheweehours · 3 pointsr/Cplusplus

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.

u/specialpatrol · 2 pointsr/gamedev

Real Time Collision Detection is the bible for all your 3D game math needs.

u/growingconcern · 2 pointsr/gamedev

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.

u/eternal-potato · 2 pointsr/rational

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.

u/STREGAsGate · 1 pointr/gamedev

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

u/montibbalt · 1 pointr/todayilearned

Anyone interested in collision detection should probably purchase this book at some point.

u/[deleted] · 1 pointr/gamedev

As general advice:

  1. Get the fundamentals of programming down
  2. Start making basic 2D games, and progressively get more advanced. Look at arcade games by era for that purpose if you need game ideas. Start with Pong, then go from there.
    2.a. Feel free to experiment with different languages/APIs/etc., but try and stay at least somewhat focused
  3. After spending plenty of time at #2, start playing with 3D. You can either learn by coding the logic of 3D from scratch (e.g. in ActionScript following along with the end of http://www.amazon.com/Foundation-Actionscript-3-0-Animation-Making/dp/1590597915 ), using a graphics API (e.g. DirectX, OpenGL), or using a game engine (e.g. UDK, Unity, etc.). The hurdle from 2D to 3D is big, and it can be really confusing. If you're having trouble wrapping your head around the math, try http://www.amazon.com/Essential-Mathematics-Games-Interactive-Applications/dp/155860863X and http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323

    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. =]
u/auzden · 1 pointr/Unity3D

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. :-)