Help with Maxscript to find where a line segment would intersect another if extended

[mikegold10]

Please refer to the image at the bottom for the description, below.

Given two hypothetical line segments:

a from point3 A1 to point3 A2
b from point3 B1 to point3 B2

If we were to create a new segment, c, which extends from point3 A2 to point3 B3 where it intersects segment b, making c an extension of segment a from its end point A2 to the new point B3 (i.e., segment c should be collinear with a), how would we go about doing this using Maxscript and let’s assume all coordinates are in World space to make life simpler?

Note that the angle of intersection, 𝛂, could be acute, right, or obtuse, depending on the direction of a and b.

To make things simpler, I am most interested in a function that returns the new intersection point3 B3, given point3s A1, A2, B1 and B2 as parameters, assuming of course that segment a would intersect segment b if projected as indicated by c. I suppose the function could return undefined if a and b are parallel or skew (i.e., not co-planar) with respect to each other.

fn findIntersectionPoint A1 A2 B1 B2
(
  B3=[0,0,0] -- Point of intersection, to be calculated
  /* Calculation code
  ...
  */
  B3
)

Thanks you for your help!

[Serejah]

didn’t you ask that question on scriptspot?

[Senorpablo]

There are a lot of useful calculations here, including line intersections:

Geometrical calculations : points, lines, planes : intersections, distances, angles

nice stuff takes me back to highschool math days…

[mikegold10]

I read that, but it didn’t have a way to go from two lines that don’t presently intersect to making them intersect.

[denisT]

here is the pure math for 2d intersection. it also tells if intersection was happened IN or OUT of bounds (what was the point for me).

it’s a c++ code (i don’t remember where i found the algorithm. so sorry for not giving someone a credit)

int RayIntersect2D(Point3 p11, Point3 p12, Point3 p21, Point3 p22, Point3& pt) 
{
	float z  = (p12.y-p11.y)*(p21.x-p22.x)-(p21.y-p22.y)*(p12.x-p11.x);
	float ca = (p12.y-p11.y)*(p21.x-p11.x)-(p21.y-p11.y)*(p12.x-p11.x);
	float cb = (p21.y-p11.y)*(p21.x-p22.x)-(p21.y-p22.y)*(p21.x-p11.x);
	
	if ((z == 0) && (ca == 0) && (cb == 0))
	{
		return 0; // same line
	}
	else if (z == 0) return 0; // parallel
	else
	{
		float ua = ca/z;
		float ub = cb/z;
		
		pt.x = p11.x + (p12.x - p11.x)*ub;
		pt.y = p11.y + (p12.y - p11.y)*ub;
		pt.z = 0;

		if (ua >=0 && ua <= 1 && ub >=0 && ub <= 1) 
		{
			return 1; // in bounds
		}
		else return -1;
	}
}

i hope someone will help you to translate it on MXS (if you can’t do it yourself).

[Senorpablo]

To make the line intersect, move one of the lines endpoints to the point of intersection. In your illustration, you would set the position of A2 to be the point of intersection(B3).

That’s all easier said than done, as there are many combinations and possibilities. You’ll have to do some other tests to figure out which point to move.

[mikegold10]

To make the line intersect, move one of the lines endpoints to the point of intersection. In your illustration, you would set the position of A2 to be the point of intersection(B3).

If I knew the exact distance I need to move point A2 along the direction of the unit vector formed by (nomalize A2-A1) to make it lie on B3 (i.e., the exact length of segment c), my problem would be a non-problem, because B3 is trivial to calculate if you know the length of c. It simply comes down to:

B3 = A2 + (normalize A2-A1) * (length c)

Unfortunately, determining the length of segment c in order to substitute it for the expression (length c), above, since we don’t know what c is (i.e., it’s part of the problem), does not seem possible without prior determination of point B3.

So, going this route would create a “chicken and egg problem.” (length c), or more generally the definition of line segment c, depends on knowledge of the coordinates of point B3 and the coordinates of point B3 are determined in the code above based on the length of segment c.

[Senorpablo]

The distance you need to move a2 is the distance from a2 to b3(intersection), yes? Or length b3-a2.

In reality, you probably also need to determine the farthest end point, which in reality could be a1 or a2, as the intersection test probably doesn’t care which way the line is pointing.

If you just calculate the farthest point, either a1 or a2, from the intersection b3, you know that’s one end. The other end is b3.

If (length b3-a1) > (length b3-a2) then line = b3-a1
else line = b3-a2

[mikegold10]

The distance you need to move a2 is the distance from a2 to b3(intersection), yes? Or length b3-a2.

Yes, that is correct, any of the following are correct:

(distance A2 B3)
(length B3-A2)
(length c)
// They all produce the same value, the length of segment c

In reality, you probably also need to determine the farthest end point, which in reality could be a1 or a2, as the intersection test probably doesn’t care which way the line is pointing.

Let’s assume I even know that the farther endpoint is A1, since this is also very easy to determine. It’s the endpoint of a that is the greatest distance from both B1 and B2.

If you just calculate the farthest point, either a1 or a2, from the intersection b3, you know that’s one end. The other end is b3.

If (length b3-a1) > (length b3-a2) then line = b3-a1
else line = b3-a2

All of the above is true, but as I said previously, I don’t know the coordinates of B3. That’s the problem I am trying to solve - to find the coordinates B3 or to find the length of segment c so I can use it to calculate said coordinates.

[aaandres]

My God!
Please, check DenisT code and try to understand it.

[mikegold10]

pt.z = 0;

Before pushing said code down my throat, consider the validity of the single line above for all cases where the lines intersect!

