Jump to content
  • Advertisement
Sign in to follow this  
heron3d

is it possible to check if 2 vectors are criss crossing?

This topic is 2565 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This one is for the math gurus out there. I have 2 starting points and 2 direction vectors with variable magnitudes in 3d space. How would I check if the vectors criss cross from the view point of an arbitrary camera angle?

heron

Share this post


Link to post
Share on other sites
Advertisement

This one is for the math gurus out there. I have 2 starting points and 2 direction vectors with variable magnitudes in 3d space. How would I check if the vectors criss cross from the view point of an arbitrary camera angle?

heron


multiply them with the cameras projection matrix and then do a line/line intersection test ?

Share this post


Link to post
Share on other sites

multiply them with the cameras projection matrix and then do a line/line intersection test ?


when you say projection matrix are you referring to the camera's transformation matrix?

Share this post


Link to post
Share on other sites

[quote name='SimonForsman' timestamp='1322957061' post='4890262']
multiply them with the cameras projection matrix and then do a line/line intersection test ?


when you say projection matrix are you referring to the camera's transformation matrix?
[/quote]

No, it is projection matrix, allthough you have to do the transformation matrix aswell first.

I'm not 100% sure about the math though, i think doing (Vector * Transform) * Projection would give you the vectors on an plane. (You want to project the vectors onto a plane that is parallel to the cameras near or far plane, at that point it will just be a basic line intersection test)

If you are using OpenGL you can use gluProject to simplify it, (It takes a x,y,z coordiante, a modelview matrix, projection matrix and viewport and gives you the screenspace coordinates for that point) (There should be third party libraries around that does projection without requiring a specific API aswell)

Share this post


Link to post
Share on other sites
To do the transform you need to create the matrix

transform = cameraProjection * cameraTransform

to transform a 3d point multiply a 4d vector by the transform where the 4th component is a 1

transformedVec = transform * (x, y, z, 1)

then multiply the transformedVec by the inverse of the 4th component of transformedVec

wInv = 1.0 / transformedVec.w (w is the 4th component of the the 4d vector)

transformedVec *= wInv

then you take the x,y of the final transformedVec and use that for a 2d line segment collision.

So in code



// classes needed
class Matrix;
class Vector3; // x, y, z
class Vector4; // x, y, z, w
class Ray; // Vector3 origin, Vector3 direction
class Segment; // Vector3 a, Vector3 b

// method for matrix
Vector3 Matrix::tranformPointWithPerspective(const Vector3& in)
{
Vector4 vec4 = Vector4(in.x, in.y, in.z, 1.0);

Vector4 transVec = (*this) * vec4;

double wInv = 1.0 / transVec.w;

return Vector3(transVec.x * wInv, transVec.y * wInv, transVec.z * wInv);
}

// then to do a segment collision
// this method could go in camera class
bool doesCollideInView(const Ray& rayA, const Ray& rayB)
{
Matrix resultTranform = perspectiveMatrix * cameraTransform; // perspectiveMatrix * cameraTransform; // this could be done once and saved somewhere if you need to do many collision checks

Segment segA(resultTranform.tranformPointWithPerspective(rayA.origin), resultTransform.tranformPointWithPerspective(rayA.origin + rayA.direction)); Segment segB(resultTranform.tranformPointWithPerspective(rayB.origin), resultTransform.tranformPointWithPerspective(rayB.origin + rayB.direction));

// then you ignore the z component on each segment and do a 2d segment collision to see if they overlap
// I wont provide the code for that, you should be able to find something like that

}



Hope that is clear

Share this post


Link to post
Share on other sites
so I got this equation to check for intersection: http://en.wikipedia.org/wiki/Line-line_intersection

the problem with this is that creates an accurate intersection ONLY if the first segment has an origin of (0, 0).

Is that how all line intersection equations work or should I find one that does not have a zero origin as a requirement?

Share this post


Link to post
Share on other sites

so I got this equation to check for intersection: http://en.wikipedia....ne_intersection

the problem with this is that creates an accurate intersection ONLY if the first segment has an origin of (0, 0).

Is that how all line intersection equations work or should I find one that does not have a zero origin as a requirement?


Where does it say one of the end points has to be the origin?

But eitherway you want an algorithm to tell you if the line segments themselves intersect, not if their infinite lines do, you don't even need to know where.

If you take the two line segments as rays (a + tu) and (b + sv) for t,s in [0,1] (aka given line x1 to x2, the ray is x1 + t(x2-x1)) then you can compute:

t = (b-a) perpdot v / u perpdot v
s = (b-a) perpdot u / u perpdot v

where [ux ; uy] perpdot [vx ; vy] = ux*vy - uy*vx

and check that 0 <= s,t <= 1, you can of course exit early at various points, and need to check u perpdot v is not zero (which indicates parallel lines)

Share this post


Link to post
Share on other sites

[quote name='heron3d' timestamp='1323135469' post='4890937']
so I got this equation to check for intersection: http://en.wikipedia....ne_intersection

the problem with this is that creates an accurate intersection ONLY if the first segment has an origin of (0, 0).

Is that how all line intersection equations work or should I find one that does not have a zero origin as a requirement?


Where does it say one of the end points has to be the origin?
[/quote]

It doesn't say but my tests show that it is a ray line intersection equation not a line to line intersection NOR a segment to segment intersection equation.

But the fact that it can show me the intersection at any point along the infinite line works to my advantage. I just wish the first line didn't have to be a ray at the origin.

Here is a sample of my tests.

Share this post


Link to post
Share on other sites

If you take the two line segments as rays (a + tu) and (b + sv) for t,s in [0,1] (aka given line x1 to x2, the ray is x1 + t(x2-x1)) then you can compute:


I'm having a little trouble visualizing your variables. Would it be too much trouble to request a diagram?:)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!