Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Succinct

Logical Interpretation: Intersection of 2 2d lines expressed as vectors and dots.

This topic is 5281 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

Ok folks, I have an interesting question. I recently needed to solve some 2d line intersections. First I found a few articles here explaining the algo from either the graphics or game gems books. The articles didn''t explain the math too much - they just presented it and explained what the solutions represented -so I went and solved the equations myself, just to make sure I understood what those guys were doing and how they drew the conclusions they had. I came to a slightly different solution than them, but it turned out to be the same values, just with different arrangements of some negative signs. I felt confident with what they''d presented, and that I understood how they came to that solution. I looked at it a little bit more, and I realized that the solutions they have a basically dot products of 2d vector sums. Without really understanding what''s being dotted with what, I just used some standard substitutions to come to a vector form for the same equations. The vector code works, but I''m not positive why, other than that it matches the simultaneous solution. Neglecting pathological cases, such as parallel lines (denominator of 0), the code is pretty much:
	#ifndef USE_VECTOR_SOLUTION
		float Denominator = (B.x - A.x)*(D.y - C.y) - (B.y - A.y)*(D.x - C.x);
		float rNumerator = (A.y - C.y)*(D.x - C.x) - (A.x - C.x)*(D.y - C.y);
		float sNumerator = (A.y - C.y)*(B.x - A.x) - (A.x - C.x)*(B.y - A.y);
	#else 
		CVector l1 = B - A;
		CVector l2 = D - C;
		float Denominator = l1 | -l2.CalcPositivePerp();
		CVector lCommonPerp = (C - A).CalcPositivePerp();
		float rNumerator = (lCommonPerp | l2);
		float sNumerator = (lCommonPerp | l1);
	#endif

	float DenominatorInverse = 1.0f/Denominator;
	float r = rNumerator*DenominatorInverse;
	float s = rNumerator*DenominatorInverse;
In this example, CalcPositivePerp() uses the 2d trick to find a perp line: swap the terms, and invert one. The "positive" perp in this case is found by inverting the y, after the swap, so (x,y) becomes (-y,x). It''s "positive" because it points in the direction of positive angular rotation, were the line to be in standard position. The | operator means dot, so A | B is A.DotProduct(B). So, what I''m curious about is how to logically interpret what''s going on there. For instance, the denominator is cosine of the angle between the first line and the negative perpendicular of the second line, times both of their lengths. Why is that? Why would the solution of their intersection include this as a term? Why would it be divided by it? It seems that a few projections are going on, along perps to the line shared between both line''s origins, and a mess of other things. Has anyone seen this solution before? Might anyone be able to shed some light on the what''s here rather than the how''s? Thank you for your bandwidth, Succinct

Share this post


Link to post
Share on other sites
Advertisement
To find the intersection between two lines, you can first put them in the vector form (a, b, c), from the standard equation for a line, ax + by + c = 0. When you take the cross product of both line vectors, you end up with a point in homogeneous coordinates (x, y, w). When you divided everything by w, you get (x/w, y/w, 1), which is the intersection in the Euclidean plane.

If you take a close look at the code they provide, it closely resembles a cross product operation, however they make use a few tricks so that they don''t have to directly calculate c. It definitely isn''t easy to reverse engineer, so I suggest you draw a picture with all the vectors.

Share this post


Link to post
Share on other sites
I haven''t seen the actual graphics (game?) gems code, just a few posts here and there on gamedev''s forums. The math I worked out started off as the simultaneous equation:

A + r(B - A) = C + s(D - C)

which expands to the two equations:
Ax + r(Bx - Ax) = Cx + s(Dx - Cx)
Ay + r(By - Ay) = Cy + s(Dy - Cy)

Eventually you can solve them for r and s:
r = ((A.y - C.y)*(D.x - C.x) - (A.x - C.x)*(D.y - C.y))/((B.x - A.x)*(D.y - C.y) - (B.y - A.y)*(D.x - C.x))
s = ((A.y - C.y)*(B.x - A.x) - (A.x - C.x)*(B.y - A.y))/((B.x - A.x)*(D.y - C.y) - (B.y - A.y)*(D.x - C.x))

Terms like (A.y - C.y)*(D.x - C.x) - (A.x - C.x)*(D.y - C.y) look frightfully similar to dot products, so after a little bit of rearranging and finding some perpendiculars, I found that the vector solution I had in the last post was exactly the same.

I didn''t really reverse engineer anything - I just expressed it in a different form that I derived myself, and I don''t really understand why that form works.

Are we talking about the same thing? 6 in one, half dozen in the other?

Share this post


Link to post
Share on other sites
with vector maths, it''s quite simple.

you have two segments [A0, B0], [A1, B1].

imagine the 2D plane of the screen, being the floor, and you are looking straight down.

imagine the segment [A1, B1] being actually part of a plane the stretches perpendicular to the screen, and you are looking right down an edge of it.

now, the intersection of [A0, B0] with [A1, B1] is like intersecting that plane with a segment [A0, B0].

The normal of the plane passing through [A1, B1] and perpendicular to the screen is simply the vector perpendicular to the edge [A1, B1], and then, you are trying to find an intersection of that plane with the line [A0, B0].

so normal of the plane N1 is Vector(B1.y - A1.y, A1.x - B1.x), or (B1 - A1) x Vector(0, 0, 1), and the distance to the origin is d1 = (N1 * A1)

so it''s a standard line/plane equation solving.

P is on segment [A0, B0] if P = A0 + t0.D0, [eq1]
where D0 = (B0 - A0), 0
P is on the plane if P.N1 = d1 [eq2]
where N1 = (B1.y - A1.y, A1.x - B1.x), d1 = N1.A1

so, replace P in [eq2] with P in [eq1], and you get

A0.N1 + t0*(D0.N1) = d1
t0 = (d1 - A0.N1) / (D0.N1)

if t0 < 0, or t0 > 1, then there is no intersection.

now, to get t1 on the other line, you have two solutions. you can swap the segments around and repeat the process, or calculate the point of intersection, and calculate it''s projection parameter on the second segment

P = A0 + t0 * (B0 - A0)
t1 = (P - A1).(B1 - A1) / (B1 - A1).(B1 - A1)

again, if t1 < 0, or t1 > 1, no intersection.

if you expand the equations from vector maths plain scalar operations like above, you should find the same set of equations than the one given when doing the other method.

you can also expand it to 3D lines [A0, B0], and [A1, B1]. create a plane passing through one of the lines, and parallel to the vector (D0 x D1), where D0 = (B0 - A0), D1 = (B1 - A1).

Share this post


Link to post
Share on other sites
ahhh. Now THAT''s what I was looking for! How to visualize what''s going on. You hit the nail on the head, oliii. Thank you very much.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!