Blog

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