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

Breaking the last equation into (x,y) components,

    s*S2x – t*S1x = p0x – p2x

    s*S2y – t*S1y = p0y – p2y

We have two equations, two unknowns, push into a matrix and solve for (s,t):

    |S2x     -S1x ||s| = |(p0x – p2x)|

    |S2y     -S1y ||t|   |(p0y – p2y)|

         A            X  =        B

Using Cramer’s Rule we have the following:

Multiplying all this stuff out, you get

    s = (-S1y*(p0x–p2x) + S1x*(p0y–p2y))/(-S2x*S1y + S1x*S2y)

    t = ( S2x*(p0y–p2y) - S2y*(p0x–p2x))/(-S2x*S1y + S1x*S2y)

There’s no need to test for intersections of two lines segments if their bounding boxes don’t overlap.

Then once you have found (s,t), you can plug either of them into

    U = p0 + t*S1

    V = p2 + s*S2

and solve for U(x,y) or V(x,y). However, for s,t to be valid both of them must be in the range of (0..1). If either of them is out of range then there is NO intersection. Referring to the worked example in Figure 13.31, let’s see if the math works:

    p0=(4,7), p1=(16,3),  S1=p1-p0=<12,-4>

    p2=(1,1), p3=(17,10), S2=p3-p2=<16,9>

Figure 13.31 A worked line segment intersection example.

And we know that:

    s = (-S1y*(p0x–p2x) + S1x*(p0y–p2y))/(-S2x*S1y + S1x*S2y)

    t =  (S2x*(p0y–p2y) - S2y*(p0x–p2x))/(-S2x*S1y + S1x*S2y)

Plugging in all the values we get

    s = (4*(4-1) + 12*(7-1))/(17*4 + 12*10)   = 0.44

    t = (17*(7-1) – 10*(4-1))/ (17*4 + 12*10) = 0.383

Since both 0<=(s,t)<=1, we know that we have a valid intersection and thus either s or t can be used to find the intersection point (x,y). Let’s use t, shall we?

    U(x,y) = p0 + t*S1

           = <7,7> + t*<12,-4>

Plugging in t=.44, we get

           = <7,7> + 0.44*<12,-4> = (9.28, 5.24)

which is indeed the intersection. Isn’t math fun?

As for using all this technology, I have created a demo of a ball bouncing off the interior of an irregularly shaped polygonal 2D object. Take a look at `DEMO13_7.CPP|EXE`. A screen shot is shown in Figure 13.32. Try editing the code and changing the shape of the polygon.

Figure 13.32 A bouncing ball trapped in an irregularly shaped polygon demo.

Finally, you may want to try another heuristic when finding a collision trajectory vector. In the previous example we used the velocity vector as one test segment. However, it may make more sense to create a vector that is the length of the radius of the ball and then drop it from the center perpendicular to the edge being tested. This way you catch scathing collisions, but it’s a bit more complex and I’ll just leave it as an exercise.

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.