xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

C++代写-FIT2096

时间：2021-04-25

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

学霸联盟

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

学霸联盟