[gameprogrammer] Re: argh, math!

At 01:29 PM 29-05-04 -0700, you wrote:
>I dont know if this helps any, but i might be going about this the wrong
>way.
>
>Im making a portal engine and what i need to be able to do is be able to
>tell if a portal intersects with the frustum.
>
>i have the 6 planes of the frustum, and i have the 8 points of the portal
>(as well as the 6 planes of the portal). and need to be able to tell if the
>portal and the frustum overlap.
>
>is there a better way to do that maybe?

There may be an elegant solution, but here's a brute-force one FWIW.

The hardest case is testing whether the cubes have any overlap at all.
Easier would be to test if given faces, or given vertices, of the cube are
"close". But if u want to test for 2 cubes sharing _any_ volume (strict
interpenetration), u have to deal with cases where:
1 - one cube is entirely inside the other
2 - one or more vertices of one cube is interior to the other (corner overlap)
3 - neither cube has any vertex inside the other, but their edges overlap.

The most general case would require to test each of 12 edges of each cube
to see whether any edge of cube A crosses any side of cube B. I assume u
know how to derive the equation of an edge, and how to calculate the point
where that line intersects the plane of each face of the other cube. Then u
have to test whether that intersection point lies on that plane within the
4 bounding edges of that side, _and_ is between the endpoints of the edge
of cube A. Test the endpoints first because it's faster, and if it fails,
there's no intersection for that edge. Repeat for each edge of A vs each
side of B.

Then turn around and do the same test for each edge of B crossing any side
of A. If u don't test both ways, u might miss an intersection where cube B
sticks a corner thru a side of A. 

That will find every case except "completely contained", so last, test one
vertex of A to see if it's interior to B, and B vs A as well. 

Hmmm, computationally, this might be simplified. In fact, u might find it
more efficient to do some pre-screening, i.e. first do the simplest tests
which if passed mean they intersect, but which if failed prove nothing.

That would mean testing each vertex of A to see if it's interior to B, then
vice versa. But note, even if neither cube has any vertex inside the other,
they can still overlap at two edges, so if they all are outside you'll end
up doing the edge-plane intercept calculation anyway, to be sure.

Hmmm, i'm sure there's a simpler analytic calculation to solve this. A
simpler question to ask might be, does any plane exist which has all the
vertices of A on one side, and all the vertices of B on the other side?
Obviously if there is a dividing plane, the cubes don't intersect, and if
there isn't, they do.

Cast that way, your problem becomes finding the coefficients of Px + Qy +
Rz + S = 0, such that all 8 vertices of cube A lie on one side of the
plane, and all 8 vertices of B lie on the other side. Generally there are
either zero or an infinite number of such planes. This may be
computationally more difficult to solve, but it's a single test which gives
an unambiguous answer.

Interesting problem :)

HTH - grant

>----- Original Message ----- 
>From: "Kevin Jenkins" <gameprogrammer@xxxxxxxxxx>
>To: <gameprogrammer@xxxxxxxxxxxxx>
>Sent: Saturday, May 29, 2004 1:11 PM
>Subject: [gameprogrammer] Re: argh, math!
>
>
>> If I remember my linear algebra right, you have to put all 12 equations in
>a
>> matrix and do row reduction until you get a single 1 in each row.  Or
>> something like that :(
>>
>> ----- Original Message -----
>> From: "Alan Wolfe" <atrix2@xxxxxxx>
>> To: <gameprogrammer@xxxxxxxxxxxxx>
>> Sent: Saturday, May 29, 2004 1:14 PM
>> Subject: [gameprogrammer] Re: argh, math!
>>
>>
>> > Hey Rob,
>> >
>> > it sounds easy but nobody seems to be able to help :P
>> >
>> > lets say you have 12 of these:
>> >
>> > Ax+By+Cz+D > 0
>> >
>> > where in each of the 12 equations, there is a different value for A,B,C
>> and
>> > D.
>> >
>> > how could you be able to tell if there is some value for x,y,z that
>> > satisfies all 12 equations?
>> >
>> > ----- Original Message -----
>> > From: "Rob Quill" <rjquill@xxxxxxxxxx>
>> > To: <gameprogrammer@xxxxxxxxxxxxx>
>> > Sent: Saturday, May 29, 2004 1:01 PM
>> > Subject: [gameprogrammer] Re: argh, math!
>> >
>> >
>> > > OK, my maths isn't great, but they will be overlapping if the lines
>> > > intersect, so by putting two of the equations equal to each other and
>> > > solving you can see if there is a point of intersection.
>> > >
>> > > That sounds a bit too simple, so maybe I have mis-interpretted the
>> > problem.
>> > >
>> > > Or thinking about it, could you not use vectors? If you had the vector
>> > > equations you could use:
>> > >
>> > > a.b = |a||b|cos(x)
>> > >
>> > > But again, it seems too simple. Is it that hard to solve a equation 12
>> > > times.
>> > >
>> > > Rob
>> > >
>> > > Rob
>> > > ----- Original Message -----
>> > > From: "Alan Wolfe" <atrix2@xxxxxxx>
>> > > To: <gameprogrammer@xxxxxxxxxxxxx>
>> > > Sent: Saturday, May 29, 2004 8:52 PM
>> > > Subject: [gameprogrammer] argh, math!
>> > >
>> > >
>> > > > hey everyone
>> > > > I have a math problem im trying to solve for my game and am having
>> > > difficulty :P
>> > > >
>> > > > i have a "box" defined by 6 planes in the form of: Ax+By+Cz+D=0,
>where
>> > > A,B,C and D are known constants for each equation.
>> > > >
>> > > > the box doesnt have to have corners at right angles, but it's
>assumed
>> to
>> > > be concave.
>> > > >
>> > > > what im trying to do is take 2 of these "boxes" and see if they
>> overlap
>> > at
>> > > all.
>> > > >
>> > > > so basicly from what i can tell i have 12 plane equations and what i
>> am
>> > > trying to do is find if there are any sets of X,Y,Z which satisfy all
>12
>> > > equations.
>> > > >
>> > > > I asked around how to solve systems of inequalities but people keep
>> > saying
>> > > "graph it", which doesnt help me any :P
>> > > >
>> > > > Does anyone know how to do this? I'm starting to think that there is
>> no
>> > > solution ::cry:: hehe
>> > > >
>> > > >
>> > > >
>> > > > ---------------------
>> > > > To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>> > > >
>> > > >
>> > > >
>> > >
>> > >
>> > >
>> > >
>> > > ---------------------
>> > > To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>> > >
>> > >
>> >
>> >
>> >
>> > ---------------------
>> > To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>> >
>> >
>> >
>> >
>>
>>
>>
>> ---------------------
>> To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>>
>>
>
>
>
>---------------------
>To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>
>
>
>



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

Other related posts: