##Introduction##

This lesson might be a little long, but at the end of it, you'll have a great sliding camera so you can run around on your terrain created by the hightmap in the last lesson. On top of all this, you will know how to add new models and geometry to the "polygon soup", which is just a name for all the polygons we will be checking for collision against, so you can load in a 3d model such as a building or tree, and be able to check for a collision against it so you can run up the stairs or slide around the tree for example.

The algorithm we will use to accomplish this "sliding ellipsoid" is taken from the paper "Improved Collision detection and Response" written by Kasper Fauerby. It can be found .[http://www.peroxide.dk/papers/collision/collision.pdf][here].

##Collision Detection and Response Overview##

I will cover the idea of what we will be doing here , then explain each part in a little more detail when we get to the code.

The first thing we do, is create an ellipsoid that will represent our camera (or object). We will convert the velocity vector, position of the camera or object, and all geometry from "world" space to "ellipsoid" space, so we are working with a "unit" sphere. Then, before we actually move the sphere, we will "project" the sphere along the velocity vector (called a "swept" sphere), and check when and if the sphere will collide with a triangle before we reach the end of the velocity vector. If we detect that there will be a collision with a triangle before the sphere reaches it's "final destination" (the end of the velocity vector), we will move the sphere to the point along the velocity vector that it first "touches" or "rests" on the triangle, then we will use the collision point (where the sphere and triangle meet), and the vector we get from the position of the sphere minus (-) the collision point, to get the "sliding" plane. We can use this sliding plane to get a new velocity vector that runs parallel to the sliding plane that the sphere can follow and "slide" across the triangle or around a hard edge (such as stairs, or a doorway) (This is also the part we can modify if we would rather the sphere "bounce" off the collision plane instead of sliding and gliding). After we have a new velocity vector, and before we move the sphere, we need to repeat (recurse) this operation all over again with the new velocity vector in case that the new velocity vector pushes the sphere into another triangle. Finally, we move the position to the final destination point, and convert it from "ellipsoid" space back to "world" space!

+[http://www.braynzarsoft.net/image/100073][Collision detection and response]

##Outline of Operation##

Before I get into the details, i'd like to explain and go through the steps we will take from beginning to end, so you see how the "big picture" looks.

First, we get a velocity vector for our camera (or object we are moving), which describes the direction the camera travels, and the distance it travels (distance is the "length" of the velocity vector)

+[http://www.braynzarsoft.net/image/100074][Sliding sphere]

After we have a velocity vector, we need to check if the bounding ellipsoid will collide with the world before we move the camera to the end of the velocity vector. So we call our CollisionSlide() function, giving it our velocity vector and position (in world space), along with the geometry (vertex positions and index list) information (in world space). Make a note that the geometry we pass into this function is already transformed into world space, since we will assume it does not change at all throughout the scene (and if it did, the vertex positions in this array would need to be updated). What I mean to say, is transform this geometry to world space BEFORE you create the vertex positions array (which we call the "polygon soup"), and do not transform it again throughout the scene (without updating the "polygon soup").

**Ellispoid Space**
In our CollisionSlide() function, we will transform the velocity vector and position into ellipsoid space.

After we do that conversion, we call the function that will do the collision detection stuff, CollideWithWorld(). We pass the velocity and position (which are now in ellipsoid space), along with the world geometry (stuff we want to collide with).

CollideWithWorld() is a recursable function, which means it can call itself over and over again, so the first thing we do in this function is check that the recursion is not too deep, so we do not get into an infinite loop calling itself over and over again.

**Swept-Sphere to Triangle Collision Detection**
We will enter a loop that gets a single triangle at a time from the polygon soup, convert the triangle (vertex positions) from world space to ellipsoid space, then call the function that checks for a collision between a swept-sphere and a single triangle, SphereCollidingWithTriangle(). This loop does not stop looping until all triangles have been checked, because it's possible, and very likely, that the first triangle you collide with is not the closest triangle, so this loop will check all triangles for a collision, and keep track of the closest collision, if there was a collision at all.

In this function, we will do 3 different collision detections with the triangle, one for the surface (inside the triangles edges), one for the vertices that make up the triangle, and one for the 3 edges of the triangle.

This function will find the collision point, and the distance to the collision point between the swept sphere and triangle.

If at this point, there was no collision detected, we return the new position of the sphere (current position + velocity vector).

**Sliding Plane Collision Response**
If there was a collision, we move the sphere down the velocity vector to the collision point. We do not want to actually move the sphere ALL the way to the point where it's actually resting on the triangle. Instead we move it to a VERY close distance to the collision point, and move the collision point away from the triangle as well so we do not have inaccuracy when getting the new velocity vector. The reason we do not want the sphere to actually be touching the triangle is because of floating point inaccuracy. What may happen (and will), is that the new velocity vector may not be PERFECTLY parallel to the triangle, and off by a FRACTION of a degree, pointing towards the triangles surface, so that the next time we recurse, a collision will be detected immediately with the same triangle, and the new velocity vector will not change at all, wasting an entire recursion and performance for no reason.

Next we get the sliding plane, which is defined by a point on the plane (point of collision), and a normal (spheres position - collision point). We call this the "sliding" plane in this lesson, as we will use it to slide the sphere (camera) across triangles and around edges, but you can use this plane to have objects "bounce" off planes and corners instead of sliding.

Next, we get the distance from the destination point (where the sphere WOULD have gone if no collision was detected (position + velocity), to the sliding plane.

We move the destination point down the planes normal, so that it's laying IN the plane ((destination point) - (distance from destination point to plane) * (plane normal)).

We use this NEW destination point, and the point of collision, to get the new velocity vector, so that now when we move the sphere, it travels along the sliding plane!

Now we check if the new velocity vector is very small so we do not make an extra recursion for no noticeable reason, and return the newest position (position we have before finding this newest velocity vector).

if the velocity vector was still long enough to noticeably move the sphere, we call this funtion (CollideWithWorld()) again (recurse), to check if this new velocity vector will push the sphere into another triangle.

After we get to the end of our velocity vector, we return from this function back into CollisionSlide(), where we either add a new velocity vector for gravity and do the whole operation again, or go straight to the end of the function and convert our spheres final position from ellipsoid space to world space. After we have the final position in world space, we return the position, which (in this lesson is the camera) will be the new position of the object you are moving!

##Ellipsoid Space##

Alright, let's get started. Ellipsoid space is what we call a "vector space". A vector space can be described by a vector containing one or more components representing the separate axes of the space (eg. "world" space, as we'll call it, is a 3D space, which means it has 3 axes (x,y,z). Our 3D world space is described by the vector (1,1,1). a 1D space would be a vector containing a single component (x), a 2D space would contain 2 (x,y), and a 4D space would have 4 (x,y,z,w), etc. Ellipsoid space is a 3D space, which makes things much easier to transform from "world" space (where the ellipsoid is an ellipsoid), to ellipsoid space (where the ellipsoid is now represented as a "unit" sphere), and from ellipsoid space back to world space. So, what exactly is an ellipsoid? An ellipsoid is basically a "stretched" sphere, just like a 2d ellipse is a "stretched" circle. An ellipsoid can be defined by "3" radiuses, one for each axis (eg. (1,3,1)). A sphere, as you probably know, can be defined by a single radius. A sphere can however, also be defined by 3 axes, where all 3 axes are the same length (eg. (1,1,1)). In "Ellipsoid Space", the ellipsoid is actually a "unit" sphere. A "unit" sphere has a radius of "1". This makes the algorithm so much easier, as a collision point ANYWHERE on the surface is always "1" unit away from the center or position of the sphere (theoretically speaking of course, not taking "floating point innacuracy" into account ;).

+[http://www.braynzarsoft.net/image/100075][Ellipsoid space]

The algorithm and calculations we will do to impliment collision detection and collision response use a "unit" sphere. What this means, is that before we send the velocity vector and camera position to the functions to impliment collision detection and response, we need to transform them first to ellipsoid space. Because we transform those to ellipsoid space, we ALSO have to transform our geometry positions to ellipsoid space. The result of the calculations will also be in ellipsoid space, so we will have to transform the results back to "world" space, where the ellipsoid is an ellipsoid again.

To transform between "world" space and "ellipsoid" space is really easy. We will be using a 3D vector to define our ellipsoid, and this same vector is what i keep calling ellipsoid space, so it is the vector we use to transform everything into ellipsoid space. All we have to do to transform a coordinate or 3d vector from world space to ellipsoid space, is divide the world space vector by the ellipsoid space vector:

    ellipsoidSpace = (1, 3, 1); // Our ellipsoid (ellipsoid space)
    w_Position = (6, 9, 12); // Position of the camera in "world" space
    e_Position = w_Position / ellipsoidSpace; // The cameras position in "ellipsoid" space (6, 3, 12)

After transforming the cameras velocity vector, position, and world geometry into ellipsoid space, the ellipsoid that is "bound" to our camera is actually a unit sphere! Like I mentioned, after we do our calculations, our results will be in ellipsoid space, which means we will have to transform them back to "world" space. To transform from ellipsoid space to world space, just multiply the world space vector by the ellipsoid space vector. Like this:

    ellipsoidSpace = (1, 3, 1); // Our ellipsoid (ellipsoid space)
    e_Position = (6, 3, 12); // Position of the camera in "ellipsoid" space
    w_Position = e_Position * ellipsoidSpace; // The cameras position in "world" space (6, 9, 12)

Now that we know how to convert between world space and ellipsoid space, we can now focus on working with a "unit" sphere!

##The Swept Sphere##

I've mentioned the swept sphere a couple times before now, so what exactly is a swept sphere? A swept sphere is a "projection" of the sphere along a velocity vector. A swept sphere is very useful in collision detection, because it cannot POSSIBLY miss a collision if done right. Think about checking for a collision between two objects in a game. You move the objects, then test for a collision wherever it lands. The problem with this is if the velocity vector is too long, the objects might pass completely through each other before getting to their destination points, where the collision check is done. So when the collision check is done at their final destinations, there will be no collision detected because the objects are not touching each other, even though they passed right through each other. A swept sphere on the other hand, looks ahead down the velocity vector BEFORE moving the object. It will find the point down the velocity vector that a collision will happen, then move the object to that point of collision, or whatever you want to do when a collision is detected. The point is, that the swept sphere will find the collision if there is one, no matter how long the velocity vector, an object using a swept sphere collision detection WILL NOT pass through another object without a collision being detected. Now for the math part of the swept sphere. A swept sphere can be defined by a starting position, a velocity vector, and a position in time down the velocity vector (t), where "t" is the time (0 to 1) down the velocity vector. t = 0 means the swept sphere is at the very beginning of the velocity vector, so at it's starting position. When t = 1, the sphere is at the end of the velocity vector. If t is greater than 1, then the sphere has gone past the length of the velocity vector, and if t is less than 0, the sphere is moving backwards. We can find the position of the sphere at any time (t) down the velocity vector like this:

    sweptSpherePosition = position + (velocity * t)

+[http://www.braynzarsoft.net/image/100076][Swept sphere]

##Swept-Sphere to Triangle Collision Detection##

From here on (until we get to the code), we will assume that everything has already been converted to ellipsoid space (so we are working with a unit sphere). We need to check for 3 different collisions with each triangle in the "polygon soup". Before we even check the swept sphere and triangle for a collision, we check to see if the triangle is facing "away" from the direction the velocity vector is pointing, because we should never have to collide with the back side of a triangle. This will theoretically remove half the triangles in the scene, which increases our performance a lot.

+[http://www.braynzarsoft.net/image/100077][Swept sphere to triangle collision detection]

**Sphere - (Inside Triangle) Collision Detection**

Now that we know the velocity vector is pointing towards the front face of the triangle, we will check first for a collision with the triangles "plane". A plane can be defined by a normal and a point on the plane. The point on the plane is just one of the three triangle's vertices. To get the plane's normal, we first get two of the triangles edges, then cross them to get the triangle's normal (which is the same as the plane's normal). "Crossing" two vectors results in a vector that is orthogonal to the two vectors, or in other words, points down the "third" axis. For example, if we were to cross a vector pointing down the x axis (1,0,0) with a vector pointing down the y axis (0,1,0), the result would be a vector pointing down the z axis (0,0,1), so
"(1,0,0) x (0,1,0) = (0,0,1)"
(We have actually found the triangle normal by now, since we needed it in the last step which checks if the velocity vector is facing the front face of the triangle):

    pointInPlane = p0;
    triNormal = (p1 - p0) x (p2 - p0);

Where p0, p1, and p2 are the three vertices that make up the triangle, and "x" denotes a cross product.

Next we'll check to see if the velocity vector is parallel with the plane. We can do this using a dot product between the velocity vector and the planes normal. If the result is zero (0), the velocity vector is parallel with the plane. A dot product can be useful to find the degree between two vectors, as the result of a dot product is directly related to the cosine of the two vectors angle. A dot product between two vectors resulting in zero (0) means that the two vectors are orthogonal. If the velocity is parallel with the plane, we need to check the distance between the sphere and plane. If the distance is greater than one (1) (unit sphere's radius), then we know that the sphere cannot possibly collide with the triangle, and exit early. Otherwise, if the sphere is less than one unit away from the triangles plane, we know the sphere is "imbedded" in the plane, so we set a boolean variable to make sure we do not do the calculation that checks if the sphere is colliding with the inside of the triangle, as that will result in a divide by zero error. However, we still need to check if the sphere collides with either one of the triangles vertices or edges, since thats still possible.

+[http://www.braynzarsoft.net/image/100078][Swept sphere]

The Plane Equation. Now is a good time to talk about the plane equation. At this point we will need the distance between the sphere's position and the plane. But before we get the distance between the position and plane, we need to solve the Plane Equation, "Ax + By + Cz + D = 0", which will give us the "Plane Constant" (D). ABC are the (x,y,z) of the plane normal, and xyz are the (x,y,z) of the point in the plane, and D is the plane constant. To get D, we do some simple algebra:

    1. Ax + By + Cz + D = 0			// The Plane Equation
    2. -D = Ax + By + Cz			// Subtract "D" from both sides
    3. -1 * -D = -1*Ax + -1*By + -1*Bz	// Multiply both sides by -1 (Because we are looking for "D", not "-D"
    4. D = -(Ax + By + Cz)			// Final Equation to find "D". Same as the above (#3), but simplified

Using the plane constant, we can get the "signed" distance between the sphere's position and the triangle's plane, by using this equation:

    signedDistance = planeNormal . point + planeConstant

"." denotes a dot product. A negative value means the point is "behind" the plane.

So now if we have found that the velocity is NOT parallel to the plane, we find WHEN (t) (along the infinite line made by the velocity vector) the swept sphere "touches" or "rests" on the plane. The sphere will actuall rest on the plane twice, once when it first touches the plane, and once on the other side of the plane after it passes through the plane. This gives us two times the sphere rests on the plane, which we will call t0 and t1. We will need the closest one.

+[http://www.braynzarsoft.net/image/100079][Swept sphere]

We know that at t0 (when the sphere first makes contact with the plane), the sphere's position will be exactly 1 unit away from the plane. So at t1, we know the "signed" distance between the sphere's position and the plane will be "-1". Knowing this, we can calculate t0 and t1 something like this:

    N = Plane Normal
    C = Plane Constant
    p = sphere's position (point along the velocity vector)
    v = velocity vector
    
    1 = N . (p + t0 * v) + C		// Signed distance from the position along the velocity vector at time t0, to the plane is "1" unit
    
    1 = t0 * (N . v) + (N . p) + C		// Pull t0 out to get it by itself
    
    1 - (N . p) + C = t0 * (N . v)		// subtract (N . p) + C from both sides
    
    (1 - (N . p) + C) / (N . v) = t0	// divide both sides by (N . v) to get the final equation which finds t0!

We know that t1 is the same thing, but when the signed distance is -1 instead of 1, so now we can find both t0 and t1:

    t0 = ( 1 - (N . p) + C) / (N . v)
    t1 = (-1 - (N . p) + C) / (N . v)

In the code, by the time we calculate t0 and t1, we already have the signed distance between the plane and spheres position stored, and the plane normal dot velocity stored, so our equations looks even more simple: (remember that (N . p) + C is actually the signed distance between "p" and the plane)

    t0 = ( 1.0f - signedDistFromPositionToTriPlane) / planeNormalDotVelocity;
    t1 = (-1.0f - signedDistFromPositionToTriPlane) / planeNormalDotVelocity;

Now that we have t0 and t1, the two times that the sphere rests on the triangles plane, what do we do with them? Remember that when t (t0 and t1) is zero (0) it is at time zero, which means the beginning of the velocity vector. Basically, it represents the spheres origin. When t is 1, then the sphere is at the end of the velocity vector. So what we want to do now is find of the collision happens outside the (0, 1) timeframe, which represents the full length of the velocity vector. If t0 is greater than 1, then we know both contacts with the plane are past the length of the velocity vector, and there was no collision, so we can return. Same goes for if t1 is less than 0, which means that both contacts with the plane happened behind the velocity vector (which actually shouldn't even happen because we check if the velocity vector is facing the front face of the triangle or not ;).

We have just found WHEN the sphere collides with the triangles plane, but now we need to find two more things, WHERE the sphere collides with the triangles plane, and IF the collision point is even inside the triangle. This is one of the times that working with a unit sphere makes things more simple, since the distance from the position of the sphere to the point of contact with the plane is 1 unit. To get the intersection point, all we have to do is get the position of the sphere at the time (t0) of contact, and subtract the triangle planes normal:

+[http://www.braynzarsoft.net/image/100080][Swept sphere]

    spherePosAtTimeOfContact = position + t0 * velocity
    pointOfContact = spherePosAtTimeOfContact - planeNormal
    
    // Or, as we have it in the code:
    pointOfContact = (position + t0 * velocity) - planeNormal

Next we find if the point of contact is INSIDE the triangle. I have explained how to find if a point is inside a triangle in the direct3d 11 lesson on picking, found here. So now, if the collision point is INSIDE the triangle, we can store our two results that will be used to get the sliding plane our sphere will slide across (or bounce if thats what you wish), which are the distance to the collision, and the collision point. I say "store" because we still have to go through every triangle in the polygon soup to find if there was a collision with a triangle that's closer than the current collision point. If we just returned the first collision we found, we might skip a triangle that is actually closer, and just go straight through that triangle.

+[http://www.braynzarsoft.net/image/100081][Swept sphere]

**Sphere - Vertex Collision Detection**

+[http://www.braynzarsoft.net/image/100082][Swept sphere]

Now, if the collision point with the plane we found in the section above was NOT inside the triangle, we will need to go on and check the vertices and edges of the triangle for a collision. We'll start with the vertices. We do the vertex check first because if we didn't, it's likely that when you slide over a corner (where the vertex is) of a triangle, a collision might not be detected exactly, and the sphere will get a little pushed into the geometry, maybe not far enough to actually fall through the world, but enough to "stick" and slide along the edge of the triangle, which is not what you want in a game.
We will be solving the quadratic equation :

    At² + Bt + C = 0

to find when (t) the sphere touches the vertex. There will be two possible results (if there's a result at all), once when the sphere first touches the vertex, and one for when the sphere passes the vertex and the vertex touches the other side of the sphere. Let's start by getting the parameters of this equation:

    A = velocityLength * velocityLength			// Velocity's length squared (All three vertex checks use the same A)
    B = 2 * (velocity . (position - vertPos))
    C = (vertPosToPositionLength * vertPosToPositionLength) - 1
    t = 1

I won't get into how to solve this equation, just how to set the parameters correctly. We have a function that will solve this for us (if it's even solvable), which was taken from Kasper Fauerby's paper i mentioned at the beginning of this lesson. So anyway, if this equation is not solvable, there was no collision between the sphere and the vertex. Otherwise, if there was an answer to this equation, we set that to "t" (meaning replace t with the new answer, since t was already set to 1). The answer, if there was one, is the time down the velocity vector that the sphere first makes contact with the vertex. If there was a collision, we can find the two results we need for finding the sliding plane, which are the collision point (vertex position), and the distance to the collision point (t * velocityLength).

**Sphere - Edge Collision Detection**

+[http://www.braynzarsoft.net/image/100083][Swept sphere]

Even if there was a collision with a vertex, we must still check the edges of the triangle, since it's possible that the sphere is intersecting with one of the edges before it actually touches the vertex. We can find a if there was a collision (and how far down the velocity vector) between the sphere and edge by solving the same quadratic equation, "At² + Bt + C = 0", as we did with the sphere-vertex collision detection, but this time the parameters are a bit more complex:

    edge = p1 - p0	// Get the edge between the first vertex and second vertex
    positionToVertex = position - p0;
    
    A = edgeLength² * -velocityLength² + (edge . velocity)²
    B = edgeLength² * 2(velocity . positionToVertex) - 2((edge . velocity)(edge . positionToVertex))
    C = edgeLength² * (1 - positionToVertexLength²) + (edge . positionToVertex)²
    t = 1

Again, if there was a collision with the edge, the equation is solvable, and will return t (the time down the velocity vector that the sphere intersects with the edge). If after checking all three edges of the triangle, and none of the equations were solvable, there was no collision at all with this triangle, and we move on to the next triangle.

Collision Detection Results
After we have checked every triangle in the polygon soup for a collision, we will know if there was a collision or not. If there was no collision at all after we have checked all the triangles, we can move our sphere to the end of the velocity vector without changing directions. Then we can either return to our game, or add an extra vector representing gravity, and do the check all over again.

If there WAS a collision after checking all the triangles, we will need to give the Collision Response step two bits of information. They are the position of the collision point, and the distance from the center of the swept sphere (swept sphere's position) to the collision point. I say swept sphere because we are not talking about our spheres origin here. We are talking about the distance (time (t)) down the velocity vector that the collision will occur. In the next part we will move the sphere, which changes it's "origin" as I called it.

##Sliding Plane Collision Response##

I say sliding plane because that's how we will impliment the "collision plane". You can however, and very easily too, change this part from sliding the position along the collision plane, to bouncing off the collision plane. This works well for throwing a ball for example, where it bounces off walls and the ground and whatever, and gravity is taken into account (if you want). But for our camera, which this lesson focuses on, we will be using the collision plane as a sliding plane, and slide across the plane.

We will only reach this part of the whole collision detection/response algorithm if a collision was detected, so, if we have indeed made it this far, we know a collision has occured.

The first thing we will do, is move our sphere's origin to the new position (point along velocity vector where collision occured). However, we do not actually move the sphere ALL the way so it is really TOUCHING the triangle, but instead, move it to a VERY close distance to the collision point. We will also have to move the collision point away from the triangle too, so we don't get innacurate results from not moving the sphere all the way to where it is touching the collision point. The reason we do this whole step is because of floating point inaccuracy. What this means is that in computers, the results might be a FRACTION of a FRACTION of a degree off. So when we get our new velocity vector, it might not be 100% parallel to the sliding plane, but instead lean a tiny tiny bit towards the plane, which might also be the face of the triangle. So instead of the sphere sliding nicely across the face of a triangle, if we did not move the sphere a little away from the triangle, the next recurse might detect a collision against the triangle immediately, and the whole recurse was completely wasted because the resulting velocity vector will be the same, and the sphere has not moved at all, wasting performance, and making the whole sliding process sticky and jerky. It won't always happen that the collision will be found of course, but theoretically, half the time you are sliding across a triangles surface, you would "stick" for a moment if we did not move the sphere slightly away from the actual collision point with the triangle.

+[http://www.braynzarsoft.net/image/100084][Swept sphere]

After we have moved our sphere to RIGHT BEFORE we collide, we get our sliding plane (which you could also call collision plane i suppose)! To define a plane, (i've already mentioned this, but oh well), you need a point in the plane, and the plane's normal. For our sliding plane, we will use the collision point as the point in the plane, and (spherePosition - collisionPoint) as the sliding plane's normal.

Once we have our plane, we need to find the distance from the plane to the "intendedDestination", or where the sphere WOULD have traveled to if no collision was detected, so once again we will have to solve the plane equation "Ax + By + Cz + D = 0" to get the plane constant "D". You can look up where we find a collision with the inside of a triangle if you don't remember how to solve this equation.

**Find the New Velocity Vector**
Now we get to use the sliding plane (or collision plane). What we do first, is get the "new" destinationPoint. We use the signed distance from the intended destination point to the sliding plane, and the planes normal, to move the intended destination point along the planes normal until it is laying in the sliding plane. That is how we impliment sliding. However, you could use this "sliding" plane as a "bounce" plane, and instead of moving the intended destination to lay in the plane itself, you could "reflect" the intended destination point off the sliding plane, so that when the object collides with the surface, it will "bounce" off instead of sliding across the surface. With the sliding vector we impliment in this lesson, if you think about it, you will see that the velocity vector gets shorter as we move it along the sliding planes normal into the sliding plane, so that eventually, it will be extremely small if we kept colliding with triangles.

+[http://www.braynzarsoft.net/image/100085][Swept sphere]

Notice the short length of the bounce planes new velocity vector. You will have to normalize that vector, then multiply it by a scalar value representing the length you want it to be. You could just set it as the length of your old velocity vector, then it will bounce off the surface with as much force as it came in with, or you could make the length of the new velocity vector slightly smaller than the old velocities length, so that it loses power and speed each time it bounces. choice is yours!

We can get the new destination point (for sliding) like this:

    newDestinationPoint = destinationPoint - signedDistFromDestPointToSlidingPlane * slidePlaneNormal

That's not the end quite yet though, we need to use that new destination point to get the velocity vector we want the sphere to travel along. We can get the new velocity vector by subtracting the collision point from the new destination point like this:

    newVelocityVector = newDestinationPoint - intersectionPoint

Next we want to check that this velocity vector is not so small that we wouldn't notice if the sphere traveled along it or not, so we don't waste time recursing for this very short velocity vector. If it's very very short, where moving the sphere to the end of it would not make a noticeable difference, we return the last position we found. If the vector is still long enough to make a noticeable difference, we will do another recursion, which checks all the geometry again, but this time using the new position and velocity vector, in case that this new velocity vector pushes the sphere into another triangle!

Gravity

In this lesson, gravit is included. We have a vector that points down on the y axis, which is our gravity's velocity. After we go through all the collision detection and collision response stuff from above for the velocity vector that is moving the camera around (or object), we do it all once more with the gravity's velocity vector! We'll use the sphere's final position we got from doing the above operations on the camera's "unique" velocity vector (the once we send to the function ourselves).

You will notice however, that even the slightest slope will cause the camera to slide down. Let this be an exercise! Fix it so that the gravity only works when the camera (or object) is on very steep slopes, or in free fall.

Convert Results Back to World Space

At last, after we have either reached the end of our velocity vector, or recursed too far, we will have the final position of our camera (or object)... in ellipsoid space! but don't worry, with a very simple multiplication, we will have the position in world space, ready to use!

    finalPosition = currentPosition * ellipsoidSpace

##Globals##

These are a couple global variables that are used for our collision detection and response stuff. unitsPerMeter helps us define the "veryCloseDistance" variable later. gravity is just a vector representing the pull of gravity (in the negative y axis). The next two are vector arrays, which store our "polygon soup".

    const float unitsPerMeter = 100.0f;
    
    XMVECTOR gravity = XMVectorSet(0.0f, -0.2f, 0.0f, 0.0f);
    
    std::vector<XMFLOAT3> collidableGeometryPositions;
    std::vector<DWORD> collidableGeometryIndices;

##The CollisionPacket Structure##

This structure will be passed to and from the collision detection and response functions to make passing data between them easier.

    struct CollisionPacket{
    	// Information about ellipsoid (in world space)
    	XMVECTOR ellipsoidSpace;
    	XMVECTOR w_Position;
    	XMVECTOR w_Velocity;
    
    	// Information about ellipsoid (in ellipsoid space)
    	XMVECTOR e_Position;
    	XMVECTOR e_Velocity;
    	XMVECTOR e_normalizedVelocity;
    
    	// Collision Information
    	bool foundCollision;
    	float nearestDistance;
    	XMVECTOR intersectionPoint;
    	int collisionRecursionDepth;
    };

##New Functions##

These are our function prototypes, so that they can be called anywhere in our code.

    // Collision Detection and Response Function Prototypes
    XMVECTOR CollisionSlide(CollisionPacket& cP,			// Pointer to a CollisionPacket object (expects ellipsoidSpace, w_Position and w_Velocity to be filled)
    	std::vector<XMFLOAT3>& vertPos,						// An array holding the polygon soup vertex positions
    	std::vector<DWORD>& indices);						// An array holding the polygon soup indices (triangles)
    
    XMVECTOR CollideWithWorld(CollisionPacket& cP,			// Same arguments as the above function
    	std::vector<XMFLOAT3>& vertPos,
    	std::vector<DWORD>& indices);
    
    bool SphereCollidingWithTriangle(CollisionPacket& cP,	// Pointer to a CollisionPacket object	
    	XMVECTOR &p0,										// First vertex position of triangle
    	XMVECTOR &p1,										// Second vertex position of triangle
    	XMVECTOR &p2,										// Third vertex position of triangle 
    	XMVECTOR &triNormal);								// Triangle's Normal
    
    // Checks if a point (inside the triangle's plane) is inside the triangle
    bool checkPointInTriangle(const XMVECTOR& point, const XMVECTOR& triV1,const XMVECTOR& triV2, const XMVECTOR& triV3);
    
    // Solves the quadratic eqation, and returns the lowest root if equation is solvable, returns false if not solvable
    bool getLowestRoot(float a, float b, float c, float maxR, float* root);

##The CollisionSlide() Function##

I'm not going to spend much time explaining these functions, since i made sure the code was WELL commented, and the main ideas are explained at the top of this page.

But anyways, this function will be the function we call from our update camera function, where we get our cameras velocity vector, and pass in a CollisionPacket object which contains the cameras position, velocity vector, and ellipsoid space vector. We also pass in the polygon soup to this function. This function will then convert the cameras vector and position to ellipsoid space, using the ellipsoidSpace vector we put in the CollisionPacket object we sent to this function. After the conversion, we call CollideWithWorld to get our new position (the new position is only different from the position we passed into this function if a collision was detected). After we do that, we can do the same thing but this time with the gravity velocity vector, and the new position of our camera (or object if we are using this function for an object and not the camera, such as the character in a 3rd person camera). Finally, we convert the final position from ellipsoid space back to world space, and return the position so we can update our camera.

    XMVECTOR CollisionSlide(CollisionPacket& cP,
    	std::vector<XMFLOAT3>& vertPos,
    	std::vector<DWORD>& indices)
    {
    	// Transform velocity vector to the ellipsoid space (e_ denotes ellipsoid space)
    	cP.e_Velocity = cP.w_Velocity/cP.ellipsoidSpace;
    
    	// Transform position vector to the ellipsoid space
    	cP.e_Position = cP.w_Position/cP.ellipsoidSpace;
    
    	// Now we check for a collision with our world, this function will
    	// call itself 5 times at most, or until the velocity vector is
    	// used up (very small (near zero to zero length))
    	cP.collisionRecursionDepth = 0;
    	XMVECTOR finalPosition = CollideWithWorld(cP, vertPos, indices);
    
    	// Add gravity pull:
    	// This is simply adding a new velocity vector in the downward
    	// direction (defined globaly) to pull the ellipsoid down, then doing the
    	// collision check against all the geometry again. The way it is now, the
    	// ellipsoid will "slide" down even the most slightest slope. Consider this
    	// an exercise: only impliment gravity when standing on a very steep slope,
    	// or if you are not standing on anything at all (free fall)
    
    	// To remove gravity uncomment from here .....
    
    	cP.e_Velocity = gravity / cP.ellipsoidSpace;	// We defined gravity in world space, so now we have
    	// to convert it to ellipsoid space
    	cP.e_Position = finalPosition;
    	cP.collisionRecursionDepth = 0;
    	finalPosition = CollideWithWorld(cP, vertPos, indices);
    
    	// ... to here
    
    	// Convert our final position from ellipsoid space to world space
    	finalPosition = finalPosition * cP.ellipsoidSpace;
    
    	// Return our final position!
    	return finalPosition;
    }

##The CollideWithWorld() Function##

This function will do the actual collision detection and response stuff. It assumes that e_Velocity and e_Position of the CollisionPacket object sent to it has be filled (in ellipsoid space).

This is the recursable function, where it will call itself again if the velocity vector is too long by the time it reaches the end of the function. The reason is because the new velocity vector we create in this function, might push the sphere into another triangle, so we must check all the geometry in case there is another collision with the new velocity vector. This is why we check to make sure the recursion level is not deeper than 5, or that it has only called itself 5 or less times. There are certain times, such as when the sphere get's "pushed" into the center of a triangle, which does happen by the way, that the velocity vector does not change it's length each time through, so the function will keep calling itself over and over again. Now that we check that it only calls itself 5 times, it will not continue to call itself forever, and freeze the program (it would actually crash the program eventually).

We then get the normalized velocity vector, which is used when checking for the actual collision, and reset a couple variables in the CollisionPacket object sent to this function.

Then we enter a loop which will loop through every trying in the polygon soup passed into this function, convert each of the vertices positions from world space to ellipsoid space, get the triangle normal, and finally call the function that checks for a collision between the swept sphere and a triangle (SphereCollidingWithTriangle).

After we check for collisions, we check to see if there actually was a collision, and return the spheres position + velocity vector if there was no collision detected. Otherwise we move on.

Next we will get the sliding plane, and find the new velocity vector, which will cause the sphere to "slide" across the sliding plane (or, if you want, to "bounce" off the plane).

Finally we check to see if the length of the velocity vector is very small, and if it is, return the new position of our sphere. If it's still long enough though, we will call this function again with the new velocity vector to see if the sphere is pushed into another triangle.

    XMVECTOR CollideWithWorld(CollisionPacket& cP,
    	std::vector<XMFLOAT3>& vertPos,
    	std::vector<DWORD>& indices)
    {
    	// These are based off the unitsPerMeter from above
    	float unitScale = unitsPerMeter / 100.0f;
    	float veryCloseDistance = 0.005f * unitScale;	// This is used to keep the sphere from actually "touching" 
    	// the triangle, as that would cause problems since
    	// each loop it would ALWAYS find a collision instead
    	// of just sliding along the triangle
    
    	// This will stop us from entering an infinite loop, or a very long loop. For example, there are times when the sphere
    	// might actually be pushed slightly into the triangles center, where the recursion will keep repeating and finding a collision
    	// even though the velocity vector does not change (I had serious problems with this part for a couple days... I couldn't
    	// figure out why the ellipsoid would LAUNCH at certain times, but if i set the ellipsoid space to (1,1,1) (a sphere), it would
    	// act normal. Stupid me made a mistake and was returning w_Position here instead of e_Position, so that the world space position
    	// was being multiplied by the ellipsoid space and "launching" it whenever it accidently got pushed into a triangle)
    	if (cP.collisionRecursionDepth > 5)
    		return cP.e_Position;
    
    	// Normalize velocity vector
    	cP.e_normalizedVelocity = XMVector3Normalize(cP.e_Velocity);	
    
    	// Initialize collision packet stuff
    	cP.foundCollision = false;
    	cP.nearestDistance = 0.0f;
    
    	// Loop through each triangle in mesh and check for a collision
    	for(int triCounter = 0; triCounter < indices.size() / 3; triCounter++)
    	{
    		// Get triangle
    		XMVECTOR p0, p1, p2, tempVec;
    		p0 = XMLoadFloat3(&vertPos[indices[3*triCounter]]);
    		p1 = XMLoadFloat3(&vertPos[indices[3*triCounter+1]]);
    		p2 = XMLoadFloat3(&vertPos[indices[3*triCounter+2]]);
    
    		// Put triangle into ellipsoid space
    		p0 = p0/cP.ellipsoidSpace;
    		p1 = p1/cP.ellipsoidSpace;
    		p2 = p2/cP.ellipsoidSpace;
    
    		// Calculate the normal for this triangle
    		XMVECTOR triNormal;
    		triNormal = XMVector3Normalize(XMVector3Cross((p1 - p0),(p2 - p0)));
    
    		// Now we check to see if the sphere is colliding with the current triangle
    		SphereCollidingWithTriangle(cP, p0, p1, p2, triNormal);
    	}
    
    	// If there was no collision, return the position + velocity
    	if (cP.foundCollision == false) {
    		return cP.e_Position + cP.e_Velocity;
    	}
    
    	// If we've made it here, a collision occured
    	// destinationPoint is where the sphere would travel if there was
    	// no collisions, however, at this point, there has a been a collision
    	// detected. We will use this vector to find the new "sliding" vector
    	// based off the plane created from the sphere and collision point
    	XMVECTOR destinationPoint = cP.e_Position + cP.e_Velocity;
    
    	XMVECTOR newPosition = cP.e_Position;	// Just initialize newPosition
    
    	// If the position is further than "veryCloseDistance" from the point
    	// of collision, we will move the sphere along the velocity path until
    	// it "almost" touches the triangle, or point of collision. We do this so
    	// that the next recursion (if there is one) does not detect a collision
    	// with the triangle we just collided with. We don't need to find a collision
    	// with the triangle we just collided with because we will be moving parallel
    	// to it now, and if we were finding the collision with it every recursion
    	// (since it's the closest triangle we would collide with), we would 
    	// finish our 5 recursions (checked above) without ever moving after
    	// touching a triangle, because before the triangle has a chance to move
    	// down the new velocity path (even though it's about parallel with the triangle)
    	// it would find the collision with the triangle, and simply recompute the same
    	// velocity vector it computed the first time. This would happen because of
    	// floating point innacuracy. theoretically, we would not have to worry about this
    	// because after the new velocity vector is created, it SHOULD be perfectly parallel
    	// to the triangle, and we detect that in our code and basically skip triangles
    	// who are perfectly parallel with the velocity vector. But like i said, because
    	// of innacuracy, the new velocity vector might be VERY SLIGHTLY pointed down towards
    	// the triangles plane, which would make us waste a recursion just to recompute the same
    	// velocity vector. Basically, the whole sliding thing works without this, but it's a lot
    	// more "choppy" and "sticky", where you get stuck in random places.
    	if (cP.nearestDistance >= veryCloseDistance)
    	{
    		// Move the new position down velocity vector to ALMOST touch the collision point
    		XMVECTOR V = cP.e_Velocity;
    		V = XMVector3Normalize(V);
    		V = V * (cP.nearestDistance - veryCloseDistance);
    		newPosition = cP.e_Position + V;
    
    		// Adjust polygon intersection point (so sliding
    		// plane will be unaffected by the fact that we
    		// move slightly less than collision tells us)
    		V = XMVector3Normalize(V);
    		cP.intersectionPoint -= veryCloseDistance * V;
    	}
    
    	// This is our sliding plane (point in the plane and plane normal)
    	XMVECTOR slidePlaneOrigin = cP.intersectionPoint;
    	XMVECTOR slidePlaneNormal =	newPosition - cP.intersectionPoint;
    	slidePlaneNormal = XMVector3Normalize(slidePlaneNormal);
    
    	// We will use the sliding plane to compute our new "destination" point
    	// and new velocity vector. To do this, we will need to solve another quadratic
    	// equation (Ax + By + Cz + D = 0), where D is what we call the plane constant,
    	// which we use to find the distance between the sliding plane and our original
    	// destination point (original as up until now, since it's likely that this is
    	// not the first recursion of this function, and the original original destination
    	// has been changed up until now).
    	// First the point in the plane
    	float x = XMVectorGetX(slidePlaneOrigin);
    	float y = XMVectorGetY(slidePlaneOrigin);
    	float z = XMVectorGetZ(slidePlaneOrigin);
    
    	// Next the planes normal
    	float A = XMVectorGetX(slidePlaneNormal);
    	float B = XMVectorGetY(slidePlaneNormal);
    	float C = XMVectorGetZ(slidePlaneNormal);
    	float D = -((A*x) + (B*y) + (C*z));
    
    	// To keep the variable names clear, we will rename D to planeConstant
    	float planeConstant = D;
    
    	// Get the distance between sliding plane and destination point
    	float signedDistFromDestPointToSlidingPlane = XMVectorGetX(XMVector3Dot(destinationPoint, slidePlaneNormal)) + planeConstant;
    
    	// Now we calculate the new destination point. To get the new destination point, we will subtract
    	// the distance from the plane to the original destination point (down the planes normal) from the
    	// original destination point. It's easier to picture this in your head than explain, so let me try
    	// to give you a very simple picture. Pretend you are this equation, standing on the plane, where UP
    	// (your head) is pointing the same direction as the plane's normal. directly below you is the "destination"
    	// point of the sphere. Your job as this equation is to "pull" the destination point up (towards the planes
    	// normal) until it is resting "in" the plane. If you can picture this the way i'm trying to get you to, you
    	// can see that the new velocity vector (from the point of collision between sphere and plane) to the new
    	// destination is "shorter" and parallel to the plane, so that now when the sphere follows this new velocity
    	// vector, it will be traveling parallel (sliding) across the triangle, at the same time, it does not travel
    	// as far as it would have if there was no collision. This is exactly what we want, because when you think about
    	// it, we do not run up mountains as fast as we run on flat ground, and if we run straight into a wall in our
    	// game, we will just stop moving, or if we run ALMOST straight into the wall, we will not go cruising sideways,
    	// but instead slowly move to either side. In my lesson on braynzarsoft.net, This is explained in pictures
    	XMVECTOR newDestinationPoint = destinationPoint - signedDistFromDestPointToSlidingPlane * slidePlaneNormal;
    
    	// I believe this line was covered briefly in the above explanation
    	XMVECTOR newVelocityVector = newDestinationPoint - cP.intersectionPoint;
    
    	// After this check, we will recurse. This check makes sure that we have not
    	// come to the end of our velocity vector (or very close to it, because if the velocity
    	// vector is very small, there is no reason to lose performance by doing an extra recurse
    	// when we won't even notice the distance "thrown away" by this check anyway) before
    	// we recurse
    	if (XMVectorGetX(XMVector3Length(newVelocityVector)) < veryCloseDistance) {
    		return newPosition;
    	}
    
    	// We are going to recurse now since a collision was found and the velocity
    	// changed directions. we need to check if the new velocity vector will
    	// cause the sphere to collide with other geometry.
    	cP.collisionRecursionDepth++;
    	cP.e_Position = newPosition;
    	cP.e_Velocity = newVelocityVector;
    	return CollideWithWorld(cP, vertPos, indices);
    }

##The SphereCollidingWithTriangle() Function##

Here we have the SphereCollidingWithTriangle() function, which will check if a swept sphere will collide with a triangle. I'm not getting into details here, just look above for the explanation of how this function works (if the comments in the code don't do it for ya ;).

    bool SphereCollidingWithTriangle(CollisionPacket& cP, XMVECTOR &p0, XMVECTOR &p1, XMVECTOR &p2, XMVECTOR &triNormal)
    {
    	// This function assumes p0, p1, p2, and the triangle normal are in ellipsoid space
    	// and that e_Position e_Velocity, and e_normalizedVelocity are defined in ellipsoid space
    	// In other words, this function checks for a collision between a SPHERE and a triangle,
    	// not an ellipsoid and a triangle. Because of this, the results from this function
    	// (specifically cP.nearestDistance and cP.intersectionPoint) are in ellipsoid space
    
    	// Check to see if triangle is facing velocity vector
    	// We will not triangle facing away from the velocity vector to speed this up
    	// since we assume that we will never run into the back face of triangles
    	float facing = XMVectorGetX(XMVector3Dot(triNormal, cP.e_normalizedVelocity));
    	if(facing <= 0)
    	{ 
    		// Create these because cP.e_Velocity and cP.e_Position add slightly to the difficulty
    		// of reading the equations
    		XMVECTOR velocity = cP.e_Velocity;
    		XMVECTOR position = cP.e_Position;
    
    		// t0 and t1 hold the time it takes along the velocity vector that the sphere (called a swept sphere)
    		// will "collide" (resting on or touching), once on the front side of the triangle (t0), and once on the
    		// backside after it goes "through" the triangle (t1) (or vertex or edge).
    		float t0, t1;
    
    		// If sphere is in the plane, it will not intersect with the center of the triangle
    		// but instead possibly intersect with one of the vertices or edges first
    		bool sphereInPlane = false;
    
    		// Find the plane equation in which the triangle lies in (Ax + By + Cz + D = 0)
    		// A, B, and C are the planes normal, x, y, and z respectively
    		// We can find D (a.k.a the plane constant) using some simple algebra, which we will do below
    		// x, y, and z in the equation defines a point in the plane. Any point in the plane
    		// will do, so we will just use p0
    
    		// First the point in the plane
    		float x = XMVectorGetX(p0);
    		float y = XMVectorGetY(p0);
    		float z = XMVectorGetZ(p0);
    
    		// Next the planes normal
    		float A = XMVectorGetX(triNormal);
    		float B = XMVectorGetY(triNormal);
    		float C = XMVectorGetZ(triNormal);
    
    		// Lets solve for D
    		// step 1: 0 = Ax + By + Cz + D
    		// step 2: subtract D from both sides
    		//			-D = Ax + By + Cz
    		// setp 3: multiply both sides by -1
    		//			-D*-1 = -1 * (Ax + By + Cz)
    		// final answer: D = -(Ax + By + Cz)
    		float D = -((A*x) + (B*y) + (C*z));
    
    		// To keep the variable names clear, we will rename D to planeConstant
    		float planeConstant = D;
    
    		// Get the signed distance from the cameras position (or object if you are using an object)
    		// We can get the signed distance between a point and plane with the equation:
    		// SignedDistance = PlaneNormal * Point + PlaneConstant 
    
    		// I've mentioned this before, but i'll do it again. When using xna math library vector function
    		// that return a scalar value (like a float) such as "XMVector3Dot", an XMVECTOR is returned, with
    		// all elements (x,y,z,w) containing that scalar value. We need to extract one, and any will do since
    		// they are all the same, so we extract the x component using "XMVectorGetX"
    		float signedDistFromPositionToTriPlane = XMVectorGetX(XMVector3Dot(position, triNormal)) + planeConstant;
    
    		// This will be used a couple times below, so we'll just calculate and store it now
    		float planeNormalDotVelocity = XMVectorGetX(XMVector3Dot(triNormal, velocity));
    
    		/////////////////////////////////////Sphere Plane Collision Test////////////////////////////////////////////
    		// Check to see if the velocity vector is parallel with the plane
    		if (planeNormalDotVelocity == 0.0f) 
    		{
    			if (fabs(signedDistFromPositionToTriPlane) >= 1.0f) 
    			{
    				// sphere not in plane, and velocity is
    				// parallel to plane, no collision possible
    				return false;
    			}
    			else 
    			{
    				// sphere is in the plane, so we will now only test for a collision
    				// with the triangle's vertices and edges
    				// Set sphereInPlane to true so we do not do the operation
    				// which will divide by zero if the velocity and plane are parallel
    				sphereInPlane = true;
    			}
    		}
    		else 
    		{
    			// We know the velocity vector at some point intersects with the plane, we just
    			// need to find how far down the velocity vector the sphere will "touch" or rest
    			// on the plane. t0 is when it first touches the plane (front side of sphere touches)
    			// and t1 is when the back side of the sphere touches.
    
    			// To find when (the time or how far down the velocity vector) the "velocity vector" itself
    			//intersects with the plane, we use the equation: (* stands for a dot product)
    			// t = (PlaneNormal * Point + PlaneConstant) / (PlaneNormal * Velocity);
    			// We have already calculated both sides of the divide sign "/", so:
    			// t = signedDistance / normalDotVelocity;
    
    			// Now remember we are working with a unit sphere (since everything has been moved from
    			// the usual space to our ellipsoid space). The unit sphere means that the distance from
    			// the center of the sphere to ANYWHERE on it's surface is "1". We are not interested in
    			// finding when the actual velocity vector intersects with the plane, but instead when
    			// the surface of the sphere "touches" the surface of the plane. We know that the distance
    			// from the center of the sphere is "1", so all we have to do to find when the sphere touches
    			// the plane is subtract and subtract 1 from the signed distance to get when both sides of the
    			// sphere touch the plane (t0, and t1)
    			t0 = ( 1.0f - signedDistFromPositionToTriPlane) / planeNormalDotVelocity;
    			t1 = (-1.0f - signedDistFromPositionToTriPlane) / planeNormalDotVelocity;
    
    			// We will make sure that t0 is smaller than t1, which means that t0 is when the sphere FIRST
    			// touches the planes surface
    			if(t0 > t1)
    			{
    				float temp = t0;
    				t0 = t1;
    				t1 = temp;
    			}
    
    			// If the swept sphere touches the plane outside of the 0 to 1 "timeframe", we know that
    			// the sphere is not going to intersect with the plane (and of course triangle) this frame
    			if (t0 > 1.0f || t1 < 0.0f) 
    			{
    				return false;
    			}
    
    			// If t0 is smaller than 0 then we will make it 0
    			// and if t1 is greater than 1 we will make it 1
    			if (t0 < 0.0) t0 = 0.0;
    			if (t1 > 1.0) t1 = 1.0;
    		}
    
    		////////////////////////////////Sphere-(Inside Triangle) Collision Test///////////////////////////////////////
    		// If we've made it this far, we know that the sphere will intersect with the triangles plane
    		// This frame, so now we will check to see if the collision happened INSIDE the triangle
    		XMVECTOR collisionPoint;		// Point on plane where collision occured
    		bool collidingWithTri = false;	// This is set so we know if there was a collision with the CURRENT triangle
    		float t = 1.0;					// Time 
    
    		// If the sphere is not IN the triangles plane, we continue the sphere to inside of triangle test
    		if (!sphereInPlane) 
    		{
    			// We get the point on the triangles plane where the sphere "touches" the plane
    			// using the equation: planeIntersectionPoint = (Position - Normal) + t0 * Velocity
    			// Where t0 is the distance down the velocity vector that the sphere first makes
    			// contact with the plane
    			XMVECTOR planeIntersectionPoint = (position + t0 * velocity - triNormal);
    
    			// Now we call the function that checks if a point on a triangle's plane is inside the triangle
    			if (checkPointInTriangle(planeIntersectionPoint,p0,p1,p2))
    			{
    				// If the point on the plane IS inside the triangle, we know that the sphere is colliding
    				// with the triangle now, so we set collidingWithTri to true so we don't do all the extra
    				// calculations on the triangle. We set t to t0, which is the time (or distance) down
    				// the velocity vector that the sphere first makes contact, then we set the point of 
    				// collision, which will be used later for our collision response
    				collidingWithTri = true;
    				t = t0;
    				collisionPoint = planeIntersectionPoint;
    			}
    		}
    
    		/////////////////////////////////////Sphere-Vertex Collision Test//////////////////////////////////////////////
    		// If the sphere is not colliding with the triangles INSIDE, we check to see if it will collide with one of
    		// the vertices of the triangle using the sweep test we did above, but this time check for each vertex instead
    		// of the triangles plane
    		if (collidingWithTri == false) 
    		{
    			// We will be working with the quadratic function "At^2 + Bt + C = 0" to find when (t) the "swept sphere"s center
    			// is 1 unit (spheres radius) away from the vertex position. Remember the swept spheres position is actually a line defined
    			// by the spheres position and velocity. t represents it's position along the velocity vector.
    			// a = sphereVelocityLength * sphereVelocityLength
    			// b = 2(sphereVelocity . (spherePosition - vertexPosition))	// . denotes dot product
    			// c = (vertexPosition - spherePosition)^2 - 1
    			// This equation allows for two solutions. One is when the sphere "first" touches the vertex, and the other is when
    			// the "other" side of the sphere touches the vertex on it's way past the vertex. We need the first "touch"
    			float a, b, c; // Equation Parameters
    
    			// We can use the squared velocities length below when checking for collisions with the edges of the triangles
    			// to, so to keep things clear, we won't set a directly
    			float velocityLengthSquared = XMVectorGetX(XMVector3Length(velocity));
    			velocityLengthSquared *= velocityLengthSquared;
    
    			// We'll start by setting 'a', since all 3 point equations use this 'a'
    			a = velocityLengthSquared;
    
    			// This is a temporary variable to hold the distance down the velocity vector that
    			// the sphere will touch the vertex.
    			float newT;
    
    			// P0 - Collision test with sphere and p0
    			b = 2.0f * ( XMVectorGetX( XMVector3Dot( velocity, position - p0 )));
    			c = XMVectorGetX(XMVector3Length((p0 - position)));
    			c = (c*c) - 1.0f;
    			if (getLowestRoot(a,b,c, t, &newT)) {	// Check if the equation can be solved
    				// If the equation was solved, we can set a couple things. First we set t (distance
    				// down velocity vector the sphere first collides with vertex) to the temporary newT,
    				// Then we set collidingWithTri to be true so we know there was for sure a collision
    				// with the triangle, then we set the exact point the sphere collides with the triangle,
    				// which is the position of the vertex it collides with
    				t = newT;
    				collidingWithTri = true;
    				collisionPoint = p0;
    			}
    
    			// P1 - Collision test with sphere and p1
    			b = 2.0*(XMVectorGetX(XMVector3Dot(velocity, position - p1)));
    			c = XMVectorGetX(XMVector3Length((p1 - position)));
    			c = (c*c) - 1.0;
    			if (getLowestRoot(a,b,c, t, &newT)) {
    				t = newT;
    				collidingWithTri = true;
    				collisionPoint = p1;
    			}
    
    			// P2 - Collision test with sphere and p2
    			b = 2.0*(XMVectorGetX(XMVector3Dot(velocity, position - p2)));
    			c = XMVectorGetX(XMVector3Length((p2 - position)));
    			c = (c*c) - 1.0;
    			if (getLowestRoot(a,b,c, t, &newT)) {
    				t = newT;
    				collidingWithTri = true;
    				collisionPoint = p2;
    			}
    
    			//////////////////////////////////////////////Sphere-Edge Collision Test//////////////////////////////////////////////
    			// Even though there might have been a collision with a vertex, we will still check for a collision with an edge of the
    			// triangle in case an edge was hit before the vertex. Again we will solve a quadratic equation to find where (and if)
    			// the swept sphere's position is 1 unit away from the edge of the triangle. The equation parameters this time are a 
    			// bit more complex: (still "Ax^2 + Bx + C = 0")
    			// a = edgeLength^2 * -velocityLength^2 + (edge . velocity)^2
    			// b = edgeLength^2 * 2(velocity . spherePositionToVertex) - 2((edge . velocity)(edge . spherePositionToVertex))
    			// c =  edgeLength^2 * (1 - spherePositionToVertexLength^2) + (edge . spherePositionToVertex)^2
    			// . denotes dot product
    
    			// Edge (p0, p1):
    			XMVECTOR edge = p1 - p0;
    			XMVECTOR spherePositionToVertex = p0 - position;
    			float edgeLengthSquared = XMVectorGetX(XMVector3Length(edge));
    			edgeLengthSquared *= edgeLengthSquared;
    			float edgeDotVelocity = XMVectorGetX(XMVector3Dot(edge, velocity));
    			float edgeDotSpherePositionToVertex = XMVectorGetX(XMVector3Dot(edge, spherePositionToVertex));
    			float spherePositionToVertexLengthSquared = XMVectorGetX(XMVector3Length(spherePositionToVertex));
    			spherePositionToVertexLengthSquared = spherePositionToVertexLengthSquared * spherePositionToVertexLengthSquared;
    
    			// Equation parameters
    			a = edgeLengthSquared * -velocityLengthSquared + (edgeDotVelocity * edgeDotVelocity);
    			b = edgeLengthSquared * (2.0f * XMVectorGetX(XMVector3Dot(velocity, spherePositionToVertex))) - (2.0f * edgeDotVelocity * edgeDotSpherePositionToVertex);
    			c = edgeLengthSquared * (1.0f - spherePositionToVertexLengthSquared) + (edgeDotSpherePositionToVertex * edgeDotSpherePositionToVertex);
    
    			// We start by finding if the swept sphere collides with the edges "infinite line"
    			if (getLowestRoot(a,b,c, t, &newT)) {
    				// Now we check to see if the collision happened between the two vertices that make up this edge
    				// We can calculate where on the line the collision happens by doing this:
    				// f = (edge . velocity)newT - (edge . spherePositionToVertex) / edgeLength^2
    				// if f is between 0 and 1, then we know the collision happened between p0 and p1
    				// If the collision happened at p0, the f = 0, if the collision happened at p1 then f = 1
    				float f = (edgeDotVelocity * newT - edgeDotSpherePositionToVertex) / edgeLengthSquared;
    				if (f >= 0.0f && f <= 1.0f) {
    					// If the collision with the edge happened, we set the results
    					t = newT;
    					collidingWithTri = true;
    					collisionPoint = p0 + f * edge;
    				}
    			}
    
    			// Edge (p1, p2):
    			edge = p2 - p1;
    			spherePositionToVertex = p1 - position;
    			edgeLengthSquared = XMVectorGetX(XMVector3Length(edge));
    			edgeLengthSquared = edgeLengthSquared * edgeLengthSquared;
    			edgeDotVelocity = XMVectorGetX(XMVector3Dot(edge, cP.e_Velocity));
    			edgeDotSpherePositionToVertex = XMVectorGetX(XMVector3Dot(edge, spherePositionToVertex));
    			spherePositionToVertexLengthSquared = XMVectorGetX(XMVector3Length(spherePositionToVertex));
    			spherePositionToVertexLengthSquared = spherePositionToVertexLengthSquared * spherePositionToVertexLengthSquared;
    
    			a = edgeLengthSquared * -velocityLengthSquared + (edgeDotVelocity * edgeDotVelocity);
    			b = edgeLengthSquared * (2.0f * XMVectorGetX(XMVector3Dot(velocity, spherePositionToVertex))) - (2.0f * edgeDotVelocity * edgeDotSpherePositionToVertex);
    			c = edgeLengthSquared * (1.0f - spherePositionToVertexLengthSquared) + (edgeDotSpherePositionToVertex * edgeDotSpherePositionToVertex);
    
    			if (getLowestRoot(a,b,c, t, &newT)) {
    				float f = (edgeDotVelocity * newT - edgeDotSpherePositionToVertex) / edgeLengthSquared;
    				if (f >= 0.0f && f <= 1.0f) {
    					t = newT;
    					collidingWithTri = true;
    					collisionPoint = p1 + f * edge;
    				}
    			}
    
    			// Edge (p2, p0):
    			edge = p0 - p2;
    			spherePositionToVertex = p2 - position;
    			edgeLengthSquared = XMVectorGetX(XMVector3Length(edge));
    			edgeLengthSquared = edgeLengthSquared * edgeLengthSquared;
    			edgeDotVelocity = XMVectorGetX(XMVector3Dot(edge, velocity));
    			edgeDotSpherePositionToVertex = XMVectorGetX(XMVector3Dot(edge, spherePositionToVertex));
    			spherePositionToVertexLengthSquared = XMVectorGetX(XMVector3Length(spherePositionToVertex));
    			spherePositionToVertexLengthSquared = spherePositionToVertexLengthSquared * spherePositionToVertexLengthSquared;
    
    			a = edgeLengthSquared * -velocityLengthSquared + (edgeDotVelocity * edgeDotVelocity);
    			b = edgeLengthSquared * (2.0f * XMVectorGetX(XMVector3Dot(velocity, spherePositionToVertex))) - (2.0f * edgeDotVelocity * edgeDotSpherePositionToVertex);
    			c = edgeLengthSquared * (1.0f - spherePositionToVertexLengthSquared) + (edgeDotSpherePositionToVertex * edgeDotSpherePositionToVertex);
    
    			if (getLowestRoot(a,b,c, t, &newT)) {
    				float f = (edgeDotVelocity * newT - edgeDotSpherePositionToVertex) / edgeLengthSquared;
    				if (f >= 0.0f && f <= 1.0f) {
    					t = newT;
    					collidingWithTri = true;
    					collisionPoint = p2 + f * edge;
    				}
    			}
    		}
    
    		// If we have found a collision, we will set the results of the collision here
    		if (collidingWithTri == true) 
    		{
    			// We find the distance to the collision using the time variable (t) times the length of the velocity vector
    			float distToCollision = t * XMVectorGetX(XMVector3Length(velocity));
    
    			// Now we check if this is the first triangle that has been collided with OR it is 
    			// the closest triangle yet that was collided with
    			if (cP.foundCollision == false || distToCollision < cP.nearestDistance) {
    
    				// Collision response information (used for "sliding")
    				cP.nearestDistance = distToCollision;
    				cP.intersectionPoint = collisionPoint;
    
    				// Make sure this is set to true if we've made it this far
    				cP.foundCollision = true;
    				return true;
    			}			
    		}
    	}
    	return false;
    }

##The Helper Functions##

These are the two helper functions. The first one finds if a point in a triangles plane is actually inside the triangle, while the second one solves the quadratic equation and returns it's lowest root. The first was taken from my lesson on picking in direct3d 11, and the second was taken directly from Kaspers paper which i mentioned a couple times before now.

    bool checkPointInTriangle(const XMVECTOR& point, const XMVECTOR& triV1,const XMVECTOR& triV2, const XMVECTOR& triV3)
    {
    	XMVECTOR cp1 = XMVector3Cross((triV3 - triV2), (point - triV2));
    	XMVECTOR cp2 = XMVector3Cross((triV3 - triV2), (triV1 - triV2));
    	if(XMVectorGetX(XMVector3Dot(cp1, cp2)) >= 0)
    	{
    		cp1 = XMVector3Cross((triV3 - triV1), (point - triV1));
    		cp2 = XMVector3Cross((triV3 - triV1), (triV2 - triV1));
    		if(XMVectorGetX(XMVector3Dot(cp1, cp2)) >= 0)
    		{
    			cp1 = XMVector3Cross((triV2 - triV1), (point - triV1));
    			cp2 = XMVector3Cross((triV2 - triV1), (triV3 - triV1));
    			if(XMVectorGetX(XMVector3Dot(cp1, cp2)) >= 0)
    			{
    				return true;
    			}
    		}
    	}
    	return false;
    }
    
    // This function solves the quadratic eqation "At^2 + Bt + C = 0" and is found in Kasper Fauerby's paper on collision detection and response
    bool getLowestRoot(float a, float b, float c, float maxR, float* root) 
    {
    	// Check if a solution exists
    	float determinant = b*b - 4.0f*a*c;
    	// If determinant is negative it means no solutions.
    	if (determinant < 0.0f) return false;
    	// calculate the two roots: (if determinant == 0 then
    	// x1==x2 but lets disregard that slight optimization)
    	float sqrtD = sqrt(determinant);
    	float r1 = (-b - sqrtD) / (2*a);
    	float r2 = (-b + sqrtD) / (2*a);
    	// Sort so x1 <= x2
    	if (r1 > r2) {
    		float temp = r2;
    		r2 = r1;
    		r1 = temp;
    	}
    	// Get lowest root:
    	if (r1 > 0 && r1 < maxR) {
    		*root = r1;
    		return true;
    	}
    	// It is possible that we want x2 - this can happen
    	// if x1 < 0
    	if (r2 > 0 && r2 < maxR) {
    		*root = r2;
    		return true;
    	}
    
    	// No (valid) solutions
    	return false;
    }

##The UpdateCamera() Function##

We have changed our camera from a from a free look camera, back to a first person camera.

Then we create a CollisionPacket object called cameraCP, and fill the appropriate members.

Next we call the CollisionSlide() function to find our cameras new position after the possibility of colliding with the world.

Finally you can see how we commented out the lines that changed our camera before, since we have put those together to create the velocity vector we put in cameraCP.

    void UpdateCamera()
    {
    	camRotationMatrix = XMMatrixRotationRollPitchYaw(camPitch, camYaw, 0);
    	camTarget = XMVector3TransformCoord(DefaultForward, camRotationMatrix );
    	camTarget = XMVector3Normalize(camTarget);
    
    	/************************************New Stuff****************************************************/
    	// First-Person Camera
    	XMMATRIX RotateYTempMatrix;
    	RotateYTempMatrix = XMMatrixRotationY(camYaw);
    	camRight = XMVector3TransformCoord(DefaultRight, RotateYTempMatrix);
    	camUp = XMVector3TransformCoord(camUp, RotateYTempMatrix);
    	camForward = XMVector3TransformCoord(DefaultForward, RotateYTempMatrix);
    
    	/*
    	// Free-Look Camera
    	camRight = XMVector3TransformCoord(DefaultRight, camRotationMatrix);
    	camForward = XMVector3TransformCoord(DefaultForward, camRotationMatrix);
    	camUp = XMVector3Cross(camForward, camRight);
    	*/
    
    	CollisionPacket cameraCP;
    	cameraCP.ellipsoidSpace = XMVectorSet(1.0f, 3.0f, 1.0f, 0.0f);
    	cameraCP.w_Position = camPosition;
    	cameraCP.w_Velocity = (moveLeftRight*camRight)+(moveBackForward*camForward);
    
    	camPosition = CollisionSlide(cameraCP,
    		collidableGeometryPositions,
    		collidableGeometryIndices);
    
    	/*camPosition += moveLeftRight*camRight;
    	camPosition += moveBackForward*camForward;*/
    	/*************************************************************************************************/
    
    	moveLeftRight = 0.0f;
    	moveBackForward = 0.0f;
    
    	camTarget = camPosition + camTarget;	
    
    	camView = XMMatrixLookAtLH( camPosition, camTarget, camUp );
    }

We are now in the InitScene() function, right after we load in our terrain.

This is where we put the terrain into the "polygon soup". I know i mentioned above, but we have to make sure that we transform the geometry sent to the polygon soup BEFORE we actually store it in with the geometry stuff. So what we do here is first transform your terrain, by making it bigger, then translating it so that the camera lands in a comfortable spot, hehe. If you decide you need to transform geometry that has already been sent to the polygon soup, you will have to update the polygon soup with the new information, which means keeping track of its vertex offset in the collidableGeometryPositions array.

In case there is other geometry already in the polygon soup, we need to make sure we set the indices for the geometry we want to store in it to the correct values. This means creating an vertex offset variable, which is the index value of the first loaded vertex of this geometry we want to store. Then we will add the vertex offset to the indices as we store them in the index array for the polygon soup.

You can see how we are translating each vertex position before we actually push them back. When drawing our geometry, we do this part in the vertex shader.

    	// Since our terrain will not be transformed throughout our scene, we will set the our groundWorlds
    	// world matrix here so that when we put the terrains positions in the "polygon soup", they will
    	// already be transformed to world space
    	groundWorld = XMMatrixIdentity();
    	Scale = XMMatrixScaling( 10.0f, 10.0f, 10.0f );
    	Translation = XMMatrixTranslation( -520.0f, -10.0f, -1020.0f );
    	groundWorld = Scale * Translation;
    
    	// Store the terrains vertex positions and indices in the
    	// polygon soup that we will check for collisions with
    	// We can store ALL static (non-changing) geometry in here that we want to check for collisions with
    	int vertexOffset = collidableGeometryPositions.size();	// Vertex offset (each "mesh" will be added to the end of the positions array)
    
    	// Temp arrays because we need to store the geometry in world space
    	XMVECTOR tempVertexPosVec;
    	XMFLOAT3 tempVertF3;
    
    	// Push back vertex positions to the polygon soup
    	for(int i = 0; i < v.size(); i++)
    	{
    		tempVertexPosVec = XMLoadFloat3(&v[i].pos);
    		tempVertexPosVec = XMVector3TransformCoord(tempVertexPosVec, groundWorld);
    		XMStoreFloat3(&tempVertF3, tempVertexPosVec);
    		collidableGeometryPositions.push_back(tempVertF3);
    	}
    
    	// Push back indices for polygon soup. We need to make sure we are
    	// pushing back the indices "on top" of the previous pushed back
    	// objects vertex positions, hence "+ vertexOffset" (This is the
    	// first object we are putting in here, so it really doesn't
    	// matter right now, but I just wanted to show you how to do it
    	for(int i = 0; i < indices.size(); i++)
    	{
    		collidableGeometryIndices.push_back(indices[i] + vertexOffset);
    	}

In the last lesson, which this lesson builds directly off of, we transformed our terrain geometry in the update scene function. Although we never actually change the transformation matrix for our terrain in the last lesson, we should still take it out since theres no need to be doing this extra bit every frame. We have already defined our terrains world space matrix in the initialization state above.

    void UpdateScene(double time)
    {
    }

Improvements can be made, so if you see anything that needs to be changed, i would very much appreciate a comment about it!

##Exercise:##

1. Try to only impliment gravity when the sphere is on a triangle with a steep slope, or if it's free falling.

2. Use this collision detection and response algorithm on an object other than the camera.

3. Change the function of the collision response to "bounce" off the sliding plane instead of "slide" across it

4. Add a jump ability for when you press the space bar

Here's the final code:

main.cpp
    //Include and link appropriate libraries and headers//
    #pragma comment(lib, "d3d11.lib")
    #pragma comment(lib, "d3dx11.lib")
    #pragma comment(lib, "d3dx10.lib")
    #pragma comment (lib, "D3D10_1.lib")
    #pragma comment (lib, "DXGI.lib")
    #pragma comment (lib, "D2D1.lib")
    #pragma comment (lib, "dwrite.lib")
    #pragma comment (lib, "dinput8.lib")
    #pragma comment (lib, "dxguid.lib")
    
    #include <windows.h>
    #include <d3d11.h>
    #include <d3dx11.h>
    #include <d3dx10.h>
    #include <xnamath.h>
    #include <D3D10_1.h>
    #include <DXGI.h>
    #include <D2D1.h>
    #include <sstream>
    #include <dwrite.h>
    #include <dinput.h>
    #include <vector>
    
    //Global Declarations - Interfaces//
    IDXGISwapChain* SwapChain;
    ID3D11Device* d3d11Device;
    ID3D11DeviceContext* d3d11DevCon;
    ID3D11RenderTargetView* renderTargetView;
    ID3D11Buffer* squareIndexBuffer;
    ID3D11DepthStencilView* depthStencilView;
    ID3D11Texture2D* depthStencilBuffer;
    ID3D11Buffer* squareVertBuffer;
    ID3D11VertexShader* VS;
    ID3D11PixelShader* PS;
    ID3D11PixelShader* D2D_PS;
    ID3D10Blob* D2D_PS_Buffer;
    ID3D10Blob* VS_Buffer;
    ID3D10Blob* PS_Buffer;
    ID3D11InputLayout* vertLayout;
    ID3D11Buffer* cbPerObjectBuffer;
    ID3D11BlendState* Transparency;
    ID3D11RasterizerState* CCWcullMode;
    ID3D11RasterizerState* CWcullMode;
    ID3D11ShaderResourceView* CubesTexture;
    ID3D11SamplerState* CubesTexSamplerState;
    ID3D11Buffer* cbPerFrameBuffer;
    
    ID3D10Device1 *d3d101Device;	
    IDXGIKeyedMutex *keyedMutex11;
    IDXGIKeyedMutex *keyedMutex10;	
    ID2D1RenderTarget *D2DRenderTarget;	
    ID2D1SolidColorBrush *Brush;
    ID3D11Texture2D *BackBuffer11;
    ID3D11Texture2D *sharedTex11;	
    ID3D11Buffer *d2dVertBuffer;
    ID3D11Buffer *d2dIndexBuffer;
    ID3D11ShaderResourceView *d2dTexture;
    IDWriteFactory *DWriteFactory;
    IDWriteTextFormat *TextFormat;
    
    IDirectInputDevice8* DIKeyboard;
    IDirectInputDevice8* DIMouse;
    
    std::wstring printText;
    
    //Global Declarations - Others//
    LPCTSTR WndClassName = L"firstwindow";
    HWND hwnd = NULL;
    HRESULT hr;
    
    int Width  = 800;
    int Height = 600;
    
    DIMOUSESTATE mouseLastState;
    LPDIRECTINPUT8 DirectInput;
    
    float rotx = 0;
    float rotz = 0;
    float scaleX = 1.0f;
    float scaleY = 1.0f;
    
    XMMATRIX Rotationx;
    XMMATRIX Rotationz;
    
    XMMATRIX WVP;
    XMMATRIX cube1World;
    XMMATRIX cube2World;
    XMMATRIX camView;
    XMMATRIX camProjection;
    
    XMMATRIX d2dWorld;
    
    XMVECTOR camPosition;
    XMVECTOR camTarget;
    XMVECTOR camUp;
    XMVECTOR DefaultForward = XMVectorSet(0.0f,0.0f,1.0f, 0.0f);
    XMVECTOR DefaultRight = XMVectorSet(1.0f,0.0f,0.0f, 0.0f);
    XMVECTOR camForward = XMVectorSet(0.0f,0.0f,1.0f, 0.0f);
    XMVECTOR camRight = XMVectorSet(1.0f,0.0f,0.0f, 0.0f);
    
    XMMATRIX camRotationMatrix;
    XMMATRIX groundWorld;
    
    float moveLeftRight = 0.0f;
    float moveBackForward = 0.0f;
    
    float camYaw = 0.0f;
    float camPitch = 0.0f;
    
    XMMATRIX Rotation;
    XMMATRIX Scale;
    XMMATRIX Translation;
    float rot = 0.01f;
    
    double countsPerSecond = 0.0;
    __int64 CounterStart = 0;
    
    int frameCount = 0;
    int fps = 0;
    
    __int64 frameTimeOld = 0;
    double frameTime;
    
    //Function Prototypes//
    bool InitializeDirect3d11App(HINSTANCE hInstance);
    void CleanUp();
    bool InitScene();
    void DrawScene();
    bool InitD2D_D3D101_DWrite(IDXGIAdapter1 *Adapter);
    void InitD2DScreenTexture();
    void UpdateScene(double time);
    
    void UpdateCamera();
    
    void RenderText(std::wstring text, int inInt);
    
    void StartTimer();
    double GetTime();
    double GetFrameTime();
    
    bool InitializeWindow(HINSTANCE hInstance,
    	int ShowWnd,
    	int width, int height,
    	bool windowed);
    int messageloop();
    
    bool InitDirectInput(HINSTANCE hInstance);
    void DetectInput(double time);
    
    /************************************New Stuff****************************************************/
    // This is the scale of our scene, which we will use to find "a very small distance"
    // If this is set too small, you will notice the camera "stick" to the geometry once in a while
    // Just play with it and use whatever works best for your application
    const float unitsPerMeter = 100.0f;
    
    // The gravity's velocity vector
    XMVECTOR gravity = XMVectorSet(0.0f, -0.2f, 0.0f, 0.0f);
    
    // Polygon Soup
    std::vector<XMFLOAT3> collidableGeometryPositions;
    std::vector<DWORD> collidableGeometryIndices;
    
    struct CollisionPacket{
    	// Information about ellipsoid (in world space)
    	XMVECTOR ellipsoidSpace;
    	XMVECTOR w_Position;
    	XMVECTOR w_Velocity;
    
    	// Information about ellipsoid (in ellipsoid space)
    	XMVECTOR e_Position;
    	XMVECTOR e_Velocity;
    	XMVECTOR e_normalizedVelocity;
    
    	// Collision Information
    	bool foundCollision;
    	float nearestDistance;
    	XMVECTOR intersectionPoint;
    	int collisionRecursionDepth;
    };
    
    // Collision Detection and Response Function Prototypes
    XMVECTOR CollisionSlide(CollisionPacket& cP,			// Pointer to a CollisionPacket object (expects ellipsoidSpace, w_Position and w_Velocity to be filled)
    	std::vector<XMFLOAT3>& vertPos,						// An array holding the polygon soup vertex positions
    	std::vector<DWORD>& indices);						// An array holding the polygon soup indices (triangles)
    
    XMVECTOR CollideWithWorld(CollisionPacket& cP,			// Same arguments as the above function
    	std::vector<XMFLOAT3>& vertPos,
    	std::vector<DWORD>& indices);
    
    bool SphereCollidingWithTriangle(CollisionPacket& cP,	// Pointer to a CollisionPacket object	
    	XMVECTOR &p0,										// First vertex position of triangle
    	XMVECTOR &p1,										// Second vertex position of triangle
    	XMVECTOR &p2,										// Third vertex position of triangle 
    	XMVECTOR &triNormal);								// Triangle's Normal
    
    // Checks if a point (inside the triangle's plane) is inside the triangle
    bool checkPointInTriangle(const XMVECTOR& point, const XMVECTOR& triV1,const XMVECTOR& triV2, const XMVECTOR& triV3);
    
    // Solves the quadratic eqation, and returns the lowest root if equation is solvable, returns false if not solvable
    bool getLowestRoot(float a, float b, float c, float maxR, float* root);
    /*************************************************************************************************/
    
    int NumFaces = 0;
    int NumVertices = 0;
    
    struct HeightMapInfo{		// Heightmap structure
    	int terrainWidth;		// Width of heightmap
    	int terrainHeight;		// Height (Length) of heightmap
    	XMFLOAT3 *heightMap;	// Array to store terrain's vertex positions
    };
    
    bool HeightMapLoad(char* filename, HeightMapInfo &hminfo);
    
    LRESULT CALLBACK WndProc(HWND hWnd,
    	UINT msg,
    	WPARAM wParam,
    	LPARAM lParam);
    
    //Create effects constant buffer's structure//
    struct cbPerObject
    {
    	XMMATRIX  WVP;
    	XMMATRIX World;
    };
    
    cbPerObject cbPerObj;
    
    struct Light
    {
    	Light()
    	{
    		ZeroMemory(this, sizeof(Light));
    	}
    	XMFLOAT3 dir;
    	float pad;
    	XMFLOAT4 ambient;
    	XMFLOAT4 diffuse;
    };
    
    Light light;
    
    struct cbPerFrame
    {
    	Light  light;
    };
    
    cbPerFrame constbuffPerFrame;
    
    struct Vertex	//Overloaded Vertex Structure
    {
    	Vertex(){}
    	Vertex(float x, float y, float z,
    		float u, float v,
    		float nx, float ny, float nz)
    		: pos(x,y,z), texCoord(u, v), normal(nx, ny, nz){}
    
    	XMFLOAT3 pos;
    	XMFLOAT2 texCoord;
    	XMFLOAT3 normal;
    };
    
    D3D11_INPUT_ELEMENT_DESC layout[] =
    {
    	{ "POSITION", 0, DXGI_FORMAT_R32G32B32_FLOAT, 0, 0, D3D11_INPUT_PER_VERTEX_DATA, 0 },  
    	{ "TEXCOORD", 0, DXGI_FORMAT_R32G32_FLOAT, 0, 12, D3D11_INPUT_PER_VERTEX_DATA, 0 },  
    	{ "NORMAL",	 0, DXGI_FORMAT_R32G32B32_FLOAT,    0, 20, D3D11_INPUT_PER_VERTEX_DATA, 0}
    };
    UINT numElements = ARRAYSIZE(layout);
    
    int WINAPI WinMain(HINSTANCE hInstance,	//Main windows function
    	HINSTANCE hPrevInstance, 
    	LPSTR lpCmdLine,
    	int nShowCmd)
    {
    
    	if(!InitializeWindow(hInstance, nShowCmd, Width, Height, true))
    	{
    		MessageBox(0, L"Window Initialization - Failed",
    			L"Error", MB_OK);
    		return 0;
    	}
    
    	if(!InitializeDirect3d11App(hInstance))	//Initialize Direct3D
    	{
    		MessageBox(0, L"Direct3D Initialization - Failed",
    			L"Error", MB_OK);
    		return 0;
    	}
    
    	if(!InitScene())	//Initialize our scene
    	{
    		MessageBox(0, L"Scene Initialization - Failed",
    			L"Error", MB_OK);
    		return 0;
    	}
    
    	if(!InitDirectInput(hInstance))
    	{
    		MessageBox(0, L"Direct Input Initialization - Failed",
    			L"Error", MB_OK);
    		return 0;
    	}
    
    	messageloop();
    
    	CleanUp();    
    
    	return 0;
    }
    
    bool InitializeWindow(HINSTANCE hInstance,
    	int ShowWnd,
    	int width, int height,
    	bool windowed)
    {
    	typedef struct _WNDCLASS {
    		UINT cbSize;
    		UINT style;
    		WNDPROC lpfnWndProc;
    		int cbClsExtra;
    		int cbWndExtra;
    		HANDLE hInstance;
    		HICON hIcon;
    		HCURSOR hCursor;
    		HBRUSH hbrBackground;
    		LPCTSTR lpszMenuName;
    		LPCTSTR lpszClassName;
    	} WNDCLASS;
    
    	WNDCLASSEX wc;
    
    	wc.cbSize = sizeof(WNDCLASSEX);
    	wc.style = CS_HREDRAW | CS_VREDRAW;
    	wc.lpfnWndProc = WndProc;
    	wc.cbClsExtra = NULL;
    	wc.cbWndExtra = NULL;
    	wc.hInstance = hInstance;
    	wc.hIcon = LoadIcon(NULL, IDI_APPLICATION);
    	wc.hCursor = LoadCursor(NULL, IDC_ARROW);
    	wc.hbrBackground = (HBRUSH)(COLOR_WINDOW + 1);
    	wc.lpszMenuName = NULL;
    	wc.lpszClassName = WndClassName;
    	wc.hIconSm = LoadIcon(NULL, IDI_APPLICATION);
    
    	if (!RegisterClassEx(&wc))
    	{
    		MessageBox(NULL, L"Error registering class",	
    			L"Error", MB_OK | MB_ICONERROR);
    		return 1;
    	}
    
    	hwnd = CreateWindowEx(
    		NULL,
    		WndClassName,
    		L"Lesson 30 - Sliding Camera Collision Detection",
    		WS_OVERLAPPEDWINDOW,
    		CW_USEDEFAULT, CW_USEDEFAULT,
    		width, height,
    		NULL,
    		NULL,
    		hInstance,
    		NULL
    		);
    
    	if (!hwnd)
    	{
    		MessageBox(NULL, L"Error creating window",
    			L"Error", MB_OK | MB_ICONERROR);
    		return 1;
    	}
    
    	ShowWindow(hwnd, ShowWnd);
    	UpdateWindow(hwnd);
    
    	return true;
    }
    
    bool InitializeDirect3d11App(HINSTANCE hInstance)
    {	
    	//Describe our SwapChain Buffer
    	DXGI_MODE_DESC bufferDesc;
    
    	ZeroMemory(&bufferDesc, sizeof(DXGI_MODE_DESC));
    
    	bufferDesc.Width = Width;
    	bufferDesc.Height = Height;
    	bufferDesc.RefreshRate.Numerator = 60;
    	bufferDesc.RefreshRate.Denominator = 1;
    	bufferDesc.Format = DXGI_FORMAT_B8G8R8A8_UNORM;
    	bufferDesc.ScanlineOrdering = DXGI_MODE_SCANLINE_ORDER_UNSPECIFIED;
    	bufferDesc.Scaling = DXGI_MODE_SCALING_UNSPECIFIED;
    
    	//Describe our SwapChain
    	DXGI_SWAP_CHAIN_DESC swapChainDesc; 
    
    	ZeroMemory(&swapChainDesc, sizeof(DXGI_SWAP_CHAIN_DESC));
    
    	swapChainDesc.BufferDesc = bufferDesc;
    	swapChainDesc.SampleDesc.Count = 1;
    	swapChainDesc.SampleDesc.Quality = 0;
    	swapChainDesc.BufferUsage = DXGI_USAGE_RENDER_TARGET_OUTPUT;
    	swapChainDesc.BufferCount = 1;
    	swapChainDesc.OutputWindow = hwnd; 
    	///////////////**************new**************////////////////////
    	swapChainDesc.Windowed = true; 
    	///////////////**************new**************////////////////////
    	swapChainDesc.SwapEffect = DXGI_SWAP_EFFECT_DISCARD;
    
    	// Create DXGI factory to enumerate adapters///////////////////////////////////////////////////////////////////////////
    	IDXGIFactory1 *DXGIFactory;
    
    	HRESULT hr = CreateDXGIFactory1(__uuidof(IDXGIFactory1), (void**)&DXGIFactory);	
    
    	// Use the first adapter	
    	IDXGIAdapter1 *Adapter;
    
    	hr = DXGIFactory->EnumAdapters1(0, &Adapter);
    
    	DXGIFactory->Release();	
    
    	//Create our Direct3D 11 Device and SwapChain//////////////////////////////////////////////////////////////////////////
    	hr = D3D11CreateDeviceAndSwapChain(Adapter, D3D_DRIVER_TYPE_UNKNOWN, NULL, D3D11_CREATE_DEVICE_BGRA_SUPPORT,
    		NULL, NULL,	D3D11_SDK_VERSION, &swapChainDesc, &SwapChain, &d3d11Device, NULL, &d3d11DevCon);
    
    	//Initialize Direct2D, Direct3D 10.1, DirectWrite
    	InitD2D_D3D101_DWrite(Adapter);
    
    	//Release the Adapter interface
    	Adapter->Release();
    
    	//Create our BackBuffer and Render Target
    	hr = SwapChain->GetBuffer( 0, __uuidof( ID3D11Texture2D ), (void**)&BackBuffer11 );
    	hr = d3d11Device->CreateRenderTargetView( BackBuffer11, NULL, &renderTargetView );
    
    	//Describe our Depth/Stencil Buffer
    	D3D11_TEXTURE2D_DESC depthStencilDesc;
    
    	depthStencilDesc.Width     = Width;
    	depthStencilDesc.Height    = Height;
    	depthStencilDesc.MipLevels = 1;
    	depthStencilDesc.ArraySize = 1;
    	depthStencilDesc.Format    = DXGI_FORMAT_D24_UNORM_S8_UINT;
    	depthStencilDesc.SampleDesc.Count   = 1;
    	depthStencilDesc.SampleDesc.Quality = 0;
    	depthStencilDesc.Usage          = D3D11_USAGE_DEFAULT;
    	depthStencilDesc.BindFlags      = D3D11_BIND_DEPTH_STENCIL;
    	depthStencilDesc.CPUAccessFlags = 0; 
    	depthStencilDesc.MiscFlags      = 0;
    
    	//Create the Depth/Stencil View
    	d3d11Device->CreateTexture2D(&depthStencilDesc, NULL, &depthStencilBuffer);
    	d3d11Device->CreateDepthStencilView(depthStencilBuffer, NULL, &depthStencilView);
    
    	return true;
    }
    
    bool InitD2D_D3D101_DWrite(IDXGIAdapter1 *Adapter)
    {
    	//Create our Direc3D 10.1 Device///////////////////////////////////////////////////////////////////////////////////////
    	hr = D3D10CreateDevice1(Adapter, D3D10_DRIVER_TYPE_HARDWARE, NULL,D3D10_CREATE_DEVICE_BGRA_SUPPORT,
    		D3D10_FEATURE_LEVEL_9_3, D3D10_1_SDK_VERSION, &d3d101Device	);	
    
    	//Create Shared Texture that Direct3D 10.1 will render on//////////////////////////////////////////////////////////////
    	D3D11_TEXTURE2D_DESC sharedTexDesc;	
    
    	ZeroMemory(&sharedTexDesc, sizeof(sharedTexDesc));
    
    	sharedTexDesc.Width = Width;
    	sharedTexDesc.Height = Height;	
    	sharedTexDesc.Format = DXGI_FORMAT_B8G8R8A8_UNORM;
    	sharedTexDesc.MipLevels = 1;	
    	sharedTexDesc.ArraySize = 1;
    	sharedTexDesc.SampleDesc.Count = 1;
    	sharedTexDesc.Usage = D3D11_USAGE_DEFAULT;
    	sharedTexDesc.BindFlags = D3D11_BIND_SHADER_RESOURCE | D3D11_BIND_RENDER_TARGET;	
    	sharedTexDesc.MiscFlags = D3D11_RESOURCE_MISC_SHARED_KEYEDMUTEX;	
    
    	hr = d3d11Device->CreateTexture2D(&sharedTexDesc, NULL, &sharedTex11);	
    
    	// Get the keyed mutex for the shared texture (for D3D11)///////////////////////////////////////////////////////////////
    	hr = sharedTex11->QueryInterface(__uuidof(IDXGIKeyedMutex), (void**)&keyedMutex11);	
    
    	// Get the shared handle needed to open the shared texture in D3D10.1///////////////////////////////////////////////////
    	IDXGIResource *sharedResource10;
    	HANDLE sharedHandle10;	
    
    	hr = sharedTex11->QueryInterface(__uuidof(IDXGIResource), (void**)&sharedResource10);
    
    	hr = sharedResource10->GetSharedHandle(&sharedHandle10);	
    
    	sharedResource10->Release();
    
    	// Open the surface for the shared texture in D3D10.1///////////////////////////////////////////////////////////////////
    	IDXGISurface1 *sharedSurface10;	
    
    	hr = d3d101Device->OpenSharedResource(sharedHandle10, __uuidof(IDXGISurface1), (void**)(&sharedSurface10));
    
    	hr = sharedSurface10->QueryInterface(__uuidof(IDXGIKeyedMutex), (void**)&keyedMutex10);	
    
    	// Create D2D factory///////////////////////////////////////////////////////////////////////////////////////////////////
    	ID2D1Factory *D2DFactory;	
    	hr = D2D1CreateFactory(D2D1_FACTORY_TYPE_SINGLE_THREADED, __uuidof(ID2D1Factory), (void**)&D2DFactory);	
    
    	D2D1_RENDER_TARGET_PROPERTIES renderTargetProperties;
    
    	ZeroMemory(&renderTargetProperties, sizeof(renderTargetProperties));
    
    	renderTargetProperties.type = D2D1_RENDER_TARGET_TYPE_HARDWARE;
    	renderTargetProperties.pixelFormat = D2D1::PixelFormat(DXGI_FORMAT_UNKNOWN, D2D1_ALPHA_MODE_PREMULTIPLIED);	
    
    	hr = D2DFactory->CreateDxgiSurfaceRenderTarget(sharedSurface10, &renderTargetProperties, &D2DRenderTarget);
    
    	sharedSurface10->Release();
    	D2DFactory->Release();	
    
    	// Create a solid color brush to draw something with		
    	hr = D2DRenderTarget->CreateSolidColorBrush(D2D1::ColorF(1.0f, 1.0f, 1.0f, 1.0f), &Brush);
    
    	//DirectWrite///////////////////////////////////////////////////////////////////////////////////////////////////////////
    	hr = DWriteCreateFactory(DWRITE_FACTORY_TYPE_SHARED, __uuidof(IDWriteFactory),
    		reinterpret_cast<IUnknown**>(&DWriteFactory));
    
    	hr = DWriteFactory->CreateTextFormat(
    		L"Script",
    		NULL,
    		DWRITE_FONT_WEIGHT_REGULAR,
    		DWRITE_FONT_STYLE_NORMAL,
    		DWRITE_FONT_STRETCH_NORMAL,
    		24.0f,
    		L"en-us",
    		&TextFormat
    		);
    
    	hr = TextFormat->SetTextAlignment(DWRITE_TEXT_ALIGNMENT_LEADING);
    	hr = TextFormat->SetParagraphAlignment(DWRITE_PARAGRAPH_ALIGNMENT_NEAR);
    
    	d3d101Device->IASetPrimitiveTopology(D3D10_PRIMITIVE_TOPOLOGY_POINTLIST);	
    	return true;
    }
    
    bool HeightMapLoad(char* filename, HeightMapInfo &hminfo)
    {
    	FILE *filePtr;							// Point to the current position in the file
    	BITMAPFILEHEADER bitmapFileHeader;		// Structure which stores information about file
    	BITMAPINFOHEADER bitmapInfoHeader;		// Structure which stores information about image
    	int imageSize, index;
    	unsigned char height;
    
    	// Open the file
    	filePtr = fopen(filename,"rb");
    	if (filePtr == NULL)
    		return 0;
    
    	// Read bitmaps header
    	fread(&bitmapFileHeader, sizeof(BITMAPFILEHEADER), 1,filePtr);
    
    	// Read the info header
    	fread(&bitmapInfoHeader, sizeof(BITMAPINFOHEADER), 1, filePtr);
    
    	// Get the width and height (width and length) of the image
    	hminfo.terrainWidth = bitmapInfoHeader.biWidth;
    	hminfo.terrainHeight = bitmapInfoHeader.biHeight;
    
    	// Size of the image in bytes. the 3 represents RBG (byte, byte, byte) for each pixel
    	imageSize = hminfo.terrainWidth * hminfo.terrainHeight * 3;
    
    	// Initialize the array which stores the image data
    	unsigned char* bitmapImage = new unsigned char[imageSize];
    
    	// Set the file pointer to the beginning of the image data
    	fseek(filePtr, bitmapFileHeader.bfOffBits, SEEK_SET);
    
    	// Store image data in bitmapImage
    	fread(bitmapImage, 1, imageSize, filePtr);
    
    	// Close file
    	fclose(filePtr);
    
    	// Initialize the heightMap array (stores the vertices of our terrain)
    	hminfo.heightMap = new XMFLOAT3[hminfo.terrainWidth * hminfo.terrainHeight];
    
    	// We use a greyscale image, so all 3 rgb values are the same, but we only need one for the height
    	// So we use this counter to skip the next two components in the image data (we read R, then skip BG)
    	int k=0;
    
    	// We divide the height by this number to "water down" the terrains height, otherwise the terrain will
    	// appear to be "spikey" and not so smooth.
    	float heightFactor = 10.0f;
    
    	// Read the image data into our heightMap array
    	for(int j=0; j< hminfo.terrainHeight; j++)
    	{
    		for(int i=0; i< hminfo.terrainWidth; i++)
    		{
    			height = bitmapImage[k];
    
    			index = ( hminfo.terrainHeight * j) + i;
    
    			hminfo.heightMap[index].x = (float)i;
    			hminfo.heightMap[index].y = (float)height / heightFactor;
    			hminfo.heightMap[index].z = (float)j;
    
    			k+=3;
    		}
    	}
    
    	delete [] bitmapImage;
    	bitmapImage = 0;
    
    	return true;
    }
    
    /************************************New Stuff****************************************************/
    // This is the function we will call when we want to find if an ellipsoid will collide with
    // the world (polygon soup) while traveling along it's velocity vector, and also impliment
    // gravity by doing the collision detection and response algorithm with the gravity's
    // velocity vector. It's kind of like the collision detection and response package
    XMVECTOR CollisionSlide(CollisionPacket& cP,
    	std::vector<XMFLOAT3>& vertPos,
    	std::vector<DWORD>& indices)
    {
    	// Transform velocity vector to the ellipsoid space (e_ denotes ellipsoid space)
    	cP.e_Velocity = cP.w_Velocity/cP.ellipsoidSpace;
    
    	// Transform position vector to the ellipsoid space
    	cP.e_Position = cP.w_Position/cP.ellipsoidSpace;
    
    	// Now we check for a collision with our world, this function will
    	// call itself 5 times at most, or until the velocity vector is
    	// used up (very small (near zero to zero length))
    	cP.collisionRecursionDepth = 0;
    	XMVECTOR finalPosition = CollideWithWorld(cP, vertPos, indices);
    
    	// Add gravity pull:
    	// This is simply adding a new velocity vector in the downward
    	// direction (defined globaly) to pull the ellipsoid down, then doing the
    	// collision check against all the geometry again. The way it is now, the
    	// ellipsoid will "slide" down even the most slightest slope. Consider this
    	// an exercise: only impliment gravity when standing on a very steep slope,
    	// or if you are not standing on anything at all (free fall)
    
    	// To remove gravity uncomment from here .....
    
    	cP.e_Velocity = gravity / cP.ellipsoidSpace;	// We defined gravity in world space, so now we have
    	// to convert it to ellipsoid space
    	cP.e_Position = finalPosition;
    	cP.collisionRecursionDepth = 0;
    	finalPosition = CollideWithWorld(cP, vertPos, indices);
    
    	// ... to here
    
    	// Convert our final position from ellipsoid space to world space
    	finalPosition = finalPosition * cP.ellipsoidSpace;
    
    	// Return our final position!
    	return finalPosition;
    }
    
    // This function impliments the collision detection and collision response
    XMVECTOR CollideWithWorld(CollisionPacket& cP,
    	std::vector<XMFLOAT3>& vertPos,
    	std::vector<DWORD>& indices)
    {
    	// These are based off the unitsPerMeter from above
    	float unitScale = unitsPerMeter / 100.0f;
    	float veryCloseDistance = 0.005f * unitScale;	// This is used to keep the sphere from actually "touching" 
    	// the triangle, as that would cause problems since
    	// each loop it would ALWAYS find a collision instead
    	// of just sliding along the triangle
    
    	// This will stop us from entering an infinite loop, or a very long loop. For example, there are times when the sphere
    	// might actually be pushed slightly into the triangles center, where the recursion will keep repeating and finding a collision
    	// even though the velocity vector does not change (I had serious problems with this part for a couple days... I couldn't
    	// figure out why the ellipsoid would LAUNCH at certain times, but if i set the ellipsoid space to (1,1,1) (a sphere), it would
    	// act normal. Stupid me made a mistake and was returning w_Position here instead of e_Position, so that the world space position
    	// was being multiplied by the ellipsoid space and "launching" it whenever it accidently got pushed into a triangle)
    	if (cP.collisionRecursionDepth > 5)
    		return cP.e_Position;
    
    	// Normalize velocity vector
    	cP.e_normalizedVelocity = XMVector3Normalize(cP.e_Velocity);	
    
    	// Initialize collision packet stuff
    	cP.foundCollision = false;
    	cP.nearestDistance = 0.0f;
    
    	// Loop through each triangle in mesh and check for a collision
    	for(int triCounter = 0; triCounter < indices.size() / 3; triCounter++)
    	{
    		// Get triangle
    		XMVECTOR p0, p1, p2, tempVec;
    		p0 = XMLoadFloat3(&vertPos[indices[3*triCounter]]);
    		p1 = XMLoadFloat3(&vertPos[indices[3*triCounter+1]]);
    		p2 = XMLoadFloat3(&vertPos[indices[3*triCounter+2]]);
    
    		// Put triangle into ellipsoid space
    		p0 = p0/cP.ellipsoidSpace;
    		p1 = p1/cP.ellipsoidSpace;
    		p2 = p2/cP.ellipsoidSpace;
    
    		// Calculate the normal for this triangle
    		XMVECTOR triNormal;
    		triNormal = XMVector3Normalize(XMVector3Cross((p1 - p0),(p2 - p0)));
    
    		// Now we check to see if the sphere is colliding with the current triangle
    		SphereCollidingWithTriangle(cP, p0, p1, p2, triNormal);
    	}
    
    	// If there was no collision, return the position + velocity
    	if (cP.foundCollision == false) {
    		return cP.e_Position + cP.e_Velocity;
    	}
    
    	// If we've made it here, a collision occured
    	// destinationPoint is where the sphere would travel if there was
    	// no collisions, however, at this point, there has a been a collision
    	// detected. We will use this vector to find the new "sliding" vector
    	// based off the plane created from the sphere and collision point
    	XMVECTOR destinationPoint = cP.e_Position + cP.e_Velocity;
    
    	XMVECTOR newPosition = cP.e_Position;	// Just initialize newPosition
    
    	// If the position is further than "veryCloseDistance" from the point
    	// of collision, we will move the sphere along the velocity path until
    	// it "almost" touches the triangle, or point of collision. We do this so
    	// that the next recursion (if there is one) does not detect a collision
    	// with the triangle we just collided with. We don't need to find a collision
    	// with the triangle we just collided with because we will be moving parallel
    	// to it now, and if we were finding the collision with it every recursion
    	// (since it's the closest triangle we would collide with), we would 
    	// finish our 5 recursions (checked above) without ever moving after
    	// touching a triangle, because before the triangle has a chance to move
    	// down the new velocity path (even though it's about parallel with the triangle)
    	// it would find the collision with the triangle, and simply recompute the same
    	// velocity vector it computed the first time. This would happen because of
    	// floating point innacuracy. theoretically, we would not have to worry about this
    	// because after the new velocity vector is created, it SHOULD be perfectly parallel
    	// to the triangle, and we detect that in our code and basically skip triangles
    	// who are perfectly parallel with the velocity vector. But like i said, because
    	// of innacuracy, the new velocity vector might be VERY SLIGHTLY pointed down towards
    	// the triangles plane, which would make us waste a recursion just to recompute the same
    	// velocity vector. Basically, the whole sliding thing works without this, but it's a lot
    	// more "choppy" and "sticky", where you get stuck in random places.
    	if (cP.nearestDistance >= veryCloseDistance)
    	{
    		// Move the new position down velocity vector to ALMOST touch the collision point
    		XMVECTOR V = cP.e_Velocity;
    		V = XMVector3Normalize(V);
    		V = V * (cP.nearestDistance - veryCloseDistance);
    		newPosition = cP.e_Position + V;
    
    		// Adjust polygon intersection point (so sliding
    		// plane will be unaffected by the fact that we
    		// move slightly less than collision tells us)
    		V = XMVector3Normalize(V);
    		cP.intersectionPoint -= veryCloseDistance * V;
    	}
    
    	// This is our sliding plane (point in the plane and plane normal)
    	XMVECTOR slidePlaneOrigin = cP.intersectionPoint;
    	XMVECTOR slidePlaneNormal =	newPosition - cP.intersectionPoint;
    	slidePlaneNormal = XMVector3Normalize(slidePlaneNormal);
    
    	// We will use the sliding plane to compute our new "destination" point
    	// and new velocity vector. To do this, we will need to solve another quadratic
    	// equation (Ax + By + Cz + D = 0), where D is what we call the plane constant,
    	// which we use to find the distance between the sliding plane and our original
    	// destination point (original as up until now, since it's likely that this is
    	// not the first recursion of this function, and the original original destination
    	// has been changed up until now).
    	// First the point in the plane
    	float x = XMVectorGetX(slidePlaneOrigin);
    	float y = XMVectorGetY(slidePlaneOrigin);
    	float z = XMVectorGetZ(slidePlaneOrigin);
    
    	// Next the planes normal
    	float A = XMVectorGetX(slidePlaneNormal);
    	float B = XMVectorGetY(slidePlaneNormal);
    	float C = XMVectorGetZ(slidePlaneNormal);
    	float D = -((A*x) + (B*y) + (C*z));
    
    	// To keep the variable names clear, we will rename D to planeConstant
    	float planeConstant = D;
    
    	// Get the distance between sliding plane and destination point
    	float signedDistFromDestPointToSlidingPlane = XMVectorGetX(XMVector3Dot(destinationPoint, slidePlaneNormal)) + planeConstant;
    
    	// Now we calculate the new destination point. To get the new destination point, we will subtract
    	// the distance from the plane to the original destination point (down the planes normal) from the
    	// original destination point. It's easier to picture this in your head than explain, so let me try
    	// to give you a very simple picture. Pretend you are this equation, standing on the plane, where UP
    	// (your head) is pointing the same direction as the plane's normal. directly below you is the "destination"
    	// point of the sphere. Your job as this equation is to "pull" the destination point up (towards the planes
    	// normal) until it is resting "in" the plane. If you can picture this the way i'm trying to get you to, you
    	// can see that the new velocity vector (from the point of collision between sphere and plane) to the new
    	// destination is "shorter" and parallel to the plane, so that now when the sphere follows this new velocity
    	// vector, it will be traveling parallel (sliding) across the triangle, at the same time, it does not travel
    	// as far as it would have if there was no collision. This is exactly what we want, because when you think about
    	// it, we do not run up mountains as fast as we run on flat ground, and if we run straight into a wall in our
    	// game, we will just stop moving, or if we run ALMOST straight into the wall, we will not go cruising sideways,
    	// but instead slowly move to either side. In my lesson on braynzarsoft.net, This is explained in pictures
    	XMVECTOR newDestinationPoint = destinationPoint - signedDistFromDestPointToSlidingPlane * slidePlaneNormal;
    
    	// I believe this line was covered briefly in the above explanation
    	XMVECTOR newVelocityVector = newDestinationPoint - cP.intersectionPoint;
    
    	// After this check, we will recurse. This check makes sure that we have not
    	// come to the end of our velocity vector (or very close to it, because if the velocity
    	// vector is very small, there is no reason to lose performance by doing an extra recurse
    	// when we won't even notice the distance "thrown away" by this check anyway) before
    	// we recurse
    	if (XMVectorGetX(XMVector3Length(newVelocityVector)) < veryCloseDistance) {
    		return newPosition;
    	}
    
    	// We are going to recurse now since a collision was found and the velocity
    	// changed directions. we need to check if the new velocity vector will
    	// cause the sphere to collide with other geometry.
    	cP.collisionRecursionDepth++;
    	cP.e_Position = newPosition;
    	cP.e_Velocity = newVelocityVector;
    	return CollideWithWorld(cP, vertPos, indices);
    }
    
    // This function checks if the swept sphere collides with a single triangle
    bool SphereCollidingWithTriangle(CollisionPacket& cP, XMVECTOR &p0, XMVECTOR &p1, XMVECTOR &p2, XMVECTOR &triNormal)
    {
    	// This function assumes p0, p1, p2, and the triangle normal are in ellipsoid space
    	// and that e_Position e_Velocity, and e_normalizedVelocity are defined in ellipsoid space
    	// In other words, this function checks for a collision between a SPHERE and a triangle,
    	// not an ellipsoid and a triangle. Because of this, the results from this function
    	// (specifically cP.nearestDistance and cP.intersectionPoint) are in ellipsoid space
    
    	// Check to see if triangle is facing velocity vector
    	// We will not triangle facing away from the velocity vector to speed this up
    	// since we assume that we will never run into the back face of triangles
    	float facing = XMVectorGetX(XMVector3Dot(triNormal, cP.e_normalizedVelocity));
    	if(facing <= 0)
    	{ 
    		// Create these because cP.e_Velocity and cP.e_Position add slightly to the difficulty
    		// of reading the equations
    		XMVECTOR velocity = cP.e_Velocity;
    		XMVECTOR position = cP.e_Position;
    
    		// t0 and t1 hold the time it takes along the velocity vector that the sphere (called a swept sphere)
    		// will "collide" (resting on or touching), once on the front side of the triangle (t0), and once on the
    		// backside after it goes "through" the triangle (t1) (or vertex or edge).
    		float t0, t1;
    
    		// If sphere is in the plane, it will not intersect with the center of the triangle
    		// but instead possibly intersect with one of the vertices or edges first
    		bool sphereInPlane = false;
    
    		// Find the plane equation in which the triangle lies in (Ax + By + Cz + D = 0)
    		// A, B, and C are the planes normal, x, y, and z respectively
    		// We can find D (a.k.a the plane constant) using some simple algebra, which we will do below
    		// x, y, and z in the equation defines a point in the plane. Any point in the plane
    		// will do, so we will just use p0
    
    		// First the point in the plane
    		float x = XMVectorGetX(p0);
    		float y = XMVectorGetY(p0);
    		float z = XMVectorGetZ(p0);
    
    		// Next the planes normal
    		float A = XMVectorGetX(triNormal);
    		float B = XMVectorGetY(triNormal);
    		float C = XMVectorGetZ(triNormal);
    
    		// Lets solve for D
    		// step 1: 0 = Ax + By + Cz + D
    		// step 2: subtract D from both sides
    		//			-D = Ax + By + Cz
    		// setp 3: multiply both sides by -1
    		//			-D*-1 = -1 * (Ax + By + Cz)
    		// final answer: D = -(Ax + By + Cz)
    		float D = -((A*x) + (B*y) + (C*z));
    
    		// To keep the variable names clear, we will rename D to planeConstant
    		float planeConstant = D;
    
    		// Get the signed distance from the cameras position (or object if you are using an object)
    		// We can get the signed distance between a point and plane with the equation:
    		// SignedDistance = PlaneNormal * Point + PlaneConstant 
    
    		// I've mentioned this before, but i'll do it again. When using xna math library vector function
    		// that return a scalar value (like a float) such as "XMVector3Dot", an XMVECTOR is returned, with
    		// all elements (x,y,z,w) containing that scalar value. We need to extract one, and any will do since
    		// they are all the same, so we extract the x component using "XMVectorGetX"
    		float signedDistFromPositionToTriPlane = XMVectorGetX(XMVector3Dot(position, triNormal)) + planeConstant;
    
    		// This will be used a couple times below, so we'll just calculate and store it now
    		float planeNormalDotVelocity = XMVectorGetX(XMVector3Dot(triNormal, velocity));
    
    		/////////////////////////////////////Sphere Plane Collision Test////////////////////////////////////////////
    		// Check to see if the velocity vector is parallel with the plane
    		if (planeNormalDotVelocity == 0.0f) 
    		{
    			if (fabs(signedDistFromPositionToTriPlane) >= 1.0f) 
    			{
    				// sphere not in plane, and velocity is
    				// parallel to plane, no collision possible
    				return false;
    			}
    			else 
    			{
    				// sphere is in the plane, so we will now only test for a collision
    				// with the triangle's vertices and edges
    				// Set sphereInPlane to true so we do not do the operation
    				// which will divide by zero if the velocity and plane are parallel
    				sphereInPlane = true;
    			}
    		}
    		else 
    		{
    			// We know the velocity vector at some point intersects with the plane, we just
    			// need to find how far down the velocity vector the sphere will "touch" or rest
    			// on the plane. t0 is when it first touches the plane (front side of sphere touches)
    			// and t1 is when the back side of the sphere touches.
    
    			// To find when (the time or how far down the velocity vector) the "velocity vector" itself
    			//intersects with the plane, we use the equation: (* stands for a dot product)
    			// t = (PlaneNormal * Point + PlaneConstant) / (PlaneNormal * Velocity);
    			// We have already calculated both sides of the divide sign "/", so:
    			// t = signedDistance / normalDotVelocity;
    
    			// Now remember we are working with a unit sphere (since everything has been moved from
    			// the usual space to our ellipsoid space). The unit sphere means that the distance from
    			// the center of the sphere to ANYWHERE on it's surface is "1". We are not interested in
    			// finding when the actual velocity vector intersects with the plane, but instead when
    			// the surface of the sphere "touches" the surface of the plane. We know that the distance
    			// from the center of the sphere is "1", so all we have to do to find when the sphere touches
    			// the plane is subtract and subtract 1 from the signed distance to get when both sides of the
    			// sphere touch the plane (t0, and t1)
    			t0 = ( 1.0f - signedDistFromPositionToTriPlane) / planeNormalDotVelocity;
    			t1 = (-1.0f - signedDistFromPositionToTriPlane) / planeNormalDotVelocity;
    
    			// We will make sure that t0 is smaller than t1, which means that t0 is when the sphere FIRST
    			// touches the planes surface
    			if(t0 > t1)
    			{
    				float temp = t0;
    				t0 = t1;
    				t1 = temp;
    			}
    
    			// If the swept sphere touches the plane outside of the 0 to 1 "timeframe", we know that
    			// the sphere is not going to intersect with the plane (and of course triangle) this frame
    			if (t0 > 1.0f || t1 < 0.0f) 
    			{
    				return false;
    			}
    
    			// If t0 is smaller than 0 then we will make it 0
    			// and if t1 is greater than 1 we will make it 1
    			if (t0 < 0.0) t0 = 0.0;
    			if (t1 > 1.0) t1 = 1.0;
    		}
    
    		////////////////////////////////Sphere-(Inside Triangle) Collision Test///////////////////////////////////////
    		// If we've made it this far, we know that the sphere will intersect with the triangles plane
    		// This frame, so now we will check to see if the collision happened INSIDE the triangle
    		XMVECTOR collisionPoint;		// Point on plane where collision occured
    		bool collidingWithTri = false;	// This is set so we know if there was a collision with the CURRENT triangle
    		float t = 1.0;					// Time 
    
    		// If the sphere is not IN the triangles plane, we continue the sphere to inside of triangle test
    		if (!sphereInPlane) 
    		{
    			// We get the point on the triangles plane where the sphere "touches" the plane
    			// using the equation: planeIntersectionPoint = (Position - Normal) + t0 * Velocity
    			// Where t0 is the distance down the velocity vector that the sphere first makes
    			// contact with the plane
    			XMVECTOR planeIntersectionPoint = (position + t0 * velocity - triNormal);
    
    			// Now we call the function that checks if a point on a triangle's plane is inside the triangle
    			if (checkPointInTriangle(planeIntersectionPoint,p0,p1,p2))
    			{
    				// If the point on the plane IS inside the triangle, we know that the sphere is colliding
    				// with the triangle now, so we set collidingWithTri to true so we don't do all the extra
    				// calculations on the triangle. We set t to t0, which is the time (or distance) down
    				// the velocity vector that the sphere first makes contact, then we set the point of 
    				// collision, which will be used later for our collision response
    				collidingWithTri = true;
    				t = t0;
    				collisionPoint = planeIntersectionPoint;
    			}
    		}
    
    		/////////////////////////////////////Sphere-Vertex Collision Test//////////////////////////////////////////////
    		// If the sphere is not colliding with the triangles INSIDE, we check to see if it will collide with one of
    		// the vertices of the triangle using the sweep test we did above, but this time check for each vertex instead
    		// of the triangles plane
    		if (collidingWithTri == false) 
    		{
    			// We will be working with the quadratic function "At^2 + Bt + C = 0" to find when (t) the "swept sphere"s center
    			// is 1 unit (spheres radius) away from the vertex position. Remember the swept spheres position is actually a line defined
    			// by the spheres position and velocity. t represents it's position along the velocity vector.
    			// a = sphereVelocityLength * sphereVelocityLength
    			// b = 2(sphereVelocity . (spherePosition - vertexPosition))	// . denotes dot product
    			// c = (vertexPosition - spherePosition)^2 - 1
    			// This equation allows for two solutions. One is when the sphere "first" touches the vertex, and the other is when
    			// the "other" side of the sphere touches the vertex on it's way past the vertex. We need the first "touch"
    			float a, b, c; // Equation Parameters
    
    			// We can use the squared velocities length below when checking for collisions with the edges of the triangles
    			// to, so to keep things clear, we won't set a directly
    			float velocityLengthSquared = XMVectorGetX(XMVector3Length(velocity));
    			velocityLengthSquared *= velocityLengthSquared;
    
    			// We'll start by setting 'a', since all 3 point equations use this 'a'
    			a = velocityLengthSquared;
    
    			// This is a temporary variable to hold the distance down the velocity vector that
    			// the sphere will touch the vertex.
    			float newT;
    
    			// P0 - Collision test with sphere and p0
    			b = 2.0f * ( XMVectorGetX( XMVector3Dot( velocity, position - p0 )));
    			c = XMVectorGetX(XMVector3Length((p0 - position)));
    			c = (c*c) - 1.0f;
    			if (getLowestRoot(a,b,c, t, &newT)) {	// Check if the equation can be solved
    				// If the equation was solved, we can set a couple things. First we set t (distance
    				// down velocity vector the sphere first collides with vertex) to the temporary newT,
    				// Then we set collidingWithTri to be true so we know there was for sure a collision
    				// with the triangle, then we set the exact point the sphere collides with the triangle,
    				// which is the position of the vertex it collides with
    				t = newT;
    				collidingWithTri = true;
    				collisionPoint = p0;
    			}
    
    			// P1 - Collision test with sphere and p1
    			b = 2.0*(XMVectorGetX(XMVector3Dot(velocity, position - p1)));
    			c = XMVectorGetX(XMVector3Length((p1 - position)));
    			c = (c*c) - 1.0;
    			if (getLowestRoot(a,b,c, t, &newT)) {
    				t = newT;
    				collidingWithTri = true;
    				collisionPoint = p1;
    			}
    
    			// P2 - Collision test with sphere and p2
    			b = 2.0*(XMVectorGetX(XMVector3Dot(velocity, position - p2)));
    			c = XMVectorGetX(XMVector3Length((p2 - position)));
    			c = (c*c) - 1.0;
    			if (getLowestRoot(a,b,c, t, &newT)) {
    				t = newT;
    				collidingWithTri = true;
    				collisionPoint = p2;
    			}
    
    			//////////////////////////////////////////////Sphere-Edge Collision Test//////////////////////////////////////////////
    			// Even though there might have been a collision with a vertex, we will still check for a collision with an edge of the
    			// triangle in case an edge was hit before the vertex. Again we will solve a quadratic equation to find where (and if)
    			// the swept sphere's position is 1 unit away from the edge of the triangle. The equation parameters this time are a 
    			// bit more complex: (still "Ax^2 + Bx + C = 0")
    			// a = edgeLength^2 * -velocityLength^2 + (edge . velocity)^2
    			// b = edgeLength^2 * 2(velocity . spherePositionToVertex) - 2((edge . velocity)(edge . spherePositionToVertex))
    			// c =  edgeLength^2 * (1 - spherePositionToVertexLength^2) + (edge . spherePositionToVertex)^2
    			// . denotes dot product
    
    			// Edge (p0, p1):
    			XMVECTOR edge = p1 - p0;
    			XMVECTOR spherePositionToVertex = p0 - position;
    			float edgeLengthSquared = XMVectorGetX(XMVector3Length(edge));
    			edgeLengthSquared *= edgeLengthSquared;
    			float edgeDotVelocity = XMVectorGetX(XMVector3Dot(edge, velocity));
    			float edgeDotSpherePositionToVertex = XMVectorGetX(XMVector3Dot(edge, spherePositionToVertex));
    			float spherePositionToVertexLengthSquared = XMVectorGetX(XMVector3Length(spherePositionToVertex));
    			spherePositionToVertexLengthSquared = spherePositionToVertexLengthSquared * spherePositionToVertexLengthSquared;
    
    			// Equation parameters
    			a = edgeLengthSquared * -velocityLengthSquared + (edgeDotVelocity * edgeDotVelocity);
    			b = edgeLengthSquared * (2.0f * XMVectorGetX(XMVector3Dot(velocity, spherePositionToVertex))) - (2.0f * edgeDotVelocity * edgeDotSpherePositionToVertex);
    			c = edgeLengthSquared * (1.0f - spherePositionToVertexLengthSquared) + (edgeDotSpherePositionToVertex * edgeDotSpherePositionToVertex);
    
    			// We start by finding if the swept sphere collides with the edges "infinite line"
    			if (getLowestRoot(a,b,c, t, &newT)) {
    				// Now we check to see if the collision happened between the two vertices that make up this edge
    				// We can calculate where on the line the collision happens by doing this:
    				// f = (edge . velocity)newT - (edge . spherePositionToVertex) / edgeLength^2
    				// if f is between 0 and 1, then we know the collision happened between p0 and p1
    				// If the collision happened at p0, the f = 0, if the collision happened at p1 then f = 1
    				float f = (edgeDotVelocity * newT - edgeDotSpherePositionToVertex) / edgeLengthSquared;
    				if (f >= 0.0f && f <= 1.0f) {
    					// If the collision with the edge happened, we set the results
    					t = newT;
    					collidingWithTri = true;
    					collisionPoint = p0 + f * edge;
    				}
    			}
    
    			// Edge (p1, p2):
    			edge = p2 - p1;
    			spherePositionToVertex = p1 - position;
    			edgeLengthSquared = XMVectorGetX(XMVector3Length(edge));
    			edgeLengthSquared = edgeLengthSquared * edgeLengthSquared;
    			edgeDotVelocity = XMVectorGetX(XMVector3Dot(edge, cP.e_Velocity));
    			edgeDotSpherePositionToVertex = XMVectorGetX(XMVector3Dot(edge, spherePositionToVertex));
    			spherePositionToVertexLengthSquared = XMVectorGetX(XMVector3Length(spherePositionToVertex));
    			spherePositionToVertexLengthSquared = spherePositionToVertexLengthSquared * spherePositionToVertexLengthSquared;
    
    			a = edgeLengthSquared * -velocityLengthSquared + (edgeDotVelocity * edgeDotVelocity);
    			b = edgeLengthSquared * (2.0f * XMVectorGetX(XMVector3Dot(velocity, spherePositionToVertex))) - (2.0f * edgeDotVelocity * edgeDotSpherePositionToVertex);
    			c = edgeLengthSquared * (1.0f - spherePositionToVertexLengthSquared) + (edgeDotSpherePositionToVertex * edgeDotSpherePositionToVertex);
    
    			if (getLowestRoot(a,b,c, t, &newT)) {
    				float f = (edgeDotVelocity * newT - edgeDotSpherePositionToVertex) / edgeLengthSquared;
    				if (f >= 0.0f && f <= 1.0f) {
    					t = newT;
    					collidingWithTri = true;
    					collisionPoint = p1 + f * edge;
    				}
    			}
    
    			// Edge (p2, p0):
    			edge = p0 - p2;
    			spherePositionToVertex = p2 - position;
    			edgeLengthSquared = XMVectorGetX(XMVector3Length(edge));
    			edgeLengthSquared = edgeLengthSquared * edgeLengthSquared;
    			edgeDotVelocity = XMVectorGetX(XMVector3Dot(edge, velocity));
    			edgeDotSpherePositionToVertex = XMVectorGetX(XMVector3Dot(edge, spherePositionToVertex));
    			spherePositionToVertexLengthSquared = XMVectorGetX(XMVector3Length(spherePositionToVertex));
    			spherePositionToVertexLengthSquared = spherePositionToVertexLengthSquared * spherePositionToVertexLengthSquared;
    
    			a = edgeLengthSquared * -velocityLengthSquared + (edgeDotVelocity * edgeDotVelocity);
    			b = edgeLengthSquared * (2.0f * XMVectorGetX(XMVector3Dot(velocity, spherePositionToVertex))) - (2.0f * edgeDotVelocity * edgeDotSpherePositionToVertex);
    			c = edgeLengthSquared * (1.0f - spherePositionToVertexLengthSquared) + (edgeDotSpherePositionToVertex * edgeDotSpherePositionToVertex);
    
    			if (getLowestRoot(a,b,c, t, &newT)) {
    				float f = (edgeDotVelocity * newT - edgeDotSpherePositionToVertex) / edgeLengthSquared;
    				if (f >= 0.0f && f <= 1.0f) {
    					t = newT;
    					collidingWithTri = true;
    					collisionPoint = p2 + f * edge;
    				}
    			}
    		}
    
    		// If we have found a collision, we will set the results of the collision here
    		if (collidingWithTri == true) 
    		{
    			// We find the distance to the collision using the time variable (t) times the length of the velocity vector
    			float distToCollision = t * XMVectorGetX(XMVector3Length(velocity));
    
    			// Now we check if this is the first triangle that has been collided with OR it is 
    			// the closest triangle yet that was collided with
    			if (cP.foundCollision == false || distToCollision < cP.nearestDistance) {
    
    				// Collision response information (used for "sliding")
    				cP.nearestDistance = distToCollision;
    				cP.intersectionPoint = collisionPoint;
    
    				// Make sure this is set to true if we've made it this far
    				cP.foundCollision = true;
    				return true;
    			}			
    		}
    	}
    	return false;
    }
    
    // These are the "helper" functions
    // This function is found in my lesson on picking in direct3d 11
    // This function finds if a point (in the triangle plane) is INSIDE the triangle
    bool checkPointInTriangle(const XMVECTOR& point, const XMVECTOR& triV1,const XMVECTOR& triV2, const XMVECTOR& triV3)
    {
    	XMVECTOR cp1 = XMVector3Cross((triV3 - triV2), (point - triV2));
    	XMVECTOR cp2 = XMVector3Cross((triV3 - triV2), (triV1 - triV2));
    	if(XMVectorGetX(XMVector3Dot(cp1, cp2)) >= 0)
    	{
    		cp1 = XMVector3Cross((triV3 - triV1), (point - triV1));
    		cp2 = XMVector3Cross((triV3 - triV1), (triV2 - triV1));
    		if(XMVectorGetX(XMVector3Dot(cp1, cp2)) >= 0)
    		{
    			cp1 = XMVector3Cross((triV2 - triV1), (point - triV1));
    			cp2 = XMVector3Cross((triV2 - triV1), (triV3 - triV1));
    			if(XMVectorGetX(XMVector3Dot(cp1, cp2)) >= 0)
    			{
    				return true;
    			}
    		}
    	}
    	return false;
    }
    
    // This function solves the quadratic eqation "At^2 + Bt + C = 0" and is found in Kasper Fauerby's paper on collision detection and response
    bool getLowestRoot(float a, float b, float c, float maxR, float* root) 
    {
    	// Check if a solution exists
    	float determinant = b*b - 4.0f*a*c;
    	// If determinant is negative it means no solutions.
    	if (determinant < 0.0f) return false;
    	// calculate the two roots: (if determinant == 0 then
    	// x1==x2 but let��s disregard that slight optimization)
    	float sqrtD = sqrt(determinant);
    	float r1 = (-b - sqrtD) / (2*a);
    	float r2 = (-b + sqrtD) / (2*a);
    	// Sort so x1 <= x2
    	if (r1 > r2) {
    		float temp = r2;
    		r2 = r1;
    		r1 = temp;
    	}
    	// Get lowest root:
    	if (r1 > 0 && r1 < maxR) {
    		*root = r1;
    		return true;
    	}
    	// It is possible that we want x2 - this can happen
    	// if x1 < 0
    	if (r2 > 0 && r2 < maxR) {
    		*root = r2;
    		return true;
    	}
    
    	// No (valid) solutions
    	return false;
    }
    /*************************************************************************************************/
    
    bool InitDirectInput(HINSTANCE hInstance)
    {
    	hr = DirectInput8Create(hInstance,
    		DIRECTINPUT_VERSION,
    		IID_IDirectInput8,
    		(void**)&DirectInput,
    		NULL); 
    
    	hr = DirectInput->CreateDevice(GUID_SysKeyboard,
    		&DIKeyboard,
    		NULL);
    
    	hr = DirectInput->CreateDevice(GUID_SysMouse,
    		&DIMouse,
    		NULL);
    
    	hr = DIKeyboard->SetDataFormat(&c_dfDIKeyboard);
    	hr = DIKeyboard->SetCooperativeLevel(hwnd, DISCL_FOREGROUND | DISCL_NONEXCLUSIVE);
    
    	hr = DIMouse->SetDataFormat(&c_dfDIMouse);
    	hr = DIMouse->SetCooperativeLevel(hwnd, DISCL_EXCLUSIVE | DISCL_NOWINKEY | DISCL_FOREGROUND);
    
    	return true;
    }
    
    void UpdateCamera()
    {
    	camRotationMatrix = XMMatrixRotationRollPitchYaw(camPitch, camYaw, 0);
    	camTarget = XMVector3TransformCoord(DefaultForward, camRotationMatrix );
    	camTarget = XMVector3Normalize(camTarget);
    
    	/************************************New Stuff****************************************************/
    	// First-Person Camera
    	XMMATRIX RotateYTempMatrix;
    	RotateYTempMatrix = XMMatrixRotationY(camYaw);
    	camRight = XMVector3TransformCoord(DefaultRight, RotateYTempMatrix);
    	camUp = XMVector3TransformCoord(camUp, RotateYTempMatrix);
    	camForward = XMVector3TransformCoord(DefaultForward, RotateYTempMatrix);
    
    	/*
    	// Free-Look Camera
    	camRight = XMVector3TransformCoord(DefaultRight, camRotationMatrix);
    	camForward = XMVector3TransformCoord(DefaultForward, camRotationMatrix);
    	camUp = XMVector3Cross(camForward, camRight);
    	*/
    
    	CollisionPacket cameraCP;
    	cameraCP.ellipsoidSpace = XMVectorSet(1.0f, 3.0f, 1.0f, 0.0f);
    	cameraCP.w_Position = camPosition;
    	cameraCP.w_Velocity = (moveLeftRight*camRight)+(moveBackForward*camForward);
    
    	camPosition = CollisionSlide(cameraCP,
    		collidableGeometryPositions,
    		collidableGeometryIndices);
    
    	/*camPosition += moveLeftRight*camRight;
    	camPosition += moveBackForward*camForward;*/
    	/*************************************************************************************************/
    
    	moveLeftRight = 0.0f;
    	moveBackForward = 0.0f;
    
    	camTarget = camPosition + camTarget;	
    
    	camView = XMMatrixLookAtLH( camPosition, camTarget, camUp );
    }
    
    void DetectInput(double time)
    {
    	DIMOUSESTATE mouseCurrState;
    
    	BYTE keyboardState[256];
    
    	DIKeyboard->Acquire();
    	DIMouse->Acquire();
    
    	DIMouse->GetDeviceState(sizeof(DIMOUSESTATE), &mouseCurrState);
    
    	DIKeyboard->GetDeviceState(sizeof(keyboardState),(LPVOID)&keyboardState);
    
    	if(keyboardState[DIK_ESCAPE] & 0x80)
    		PostMessage(hwnd, WM_DESTROY, 0, 0);
    
    	float speed = 15.0f * time;
    
    	if(keyboardState[DIK_A] & 0x80)
    	{
    		moveLeftRight -= speed;
    	}
    	if(keyboardState[DIK_D] & 0x80)
    	{
    		moveLeftRight += speed;
    	}
    	if(keyboardState[DIK_W] & 0x80)
    	{
    		moveBackForward += speed;
    	}
    	if(keyboardState[DIK_S] & 0x80)
    	{
    		moveBackForward -= speed;
    	}
    	if((mouseCurrState.lX != mouseLastState.lX) || (mouseCurrState.lY != mouseLastState.lY))
    	{
    		camYaw += mouseLastState.lX * 0.001f;
    
    		camPitch += mouseCurrState.lY * 0.001f;
    
    		mouseLastState = mouseCurrState;
    	}
    
    	UpdateCamera();
    
    	return;
    }
    
    
    void CleanUp()
    {
    	SwapChain->SetFullscreenState(false, NULL);
    	PostMessage(hwnd, WM_DESTROY, 0, 0);
    
    	//Release the COM Objects we created
    	SwapChain->Release();
    	d3d11Device->Release();
    	d3d11DevCon->Release();
    	renderTargetView->Release();
    	squareVertBuffer->Release();
    	squareIndexBuffer->Release();
    	VS->Release();
    	PS->Release();
    	VS_Buffer->Release();
    	PS_Buffer->Release();
    	vertLayout->Release();
    	depthStencilView->Release();
    	depthStencilBuffer->Release();
    	cbPerObjectBuffer->Release();
    	Transparency->Release();
    	CCWcullMode->Release();
    	CWcullMode->Release();
    
    	d3d101Device->Release();
    	keyedMutex11->Release();
    	keyedMutex10->Release();
    	D2DRenderTarget->Release();	
    	Brush->Release();
    	BackBuffer11->Release();
    	sharedTex11->Release();
    	DWriteFactory->Release();
    	TextFormat->Release();
    	d2dTexture->Release();
    
    	cbPerFrameBuffer->Release();
    
    	DIKeyboard->Unacquire();
    	DIMouse->Unacquire();
    	DirectInput->Release();
    }
    
    void InitD2DScreenTexture()
    {
    	//Create the vertex buffer
    	Vertex v[] =
    	{
    		// Front Face
    		Vertex(-1.0f, -1.0f, -1.0f, 0.0f, 1.0f,-1.0f, -1.0f, -1.0f),
    		Vertex(-1.0f,  1.0f, -1.0f, 0.0f, 0.0f,-1.0f,  1.0f, -1.0f),
    		Vertex( 1.0f,  1.0f, -1.0f, 1.0f, 0.0f, 1.0f,  1.0f, -1.0f),
    		Vertex( 1.0f, -1.0f, -1.0f, 1.0f, 1.0f, 1.0f, -1.0f, -1.0f),
    	};
    
    	DWORD indices[] = {
    		// Front Face
    		0,  1,  2,
    		0,  2,  3,
    	};
    
    	D3D11_BUFFER_DESC indexBufferDesc;
    	ZeroMemory( &indexBufferDesc, sizeof(indexBufferDesc) );
    
    	indexBufferDesc.Usage = D3D11_USAGE_DEFAULT;
    	indexBufferDesc.ByteWidth = sizeof(DWORD) * 2 * 3;
    	indexBufferDesc.BindFlags = D3D11_BIND_INDEX_BUFFER;
    	indexBufferDesc.CPUAccessFlags = 0;
    	indexBufferDesc.MiscFlags = 0;
    
    	D3D11_SUBRESOURCE_DATA iinitData;
    
    	iinitData.pSysMem = indices;
    	d3d11Device->CreateBuffer(&indexBufferDesc, &iinitData, &d2dIndexBuffer);
    
    
    	D3D11_BUFFER_DESC vertexBufferDesc;
    	ZeroMemory( &vertexBufferDesc, sizeof(vertexBufferDesc) );
    
    	vertexBufferDesc.Usage = D3D11_USAGE_DEFAULT;
    	vertexBufferDesc.ByteWidth = sizeof( Vertex ) * 4;
    	vertexBufferDesc.BindFlags = D3D11_BIND_VERTEX_BUFFER;
    	vertexBufferDesc.CPUAccessFlags = 0;
    	vertexBufferDesc.MiscFlags = 0;
    
    	D3D11_SUBRESOURCE_DATA vertexBufferData; 
    
    	ZeroMemory( &vertexBufferData, sizeof(vertexBufferData) );
    	vertexBufferData.pSysMem = v;
    	hr = d3d11Device->CreateBuffer( &vertexBufferDesc, &vertexBufferData, &d2dVertBuffer);
    
    	//Create A shader resource view from the texture D2D will render to,
    	//So we can use it to texture a square which overlays our scene
    	d3d11Device->CreateShaderResourceView(sharedTex11, NULL, &d2dTexture);
    }
    
    bool InitScene()
    {
    	InitD2DScreenTexture();
    
    	//Compile Shaders from shader file
    	hr = D3DX11CompileFromFile(L"Effects.fx", 0, 0, "VS", "vs_4_0", 0, 0, 0, &VS_Buffer, 0, 0);
    	hr = D3DX11CompileFromFile(L"Effects.fx", 0, 0, "PS", "ps_4_0", 0, 0, 0, &PS_Buffer, 0, 0);
    	hr = D3DX11CompileFromFile(L"Effects.fx", 0, 0, "D2D_PS", "ps_4_0", 0, 0, 0, &D2D_PS_Buffer, 0, 0);
    
    	//Create the Shader Objects
    	hr = d3d11Device->CreateVertexShader(VS_Buffer->GetBufferPointer(), VS_Buffer->GetBufferSize(), NULL, &VS);
    	hr = d3d11Device->CreatePixelShader(PS_Buffer->GetBufferPointer(), PS_Buffer->GetBufferSize(), NULL, &PS);
    	hr = d3d11Device->CreatePixelShader(D2D_PS_Buffer->GetBufferPointer(), D2D_PS_Buffer->GetBufferSize(), NULL, &D2D_PS);
    
    	//Set Vertex and Pixel Shaders
    	d3d11DevCon->VSSetShader(VS, 0, 0);
    	d3d11DevCon->PSSetShader(PS, 0, 0);
    
    	light.dir = XMFLOAT3(0.0f, -1.0f, 0.0f);
    	light.ambient = XMFLOAT4(0.2f, 0.2f, 0.2f, 1.0f);
    	light.diffuse = XMFLOAT4(1.0f, 1.0f, 1.0f, 1.0f);
    
    
    	HeightMapInfo hmInfo;
    	HeightMapLoad("heightmap.bmp", hmInfo);		// Load the heightmap and store it into hmInfo
    
    	int cols = hmInfo.terrainWidth;
    	int rows = hmInfo.terrainHeight;
    
    	//Create the grid
    	NumVertices = rows * cols;
    	NumFaces  = (rows-1)*(cols-1)*2;
    
    	std::vector<Vertex> v(NumVertices);
    
    	for(DWORD i = 0; i < rows; ++i)
    	{
    		for(DWORD j = 0; j < cols; ++j)
    		{
    			v[i*cols+j].pos = hmInfo.heightMap[i*cols+j];
    			v[i*cols+j].normal = XMFLOAT3(0.0f, 1.0f, 0.0f);
    		}
    	}
    
    	std::vector<DWORD> indices(NumFaces * 3);
    
    	int k = 0;
    	int texUIndex = 0;
    	int texVIndex = 0;
    	for(DWORD i = 0; i < rows-1; i++)
    	{
    		for(DWORD j = 0; j < cols-1; j++)
    		{
    			indices[k]   = i*cols+j;		// Bottom left of quad
    			v[i*cols+j].texCoord = XMFLOAT2(texUIndex + 0.0f, texVIndex + 1.0f);
    
    			indices[k+1] = (i+1)*cols+j;	// Top left of quad
    			v[(i+1)*cols+j].texCoord = XMFLOAT2(texUIndex + 0.0f, texVIndex + 0.0f);
    
    			indices[k+2] = i*cols+j+1;		// Bottom right of quad
    			v[i*cols+j+1].texCoord = XMFLOAT2(texUIndex + 1.0f, texVIndex + 1.0f);
    
    
    			indices[k+3] = (i+1)*cols+j;	// Top left of quad
    			v[(i+1)*cols+j].texCoord = XMFLOAT2(texUIndex + 0.0f, texVIndex + 0.0f);
    
    			indices[k+4] = (i+1)*cols+j+1;	// Top right of quad
    			v[(i+1)*cols+j+1].texCoord = XMFLOAT2(texUIndex + 1.0f, texVIndex + 0.0f);
    
    			indices[k+5] = i*cols+j+1;		// Bottom right of quad
    			v[i*cols+j+1].texCoord = XMFLOAT2(texUIndex + 1.0f, texVIndex + 1.0f);
    
    			k += 6; // next quad
    
    			texUIndex++;
    		}
    		texUIndex = 0;
    		texVIndex++;
    	}
    
    	/************************************New Stuff****************************************************/
    	// Since our terrain will not be transformed throughout our scene, we will set the our groundWorlds
    	// world matrix here so that when we put the terrains positions in the "polygon soup", they will
    	// already be transformed to world space
    	groundWorld = XMMatrixIdentity();
    	Scale = XMMatrixScaling( 10.0f, 10.0f, 10.0f );
    	Translation = XMMatrixTranslation( -520.0f, -10.0f, -1020.0f );
    	groundWorld = Scale * Translation;
    
    	// Store the terrains vertex positions and indices in the
    	// polygon soup that we will check for collisions with
    	// We can store ALL static (non-changing) geometry in here that we want to check for collisions with
    	int vertexOffset = collidableGeometryPositions.size();	// Vertex offset (each "mesh" will be added to the end of the positions array)
    
    	// Temp arrays because we need to store the geometry in world space
    	XMVECTOR tempVertexPosVec;
    	XMFLOAT3 tempVertF3;
    
    	// Push back vertex positions to the polygon soup
    	for(int i = 0; i < v.size(); i++)
    	{
    		tempVertexPosVec = XMLoadFloat3(&v[i].pos);
    		tempVertexPosVec = XMVector3TransformCoord(tempVertexPosVec, groundWorld);
    		XMStoreFloat3(&tempVertF3, tempVertexPosVec);
    		collidableGeometryPositions.push_back(tempVertF3);
    	}
    
    	// Push back indices for polygon soup. We need to make sure we are
    	// pushing back the indices "on top" of the previous pushed back
    	// objects vertex positions, hence "+ vertexOffset" (This is the
    	// first object we are putting in here, so it really doesn't
    	// matter right now, but I just wanted to show you how to do it
    	for(int i = 0; i < indices.size(); i++)
    	{
    		collidableGeometryIndices.push_back(indices[i] + vertexOffset);
    	}
    	/*************************************************************************************************/
    
    	//////////////////////Compute Normals///////////////////////////
    	//Now we will compute the normals for each vertex using normal averaging
    	std::vector<XMFLOAT3> tempNormal;
    
    	//normalized and unnormalized normals
    	XMFLOAT3 unnormalized = XMFLOAT3(0.0f, 0.0f, 0.0f);
    
    	//Used to get vectors (sides) from the position of the verts
    	float vecX, vecY, vecZ;
    
    	//Two edges of our triangle
    	XMVECTOR edge1 = XMVectorSet(0.0f, 0.0f, 0.0f, 0.0f);
    	XMVECTOR edge2 = XMVectorSet(0.0f, 0.0f, 0.0f, 0.0f);
    
    	//Compute face normals
    	for(int i = 0; i < NumFaces; ++i)
    	{
    		//Get the vector describing one edge of our triangle (edge 0,2)
    		vecX = v[indices[(i*3)]].pos.x - v[indices[(i*3)+2]].pos.x;
    		vecY = v[indices[(i*3)]].pos.y - v[indices[(i*3)+2]].pos.y;
    		vecZ = v[indices[(i*3)]].pos.z - v[indices[(i*3)+2]].pos.z;		
    		edge1 = XMVectorSet(vecX, vecY, vecZ, 0.0f);	//Create our first edge
    
    		//Get the vector describing another edge of our triangle (edge 2,1)
    		vecX = v[indices[(i*3)+2]].pos.x - v[indices[(i*3)+1]].pos.x;
    		vecY = v[indices[(i*3)+2]].pos.y - v[indices[(i*3)+1]].pos.y;
    		vecZ = v[indices[(i*3)+2]].pos.z - v[indices[(i*3)+1]].pos.z;		
    		edge2 = XMVectorSet(vecX, vecY, vecZ, 0.0f);	//Create our second edge
    
    		//Cross multiply the two edge vectors to get the un-normalized face normal
    		XMStoreFloat3(&unnormalized, XMVector3Cross(edge1, edge2));
    		tempNormal.push_back(unnormalized);			//Save unormalized normal (for normal averaging)
    	}
    
    	//Compute vertex normals (normal Averaging)
    	XMVECTOR normalSum = XMVectorSet(0.0f, 0.0f, 0.0f, 0.0f);
    	int facesUsing = 0;
    	float tX;
    	float tY;
    	float tZ;
    
    	//Go through each vertex
    	for(int i = 0; i < NumVertices; ++i)
    	{
    		//Check which triangles use this vertex
    		for(int j = 0; j < NumFaces; ++j)
    		{
    			if(indices[j*3] == i ||
    				indices[(j*3)+1] == i ||
    				indices[(j*3)+2] == i)
    			{
    				tX = XMVectorGetX(normalSum) + tempNormal[j].x;
    				tY = XMVectorGetY(normalSum) + tempNormal[j].y;
    				tZ = XMVectorGetZ(normalSum) + tempNormal[j].z;
    
    				normalSum = XMVectorSet(tX, tY, tZ, 0.0f);	//If a face is using the vertex, add the unormalized face normal to the normalSum
    				facesUsing++;
    			}
    		}
    
    		//Get the actual normal by dividing the normalSum by the number of faces sharing the vertex
    		normalSum = normalSum / facesUsing;
    
    		//Normalize the normalSum vector
    		normalSum = XMVector3Normalize(normalSum);
    
    		//Store the normal in our current vertex
    		v[i].normal.x = XMVectorGetX(normalSum);
    		v[i].normal.y = XMVectorGetY(normalSum);
    		v[i].normal.z = XMVectorGetZ(normalSum);
    
    		//Clear normalSum and facesUsing for next vertex
    		normalSum = XMVectorSet(0.0f, 0.0f, 0.0f, 0.0f);
    		facesUsing = 0;
    	}
    
    	D3D11_BUFFER_DESC indexBufferDesc;
    	ZeroMemory( &indexBufferDesc, sizeof(indexBufferDesc) );
    
    	indexBufferDesc.Usage = D3D11_USAGE_DEFAULT;
    	indexBufferDesc.ByteWidth = sizeof(DWORD) * NumFaces * 3;
    	indexBufferDesc.BindFlags = D3D11_BIND_INDEX_BUFFER;
    	indexBufferDesc.CPUAccessFlags = 0;
    	indexBufferDesc.MiscFlags = 0;
    
    	D3D11_SUBRESOURCE_DATA iinitData;
    
    	iinitData.pSysMem = &indices[0];
    	d3d11Device->CreateBuffer(&indexBufferDesc, &iinitData, &squareIndexBuffer);
    
    	D3D11_BUFFER_DESC vertexBufferDesc;
    	ZeroMemory( &vertexBufferDesc, sizeof(vertexBufferDesc) );
    
    	vertexBufferDesc.Usage = D3D11_USAGE_DEFAULT;
    	vertexBufferDesc.ByteWidth = sizeof( Vertex ) * NumVertices;
    	vertexBufferDesc.BindFlags = D3D11_BIND_VERTEX_BUFFER;
    	vertexBufferDesc.CPUAccessFlags = 0;
    	vertexBufferDesc.MiscFlags = 0;
    
    	D3D11_SUBRESOURCE_DATA vertexBufferData; 
    
    	ZeroMemory( &vertexBufferData, sizeof(vertexBufferData) );
    	vertexBufferData.pSysMem = &v[0];
    	hr = d3d11Device->CreateBuffer( &vertexBufferDesc, &vertexBufferData, &squareVertBuffer);
    
    	//Create the Input Layout
    	hr = d3d11Device->CreateInputLayout( layout, numElements, VS_Buffer->GetBufferPointer(), 
    		VS_Buffer->GetBufferSize(), &vertLayout );
    
    	//Set the Input Layout
    	d3d11DevCon->IASetInputLayout( vertLayout );
    
    	//Set Primitive Topology
    	d3d11DevCon->IASetPrimitiveTopology( D3D11_PRIMITIVE_TOPOLOGY_TRIANGLELIST );
    
    	//Create the Viewport
    	D3D11_VIEWPORT viewport;
    	ZeroMemory(&viewport, sizeof(D3D11_VIEWPORT));
    
    	viewport.TopLeftX = 0;
    	viewport.TopLeftY = 0;
    	viewport.Width = Width;
    	viewport.Height = Height;
    	viewport.MinDepth = 0.0f;
    	viewport.MaxDepth = 1.0f;
    
    	//Set the Viewport
    	d3d11DevCon->RSSetViewports(1, &viewport);
    
    	//Create the buffer to send to the cbuffer in effect file
    	D3D11_BUFFER_DESC cbbd;	
    	ZeroMemory(&cbbd, sizeof(D3D11_BUFFER_DESC));
    
    	cbbd.Usage = D3D11_USAGE_DEFAULT;
    	cbbd.ByteWidth = sizeof(cbPerObject);
    	cbbd.BindFlags = D3D11_BIND_CONSTANT_BUFFER;
    	cbbd.CPUAccessFlags = 0;
    	cbbd.MiscFlags = 0;
    
    	hr = d3d11Device->CreateBuffer(&cbbd, NULL, &cbPerObjectBuffer);
    
    	//Create the buffer to send to the cbuffer per frame in effect file
    	ZeroMemory(&cbbd, sizeof(D3D11_BUFFER_DESC));
    
    	cbbd.Usage = D3D11_USAGE_DEFAULT;
    	cbbd.ByteWidth = sizeof(cbPerFrame);
    	cbbd.BindFlags = D3D11_BIND_CONSTANT_BUFFER;
    	cbbd.CPUAccessFlags = 0;
    	cbbd.MiscFlags = 0;
    
    	hr = d3d11Device->CreateBuffer(&cbbd, NULL, &cbPerFrameBuffer);
    
    	//Camera information
    	camPosition = XMVectorSet( 0.0f, 5.0f, -8.0f, 0.0f );
    	camTarget = XMVectorSet( 0.0f, 0.0f, 0.0f, 0.0f );
    	camUp = XMVectorSet( 0.0f, 1.0f, 0.0f, 0.0f );
    
    	//Set the View matrix
    	camView = XMMatrixLookAtLH( camPosition, camTarget, camUp );
    
    	//Set the Projection matrix
    	camProjection = XMMatrixPerspectiveFovLH( 0.4f*3.14f, (float)Width/Height, 1.0f, 1000.0f);
    
    	D3D11_BLEND_DESC blendDesc;
    	ZeroMemory( &blendDesc, sizeof(blendDesc) );
    
    	D3D11_RENDER_TARGET_BLEND_DESC rtbd;
    	ZeroMemory( &rtbd, sizeof(rtbd) );
    
    	rtbd.BlendEnable			 = true;
    	rtbd.SrcBlend				 = D3D11_BLEND_SRC_COLOR;
    	rtbd.DestBlend				 = D3D11_BLEND_INV_SRC_ALPHA;
    	rtbd.BlendOp				 = D3D11_BLEND_OP_ADD;
    	rtbd.SrcBlendAlpha			 = D3D11_BLEND_ONE;
    	rtbd.DestBlendAlpha			 = D3D11_BLEND_ZERO;
    	rtbd.BlendOpAlpha			 = D3D11_BLEND_OP_ADD;
    	rtbd.RenderTargetWriteMask	 = D3D10_COLOR_WRITE_ENABLE_ALL;
    
    	blendDesc.AlphaToCoverageEnable = false;
    	blendDesc.RenderTarget[0] = rtbd;
    
    	hr = D3DX11CreateShaderResourceViewFromFile( d3d11Device, L"grass.jpg",
    		NULL, NULL, &CubesTexture, NULL );
    
    	// Describe the Sample State
    	D3D11_SAMPLER_DESC sampDesc;
    	ZeroMemory( &sampDesc, sizeof(sampDesc) );
    	sampDesc.Filter = D3D11_FILTER_MIN_MAG_MIP_LINEAR;
    	sampDesc.AddressU = D3D11_TEXTURE_ADDRESS_WRAP;
    	sampDesc.AddressV = D3D11_TEXTURE_ADDRESS_WRAP;    
    	sampDesc.AddressW = D3D11_TEXTURE_ADDRESS_WRAP;
    	sampDesc.ComparisonFunc = D3D11_COMPARISON_NEVER;
    	sampDesc.MinLOD = 0;
    	sampDesc.MaxLOD = D3D11_FLOAT32_MAX;
    
    	//Create the Sample State
    	hr = d3d11Device->CreateSamplerState( &sampDesc, &CubesTexSamplerState );
    
    	d3d11Device->CreateBlendState(&blendDesc, &Transparency);
    
    	D3D11_RASTERIZER_DESC cmdesc;
    
    	ZeroMemory(&cmdesc, sizeof(D3D11_RASTERIZER_DESC));
    	cmdesc.FillMode = D3D11_FILL_SOLID;
    	cmdesc.CullMode = D3D11_CULL_BACK;
    	cmdesc.FrontCounterClockwise = true;
    	hr = d3d11Device->CreateRasterizerState(&cmdesc, &CCWcullMode);
    
    	cmdesc.FrontCounterClockwise = false;
    
    	hr = d3d11Device->CreateRasterizerState(&cmdesc, &CWcullMode);
    
    	return true;
    }
    
    void StartTimer()
    {
    	LARGE_INTEGER frequencyCount;
    	QueryPerformanceFrequency(&frequencyCount);
    
    	countsPerSecond = double(frequencyCount.QuadPart);
    
    	QueryPerformanceCounter(&frequencyCount);
    	CounterStart = frequencyCount.QuadPart;
    }
    
    double GetTime()
    {
    	LARGE_INTEGER currentTime;
    	QueryPerformanceCounter(&currentTime);
    	return double(currentTime.QuadPart-CounterStart)/countsPerSecond;
    }
    
    double GetFrameTime()
    {
    	LARGE_INTEGER currentTime;
    	__int64 tickCount;
    	QueryPerformanceCounter(&currentTime);
    
    	tickCount = currentTime.QuadPart-frameTimeOld;
    	frameTimeOld = currentTime.QuadPart;
    
    	if(tickCount < 0.0f)
    		tickCount = 0.0f;
    
    	return float(tickCount)/countsPerSecond;
    }
    
    /************************************New Stuff****************************************************/
    void UpdateScene(double time)
    {
    }
    /*************************************************************************************************/
    
    void RenderText(std::wstring text, int inInt)
    {
    
    	d3d11DevCon->PSSetShader(D2D_PS, 0, 0);
    
    	//Release the D3D 11 Device
    	keyedMutex11->ReleaseSync(0);
    
    	//Use D3D10.1 device
    	keyedMutex10->AcquireSync(0, 5);	
    
    	//Draw D2D content		
    	D2DRenderTarget->BeginDraw();	
    
    	//Clear D2D Background
    	D2DRenderTarget->Clear(D2D1::ColorF(0.0f, 0.0f, 0.0f, 0.0f));
    
    	//Create our string
    	std::wostringstream printString; 
    	printString << text << inInt;
    	printText = printString.str();
    
    	//Set the Font Color
    	D2D1_COLOR_F FontColor = D2D1::ColorF(1.0f, 1.0f, 1.0f, 1.0f);
    
    	//Set the brush color D2D will use to draw with
    	Brush->SetColor(FontColor);	
    
    	//Create the D2D Render Area
    	D2D1_RECT_F layoutRect = D2D1::RectF(0, 0, Width, Height);
    
    	//Draw the Text
    	D2DRenderTarget->DrawText(
    		printText.c_str(),
    		wcslen(printText.c_str()),
    		TextFormat,
    		layoutRect,
    		Brush
    		);
    
    	D2DRenderTarget->EndDraw();	
    
    	//Release the D3D10.1 Device
    	keyedMutex10->ReleaseSync(1);
    
    	//Use the D3D11 Device
    	keyedMutex11->AcquireSync(1, 5);
    
    	//Use the shader resource representing the direct2d render target
    	//to texture a square which is rendered in screen space so it
    	//overlays on top of our entire scene. We use alpha blending so
    	//that the entire background of the D2D render target is "invisible",
    	//And only the stuff we draw with D2D will be visible (the text)
    
    	//Set the blend state for D2D render target texture objects
    	d3d11DevCon->OMSetBlendState(Transparency, NULL, 0xffffffff);
    
    	//Set the d2d Index buffer
    	d3d11DevCon->IASetIndexBuffer( d2dIndexBuffer, DXGI_FORMAT_R32_UINT, 0);
    	//Set the d2d vertex buffer
    	UINT stride = sizeof( Vertex );
    	UINT offset = 0;
    	d3d11DevCon->IASetVertexBuffers( 0, 1, &d2dVertBuffer, &stride, &offset );
    
    	WVP =  XMMatrixIdentity();
    	cbPerObj.WVP = XMMatrixTranspose(WVP);	
    	d3d11DevCon->UpdateSubresource( cbPerObjectBuffer, 0, NULL, &cbPerObj, 0, 0 );
    	d3d11DevCon->VSSetConstantBuffers( 0, 1, &cbPerObjectBuffer );
    	d3d11DevCon->PSSetShaderResources( 0, 1, &d2dTexture );
    	d3d11DevCon->PSSetSamplers( 0, 1, &CubesTexSamplerState );
    
    	d3d11DevCon->RSSetState(CWcullMode);
    	//Draw the second cube
    	d3d11DevCon->DrawIndexed( 6, 0, 0 );	
    }
    
    void DrawScene()
    {
    	//Clear our render target and depth/stencil view
    	float bgColor[4] = { 0.1f, 0.1f, 0.1f, 1.0f };
    	d3d11DevCon->ClearRenderTargetView(renderTargetView, bgColor);	
    	d3d11DevCon->ClearDepthStencilView(depthStencilView, D3D11_CLEAR_DEPTH|D3D11_CLEAR_STENCIL, 1.0f, 0);
    
    	constbuffPerFrame.light = light;
    	d3d11DevCon->UpdateSubresource( cbPerFrameBuffer, 0, NULL, &constbuffPerFrame, 0, 0 );
    	d3d11DevCon->PSSetConstantBuffers(0, 1, &cbPerFrameBuffer);	
    
    	//Set our Render Target
    	d3d11DevCon->OMSetRenderTargets( 1, &renderTargetView, depthStencilView );
    
    	//Set the default blend state (no blending) for opaque objects
    	d3d11DevCon->OMSetBlendState(0, 0, 0xffffffff);
    
    	//Set Vertex and Pixel Shaders
    	d3d11DevCon->VSSetShader(VS, 0, 0);
    	d3d11DevCon->PSSetShader(PS, 0, 0);
    
    	//Set the cubes index buffer
    	d3d11DevCon->IASetIndexBuffer( squareIndexBuffer, DXGI_FORMAT_R32_UINT, 0);
    	//Set the cubes vertex buffer
    	UINT stride = sizeof( Vertex );
    	UINT offset = 0;
    	d3d11DevCon->IASetVertexBuffers( 0, 1, &squareVertBuffer, &stride, &offset );
    
    	//Set the WVP matrix and send it to the constant buffer in effect file
    	WVP = groundWorld * camView * camProjection;
    	cbPerObj.WVP = XMMatrixTranspose(WVP);	
    	cbPerObj.World = XMMatrixTranspose(groundWorld);	
    	d3d11DevCon->UpdateSubresource( cbPerObjectBuffer, 0, NULL, &cbPerObj, 0, 0 );
    	d3d11DevCon->VSSetConstantBuffers( 0, 1, &cbPerObjectBuffer );
    	d3d11DevCon->PSSetShaderResources( 0, 1, &CubesTexture );
    	d3d11DevCon->PSSetSamplers( 0, 1, &CubesTexSamplerState );
    
    	d3d11DevCon->RSSetState(CWcullMode);
    	d3d11DevCon->DrawIndexed( NumFaces * 3, 0, 0 );
    
    	RenderText(L"FPS: ", fps);
    
    	//Present the backbuffer to the screen
    	SwapChain->Present(0, 0);
    }
    
    int messageloop(){
    	MSG msg;
    	ZeroMemory(&msg, sizeof(MSG));
    	while(true)
    	{
    		BOOL PeekMessageL( 
    			LPMSG lpMsg,
    			HWND hWnd,
    			UINT wMsgFilterMin,
    			UINT wMsgFilterMax,
    			UINT wRemoveMsg
    			);
    
    		if (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE))
    		{
    			if (msg.message == WM_QUIT)
    				break;
    			TranslateMessage(&msg);	
    			DispatchMessage(&msg);
    		}
    		else{
    			// run game code    
    			frameCount++;
    			if(GetTime() > 1.0f)
    			{
    				fps = frameCount;
    				frameCount = 0;
    				StartTimer();
    			}	
    
    			frameTime = GetFrameTime();
    
    			DetectInput(frameTime);
    			UpdateScene(frameTime);
    			DrawScene();
    		}
    	}
    	return msg.wParam;
    }
    
    LRESULT CALLBACK WndProc(HWND hwnd,
    	UINT msg,
    	WPARAM wParam,
    	LPARAM lParam)
    {
    	switch( msg )
    	{
    	case WM_KEYDOWN:
    		if( wParam == VK_ESCAPE ){
    			DestroyWindow(hwnd);
    		}
    		return 0;
    
    	case WM_DESTROY:
    		PostQuitMessage(0);
    		return 0;
    	}
    	return DefWindowProc(hwnd,
    		msg,
    		wParam,
    		lParam);
    }

Effects.fx
    struct Light
    {
    	float3 dir;
    	float4 ambient;
    	float4 diffuse;
    };
    
    cbuffer cbPerFrame
    {
    	Light light;
    };
    
    cbuffer cbPerObject
    {
    	float4x4 WVP;
        float4x4 World;
    };
    
    Texture2D ObjTexture;
    SamplerState ObjSamplerState;
    
    struct VS_OUTPUT
    {
    	float4 Pos : SV_POSITION;
    	float2 TexCoord : TEXCOORD;
    	float3 normal : NORMAL;
    };
    
    VS_OUTPUT VS(float4 inPos : POSITION, float2 inTexCoord : TEXCOORD, float3 normal : NORMAL)
    {
        VS_OUTPUT output;
    
        output.Pos = mul(inPos, WVP);
    
    	output.normal = mul(normal, World);
    
        output.TexCoord = inTexCoord;
    
        return output;
    }
    
    float4 PS(VS_OUTPUT input) : SV_TARGET
    {
    	input.normal = normalize(input.normal);
    
        float4 diffuse = ObjTexture.Sample( ObjSamplerState, input.TexCoord );
    
    	float3 finalColor;
    
    	finalColor = diffuse * light.ambient;
    	finalColor += saturate(dot(light.dir, input.normal) * light.diffuse * diffuse);
    	
    	return float4(finalColor, diffuse.a);
    }
    
    float4 D2D_PS(VS_OUTPUT input) : SV_TARGET
    {
        float4 diffuse = ObjTexture.Sample( ObjSamplerState, input.TexCoord );
    	
    	return diffuse;
    }