Week 7: Physics Engines and Collisions
FIT2096: Games Programming 1
2Last week…
 Cameras
– The View Frustum
– View and Projection Matrices
 Transforming Spaces
– Another look at Model, View, and World space
 The Rendering Pipeline
– Stages of the pipeline
– Fixed vs programmable stages
– A quick introduction to shaders (vertex, geometry, and pixel shaders)
– Back-face Culling
– Depth and Stencil Buffers
 Blueprints
– Purpose and Functionality
Physics Engines
• The Physics World
• Shapes
• Physics Bodies
• Constraints and Joints
• Contacts/Collisions
Physics in Games
• Basic Physics in the Unreal Engine…
Physics in Games
• Why do we have Physics in Games?
• What interesting things can we do with our simulated
physics world?
• The material we will look at today is based upon the
Box2d Physics Engine
• Although it is for 2D games it is still relevant for our 3D
worlds
 All physics engines seek to define a physics world.
• World Dimensions
 maximum length, width and height
• Gravity
• Friction
• Mass of Objects
The Physics World
• Do all objects rendered in the Game World need to be part
of the Physics World of that game?
• Why?
• The data structure used to represent the Renderable
Game World might be different to the data structure used
for the Physics World
• Physics objects will be somehow connected to Render
objects
• Physics calculations can be expensive
• Often to save processing performance a physics engine
will allow objects that aren't moving or interacting with
objects to be put to sleep/made inactive.
• With many physics engines, when objects leave the pre-
defined “world area” they are put to rest or sleep. This
means the objects stop being processed and will no longer
interact with the rest of the world.
Physics Objects can Sleep!
• Defines simple collision geometry
• One or more Physics Shapes are used to create a Physics Body.
• Also defines the Mass of the body its attached to.
Physics Shapes
• Shapes can have custom friction values and restitution.
 Friction being how easily one physics shape moves
against another.
 Restitution being how quickly an object settles?
• Shapes/Bodies often have some form of filtering of allowable collisions.
Basically defining collision groups or categories that can be set.
• For example, you could specify in a game that all players don't collide with
each other and monsters don't collide with each other, but players and
monsters should collide.
 Sensors
• A special kind of shape that essentially doesn't produce a collision
response with other shapes when they overlap.
• Provides a notification.
• Sensors are what you'd use for an area trigger.
• Demo…
Sensors
• Its a container object.
• Its used in the physics engine to represent a rigid body, which is a really
just a collection of physics Shapes.
• Physics Shapes are added to or removed from a body and determine what
the collide-able shape of the object is.
• It can be a static or dynamic body.
Physics Bodies
• Shapes inside a body can't interact or collide with other shapes
inside the same body.
• Generally, 1 body will collide with another body based on the
shapes within each body..
• Constraints/Joints are made between bodies.
• Bodies are used as performance simplification and as a means of
grouping associated shapes together.
• Bodies have a calculated mass, dampening values.
• Impulses and torque forces are applied to bodies only.
• More complex Physics and collisions in the Unreal
Engine…
Physics in Games
 Joints / Constraints
• A range of class types which is responsible for keeping one body
connected/constrained to another.(eg, see-saws, pulleys, ragdolls etc)
• Some joints can have a limit to there range of motion, or provide some sort
of resistance force like a spring.
• In Box2D a “motor” can be associated with a joint and attempt to apply
constant force or torque to the joint.
Constraints/Joints
• Distance Joint – body A stays a fixed distance from body B
Types of Joints: Distance Joint
• Hinge/Revolute Joint – two bodies share a common anchor point to one another only
allowing angular movement between the two.
Types of Joints: Hinge/Revolute Joint
• Prismatic Joint – allows relative translation of a joint along a specified axis
Types of Joints: Prismatic Joint
• Pully Joint - body A goes up, body B goes down
Types of Joints: Pully Joint
 Demo…
Types of Joints/Constraints
 Contacts/Collisions
