[gameprogrammer] Re: argh, math!

i like what you were saying about adding a v onto each equation, would there
be a different value of v for each equation or would it be one value for all
12 equations?

----- Original Message ----- 
From: "lukasz" <atp7@xxxxx>
To: <gameprogrammer@xxxxxxxxxxxxx>
Sent: Saturday, May 29, 2004 4:09 PM
Subject: [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
>
>



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

Other related posts: