Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology)

Category: Programming
Author: Christer Ericson
4.3
All Stack Overflow 18
This Year Stack Overflow 2
This Month Stack Overflow 3

Comments

by corysama   2019-07-21

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.

by DOOMReboot   2019-07-21

Also, cannot recommend Real Time Collision Detection enough.

by anonymous   2019-07-21

I think this book is best for you...

http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323

by anonymous   2019-07-21

You will need some system that checks for and manages collisions, if you want to insist on using the glut objects then you will need to contain them in some other class/geometry-representation to check for intersections.

Some interesting reads/links on physics/collision detection:

www.realtimerendering.com/intersections.html

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/ < he also has other articles, the principles for 2D can easily be extend to 3 dimensions

http://www.dtecta.com/files/GDC2012_vandenBergen_Gino_Physics_Tut.pdf

Edit, this book is good imo: http://www.amazon.co.uk/gp/product/1558607323/ref=wms_ohs_product

by anonymous   2019-07-21

As far as I can see there are two things wrong with your collision detection. The first is that you're testing (leftX < rightX && topY < bottomY) when you should be testing (leftX <= rightX && topY <= bottomY). If you fix this your code will work in most situations.

The second problem you've got, which may not become apparent straight away, is that your are performing collision detection for discreet points in time. If your player has a large enough velocity vector you may end up with this situation:

  • Update 1: Player is in front of wall travelling towards it. AABB test shows no collision.
  • Update 2: Player is behind wall travelling away from it. AABB test shows no collision.

Your AABB test is correct and yet the player has passed through the wall. The naive approach to fixing this is to test more often (update 1.5 may have shown a collision), or to limit player velocity. Both approaches will require a lot of fine tuning especially if you're dealing with objects that can move at different speeds and walls with differing thickness.

A more robust approach is to take account of velocity in your test. Since you know the velocity of your AABB you can project this shape along its velocity vector. If you do this for both AABBs you'll end up with two elongated shapes which you can test against each other. If they overlap then you know that their paths cross and that there may be a collision.

enter image description here

Of course, knowing that there might be a collision is not hugely helpful. The problem is one AABB may be moving very slowly and the other very quickly so even though they both pass through the same space (their elongated shapes intersect) they don't pass through it at the same time.

Figuring out whether they both pass through the same space at the same time is hard, so instead we cheat. If you subtract the velocity of B from the velocity of A and then use this modified velocity to project the elongated shape of A, you can effectively treat B as a stationary object and still get the correct result. Knowing this, your test is now "does B overlap the elongated shape of A?". This is just a simple AABB vs Ngon problem.

While the above will give you a boolean as to whether two moving AABBs collide it will not tell you when they collide which is also useful for calculating things like rebounds.

I would very much recommend the book Real Time Collision Detection by Christer Ericson which is pretty much the go to book on collision detection for any aspiring game developer.

The following is a code snippet from the CD-ROM which accompanies the book. It tests a moving AABB against another moving AABB and also provides a time of first contact.

// Intersect AABBs ‘a’ and ‘b’ moving with constant velocities va and vb.
// On intersection, return time of first and last contact in tfirst and tlast
int IntersectMovingAABBAABB(AABB a, AABB b, Vector va, Vector vb, float &tfirst, float &tlast)
{
    // Exit early if ‘a’ and ‘b’ initially overlapping
    if (TestAABBAABB(a, b)) {
        tfirst = tlast = 0.0f;
        return 1;
    }

    // Use relative velocity; effectively treating ’a’ as stationary
    Vector v = vb - va;

    // Initialize times of first and last contact
    tfirst = 0.0f;
    tlast = 1.0f;

    // For each axis, determine times of first and last contact, if any
    for (int i = 0; i < 3; i++) {
        if (v[i] < 0.0f) {
            if (b.max[i] < a.min[i]) return 0;
            // Nonintersecting and moving apart
            if (a.max[i] < b.min[i]) tfirst = Max((a.max[i] - b.min[i]) / v[i], tfirst);
            if (b.max[i] > a.min[i]) tlast = Min((a.min[i] - b.max[i]) / v[i], tlast);
        }

        if (v[i] > 0.0f) {
            if (b.min[i] > a.max[i]) return 0;
            // Nonintersecting and moving apart
            if (b.max[i] < a.min[i]) tfirst = Max((a.min[i] - b.max[i]) / v[i], tfirst);
            if (a.max[i] > b.min[i]) tlast = Min((a.max[i] - b.min[i]) / v[i], tlast);
        }

        // No overlap possible if time of first contact occurs after time of last contact
        if (tfirst > tlast) return 0;
    }
    return 1;
}

The following attribution is required by Elsevier's Software License Agreement:

“from Real-Time Collision Detection by Christer Ericson, published by Morgan Kaufmann Publishers, © 2005 Elsevier Inc”

by Impossible   2019-07-12
Real-time collision detection (Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology) https://www.amazon.com/dp/1558607323/ref=cm_sw_r_cp_apa_i_bR...) also deserves a spot on this list.
by anonymous   2019-01-13