[Senorpablo]

Yes. That is why you need the formula from the page I linked to, or the one Denis posted. It calculates the position of b3 based on the inputs a1 a2 b1 b2.

It’s all there. You have the basic understanding of vector math needed to implement those functions.

[mikegold10]

Yes. That is why you need the formula from the page I linked to, or the one Denis posted. It calculates the position of b3 based on the inputs a1 a2 b1 b2.

It’s all there. You have the basic understanding of vector math needed to implement those functions.

I read that page several times, but could not find the function/code fragment that applies here, given that I start with non-intersecting line segments and am trying to find the point of intersection if I was to logically extend one of them. Perhaps you are extrapolating one of the functions/code fragments on that page in a way I don’t see, in which case I would appreciate if you spell out the details or at least tell me which example on that page is of relevance to my problem.

[Senorpablo]

His code is for 2d intersection. The page I linked to has 3d intersection.

To calculate which line needs to be extended, you could test to see what line b3 already lies on. There is code for point on a line on that page or on the internet.

If b3 is on line b, you need to extend a. If b3 lies on line a, extend b.

[Senorpablo]

From this page:

Geometrical calculations : points, lines, planes : intersections, distances, angles

I am trying to collect the most usual functions for the geometrical calculations : Intersection point, projection, distance, angle, … Of course there are many Web sites about this, but I do not seek the mathematical formulas but functions ‘ready-to-use’ in maxscript. I start by giving the formulas which I know already. If you know other formulas do not hesitate to add them. Let’s say that you have 4 points: pA=[ax,ay,az] pB=[bx,by,bz] pC=[cx,cy,cz] pD=[dx,dy,dz] With these points you c…

Line-Line Intersection : intersection of two lines AB and CD:

fn lineLineIntersect pA pB pC pD = (
local a=pB-pA
local b=pD-pC
local c=pC-pA
local cross1 = cross a b
local cross2 = cross c b
pA + ( a*( (dot cross2 cross1)/((length cross1)^2) ) )
)

[mikegold10]

From this page:
Geometrical calculations : points, lines, planes : intersections, distances, angles

Line-Line Intersection : intersection of two lines AB and CD:

fn lineLineIntersect pA pB pC pD = (
local a=pB-pA
local b=pD-pC
local c=pC-pA
local cross1 = cross a b
local cross2 = cross c b
pA + ( a*( (dot cross2 cross1)/((length cross1)^2) ) )
)

His code is for 2d intersection. The page I linked to has 3d intersection.

To calculate which line needs to be extended, you could test to see what line b3 already lies on. There is code for point on a line on that page or on the internet.

If b3 is on line b, you need to extend a. If b3 lies on line a, extend b.

I know that B3 is on segment b, that’s given. I need to know where it is on segment b, the coordinates of B3. I can’t extend a without knowing how much is enought to extend it by, that’s the problem with that approach. I know that the amount is (at least) (length c), but I don’t have c.

[Senorpablo]

You’re getting hung up on something.

The function I just posted returns the position of B3. It is literally exactly what you asked for in your first post. It is the content for the skeleton function you wrote! Just try it.

You don’t need to extend a! You can if you want to, and it’s simple enough, but you’re overthinking it. Just set the position of a2 to b3.

If you insist on extending a, it would be:

newline = a1 + normalize (a2 -a1) * length (b3-a1)

or if you just want the portion c:

lineC = a2 + normalize (a2 -a1) * length (b3-a2)

But in practice, both those methods just give you the position b3, which you already know.

That’s it.

[mikegold10]

You’re getting hung up on something.

The function I just posted returns the position of B3. It is literally exactly what you asked for in your first post. It is the content for the skeleton function you wrote! Just try it.

You don’t need to extend a! You can if you want to, and it’s simple enough, but you’re overthinking it. Just set the position of a2 to b3.

If you insist on extending a, it would be:

newline = a1 + normalize (a2 -a1) * length (b3-a1)

or if you just want the portion c:

lineC = a2 + normalize (a2 -a1) * length (b3-a2)

But in practice, both those methods just give you the position b3, which you already know.

That’s it.

OK, I will give it a try over the weekend for various test segments a and b to see whether it works for all cases.

[Serejah]

also check out one of these

	fn lineLineIntersect pA pB pC pD =
	(
		local a=pB-pA
		local b=pD-pC
		local c=pC-pA
		local cross1 = cross a b
		local cross2 = cross c b
		pA + ( a*( (dot cross2 cross1)/((length cross1)^2) ) )
	)


	shp1 = SplineShape wirecolor:orange vertexTicks:on
	addNewSpline shp1
	addKnot shp1 1 #corner #line [0,0,0]
	addKnot shp1 1 #corner #line [20,0,0]
	updateShape shp1

	shp2 = SplineShape wirecolor:orange vertexTicks:on
	addNewSpline shp2
	addKnot shp2 1 #corner #line [10,5,0]
	addKnot shp2 1 #corner #line [10,25,0]
	updateShape shp2

	pt = point size:2 centermarker:off axistripod:off cross:off box:on wirecolor:yellow

	deleteAllChangeHandlers id:#xxx
	when geometry #( shp1, shp2 ) changes id:#xxx do
	(
		pt.pos = lineLineIntersect (getKnotPoint shp1 1 1) (getKnotPoint shp1 1 2) (getKnotPoint shp2 1 1) (getKnotPoint shp2 1 2)
	)

[denisT]

i made another toy too
https://forums.autodesk.com/t5/3ds-max-programming/help-with-maxscript-to-find-where-a-segment-would-intersect/m-p/9024604#M24374