Презентация на тему Collision Detection

just pass through each other
Two parts to handling collisions
Collision

problems
Object intersections
Object proximity
Path planning

between simple objects
E.g. sphere intersection boils down to point-point

between two points P0 and P1, or

P and vector v
Break vector w = Q –

^

^

^

v

Q

P

w

w||

w⊥

^

normalized:

to u and v or



Two equations
Two unknowns

P0
u

Q0
v
P(sc)
Q(tc)


wc

lines
If lies on both segments, done
Otherwise clamp against nearest

objects expensive
Provide simple object that surrounds them to cheaply

model
For each point, compute distance from center, save max

for center?
Local origin of model
Centroid (average of all points)
Center

centers
If d < r1 + r2, colliding
Note: d2 is

d

r1

r2

model
Compare points to min/max vertices
If element less/greater, set element

(min x, min y)

(max x, max y)

to world axes
Recalc when object changes orientation
Collision checks are

in min,max vertices
If min2 > max1 or min1 >

min1

max1

min2

max2

with local object coordinate system
Much tighter, but collision calcs

plane between boxes exists
Project box extent onto plane vector,

c∙v

b∙v

a∙v

a

b

c

take dot product using only absolute values


Check against axes

way to compute
Calc bounding box
Use long axis for length
Next

line segment
Oriented shape w/faster test than OBB
Test path collision

is line segment with surrounding radius
Compute distance between line

is not to be trusted
Precision worse farther from 0
Use

necessary
Start with cheap tests, move up the list
Sphere
Swept Sphere
Box
May

good fit
AABB -- still cheap, but must recalc and

process
Broad phase
Cull out non-colliding pairs
Narrow phase
Determine penetration and contact

pair once
Flag object if collisions already checked
Only check moving

hierarchy and build bounds for each level of hierarchy
Finer

to maintain bounding information
Propagate transforms down to children
Propagate bound

areas
Only check your area and neighbors
Simplest: uniform
Slabs
Grid
Voxels

extents of objects
Sweep from min x to max x
As

kd-trees
Room-portal
Choice depends on your game type, rendering engine, memory

nearby
Check those first
Can take memory to store information

to find
Contact point
Normal
Penetration (if any)

one (or more) regions



A bit messy to deal with
Many

pair of contact features
Only consider E-E and F-V pairs
Infinite

of edges
Normal is cross product of edge vectors
For F-V:
Point

points
Ex: two concave objects



Store as part of collision detection

normal n (after you normalize)



Penetration distance p is p =

c1

c2

penetration distance along extended normal





If touching, where normal

v = ½(c1 + r1n + c2 - r2n)

^

^

c1

c2

hard to implement
Closest features generally same from frame to

easy to implement
Finds point in Configuration Space Obstacle closest

too large for object speed, two objects may pass

interval
Simulate between slices




Same problem, just reduced frequency

volumes




If volumes collide, may collide in frame
With more work

and computing
Break into two phases: broad and narrow
Be careful

Ian Shamos, Computational Geometry: An Introduction, Springer-Verlag, New York,