[gameprogrammer] Re: argh, math!

W liście z sob, 29-05-2004, godz. 23:11, Rob Quill pisze: 
> OK, chose 3 equations and put them equal to each other. Say:
> 
> 3x + 2y + 5z + 3 = 0
> 6x + 3y + 3z + 1 = 0
> 5x + 7y + 2z + 8 = 0
> 
> (...)
> 
> Then substitute z into y = -7z - 5 to get y, then substitute y and z into
> any of the original equations to get x.
> 
> Then put the values of x, y and z through all your equations and check all
> the answers work out to be 0. If they do then the point exists, if they
> don't then it doesn't.
> 
> Easy, huh?
> 

Not that easy. You find the intersection point of 3 arbitrary planes,
which needs not to be on the other planes or even inside the common
polyhedron. Totally wrong approach.

> > lets say you have 12 of these:
> >
> > Ax+By+Cz+D > 0
> >
> > how could you be able to tell if there is some value for x,y,z that
> > satisfies all 12 equations?

One way is to use linear programming. The idea is to add extra unknowns
to transform inequalities into equalities, for instance

Ax + By + Cz + D > 0

becomes

Ax + By + Cz + D + v = 0

where an extra variable v > 0.

Then you use the simplex algorithm to find a solution. If the solution
is found, there're points inside the region. Refer to literature or the
Internet for details.


An other approach is more specific: the two "boxes" overlap if (1) one
is inside the other, or (2) there's a side of one box that intersects
with a side of the other box.

In order to test (1), say Box1 being inside Box2, you select a random
point of Box1 (e.g. the intersection point of 3 of its planes that form
a vertex), and check whether it's inside Box2 (put the point's x, y, z
into all 6 inequalities of planes forming Box2, if all hold true, the
point is inside). If failed, you need to do similar test for whether
Box2 is inside Box1.

The above assumes the planes' normal vectors are headed inside the
"box." For each plane that does not satisfy this condition it is
necessary to multiply its coefficients: A, B, C, and D by (-1).

For (2) I suppose it is sufficient to compute all edges of, say, Box1,
then test whether any of them intersects with any side of Box2; this can
done by simply intersecting a plane with a line, then checking if the
resulting point is within ranges for both figures. I believe there're
faster algorithms doing this, though.

Lukasz M. Nojek



---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html

Other related posts: