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

## 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 on other sites

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 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 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 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 on other sites

To do the transform you need to create the matrix...

Hope that is clear

excellent! thank you HappyCoder.

##### 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 on other sites

so I got this equation to check for 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 on other sites

[quote name='heron3d' timestamp='1323135469' post='4890937']
so I got this equation to check for 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 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? • ### Game Developer Survey We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 9
• 56
• 16
• 19
• 26