[SOLVED] How to find intersection between two Rays?

Questions
1

Not a math guy here. The title refers to Rays rather than line segments is only because I “think” I’ll need to work with two Rays.

Anyhow, Given two line segments on the same plane and assuming they do not currently intersect with each other, I want to check if two line segments can/will eventually intersect.

if they can intersect, where does the intersection occur.

I only care about checking against their direction from start to end,

What’s the best way to do this? I looked at the THREE.Ray class and don’t see a obvious name that would allow me to perform such a check like Ray.intersectRay(Ray).

here’s a jsfiddle displaying 2 line segment.
https://jsfiddle.net/blackstrings/ap8ngsqz/
image

2

Maybe you can adapt that.
https://www.geeksforgeeks.org/program-for-point-of-intersection-of-two-lines/

see class Test

even more

I found there: http://walter.bislins.ch/blog/index.asp?page=Schnittpunkt+zweier+Geraden+berechnen+(JavaScript)

function IntersectLines( P, r, Q, s ) {
  // line1 = P + lambda1 * r
  // line2 = Q + lambda2 * s
  // r and s must be normalized (length = 1)
  // returns intersection point O of line1 with line2 = [ Ox, Oy ] 
  // returns null if lines do not intersect or are identical
  var PQx = Q[0] - P[0];
  var PQy = Q[1] - P[1];
  var rx = r[0];
  var ry = r[1];
  var rxt = -ry;
  var ryt = rx;
  var qx = PQx * rx + PQy * ry;
  var qy = PQx * rxt + PQy * ryt;
  var sx = s[0] * rx + s[1] * ry;
  var sy = s[0] * rxt + s[1] * ryt;
  // if lines are identical or do not cross...
  if (sy == 0) return null;
  var a = qx - qy * sx / sy;
  return [ P[0] + a * rx, P[1] + a * ry ];
}
3 Likes
3

Related:
http://jsfiddle.net/justin_c_rounds/Gd2S2/light/

2 Likes
4

While geeksforgeeks.org link works for Scenario A, it fails on Scenario B.
I’ll try the link provided by @prisoner849
and I start to wonder, should this be a feature on the Ray class to make it easier for users like me :stuck_out_tongue:

image
image707×806 5.87 KB

Update: the link example justin_c_rounds/Gd2S2/light/ while works also fails in scenario B test.

5

Hm, what’s the problem with the solution, provided by @hofk?
If you want to determine, that the intersection is not so-called “false”, then just check that the dot-product for both vectors of lines and the point of intersection is greater than 0.

Something like this, having found the point of intersection:

function isPositive( p1, p2, pi ){ // all parameters are THREE.Vector3()
  let v1 = new THREE.Vector3().copy( p2 ).sub( p1 );
  let v2 = new THREE.Vector3().copy( pi ).sub( p1 );
  return v1.dot( v2 ) >= 0;
}

var line1res = isPositive( line1Start, line1End, pointOfIntersection );
var line2res = isPositive( line2Start, line2End, pointOfIntersection );

if ( line1res && line2res ) {
  // do something when the intersection is not "false" as both results are "true"
}
else { // 
  // do something when the intersection is "false" as one of results is "false"
}

Just a short snippet for understandind of dot-product, that you can check with jsfiddle or codepen:

var v1 = new THREE.Vector3( 1, 0, 0 );
var v2 = new THREE.Vector3( 1, 1, 0 ).normalize();
var dot = v1.dot( v2 );
console.log( dot );
1 Like
6

Thanks @prisoner849 and @hofk !!
The missing piece was to use the dot product (which I still have to get my head around) to get the result I was looking for. the method name could use a better name if anyone uses it.

function isPositive( start, end, intersection ){ // all parameters are THREE.Vector3()
  let v1 = new THREE.Vector3().copy( end ).sub( start );
  let v2 = new THREE.Vector3().copy( intersection ).sub( start );
  return v1.dot( v2 ) >= 0;
}