In order to implement more or less realistic bouncing it is not enough to have only positions and bounding boxes of colliding objects. You need to have some kind of kinematic history: to be able to tell how objects move after collision you should also know how they were moving before the collision.

In simplest case, you want to have at least a velocity (speed) vector (direction and magnitude) and, probably, a mass for every object. When collision is detected you may simply invert the direction of the velocity vector of one of the objects (for example, smaller and lighter one).

The pseudocode will be something like:

if have_collided(object1, object2):
   if object1.mass > object2.mass:
      object2.velocity = -object2.velocity
   else:
      object1.velocity = -object1.velocity

This would not look very realistic, but is very simple to implement. For more realism you could use momentum conservation principle or elastic collisions. For even more realistic bouncing, implement acceleration vector and re-calculate both, velocity and acceleration after collision is detected. Having acceleration you may now add arbitrary forces influencing your objects (gravity, friction, maybe even electromagnetic forces etc.). Adding more attributes make it more interesting: for example adding elasticity and viscosity may be used to calculate deformations.

As you see there is more in object interactions involved than just positions.

Additionally, collision detection and bouncing code could (and should) be decoupled. That means that you would want to implement them in different parts of code (different set of functions and classes): collision subsystem will detect the collision event, providing information like: whether collision happened or not and if yes, by how far objects currently intersect with each other. After that, bouncing code, based on this information, will decide how to change objects traveling, while deformation code will decide how to change objects shapes etc. Thus, there will be no silly problems like which "if" statement in collision code came first decides the direction of bouncing.

Overall I would suggest you:

  • To look up some physics. For example:

    • Wiki: Inelastic collision
    • Wiki: Elastic collision
  • To get this excellent book: Real-Time Collision Detection

  • To read through some popular questions on gamedev.stackexchange.com, for example on collision (sort by votes)

Finally, you should know that DirectX 9 API is wildly obsolete, not supported and should not be used for new projects. It is notoriously hard to port D3DX* stuff to modern APIs. You may want to take a look at DirectX 11 and OpenGL 4, along with their support library ecosystems, or maybe even a good rendering or game engine. Specifically you may want to use some good math library (with vectors, matrices, linear algebra, geometry).

by xx3000   2018-10-06
I would also add Real-Time Rendering[2] and Real-Time Collision Detection[3] to the list of absolutely essential game development books.

[1]https://www.amazon.com/Engine-Architecture-Third-Jason-Grego... [2]https://www.amazon.com/Real-Time-Rendering-Fourth-Tomas-Aken... [3]https://www.amazon.com/Real-Time-Collision-Detection-Interac...

by anonymous   2017-08-20

12pm - I can't think of any immediately obvious, simple, way to do this in iOS. I'd look around for a package and if you're lucky there will be one! Otherwise it's just a case of plain hard programming.

You may possibly have to use beziers (Find the tangent of a point on a cubic bezier curve (on an iPhone)) to define the travel path. Or maybe, "simply" two half-circles.

From there use a "normal" slider concept to get the X position of the finger, but just position the "y" value of the red ball, per your equations. That will work OK.


For a better approach (I doubt it will be necessary), the NEXT more complicated approach is: ALSO note the Y value of the finger. WHEN THE FINGER IS NEAR the "difficult" parts", THEN INSTEAD consider the Y value. Do you see what I mean?

Finally the "ultimate solution" .. you need to get in to finding the "closest point on a curve" (i.e., give some point). This is classic game programming math. So follow something like

http://hal.archives-ouvertes.fr/docs/00/51/83/79/PDF/Xiao-DiaoChen2007c.pdf

Check out any of these classic books for that type of thing

http://www.amazon.com/Mathematics-Programming-Computer-Graphics-Edition/dp/1435458869

http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323

However, IMO it would be "thoughtless engineering" .. .solution "A" or "B" is typically perfect!

by anonymous   2017-08-20

The concept of interval notation comes up in both Mathematics and Computer Science. The Mathematical notation [, ], (, ) denotes the domain (or range) of an interval.

  • The brackets [ and ] means:

    1. The number is included,
    2. This side of the interval is closed,
  • The parenthesis ( and ) means:

    1. The number is excluded,
    2. This side of the interval is open.

An interval with mixed states is called "half-open".

For example, the range of consecutive integers from 1 .. 10 (inclusive) would be notated as such:

  • [1,10]

Notice how the word inclusive was used. If we want to exclude the end point but "cover" the same range we need to move the end-point:

  • [1,11)

For both left and right edges of the interval there are actually 4 permutations:

(1,10) =   2,3,4,5,6,7,8,9       Set has  8 elements
(1,10] =   2,3,4,5,6,7,8,9,10    Set has  9 elements
[1,10) = 1,2,3,4,5,6,7,8,9       Set has  9 elements
[1,10] = 1,2,3,4,5,6,7,8,9,10    Set has 10 elements

How does this relate to Mathematics and Computer Science?

Array indexes tend to use a different offset depending on which field are you in:

  • Mathematics tends to be one-based.
  • Certain programming languages tends to be zero-based, such as C, C++, Javascript, Python, while other languages such as Mathematica, Fortran, Pascal are one-based.

