Raycasting with an entire line..?

I have a geometry and a line3. The line3 is “hovering” a slight bit above the surface of the geometry, and I want to find the faces that would be touching the line3 if it was to be brought down and wrapped on to the surface.

Of course because I cannot “wrap” my line3, I am raycasting the points of the line3 on to the geometry, and finding the intersecting points.

This allows me to detect face 1 and face 4, but I fail to detect face 2 and 3 because there is no point on the line3 to raycast from, other than its starting and ending points.

How can I come up with an algorithm that allows me to detect all the faces that the line3 would “cut across” the surface, if wrapped on to it?

image

I can find face 1 and 4 because I have some points to raycast from (i.e., the two white dots, but I cannot find face 2 and 3 because I do not have any points to raycast from.

1 Like

/cc

It might be easier to think of the line terms of a plane (parallel to your projection direction and going through the end points of the line.

Here’s a method I have been working to get intersection which contains part of what you might find useful.

function intersectPlane(mesh, plane) {

	let meshverts = [];

	let v;
	// scale it with parent's scale
	mesh.geometry.vertices.forEach(vt => {
		v = new THREE.Vector3(	vt.x * mesh.parent.scale.x, 
								vt.y * mesh.parent.scale.y, 
								vt.z * mesh.parent.scale.z
							 );
		meshverts.push(v);
	});

	// collect faces
	let faces = [];
	let face = null;
	mesh.geometry.faces.forEach(f => {
		face = [meshverts[f.a], meshverts[f.b], meshverts[f.c]];
		faces.push(face);
	});

	// collect intersection points
	let intVerts = [];
	let pt, ln;
	faces.forEach(f => {
		ln = new THREE.Line3(f[0], f[2]);
		pt = plane.intersectLine(ln);
		if (typeof pt !== 'undefined') {
			intVerts.push(pt);
		}
		ln = new THREE.Line3(f[1], f[2]);
		pt = plane.intersectLine(ln);
		if (typeof pt !== 'undefined') {
			intVerts.push(pt);
		}
		ln = new THREE.Line3(f[0], f[1]);
		pt = plane.intersectLine(ln);
		if (typeof pt !== 'undefined') {
			intVerts.push(pt);
		}
	});


	if(intVerts.length < 3) {
		throw `Invalid mesh`;
	}


	// get center to calculate sorting origin
	let center = new THREE.Vector3();
	intVerts.forEach(vt => {
		center.x += vt.x;
		center.y += vt.y;
		center.z += vt.z;
	});
	center.x /= intVerts.length;
	center.y /= intVerts.length;
	center.z /= intVerts.length;

	// TODO: check center is contained inside polyline

	// remove duplicates
	let intVertSet = new Set();
	let reallocIntVert = [];
	for(let i=0; i<intVerts.length; i++) {
		let k = JSON.stringify(intVerts[i]);
		if (!intVertSet.has(k)) {
			reallocIntVert.push(intVerts[i]);
			intVertSet.add(k);
		}
	}
	intVerts = reallocIntVert;

	// sort it cyclic/acyclic
	let fin_order = sortPoints(intVerts, center, plane.normal);
	// add last point again to close the loop
	fin_order.push(fin_order[0].clone());


	let lineGeom = new THREE.Geometry();
	lineGeom.vertices = fin_order;
	let lineMat = new THREE.LineBasicMaterial({ color: 0x000000 });
	let line = new THREE.Line(lineGeom, lineMat);


	return line;

}

I have just copied it here, didn’t run it. Not optimized or anything either.
Hope it helps.

Not sure if this is what you were trying to attempt nor if this is any way efficient. this involves creating a little custom Face object to contain its lines, so when looping you can know what face was hit based on intersection of its lines.

The hit faces are logged in the console. Change the ray start and end points to test different cast.

Only thing is, this example does not cover when the line is all within a triangle and doesn’t touch any triangle edges. if you end up going this route, you’ll have to combine this with your current solution or something along the line of detecting a point inside triangle.

https://jsfiddle.net/blackstrings/drh96ztn/
image

you have 4 points, 2 defining the line and 2 where the line would go. You could, as @amitlzkpa suggested, create a plane through these points.
Find lines that cut the geometry through that plane.
Then you’d need to bisect the plane along the line.
Break any geometry cutting lines that intersect the plane dividing line - create new lines from the broken ones.
Discard lines that are below the plane dividing line, keep the rest.

now you just need to figure out which triangles (faces) those lines belong to.

One more alternative - just cast a bunch more rays from original position to the final one. This is quite imprecise, but given a lot of rays - you will get pretty close results. Plus it’s a super-simple solution.

I love how you created your 3D model, it looks almost like it’s made out of paper! How did you get the shadows to look so good?