   Collision Detection with my BVH.
  Hi all,I am slowly but surely getting together a real time walkthrough for a large scene I modeled in 3d max, some of you no doubt have read some of my many threads asking for help at various stages.Anyway, one of the last things I am trying to tackle is the collision detection and response. After a bit of research and advise I have set up a bounding volume hierarchy, formed with AABBs (the make-up of my fully static scene is such that they give good tight fits frequently, aside from the fact that they are fast). This splits the scene down and at the leaves of the BVH, there is just one primitive.The whole scene uses triangles as its primitive type, and all geometry is fully static. I am then solely trying to pick up and respond to collisions from the user walking around with the camera, and the scene.I know there is alot of literature around the subject of CD, but that is kind of my problem at the moment - slightly overloaded on stuff from the net and at a point where I cant see quite the best way of going about things.Some things I read suggest I should be working out rays for the users movement from the last frame to the new one, and seeing if that line segment overlaps with my hierarchy, then when I reach a leaf I can intersect the ray with the primitive itself for the exact point of collision.Other things suggest that I should be modelling my user as something like a box or a cylinder and overlapping that with my hierarchy, but I am then not sure how they are tackling the exact collision point at leaves, perhaps with another ray? or can you produce an exact collision point from calculations on the primitive triangle and the users bounding volume, eliminating rays altogether?The whole ray thing just has me a little confused. I haven't worked with them before, and they look very simple, but im just having a bit of a mind-fog about it. From a Nehe tutorial I see a formula for a point rayPointOnRay = Raystart + t * RaydirectionSo I am forming a line segment from raystart to pointOnRay? and im also unclear on what t signifies - obviously its how far along the direction we move, but how are we finding t?Also, how does modelling the users movement as a ray work alongside modelling the user as a bounding volume such as a cylinder?You can see there are things rather jumbled up in my head about the whole thing. I see that there are only 2 steps, collisions of the user with bounding volumes, and collisions of the user with final primitives, but its all not quite clicking.If anyone can point me in the right direction, or perhaps throw me a link or 2 which might explain these things in particular well, I would really appreciate it.Thanks   
  You're on the right track. Now comes the maths!the equation of a ray (line, segments, ...) P = O + D * t is a parametric equation. Any point on the line [O, D] satisfied the equation. Say t = 0, P = O, t = 1, P = O + D.Similarly, Any point on the segment [A, B] satisfied the equation P = A + (B - A) * t, 0 < t < 1. t = 0, P = A, t = 1, P = B, t = 0.5, P = (A + B) / 2.So what you try to do with the parametric equation and collision detection, is solve the equation of the ray for 't'. You alreay know 'O' (the origin of your ray) and 'D' (the direction). 't' will give you teh point of intersection, and, if O and D represents phyiscal values (O = position, D = velocity), the time of collision for example. Say you want to know when a bullet hits a sphere (a collision shape representing the head of your character for example). The bullet will be simplified to a ray, and the head will be a sphere, where any point P on the sphere [C, r] will satisfy the equation (P - C)^2 = r^2.so, you have two equations, one unknown (t).P = O + D * t(P - C)^2 = r^2Replace P in the second equation with the ray equality, and then you end up with one equation of the second order, using vectors.((O - C) + D * t)^2 - r^2 = 0it's in the form : a * t^2 + b * t + c = 0, wherea = (D . D)b = (D . (O - C)) * 2c - ((O - C) . (O - C)) - r^2which you solve, as any other second order equations, and if an intersection occurs, it will leave you with two solutions for 't'. Then to find the points of collision, you simply put your two values for 't' back in the first equation.So that's teh principle of rays. Rays can be tested against planes (for triangle collision). the plane [N, A] equation being (P - A) . N = 0 (A is any point on the plane, i.e. one of the triangle vertex). Again, plugging the ray eqaution into the plane equation gives you a value for tt = ((A - O) . N) / (D . N), which in turn gives you the point of intersection of the ray and plane. As for collision detection, I've always seen the player being modeled by a bounding volume (Box, spheres, ...). Rays aren't really used litteraly, unless for bullets, particles and things like that. The simplest is to model your character with spheres. Boxes are a little bit more complicated to use. here is the simplest coll det algorythm you can use with spheres and complex environments. Character : [P, V, r] (position, velocity, bounding radius)time step : dt.Objects to test against : [objects[], numObjects].if character unhindered, at the end of the time step, P = P + V * dt.if he is colliding, his position will be 'constrained' by the collision. then you can change his velocity to refect against the collision. void Collide(Vector& P, Vector& V, float r, float dt){    Vector Ppredicted = P + V * dt; // position if no collision    Vector Pconstrained = Ppredicted; // position after collisions are processed    // test for intersections against objects    for(int i = 0; i < numObjects; i ++)    {   bool inside = false; // is the point inside the object already.   // get closest point on object from our colliding character   Vector Q = object.getClosestPoint(Pconstrained, bool inside);   // distance from closest point Vector Delta = (Pconstrained - Q);   float  dist = Delta.Length();   // closest point too far from character. no collision   if(dist > r) return false;// we are within range, push the constrinaed position away.   float  sign = (inside)? -1.0f : 1.0f; // which direction to push   dist *= sign;   // the 'push' vector   Vector Interference = Delta * ((r - dist) / dist);   // push sphere away from collision.   Pconstrained += Interference;    }    // Check if we collided with anything major    Vector Diff = (Pconstrained - Ppredicted);    const float tolerance = 1.0E-6f;    float dist = Diff.Length();    // Yes? then 'bounce'    if (dist > tolerance)    {   Vector Normal = Diff / dist; // normalise normal of collision   V -= (2.0f * V.DotProduct(Normal)) * Normal; // bounce    }}WIth these 20 lines of code, you can do simple intersection detection with any type of object (sphere, cylinder, box, triangle). All you need for each object type is a 'closest point from a point' function, which is not trivial but relatively easy. Then that code will check collisions for you against your charcter's bounding sphere, and apply a physical response to it. I have an example of what it does here. Note that there are two 'main.cpp'. The first one is simpler, the second one more complicated, it is splitting the travel of the character to avoid going through things whn you move fast.   