simple geometry problem with lines and squares

[Moach]

ok... i've cornered myself again in my ever-fumbling efforts in math.....

this time, it's a probably very basic geometry problem... but i'm having a hard time figuring it out, mostly because, i'm not sure how to call it... so googl'ing for a solution is proving very difficult...

so, allow me to express it graphically... look:

this is brought to me by the need to check for collisions inside a quad-tree environment using a per-quad sectioned surface... (to be used in a physics simulation system)

ok - here's what we have - notice the two yellow lines from the center of the box towards the "surface" planes... let's call those out "surface normal vectors"


those vectors are how the surface sections are parametrized in the quadtree - the angle of the normal (relative to "up") and the distance of the surface from the quad's center along that normal are all the data we have to define the surface inside a quad (gotta save up memory)

unlike depicted above, only ONE surface is allowed per quad

i've drawn the two surfaces because therein lies my problem - every solid object in my sim has it's own little quadtree

when two objects overlap, their own local quadtrees are cross-compared, by transforming positions from one objects local space to that of the other

whenever overlapping quads are found in the two object's trees - and those two have surface sections, a test must be performed in order to calculate if there's a collision along those sections

(are you still with me?)


what i need right now is - how does one determine that there's an intersection inside a quad, based on the two normal vectors?

in other words:
what's the relationship between those vectors and whether or not there's an intersection within that square?


or in the worse case - what name would this problem be known by? so i can at least properly google it :facepalm:


thanks in advance

 

[Radu094]

Well, if I understood your quad-tree system, the point is that you will ALWAYS have a mathematical intersection unless the two surfaces are parallel or identical.

So the point is more of a "how far away from the center is the intersection point?" is it inside the square or not?

You can simply use the two triangles I've attempted to draw out there to figure it out.

You will need the angle difference from your two normals (called it delta, and it equals a+b in my drawing) and the magnitude of the two yellow lines (A and B in my drawing).

using that and a bit of trigonometry you can determine C (ie. the distance from the center to the intersection point), and find if the intersection is within the square or not.
so:
[math]
\frac{A}{cos(a)} = \frac {B}{cos(b)}
[/math]

[math]
cos (a) = cos(delta-b) = cos(delta)*cos(b) + sin (delta) * sin (b)
[/math]

[math]
\frac{A}{cos(delta)*cos(b) + sin (delta) * sin (b)} = \frac {B}{cos(b)}
[/math]

you already know A,B and delta .. so that will be a quadratic trig. equation to solve for b

once you get b out of there

[math]
C = \frac{B}{cos(b)}
[/math]

and the angle of C is just the angle of B (relative to up) plus or minus 'b' depending if you used clockwise angles or not.

 

[Moach]

whoa dude!! THANKS! :woohoo: :10sign:

that's exactly it! may the be with you!

if i can figure out C, it's all a matter of finding it inside the quad - if either x or y are off-limits, then no collision! :thumbup:

alright! thanks dude! really!