Exercises 12 (Geometric Queries)

In our most recent lecture, we briefly brought up the question of how to detect collisions between two objects that are moving in time. Solving this problem exactly is challenging even for just a pair of triangles! In this quiz, we'll consider some simpler continuous---time collision detection tasks that help us understand how to attack this kind of problem.

Point-Point Intersection

Checking whether two points intersect is easy: just see if they have identical coordinates! But what if these points are moving? In particular, consider two points a, and b in 2D moving along linear trajectories

a(t) = (1-t) a0 + t a1

and

b(t) = (1-t) b0 + t b1

over a time interval 0 <= t <= 1. How would you test whether these points bump into each other? Describe your strategy explicitly in terms of equations in the variables t, a0, a1, b0, and b1.

Ball-Ball Intersection

In reality, it's highly unlikely that two points will ever actually hit each other---imagine two particles of dust flying through deep space. However, as anyone who's ever played dodgeball knows, it is possible that two balls might hit each other mid-flight. Suppose in particular that our dodgeballs again have linear trajectories a(t) and b(t), but this time they have radii ra, rb > 0, and_t_ can take any value (i.e., it no longer has to be between 0 and 1).

1. Write an equation for the center of each ball as a function of time.
2. Write the condition that must be satisfied in order for the two balls two intersect.
3. The balls might intersect at many moments of time. What's a problem we can solve to determine the time t* at which they intersect the most, i.e., when there's the largest overlap between the two balls?
4. Write down a closed-form solution for the time t* of greatest overlap. [Hint: substitute complicated expressions for single variables whenever possible, in order to simplify your calculations.]
5. Suppose you evaluate your expression for t*, for a given pair of moving balls. How will you know if the balls ever overlapped?

Point-Segment Intersection

It's also possible that for a moving point to collide with a moving line segment---this test starts to be useful for, say, checking if two triangles collide. In particular, consider a point following a linear trajectory

a(t) = (1-t) a0 + t a1

and an edge with endpoints p, q both following linear trajectories

p(t) = (1-t)p0 + t p1,

q(t) = (1-t)q0 + t q1,

all in the time interval 0 <= t <= 1.

1. Write an explicit equation for the segment between p and q at time t.
2. Write a simple equation whose solution describes where and when the point intersects the segment. Suppose you have values that satisfy this equation. What conditions on these values indicate that an intersection occurs? (You do not have to solve this equation yet.)
3. What are the unknowns in the previous equation, and what kind of equation is it with respect to these unknowns?
4. Re-write the equation in a standard form of "coefficients times variables."
5. How would you go about solving this equation? You don't have to give the solution; just sketch out the steps you would take to solve it.
6. Suppose you had the solution values. What conditions on these values indicate that an intersection occurs?