THREE.js raycasting very slow against single > 500k poly (faces) object, line intersection with globe

Question

in my project I have a player walk around a globe. The globe is not just a sphere, it has mountains and valleys, so I need the players z position to change. For this I'm raycasting a single ray from player's position against a single object (the globe) and I get the point they intersect and change players position accordingly. I'm only raycasting when the player moves, not on every frame.

For a complex object it takes forever. It takes ~200ms for an object with ~1m polys (faces) (1024x512 segments sphere). Does raycasting cast against every single face ?

Is there a traditional fast way to achieve this in THREE, like some acceleration structure (octree? bvh? -- tbh from my google searches I haven't seem to find such a thing included in THREE) or some other thinking-out-of-the-box (no ray casting) method?

        var dir = g_Game.earthPosition.clone();
        var startPoint = g_Game.cubePlayer.position.clone();
        var directionVector = dir.sub(startPoint.multiplyScalar(10));
        g_Game.raycaster.set(startPoint, directionVector.clone().normalize());
        var t1 = new Date().getTime();
        var rayIntersects = g_Game.raycaster.intersectObject(g_Game.earth, true);
        if (rayIntersects[0]) {
            var dist = rayIntersects[0].point.distanceTo(g_Game.earthPosition);
            dist = Math.round(dist * 100 + Number.EPSILON) / 100;
            g_Player.DistanceFromCenter = dist + 5;
        }
        var t2 = new Date().getTime();
        console.log(t2-t1);

Thank you in advance

Acetometer

Answer 1

I think you should pre-render the height map of your globe into a texture, assuming your terrain is not dynamic. Read all of it into a typed array, and then whenever your player moves, you only need to back-project her coordinates into that texture, query it, offset and multiply and you should get what you need in O(1) time.

It's up to you how you generate that height map. Actually if you have a bumpy globe, then you should probably start with height map in the first place, and use that in your vertex shader to render the globe (with the input sphere being perfectly smooth). Then you can use the same height map to query the player's Z.

Separates

height map will be either not accurate or huge (or both) – Backrest

@AlexKhoroshylov: to mitigate this, one can also consider a grid in texture coordinates (in fact spherical coordinate angles), and for every grid cell write the list of triangles that project onto it. – Coarctate

Answer 2

Do not use three.js Raycaster.

Consider Ray.js that offers function intersectTriangle(a, b, c, backfaceCulling, target)

Suggested optimizations:

1. If player starts from some known positions ⇒ you must know his initial height, − no need to raycast (or just do one time full mesh slow intersection)

2. if player moves with small steps ⇒ next raycast will most likely intersect the same face as before.

Optimization #1 − remember previous face, and raycast it first.

3. if player does not jump ⇒ next raycast will most likely intersect the adjacent face to the face where player was before.

Optimization #2 − build up a cache, so that given a face idx you could retrieve adjacent faces in O(1) time.

This cache may be loaded from the file, if your planet is not generated in real time.

---

So with my approach on each move you do O(1) read operation from cache and raycast 1-6 faces.

Win!

Backrest

Answer 3

For a complex object it takes forever. It takes ~200ms for an object with ~1m polys (faces) (1024x512 segments sphere). Does raycasting cast against every single face ?

Out of the box THREE.js does check every triangle when performing a raycast against a mesh and there are no acceleration structures built into THREE.

I've worked with others on the three-mesh-bvh package (github, npm) to help address this problem, though, which may help you get up to the speeds your looking for. Here's how you might use it:

import * as THREE from 'three';
import { MeshBVH, acceleratedRaycast } from 'three-mesh-bvh';

THREE.Mesh.prototype.raycast = acceleratedRaycast;

// ... initialize the scene...

globeMesh.geometry.boundsTree = new MeshBVH(globeMesh.geometry);

// ... initialize raycaster...

// Optional. Improves the performance of the raycast
// if you only need the first collision
raycaster.firstHitOnly = true;
const intersects = raycaster.intersectObject(globeMesh, true);

// do something with the intersections

There are some caveats mentioned in the README so keep those in mind (the mesh index is modified, only nonanimated BufferGeometry is supported, etc). And there's still some memory optimization that could be done but there are some tweakable options to help tune that.

I'll be interested to hear how this works for you! Feel free to leave feedback in the issues on how to improve the package, as well. Hope that helps!

Alembic

Answer 4

Edit: Danger! This may cause someone's death one day. The edge case I see here is the nearest collision will be not be seen because searchRange will not contain the nearest triangle but will contain the second nearest one returning it as the closest one. I.e. a robotic arm may stop nearby the torso instead of stopping at the arm right in front of it.

anyway

Here's a hack when raycasting not too far from the previous result i.e. during consecutive mousemove events. This will not work for completely random rays

Mesh raycast supports drawRange to limit how many triangles will be searched. Also each raycast result comes with faceIndex telling which triangle was hit. If you're continuously looking for raycasts i.e. with mousemove or there's a laser linearly scanning a mesh you can first search the area nearby* the previous hit.

• triangles' distance in the data may look like they're neighbours but it's not guaranteed they are sorted in any way. Still it's very possible that the close ones in the data are close in space.

let lastFaceIndex = null
const searchRange = 2000 * 3

function raycast(mesh, raycaster) {
  // limited search
  if (lastFaceIndex !== null) {
    const drawRange = mesh.geometry.drawRange
    drawRange.start = Math.max(0, lastFaceIndex * 3 - searchRange)
    drawRange.count = searchRange * 2
    const intersects = raycaster.intersectObjects([mesh]);
    drawRange.start = 0
    drawRange.count = Infinity
    if (intersects.length) {
        lastFaceIndex = intersects[0].faceIndex
        return intersects[0]
    }
  }

  // regular search
  const intersects = raycaster.intersectObjects([mesh]);
  if (!intersects.length) {
    lastFaceIndex = null
    return null
  }
  lastFaceIndex = intersects[0].faceIndex
  return intersects[0]
}

Wheatley