Real-Time Collision Detection

Christer Ericson

Mentioned 20

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.

More on Amazon.com

Mentioned in questions and answers.

I have seen number ranges represented as [first1,last1) and [first2,last2).

I would like to know what such a notation means.

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.

I'v always wondered this. In a game like GTA where there are 10s of thousands of objects, how does the game know as soon as you're on a health pack?

There can't possibly be an event listener for each object? Iterating isn't good either? I'm just wondering how it's actually done.

I would like to recommend the solid book of Christer Ericson on real time collision detection. It presents the basics of collision detection while providing references on the contemporary research efforts.

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

Anyone knows a source, website where I can get some good implementations of 3D intersection algorithms, like

  • intersection of sphere and sphere
  • sphere/ellipsoid
  • sphere/cuboid
  • ellipsoid/ellipsoid
  • ellipsoid/cuboid
  • cuboid/cuboid
  • sphere/ray
  • ellipsoid/ray
  • cuboid/ray
  • triangle/ray
  • quad/ray
  • triangle/triangle
  • quad/quad

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

You might want to put Eberly's Game Engine Design on your bookshelf. It has detailed algorithms and discussion for each of the intersections you've listed.

For a game I am developing I need an algorithm that can calculate intersections. I have solved the problem, but the way I have done it is really nasty and I am hoping someone here might have a more elegant solution.

A pair of points represent the end points of a line drawn between them. Given two pairs of points, do the drawn lines intersect, and if so, at what point?

So for example call the lines (A.x, A.y)-(B.x, B.y) and (C.x, C.y)-(D.x, D.y)

Can anyone think of a solution? A solution in any language will do.

Edit: A point I should have made clearer, the algorithm must return false if the point of intersection is beyond the lengths of the line segments.

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

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.

I'm building a 2D physics engine and I want to add broad-phase collision detection, though I only know of 2 or 3 types:

  • Check everything against everything else (O(n^2) complexity)
  • Sweep and Prune (sort and sweep)
  • something about Binary Space Partition (not sure how to do this)

But surely there's more options right? what are they? And can either a basic description of each be provided or links to descriptions?

I've seen this but I'm asking for a list of algorithms available, not the best one for my needs.

In this case, "Broad phase collision detection" is a method used by physics engines to determine which bodies in their simulation are close enough to warrant further investigation and possibly collision resolution.

I recommend quadtree partitioning. It's pretty simple and it works really well. Here is a Flash demo of brute-force collision detection vs. quadtree collision detection. (You can tell it to show the quadtree structure.) Did you notice how quadtree collision detection is only 3% of brute force in that demo?

Also, if you are serious about your engine then I highly recommend you pick up real-time collision detection. It's not expensive and it's a really great book which covers everything you would ever want to know. (Including GPU based collision detection.)

I would like to recommend the introductory reference to game physics from Ian Millington, Game Physics Engine Development. It has a great section on broad phase collision detection with sample code.

Here's my problem. I'm creating a game and I'm wondering about how to do the collisions. I have several case to analyze and to find the best solution for.

I'll say it beforehand, I'm not using any third party physics library, but I'm gonna do it in house. (as this is an educational project, I don't have schedules and I want to learn)

I have 2 types of mesh for which I have to make the collisions for :

1) Static Meshes (that move around the screen, but does not have ANY animation)

2) Skinned/Boned Meshes (animated)

Actually I have this solution (quite hacky :|)

First of all I have a test against some bounding volume that enclose the full mesh (capsule in my case), after :

1) For the static meshes I divide them manually in blocks (on the modeler) and for each of these blocks i use a sphere/AABB test. (works fine, but its a little messy to slice every mesh :P) (i tried an automatic system to divide the mesh through planes, but it gives bad results :()

2) For the animated mesh ATM i'm dividing the mesh at runtime into x blocks (where x is the number of bones). Each block contain the vertex for which that bone is the major influencer. (Sometimes works, sometimes gives really bad results. :|)

Please note that the divide of the mesh is done at loading time and not each time (otherwise it would run like a slideshow :D)

And here's the question :

