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

[kar55734]

Please refer to the following image when reading the description of the problem:

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
)

Thank you for your help.

[miauuuu]

The answer is here: https://forums.cgsociety.org/t/geometrical-calculations-points-lines-planes-intersections-distances-...

[istan]

or there:

https://www.geometrictools.com/Source/Mathematics.html

I generally also suggest this one:

https://www.amazon.com/Geometric-Computer-Graphics-Morgan-Kaufmann/dp/1558605940

[kar55734]

Actually, this specific problem is not addressed at any of the links mentioned above with the possible exception of the "Geometric Tools for Computer Graphics" book, which I own but it is a very hard to understand technical book with uncommented C source code, for the simple reason that the line segment being discussed, namely a, does not (yet) intersect the other line-segment, b. That is the problem here - to make it intersect via extension. If I knew the (minimal) length of segment c to make it intersect, the problem would be trivial to solve!

All of the discussions/examples/solutions at the links posted above assume either an existing intersection or a non-intersection due to the lines, rays, or line segments being skewed/parallel.

This particular problem involves a logical extension of a line segment (i.e., a) in a particular direction (i.e., along one of its two potential co-linear direction vectors, since the line can be extended in either direction and it may not be clear which is the right one) where said extension is of unknown length to a potential intersection point with another line segment (i.e., b) at an unknown and to be determined intersection point, B3.

[denisT.MaxDoctor]

i posted the answer on the CGTalk forum.. but can it repeat here:

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).

[kar55734]

I am not sure what you mean by in and out of bounds, but it appears to me that you are always setting the z coordinate of the (potential) point of intersection to zero, which cannot possibly be right, unless you are working in a reference coordinate system that is not World as mentioned in my problem statement or are assuming that the two line-segments in question lie on the plane defined by the equation z=0, which is not always the case.

[denisT.MaxDoctor]

IT'S 2D solution. as I said at the top of the post and the name of the function says the same.

you can project the 3D vectors on any plane (which makes it 2D where Z is zero).  

Do you need additional details on algebra?

[denisT.MaxDoctor]

the intersection of segments is a planar task in general... it is difficult for me to add something else to this

[kar55734]

---

@denisT.MaxDoctor wrote:

IT'S 2D solution. as I said at the top of the post and the name of the function says the same.

you can project the 3D vectors on any plane (which makes it 2D where Z is zero).  

Do you need additional details on algebra?

---

Well, I did state in my original problem, "... and let’s assume all coordinates are in World space," so yes apparently my "algebra details" are lacking, since I am looking for the intersection point in absolute Rᶾ space.

[denisT.MaxDoctor]

get a toy, play ...

try(destroydialog InterTest) catch()
rollout InterTest "Ray Segment Intersect" width:191
(
	checkbox flat_cb "Flat (Z = 0)"
	
	button create_test_bt "Create 4 Points" width:180 offset:[0,4]
	button intersect_bt "Intersect" width:180 offset:[0,6]
	
	label info_lb "" align:#center offset:[0,4]
	
	local a0, a1, b0, b1, c0

	fn _raySegmentIntersect p dir A B &bounds: =  
	(
		pb = B - A
		pc = A - p
		c1 = cross dir pb
		c2 = cross pc pb
		pt = p + dir * (dot c2 c1)/(dot c1 c1) 
		_sign = dot dir (pt - p)
		
		len = length pb
		bounds = if (length (pt - A) > len or length (pt - B) > len) then 0 else (if _sign < 0 then -1 else 1)
			
		pt
	)	

	on create_test_bt pressed do undo "Create" on 
	(
		delete objects
		
		z = if flat_cb.checked then 0 else 200
		
		a0 = point name:#a0 pos:(random -[200,200,z] [200,200,z]) size:40 wirecolor:yellow
		a1 = point name:#a1 pos:(random -[200,200,z] [200,200,z]) size:40 wirecolor:(yellow * 0.8)

		b0 = point name:#b0 pos:(random -[200,200,z] [200,200,z]) size:40 wirecolor:green
		b1 = point name:#b1 pos:(random -[200,200,z] [200,200,z]) size:40 wirecolor:(green * 0.8)
	)

	on intersect_bt pressed do undo "Intersect" on try 
	(
		p0 = _raySegmentIntersect a1.pos (normalize (a0.pos - a1.pos)) b0.pos b1.pos bounds:&b
		
		bounds = (if b == 0 then #out else if b == 1 then #in else #off)	
		info_lb.text = bounds as string
			
		format "pos:% bounds:%\n" p0 bounds	
		c0 = point pos:p0 size:80 wirecolor:(random red orange)
	)
	catch()

)
createdialog InterTest

... and find a time to learn Algebra 😉