• How physics engines manage collisions between shapes.
• Poly to Poly, Circle to Circle
Contacts/Collisions
• Contact Point - where a collision happened on two shapes
• Contact Normal - a unit vector pointing from shape 1 to shape 2.
• Contact Separation - the opposite of penetration
• Normal Force - calculated via a solver of x iterations, this is how hard 2
shapes collide (intensity).
Contacts/Collisions
• A special class to be called when a contact takes place.
• This contact listener will often be associated with a user
defined class that will implement custom handling of a
contact.
• This listener reports a contact point
• when it is created,
• when it persists for more than one time step,
• and when it is destroyed.
Contact Listener
 We will be covering collisions in more detail in a future
lecture
 You will need to use a collision system in your final
assignment
Collisions
 Listed below are some various Physics Engines and
SDKs
 Box2D: http://www.box2d.org
 Bullet Physics Library: http://bulletphysics.org/wordpress/
 Open Dynamics Engine: http://www.ode.org/
 Havok: http://www.havok.com/physics/
 PhysX:
http://developer.nvidia.com/object/physx_downloads.html
Great Physics Links
Collisions
• We have a world made up of dynamic (moving/changing) and static
objects which can potentially be made up of many thousands of triangles
or more.
• A truly accurate physics-collision system would need to perform
thousands of calculations every frame for a complex mesh
Collision Detection
• Simulation vs Games
• Weather simulations try to get things as accurate as possible
• This is important because people’s lives can be at risk if the weather predictions
are wrong
• What is the worst thing that could happen if we got a collision calculation
wrong in a game?
• What is the most important factor with physics simulations in games?
Collision Detection
• How can we determine collisions in a fast and efficient manner?
• There is no easy answer to this question.
• For starters, we simplify the problem as much as possible and take appropriate
short-cuts where ever we can.
Collision Detection
• All games, even simulations, take short-cuts at various stages to improve
performance. However it does leave us with the problem of losing some
accuracy.
• Most of the time gamers and users don’t even notice or care about the
short cuts - they’re usually just happy that the frame rate is moving along.
• And here-in lies the golden rule.
• It if it looks good, it is good.
• Unless it adversely effects game play
Collision Detection
• The KISS philosophy wins out here.
• The cheaper your collisions and physics are the more CPU cycles you have left for
the rest of the game.
Collision Detection
• There are 4 major types of collision objects that we work with:
• Bounding Boxes
• Bounding Spheres
• Rays
• Planes
• All of these are approximations of the actual object that is colliding.
• By approximating the shape of a complex 3D object as a simple basic 3D primitive
(sphere, box), we can vastly reduce the processing overhead.
Collision Objects & simplified collision
Collision Detection
• How could we detect a collision between these two complex 2D
shapes?
Collision Detection
• How could we detect a collision between these two 2D shapes?
Bounding Spheres
• Bounding Spheres are the simplest form of bounding
object
• They are represented using two pieces of information:
• A centre point
• And a radius
• Because of their simplicity they are the fastest to
compute and check against
• However the objects that they bound have to be quite
simplistic in shape.
Calculating a Bounding Sphere
• We need to get a value for the radius and the centre of
the object
• To get the radius all you need to do is:
• loop through all axes of the geometry in question and
determine the min and max values of the vertices,
• square root the result of the max subtracted from the min (the
difference) and it will equal the radius of the sphere.
• To get the centre point, it’s the difference divided by half.
Bounding Boxes
• Bounding Boxes are slightly more complex but can bound more complex
geometry tighter
• They are also represented using two pieces of information:
• A minimum vector V1
• And a maximum vector V2
V1(x,y)
V2(x,y)
Axis-Aligned Bounding Boxes (AABB’s)
• This might not seem like enough information but if you think about it you
are able to extend the vectors out across each axis and the points where
they meet make up the other 6 corners of the box
• This means that our Bounding Boxes are always aligned with our axes.
• These are also know as axis-aligned Bounding-boxes or AABBs
Calculating an AABB
• How would you calculate an AABB for the shape below?
V1(x,y)
V2(x,y)
Calculating an AABB
• How would you calculate an AABB for the shape below?
• Determine the min and max values for all vertices in each axis.
• V1x = min(x)
• V1y = min(y)
• V2x = max(x)
• V2y = max(y)
V1(x,y)
V2(x,y)
Rays
• A ray is just a line in space but we can check to see if
it hits things like boxes and spheres
• It is represented by two pieces of data
• A vector which represents the world position of the origin
of the ray
• A second vector that represents the direction and length of
the ray
Rays
• Typically we don’t use a ray to represent bounding
geometry (very few pieces of geometry are lines)
• But we can use them to check for other things,
including line of sight between player’s and what
object the mouse is over
• We will be using rays and ray-traces in Game
Programming 2
Planes
• A plane is a “wall” that extends to infinity in all
directions along the plane
• We represent a plane with two pieces of
information:
• A normal vector that is standing orthogonal on the
plane and facing the direction of the front side of the
plane
• A float that represents the distance (d) from the
world origin
World Origin
d
Planes
• You can’t really render a plane because we don’t
have infinite space on the screen but you can
tell what side of the plane objects are on.
World Origin
d
Planes
• Why would I want to know what side of a plane a point is on? A few
reasons, but geometry culling and collision detection are the main ones.
• Geometry culling at its basics, defines a view frustum (which is just 6
planes) around the camera. Depending on which side of the plane the
geometry is located on, we can determine quickly if we need to draw the
object or not. Other examples are occluders which are just single planes
placed around an environment.
Collision Detection
• Choosing the right collision object is based on the type of object you are
trying to bound
• A bounding sphere completely surrounds a piece of geometry. Bounding
spheres are one of the fastest approximation and representation of a
games physical object.
Collision Detection
• A bounding sphere or box isn’t always going to fit the object its
approximating well (wasted space) and this is what we refer to as a short-
cut and will cause a loss of accuracy in the collision test (the objects below
aren’t technically touching, even though their bounds are).
Collision Detection
• So that’s how we approximate the form of our 3D objects. Let’s see how
to test collisions between these bounding primitives.
• We are going to look at the following six tests:
• Sphere and Sphere
• Sphere and Point
• Sphere and Box
• Box and Box
• Box and Point
• Plane and Point
• Other tests can be found online and also in various textbooks
• Check out 3D Math Primer by Fletcher Dunn and Ian Parberry
Collision Detection, Sphere and Sphere
• Sphere to sphere collision test basically boils down to this.
• Get the difference vector between the two spheres. If the magnitude of
the difference vector is smaller than the sum of both spheres’ radius, our
spheres are intersecting.
return d < (r1 + r2)r1
r2
d
Collision Detection, Sphere -> Sphere
• For spheres that don’t have very large positional values it is possible to
do the previous calculation without square rooting the difference vector
and squaring each sphere radius before adding them together.
• This is ideal because we want to avoid expensive math at all times for a
collision detection.
Collision Detection, Sphere and Point
• Sphere to point is just like the Sphere to Sphere but we disregard the
second radius
• Again, we can use DistanceSquared() here to cut out the sqrt() call and
simply square the radius instead.
return d < r
r d
Collision Detection, Box and Box
• Box to Box
• Testing whether one box lies within or is colliding with another box is a fairly
similar process. We have two options.
• 1: Using point to box test, calculate where each of the corners of one box is
located and test on each corner.
• Or
• 2: The better way is to make sure that the first box’s minimum is smaller than the
second box’s maximum and that its maximum axis is larger than the second box’s
minimum.
Collision Detection, Sphere and Box
• Sphere to Box requires us to get the distance between the centre of the
Sphere and the closest point within the Bounding Box based on the centre
of the sphere.
• If the distance between these points is less than the radius of the sphere
then they are colliding
Vector p1 = sphere.centre
Vector p2 = ClosestPoint(box, sphere.centre)
float distance = (p1 – p2).length
return distance < sphere.radius
Collision Detection, Box and Point
• Box to point
• Testing whether a point lies within the bounds of a box (i.e it’s collided) is easy.
• If a point’s x, y and z positions are larger than the bounding box’s minimum axis
and smaller than the maximum axis then it can be said that a collision has
occurred.
Collision Detection, Plane and Point
• How do we know which side of a plane a point lies?
• Lets assume we have a plane that is made up of a normal direction and
distance, and a point that is made up of x y and z values.
float distance = plane.norm.x * point.x +
plane.norm.y * point.y +
plane.norm.z * point.z +
plane.distance
if(distance > 0.0001)
point is in front of plane
else if(distance < -0.0001)
point is behind plane
else
point is on plane
Review
• Collision Objects
• Collision Detection
• Physics Libraries


















































































































































































































































































































































































学霸联盟