What is the most sane idea to use for those 2 case? Any material for me to study these methods? (with some sourcecode and explanations would be even better (language is not important, when i understand the algorithm, the implementation is easy)) Can you argument why that solution is better than others? I heard a lot of talk about kd-tree, octree, etc..while I understand their structure I miss their utility in a collision detection scenario.

Thanks a lot for the answers!!!

EDIT : Trying to find a K-Dop example with some explanation on the net. Still haven't found anything. :( Any clues? I'm interested on HOW the K-Dop can be efficiently tested with other type of bounding volumes etc...but the documentation on the net seems highly lacking. :(

Pick up Christer Ericson's book, Real-Time Collision Detection. He discusses these very issues in great detail.

When reading articles, remember that in a real-world game application you will be working under hard limits of memory and time - you get 16.6ms per frame and that's it! So be cautious of any article or paper that doesn't seriously discuss the memory and CPU footprint of its algorithm.

I mainly focused on the Graphics aspects to create a little 2DGame. I've watched/looked at several tutorials but none of them were that pleasing. I already have a player(a square) moving and colliding with other squares on the screen. Gravity etc. Are also done.

If there are only that much objects as seen on the screen (30*20), everything works perfectly fine. But if I increase it to let's say 300*300 the program starts to run very slow since it has to check for so many objects.

I really don't get how games like Minecraft can work with ALL THOSE blocks and my program already gives up on 300*300 blocks.

I already tried to ONLY check for collisions when the objects are visible, but that leads to the program checking every single object for it's visibility leading to the same problem. What am I doing wrong? Help appreciated.

I'll post some code on how I handle the collisions.

player.collision(player, wall);

public void collision(Tile object1, Tile[] object2){
    collisionCheckUp(object1, object2);
    collisionCheckDown(object1, object2);
    collisionCheckLeft(object1, object2);
    collisionCheckRight(object1, object2);  
}

public void collisionCheckDown(Tile object1, Tile[] object2){

    for (int i = 0; i < Map.tileAmount; i++){
        if(object2[i] != null && object2[i].visible)
        {
            if(object1.isCollidingDown(object2[i])){
                object1.collisionDown = true;
                return;
            }

        }
    }       
    object1.collisionDown = false;
}

public void compileHullDown(){

     collisionHull = new Rectangle((int)x+3, (int)y+3, width-6, height);
}

int wallCount = 0;
    for (int x=0;x<Map.WIDTH;x++) {
        for (int y=0;y<Map.HEIGHT;y++) {

            if (Map.data[x][y] == Map.BLOCKED) {
                wall[wallCount] = new Tile(x * Map.TILE_SIZE, y *  Map.TILE_SIZE);
                wallCount++;
            }
        }
    }

The usual approach to optimize collision detection is to use a space partition to classify/manage your objects.

The general idea of the approach is that you build a tree representing the space and put your objects into that tree, according to their positions. When you calculate the collisions, you traverse the tree. This way, you will have to perform significantly less calculations than using the brute force approach, because you will be ignoring all objects in branches other than the one you're traversing. Minecraft and similar probably use octrees for collision (and maybe for rendering too).

The most common space partition structures are BSP-Trees, kd-Trees (a special type of BSP-trees). The simpler approach would be to use a uniform space partition for the start - split your space in axis-aligned halves.

The best resource on collision that I have discovered is this book. It should clarify all your questions on the topic.

That's if you wanted to do it right. If you want to do it quick, you could just sample the color buffer around your character, or only in the movement direction to determine if an obstacle is close.

How do games with gravity handle the relationship between moving things like players, monsters, or objects and the floor? Is the player constantly "falling into" the floor and being bounced back up?

Two ways to react to collisions that I have found are moving the player back to his previous location before the collision, and testing the new position before moving to see if it would result in a collision, but I don't see how either of these could deal with a platform that is rising upwards and needs to be able to lift the player. I'm looking at this from a 2D game design perspective, but I imagine that the same problem occurs in 3D game design. Any hints? Any references that I should check out? Thanks.

One of the most complete textbooks on this subject is Realtime Collision Detection by Christer Ericson. He has a companion blog too. Eric Lengyel's Mathematics for 3D Game Programming and Computer Graphics is useful too.

Given a bounding box, with definitions like bounds.min.(x/y/z), bounds.max.(x/y/z), and two points in 3D space (expressed as Vector3 objects), how can I determine if the line made by the two points intersects the bounding box?

Let me google that for you: Line Box Intersection (http://www.3dkingdoms.com/weekly/weekly.php?a=3)

Another link, with references (and code) for a lot of intersection tests: http://www.realtimerendering.com/intersections.html

If you want to learn more about intersection tests, this one is the bible: Real-Time Collision Detection (Amazon)

EDIT: the algorithm in this paper ("An Efficient and Robust Ray-Box Intersection Algorithm", Amy Williams and Steve Barrus and R. Keith Morley and Peter Shirley; journal of graphics, gpu, and game tools, Vol. 10(1), 49-54, 2005) looks especially concise and comes with (C++) source code, too.

I need a computer graphics book that gives the intersection curve of 3D mesh object and 2D plane. Could you advise me a book.

Real-Time Collision Detection by Christer Ericson could be a good choice for you since it covers many basic geometry intersection tests. Take a look at its table of contents.

Imagine a moving 3D force-based graph with colliding edges. How easy it is to write a specific physics engine for calculating edge (strings, ropes) collision so that every object would behave like in a real world? Strings should bend, nodes should repulse each other, etc. Accuracy beyond visual recognition as "looks real" doesn't matter, it's a game.

Edit: Maybe I forgot to mention, that approximating edges as multi-segmented strings is the only option I can think of.

And yes, would it be possible to scale such physics to hundreds or thousands of edges?

Physics engines have a lot of minor details in them to ensure that the end result 'looks real'. I would not recommend coding one unless you are looking to learn. Start with something that works and is free, such as Bullet Physics.

Besides, then you get to spend less time coding a physics engine and more time coding a game. Win-Win.

EDIT:

If you really want to program your own however, take a look at Real Time Collision Detection, which is pretty definitive information on the subject.

Imagine we have a 2D sky (10000x10000 coordinates). Anywhere on this sky we can have an aircraft, identified by its position (x, y). Any aircraft can start moving to another coordinates (in straight line).

There is a single component that manages all this positioning and movement. When a aircraft wants to move, it send it a message in the form of (start_pos, speed, end_pos). How can I tell in the component, when one aircraft will move in the line of sight of another (each aircraft has this as a property as radius of sight) in order to notify it. Note that many aircrafts can be moving at the same time. Also, this algorithm is good to be effective sa it can handle ~1000 planes.


If there is some constraint, that is limiting your solution - it can probably be removed. The problem is not fixed.

I actually found an answer to this question.

It is in the book Real-Time Collision Detection, p. 223. It's better named, as well: Intersecting Moving Sphere Against Sphere, where a 2D sphere is a circle. It's not so simple (and I may also violate some rights) to explain it here, but the basic idea is to fix one of the circles as a point, adding its radius to the radius of the moving one. The new direction for the moving one is the sum of the two original vectors.

For a school project, I have to be able to move inside a 3D scene like a room and implement collision detection with its walls.

I'm looking for tutorials and bibliography that deals with the subject.

I already have the Redbook and Opengl's Superbible.

There is an entire book on Real-Time Collision Detection.

Before you write your own collision detector from scratch, you should consider implementing the rest of your setup and plugging in an existing library. It is much easier to develop a program, if you have a correct result to compare to.

The GAMMA research group has developed a number of collision detection packages that are popular in robotics and more. You or your institution may ask them for a package for non-commercial or academic use. One of these packages, PQP, is the inspiration for Yaobi, an open-source C++ library.

Yaobi and PQP are both easy to use, requiring only a bunch of triangles to model a geometry.

I am trying to make a simple 3d platform game. The issue I'm having is with the collision detection and response. I am currently representing my player character (for wall and floor collisions) with a sphere.

I employ a simple gravity force and directional forces using the arrow keys for movement.

My problem occurs when I come to an edge (like a cliff). I slide over the edge like a ball would, but the behaviour I'm looking for is to fall off the edge like an upright cylinder. A boolean "I am on the platform, or I am not on the platform", and not "I'm sliding off the edge gradually".

The problem with using an upright cylinder is that sliding up stairs automatically becomes impossible, and when walking along any kind of slope, the cylinder must either touch only by one edge, or be partially embedded in the slope.

What is a good collision representation of the player character in a 3d platform game?

You may keep the sphere for the collision detection.

And if you find collision, then you should compute more accurately for collision, by dividing your character into several components.

One common solution is to used sphere (because the collision is easy to compute) for the head, the trunk, and a cylinder for the legs and the arms (you can also add sphere for the hands and feet).

Do you have the possibility to read this book ?

this may be a more general opengl question. using OpenGL ES for 2d, and reading through the tutorials, I learned how to do the basic matrix transformations like rotating and moving an object around the screen. so far, so good - I have some objects moving around and rotating.

the next step for me is to do collision detection. something simple like checking for intersection between bounding boxes would probably be ok. however, I'm stuck because in order to know when the bounding boxes intersect, I have to know the translated, rotated coordinates of my objects. but I can't find a way to get those numbers from OpenGL.

so do I really have to do the rotations and transformations myself, in addition to having OpenGL do them, just to get the translated coordinates? or is there some way to apply the current matrices to a vertex and get the results? couldn't OpenGL do the math much faster than me?

thanks for any help, I would appreciate some general advice on how this kind of thing is usually done.

Visual information and collision information are usually treated individually in games. Note that you should reuse all your transform information in your physics code (that is all your matrices), not the vertex information. It does sound a bit inefficient and counter intuitive at first.

One of the reasons is that it is unusual to require collision detection at polygon accuracy. Instead, approximate volumes are usually sufficient.

So you're rarely ever going to collide a set of polygons with another set of polygons - in fact you should be trying your hardest not to. You should be colliding spheres against themselves, boxes, lines or "swept" spheres (capsules). Larger non-convex models can be broken into multiple convex volumes and treated separately.

So if you were using the visual mesh directly for collision, your physics code would be much slower than using a lower-detail mesh, or approximate volume like a sphere or a box. It is a bit more of a pain, but the slow part of collision isn't the transforms, its the actual detection - so this method actually works out faster.

Depending on your game, I'd consider using spheres as much as possible - they don't need to be rotated, and tests are easy. Its also easy to generate a bounding sphere at model load time, before the geometry disappears into GPU land.

This book is a very good resource, and there is lots of online information as well.

I am developing a 3D Game Engine as a project. I would like to use space partitioning algorithms for each triangle/polygon in my scene to efficiently detect collisions. I just want to know (before I start programming the specifics) how fast is a typical space partitioning algorithm in modern computer games? I have dynamical objects so I am thinking that I might have to repartition my scene every frame. Is that possible and still achieve a reasonable frame rate? It would be very much appreciated if the answer could include data (e.g. the FPS, number of polygons, etc.). If that is too much trouble, just tell me if it is plausible to repartition every frame.

Any help would be appreciated.

I would first suggest reading the chapter on Broad-Phase Collision Detection with CUDA. It goes into comparison of different broad phase collision algorithms. Your performance depends on a few key variables. The first variable is whether or not your algorithm is implemented using GPU acceleration. The previously cited article contains some benchmarks on framerate vs. number of objects. At the very least it should give you a good idea of what is achievable.

If you don’t plan on GPU acceleration, sweep and prune is one of the easiest to implement. I don’t know the exact figures, but it performs well when there are few objects and your objects don’t vary too much between frames. In this situation, you have O(n) performance. This is a good one to start with as a baseline, because it is trivial to implement.

If you are really getting serious, I recommend the book Real-Time Collision Detection. I used this one when doing research on collision detection methods. It was a great resource.

I'm a fairly inexperienced programmer currently learning C# and trying to learn Game Design in general.

I'm using Microsoft's XNA framework to build a Galaga-esque Scrolling Shooter game. After a few rough trials in which I struggled with shoddy OOP structure, making some bad design choices, I've finally come up with a respectable start of an engine.

Presently I'm having problems with making collision detection not lag the game out. My current engine keeps all active game objects in a List object and cycles through each, checking if it collides with each other object. Needless to say, it could be a lot better.

Here's my collision checking, done in the ObjectHandler class.

public override void Update(GameTime gameTime)
    {
    ...
        //Handle collisions
        foreach (GameObject obj in Objects)
        {
            ICollideable e = obj as ICollideable;
            //Check if the object implements ICollideable
            if (e != null)
            {
                //Check collision with each other object
                foreach (GameObject obj2 in Objects)
                {
                    //Check if the second object implements ICollideable
                    ICollideable e2 = obj2 as ICollideable;
                    //check if they are in the same sector
                    if (e2 != null && SameSector(e.Sector,e2.Sector))
                    {
                        //Check if the collision masks interesect
                        //if so call each object's collision event
                        if (e.Mask.Intersects(e2.Mask))
                        {
                            e.CollisionEvent(e2);
                            e2.CollisionEvent(e);
                        }
                    }
                }
            }
        }
      ...
    }

Here's the SameSector function.

private bool SameSector(Point p1, Point p2)
    {
        if (Math.Abs(p1.X-p2.X)<=1 && Math.Abs(p1.Y-p2.Y)<=1)
            return true;
        else 
            return false;
    }

"Mask" here is a Rectangle object, which is part of the XNA framework. As you can see I've implemented a sort of spacial partitioning system, where each object sets which 60x60 square it's in. However, I'm not really sure that I've done anything useful as it takes just as much time to check if two objects are in the same sector (or adjacent sectors) as it does to check if they're colliding.

I've seen a question similar to this posted already, but it didn't quite satisfy my question. From it I did gather that a time management system is useful. I'll try to implement that eventually but as I'm still fairly new to programming, I'd like to optimize the collision checking itself before delving into more advanced design.

So, is there I way I can effectively optimize my current collision checking, or is what I have way off to begin with?

Spatial partitioning will only help you if you've implemented it in a way that doesn't require you to compare every object against every object in some way.

In your spatial partitioning grid, you want each grid cell to have some kind of membership list of objects within it, as well as for each object to be aware of what cell it's in. Then you only need to do comparisons between an object and all other objects within that cell and within immediately adjacent cells (because an object may overlap bounds). The downside is you now need to keep all this state updated.

I highly recommend the book Real-Time Collision Detection which covers several different broad-phase partitioning schemes in depth and their relative strengths and weaknesses, in addition to other CD topics. In addition to uniform grids, there are hierarchical grids, quadtrees, sweep and prune, and other techniques that may be more appropriate for you (sweep and prune might be particularly beneficial).

I've been working as a programmer for some years. I have a degree on computer science so I have been bought about geometry, calculus, algebra, etc... The problem is that it was several years ago. This days I'm returning to one of my main hobbies, this is, game programming and I'm trying to build a little game where physics/maths are a key concept.

During some days I have been gathering information over the net about collision detection, restitution, etc... and the math involved but I get stuck sometimes on affirmations/forumulas that don't know where they are taken from and I get frustrated. I think it is a good time to start reviewing a lot of math concepts and do a bunch of exercises to recall all the concepts.

Could anybody suggest any information, books, videos, etc... and more important exercise books to start my new math rearming?.

For physics development books I would recommend what are commonly referred to as "The Orange Books." they are two books for physics engine development. One is more of a tutorial of how to go about creating your first physics engine and the other is all about collision detection.

Game Physics Engine Development by Ian Millington

Real Time Collision Detection by Christer Ericson

They both have chapters on the math that is going to be used in the book.

I'm making an iOS app for sound synthesis. And I need a custom slider by which user can adjust the sound frequency. The slider has unique design - wave form (an example is shown in the picture).

Custom slider

How to make slider with complex curve?

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!

I really need to know how to make collision detection. I can only do axis-aligned-bounding-boxes. I have heard of other methods. I heard of something called a minimal oobb. but I can't figure them out. I'm still in school and I'm pretty good at math. But I don't know the first thing about physics. I know I could use Bullet physics but I really would like to know how to do it myself. I don't really know about anything other than aabbs and oobbs. and as I said before, aabbs are all I can do. So please show me what methods there are and where I can learn how to do them. Thanks in advance :D