Real-Time Collision Detection
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.
Stats for nerds
23recommend
38mentions
27people
2011–2025years
87% recommend13% neutral
Mentions per year
What Hacker News says
- For geometry, start with high-school algebra and coordinate geometry, and learn how to put the two together: equations representing geometry. By which I mean, being able to write down equations for geometric objects and manipulate the equations to get them into different useful forms, and to compute useful things. A first example would be studying different ways of writing down equations for the line [1], and then learn how each of the forms relate, how to use algebra to move between them, and what each for is useful for. For example finding the intersection of two lines involves simultaneously solving for (x,y) that satisfy both equations, and there's a particular form that is best suited to that. Another form is better if you want to "move along a line" say, parameterised by time. One form might be best for GPU rendering. Once you're comfortable with algebraic expressions for lines, then you can move on to the more complex curves that you listed -- the equations for these curves can be manipulated in analogous ways. EDIT: importantly you want to learn not how to "plug and chug" numbers, but instead how to use these equations in code: e.g. how would you use the equations to write code to draw a line/curve, and how to derive functions to intersect curves, connect curves at tangents, etc.
There's more to it than that of course. For example working out equations for tangents to curves will become important. But start with the above. You mention de casteljau algorithm, I am not familiar with that, but it looks like it might be heading more into algebra, in particular manipulating polynomials, which you learn to write down in high-school, study more in pre-calculus and calculus, but can get pretty complicated, for example if you want to solve a quintic equation.
Two elementary books:
McDougal, Little, "Geometry for Enjoyment and Challenge"
Joseph H. Kindle, "Theory and Problems of Plane and Solid Analytic Geometry (Shaum's outline)"
The following are approachable, but don't directly address your interest in curves:
Joseph O'Rourke, "Computational Geometry in C," second edition (basics everyone should know, starts with primitives like knowing the best way to compute the intersection of two line segments.
Christer Ericson, "Real-time collision detection" (a bit more specific, but a fantastic book, recommended to me here on HN in the past)
And of course I must reference Inigo Quilez' [2] "SDF of a ..." videos which give an illuminating perspective on using equations to describe geometry[3].
[1] https://math.libretexts.org/Bookshelves/Applied_Mathematics/...
[3] SDF of a Line https://www.youtube.com/watch?v=PMltMdi1Wzg
EDIT: some of the IRC servers have #math channels, and some of those are open to drop ins asking questions like yours (others seem to be full of people studying for exams).
- I also struggled to find the answer online. I found it in only 2 books.
Chapter 12 of Real-Time Collision Detection has a section on vertex welding.
The 1st edition of 3D Math Primer has it in Chapter 14.4.2: Vertex Welding.
If you want to merge vertices that are within WELD_EPSILON then you can create a 3D grid of cells with cell sizes being at least as large as 2*WELD_EPSILON and put each vertex in its cell. For each cell, you only need to check the 8 neighboring cells to see if the vertex should be merged with a nearby vertex.
The worst case could be worse than O(N) if most of the vertices end up in the same grid cell but don't require merging.
- One of my favorite books is Real-Time Collision Detection[1] which covers this and other adjacent topics(like cache line aware data structures!). I generally refer to it as "data structures for 2D/3D" and I think only the Art of Electronics has more value on a page-by-page basis for the domains I've enjoyed.
- Even logic with line intersection has to be careful! I wrote some code to use line intersection tests for 2D platforming. Turns out "find a line this line collides with, move to that point, and repeat" is easy to mess up due to FP precision.
I second Real Time Collision Detection. I used its section on line segment intersection to get my code working.
- real time collision detection is a good book on those fundamentals with real world considerations.
- Going more in the computational geometry direction, in addition to some interesting algorithms in the Graphics Gems series:
O'Rourke, "Computational Geometry in C 2e". Deals with the basics in a principled way. Start here for fundamentals like a good algorithm for intersection of two lines, or inside/outside polygon tests (don't depend on garbage blog posts for well studied fundamentals like this). The book's webpage is https://www.science.smith.edu/~jorourke/books/compgeom.html
Ericson, "Real-Time Collision Detection". Deep dive into practical collision detection algorithms.
And for Shaders, check out Inigo Quilez and ShaderToy:
- https://www.youtube.com/@InigoQuilez
You should be able to get your hands dirty pretty quickly implementing cool things on ShaderToy.
Related
Real-time rendering
34 recommend · 54
Boundary Representation Modelling Techniques
2 recommend · 3
Optimal state estimation
2 recommend · 2
Game engine architecture
35 recommend · 55
Flow-based programming
5 recommend · 14
Mastering algorithms with C
3 recommend · 9
