Tricks of the Windows Game Programming Gurus:Vector Rasterization and 2D Transformations

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

#### Computing the Intersection of Two Lines Using the Matrix Form

So it looks like a = m, b = -1, and c = (-m*x0 – y0). Now that you know how to transform the Point Slope form into the general form, you can move on to yet another method of solutions based on matrices. Let’s take a look.

Given two general linear equations in this form:

    a1*x + b1*y = c1

    a2*x + b2*y = c2

You want to find (x,y) such that both equations are simultaneously solved. In the previous example, you used substitution, but there’s another method based on matrices. I’m not going to go into the theory too much because I’m going to give you a crash course in vector/matrix math when you get to 3D. For now, I’m just going to show you the results and tell you how to find (x,y) using matrix operations. Take a look.

Let the matrix A equal

    |a1    b1|

    |a2    b2|

and X (the unknowns) equal

    |x|

    |y|

and finally, Y (the constants) equals

    |c1|

    |c2|

Therefore, you can write the matrix equation:

    A*X = Y

Multiplying both sides by the inverse of A, or A-1, you get

    A-1*A*X = A-1*Y

Simplifying:

    X = A-1*Y

That’s it! Of course, you have to know how to find the inverse of a matrix and then perform the matrix multiplication to extract (x,y), but I’ll give you some help here and show the final results:

    x = Det(A1)/Det

    y = Det(A2)/Det

where A1 equals

    |c1 b1|

    |c2 b2|

and A2 equals

    |a1 c1|

    |a2 c2|

In essence, you have replaced the first and second column of A with Y to create A1 and A2, respectively. Det(M) means the determinate of M and is computed as follows (in general).

Given a general 2×2 matrix M:

    M = |a b|

        |c d|

    Det(M) =  (a*d – c*b)

With all that in mind, here’s a real example:

    A*X       = Y

    5*x – 2*y = -1

    2*x + 3*y = 3

    A = |5 –2|

        |2  3|

    X = |x|

        |y|

    Y = |-1|

        | 3|

Therefore:

    A1 = |-1 –2|

         |3   3|

    A2 = |5  -1|

         |2   3|

Solving for x,y:

        Det |-1 –2|

            | 3  3|     (-1*3 – 3*(-2))

    x =    ---------- = ---------------- = 3/19

        Det |5  -2|     (5*3 – 2*(-2))

            |2   3|

        Det |5  –1|

            |2   3|     (5*3 – 2*(-1))

    y =    ---------- = ---------------- = 17/19

        Det |5  -2|     (5*3 – 2*(-2))

            |2   3|

Wow! Seems like a lot of drama, huh? Well, that’s what game programming is all about—math! Especially these days. Luckily, once you write the math code, you don’t have to worry about it. But it’s good to understand it, which is why I’m giving you a brief refresher on it.

Now that you’ve taken a little mathematical detour, let’s get back to the reason for all this—clipping.

#### Clipping the Line

As you can see, the concept of clipping is trivial, but the actual implementation can be a bit complex because linear algebra comes into play. At the very least, you have to understand how to deal with linear equations and compute their intersection. However, as I mentioned before, you can always take advantage of a priori knowledge about the geometry of the problem to help simplify the math, and this is one of those times.

Ultimately, you still have a long way to go to clip a line against a general rectangle, but we’ll get to that. Right now, let’s take a look at the problem and see if it can help to know that you’re always going to clip a general line against either a vertical line or horizontal line. Take a look at Figure 8.11.

Figure 8.11 Clipping against a rectangle is much easier than the general case.

You see in Figure 8.11 that you only need to consider one variable at a time here, either the x or the y. This greatly simplifies the math. Basically, instead of doing all the hard math (which you need to know once you get to 3D), you can use the Point Slope form of the line itself to find the intersection point by plugging in the known value for either a line of the form X = constant or Y = constant. For example, let’s say that your clipping region is (x1,y1) to (x2,y2). If you want to find where your line intersects the left edge, you know that at the point of intersection the x-coordinate must be x1! Thus, all you have to do is find the y coordinate and you’re done.

Conversely, if you want to find the point of intersection on a horizontal line such as the bottom of the clipping rectangle, y2 in this case, you know that the y-coordinate is y2 and you just have to find the x—get it? Here’s the math for computing the (x,y) intersections of a line, (x0,y0) to (x1,y1), with a horizontal line with value Y = Yh, and for a vertical line X = xv.

Horizontal Line Intersection—(x,Yh):

    We want x…

    Start with Point-Slope, m =(y1 – y0)/(x1 – x0)

    (y – y0)            = m*(x – x0)

    (y – y0)            = m*x – m*x0

    (y – y0)  + m*x0    = m*x

    ((y – y0) + m*x0)/m = x

    x = ((y – y0) + m*x0)/m

or

    x = 1/m * (y – y0) + x0

Vertical Line Intersection—(Xv, y):

    We want y…

    Start with Point-Slope, m =(y1 – y0)/(x1 – x0)

    (y – y0)            = m*(x – x0)

    y                   = m*(x – x0) + y0

And that’s how that goes. So now you can compute the intersection of a line with an arbitrary line and with a purely vertical or horizontal line (the important one in the case of rectangular clipping). At this point, we can talk about the rest of the clipping problem.

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.