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

#### Bounding Box

Although the mathematics of the bounding sphere/circle algorithm are very straightforward, the obvious problem in your case is that the object (polygon) is being approximated with a circular object. This may or may not be appropriate. For example, take a look at Figure 8.39. It depicts a polygonal object that has general rectangular geometry. Approximating this object with a bounding sphere would induce a lot of errors, so it’s better to use a geometrical entity that’s more like the object itself. In these cases, you can use a bounding box (square or rectangle) to make the collision detection easier.

Figure 8.39 Using the best bounding geometry for the job.

Creating a bounding rectangle for a polygon is done in the same manner as for a bounding sphere, except that you must find four edges rather than a radius. I usually like to call them (max_x, min_x, max_y, min_y) and they’re relative to the center of the polygon. Figure 8.40 shows the setup graphically.

Figure 8.40 Bounding rectangle (box) setup

To find the values for (max_x, min_x, max_y, min_y), you can use the following simple algorithm:

  1. Initialize (max_x=0, min_x=0, max_y=0, min_y=0). This assumes that the center of the polygon is at (0,0).
  2. For each vertex in the polygon, test the (x,y) component against (max_x, min_x, max_y, min_y) and update appropriately.

And here’s the algorithm coded to work for your standard `POLYGON2D` structure:

    int Find_Bounding_Box_Poly2D(POLYGON2D_PTR poly,

                                 float &min_x, float &max_x,

                                 float &min_y, float &max_y)

    {

    // this function finds the bounding box of a 2D polygon

    // and returns the values in the sent vars

    // is this poly valid?

    if (poly->num_verts == 0)

        return(0);

    // initialize output vars (note they are pointers)

    // also note that the algorithm assumes local coordinates

    // that is, the poly verts are relative to 0,0

    max_x = max_y = min_x = min_y = 0;

    // process each vertex

    for (int index=0; index < poly->num_verts; index++)

        {

        // update vars – run min/max seek

        if (poly->vlist[index].x > max_x)

           max_x = poly->vlist[index].x;

        if (poly->vlist[index].x < min_x)

           min_x = poly->vlist[index].x;

> Note: Notice that the function sends the parameters as “call by reference” using the `&` operator. This is similar to using a pointer, except that you don’t have to dereference. Moreover, unlike a pointer, `&` references are aliases.

        if (poly->vlist[index].y > max_y)

           max_y = poly->vlist[index].y;

        if (poly->vlist[index].y < min_y)

           min_y = poly->vlist[index].y;

    } // end for index

    // return success

    return(1);

    } // end Find_Bounding_Box_Poly2D

You would call the function like this:

    POLYGON2D poly; // assume this is initialized

    float min_x, min_y, max_x, max_y; // used to hold results

    // make call

    Find_Bounding_Box_Poly2D(&poly, min_x, max_x, min_y, max_y);

After the call, the min/max rectangle will be built and stored in (min_x, max_x, min_y, max_y). With these values, along with the position of the polygon (x0,y0), you can then perform a bounding box collision test by testing two different bounding boxes against each other. Of course, you can accomplish this in a number of ways, including by testing if any of the four corner points of one box are contained within the other box, or by using more clever techniques.

> Note: I could have used a single `if` statement along with another `&&` to connect the two terms, but this code more clearly illustrates the linear separability of the problem—that is, the x- and y-axes can be processed independently.

#### Point Containment

In light of my last statement about testing if a point is contained within a rectangle, I thought it might be a good idea to show you how to figure out if a point is contained within a general convex polygon. What do you think? Obviously, figuring out if a point is within a rectangle is no more than the following:

Given rectangle (x1,y1) to (x2,y2) and that you want to test (x0,y0) for containment:

    if (x0 >= x1 && x0 <= x2) // x-axis containment

       if (y0 >= y1 && y0 <= y2) // y-axis containment

          { /* point is contained */ }

Let’s see if you can figure out if a point is contained within a convex polygon, as shown in Figure 8.41. At first, you might think that it’s an easy problem, but I assure you that it’s not. There are a number of ways to approach the problem, but one of the most straightforward is the half-space test. Basically, if the polygon you’re testing is convex (which it is in this case), you can think of each side as a segment that is colinear with an infinite plane. Each plane divides space into two half-spaces, as shown in Figure 8.42.

Figure 8.41 The setup for a point in polygon containment testing.

Figure 8.42 Using half-spaces to help solve the point in a polygon problem.

If the point you’re testing is on the interior side of each half-space, the point must be within the polygon because of the convex property of the polygon. Thus, all you need to do is figure out a way to test if a point in a 2D space is on one side of a line or the other.

This isn’t too bad, assuming that you label the lines in some order and convert them to vectors. Then you’ll think of each of the line segments as a plane. Using the dot product operator, you can determine if a point is on either side of each plane or on the plane itself. This is the basis of the algorithm.

You may not be up to speed on vectors, dot products, and so on, so I’m going to hold off for this test and the accompanying algorithm until we cover 3D math—no need to confuse you here. However, I wanted you to at least understand the geometry of the solution. The details are just math, and any high-level organic or inorganic organism can perform math if taught properly… right?

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.