2D Collisions

What is the difference between collision detection & collision response?

Detection:

- whether objects collide

- when they collide

- where they collide

Response:

- what happens after collision

What is the multi-phase system for collision?

1. Broad Phase

2. Narrow Phase

3. Middle Phase

4. Collision Response

What is the broad phase?

Quick elimination of object that cannot possibly collide

What is AABB?

- Axis-Aligned Bounding Boxes

- involves a simple rectangle around an object, aligned with X, Y axes

- Tests for collision if they overlap

- Fast, simple, supports scaling / translation

- Inaccurate for rotated or fast objects

What are bounding circles?

- involves a simple circle around an object

- collision determined by overlap of sprites

- handles scaling, translation, rotation

- inaccurate for fast-moving / multiple objects

What is SAT?

- Separating Axis Theorem

- Used for convex polygons / rotated rectangles

- collision if no separating axis exists between two polygons

What is a separating axis?

A direction where the projections of two shapes do not overlap

How does exact sprite collision detection work?

- Sprites contain visible pixels & transparent pixels

- Collision when visible pixels overlap

- Very accurate but computationally expensive for multiple / rotated / scaled sprites

What is the tunnelling problem?

- When a fast-moving object passes through another object between frames

- moves >= 1/3 of its smallest dimension between frames

How is the tunnelling problem solved?

- Swept AABB collision detection

- create a larger collision area covering previous and current position

- helps detect possible missed collisions

- assumed straight-line movement

What is a quadtree?

- Tree data structure that divides 2D space into 4 regions repeatedly

- objects stored in regions

- only compare nearby regions when checking objects

- adv: efficient for multiple objects

- disadv: tree overhead, trade-off between list mngmnt vs object comparisons

What is the narrow phase?

process of precise collision detection between objects that survived broad phase

How is convex polygon collision handled?

- SAT tests overlap for convex shapes

- Non-convex broken into smaller convex shapes

- May need to distinguish internal/external edges for collision response

How are curved shapes tested for collision?

- Circle-vs-AABB with Voronoi regions

- test overlap by checking regions nearest to particular edge/corner satisfying equation

What are Voronoi Diagrams?

- Partitions 2D space into distinct regions

- based on proximity to a feature of a shape

- feature: edge, corner

How should non-circular curved shapes be handled for collision?

- semicircles / quarter-circles easy

- ellipses, etc. should be avoided or use rasterization

When is line intersection used?

To find the exact collision point

How do we know when two lines intersect?

If both:

- are not parallel

- parameter values are between 0 & 1

How is Circle & Line intersection done?

- Substitute line equation into circle equation

- Test using discriminant

- (

What are kinetics?

- motion and the forces causing movement

- uses physics forces (mass, force, accel, Newton's laws)

- realistic accuracy but computationally expensive

What are kinematics?

- studies motion without considering forces

- direct manipulation of position/velocity

- simpler, lack realism

How is the moment of impact determined?

- Collisions happen between frames

- collision order matters

- use swept AABBs to check movement path between frames

What is the separating normal vector used for?

- Bounce direction

- friction

- displacement correction

Which separating normal vector should be used depending on the collision type?

- Vertex/Curve-to-line: line normal

- Line-to-line: either line normal

- Curve-to-curve: curve normal at contact point

What should objects not done when in motion?

- pass through walls

- intersect each other

What are the two types of animation constraints?

- Link Constraints: maintain distance (pairwise)

- Angle Constraints: maintain angle range (three-way)

What are ragdoll physics?

- Use of motion constrains to simulate body movement

- Forces on one part of body propagated to other objects through joints

What are some problems with ragdoll physics?

- Fixing one constraint may break another

- Instability of penalty springs

- Zero tolerance is expensive

- Shortest vector may not be the right vector

- Elastic vs plastic