Tricks of the Windows Game Programming Gurus:Playing God: Basic Physics Modeling

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

#### An Example of Vector Reflection

When I used to study mathematics, I used to read things like “R is a closed ring with an isomorphism on Q’s kernel.” I wouldn’t be as nutty as I am today if they just gave me an example once in a while! Alas, I don’t want you to end up running naked in the streets with a cape—one naked super hero game programmer is enough, so let’s try a real example.

Figure 13.26 shows the setup of the problem. I have made the bounce plane co-linear with the x-axis to make things easier.

Figure 13.26 A numerical example of vector reflection.

The initial velocity vector of our object is I=<4,-2>, N`'`=<0,1>, and we want to find F. Let’s plug everything into our equation:

    F =  2*N + I

      =  2*(-I . N')*N' + I

      = -2*(<4,-2> . <0,1>)*<0,1> + <4,-2>

      = -2*(4*0 + -2*1)*<0,1> + <4,-2>

      = 4*<0,1> + <4,-2>

      = <0,4> + <4,-2>

      = <4,2>

Lo and behold, if you look at Figure 13.26, that’s the correct answer! Now, there’s only one detail that we’ve left out of all this: determining when the ball or object actually hits the plane or line.

#### Intersection of Line Segments

You could probably figure this one out, but I’ll give you a hand. The problem is basically a line intersection computation. But the surprise is that we are intersecting line segments, not lines; there’s a difference. A line goes to infinity in both directions, while a line segment is finite, as shown in Figure 13.27.

Figure 13.27 Lines and line segments are very different.

The problem boils down to this: As an object moves with some velocity vector Vi, we want to detect whether the vector pierces through the collision plane or line. Why? Well, if an object is moving at velocity Vi then one frame or time click later it will be located at its current position (x0,y0)+Vi, or in terms of components:

    x1 = x0 + vix

    y1 = y0 + viy

Therefore, you can think of the velocity vector as a line segment that leads the way to wherever the object we are drawing is going. In other words, we want to determine whether there is an intersection point (x,y) of the line segments. Here’s the setup:

  Object Vector Segment: S1 = <p1(x1,y1) – p0(x0,y0)>
  Boundary Line Segment: S2 = <p3(x3,y3) – p2(x2,y2)>

You need the exact intersection point (x,y), so that when you compute the reflection vector F you start its initial position at (x,y). This is shown in Figure 13.28. The problem seems simple enough, but it’s not as easy as you think. Intersecting two lines is as easy as solving a system of 2 equations, but determining if two line segments intersect is a little harder. That’s because that although the segments are lines, they are finite, so even if the lines that the segments run along intersect, the segments may not. This is shown in Figure 13.29. Therefore, you need to not only determine where the lines that the segments define intersect, you need to see if this point is within both segments! This is the hard part.

Figure 13.28 Intersection and reflection.

Figure 13.29 Intersecting and non-intersecting segments.

The trick to solving the problem is using a parametric representation of each line segment. I’ll call U the position vector of any point on S1 and V the position vector of any point on S2:

  Equation 1: U= p0 + t*S1
  Equation 2: V= p2 + s*S2

with the constraint that (0 <= t <= 1), (0 <= s <= 1).

Figure 13.30 shows what these two equations represent.

Figure 13.30 The parametric representation of U and V.

Math Cramer’s Rule states that you can solve a system of equations AX=B, by computing xi = Det(Ai)/Det. Where Ai is the matrix formed by replacing the ith column of A with B.

Math

The determinate (Det) of a matrix in general is rather complex, but for a 2×2 or 3×3 it is very simple to remember. Given a 2×2 matrix the determinate can be computed as follows:

              A = |a b|  Det = (a*d – c*b)

                  |c d|

Referring to the figure, we see that as t varies from 0 to 1 the line segment from p0 to p1 is traced out and similarly as s varies from 0 to 1, the line segment from p2 to p3 is traced out. Now we have all we need to solve the problem. We solve equations 1 and 2 for s,t and then plug the values back in to either equation and find the (x,y) of the intersection. Moreover, when we find (s,t) if either of them is not in the range (0 to 1) then we know that the intersection was not within the segments. Pretty neat, huh? I’m not going to every detail of the entire derivation since this is in about 100,000 math books, but I’ll show you the important stuff:

Given:

    U = p0 + t*S1

    V = p2 + s*S2

solve for (s,t) when U = V,

    p0 + t*S1 = p2 + s*S2

    s*S2 – t*S1 = p0 – p2

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.