// checks if two line segments will intersect on a point 
// when traveling in one specific direction from start to end
// but not in the direction from end to start
// params (THREE.Line3, THREE.Line3)
function getIntersectionOnAPoint(line1, line2)
{ 
  var intersection = null;
  var A = line1.start;
  var B = line1.end;
  var C = line2.start;
  var D = line2.end;

  // Line AB represented as a1x + b1y = c1 
  var a1 = B.y - A.y; 
  var b1 = A.x - B.x; 
  var c1 = a1*(A.x) + b1*(A.y); 

  // Line CD represented as a2x + b2y = c2 
  var a2 = D.y - C.y; 
  var b2 = C.x - D.x; 
  var c2 = a2*(C.x)+ b2*(C.y); 

  var determinant = a1*b2 - a2*b1; 

  if (determinant == 0) { 
    // The lines are parallel.
  } else { 
      var x = (b2*c1 - b1*c2)/determinant; 
    var y = (a1*c2 - a2*c1)/determinant; 
    intersection = new THREE.Vector3(x, y); 
  }
  
  // if there is an intersection. verify intersection occurs on the two line segments
  // when calculating from start to end
  if (intersection) {
  	var line1result = isPositive( line1.start, line1.end, intersection );
    var line2result = isPositive( line2.start, line2.end, intersection );
    if ( line1result && line2result ) {
      // do nothing when the intersection is not "false" as both results are "true"
    }
    else { // 
      // set intersection to null when the intersection is "false" as one of results is "false"
      intersection = null;
    }
  }
  return intersection;
}

more tweaks would be needed but do you guys think such a function deserves to be on the Ray class?
so someone can do

var ray1 = new THREE.Ray(); // set the origin and direction
var ray2 = new THREE.Ray(); // set the origin and direction
var intersection = ray1.intersectRay(ray2); // returns null if no intersection
7

Dunn and Parberry presented in 3D Math Primer for Graphics and Game Development a formula for the intersection test of two rays in 3D. They also mentioned the following:

Of course, in practice, an exact intersection rarely occurs due to floating point imprecision…

Apart from that, you need a special scenario so that rays or line segments actually intersect in 3D because lines have an infinitely small width. Because of this, I’m a bit sceptical about a new method in the core. If three.js would be a 2D graphics library, I would have no objections. But testing rays or line segments in 3D is more special and not that common like a Ray/Plane, Ray/Sphere or Ray/AABB intersection test.

3 Likes
8

Because I’m interested, I’ve made a little programme. It calculates the distance of skewed straight lines with two different formulas. With determinants and with cross vectors.

Then you can set an accuracy limit and determine the intersection point.
If there are two trajectories, you can use the size of the objects to detect collisions.

To simplify things, you can only change the direction of a line, the component x.

20190311-0958-48986

It can be tested there http://threejs.hofk.de/LinesDistance/LinesDistance.html

The full code:

  <!DOCTYPE html>

<head>
  <title> LinesDistance </title>
  <meta charset="utf-8" />
</head>

<body>
	mp.x <input type="range" id="mpx" min="0" max="1" value="0.725" step="0.0001" style="width: 90%;"> 
	<div id="distance"> </div> 
	<div id="Pn"> </div> 
	<div id="Qn"> </div>
</body>

<script src="../js/three.min.102.js"></script>
<script src="../js/OrbitControls.js"></script>

<script>

// @author hofk

var mpx = document.getElementById( 'mpx' );
mpx.onchange = refresh;

var dpnqnDet, pnDet, qnDet; // uses determinant
var dpnqnCr, pnCr, qnCr; // uses cross vectors
var dist; // uses formula distance

var scene = new THREE.Scene();
var camera = new THREE.PerspectiveCamera( 55, window.innerWidth / window.innerHeight, 0.1, 1000 );
camera.position.set( 0, 10, 40 );
var renderer = new THREE.WebGLRenderer( { antialias: true } );
renderer.setSize( window.innerWidth, window.innerHeight );
renderer.setClearColor( 0xaaaaaa, 1 );	
var container = document.createElement( 'div' );
document.body.appendChild( container );
container.appendChild( renderer.domElement ); 
var controls = new THREE.OrbitControls( camera, renderer.domElement );

var axesHelper = new THREE.AxesHelper( 28 );
scene.add( axesHelper );
var grid = new THREE.GridHelper( 50, 50 );
scene.add( grid );

var gLineP = new THREE.BufferGeometry( );
gLineP.positions = new Float32Array( 6 );
gLineP.addAttribute( 'position', new THREE.BufferAttribute( gLineP.positions, 3 ).setDynamic( true )   );
lineP  = new THREE.Line( gLineP, new THREE.LineBasicMaterial( { color: 0x00ffff, side: THREE.DoubleSide } ) );

var p = new THREE.Vector3( -15, 12, -5 );
var mp = new THREE.Vector3( 35, -8 , 15 ); // mp.x can be changed with slider

gLineP.positions[ 0 ] = p.x;
gLineP.positions[ 1 ] = p.y;
gLineP.positions[ 2 ] = p.z;

gLineP.positions[ 3 ] = p.x + mp.x;
gLineP.positions[ 4 ] = p.y + mp.y;
gLineP.positions[ 5 ] = p.z + mp.z;