These differences can lead to subtle fence post errors, aka, off-by-one bugs when implementing Mathematical algorithms such as for-loops.

Integers

If we have a set or array, say of the first few primes [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ], Mathematicians would refer to the first element as the 1st absolute element. i.e. Using subscript notation to denote the index:

  • a1 = 2
  • a2 = 3
  • :
  • a10 = 29

Some programming languages, in contradistinction, would refer to the first element as the zero'th relative element.

  • a[0] = 2
  • a[1] = 3
  • :
  • a[9] = 29

Since the array indexes are in the range [0,N-1] then for clarity purposes it would be "nice" to keep the same numerical value for the range 0 .. N instead of adding textual noise such as a -1 bias.

For example, in C or JavaScript, to iterate over an array of N elements a programmer would write the common idiom of i = 0, i < N with the interval [0,N) instead of the slightly more verbose [0,N-1]:

function main() {
    var output = "";
    var a = [ 2, 3, 5, 7,  11, 13, 17, 19, 23, 29 ];
    for( var i = 0; i < 10; i++ ) // [0,10)
       output += "[" + i + "]: " + a[i] + "\n";

    if (typeof window === 'undefined') // Node command line
        console.log( output )
    else
        document.getElementById('output1').innerHTML = output;
}
 <html>
     <body onload="main();">
         <pre id="output1"></pre>
     </body>
 </html>

Mathematicians, since they start counting at 1, would instead use the i = 1, i <= N nomenclature but now we need to correct the array offset in a zero-based language.

e.g.

function main() {
    var output = "";
    var a = [ 2, 3, 5, 7,  11, 13, 17, 19, 23, 29 ];
    for( var i = 1; i <= 10; i++ ) // [1,10]
       output += "[" + i + "]: " + a[i-1] + "\n";

    if (typeof window === 'undefined') // Node command line
        console.log( output )
    else
        document.getElementById( "output2" ).innerHTML = output;
}
<html>
    <body onload="main()";>
        <pre id="output2"></pre>
    </body>
</html>

Aside:

In programming languages that are 0-based you might need a kludge of a dummy zero'th element to use a Mathematical 1-based algorithm. e.g. Python Index Start

Floating-Point

Interval notation is also important for floating-point numbers to avoid subtle bugs.

When dealing with floating-point numbers especially in Computer Graphics (color conversion, computational geometry, animation easing/blending, etc.) often times normalized numbers are used. That is, numbers between 0.0 and 1.0.

It is important to know the edge cases if the endpoints are inclusive or exclusive:

  • (0,1) = 1e-M .. 0.999...
  • (0,1] = 1e-M .. 1.0
  • [0,1) = 0.0 .. 0.999...
  • [0,1] = 0.0 .. 1.0

Where M is some machine epsilon. This is why you might sometimes see const float EPSILON = 1e-# idiom in C code (such as 1e-6) for a 32-bit floating point number. This SO question Does EPSILON guarantee anything? has some preliminary details. For a more comprehensive answer see FLT_EPSILON and David Goldberg's What Every Computer Scientist Should Know About Floating-Point Arithmetic

Some implementations of a random number generator, random() may produce values in the range 0.0 .. 0.999... instead of the more convenient 0.0 .. 1.0. Proper comments in the code will document this as [0.0,1.0) or [0.0,1.0] so there is no ambiguity as to the usage.

Example:

  • You want to generate random() colors. You convert three floating-point values to unsigned 8-bit values to generate a 24-bit pixel with red, green, and blue channels respectively. Depending on the interval output by random() you may end up with near-white (254,254,254) or white (255,255,255).

+--------+-----+ |random()|Byte | |--------|-----| |0.999...| 254 | <-- error introduced |1.0 | 255 | +--------+-----+

For more details about floating-point precision and robustness with intervals see Christer Ericson's Real-Time Collision Detection, Chapter 11 Numerical Robustness, Section 11.3 Robust Floating-Point Usage.

by anonymous   2017-08-20

Not really a website, but this book Real-Time Collision Detection is well worth it for what you are looking for.

by Simucal   2017-08-20

If you get the chance you should really check out the Collision Detection bible, "Real Time Collision Detection" if you plan on doing anything non-trivial. I'm not a professional game programmer and I understood and could apply the concepts in it with little trouble.

alt text http://msinilo.pl/blog/img/RealTimeCollisionDetection_13330/cover_rtcd.png

Amazon - Real Time Collision Detection

Basically, doing a set of line intersection tests is expensive no matter what. What you do is use things like Bounding Boxes (axis aligned or oriented) over your complex polygons. This will allow you to quickly do a worst case O(N^2) check of collision between each "object". You can then speed things up even further by using spatial trees (Binary Partitioning or QuadTrees) by only checking intersections of objects close to eachother.

This allows you to prune many, many collision tests. The best optimization is not doing something at all. Only once you have a collision between bounding boxes do you do your expensive line intersections to determine if the objects truly do intersect or not. This allows you to scale the number of objects up while still keeping the speed reasonable.