scene.add( lineP );

var gLineQ = new THREE.BufferGeometry( );
gLineQ.positions = new Float32Array( 6 );
gLineQ.addAttribute( 'position', new THREE.BufferAttribute( gLineQ.positions, 3 )  );
lineQ  = new THREE.Line( gLineQ, new THREE.LineBasicMaterial( { color: 0xffff00, side: THREE.DoubleSide } ) );

var q = new THREE.Vector3( -12, 14, -15 );
var mq = new THREE.Vector3( 34, -12, 33 );

gLineQ.positions[ 0 ] = q.x;
gLineQ.positions[ 1 ] = q.y;
gLineQ.positions[ 2 ] = q.z;

gLineQ.positions[ 3 ] = q.x + mq.x;
gLineQ.positions[ 4 ] = q.y + mq.y;
gLineQ.positions[ 5 ] = q.z + mq.z;

scene.add( lineQ );

refresh( );

animate();

function animate() {

	requestAnimationFrame( animate );
	renderer.render( scene, camera );
	controls.update();
	
}

function linesDistance( ) { // mp and mq  non-collinear

	var pq = new THREE.Vector3( ).subVectors( q, p );
	var n = new THREE.Vector3( ).crossVectors( mp, mq ).normalize( );
	var d = pq.dot( n );
	
	return Math.abs( d );
	
} 

function closestPointsDet( ) { // mp and mq  non-collinear

	// using determinant
 
 	var qp = new THREE.Vector3( ).subVectors( p, q );
	
	var qpDotmp = qp.dot( mp );
	var qpDotmq = qp.dot( mq );
	var mpDotmp = mp.dot( mp );
	var mqDotmq = mq.dot( mq );
	var mpDotmq = mp.dot( mq );	
	
	var detp = qpDotmp * mqDotmq - qpDotmq * mpDotmq;
	var detq = qpDotmp * mpDotmq - qpDotmq * mpDotmp;
	
	var detm = mpDotmq * mpDotmq - mqDotmq * mpDotmp; 
	
	pnDet = p.clone( ).add( mp.clone( ).multiplyScalar( detp / detm ) );
	qnDet = q.clone( ).add( mq.clone( ).multiplyScalar( detq / detm ) );
	
	dpnqnDet = pnDet.clone( ).sub( qnDet ).length( );
		
}

function closestPointsCross( ) { // mp and mq  non-collinear

	// using cross vectors
	
	var qp = new THREE.Vector3( ).subVectors( p, q );
	var pq = qp.clone( ).multiplyScalar( -1 );
	
	var npq = new THREE.Vector3( ).crossVectors( mp, mq ).normalize( );
	var nqp = new THREE.Vector3( ).crossVectors( mq, mp ).normalize( );
	
	var n1 = new THREE.Vector3( ).crossVectors( mp, nqp ).normalize( );
	var n2 = new THREE.Vector3( ).crossVectors( mq, npq ).normalize( );
	
	var qpDotn1 = qp.dot( n1 );
	var pqDotn2 = pq.dot( n2 );
	
	var mpDotn2 = mp.dot( n2 );
	var mqDotn1 = mq.dot( n1 );
		
	pnCr = p.clone( ).add( mp.clone( ).multiplyScalar( pqDotn2 / mpDotn2 ) ); 
	qnCr = q.clone( ).add( mq.clone( ).multiplyScalar( qpDotn1 / mqDotn1 ) ); 
	
	dpnqnCr = pnCr.clone( ).sub( qnCr ).length( );
	
}

function refresh( ) { 
	
	mp.x = mpx.value * 50;
	
	gLineP.positions[ 3 ] = p.x + mp.x;
	gLineP.attributes.position.needsUpdate = true;
	
	closestPointsDet( );	
	closestPointsCross( );
	
	Pn.innerHTML = ' Pn Det ( ' + pnDet.x + ', '+ pnDet.y + ', '+ pnDet.z + ' ) <==> Pn Cr ( ' + pnCr.x + ', '+ pnCr.y + ', '+ pnCr.z + ' ) ';
	Qn.innerHTML = ' Qn Det ( ' + qnDet.x + ', '+ qnDet.y + ', '+ qnDet.z + ' ) <==> Qn Cr ( ' + qnCr.x + ', '+ qnCr.y + ', '+ qnCr.z + ' ) ';	
	
	dist = linesDistance( );	
	distance.innerHTML = 'distance: dPQ Determinant: ' + dpnqnDet +  '  <==>   function linesDistance( ) :' + dist + '   <==> dPQ Cross: ' + dpnqnCr;
	
}</script>

</html>
1 Like